決定木

左から右に描かれる決定木には、分岐ノード（分岐経路）はありますが、収束ノード（収束経路）はありません。そのため、手動で作成すると非常に大きくなり、完全に手作業で描くのが難しくなることがよくあります。従来、決定木は手動で作成されていましたが（横の例が示すように）、近年では専用ソフトウェアが使用されることが増えています。

決定木は決定ルールに線形化することができ、^{[ 5 ]}結果は葉ノードの内容であり、パスに沿った条件はif節で論理積を形成します。一般に、ルールは次の形式をとります。

条件1と条件2と条件3が満たされる場合、結果。

決定ルールは、右側のターゲット変数との関連ルールを構築することによって生成できます。また、時間的または因果関係を表すこともできます。 ^{[ 6 ]}

意思決定ツリーは、多くの人が読みやすく理解しやすいため、一般的にフローチャート記号を用いて描かれます。ただし、以下のツリーの「続行」の計算には概念的な誤りがあります。この誤りは、訴訟で裁定される「費用」の計算に関するものです。

分析では、意思決定者（例えば企業）の好みや効用関数を考慮に入れることができます。例えば、次のようになります。

この状況における基本的な解釈は、現実的なリスク選好係数（40万ドル以上）の下では、会社はBのリスクと報酬を好むということである（このリスク回避の範囲では、会社は「AもBも選ばない」という3つ目の戦略をモデル化する必要がある）。

オペレーションズリサーチのコースでよく使われるもう1つの例は、ビーチでのライフガードの配置（別名「人生はビーチ」の例）です。^{[ 7 ]}この例では、2つのビーチがあり、それぞれのビーチにライフガードを配置する必要があります。2つのビーチに分配できる最大予算Bがあり（合計）、限界収益表を使用して、アナリストは各ビーチに何人のライフガードを割り当てるかを決定できます。

この例では、ビーチ1における収穫逓減の原理を説明するために、意思決定ツリーを作成することができる。

意思決定ツリーは、ライフガードを順次配置する場合、予算がライフガード1人分しかない場合は、最初のライフガードをビーチ1に配置するのが最適であることを示している。しかし、予算がライフガード2人分ある場合は、両方をビーチ2に配置することで、溺死事故をより多く防ぐことができる。

意思決定ツリーに含まれる情報の多くは、影響図としてより簡潔に表現することができ、問題点や事象間の関係性に焦点を当てることができる。

決定木の精度は、決定木の深さによって変化する可能性があります。多くの場合、木の葉は純粋ノードです。^{[ 11 ]}ノードが純粋であるということは、そのノード内のすべてのデータが単一のクラスに属していることを意味します。^{[ 12 ]}たとえば、データセットのクラスが癌と非癌である場合、葉ノード内のすべてのサンプルデータが癌または非癌のいずれか1つのクラスに属しているときに、葉ノードは純粋であるとみなされます。決定木を最適化する場合、深い木が常に優れているとは限りません。深い木は実行時間に悪影響を与える可能性があります。特定の分類アルゴリズムが使用されている場合、深い木は、この分類アルゴリズムの実行時間が著しく遅くなることを意味する可能性があります。また、決定木を構築する実際のアルゴリズムが、木が深くなるにつれて著しく遅くなる可能性もあります。使用されている木構築アルゴリズムが純粋ノードを分割する場合、木分類器の全体的な精度が低下する可能性があります。場合によっては、ツリーの深さを深くすると、全体的な精度が低下することがあるため、決定木の深さを変更してテストし、最良の結果が得られる深さを選択することが非常に重要です。まとめると、以下の点に注意してください。ここでは、数値Dをツリーの深さと定義します。

Dの数を増やすことによる考えられる利点：

• 決定木分類モデルの精度が向上する。

Dを増やすことによる潜在的なデメリット

•  実行時の問題
• 全般的な精度低下
• より深い階層に進む際に純粋なノード分割を行うと、問題が発生する可能性があります。

Dの値を変更した際の分類結果の差異を検証できる機能は不可欠です。決定木モデルの精度と信頼性に影響を与える可能性のある変数を、容易に変更して検証できる必要があります。

ノード分割に使用する関数は、決定木の精度向上に影響を与える可能性があります。たとえば、情報利得関数を使用すると、ファイ関数を使用するよりも良い結果が得られる場合があります。ファイ関数は、決定木のノードにおける候補分割の「良さ」の尺度として知られています。情報利得関数は、「エントロピーの減少」の尺度として知られています。以下では、2つの決定木を構築します。1つはファイ関数を使用してノードを分割する決定木、もう1つは情報利得関数を使用してノードを分割する決定木です。

情報利得とファイ関数の主な利点と欠点

