デシジョンツリー（決定木）とは？基本概念と学習アルゴリズムをわかりやすく解説

デシジョンツリーの概要

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

デシジョンツリーを学習するアルゴリズム

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

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

出力 − 構築されたデシジョンツリー。

具体的な手順

1. ノードNを作成する。
2. すべてのサンプルが同一クラスCに属する場合は、次へ進む。
3. クラスCのラベルを付けた葉ノードとしてNを返す。
4. attribute-listが空である場合は、次へ進む。
5. サンプル内で最も一般的なクラスのラベルを付けた葉ノードとしてNを返す（多数決による決定）。
6. attribute-listの中から、情報利得が最も高い属性をテスト属性（test-attribute）として選択する。
7. ノードNにテスト属性のラベルを付ける。
8. テスト属性の既知の値a_iごとに、サンプルを分割する。
9. 条件「test-attribute = a_i」に対応する枝をノードNから伸ばす。
10. test-attribute = a_i を満たすサンプルの集合をs_iとする。
11. s_iが空である場合は、サンプル内で最も一般的なクラスのラベルを持つ葉ノードを接続する。
12. そうでなければ、generate_decision_tree(s_i, attribute-list − test-attribute) が返すノードを接続する。

デシジョンツリー帰納（Decision Tree Induction）とは

事例から決定ルールを自動的に生成することを「ルール帰納（rule induction）」または「自動ルール帰納」と呼びます。デシジョンツリーを構築する形で決定ルールを暗黙的に作り出す処理もルール帰納と呼ばれることがありますが、一般には「ツリー帰納」「デシジョンツリー帰納」という用語が好んで使われます。

デシジョンツリー帰納の基本アルゴリズムは貪欲法（greedy algorithm）に基づいており、トップダウンかつ再帰的な分割統治法（divide-and-conquer）の方式でデシジョンツリーを生成します。有名なデシジョンツリー帰納アルゴリズムであるID3も、この基本アルゴリズムの一種です。

基本的な手法の流れ

• ツリーは、訓練サンプル全体を表す単一のノード（ルートノード）から始まる。
• すべてのサンプルが同じクラスに属する場合、そのノードは葉ノードとなり、そのクラスのラベルが割り当てられる。
• アルゴリズムは、サンプルを個々のクラスに分割する属性を選択する際のヒューリスティックとして、「情報利得（information gain）」と呼ばれるエントロピーに基づく尺度を利用する。この属性がノードにおける「テスト属性」または「決定属性」となる。この形式のアルゴリズムでは、すべての属性がカテゴリカル（離散値）であることを前提とするため、連続値属性はあらかじめ離散化しておく必要がある。
• テスト属性の既知の値ごとに枝が生成され、それに応じてサンプルが適切に分割される。
• アルゴリズムは同じ手順を繰り返し適用して、各分割後のサンプル群に対してデシジョンツリーを形成していく。ある属性が一度ノードで使用された場合、その子孫ノードでは再度使用してはならないという制約が課される。

まとめ

デシジョンツリーは、内部ノード・枝・葉ノードから構成される直感的で解釈しやすいモデルです。ID3に代表される帰納アルゴリズムでは、情報利得を指標として属性を選択しながら、データをトップダウンに再帰的に分割することでツリーを構築します。分類問題を中心に幅広く活用されており、機械学習の基礎として重要な概念といえます。