決定木学習

真陽性が偽陽性をどの程度上回っているかを特定するために、シンプルで効果的な指標を使用できます（混同行列を参照）。この指標「陽性正答率の推定値」は、以下のように定義されます。

${\displaystyle E_{P}=TP-FP}$

この式では、真陽性（TP）の総数から偽陽性（FP）の総数を差し引きます。結果として得られる数値は、その特徴量がデータ内で正しく識別できる陽性例の数を推定するものであり、数値が大きいほど、その特徴量がより多くの陽性サンプルを正しく分類できることを意味します。以下は、特定の特徴量の完全な混同行列が与えられた場合に、この指標を使用する方法の例です。

特徴A 混同行列

ここで、TP値は8、FP値は2（表中の下線付きの数字）であることがわかります。これらの数字を式に代入すると、推定値を計算できます。${\displaystyle E_{p}=TP-FP=8-2=6}$つまり、この特徴量に推定値を使用すると、スコアは6になるということです。

ただし、この数値はあくまで推定値であることに注意が必要です。例えば、2つの特徴量の偽陽性（FP）値が両方とも2で、一方の特徴量の真陽性（TP）値が高い場合、式を用いた推定値が高くなるため、その特徴量が他方よりも上位にランク付けされます。特徴量によって陽性サンプル数が異なる場合、この指標を使用すると不正確な結果が生じる可能性があります。これに対処するため、混同行列の値の割合を考慮して実際の真陽性率（TPR）を算出する、感度と呼ばれるより強力な指標を用いることができます。これらの指標の違いは、以下の例に示されています。

この例では、特徴Aの推定値は6、TPRは約0.73でしたが、特徴Bの推定値は4、TPRは0.75でした。これは、一部の特徴の正の推定値が高くても、正の推定値が低い他の特徴と比較すると、その特徴のより正確なTPR値は低くなる可能性があることを示しています。状況やデータおよび決定木に関する知識によっては、問題を迅速かつ容易に解決するために正の推定値を使用することを選択する場合があります。一方、より経験豊富なユーザーは、データの割合と正と分類されるべきすべてのサンプルを考慮に入れるため、TPR値を使用して特徴をランク付けすることを好むでしょう。

ジニ不純度、ジニの多様性指数^{[ 26 ]}、または生物多様性研究におけるジニ・シンプソン指数は、分類木のためのCART（分類回帰木）アルゴリズムで使用されます。ジニ不純度は、セット内のラベルの分布に従ってランダムかつ独立にラベル付けされた場合に、セットからランダムに選択された要素が誤ったラベル付けをされる確率です。ノード内のすべてのケースが単一のターゲットカテゴリに分類される場合に、最小値（ゼロ）に達します。

一連のアイテムについて${\displaystyle J}$階級と相対頻度${\displaystyle p_{i}}$、${\displaystyle i\in \{1,2,...,J\}}$ラベルが付いたアイテムを選択する確率${\displaystyle i}$は${\displaystyle p_{i}}$そして、その項目を誤って分類する確率は${\displaystyle \sum _{k\neq i}p_{k}=1-p_{i}}$ジニ不純度は、各クラスラベルについて、これらの確率のペアごとの積を合計することによって計算されます。

${\displaystyle \operatorname {I} _{G}(p)=\sum _{i=1}^{J}\left(p_{i}\sum _{k\neq i}p_{k}\right)=\sum _{i=1}^{J}p_{i}(1-p_{i})=\sum _{i=1}^{J}(p_{i}-p_{i}^{2})=\sum _{i=1}^{J}p_{i}-\sum _{i=1}^{J}p_{i}^{2}=1-\sum _{i=1}^{J}p_{i}^{2}.}$

ジニ不純度も情報理論的尺度であり、変形係数を持つツァリスエントロピーに対応する。${\displaystyle q=2}$これは物理学では、非平衡、非広範性、散逸性、量子系における情報不足と関連付けられています。極限では$q→1$そこから、通常のボルツマン・ギブスエントロピーまたはシャノンエントロピーが復元される。この意味で、ジニ不純度は、決定木における通常のエントロピー尺度の変形に過ぎない。

ID3、C4.5、C5.0などのツリー生成アルゴリズムで使用される情報利得は、情報理論におけるエントロピーと情報量の概念に基づいています。

エントロピーは以下のように定義される。

