決定木はノンパラメトリックな教師あり学習アルゴリズムで、分類と回帰の両方のタスクに利用されます。 決定木は階層型のツリー構造で、ルート・ノード、ブランチ、内部ノード、リーフ・ノードから構成されています。

上図で示されるように、決定木は入力ブランチのないルート・ノードで始まります。 ルート・ノードからの出力ブランチは、内部ノード（決定ノードとも呼ばれる）に送られます。 両ノードとも与えられた特徴に基づいて均質なサブセットを形成するための評価を行い、リーフ・ノードまたは終端ノードと呼ばれます。 リーフノードは、データ・セット内でのすべての結果を表します。 例えばサーフィンに行くかどうかを決めかねているときは、次のような決定ルールで行動を決めることが考えられます。

また、このようなフローチャート構造では意思決定のプロセスがわかりやすく表現されているため、なぜそのような決定がなされたのかを組織内の他のグループもよりよく理解できるようになります。

決定木学習は、ツリー内の最適な分岐点を入念に検討する分割統治方式を採用しています。 この分割プロセスは、すべてまたは大部分のレコードが特定のクラス・ラベルに分類されるまで、トップダウンで再帰的に繰り返されます。 すべてのデータ・ポイントが均質な集合として分類されるかどうかは、決定木の複雑さに大きく依存します。 ツリーが小さいほど純粋なリーフ・ノードが得られる、つまりすべてのデータ・ポイントが単一のクラスに属することになります。 ところがツリーのサイズが大きくなるとこの純度を保つことが難しくなり、与えられたサブツリー内に含まれるデータが少なすぎるという結果になりがちです。 このような現象はデータの断片化と呼ばれ、多くの場合は過剰適合（過学習）につながります。 そのため決定木は、できるだけ小さいツリー構造にすることが肝要です。 これは「オッカムの剃刀」のパーシモンの法則、つまり「必要なしに多くのものを定立してはならない」という原則にも合致しています。 言い換えると、決定木は必要な場合に必要なだけ複雑さを加えるべきであり、最も単純な構造が最良の結果を得られることが多いようです。 複雑さを軽減して過学習を防ぐために、通常はプルーニングが行われます。これは、重要度の低い特徴で分岐した枝を削除する処理です。 次に、クロスバリデーションというプロセスを実行することで、モデルの適合性を評価することができます。 決定木の精度を維持するもう一つの方法として、ランダムフォレスト・アルゴリズムによるアンサンブル形成があります。この分類器は、特に個々のツリーが互いに相関関係がない場合に、より正確な結果を予測することができます。

各ノードで最適な属性を選択する方法は多数ありますが、情報利得とジニ不純物の2つの方法が決定木モデルの一般的な分割基準として使用されています。 これらの方法は、各テスト条件の品質や、サンプルをどの程度適切にクラスに分類できるかを評価するのに役立ちます。  

エントロピーと情報利得

エントロピーについての解説を抜きにして情報利得を説明することはできません。 エントロピーとは情報理論に由来する概念で、サンプル値の不純度を測定するものです。 これは、次の式で定義されます。 

• Sはエントロピーを計算するデータセットを表します 
• cは集合Sのクラスを表します
• p(c)は集合Sの全データ点数に対するクラスcに属するデータ点数の割合を表します。

エントロピー値は0から1の間の値になります。 データ・セットSのすべてのサンプルが1つのクラスに属する場合、エントロピーはゼロに等しくなります。 サンプルの半分が1つのクラスに分類され、残りの半分が別のクラスにある場合、エントロピーは最高の1になります。 分割に最適な特徴を選択し、最適な決定木を見つけるためには、エントロピーが最も小さい属性を使用する必要があります。 情報利得は、ある属性に関する分割前後のエントロピーの差を表します。 情報利得が最も高い属性は、学習データをその目標分類に従って分類するのに最適な機能をしているため、最良の分割結果を生成します。 情報利得は、一般的に次の式で表されます。 

