CART

classification and regression tree (CART) †

Leo Breiman が考案した代表的な決定木アルゴリズム．

ID3と同様に分割統治アルゴリズムで，各ノードで分割する属性を木全体の Gini index の減少を最大にするという規準で選ぶ．

目的変数がカテゴリ変数のときは決定木が，目的変数が連続数値変数なら回帰木が得られる．

Gini係数 †

クラス \(c\in C\) のサンプルの，全サンプルに対する割合を \(p_c\) で表すと Gini係数 (Gini index) は \[ \mathrm{Gini}\mathrm{\ index} = 1 - \sum_{c\in C} p_c^2 \]

各葉ノードについてGini係数を求め，それを，その葉ノードに分類されるサンプルの割合で重み付けする．この重み付けしたGini係数を全てのはノードについてとった総和を，決定木全体のGini係数とする．

Gini係数は，入力データがどれだけ一様に分布しているか測る目的で考案された．オリジナルはこのような離散値ではなく，連続値について定義され，国民の収入の偏りを測るのに用いられた．

-- しましま

関連項目 †

• classification and regression tree
   
• Gini index
• Gini係数
   
• 決定木
• 回帰木
• ID3
• C4.5
• 分割統治アルゴリズム
   
• 検索:CART

リンク集 †

• RjpWiki:rpart(再帰的分割(Recursive Partitioning))パッケージ中のオブジェクト一覧 RのCARTアルゴリズム用パッケージ
• Rのセットアップ＋CART
   
• Wikipedia:Gini_coefficient

関連文献 †

• 基本文献
  L.Breiman, J.H.Friedman, R.A.Olshen and C.J.Stone, "Classification and Regression Trees", Wadsworth (1984)
  GoogleScholarAll:Classification and Regression Trees
• Book/データマイニングの基礎 2.1節