決定木学習

決定木学習は、統計、データマイニング、機械学習で使用される教師あり学習アプローチです。この形式では、分類または回帰決定木が予測モデルとして使用され、一連の観察結果に関する結論を導き出します。

対象変数が離散的な値を取ることができるツリーモデルは分類 ツリーと呼ばれます。これらのツリー構造では、葉はクラスラベルを表し、枝はそれらのクラスラベルにつながる特徴の結合を表します。対象変数が連続値（通常は実数）を取ることができる決定木は回帰 ツリーと呼ばれます。より一般的には、回帰ツリーの概念は、カテゴリシーケンスなどのペアワイズ非類似性を備えたあらゆる種類のオブジェクトに拡張できます。^[1]

決定木は、その分かりやすさとシンプルさから、最も人気のある機械学習アルゴリズムの一つです。^[2]

意思決定分析では、決定木を使用して、意思決定と意思決定を視覚的かつ明示的に表現できます。データ マイニングでは、決定木はデータを説明します (ただし、結果として得られる分類ツリーは意思決定の入力として使用できます)。

決定木学習は、データマイニングでよく使われる手法です。^[3]目標は、複数の入力変数に基づいてターゲット変数の値を予測するモデルを作成することです。

決定木は、例を分類するための単純な表現です。このセクションでは、すべての入力フィーチャが有限の離散ドメインを持ち、「分類」と呼ばれる単一のターゲット フィーチャがあると仮定します。分類のドメインの各要素は、クラスと呼ばれます。決定木または分類木は、各内部 (非リーフ) ノードが入力フィーチャでラベル付けされたツリーです。入力フィーチャでラベル付けされたノードから来るアークは、ターゲット フィーチャの可能な各値でラベル付けされるか、アークは異なる入力フィーチャの従属決定ノードにつながります。ツリーの各リーフは、クラスまたはクラスに対する確率分布でラベル付けされ、データ セットがツリーによって特定のクラスまたは特定の確率分布 (決定木が適切に構築されている場合、特定のクラスのサブセットに偏っている) に分類されていることを示します。

ツリーは、ツリーのルートノードを構成するソースセットを、後続の子を構成するサブセットに分割することによって構築されます。分割は、分類機能に基づく一連の分割ルールに基づいています。 ^{[4]このプロセスは、}再帰分割 と呼ばれる再帰的な方法で、派生した各サブセットに対して繰り返されます。再帰は、ノードのサブセットがターゲット変数の値をすべて同じにしたとき、または分割しても予測に値が追加されなくなったときに完了します。この決定木のトップダウン誘導(TDIDT) ^{[5]のプロセスは、}貪欲アルゴリズムの例であり、データから決定木を学習するための最も一般的な戦略です。^[6]

データマイニングでは、決定木は、特定のデータセットの説明、分類、一般化を支援するための数学的手法と計算手法の組み合わせとしても説明できます。

データは次の形式のレコードで提供されます:

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

従属変数は、理解、分類、または一般化しようとしているターゲット変数です。ベクトルは、そのタスクに使用される 特徴などで構成されます。${\displaystyle Y}$${\displaystyle {\textbf {x}}}$${\displaystyle x_{1},x_{2},x_{3}}$

データ マイニングで使用される決定木には、主に 2 つの種類があります。

• 分類ツリー分析は、予測される結果がデータが属するクラス (離散的) である場合に行われます。
• 回帰ツリー分析は、予測される結果を実数（住宅の価格や患者の入院期間など）と見なせる場合に行われます。

分類と回帰ツリー（CART）分析という用語は、上記のいずれかの手順を指すために使用される包括的な用語であり、 1984年にBreimanらによって初めて導入されました。 ^[7]回帰に使用されるツリーと分類に使用されるツリーにはいくつかの類似点がありますが、分割する場所を決定するために使用される手順など、いくつかの違いもあります。^[7]

アンサンブル法と呼ばれるいくつかの手法では、複数の決定木が構築されます。

