交互決定ツリー: 基礎と応用

By Fouad Sabry

交互デシジョン ツリーとは

機械学習によって学習できる分類戦略は、交互デシジョン ツリー (ADTree) として知られています。 これは、デシジョン ツリーの強化と一般化につながり、同時にデシジョン ツリーを一般化します。

メリット

(I) 以下のトピックに関する洞察と検証 :

第 1 章: 交互デシジョン ツリー

第 2 章: デシジョン ツリー学習

第 3 章: AdaBoost

第 4 章: ランダム フォレスト

第 5 章: 勾配ブースティング

第 6 章: 命題計算

第 7 章: サポート ベクター マシン

第 8 章: 分析方法 Tableaux

第 9 章: ブール充足可能性アルゴリズム ヒューリスティック

第 10 章: 乗算重み更新方法

(II) 交互デシジョン ツリーに関する一般のよくある質問に回答します。

(III) 多くの分野における交互デシジョン ツリーの使用例の実例。

(IV) 360 の各業界の 266 の新興テクノロジーを簡潔に説明する 17 の付録。

本書の対象者

専門家、学部生および大学院生、愛好家、趣味愛好家、および以下のような人々 あらゆる種類の交互デシジョン ツリーに関する基本的な知識や情報を超えたいと考えています。

 

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: Jun 23, 2023

Book preview

第 1 章: 交互のデシジョン ツリー

分類のための機械学習手法は、交互決定木 (ADTree) と呼ばれます。これは、決定木のブーストと一般化につながります。

ADTree は、単一の数値を持つ予測ノードと、述語条件を提供する決定ノードで構成されます。ADTree は、すべての予測ノードが真であるすべてのパスをトラバースし、真である決定ノードを追加することによって、インスタンスを分類します。

Yoav FreundとLlew MasonがADTreesを発表しました。Weka と JBoost に実装があります。

決定木または決定切り株は、元のブースティングアルゴリズムの弱い仮説としてよく利用されていました。

説明のために、決定切り株をブーストすると、 T 重み付けされた決定切り株のセット ( T ここで、 はブースティング反復回数) が作成され、その後、最終的な分類の重みに基づいて投票が投じられます。

個々の判断は、データをどれだけうまく分類できるかに基づいて重み付けされます。

単純な学習者をブーストすると、構造化されていない T 一連の仮説が生成され、属性間の接続の推論が妨げられます。

以前の反復で形成された仮説を構築することを義務付けることにより、交互の決定木は一連の仮説構造を提供します。

仮説とその「親」の間の接続に基づいて、結果の仮説のコレクションをツリーとして表すことができます。

反復ごとにデータに異なる分布が与えられるという事実は、ブーストアルゴリズムのもう一つの重要な側面です。誤って分類されたオカレンスには重みが増し、正しく分類されたインスタンスには重みが小さくなります。

決定ノードと予測ノードは、交互の決定木を構成します。述部条件は、決定ノードによって指定されます。予測ノードには 1 つの番号しかありません。予測ノードは、常に ADTrees のルートとリーフとして機能します。ADTrees は、すべての決定ノードが真であるすべての経路を走査し、移動した予測ノードを追加することで、インスタンスを分類します。CART (分類および回帰ツリー) や C4.5 などの二項分類ツリーでは、インスタンスがツリーを 1 つのパスで通過しますが、このタイプのツリーには複数の分類レベルがあります。

スパムベースのデータセットを使用して、JBoost を使用して次のツリーを作成しました。この場合、通常の電子メールは 1 としてコード化され、スパムは 1 としてコード化されます。

An ADTree for 6 iterations on the Spambase dataset.

1 つのインスタンスの詳細の一部を次の表に示します。

インスタンスが渡すすべての予測ノードを合計すると、スコアが与えられます。上記のシナリオでは、スコアは次のように決定されます。

最終スコア 0.657 が肯定的であるため、発生はスパムとして分類されます。値の大きさは、予測の信頼度のバロメーターとして機能します。ADTreeによって検出された特性のコレクションの3つの程度の解釈は、元の著者によってリストされています。

予測のために各ノードの容量を個別に評価することができます。

同じパス上のノードのグループを共同効果があると認識することが可能です。

ツリー全体を理解できます。

