決定木メモ
はじめに
決定木についてちょっと調べてみたので、メモ。
決定木(decision tree)とは
- 木構造(多分木)を使って、分類・回帰問題を解く
- root(根)を含む各内部ノードは、「変数」を表す
- leaf(葉)は、変数に対する「予測値、分類値」を表す
- 入力xを、ルートからスタートし各ノードの条件に従って葉に来て出力yが決まる
- 連続if-thenだと見ると理解しやすい
- 出力yは、分類ならクラス、回帰なら定数値などになる
- 訓練データD={(x,y)}から木構造を構築することを「決定木の学習」という
- 見た目にもわかりやすく、扱いやすい、比較的単純な機械学習法の一つ
- サイズが小さめならば。
- 精度はあまりでない(らしい)
- 空間を矩形領域でしか区分しないと考えるとそんな感じもする
- 問題点
- 多くの学習方法では、特徴空間の軸に平行(x_0<3.0など)なため、平行でないような場合(x_1>2x_0+3など)に対応できていない(または非効率)
- 特徴空間の領域とただ1つの葉が対応することができない
- 回帰では、葉が離散なので、連続な関数をモデル化しようとしても不連続領域ごとの定数予測になってしまう
学習アルゴリズム
基本的に、ルートノードを設定し、どんどんノードをつなげて木を構築していくようなアプローチ。(または枝かり)
よい木構造を作るためには「各ノードの条件をどのような指標を使って選ぶか」が問題となる。
そこで、混合の度合いを指標にノードの条件を選ぶ。
CART(Classification and Regression Trees)
ID3(Iterative Dichotomiser 3)
- Quinlan, 1986
- 各ノードの条件に「情報量(エントロピー)の期待値が最大になるもの」を選ぶ
C4.5
- Quinlan, 1993
- ID3の拡張
CHAID(Chi-Squared Automatic Integration Detector)
- Kass, 1980
- 各ノードの条件に「カイ二乗統計量」を使用
関連アルゴリズム
Incremental decision tree
- http://en.wikipedia.org/wiki/Incremental_decision_tree
- データの追加・修正に対応した決定木の学習アルゴリズム
ID3を試す
wikipediaに例が載っていたので、ちょっと書いてみる。
(ちょっととか言って、設計めちゃくちゃで実装にはまった、、、)
http://ja.wikipedia.org/wiki/ID3
#include <iostream> #include <vector> #include <map> #include <cmath> //各データ struct Data { std::vector<int> a; //独立変数 int y; //出力 }; //ノード struct Node { bool isleaf; //葉ノードか否か int ai; //ラベル std::vector<int> index; //Dのデータのインデクス std::map<int,int> next; //次のノード番号 Node():isleaf(false), ai(-1){ } }; //ID3アルゴリズム class ID3_train { std::vector<Node> Tree; //木のデータ //対象のindexの出力yの平均情報量を計算 double calc_gain(const std::vector<int> &index, const std::vector<Data> &D){ std::map<int,bool> memo; double ret = 0; for(int i=0; i<index.size(); i++){ memo[D[index[i]].y] = true; } std::map<int,bool>::iterator itr = memo.begin(); for(; itr != memo.end(); ++itr){ int cnt = 0; for(int i=0; i<index.size(); i++){ if(D[index[i]].y == (*itr).first){ cnt++; } } double px = cnt / (double)(index.size()); ret -= px * log(px) / log(3); //wikipediaでは底を3にしていたので。 } return ret; } //対象のindexの中で平均情報量の期待値が最大となる独立変数を返す int select(const std::vector<int> &index, const std::vector<Data> &D){ int ret = -1; double retp = 0.0; double MC = calc_gain(index, D); //ある独立変数aiでindexを分類する for(int ai=0; ai<D[0].a.size(); ai++){ double Mij = 0; std::map<int,bool> memo; for(int i=0; i<index.size(); i++){ memo[D[index[i]].a[ai]] = true; } std::map<int,bool>::iterator itr = memo.begin(); for(; itr != memo.end(); ++itr){ //Cijに分割 std::vector<int> idx; for(int i=0; i<index.size(); i++){ if(D[index[i]].a[ai] == (*itr).first){ idx.push_back(index[i]); } } Mij += calc_gain(idx, D) * (double)(idx.size()) / (double)(index.size()); } double Mi = MC - Mij; if(Mi > retp){ retp = Mi; ret = ai; } } return ret; } //対象のindexの中で、独立変数がaiのものの値の種類を返す std::vector<int> indexlist(const std::vector<int> &index, int ai, const std::vector<Data> &D){ std::map<int,bool> memo; std::vector<int> ret; for(int i=0; i<index.size(); i++){ memo[D[index[i]].a[ai]] = true; } std::map<int,bool>::iterator itr = memo.begin(); for(; itr != memo.end(); ++itr){ ret.push_back((*itr).first); } return ret; } public: //学習 void train(const std::vector<Data> &D){ int tree_index = 0; Node empty; //rootノードの作成 Tree.push_back(empty); for(int i=0; i<D.size(); i++){ Tree[0].index.push_back(i); } //繰り返し while(tree_index < Tree.size()){ //大きくなりすぎたら、エラーで終了にする if(Tree.size() > 1000){ std::cerr << "error: cannot make tree." << std::endl; Tree.clear(); return; } bool issame = true; int tmp = -1; for(int i=0; i<Tree[tree_index].index.size(); i++){ if(tmp == -1){ tmp = D[Tree[tree_index].index[i]].y; } else { if(tmp != D[Tree[tree_index].index[i]].y) issame = false; } } if(Tree[tree_index].index.size() == 1 || issame){ //すべての出力が同じなので、次のノードへ Tree[tree_index].ai = tmp; Tree[tree_index].isleaf = true; tree_index++; continue; } //平均情報量の最大となる独立変数 Tree[tree_index].ai = select(Tree[tree_index].index, D); //その独立変数の値のリスト std::vector<int> index_list = indexlist(Tree[tree_index].index, Tree[tree_index].ai, D); //新しいノードを追加 for(int i=0; i<index_list.size(); i++){ Tree.push_back(empty); Tree[tree_index].next[index_list[i]] = Tree.size()-1; } //インデクスを継承する for(int i=0; i<index_list.size(); i++){ for(int j=0; j<Tree[tree_index].index.size(); j++){ if(D[Tree[tree_index].index[j]].a[Tree[tree_index].ai] == index_list[i]){ Tree[Tree[tree_index].next[index_list[i]]].index.push_back(Tree[tree_index].index[j]); } } } tree_index++; } for(int i=0; i<Tree.size(); i++){ std::cerr << "Tree[" << i << "]=============" << std::endl; std::cerr << " isleaf: " << Tree[i].isleaf << std::endl; std::cerr << " ai: " << Tree[i].ai << std::endl; } } //予測 int predict(const std::vector<int> &a){ int ret = 0; int tree_index = 0; while(true){ std::cerr << "node : " << tree_index << std::endl; if(Tree[tree_index].isleaf){ ret = Tree[tree_index].ai; break; } tree_index = Tree[tree_index].next[a[Tree[tree_index].ai]]; } return ret; } }; int main(){ int N, M; std::vector<Data> D; //データ数と独立変数の数 std::cin >> N >> M; //データの読み込み「出力 独立変数1の値 独立変数2の値 ... 」 for(int i=0; i<N; i++){ Data d; int y, x; std::cin >> y; d.y = y; for(int j=0; j<M; j++){ std::cin >> x; d.a.push_back(x); } D.push_back(d); } //ID3アルゴリズム ID3_train dt; //学習 dt.train(D); //予測 { std::vector<int> d; int x; while(std::cin >> x){ d.clear(); d.push_back(x); for(int i=1; i<M; i++){ std::cin >> x; d.push_back(x); } std::cout << "=>" << dt.predict(d) << std::endl; } } return 0; }
- 入力
- http://ja.wikipedia.org/wiki/ID3 の「実行例」に対応(番号に置き換え)
- 学習
5 3 0 0 0 0 1 0 1 0 1 1 1 0 2 0 0 1 0 1 0 0
-
- 予測
0 0 0 0 1 0 1 1 0 0 0 1 1 0 0
- 結果
Tree[0]============= isleaf: 0 ai: 1 Tree[1]============= isleaf: 0 ai: 2 Tree[2]============= isleaf: 1 ai: 1 Tree[3]============= isleaf: 1 ai: 0 Tree[4]============= isleaf: 1 ai: 2 node : 0 node : 1 node : 3 =>0 node : 0 node : 2 =>1 node : 0 node : 2 =>1 node : 0 node : 1 node : 4 =>2 node : 0 node : 1 node : 3 =>0
同じっぽい。
wikipediaのページの0.667はどこから出てきた数値なのか、、、