• ブーストツリーは、新しいインスタンスをトレーニングすることで、以前に誤ってモデル化されたトレーニングインスタンスを強調し、アンサンブルを段階的に構築します。典型的な例はAdaBoostです。これらは、回帰型および分類型の問題に使用できます。 ^{[8] [9]}
• 決定木委員会（k-DT ^[10]とも呼ばれる）は、ランダム化決定木アルゴリズムを使用してトレーニングデータから複数の異なる木を生成し、多数決を使用してそれらを組み合わせて出力を生成する初期の方法です。^[11]
• 初期のアンサンブル法であるブートストラップ集約型（またはバッグ型）決定木は、トレーニングデータを繰り返し置換して再サンプリングし、コンセンサス予測のために決定木に投票することで、複数の決定木を構築します。 ^[12]
  • ランダムフォレスト分類器は、ブートストラップ集約の特定のタイプである。
• 回転フォレスト–入力特徴のランダムなサブセットに主成分分析（PCA）を適用して、すべての決定木をトレーニングします。 ^[13]

決定木の特殊なケースとして決定リストがある^[14]。これは片側決定木であり、すべての内部ノードには1つのリーフノードと1つの内部ノードが子として存在する（最下層のノードは例外で、その唯一の子は単一のリーフノードである）。決定リストは表現力に劣るが、一般的な決定木よりもスパース性が高く[要出典]、非貪欲学習法[15]と単調制約を課すことができるため理解し^{やすいと言える}。^[ 16 ^]

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

• ID3 (反復二分法 3)
• C4.5 (ID3の後継)
• CART（分類と回帰木）^[7]
• OC1（斜分類器1）。各ノードで多変量分割を作成した最初の方法。^[17]
• カイ二乗自動相互作用検出（CHAID）。分類ツリーを計算する際に多段階分割を実行します。^{[18] [19] [20]}
• MARS : 決定木を拡張して数値データをより適切に処理します。
• 条件付き推論ツリー。ノンパラメトリック検定を分割基準として用いる統計ベースのアプローチで、過剰適合を避けるために多重検定を補正する。このアプローチでは偏りのない予測子選択が行われ、剪定を必要としない。^{[21] [22]}

ID3 と CART はほぼ同時期 (1970 年から 1980 年の間) に独立して発明されましたが^{(引用が必要)}、トレーニング タプルから決定木を学習するという同様のアプローチを採用しています。

また、ファジー集合論の概念を活用して、ファジー決定木（FDT）と呼ばれる特別なバージョンの決定木を定義することも提案されています。^[23] このタイプのファジー分類では、通常、入力ベクトルは複数のクラスに関連付けられ、それぞれが異なる信頼値を持ちます。FDTのブーストされたアンサンブルも最近調査されており、他の非常に効率的なファジー分類器に匹敵するパフォーマンスを示しています。^[24]${\displaystyle {\textbf {x}}}$

決定木を構築するアルゴリズムは通常、各ステップで項目セットを最もよく分割する変数を選択することで、トップダウンで動作します。^[6]異なるアルゴリズムでは、「最良」を測定するために異なるメトリックを使用します。これらは通常、サブセット内のターゲット変数の均質性を測定します。以下にいくつかの例を示します。これらのメトリックは各候補サブセットに適用され、結果の値が結合 (平均化など) されて、分割の品質の尺度が提供されます。基礎となるメトリックに応じて、決定木学習のさまざまなヒューリスティック アルゴリズムのパフォーマンスは大幅に異なる場合があります。^[25]

単純かつ効果的なメトリックを使用して、真陽性が偽陽性を上回る度合いを特定できます (混同行列を参照)。このメトリック「陽性の正確さの推定」は、次のように定義されます。

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

この式では、偽陽性 (FP) の合計が真陽性 (TP) の合計から減算されます。結果の数値は、データ内で機能が正しく識別できる陽性サンプルの数の推定値を示します。数値が高いほど、機能がより多くの陽性サンプルを正しく分類できることを意味します。以下は、特定の機能の完全な混同行列が与えられている場合に、このメトリックを使用する方法の例です。

機能 A 混同マトリックス

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