• aは特定の属性またはクラス・ラベルを表します
• Entropy(S)はエントロピーのデータ・セットSを表します
• |Sv|/ |S|データセットSに含まれる値の数に対するS_vの値の割合を表します
• Entropy(S_v)はエントロピーのデータ・セットS_vを表します

以上のコンセプトを確認するために、例を挙げて説明しましょう。 次のような任意のデータ・セットがあるとします。

このデータ・セットの場合、エントロピーは0.94です。 これは、「テニスをする」が「はい」の日の割合を9/14、「テニスをしない」の日の割合を5/14と求めることで算出できます。 それでは、ここで得られた値を上のエントロピーの式に当てはめてみましょう。

Entropy (Tennis) = -(9/14) log2(9/14) – (5/14) log2 (5/14) = 0.94

次に、それぞれの属性について個別に情報利得を計算してみましょう。 例えば、属性「Humidity」の情報利得は次のようになります。

Gain (Tennis, Humidity) = (0.94)-(7/14)*(0.985) – (7/14)*(0.592) = 0.151

要約すると、

7/14は、Humidity値の総数に対する湿度が「High」となる値の割合を示しています。 このケースでは、Humidityが「High」となる数値の数は、「Normal」となる数値の数と同じです。

0.985はHumidity = "High"の時のエントロピーです。

- 0.59はHumidity = "Normal"の時のエントロピーです。

そして、上の表の各属性について情報利得の計算を繰り返し、最も情報利得の高い属性を決定木の最初の分岐点とします。 このケースでは、Outlookが最も高い情報利得を生成しています。 そこから、各サブツリーに対してプロセスを繰り返します。 

ジニ不純物 

ジニ不純物とは、データセット中のランダムなデータ点を、データセットのクラス分布に基づいてラベル付けした場合に、誤って分類する確率である。 エントロピーと同様に、集合Sが純粋である場合、つまり1つのクラスに属する場合、その不純度はゼロです。 これは、次の式で表されます。 

決定木は様々なユースケースで利用できますが、一般的には他のアルゴリズムの方が決定木のアルゴリズムより優れています。 ただ、決定木は データ・マイニング や知識発見では非常に有用です。 それでは、決定木を活用する主なメリットと課題について、より深く掘り下げていきましょう。

-解釈が容易：決定木のブール論理と視覚的表現により、理解しやすく利用しやすい。 また、決定木は階層的な性質を持っているため、どの属性が最も重要であるかがわかりやすく、 ニューラル・ネットワークのような他のアルゴリズムでは必ずしも明確ではありません。

-データを準備する必要があまりない：決定木にはいくつかの特徴があり、他の分類器よりも柔軟性が高くなっています。 離散値や連続値など様々なデータ型を扱うことができ、連続値は閾値を使用してカテゴリー値に変換することができます。 さらに、ナイーブベイズのような他の分類器では問題となる、欠損値を含む値も扱うことができます。  

-柔軟性が高い：決定木は分類と回帰の両方のタスクに活用できるため、他のアルゴリズムよりも柔軟性があります。 また、属性間の関係も峻別しません。つまり、2つの変数に高い相関性がある場合、アルゴリズムはどちらか一方の特徴のみを選んで分割します。 

-過学習しやすい：複雑な決定木では過学習する傾向があり、その場合は新しいデータに対してうまく汎化できません。 このような状況は、プレプルーニングとポストプルーニングのプロセスを実行することで回避できます。 プレプルーニングを実行するとデータ不足が発生したときにツリーの成長を止め、ポストプルーニングを実行するとツリーの構築後にデータ不足のサブツリーを削除します。 

-高い分散推定値：データ内の小さなばらつきが、非常に異なった決定木を生み出すことがあります。 これには、バギング（推定値の平均化）が決定木の分散を低減する方法として有効です。 ただし、この方法では相関の強い予測変数ができる可能性があるため、その効果には限界があります。  

-コストがかかる：決定木は構築時に入念な探索アプローチをとるため、他のアルゴリズムと比較して学習コストが高くなることがあります。