${\displaystyle \mathrm {H} (T)=\operatorname {I} _{E}\left(p_{1},p_{2},\ldots ,p_{J}\right)=-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}}$

どこ${\displaystyle p_{1},p_{2},\ldots }$これらは合計が 1 になる分数であり、ツリーの分割によって生じる子ノードに存在する各クラスの割合を表します。^{[ 27 ]}

$$\displaystyle \overbrace {IG(T,a)} ^{\text{情報利得}}=\overbrace {\mathrm {H} (T)} ^{\text{エントロピー（親）}}-\overbrace {\mathrm {H} (T\mid a)} ^{\text{エントロピーの合計（子）}}}$$${\displaystyle =-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}-\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)}$

可能な値の平均${\displaystyle A}$、

$$${\displaystyle \overbrace {E_{A}(\operatorname {IG} (T,a))} ^{\text{期待情報利得}}=\overbrace {I(T;A)} ^{{\text{TとA間の相互情報量}=\overbrace {\mathrm {H} (T)} ^{\text{エントロピー（親）}}-\overbrace {\mathrm {H} (T\mid A)} ^{\text{エントロピーの加重和（子）}}}$$$${\displaystyle =-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}-\sum _{a}p(a)\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)}$

ここで、エントロピーの加重和は次のように与えられる。

${\displaystyle {\mathrm {H} (T\mid A)}=\sum _{a}p(a)\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)}$

つまり、期待される情報利得は相互情報量であり、平均的には、 Tのエントロピーの減少は相互情報量である。

情報利得は、ツリー構築の各ステップでどの特徴に基づいて分割するかを決定するために使用されます。シンプルさが最善であるため、ツリーは小さく保ちたいと考えます。そのためには、各ステップで、最も一貫性のある子ノードが得られる分割を選択する必要があります。一貫性の一般的な尺度は情報と呼ばれ、ビット単位で測定されます。ツリーの各ノードについて、情報値は「例がそのノードに到達した場合に、新しいインスタンスをはいまたはいいえに分類するかどうかを指定するために必要な期待される情報量を表します」。^{[ 27 ]}

4 つの属性(天気(晴れ、曇り、雨)、気温(暑い、穏やか、涼しい)、湿度(高い、普通)、風(あり、なし)) と、バイナリ (はいまたはいいえ) の目的変数play、および 14 個のデータ ポイントを持つデータセットを考えてみましょう。このデータに基づいて決定木を構築するには、4 つの特徴のいずれかで分割された 4 つの木それぞれの情報利得を比較する必要があります。情報利得が最も高い分割が最初の分割として採用され、すべての子ノードがそれぞれ一貫したデータを持つか、情報利得が 0 になるまで処理が続きます。

windyを使って分割による情報利得を求めるには、まず分割前のデータに含まれる情報を計算する必要があります。元のデータには、9 つ​​の「はい」と 5 つの「いいえ」が含まれていました。

${\displaystyle I_{E}([9,5])=-{\frac {9}{14}}\log _{2}{\frac {9}{14}}-{\frac {5}{14}}\log _{2}{\frac {5}{14}}=0.94}$

特徴量windyを使用した分割により、 windy の値が true のノードとwindy の値が false のノードの 2 つの子ノードが生成されます。このデータセットには、windy の値が true のデータポイントが 6 つあり、そのうち 3 つはplay ( playは目的変数) の値が yes で、3 つはplayの値が no です。windyの値が false の残りの 8 つのデータポイントには、no が 2 つと yes が 6 つ含まれています。windy = true ノードの情報は、上記のエントロピー方程式を使用して計算されます。このノードには yes と no が同数あるため、

${\displaystyle I_{E}([3,3])=-{\frac {3}{6}}\log _{2}{\frac {3}{6}}-{\frac {3}{6}}\log _{2}{\frac {3}{6}}=-{\frac {1}{2}}\log _{2}{\frac {1}{2}}-{\frac {1}{2}}\log _{2}{\frac {1}{2}}=1}$

windy = falseのノードには8 つのデータ ポイントがあり、6 つの yes と 2 つの no がありました。したがって、

${\displaystyle I_{E}([6,2])=-{\frac {6}{8}}\log _{2}{\frac {6}{8}}-{\frac {2}{8}}\log _{2}{\frac {2}{8}}=-{\frac {3}{4}}\log _{2}{\frac {3}{4}}-{\frac {1}{4}}\log _{2}{\frac {1}{4}}=0.81}$

