この記事の読者
キーワード・知ってると理解がしやすい
- 集合論
- 判別関数 / 識別関数
確率
- 事後確率
- 同時確率
- 周辺確率
事後確率について
同時確率について
決定木 / Decision Tree #まとめ編
Index
決定木アルゴリズム / Decision Tree
単純な識別規則を組み合わせて複雑な識別境界 / 非線形な識別空間を取得する手法.
識別関数は、非線形関数となるのが特徴.
上図ように、ある特徴軸 (上図でいうと、x1, x2) の「データ値」と「閾値 (上図でいうと、a ~ e) 」の大小関係を判断する過程は、下図のように決定木として表現できる.
構成要素
木を構成する要素は、
- ノード
- ノードとノードを結ぶリンク
ノードにも種類があり、以下のように呼称する.
- 一番最初のノードを根ノード
- 一番末端のノードを終端ノード、葉ノード
- 根ノードでも葉ノードでもないノードを内部ノード
葉ノード以外のノード(非終端ノード)で、閾値判断が行われる.
与えられたデータがどちらのクラスに属するかは、葉ノードが決定する.
ボトムアップとトップダウン
現在はトップダウン的な手法で決定木を構築するのが主流.
トップダウン的な手法で決定木を学習データから構築するためには、次の要素について考える必要がある.
- 各ノードにおいて特徴空間分割規則を構成するための「特徴軸」と「閾値」の選択.
- 葉ノードの決定. 一つの葉ノードに一つのクラスの学習データのみが含まれるまで特徴量空間の分割を繰り返し大きな木を作るのか、 あるいは複数のクラスの学習学習データが含まれても良いとするのかの選択. また、大きくなった木の剪定(pruning)をどこまで行うかの選択.
- 葉ノードに対する多数決によるクラスの割り当て. (#01)
決定木の方式
決定木の学習に関する代表的な方式には、CART (Classification And Regression Tree) と呼ばれるものと、
ID3 (Iterative Dichotomiser 3) やその後継の C4.5 と呼ばれるものがある.
以下からはCARTを前提に進める.
決定木に関する「定義」と「数式化」
CART の決定木は 2分木であり、 と はそれぞれ左側、右側の次のノード番号を与える関数である.
これらは次の2つの性質を満たす.
木自身を で表すことにする.
例えば、ノード が、ノード の祖先であれば、ノード からノード への 一意のパスがあって、
のようなノード達がリンクでつながり、
の関係が成り立っている.
決定木では、各領域 に特定のクラスを割り当てて、入力データのクラス分類を行う.
ノードにおける確率
クラスを としたとき、あるノード が表すクラス の事前確率を以下のように計算する.
クラスラベル付きの学習データ集合を とする.
特徴量空間は決定木のノードを経るごとに分割されていく.
あるノード の領域に属する学習データ数をとする.
個のデータのうち、 番目のクラスに属するデータを で表す.
最終的な数式の意味としては、
となり、そりゃそうかという感じに落ち着く.
入力データが決定木の規則によってある葉ノードに当てはまったとき、「どのクラスとして分類される確率」はここでいう事後確率を示す.
この確率を関数と考え、以下のような形式の関数と考えることができる.
そのとき、決定木の事後確率は適応基底関数モデルとして考えることができる.
- 適応基底関数モデル
ノード においてクラス識別 / 分類を行う場合、事後確率が最大となるクラスを選ぶ.
ノード で学習データはさらに分割され、子ノード と が生成される.
緒定義完了.
参考
書籍
はじめてのパターン認識
- 11 識別器の組み合わせによる性能強化
- 11.2 決定木
- 11.2.1 決定木に関する緒定義
- 11.2 決定木
-
- 11 識別器の組み合わせによる性能強化
Machine Learning A Probabilistic Perspective
- 16 Adaptive basis function models
- 16.2 Classification and regression trees (CART)
- 16 Adaptive basis function models
Web サイト
- 今更感あるけど決定木について調べたのでまとめる
- www.st-hakky-blog.com
- ID3 (Iterative Dichotomiser 3)