機械学習 リファレンス マニュアル
- イントロダクション，共通のクラスと関数（Introduction. Common classes and functions）
- ナイーブベイズ（単純ベイズ）分類器（Normal Bayes Classifier）
- K近傍法（K Nearest Neighbors）
- サポートベクターマシン（SVM）
- 決定木（Decision Trees）
- ブースティング（Boosting）
- ランダムツリー（Random Trees）
- EMアルゴリズム（Expectation-Maximization）
- ニューラルネットワーク（Neural Networks）
決定木（Decision Trees）
このセクションで議論される ML クラスは， [Brieman84] で述べられる分類木および回帰木のアルゴリズムを提供する．
CvDTreeクラスは，これ単体で用いられる単一決定木，あるいは決定木集合の基底クラスとして用いられる （Boosting と Random Trees を参照）．
決定木は二分木（つまり，それぞれの葉以外のノードがちょうど二つずつの子ノードを持つような木）である． 木の葉がそれぞれ，あるクラスラベルを持つ（複数の葉が同じラベルを持つこともある）場合には分類に， 木の葉がそれぞれ，定数を持つ場合には回帰に（このような決定木は近似関数とも見なせるが，これは区分的に一定な値（つまり離散値）を出力することになる），用いられる．
決定木による予測
予測手続きは，ルートノードから開始して葉に到達することで，入力特徴ベクトルに対する応答を得る． この処理は，ある変数の値を基に，葉ではない各ノードから左（つまり次の観測ノードとして左側の子ノードを選択），あるいは右に分岐して進む． そのインデックスは観測ノードに保存される．変数は連続変数，あるいはカテゴリ変数を取り得る．1番目のケース（入力が連続変数）では， 入力された変数値はある閾値（これもノードに保存されている）と比較され，その値が閾値より小さい場合は左に，そうでない場合は右に進む （例えば重さが 1kgよりも軽い場合は左に，重い場合は右に進む）． そして2番目のケース（入力がカテゴリ変数）では，入力された離散変数値が取りうる値の有限集合の内，ある値の部分集合（これもノードに保存される）に属するかが調べられる． 属している場合は左に，そうでない場合は右に進む（例えば色が緑か赤の場合は左に進み，そうでない場合は右に進む）． つまり各ノードにおいてエンティティのペア（<variable_index>, <decision_rule (threshold/subset)>）が用いられる． このペアは，分岐（変数 #<variable_index> による分岐）と呼ばれる．葉ノードに到達すると，そのノードの値が予測の出力値となる．
まれに，入力ベクトルのある特徴が欠損する（例えば，暗い場所ではオブジェクトの色を測定することが困難）と， 予測手続きが，あるノード（前述の例では色で分岐するノードの条件）で行き詰まるかもしれない． このような状況を回避するために，決定木は，いわゆる代理分岐（surrogate split）を利用する． つまり最適な「第一」分岐に加えて，決定木の各ノードが，ほぼ同じ結果を与える一つ以上の別の変数によって分岐することがある．
決定木の学習
決定木の構築はルートノードから開始され，再帰的に行われる．
全学習データ（特徴ベクトル，およびそれに対する応答）は，ルートノードを分岐させるために用いられる．
各ノードにおいて，ある基準（機械学習では，分類にはジニ（GINI）「純粋」指標が，回帰には誤差の2乗の和が用いられる）に基づき，
最適な決定規則（つまり，最適な「第一」分岐）が求められる．必要ならば，学習データにおける第一分岐の結果に類似した代理分岐を求める．
すべてのデータは，第一分岐と代理分岐を利用して（まさに予測手続きでされるように）左右の子ノードに分類される．
そして，この分類処理は左右のノードでも再帰的に行われる．以下のいずれかの場合に，各ノードにおける再帰的処理が停止する（つまりノードがそれ以上分岐しない）．
- 木の枝の深さが指定した最大値に到達した場合．
- ノードの学習サンプル数が指定した閾値以下，つまり，そのサンプルがノードをさらに分岐させるための統計的な代表集合ではない場合．
- ノードの全サンプルが同じクラスに属する（あるいは回帰の場合，分散が非常に小さい）場合．
- その第一分岐が，単なるランダム選択と同程度の効果しか示さない場合．
木が構成された後，必要ならば交差検証法（cross-validation）により不要なデータが取り除かれる． つまり，モデルを過剰適合させてしまうような木の枝が刈られる．この手続きは通常，スタンドアロンな決定木に対してのみ用いられる． 一方，決定木集合の場合は通常，十分に小さい木々を構成することで，過剰適合に対する自身の防護機構が働く．
変数の重要度
決定木は，予測はもちろんの事，他にも様々なデータ解析に利用できる． ここでキーとなる性質の一つは，決定木のアルゴリズムは各変数の重要度（relative decisive power）が計算できるという事である． 例えばスパムフィルタで，文章中に登場する単語の集合を特徴ベクトルとして用いると，変数の重要度評価は，最も「スパムらしい」 単語を決定するために利用でき，その結果，適切な辞書のサイズを保つのに役立つ．
各変数の重要度は，その変数が通過する木の第一分岐と代理分岐全てを使って計算される． 従って，変数の重要度を正しく計算するためには，たとえデータ欠損がない場合でも，学習パラメータにおいて代理分岐が有効でなければならない．
CvDTreeSplit
決定木ノードの分岐
struct CvDTreeSplit
{
int var_idx;
int inversed;
float quality;
CvDTreeSplit* next;
union
{
int subset[2];
struct
{
float c;
int split_point;
}
ord;
};
};
- var_idx
- 分岐で用いられる変数のインデックス．
- inversed
- 1の場合，逆分岐規則が用いられる（つまり左右の枝が交換される）．
- quality
- 正の数で表現される分岐のクオリティ． これは最も重要な分岐の選択，代理分岐の選択・ソートに用いられる．木が構成された後は，変数の重要度を計算するために用いられる．
- next
- ノード分岐リスト内の次の分岐へのポインタ．
- subset
- カテゴリ変数に対する分岐の場合，部分集合を表すビット配列．
var_value が subset に属する場合 next_node<-left ，そうでない場合 next_node<-right．
- c
- 連続変数に対する分岐の場合，閾値．
var_value < c の場合 next_node<-left ，そうでない場合 next_node<-right． - split_point
- 学習アルゴリズムで内部的に利用される．
CvDTreeNode
決定木ノード
struct CvDTreeNode
{
int class_idx;
int Tn;
double value;
CvDTreeNode* parent;
CvDTreeNode* left;
CvDTreeNode* right;
CvDTreeSplit* split;
int sample_count;
int depth;
...
};
- value
- 木のノードに割り当てられた値．これはクラスラベルか，推定された関数値のいずれかとなる．
- class_idx
- ノードに割り当てられた正規化されたクラスインデックス（0 から class_count-1 までの範囲）．分類木と木集合の内部で用いられる．
- Tn
- 複数の木を順番に並べた場合の木のインデックス．これらのインデックスは，刈り込み手続き中およびその後に利用される． ルートノードは，木全体における最大値 Tn を持ち，子ノードは親ノードのTn 以下の Tn を持つ． Tn≤CvDTree::pruned_tree_idx となるノードは， 刈り込みを行う際にそれらが木から物理的に削除されなくても，予測ステージにおいて考慮されない（対応する枝が刈り込まれたものと見なされる）．
- parent, left, right
- 親ノード，子ノード（左），子ノード（右）へのポインタ．
- split
- 最初の（第一）分岐へのポインタ．
- sample_count
- 学習ステージでノードに分類されるサンプル数．
これは困難なケースを解決するために用いられる．つまり第一分岐の変数が見つからず，他の全ての代理分岐に対する変数も見つからない場合は，
left->sample_count>right->sample_count のとき，サンプルは左に向かい，そうでなければ右に向かう． - depth
- ノードの深さ．ルートノードの深さは 0 であり，子ノードの深さは親ノードの深さ +1 となる．
CvDTreeNode の他の多数のフィールドは，学習ステージにおいて内部的に利用される．
CvDTreeParams
決定木の学習パラメータ
struct CvDTreeParams
{
int max_categories;
int max_depth;
int min_sample_count;
int cv_folds;
bool use_surrogates;
bool use_1se_rule;
bool truncate_pruned_tree;
float regression_accuracy;
const float* priors;
CvDTreeParams() : max_categories(10), max_depth(INT_MAX), min_sample_count(10),
cv_folds(10), use_surrogates(true), use_1se_rule(true),
truncate_pruned_tree(true), regression_accuracy(0.01f), priors(0)
{}
CvDTreeParams( int _max_depth, int _min_sample_count,
float _regression_accuracy, bool _use_surrogates,
int _max_categories, int _cv_folds,
bool _use_1se_rule, bool _truncate_pruned_tree,
const float* _priors );
};
- max_depth
- このパラメータは木が取りうる最大の深さを決定する．学習アルゴリズムは，ノードの深さが max_depth よりも小さいならば，それを分岐させようとする．他の終了条件が満たされた場合や（セクション始めにある学習手続きの概要を参照）， あるいは/さらに，木が刈り込まれた場合など，実際の深さはもっと浅いかもしれない．
- min_sample_count
- あるノードに対するサンプル数がこのパラメータ値よりも少ない場合，そのノードは分岐しない．
- regression_accuracy
- 別の終了条件 - 回帰木の場合のみ． 推定されたノード値が，そのノードの学習サンプルの応答に対して，このパラメータ値よりも低い精度を持つ場合，ノードはそれ以上分岐しなくなる．
- use_surrogates
- trueの場合，代理分岐が構築される． 代理分岐は観測値データの欠損を処理する場合や，変数の重要度の推定に必要である．
- max_categories
- 学習手続きが分岐を作るときの離散変数が max_categoriesよりも多くの値を取ろうとするならば，
（アルゴリズムが指数関数的であるので）正確な部分集合推定を行う場合に非常に時間がかかる可能性がある．
代わりに，（MLを含む）多くの決定木エンジンが，全サンプルを max_categories 個のクラスタに分類することによって
（つまりいくつかのカテゴリは一つにマージされる），この場合の次善最適分岐を見つけようとする．
このテクニックは，N(>2)-クラス分類問題においてのみ適用されることに注意する． 回帰および 2-クラス分類の場合は，このような手段をとらなくても効率的に最適分岐を見つけることができるので，このパラメータは使用されない． - cv_folds
- このパラメータが >1 の場合，木は cv_folds 分割交差検証法により刈り込まれる．
- use_1se_rule
- true の場合，木は刈り込み手続きによって切り捨てられる． これにより，コンパクトで学習データノイズに対してより耐性を持つような木になるが，決定木の正確さはやや劣る．
- truncate_pruned_tree
- true の場合，（Tn≤CvDTree::pruned_tree_idxである） カットオフノードが，木から物理的に削除される． そうでない場合は，それらは削除はされず，CvDTree::pruned_tree_idx を減らす（例えば -1 を設定する） ことによって，オリジナルの刈り込みされていない（あるいは積極的には刈り込まれていない）木からの結果を得ることができる．
- priors
- クラスラベル値によって保存されたクラス事前確率の配列．
このパラメータは，ある特定のクラスに対する決定木の優先傾向を調整するために用いられる．
例えば，もしユーザがなんらかの珍しい例外的発生を検出したいと考えた場合，学習データは，おそらく例外的なケースよりもずっと多くの正常なケースを含んでいるので，
全ケースが正常であるとみなすだけで，非常に優れた分類性能が実現されるだろう．
このように例外ケースを無視して分類性能を上げることを避けるために，事前確率を指定することができる．
例外的なケースの確率を人工的に増加させる（0.5 まで，あるいはそれ以上に）ことで，分類に失敗した例外の重みがより大きくなり，木は適切に調節される．
メモリの取り扱いに関する注意：priors フィールドは， 単精度浮動小数点型（float）配列へのポインタである． 配列はユーザによって確保され，構造体CvDTreeParams が CvDTreeTrainData あるいは CvDTree コンストラクタ/メソッド（メソッドは配列のコピーを作る）に渡された直後に解放されるべきである．
この構造体は，決定木の学習パラメータの全てを含んでいる． デフォルトコンストラクタは，全てのパラメータを，スタンドアロンな分類木用に調整されたデフォルト値で初期化する． いずれのパラメータもオーバーライド可能で，この構造体は改良型のコンストラクタを用いて完全に初期化されるかもしれない．
CvDTreeTrainData
決定木の学習データ，および決定木集合の共有データ
struct CvDTreeTrainData
{
CvDTreeTrainData();
CvDTreeTrainData( const CvMat* _train_data, int _tflag,
const CvMat* _responses, const CvMat* _var_idx=0,
const CvMat* _sample_idx=0, const CvMat* _var_type=0,
const CvMat* _missing_mask=0,
const CvDTreeParams& _params=CvDTreeParams(),
bool _shared=false, bool _add_labels=false );
virtual ~CvDTreeTrainData();
virtual void set_data( const CvMat* _train_data, int _tflag,
const CvMat* _responses, const CvMat* _var_idx=0,
const CvMat* _sample_idx=0, const CvMat* _var_type=0,
const CvMat* _missing_mask=0,
const CvDTreeParams& _params=CvDTreeParams(),
bool _shared=false, bool _add_labels=false,
bool _update_data=false );
virtual void get_vectors( const CvMat* _subsample_idx,
float* values, uchar* missing, float* responses, bool get_class_idx=false );
virtual CvDTreeNode* subsample_data( const CvMat* _subsample_idx );
virtual void write_params( CvFileStorage* fs );
virtual void read_params( CvFileStorage* fs, CvFileNode* node );
// 全データを解放
virtual void clear();
int get_num_classes() const;
int get_var_type(int vi) const;
int get_work_var_count() const;
virtual int* get_class_labels( CvDTreeNode* n );
virtual float* get_ord_responses( CvDTreeNode* n );
virtual int* get_labels( CvDTreeNode* n );
virtual int* get_cat_var_data( CvDTreeNode* n, int vi );
virtual CvPair32s32f* get_ord_var_data( CvDTreeNode* n, int vi );
virtual int get_child_buf_idx( CvDTreeNode* n );
////////////////////////////////////
virtual bool set_params( const CvDTreeParams& params );
virtual CvDTreeNode* new_node( CvDTreeNode* parent, int count,
int storage_idx, int offset );
virtual CvDTreeSplit* new_split_ord( int vi, float cmp_val,
int split_point, int inversed, float quality );
virtual CvDTreeSplit* new_split_cat( int vi, float quality );
virtual void free_node_data( CvDTreeNode* node );
virtual void free_train_data();
virtual void free_node( CvDTreeNode* node );
int sample_count, var_all, var_count, max_c_count;
int ord_var_count, cat_var_count;
bool have_labels, have_priors;
bool is_classifier;
int buf_count, buf_size;
bool shared;
CvMat* cat_count;
CvMat* cat_ofs;
CvMat* cat_map;
CvMat* counts;
CvMat* buf;
CvMat* direction;
CvMat* split_buf;
CvMat* var_idx;
CvMat* var_type; // i番目の要素が
// k<0 - 連続変数
// k>=0 - カテゴリ変数，cat_* 配列の k番目の要素を参照
CvMat* priors;
CvDTreeParams params;
CvMemStorage* tree_storage;
CvMemStorage* temp_storage;
CvDTreeNode* data_root;
CvSet* node_heap;
CvSet* split_heap;
CvSet* cv_heap;
CvSet* nv_heap;
CvRNG rng;
};
この構造体は通常，スタンドアロンな木と決定木集合の両方を効率的に格納するために内部的に利用される．基本的に3 種類の情報を含む．
- 学習パラメータである CvDTreeParams インスタンス．
- より効率良く最適分岐を見つけるために前処理された学習データ． 決定木集合の場合，この前処理されたデータは全ての木で再利用される． さらに，決定木集合の全ての木で共有される学習データの特徴もここに保存される：様々な型，クラス数，クラスラベル圧縮マップなど．
- バッファ．木ノードや分岐，木構造の他の要素のためのメモリストレージである．
この構造体を扱う方法は二つある． 簡単な場合（例えばスタンドアロンな木や，Random Trees や Boosting のような ML にある，すぐ使える「ブラックボックス」的な決定木集合）は， その構造体を気にしたり，あるいは知る必要さえなく，必要な統計モデルを単に作成し，学習して使うだけである． この場合，構造体 CvDTreeTrainData は内部的に構成・利用されるだろう． しかし独自の木アルゴリズムを利用したり，あるいは別の高度な場合においては，この構造体は明確に構成され，利用されるかもしれない． その概要は以下の通りである．
- 構造体はデフォルトコンストラクタにより初期化された後，set_data される（あるいは完全な書式のコンストラクタによって作成される）． パラメータ_shared は，true に設定されなければならない．
- このデータを用いて一つ以上の木が学習される． 学習についてはCvDTree::train を参照．
- 最後に，これを利用した全ての木が解放された場合に限り，その後でこの構造体が解放される．
CvDTree
決定木クラス
class CvDTree : public CvStatModel
{
public:
CvDTree();
virtual ~CvDTree();
virtual bool train( const CvMat* _train_data, int _tflag,
const CvMat* _responses, const CvMat* _var_idx=0,
const CvMat* _sample_idx=0, const CvMat* _var_type=0,
const CvMat* _missing_mask=0,
CvDTreeParams params=CvDTreeParams() );
virtual bool train( CvDTreeTrainData* _train_data, const CvMat* _subsample_idx );
virtual CvDTreeNode* predict( const CvMat* _sample, const CvMat* _missing_data_mask=0,
bool raw_mode=false ) const;
virtual const CvMat* get_var_importance();
virtual void clear();
virtual void read( CvFileStorage* fs, CvFileNode* node );
virtual void write( CvFileStorage* fs, const char* name );
// 決定木集合における専用の read, write メソッド
virtual void read( CvFileStorage* fs, CvFileNode* node,
CvDTreeTrainData* data );
virtual void write( CvFileStorage* fs );
const CvDTreeNode* get_root() const;
int get_pruned_tree_idx() const;
CvDTreeTrainData* get_data();
protected:
virtual bool do_train( const CvMat* _subsample_idx );
virtual void try_split_node( CvDTreeNode* n );
virtual void split_node_data( CvDTreeNode* n );
virtual CvDTreeSplit* find_best_split( CvDTreeNode* n );
virtual CvDTreeSplit* find_split_ord_class( CvDTreeNode* n, int vi );
virtual CvDTreeSplit* find_split_cat_class( CvDTreeNode* n, int vi );
virtual CvDTreeSplit* find_split_ord_reg( CvDTreeNode* n, int vi );
virtual CvDTreeSplit* find_split_cat_reg( CvDTreeNode* n, int vi );
virtual CvDTreeSplit* find_surrogate_split_ord( CvDTreeNode* n, int vi );
virtual CvDTreeSplit* find_surrogate_split_cat( CvDTreeNode* n, int vi );
virtual double calc_node_dir( CvDTreeNode* node );
virtual void complete_node_dir( CvDTreeNode* node );
virtual void cluster_categories( const int* vectors, int vector_count,
int var_count, int* sums, int k, int* cluster_labels );
virtual void calc_node_value( CvDTreeNode* node );
virtual void prune_cv();
virtual double update_tree_rnc( int T, int fold );
virtual int cut_tree( int T, int fold, double min_alpha );
virtual void free_prune_data(bool cut_tree);
virtual void free_tree();
virtual void write_node( CvFileStorage* fs, CvDTreeNode* node );
virtual void write_split( CvFileStorage* fs, CvDTreeSplit* split );
virtual CvDTreeNode* read_node( CvFileStorage* fs, CvFileNode* node, CvDTreeNode* parent );
virtual CvDTreeSplit* read_split( CvFileStorage* fs, CvFileNode* node );
virtual void write_tree_nodes( CvFileStorage* fs );
virtual void read_tree_nodes( CvFileStorage* fs, CvFileNode* node );
CvDTreeNode* root;
int pruned_tree_idx;
CvMat* var_importance;
CvDTreeTrainData* data;
};
CvDTree::train
決定木を学習する
bool CvDTree::train(const CvMat* _train_data, int _tflag, const CvMat* _responses, const CvMat* _var_idx=0, const CvMat* _sample_idx=0, const CvMat* _var_type=0, const CvMat* _missing_mask=0, CvDTreeParams params=CvDTreeParams() ); bool CvDTree::train(CvDTreeTrainData* _train_data, const CvMat* _subsample_idx );
CvDTree には二つの train メソッドが存在する．
1番目のメソッドは，一般的な CvStatModel::trainの仕様の，最も完全な書式に従う． 両方のデータレイアウト（_tflag=CV_ROW_SAMPLE と _tflag=CV_COL_SAMPLE） がサポートされる． また，サンプルと変数の部分集合，データ欠損，入出力変数型の任意の組み合わせなども同様にサポートされる． 最後のパラメータは必要な全ての学習パラメータを含む．CvDTreeParams の記述を参照すること．
2番目の train メソッドは，主に決定木集合を作成するために用いられる． これは，あらかじめ作成された CvDTreeTrainData のインスタンスと，オプションとして学習データ集合の部分集合を引数にとる． _subsample_idx の値は，相対的に _sample_idxのインデックス値と見なされ， CvDTreeTrainDataコンストラクタに渡される． 例えば_sample_idx=[1, 5, 7, 100] の場合，_subsample_idx=[0,3] は， 元の学習データ集合のサンプルの内の [1, 100] が使われることを意味する．
CvDTree::predict
入力ベクトルに対する決定木の葉ノードを返す
CvDTreeNode* CvDTree::predict(const CvMat* _sample, const CvMat* _missing_data_mask=0,
bool raw_mode=false ) const;
このメソッドは，特徴ベクトルとオプションとしてデータ欠損マスクを入力として受け取り，決定木を辿って到達した葉ノードを出力として返す． 予測結果として，クラスラベルあるいは推定関数値が， 構造体 CvDTreeNode のvalue フィールド，例えば dtree->predict(sample,mask)->value に代入される．
最後のパラメータは大抵，通常の入力を意味するfalse に設定される． もしこれが true の場合，このメソッドは離散入力変数の全ての値があらかじめ， 0..<num_of_categoriesi>-1 の範囲に正規化されていることを仮定する （決定木は内部的にはこのような正規化された表現を用いている）．これは決定木集合の高速な予測に役立つ．連続変数の入力変数に対しては，このフラグは利用されない．
（例）キノコを分類する木の作成
決定木の作り方と使い方のサンプル mushroom.cppを参照すること．