分割に関する情報を得るには、各ノードにいくつの観測値が属したかに基づいて、これら2つの数値の加重平均を取ります。

${\displaystyle I_{E}([3,3],[6,2])=I_{E}({\text{windy or not}})={\frac {6}{14}}\cdot 1+{\frac {8}{14}}\cdot 0.81=0.89}$

これで、風の特徴に基づいて分割することで得られる情報利得を計算できます。

${\displaystyle \operatorname {IG} ({\text{windy}})=I_{E}([9,5])-I_{E}([3,3],[6,2])=0.94-0.89=0.05}$

ツリーを構築するには、考えられる各最初の分割の情報利得を計算する必要があります。最適な最初の分割は、最も多くの情報利得を提供するものです。このプロセスは、ツリーが完成するまで、各不純ノードに対して繰り返されます。この例は、Witten et al. ^{[ 27 ]に掲載されている例を改変したものです。}

情報利得は、生物多様性研究においてはシャノン指数としても知られている。

CARTで導入された^{[ 7 ]}分散削減は、目的変数が連続変数（回帰木）である場合によく用いられます。つまり、他の多くの指標を用いるには、まず離散化してから適用する必要があります。ノードNの分散削減は、このノードでの分割によって目的変数Yの分散がどれだけ減少するかを総括的に表したものです。

${\displaystyle I_{V}(N)={\frac {1}{|S|^{2}}}\sum _{i\in S}\sum _{j\in S}{\frac {1}{2}}(y_{i}-y_{j})^{2}-\left({\frac {|S_{t}|}{|S|}}{\frac {1}{|S_{t}|^{2}}}\sum _{i\in S_{t}}\sum _{j\in S_{t}}{\frac {1}{2}}(y_{i}-y_{j})^{2}+{\frac {|S_{f}|}{|S|}}{\frac {1}{|S_{f}|^{2}}}\sum _{i\in S_{f}}\sum _{j\in S_{f}}{\frac {1}{2}}(y_{i}-y_{j})^{2}\right)}$

どこ${\displaystyle S}$、${\displaystyle S_{t}}$、 そして${\displaystyle S_{f}}$は、それぞれ分割前のサンプルインデックスの集合、分割検定が真となるサンプルインデックスの集合、および分割検定が偽となるサンプルインデックスの集合を表します。上記の各項は、平均値を直接参照しない形式で記述された分散推定値です。

置き換えることで${\displaystyle (y_{i}-y_{j})^{2}}$上記の式における非類似度${\displaystyle d_{ij}}$2つの物体の間${\displaystyle i}$そして${\displaystyle j}$分散低減基準は、ペアワイズ非類似度を計算できるあらゆる種類のオブジェクトに適用されます。^{[ 1 ]}

1984年にCARTで使用された^{[ 28 ]}「良さ」の尺度は、候補となる分割が純粋な子ノードを生成する能力と、同じサイズの子ノードを生成する能力のバランスを最適化する関数です。このプロセスは、ツリーが完成するまで、各不純ノードに対して繰り返されます。${\displaystyle \varphi (s\mid t)}$、 どこ${\displaystyle s}$ノードで分割された候補です${\displaystyle t}$は以下のように定義される。

${\displaystyle \varphi (s\mid t)=2P_{L}P_{R}\sum _{j=1}^{\text{class count}}|P(j\mid t_{L})-P(j\mid t_{R})|}$

どこ${\displaystyle t_{L}}$そして${\displaystyle t_{R}}$ノードの左と右の子です${\displaystyle t}$分割を使用する${\displaystyle s}$、 それぞれ;${\displaystyle P_{L}}$そして${\displaystyle P_{R}}$レコードの割合は${\displaystyle t}$で${\displaystyle t_{L}}$そして${\displaystyle t_{R}}$それぞれ、${\displaystyle P(j\mid t_{L})}$そして${\displaystyle P(j\mid t_{R})}$クラスの割合は${\displaystyle j}$記録${\displaystyle t_{L}}$そして${\displaystyle t_{R}}$、 それぞれ。