個々のノードは、スコアが反復ごとのデータの再重み付けを表すため、慎重に解釈する必要があります。

交互決定木アルゴリズムの入力は次のとおりです。

入力のセット (x_1,y_1),\ldots,(x_m,y_m) ここで x_{i} 、 は属性のベクトルであり、 は y_{i} -1 または 1 です。

さらに、インスタンス、入力とも呼ばれます。

各インスタンスに対応する w_{i} 重みのセット。

このルールは、ADTree アルゴリズムのコア コンポーネントです。前提条件、条件、および 2 つのスコアが 1 つのルールを構成します。構文「属性比較>値」を使用する述語は条件です。簡単に言えば、前提条件は条件の論理的な和集合です。ルールを評価するために、2 つのネストされた if ステートメントがあります。

1 if (前提条件)

2 if (条件)

3 score_oneを返す

4 その他

5 score_twoを返す

6 終了の場合

7 その他

8 0を返す

9 終了の場合

アルゴリズムには、いくつかの補助関数も必要です。

W_+(c) 述語を満たすすべての正のラベル付けされた例の重みの合計を返します。 c

W_-(c) 述語を満たすすべての否定的にラベル付けされた例の重みの合計を返します。 c

W(c) = W_+(c) + W_-(c) 述語を満たすすべての例の重みの合計を返します。 c

アルゴリズムは次のようになります。

1 機能 ad_tree

2 入力 m 個のトレーニングインスタンスのセット

3

4 wi = すべての i に対して  1/m

5 a = \frac 1 2 \textrm{ln}\frac{W_+(true)}{W_-(true)}

6 R0 = スコア a と 0、前提条件 true、条件 true を持つルール。

7 \mathcal{P} = \{true\}

8 \mathcal{C} = 考えられるすべての条件のセット

9 の場合 j = 1 \dots T

10 p \in \mathcal{P}, c \in \mathcal{C} 最小化する値を取得する

z = 2 \left( \sqrt{W_+(p \wedge c) W_-(p \wedge c)} + \sqrt{W_+(p \wedge \neg c) W_-(p \wedge \neg c)} \right) +W(\neg p)

11 \mathcal{P} += p \wedge c + p \wedge \neg c

12 a_1=\frac{1}{2}\textrm{ln}\frac{W_+(p\wedge c)+1}{W_-(p \wedge c)+1}

13

a_2=\frac{1}{2}\textrm{ln}\frac{W_+(p\wedge \neg c)+1}{W_-(p \wedge \neg c)+1}

14 Rj =  前提条件 p、条件 c、および重み a1 と a2 を持つ新しいルール

15 w_i = w_i e^{ -y_i R_j(x_i) }

16 終了

Rjの17 リターンセット

セットは {\mathcal {P}} 各反復で 2 つの前提条件によって増加し、後続の各ルールで使用される前提条件に注意することで、ルールのセットのツリー構造を決定できます。

ADTreesは、元の論文の図6に見られるように、ブーストされた決定木やブーストされた決定切り株と同じくらい信頼性が高いことがよくあります。通常、再帰的なパーティション分割アルゴリズムよりもはるかに単純なツリー構造で、同等の精度を実現できます。

{第 1 章終了}

第2章:決定木の学習

決定木を使用した学習は、統計、データマイニング、機械学習の分野で使用される教師あり学習の一種です。この形式主義では、分類または回帰決定木が予測モデルとして使用され、データのコレクションに関する結論を導き出します。[C]ラッシフィケーション決定木 [R]出力決定木 [C]ラッシフィケーション決定木 [D]エキシジョンツリー。

分類木は、目標変数が有限個の値を取ることができる木モデルです。これらのツリー構造では、葉はクラスラベルを示し、ブランチはそれらのクラスラベルにつながる特性の結合を表します。回帰木は、ターゲット変数が連続値を取る可能性がある場合に使用される一種の決定木であり、通常は実数で表されます。より広い意味では、回帰木の概念は、カテゴリシーケンスなど、ペアワイズの非類似性を持つあらゆる種類のオブジェクトに適用できます。

決定木は、選択と意思決定プロセスをグラフィカルかつ明確に反映できるため、意思決定分析に役立つツールです。データ マイニングでは、デシジョン ツリーがデータを説明します (ただし、結果の分類ツリーは意思決定の入力になります)。

