別の記事で勾配ブースティング手法を勉強しようとしているのですが、そこでよく用いられる決定木について知らなかったので決定木の話を書きました。初学者なのでおかしい点がありましたらご指摘いただけますと幸いです。
参考文献
- はじめてのパターン認識 | 平井 有三 |本 | 通販 | Amazon
- 11章で決定木を扱っています。
- 統計的学習の基礎 ―データマイニング・推論・予測― | Trevor Hastie, Robert Tibshirani, Jerome Friedman, 杉山 将, 井手 剛, 神嶌 敏弘, 栗田 多喜夫, 前田 英作, 井尻 善久, 岩田 具治, 金森 敬文, 兼村 厚範, 烏山 昌幸, 河原 吉伸, 木村 昭悟, 小西 嘉典, 酒井 智弥, 鈴木 大慈, 竹内 一郎, 玉木 徹, 出口 大輔, 冨岡 亮太, 波部 斉, 前田 新一, 持橋 大地, 山田 誠 |本 | 通販 | Amazon
- 9章で決定木を扱っています。
- Induction of Decision Trees
- ID3 開発者による ID3 及びその改善点についての論文で1986年のものですが、ID3 自体は1979年に発表されたものであるようです。C4.5 につながる連続値の取り扱いや情報量ゲイン比についても記述されています。
- A Brief History of Classification and Regression Trees
- 拾い物のスライドですが、決定木の歴史について詳しそうです。
- A comparative study of decision tree ID3 and C4.5
- C4.5 について記述がありそうだったのでメモしましたが、ちゃんと読んでいません。
- ID3 - Wikipedia
- 例を借用したんですが、実は ID3 自体はこの例のような3値以上の分類に対応していないようです。
Appendix1. 自分が初めて決定木を学ぶ上で勝手に混乱したという読み飛ばしていい話
決定木について調べると、「決定木生成アルゴリズムの代表例として ID3、C4.5、CART などがある」と紹介されていることが多いと思います。それらが決定木生成アルゴリズムであることに間違いはないですが、一つのアルゴリズムというよりはむしろ必要な要素アルゴリズムを組み合わせて実行できるようにしたプログラム／システム（それもかなり古い）です（のはず）。なので、それらについて調べようとしても明確な数学的定義というよりは当時こんなものが発表されたという断片的な情報が多いです（CART については当時原書籍が出たことしか自分はわからなかったので、そもそも各要素が一義的にこれと定められていたのかも自分はよくわかっていません）。また、ID3、C4.5、CART の要素アルゴリズムの組み合わせは必然性が強いというものではないはずです。なので、ID3、C4.5、CART などが決定木を学ぶ軸になるというものではないです。自分で学ぼうとするとき、それらを踏まえないと混乱すると思います。そもそも ID3（1979年）と C4.5（1993年）は Quinlan さんが開発した分類木生成プログラムであり、CART（1984年）は Breiman さんらがまとめた回帰／分類木生成システムです（のはず）（ただし CART といったとき、現在まで改修され続けている CART の血を継ぐ各種パッケージのこととか、もっと一般的な回帰／分類木を生成する方法論を指していることも多いと思います）。決定木を生成する典型的な方法は「分岐に利用する特徴と境界をどのように選ぶか」「どこまで分岐させるか」「終端にどんな予測値を割り当てるか」の3つの要素をどう実現するか決めることで（参考文献1. 178ページ）、ID3 も C4.5 も CART もこの3つの要素を何か実装しています（かつ、その実装により対応できる入出力の型がカテゴリ値のみか連続値も可能か決まっています）。ただそれはプログラムの実装がそうなっているというだけです。例えば ID3 は連続入力値を扱えないとされますが、いま私たちが再実装するならば閾値探索を入れる拡張は容易にできるはずです。なんというか、ID3 の特徴選択基準（情報量ゲイン）が絶望的に連続値に対応できないというわけではないです。
いいたいことは、ID3、C4.5、CART は厳密にこんな要素の組み合わせなのだと明らかにしようとするのは歴史の勉強でしかなくて（もちろんその組み合わせで概してどのような学習の傾向がみられたという情報は重要ですが）、大事なのは決定木生成アルゴリズムがどのような要素アルゴリズムからなり（＝上述の緑太字）、それぞれの要素アルゴリズムにどのようなバリエーションがあり、それぞれのバリエーションがどのような意味をもつのかだと思います。無論、上の3つの要素の組み合わせにあてはまらない木もあります（階層的混合エキスパートなど）。
Appendix2. ID3、C4.5、CART のまとめ
Appendix1. にかいた通り ID3、C4.5、CART が厳密にどうなっているかを追いかけることは本質的ではないと思いますが、どのようなアイデアが含まれているか自体は重要と思うので自分の認識をまとめておきます。正確ではないです。| ID3 | C4.5 | CART | ||
|---|---|---|---|---|
| 入力ベクトルの型 | カテゴリ値（欠損不可） | カテゴリ値 or 連続値（欠損可） | ||
| 目的変数の型 | 2値カテゴリ値（3値以上の場合は各カテゴリ値かどうかで別々に木をつくる） | 連続値 | ||
| 分岐の仕方のよさの指標 | 分岐後のノードたちのエントロピーのデータ数重み付き平均が小さいような分岐ほどよい分岐とする。 ⇔ 分岐元ノードのエントロピーに比べて分岐後のノードたちのエントロピーの重み付き平均がどれだけ減ったかをその分岐の情報量ゲインと定義し、情報量ゲインが大きい分岐ほどよい分岐とする。 |
ID3 と似ているが、情報量ゲインは分岐が多いほど大きくなりがちなので、過学習を防ぐ観点から、情報量ゲインを分岐のエントロピー（たくさん枝分かれさせると大きい）で割った情報量ゲイン比に修正し、情報量ゲイン比が大きい分岐ほどよい分岐とする。 | 典型的には分岐後のノードたちのジニ指数のデータ数重み付き平均が小さいような分岐ほどよい分岐とする。ただノードにおける目的変数の不純度を測る指標なら何でもよくて、エントロピーなどでもよいはず。 | 分岐後の誤差2乗和が最小となる分岐ほどよい分岐とする（他の誤差の指標も適用できそうだが）。 |
| その指標にしたがって分岐させる方法 | 各カテゴリ特徴について、カテゴリ値が取りうる値だけ分岐させたときの分岐の情報量ゲインを計算し、最も情報量ゲインの大きい特徴で分岐させる。 | 特徴がカテゴリ値の場合は、C4.5はID3同様にカテゴリ値がとりうる値だけ分岐させたときの分岐のよさの指標を計算する？ CARTについては2分岐しかしないという情報を散見するので、3値以上とりうるカテゴリ値はone-hotにするんだと思う。パッケージによると思う。 特徴が連続値の場合は閾値によって2つの枝に分岐させるすべてのパターンについて分岐のよさの指標を計算する。 何にせよ、最も分岐のよさの指標がよい特徴および分岐パターン／閾値で分岐させる。 | ||
| 一旦どこまで分岐させるかのルール | ノードに同一ラベルのデータしか存在しなくなったらそこで止める。または、分岐させることのできる特徴がなくなってしまったらそこで止める。または空のノードができたらそこで止める（とりうるカテゴリ値の枝を全てつくるらしいので空ノードがありうる）。 | 参考文献2. の記述では、終端ノードに振り分けられるデータ数がある値まで小さくなるまで分割するというようにある（351ページ）。 | ||
| 一旦どこまで分岐させた後に余分な枝を刈り取るルール | 刈り取らない。 | 刈り取る。後で追記。 | 「判定の誤りの指標」に「終端の数」を適当なバランスで足し合わせた「修正誤り指標（木のコスト）」をつくって、修正誤り指標の削減に貢献していない枝を刈り取る。 | |
| 終端ノードに割り当てる予測値 | 通常は終端ノードに振り分けられたデータの目的変数の平均値。後で追記。 | |||
決定木とは
決定木はあなたにまず最初の質問を出してきます。あなたがその質問に答えるとその答えによって別の異なる質問を出してきます。その質問にも答えるとまた別の異なる質問を出してきます。それを何度か繰り返したのち、あなたに何か判定結果を下してきます。そんな木です。要するにアキネイターです。やりたいこと
既にいるアキネイターから判定結果を得るには質問に答えていけばいいです。いまやりたいのは新しいアキネイターをつくることです。言い換えると、- 目的は個々の入力データに対して何らかの判定をすることです（※1）。
- それを達成する方針として、入力データに、入力データが答えらえる質問を繰り返すことにします。
- やるべきことはこの「どんな質問たちを、どんな順番で出して、どんな判定を下すか」のマニュアルを完全に決めることです。そういうマニュアルを学習データを利用してつくります。
※1. 判定するとは例えば、服屋に来店する個々のお客さんがどの商品を欲しがるかとかです。服屋に来店するお客さんという入力データには「男性か女性か」「子どもか大人か」「背が高いか低いか」のような質問ができそうです。「江戸時代のご先祖が武士だったか」のような、来店するお客さんのデータで答えられない質問は駄目です。また、「どの商品が欲しいか」自体を訊くのもいまは駄目です。というかそれが訊けるなら訊いた方がいいですが、新しく来店したお客さんはまだこの店のラインナップをよく知らないので、こちらで何がお気に召しそうか予測して売り場にご案内したいという状況とでも考えてください。
やりかた
しかしそのようなマニュアル＝木をつくるのは大変そうです。入力データに訊くべき質問は色々ありえるし、質問の順番も決めなければなりません。学習データに対してなるべく正しい判定をする木を探せばよさそうですが、極端な話、何も考えずに木をどこまでも枝分かれさせれば個々の学習データを完全に正しく判定する木というのができてしまいそうです。しかし、そんな木はきっと学習データの思わぬノイズまでも学習してしまって未知データへの性能が悪そうです。なので、「ノイズらしきデータからはなるべく学習しない」を満たすような木のつくり方をしたい気がします。
基本的な決定木生成アルゴリズムでは、質問は以下のようにすることに決めています。
- 1回の質問では「1つの特徴の値がどんなか」のみを訊く（※2）。
※2. つまり「2つの数値的特徴の積がどんなか」のような質問は訊かないことにしているわけです。アルゴリズムの中でそのような質問も考慮してみてもいいかもしれませんが、それを常に調べるのはとても時間がかかりそうですし、個別の特徴への質問を組み合わせて繰り返せば近似的に「2つの特徴の積がどんなか」っぽい振り分けは達成できそうです。しかし、ある2つの特徴の積を考慮した方がよいと信じられる状況であれば、それを新たな特徴として追加しておくのがよいと思います。
誤差2乗和による回帰木の生成
後で追記。情報量ゲインによる分類木の生成
後で追記。下のスクリプトを参照。ジニ指数による分類木の生成
後で追記。計算用スクリプト（アルゴリズムの実装ではありません）
情報量ゲインによる分類木の生成です。ウィキペディアのID3の例を借りていますが、実はID3自体はこの例のような3値以上の分類に対応していません。目的変数が3値以上でもエントロピーを計算することはできますが、「それでエントロピーが小さい方がよりよい分岐の仕方といえるのか」というところがあやしくなってくるんだと思います。しかし下の例ではそういう細かい点は無視することにしてアルゴリズムを実行しています。
import numpy as np import pandas as pd from collections import OrderedDict # 準備．pandas.Series を渡すとユニーク要素ごとの出現確率のベクトルを返す関数 def get_probabilities(series): probabilities = series.value_counts() / series.shape return probabilities # 準備．離散確率分布を渡すと平均情報量を返す関数（ウィキペディアに合わせて対数の底=3） def get_entropy(probabilities): return np.sum(probabilities * np.log2(1.0 / probabilities) / np.log2(3.0)) # 準備．データとラベル名と特徴名とその特徴のあるカテゴリ値を渡すと # 「各特徴が各カテゴリ値か否か」で2ノードに分岐させたときの # 各ノードの平均情報量を各ノードに振り分けられるデータ数で重み付き平均した値を返す関数 def get_expected_entropy(df, label_name, feature_name, feature): df0 = df[df[feature_name]!=feature] w0 = df0.shape[0] / df.shape[0] df1 = df[df[feature_name]==feature] w1 = df1.shape[0] / df.shape[0] return w0 * entropy(get_probabilities(df0[label_name])) \ + w1 * entropy(get_probabilities(df1[label_name])) # ------------------------- やりたいことはここから ------------------------- # いまやりたいことは、以下の「食性」「発生」「体温」の特徴から「分類」を予測すること od = OrderedDict() od['名前'] = ['ペンギン', 'ライオン', 'ウシ', 'トカゲ', 'ブンチョウ'] od['食性'] = [ '肉食', '肉食', '草食', '肉食', '草食'] od['発生'] = [ '卵生', '胎生', '胎生', '卵生', '卵生'] od['体温'] = [ '恒温', '恒温', '恒温', '変温', '恒温'] od['分類'] = [ '鳥類', '哺乳類', '哺乳類', '爬虫類', '鳥類'] df = pd.DataFrame(od) print(df) # まずすべてのデータを根ノードに所属させる # 根ノードでの平均情報量をみる ent = get_entropy(get_probabilities(df['分類'])) print(ent) # 0.9602297178607613 ... 平均情報量が大きいほどこのノードでの混じり気が大きい # 混じり気が小さくなるように分岐させたいので、「各特徴が各カテゴリ値か否か」で2ノードに分岐させたときの # 各ノードの平均情報量を各ノードに振り分けられるデータ数で重み付き平均した値が、 # いまの混じり気よりもどれだけ減るかをみる print(ent - get_expected_entropy(df, '分類', '食性', '肉食')) # 食性が肉食か否か --> 0.1078578164321784 print(ent - get_expected_entropy(df, '分類', '発生', '卵生')) # 発生が卵生か否か --> 0.6126016192893443 print(ent - get_expected_entropy(df, '分類', '体温', '恒温')) # 体温が恒温か否か --> 0.45548591500359525 # 「発生が卵生か否か」が最も混じり気を減らすのでそれで分岐させることに決める df_0 = df[df['発生']!='卵生'] df_1 = df[df['発生']=='卵生'] ent_0 = get_entropy(get_probabilities(df_0['分類'])) ent_1 = get_entropy(get_probabilities(df_1['分類'])) print(ent_0) # 0.0 --> こちらのノードではすでに混じり気なし（発生が胎生なら分類は哺乳類でしかない） print(ent_1) # 0.5793801642856949 --> このノードではまだ混じり気あり # 混じり気を小さくしたいので、また分岐を試みる print(ent_1 - get_expected_entropy(df_1, '分類', '食性', '肉食')) # 食性が肉食か否か --> 0.15876032857138994 print(ent_1 - get_expected_entropy(df_1, '分類', '体温', '恒温')) # 体温が恒温か否か --> 0.5793801642856949 # 「体温が恒温か否か」が最も混じり気を減らす（というか完全に混じり気を減らす）のでそれで分岐させることに決める df_1_0 = df_1[df_1['体温']!='恒温'] df_1_1 = df_1[df_1['体温']=='恒温'] ent_1_0 = get_entropy(get_probabilities(df_1_0['分類'])) ent_1_1 = get_entropy(get_probabilities(df_1_1['分類'])) print(ent_1_0) # 0.0 --> 混じり気なし（卵生かつ変温なら爬虫類） print(ent_1_1) # 0.0 --> 混じり気なし（卵生かつ恒温なら鳥類） # よって、やりたいことは、以下の木にしたがって分類することで達成される # 「発生が卵生か」 -- No --> 哺乳類 # -- Yes --> 「体温が恒温か」-- No --> 爬虫類 # -- Yes --> 鳥類
