【本記事の内容】決定木を初学者向けに簡単解説
今回は機械学習でよく用いられる決定木について解説します。
目次
決定木とは？
https://assign-navi.jp/magazine/consultant/c41.html から引用
決定木分析とは、分類・回帰問題でよく使われる手法の1つで、木構造を用いて「条件分岐」を繰り返すことでサンプルを分類する機械学習の手法。（決定木は決定木分析の分析結果の出力の木のことを指す。）
その際には、サンプルのグループがなるべく同じ属性になるように分割する。
例
「温度と湿度がどのようなときに暑いと感じるのか」を表現したツリー
決定木の特徴（長所・短所）
長所
・可読性が高い
→「どのようにして分類結果が得られたか」が木やグラフからわかりやすい。
・扱える変数の尺度が多い
→説明変数・目的変数が質的データでも量的データでも扱える。
・外れ値に対して頑健
→外れ値があってもモデルが大きく影響を受けない。
・変数の標準化が不必要
→標準化してもしなくても、サンプル間の特徴量の大小同じであるため、得られる分類結果は同じ。（ただし、他の手法と比べるときにグラフのスケーリングを揃える必要がある場合は標準化する）
短所
・分類性能が高い手法ではない
→決定木単体では精度が低いが、複数の決定木をアンサンブル学習させることで精度が高くなる。
・過学習を起こしやすい
→木のサイズ（深さ）を大きくしすぎると過学習を起こす。
対策として、「木のサイズ（分割回数）の調整」や「木の剪定・枝刈り」が挙げられる。以下が詳しい。
・線形性のあるデータには適してない
その他の特徴
・ノンパラメトリックな教師あり学習の手法
→ノンパラメトリックとは、「サンプルの母集団の分布を仮定しないこと」を指す。教師あり学習は「ラベル付き（正解付き）データを学習する手法であること」を指す。
・「決定木」はアルゴリズムの名前ではない
→決定木は分析結果として得られる木構造の出力のことを指す。決定木を用いた代表的なアルゴリズムには「CART」や「C4.5」などがある。
CART
「CART」とは、決定木を使ったアルゴリズムの1つ。「ジニ不純度」「利得」と呼ばれる指標をもとに決定木を構成していく。
CARTの特徴
・二分木のみの分類
・ジニ不純度をもとに分割を行う
・分類・回帰で使用可
ジニ不純度
ジニ不純度とは、あるグループ（分割結果）に対する指標で、様々なクラスが混在する場合は値が大きくなり、ある1つのクラスが多く占めるほど値が小さくなるという指標である。
→ 各ノードの不純度の定義
（例）
男子10人と女子10人を
・今朝の朝食が 「パン」 or 「ごはん」で分ける
「パン」派 : 男子5人, 女子7人 ← ジニ不純度は大きい
・身長が「低い」 or 「高い」で分ける
「低い」グループ : 男子1人,女子9人 ←ジニ不純度は小さい
・ジニ不純度 :
$$ I_G(t) = 1 ~- \sum_{i=1}^{K}\{ p(c_i|t)\}^2 $$
$$ p(c_i|t) = \frac{n_i}{N} $$
ただし、
- \( I_G(t) \) : ジニ不純度
- \( K \) : 目的変数のクラス数
- \( t \) : 現在のノード
- \( n_i \) : クラスCiに属するトレーニングデータ数
- \( N \) : 全トレーニングサンプル数
- \( C_i \) : i番目のクラス
※ここらへんの議論は数式だけでは理解できないと思うので、以下の例題で具体的な数値を使って理解していくとよいと思います。
利得(Gain）
利得とは、「分岐前のジニ不純度」と「分岐後のジニ不純度」の差(のようなもの)で定義される。すなわち、利得は「分割による不純度の減少分(のようなもの)」を表す。
→その分割により「サンプルをどれだけうまく分割できたか」の定義
・利得 :
$$ \Delta I_G(t) = I_G(t_B) ~- (w_L I_G(t_L) + w_R I_G(t_R)) $$
ただし、
- \( \Delta I_G(t) \) : 利得
- \( t_B \) : 分岐前のノード
- \( t_L,t_R \) : 分岐後の左ノード , 右ノード
- \( w_L,w_R\) : 分岐後の左ノードの重み , 右ノードの重み
閾値（しきい値）の決め方
・説明変数が質的変数の場合は「各値で場合分け」
（例）
「天気」という変数なら「晴れ」「曇り」「雨」で場合分け
・説明変数が量的変数の場合は「中央値で場合分け」
（例）
「小テストの点数(10点満点)」という変数で、サンプルの10人が「3,4,5,5,6 ,7,7,8,9,10」という結果なら「7点以上」「7点未満」で場合分け
CARTのアルゴリズム
CARTでは「利得の最も大きい分岐を繰り返し求めること」で木を作成していく。アルゴリズムを大まかに示すと以下のようになる。
- 各説明変数で分岐を作成
- 各分岐で利得を計算
- 利得が最も大きい分岐を採用
- 1に戻る
例題(CART)
【問題】
以下の分割ルール1および分割ルール2における左右のノードのジニ不純度と利得をそれぞれ計算せよ。
【設定】
複数の天候条件で「外出する」か「外出しない」かのアンケートをとったところ、アンケートの回答状況は以下のようになった。
- 「外出する」: 100人
- 「外出しない」 : 200人
【解答】
・分割前の不純度
$$ I_{G}(t_B) = 1 ~- \{ (\frac{100}{300})^2 + (\frac{200}{300})^2 \} = 0.44$$
・分割ルール１の’yes’グループのジニ不純度
$$ I_{G1y}(t_L) = 1 ~- \{ (\frac{10}{190})^2 + (\frac{180}{190})^2 \} = 0.10$$
・分割ルール1の’no’グループのジニ不純度
$$ I_{G1n}(t_L) = 1 ~-\{ (\frac{90}{110})^2 + (\frac{20}{110})^2 \} = 0.30 $$
・分割ルール1の利得
$$ \Delta I_{G1}(t) = 0.44 – ((\frac{190}{300})×0.10 +(\frac{110}{300})×0.30 )= 0.27 $$
・分割ルール2の’yes’グループのジニ不純度
$$ I_{G2y}(t_L) = 1 ~- \{ (\frac{50}{170})^2 + (\frac{120}{170})^2 \} = 0.42 $$
・分割ルール2の’no’グループのジニ不純度
$$ I_{G2n}(t_L) = 1 ~- \{ (\frac{50}{130})^2 + (\frac{80}{130})^2 \} = 0.47 $$
・分割ルール2の利得
$$ I_{G2}(t) = 0.44 -((\frac{170}{300})×0.42+(\frac{130}{300})×0.47 )= -0.002$$
→利得が大きい「分割ルール1」を採用して木を構成していく
参考文献
次回予告
特に決めていません。
「とりあえず1か月ブログをやってみる」ということを目標にやってきたので、ひとまず今回で一段落ということにしたいと思います。
これから卒論とかあるのでそっちを頑張りつつ気が向けばって感じで書いていければいいかなと思っています。
コメント