本日のまとめ

決定木学習

参考

決定木の学習方法

  • 情報利得が最大となる特徴量でデータを分割する
  • 情報利得の考え方には、情報エントロピーを考える方法（C4.5)と、ジニ不純度、分類誤差を考える方法がある
  • どちらの方法でも、分割前後の不純度の差分が大きければ大きいほど、情報利得が大きいと考えることができる. 情報利得は次のように定義される

 IG(D_p , f) = I (D_p) - \sum_{j=1}^{m} \frac{N_j}{N_p} I(D_j) \\

IG : 情報利得 \\
D_p : 親ノードデータセット（分割前）\\
D_j : 子ノードデータセット（分割後）\\
I: 不純度の数値化（ジニ不純度 or エントロピー) \\
N_p : 親ノードサンプルの総数 \\
N_j : j番目の子ノードのサンプル総数
  • 二分決定木の場合は、以下のようになる

IG(D_p , f) = I(D_p) - \frac{N_{left}}{N_p} I(D_{left}) - \frac{N_{right}}{N_p} I(D_{right})



I_H(t) = - \sum_{i=1}^c p(i|t) log_2 p(i|t) \\

p(i|t) : 特定のノードtにおいて、クラスiに属するサンプルの割合
  • 上記の定義から、ノードのサンプルがすべて同じクラスの場合p(i|t) = 1で、は log1 = 0となるので、エントロピーは0となる。エントロピーが最大となるのは、サンプルが一様に分布している場合。
  • ジニ不純度の定義は以下の通り

I_G(t) = - \sum_{i=1}^c p(i|t) (1 - p(i|t)) = 1 - \sum_{i=1}^c p(i|t)^2 \\
p(i|t) : 特定のノードtにおいて、クラスiに属するサンプルの割合
  • 2値分類の場合、

I_G(t) = 1 - \sum_{i=1}^2 0.5^2  = 0.5
  • 分類誤差の定義は以下の通り

I_E(t) = 1 - max\{p(|t)\}
  • 分類誤差は、クラス確率の変化に敏感ではないため、決定木の成長には向いていない

ランダムフォレストについて

  • ランダムフォレストは、決定木の「アンサンブル」
  • 決定木は、根を深くすると、過学習（バリアンスが高い状態）を起こしがち
  • バリアンスが高い複数の（深い）決定木を平均化することで、より汎化性能が高い頑健なモデルを構築する

  • 手順は以下の通り

  • トレーニングデータからnこのサンプルをランダムに選択する

  • 標本から決定木を成長させる。

    • 特徴量を重複なしで抽出する
    • 特徴量を使って、ノードを分割する

  • 上記をk回繰り返し、「多数決」に基づいてクラスラベルを割り当てる。

  • ハイパーパラメータの調整に悩む必要がないという利点がある。

  • サンプルのサイズを小さくすると、「ランダム性」が向上し、過学習を抑える効果が期待できる
  • 特徴量の数は、ルートをとることがおおい。

k近傍法 ( K-nearest neighbor classifier)

  • kの値と、距離指標を選択する
  • 分類したいサンプルから、k子の最近傍のデータ点を見つけ出す
  • 多数決によりクラスラベルを割り当てる
  • 距離指標は、データセットの特徴量に適した指標を選択することが需要！