ただし、この数値は推定値にすぎないことに注意してください。たとえば、2 つの特徴の FP 値が両方とも 2 で、一方の特徴の TP 値の方が高かった場合、方程式を使用した場合の推定値が高い値になるため、その特徴はもう一方の特徴よりも高いランクになります。一部の特徴の陽性サンプルが他の特徴よりも多い場合、このメトリックを使用すると不正確になる可能性があります。これに対処するには、混同行列の値の比率を考慮して実際の真陽性率(TPR)を算出する、感度と呼ばれるより強力なメトリックを使用できます。これらのメトリックの違いを次の例に示します。

この例では、特徴 A の推定値は 6、TPR は約 0.73 でしたが、特徴 B の推定値は 4、TPR は 0.75 でした。これは、一部の特徴の正の推定値は高くなる可能性があるものの、その特徴のより正確な TPR 値は、正の推定値が低い他の特徴と比較すると低くなる可能性があることを示しています。状況やデータおよび決定木に関する知識によっては、問題を迅速かつ簡単に解決するために正の推定値を使用することを選択する場合があります。一方、経験豊富なユーザーは、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}$${\displaystyle q\to 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}}$

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

$${\displaystyle \overbrace {IG(T,a)} ^{\text{information gain}}=\overbrace {\mathrm {H} (T)} ^{\text{entropy (parent)}}-\overbrace {\mathrm {H} (T\mid a)} ^{\text{sum of entropies (children)}}}$$${\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{expected information gain}}=\overbrace {I(T;A)} ^{{\text{mutual information between }}T{\text{ and }}A}=\overbrace {\mathrm {H} (T)} ^{\text{entropy (parent)}}-\overbrace {\mathrm {H} (T\mid A)} ^{\text{weighted sum of entropies (children)}}}$$${\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のエントロピーの減少は相互情報量であることを意味します。

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

4 つの属性 (見通し(晴れ、曇り、雨)、気温(暑い、穏やか、涼しい)、湿度(高い、普通)、風が強い(真、偽))、バイナリ (はい、いいえ) のターゲット変数play、および 14 個のデータ ポイントを含むデータ セットの例を考えてみましょう。このデータで決定木を構築するには、4 つのツリーのそれぞれの情報ゲインを比較する必要があります。各ツリーは、4 つの特徴の 1 つで分割されます。情報ゲインが最も高い分割が最初の分割として採用され、すべての子ノードがそれぞれ一貫したデータを持つか、情報ゲインが 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を使用した分割により、2 つの子ノードが生成されます。1 つはwindy値が true で、もう 1 つはwindy値が false です。このデータ セットには、真のwindy値を持つ 6 つのデータ ポイントがあり、そのうち 3 つはplay ( playはターゲット変数) 値が yes で、3 つはplay値が no です。windy 値が false である残りの 8 つのデータ ポイントには、2 つの no と 6 つの yes が含まれています。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つははい、2つはいいえでした。したがって、

${\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}|^{2}}{|S|^{2}}}{\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}|^{2}}{|S|^{2}}}{\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}}$

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

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})|}$

ここで、 および はそれぞれ、 split を使用するノード の左と右の子です。および はそれぞれ、およびにおけるレコードの割合です。また、および はそれぞれ、およびにおけるクラス レコードの割合です。 ${\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)}$

特徴の節約を見つけるには、各値の量に注意する必要があります。元のデータには、3 つの低、3 つの中、2 つの高が含まれていました。低のうち 1 つは信用リスクが良好でしたが、中と高のうち 4 つは信用リスクが良好でした。貯蓄が低いレコードが左の子に配置され、他のすべてのレコードが右の子に配置される ように候補を分割すると仮定します。${\displaystyle \varphi (s\mid t)}$${\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] 、または適応型leave-one-out特徴選択^{[42]によって回避できます。}

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

オープンソースの例には以下が含まれます。

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

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

• MATLAB、
• Microsoft SQL Server、および
• ラピッドマイナー、
• SASエンタープライズマイナー、
• IBM SPSS モデラー、

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

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

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

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

• ジェームズ、ガレス、ウィッテン、ダニエラ、ハスティー、トレバー、ティブシラニ、ロバート (2017)。「ツリーベース手法」(PDF)。統計学習入門: R での応用。ニューヨーク: シュプリンガー。pp. 303–336。ISBN 978-1-4614-7137-0。

• C++ での決定木の進化学習
• 分割基準としての情報利得の非常に詳細な説明