決定木

決定木（けっていぎ、英: decision tree）は、（リスクマネジメントなどの）決定理論の分野において決定を行うためのグラフであり、計画を立案して目標に到達するのに用いられる。決定木は、意志決定を助けることを目的として作られる。決定木は木構造の特別な形である。

概説

機械学習の分野において決定木は予測モデルであり、ある事項に対する観察結果から、その事項の目標値に関する結論を導く。内部の節点は変数に対応し、子である節点への枝はその変数の取り得る値を示す。葉（端点）は、根(root)からの経路によって表される変数値に対して、目的変数の予測値を表す。

データから決定木を作る機械学習の手法のことを決定木学習 (英: decision tree learning)、または略して単に決定木と呼ぶ。

決定木による分類モデルはその分類にいたる過程が容易に解釈できるので、決定木はデータマイニングでよく用いられる^[1]。その場合、決定木は、葉が分類を表し、枝がその分類に至るまでの特徴の集まりを表す木構造を示す^[2]。

決定木の学習は、元となる集合を属性値テストに基づいて部分集合に分割することによって行える^[2]。この処理は、すべての部分集合に対して再帰的に繰り返される。繰返しは、分割が実行不可能となった場合、または部分集合の個々の要素が一つずつの分類となってしまう段階で終了する。^{[要検証 – ノート]}

決定木は、データの集合を表現したり分類や法則化を助ける数学的手法、計算手法であるともいえる。データは次のような形式のレコードである。

(x, y) = （x₁, x₂, x₃, …, x_k, y）

従属変数 y は、理解し分類や法則化を行う対象であり、残りの変数 x₁, x₂, x₃ などは分類や法則化を行う上で参考となる変数である。

決定木には、他に2つの呼び名がある。

決定木を例で見てみる。

ある有名なゴルフクラブの経営者が、客の来場状況について悩みを抱えている。客が殺到する日があり、そういう日はクラブの従業員が足りない。逆に客がまったく来ない日もあり、そんな日は従業員は非常に暇である。

週間天気予報に基づいて、客がいつゴルフクラブにやってくるのかを予測し、従業員の勤務体制を最適化したい。つまり、人がゴルフをやりたくなる理由を知りたい。

そこで2週間にわたって、次の情報を集めた。

天気（晴れ／曇／雨）、気温（度）、湿度(%)，風（強い／弱い）、客のゴルフクラブ日、その客が来たかどうか。

その結果、次のような 14 行 5 列のデータを集めることができた。

問題を解決するために、決定木を作った。

上図のとおり、木の形をした閉路を含まない有向グラフである。最も上の節点は全データを表す。この決定木の作り方を述べる。

分類木を自動生成するアルゴリズム（詳細は述べない）があり、それを上の表に示すデータに適用すると、従属変数である「ゴルフをするか」を説明する最も良い方法は、変数「天気」を用いることだという結果が得られる。「天気」の値によって表を並べ替えると、下表のとおりになる。

変数「天気」の分類を用いると、3つのグループがある。晴れの日にゴルフをするグループ、曇の日にゴルフをするグループ、そして雨が降っていてもゴルフをするグループもいることが分かった。

ここで、変数「気温」の値の昇順に表を並べ替えると、こうなる。

ある温度を境にして2グループまたは3グループに分けようとしても、明確には分けられない。他の変数についても同様である。「天気」で分類すると、曇の場合に従属変数が "する" であるデータだけのグループが作れることから、最初に「天気」で分類することは適切な判断といえる。

全データをまず「天気」で分類すると、最初の結論として、天気が曇なら人は必ずゴルフをし、雨の日であっても熱狂的な人はゴルフをするということが分かる。

さらに、晴れの日のグループを2つのグループに分ける。客は湿度が70%よりも高い時はゴルフをしたがらないようだ。

最後に、雨の日を2つに分けてみると、風が強い時には客はゴルフをしに来ないことが分かる。

したがって、問題の答えは、この分類木によって端的に次のとおりになる。晴れていてじめじめした日や風の強い雨の日にはゴルフをしに来る人はほとんどいないので、従業員のほとんどを休ませるとよい。それ以外の、多くの人がゴルフをすると思われる日には、仕事を手伝ってくれる臨時従業員を雇う。

このように、決定木は複雑なデータの表現を簡単な構造に変換するのに役立つ。

Segaran, T. 著、當山仁健・鴨澤眞夫訳『集合知プログラミング』（初版）オライリー・ジャパン、2008年。ISBN 978-4-87311-364-7。
Menzies, T.; Hu, Y. (October 2003). “Data mining for very busy people”. IEEE Computer: 18–25.