データマイニングでは、多くの場合、決定木学習と呼ばれる方法論を利用します。多数の入力要因が与えられたターゲット変数の値を正確に予測できるモデルを構築することが、このプロジェクトの目的です。

決定木は、ケースを分類するために使用できる簡単な形式です。このセクションのために、すべての入力フィーチャに有限の離散ドメインがあり、分類 と呼ばれる単一の目標フィーチャがあると仮定します。「クラス」という用語は、分類の全体的なドメインを構成する個々のコンポーネントを指します。ツリーは、各内部ノード (リーフではないノード) に入力特性のラベルが付けられている場合、決定木または分類ツリーと呼ばれます。入力フィーチャでラベル付けされたノードから発生するアークは、ターゲット フィーチャに割り当てられる可能性のあるすべての値でラベル付けされるか、別の入力フィーチャでラベル付けされた下位決定ノードに移動します。データセットは、ツリーによって特定のクラスまたは特定の確率分布に分類され、ツリーの各リーフには、クラスまたはクラス全体の確率分布のいずれかでラベル付けされています。これは、データセットがこれら2つのカテゴリのいずれかに割り当てられていることを示します(決定木が適切に構築されている場合、クラスの特定のサブセットに偏っています)。

ツリーを構築するには、ツリーのルート ノードとして機能するソース セットを最初にサブセットに分割し、次にツリーの後継子を生成する必要があります。分割は、分類特性によって決定される所定の基準セットに従って行われます。この手法は、再帰的パーティショニングと呼ばれる再帰的な方法で実行され、各派生サブセットに適用されます。ノードのサブセットがターゲット変数の値をすべて同じにした場合、または分割によって予測に値が追加されなくなった場合、再帰は終了に達し、プロセスは完了します。この方法では、デシジョン ツリーをトップダウンで構築します (TDIDT)

データマイニングの分野では、決定木は、特定のデータセットの記述、分類、および一般化を支援するために使用される数学的方法と計算方法の組み合わせとして定義することもできます。

情報は、次の形式のレコードに格納されます。

({\textbf {x}},Y)=(x_{1},x_{2},x_{3},...,x_{k},Y)

従属 Y 変数 は、私たちが理解しようとしている変数であり、それを分類または一般化します。

ベクターは {\textbf {x}} 、特徴等から構成 x_{1},x_{2},x_{3} され、義務を果たす際に採用されるものである。

データ マイニングで使用されるデシジョン ツリーには、主に次の 2 種類があります。

分類ツリー分析の結論は、データが属するクラス(離散)であり、手法はその同名にちなんで名付けられました。

予測結果が実数と見なされる場合 (たとえば、不動産の価格や患者が病院で過ごす時間など)、回帰木分析が使用されます。

分類および回帰ツリー分析の略であるCART分析は、前述のプロセスのいずれかを指すために使用できる包括的なフレーズです。この概念は、1984年にBreimanらによって最初に確立されました。

アンサンブル法と呼ばれることもあるいくつかのアプローチには、多くの決定木の構築が含まれます。

ブーストされた木 新しいトレーニングインスタンスごとに教えて、以前に誤ってモデル化されたトレーニングインスタンスを強調することで、アンサンブルを少しずつまとめます。よくある一例は、AdaBoostです。これらは、回帰分析を行うのに役立ちます。タイプと分類タイプの両方の難しさ。

ブートストラップ集約デシジョンツリー(袋詰めデシジョンツリーとも呼ばれる)と呼ばれる初期のアプローチでは、トレーニングデータを置換して継続的にリサンプリングし、ツリーに投票して最も正確な予測を生成するツリーを確認することで、多くのデシジョンツリーを作成します。

ブートストラップ集計にはいくつかの種類があり、そのうちの 1 つはランダム フォレスト分類器と呼ばれます。

回転フォレスト内のすべての決定木は、最初に入力特性の異なるサブセットに対して主成分分析 (PCA) を実行することによってトレーニングされます。これは回転林で行われます。

最も注目すべき決定木アルゴリズムには、次のものがあります。

ID3 (反復二分法 3)

C4.5 (ID3 の後継)

CART (分類および回帰ツリー)

カイ二乗自動相互作用検出(CHAID)。分類ツリーを構築する場合、この関数は複数のレベルで分割を実行します。