デシジョン・ツリーとは?

データ・マイニングと知識発見のタスクでデシジョン・ツリーを使用する長所と短所について解説します。

AIとデータストレージがコンピューティングを高速化する図

決定木

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

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

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

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


デシジョン・ツリーの種類

ハントのアルゴリズムは心理学の分野で人間学習のモデルとして1960年代に開発され、以下のような多くの一般的なデシジョン・ツリーのアルゴリズムの基礎を成しています: 

-ID3:ロス・クインランは、ID3(Iterative Dichotomiser 3)の開発者として知られています。 このアルゴリズムでは、エントロピーと情報利得を指標として分割候補を評価します。 1986年から続くこのアルゴリズムに関するクインランの研究の一部を、 ここ からご覧になれます(PDF、1.3MB)(リンクは ibm.comの外部にあります)。

-C4.5: このアルゴリズムは、同じくQuinlanによって開発されたID3の後継アルゴリズムです。 これはデシジョン・ツリー内の分岐点を評価するために、情報利得や利得比を使用することができます。 

-カート: CARTとは、「Classification and Regression Tree」の略で、レオ・ブレイマンにより提唱されました。 一般的にこのアルゴリズムではジニ不純物を使用して、分割する理想的な属性を識別します。 ジニ不純物は、ランダムに選択された属性が誤分類される頻度を測定します。 ジニ不純物を使用して評価する場合は、値が低くなるほど理想的な結果となります。 


各ノードで最高の属性を選択する方法

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

エントロピーと情報利得

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

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

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

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

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

このデータ・セットの場合、エントロピーは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つの変数に高い相関性がある場合、アルゴリズムはどちらか一方の特徴のみを選んで分割します。 

デメリット

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

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

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

- Scikit-learnでは完全にはサポートされていない: Scikit-learnは、Pythonベースの有名な機械学習ライブラリーです。 このライブラリには デシジョン・ツリーのモジュール(DecisionTreeClassifier、リンクは ibm.comの外部にあります)がありますが、現在の実装環境ではカテゴリー変数をサポートしていません。


デシジョンツリーとIBM

IBM SPSS Modelerは、予測モデルを開発して業務に展開することができるデータ・マイニング・ツールです。 業界標準のCRISP-DMモデルに基づいて設計されたIBM SPSS Modelerは、データ処理からより良いビジネス成果の達成まで、データマイニング・プロセス全体をサポートします。

IBM SPSS Decision Treesは、視覚的な分類とデシジョン・ツリーを備えており、カテゴリー別の結果を提示したり、非技術系のユーザーに分析結果をより明確に説明するのに役立ちます。 セグメンテーション、層別化、予測、データ削減、変数スクリーニングのための分類モデルを作成します。

IBMのデータ・マイニング・ツールおよびソリューションの詳細については、IBMidにサインアップして、IBM Cloudアカウントを今すぐ作成してください。


関連ソリューション

IBM SPSS Modeler

IBM SPSS Modelerは、予測モデルを開発して業務に展開することができるデータマイニングツールです。 業界標準のCRISP-DMモデルに基づいて設計されたIBM SPSS Modelerは、データ処理からより良いビジネス成果の達成まで、データマイニング・プロセス全体をサポートします。


IBM SPSS Decision Trees

IBM SPSS Decision Treesトピックス可視機密区分への決定木ヘルプ、分類結果を提示し、技術者以外の対象者に分析をより明確に説明します。 セグメンテーション、層別化、予測、データ削減、変数スクリーニングのための分類モデルを作成します。



IBMのデータ・マイニング・ソリューションの詳細はこちら

IBMのデータ・マイニング・ツールおよびソリューションの詳細については、IBMidにサインアップして、IBM Cloudアカウントを今すぐ作成してください。