デシジョンツリー（決定木）の構築方法を徹底解説

デシジョンツリー（決定木）とは、フローチャートのような木構造を持つモデルです。各内部ノードは属性に対するテストを表し、各ブランチ（枝）はそのテストの結果を示し、葉ノードはクラスまたはクラス分布を表します。木の中で最上位に位置するノードは「ルートノード」と呼ばれます。

デシジョンツリー構築の基本的な流れ

デシジョンツリーの構築問題は、再帰的に定義することができます。まず、ルートノードに配置する属性を選択し、その属性が取りうる値ごとに1つのブランチを作成します。これにより、サンプル集合は属性の値ごとに複数の部分集合へと分割されます。

この手順は、各ブランチに対して再帰的に繰り返されます。このとき対象となるのは、そのブランチに到達したインスタンスのみです。そして、あるノードに到達したすべてのインスタンスが同じクラスに分類される場合には、その部分の木の構築を停止します。

純度の尺度としての「情報量」

ノードの純度を測る尺度としてよく用いられるのが「情報量」であり、「ビット」という単位で測定されます。情報量は木の各ノードに関連付けられ、そのノードに到達したインスタンスを踏まえたうえで、新しいインスタンスがyesかnoのどちらに分類されるかを判定するために必要な、期待される情報量を表します。

過学習を防ぐ「枝刈り（プルーニング）」

枝刈り（プルーニング）とは、デシジョンツリーのサイズを縮小するプロセスのことです。木のサイズを制限したり、分類精度にほとんど寄与しない部分を削除したりすることで、過学習（オーバーフィッティング）のリスクを低減します。

訓練データには、ノイズや外れ値によって異常なパターンが含まれることがあります。枝刈りを行うことで、こうした異常を反映した不要な枝を取り除き、木の汎化性能を高めることができます。

多くの手法では、統計的な尺度を用いて信頼性の低い枝を除去します。その結果、分類処理が高速化されるとともに、未知のテストデータを正確に分類する能力も向上します。

デシジョンツリーの学習アルゴリズム

アルゴリズムの概要

アルゴリズム： 与えられた訓練データからデシジョンツリーを生成します。

入力： 離散値属性で記述された訓練サンプル（samples）、および候補属性のリスト（attribute-list）。

出力： デシジョンツリー。

具体的な手順

• ノードNを作成する。

• samplesがすべて同一のクラスCに属する場合は、クラスCのラベルを付けた葉ノードとしてNを返す。

• attribute-listが空の場合は、samplesにおいて最も頻度の高いクラスのラベルを付けた葉ノードとしてNを返す（多数決）。

• attribute-listの中から、情報利得が最大となる属性test-attributeを選択する。

• ノードNにtest-attributeのラベルを付ける。

• test-attributeの既知の各値a_iについて、以下の処理を行う（サンプルの分割）。

• 条件「test-attribute = a_i」に対応するブランチをノードNから伸ばす。

• samplesのうち「test-attribute = a_i」を満たすサンプル集合をs_iとする。

• s_iが空である場合は、samplesで最も一般的なクラスのラベルを持つ葉ノードを接続する。

• それ以外の場合は、Generate_decision_tree(s_i, attribute-list − test-attribute)が返すノードを接続する。