デシジョン・ツリー（決定木）とは

以下の図からわかるように、デシジョン・ツリーはルート・ノードから始まり、入力分岐がありません。ルート・ノードから出たブランチは、決定ノードとも呼ばれる内部ノードに送られます。利用可能な機能に基づいて、両方のノード・タイプが評価を実行し、リーフ・ノード（もしくは結果ノード）で表される同種のサブセットを形成します。リーフ・ノードは、データ・セット内のすべての可能性のある結果を表します。

例として、サーフィンに行くべきかの判断を、次のデシジョン・ツリーを使って決断へと導くことができます。

また、このようなフロー・チャート構造では、意思決定をわかりやすく表現できるため、組織内のさまざまなグループが、意思決定が行われた理由をよりよく理解できるようになります。

デシジョン・ツリー学習では、貪欲な検索を実行してツリー内の最適な分割ポイントを特定することにより、分割統治法を採用しています。この分割プロセスは、すべてまたは大部分のレコードが特定のクラス・ラベルに分類されるまで、トップダウンの再帰的な方法で繰り返されます。

すべてのデータ・ポイントが同種のセットとして分類されるかどうかは、デシジョン・ツリーの複雑さに大きく依存します。小さなツリーほど、より簡単に純粋なリーフ・ノード（つまり、単一クラス内のデータ・ポイント）を得ることができます。ただし、ツリーのサイズが大きくなるにつれて、この純度を維持することが困難になり、通常、特定のサブ・ツリー内に含まれるデータが少なすぎる結果になります。これは、データの断片化と呼ばれ、過剰適合につながることがよくあります。

結果として、デシジョン・ツリーは小さなツリーを優先します。これは、オッカムの剃刀（節約の原理）と一致しています。つまり、「エンティティーは必要以上に増やすべきではない」ということです。言い換えれば、最も単純な説明が最善であることが多いため、デシジョン・ツリーは必要な場合にのみ複雑さを増す必要があります。複雑さを減らして、過剰適合を防ぐために、通常は枝刈りを行います。これは、重要度の低い機能で分割された分岐を排除するプロセスです。その後、相互検証のプロセスを通じてモデルの適合性を評価できます。

デシジョン・ツリーの精度を維持するためのもう1つの方法は、ランダム・フォレスト・アルゴリズムを使用してアンサンブルを形成することです。この分類器は、特に個々のツリーが互いに相関していない場合に、より正確な結果を予測できます。

ハントのアルゴリズムは、心理学における人間の学習をモデル化するために1960年代に開発されたもので、次のような多くの一般的なデシジョン・ツリー・アルゴリズムの基礎になっています。

- ID3：Ross Quinlanは、「Iterative Dichotomiser 3」の省略形であるID3の開発に携わった功績が認められています。このアルゴリズムは、エントロピーと情報ゲインを指標として候補分割を評価します。1986年にQuinlanがこのアルゴリズムについて行った研究の一部は、こちら でご覧いただけます。

- C4.5：このアルゴリズムは、同じくQuinlanによって開発されたID3のイテレーションと考えられています。情報利得または利得比を用いて、デシジョン・ツリー内の分割ポイントを評価できます。

- CART：CARTという用語は、「分類および回帰ツリー（classification and regression tree)」の略語であり、Leo Breiman氏によって導入されました。このアルゴリズムは通常、ジニ不純度を用いて、分割する理想的な属性を決定します。ジニ不純度は、ランダムに選択された属性が誤って分類される頻度を測定します。ジニ不純度を用いて評価する場合は、値が低いほど理想的です。

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

エントロピーについて議論せず、情報利得について説明するのは困難です。エントロピーは情報理論の概念であり、サンプル値の不純度を測定します。それは次の式で定義されます。

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

エントロピー値は、0～1の間に収まります。データ・セットS 内のすべてのサンプルが1つのクラスに属している場合、エントロピーはゼロになります。サンプルの半分が1つのクラスに分類され、残りの半分が別のクラスに分類される場合、エントロピーは1で最高になります。分割する最適な特徴を選択し、最適なデシジョン・ツリーを見つけるには、エントロピー量が最小の属性を使用する必要があります。