3つの属性（貯蓄（低、中、高）、資産（低、中、高）、収入（数値）、バイナリターゲット変数信用リスク（良好、不良））と8つのデータポイントを持つデータセットの例を考えてみましょう。^{[ 28 ]}完全なデータは以下の表に示されています。決定木を開始するために、最大値を計算します。${\displaystyle \varphi (s\mid t)}$各特徴量を使用して、どの特徴量がルートノードを分割するかを調べます。このプロセスは、すべての子ノードが純粋であるか、すべての子ノードが純粋になるまで続きます。${\displaystyle \varphi (s\mid t)}$値が設定されたしきい値を下回っています。

見つける${\displaystyle \varphi (s\mid t)}$機能節約については、各値の数量に注意する必要があります。元のデータには、低値が3つ、中値が3つ、高値が2つ含まれていました。低値のうち、1つは信用リスクが良好で、中値と高値のうち、4つは信用リスクが良好でした。候補分割を仮定します。${\displaystyle s}$つまり、貯蓄額が少ないレコードは左側の子レコードに、その他のすべてのレコードは右側の子レコードに格納される。

${\displaystyle \varphi (s\mid {\text{root}})=2\cdot {\frac {3}{8}}\cdot {\frac {5}{8}}\cdot \left(\left|\left({\frac {1}{3}}-{\frac {4}{5}}\right)\right|+\left|\left({\frac {2}{3}}-{\frac {1}{5}}\right)\right|\right)=0.44}$

ツリーを構築するには、ルートノードに対するすべての候補分割の「良さ」を計算する必要があります。最も高い値を持つ候補がルートノードを分割し、ツリーが完成するまで、不純なノードごとにこのプロセスが繰り返されます。

情報利得などの他の指標と比較すると、「良さ」の尺度はよりバランスの取れたツリーを作成しようとし、より一貫性のある意思決定時間につながります。しかし、純粋な子ノードを作成するために優先順位をいくらか犠牲にするため、他の指標では見られないような追加の分岐が発生する可能性があります。

データマイニングの手法の中でも、決定木には様々な利点がある。

• 理解しやすく解釈しやすい。人々は簡単な説明の後、決定木モデルを理解することができる。木は、専門家でない人でも解釈しやすいようにグラフィカルに表示することもできる。^{[ 29 ]}
• 数値データとカテゴリデータの両方を処理できます。^{[ 29 ]}他の手法は通常、1種類の変数のみを持つデータセットの分析に特化しています。（たとえば、関係ルールは名義変数にのみ使用できますが、ニューラルネットワークは数値変数または0-1の値に変換されたカテゴリ変数にのみ使用できます。）初期の決定木はカテゴリ変数のみを処理できましたが、C4.5などの最近のバージョンにはこの制限はありません。^{[ 3 ]}
• データ準備はほとんど必要ありません。他の手法では、データの正規化が必要になることがよくあります。ツリーは定性的な予測変数を扱うことができるため、ダミー変数を作成する必要はありません。^{[ 29 ]}
• ホワイトボックスまたはオープンボックス^{[ 3 ]}モデルを使用します。モデルで特定の状況が観察可能であれば、その状況の説明はブール論理で簡単に説明できます。対照的に、ブラックボックスモデルでは、結果の説明は通常理解しにくく、たとえば人工ニューラルネットワークではそうなります。
• 統計的検定を用いてモデルを検証することが可能です。これにより、モデルの信頼性を検証することができます。
• トレーニングデータや予測残差について何の仮定も置かないノンパラメトリックなアプローチ。例えば、分布、独立性、等分散性などの仮定は不要。
• 大規模データセットの処理能力に優れています。標準的なコンピューティングリソースを使用すれば、大量のデータを妥当な時間で分析できます。
• 柔軟なモデリングによる精度。これらの方法は、精度を高めて医療研究に適用できる可能性がある。^{[ 30 ]}
• 他のアプローチよりも人間の意思決定をより忠実に反映している。^{[ 29 ]}これは人間の意思決定や行動をモデル化する際に役立つ可能性がある。
• 共線性、特にブースティングに対して頑健である。
• 組み込み機能選択。追加の無関係な機能は使用頻度が低くなるため、後続の実行で削除できます。決定木における属性の階層は、属性の重要性を反映しています。^{[ 31 ]}これは、上位の機能が最も情報量が多いことを意味します。^{[ 32 ]}
• 決定木は、XORなどの任意のブール関数を近似することができます。^{[ 33 ]}