• 情報利得の大きな欠点の1つは、ツリーの次のノードとして選択される特徴が、より多くの固有の値を持つ傾向があることです。^{[ 13 ]}
• 情報利得の利点は、ツリーの根元に近い、最も影響力の大きい特徴を選択する傾向があることです。これは、いくつかの特徴の関連性を判断するための非常に優れた指標となります。
• ファイ関数は、「良さ」に基づいていくつかの特徴の関連性を判断するための優れた指標でもあります。

これは情報利得関数の公式です。この公式によれば、情報利得は、決定木のノードのエントロピーから、決定木のノードtにおける候補分岐のエントロピーを引いた値の関数です。

${\displaystyle I_{\textrm {gain}}(s)=H(t)-H(s,t)}$

これはファイ関数の公式です。ファイ関数は、選択した特徴量によってサンプルが均等に分割され、各分割に含まれるサンプル数がほぼ等しくなる場合に最大になります。

${\displaystyle \Phi (s,t)=(2*P_{L}*P_{R})*Q(s|t)}$

構築する決定木の深さである D を 3 (D = 3) に設定します。また、がんサンプルと非がんサンプル、およびサンプルが持つか持たないかを示す変異特徴のデータセットも用意します。サンプルに特徴変異がある場合、そのサンプルはその変異に対して陽性であり、1 で表されます。サンプルに特徴変異がない場合、そのサンプルはその変異に対して陰性であり、0 で表されます。

要約すると、Cは癌、NCは非癌を表します。文字Mは変異を表し、サンプルに特定の変異がある場合は表に1と表示され、そうでない場合は0と表示されます。

これで、データセット内の各Mについて、公式を用いてファイ関数値と情報利得値を計算できます。すべての値が計算されたら、ツリーを作成できます。まず最初に行うべきことは、ルートノードを選択することです。情報利得とファイ関数では、最適な分割とは、情報利得またはファイ関数の値が最大となる突然変異であると考えます。ここで、M1がファイ関数値が最も高く、M4が情報利得値が最も高いと仮定します。M1の突然変異がファイ関数ツリーのルートとなり、M4が情報利得ツリーのルートとなります。ルートノードは以下で確認できます。

さて、ルートノードを選択したら、サンプルがルートノードの変異に対して陽性か陰性かに基づいて、サンプルを2つのグループに分割できます。これらのグループはグループAとグループBと呼ばれます。例えば、M1を使用してルートノードのサンプルを分割すると、NC2とC2のサンプルがグループAに、残りのサンプルNC4、NC3、NC1、C1がグループBに分類されます。

ルートノードに選択された変異を無視して、情報利得またはファイ関数の値が最も高い次善の特徴を、決定木の左または右の子ノードに配置します。深さ = 3 の木のルートノードと 2 つの子ノードを選択したら、葉を追加するだけです。葉は、サンプルが持つか持たないかの変異に基づいてモデルが生成した最終的な分類決定を表します。左側の木は、情報利得を使用してノードを分割して得られた決定木であり、右側の木は、ファイ関数を使用してノードを分割して得られた決定木です。

ここで、両方のツリーからの分類結果が混同行列を使用して与えられると仮定します。

情報利得混同行列：

ファイ関数混同行列：

情報利得を用いたツリーは、精度を計算する際にファイ関数を使用した場合と同じ結果になります。情報利得を用いたモデルに基づいてサンプルを分類すると、真陽性が 1 つ、偽陽性が 1 つ、偽陰性が 0 つ、真陰性が 4 つになります。ファイ関数を使用したモデルでは、真陽性が 2 つ、偽陽性が 0 つ、偽陰性が 1 つ、真陰性が 3 つになります。次のステップは、後述の決定木評価のセクションで説明するいくつかの重要な指標を使用して決定木の有効性を評価することです。以下で説明する指標は、決定木を最適化する際に取るべき次のステップを決定するのに役立ちます。

上記の情報は、決定木の構築と最適化に関するすべてを網羅しているわけではありません。構築する決定木分類モデルを改善するための手法は数多く存在します。その一つが、ブートストラップデータセットから決定木モデルを作成することです。ブートストラップデータセットは、モデルのテストに使用するデータと同じデータで決定木モデルを構築する際に発生するバイアスを取り除くのに役立ちます。ランダムフォレストの力を活用することで、構築中のモデルの全体的な精度を大幅に向上させることも可能です。この手法では、多数の決定木から多数の決定を生成し、各決定木からの投票を集計して最終的な分類を行います。多くの手法がありますが、主な目的は、決定木モデルをさまざまな方法で構築し、可能な限り最高のパフォーマンスレベルに到達できるようテストすることです。