情報利得は、特定の属性の分割前後のエントロピーの差を表します。情報利得が最も高い属性は、ターゲットの分類に従ってトレーニング・データを分類する際に最適な仕事をしているため、最適な分割が生成されます。情報利得は通常、次の式で表されます。

where

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

これらの概念をより深く理解するために、例を見てみましょう。次の任意のデータ・セットがあるとします。

このデータ・セットのエントロピーは、0.94です。これは、「テニスをする」が「はい」の日の割合（9/14）と、「テニスをする」が「いいえ」の日の割合（5/14）を求めることで計算できます。次に、これらの値を上記のエントロピー式に代入します。

Entropy(テニス) = -(9/14) log2 (9/14) - (5/14) log2 (5/14) = 0.94

その後、各属性の情報利得を個別に計算できます。たとえば、属性「湿度」について得られる情報は次のようになります。

Gain(テニス、湿度) = (0.94) - (7/14) x (0.985)– (7/14) x (0.592)= 0.151

要点を確認しましょう。

- 7/14は、湿度の値の総数に対する、湿度が「高」に等しい値の割合を表します。この場合、湿度が「高い」となる値の数は、湿度が「普通」となる値の数と同じです。

- 0.985は、湿度 =「高」の場合のエントロピーです。

- 0.59は、湿度＝「普通」の場合のエントロピーです。

次に、上の表の各属性の情報利得の計算を繰り返し、情報利得が最も高い属性を選択して、デシジョン・ツリーの最初の分割ポイントにします。この場合、予測では情報利得が最も高くなります。そこから、各サブ・ツリーに対してプロセスが繰り返されます。

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

デシジョン・ツリーはさまざまなユースケースで使用できますが、通常は他のアルゴリズムの方が優れた結果が得られます。とはいえ、デシジョン・ツリーは、データ・マイニングや知識発見タスクに特に役立ちます。デシジョン・ツリーの主な利点と課題について詳しく見てみましょう。

• 解釈しやすい：デシジョン・ツリーのブール理論と視覚的表現により、理解しやすく、使いやすいのが強みです。また、デシジョンツリーの階層的な性質により、どの属性が最も重要かが簡単にわかります。これは、ニューラル・ネットワークなどの他のアルゴリズムでは必ずしも明確ではありません。
  
  
• データ準備の必要がほとんど、またはまったくない：デシジョン・ツリーにはいくつかの特徴があり、他の分類器よりも柔軟性が高いことが強みです。さまざまな種類のデータ型を処理できます。離散値または連続値、および連続値を、しきい値を用いてカテゴリー値に変換できます。さらに、ナイーブ・ベイズなどの他の分類器では問題となる可能性がある欠損値を含む値も処理できます。
  
  
• 高い柔軟性：デシジョン・ツリーは、分類タスクと回帰タスクの両方に使用できるため、他のアルゴリズムよりも柔軟性に優れています。また、属性間の基礎となる関係にも影響しません。つまり、2つの変数の相関が高い場合は、分割する特徴のうちの1つだけを選択します。

• 過剰適合が起きやすい：複雑なデシジョン・ツリーは過剰適合する傾向があり、新しいデータにうまく一般化されません。このシナリオは、剪定前または剪定後のプロセスを実行することで回避できます。剪定前のプロセスでは、データが不十分な場合はツリーの成長を停止し、剪定後のプロセスでは、ツリーの構築後にデータが不十分なサブ・ツリーを排除します。
  
  
• 分散の大きい推定量：データ内のわずかなばらつきによって、デシジョン・ツリーが大きく異なることがあります。バギング（推定量の平均化）は、デシジョン・ツリーの分散を小さくするための1つの方法です。ただし、このアプローチでは、相関性の高い予測変数が生成される可能性があるため、制限があります。
  
  
• コストが高い：デシジョン・ツリーは、構築時に貪欲な探索アプローチをとるため、他のアルゴリズムと比較して学習コストが高くなる可能性があります。