• ツリーは非常に頑健性に欠ける場合があります。トレーニングデータのわずかな変化がツリーに大きな変化をもたらし、結果として最終的な予測結果にも大きな影響を与える可能性があります。^{[ 29 ]}
• 最適な決定木を学習する問題は、最適性のいくつかの側面において、また単純な概念であってもNP完全であることが知られています。 ^{[ 34 ] [ 35 ]}そのため、実際の決定木学習アルゴリズムは、各ノードで局所的に最適な決定を行う貪欲アルゴリズムなどのヒューリスティックに基づいています。このようなアルゴリズムは、グローバルに最適な決定木を返すことを保証できません。局所的最適性の貪欲効果を軽減するために、デュアル情報距離（DID）木などのいくつかの方法が提案されました。^{[ 36 ]}
• 決定木学習器は、訓練データからうまく汎化できない過度に複雑な木を作成する可能性があります。（これは過学習として知られています。^{[ 37 ]} ）この問題を回避するには、剪定などのメカニズムが必要です（剪定を必要としない条件付き推論アプローチなどの一部のアルゴリズムは例外です）。^{[ 21 ] [ 22 ]}
• 分類までのノード数またはテスト数によって定義されるツリーの平均深度は、さまざまな分割基準の下で最小または小さいことが保証されるわけではありません。^{[ 38 ]}
• レベル数が異なるカテゴリ変数を含むデータの場合、決定木における情報利得は、レベル数が多い属性に有利に偏っています。^{[ 39 ]}この問題に対処するために、情報利得が最も高い属性を選択する代わりに、情報利得が平均情報利得よりも大きい属性の中で、情報利得比が最も高い属性を選択できます。 ^{[ 40 ]}これにより、決定木は、異なる値の数が多い属性を考慮することに不利に偏り、情報利得が非常に低い属性に不当な優位性を与えることはありません。あるいは、条件付き推論アプローチ^{[ 21 ]}、2段階アプローチ^{[ 41 ]}、または適応型リーブワンアウト特徴選択^{[ 42 ]によって、偏った予測子選択の問題を回避できます。}

多くのデータマイニングソフトウェアパッケージは、1つ以上の決定木アルゴリズム（例えばランダムフォレスト）の実装を提供しています。

オープンソースの例としては、以下のようなものがあります。

• ALGLIBは、C++、C#、Javaに対応した数値解析ライブラリで、データ分析機能（ランダムフォレストなど）を備えています。
• KNIMEは、無料のオープンソースのデータ分析、レポート作成、統合プラットフォームです（決定木、ランダムフォレストなど）。
• Orangeは、オープンソースのデータ可視化、機械学習、データマイニングツールキット（ランダムフォレスト）です。
• R（統計計算のためのオープンソースソフトウェア環境であり、rpart、party、randomForestパッケージなど、いくつかのCART実装を含む）
• scikit-learn （ Pythonプログラミング言語用の無料のオープンソース機械学習ライブラリ）。
• Weka（無料のオープンソースのデータマイニングスイートで、多くの決定木アルゴリズムが含まれています）

注目すべき商用ソフトウェア：

• MATLAB
• Microsoft SQL Server
• ラピッドマイナー
• SASエンタープライズマイナー
• IBM SPSS Modeler

決定木では、ルートノードからリーフノードまでのすべてのパスは論理積（ AND）によって進みます。決定グラフでは、最小メッセージ長（MML）を使用して、論理和（OR）を使用してさらに 2 つのパスを結合することができます。^{[ 43 ]} 決定グラフはさらに拡張され、これまで明示されていなかった新しい属性を動的に学習し、グラフ内のさまざまな場所で使用できるようになりました。^{[ 44 ]} より一般的なコーディング スキームにより、予測精度と対数損失確率スコアが向上します。 一般に、決定グラフは決定木よりもリーフの数が少ないモデルを推論します。

進化アルゴリズムは、局所最適解を回避し、事前のバイアスをほとんど持たずに決定木空間を探索するために使用されてきました。^{[ 45 ] [ 46 ]}

MCMCを使用してツリーをサンプリングすることも可能です。^{[ 47 ]}

ツリーはボトムアップ方式で探索できます。^{[ 48 ]}または、分類までのテストの必要回数を減らすために、複数のツリーを並列に構築することもできます。^{[ 38 ]}