St_Hakky’s blog

Data Science / Human Resources / Web Applicationについて書きます

今更感あるけど決定木について調べたのでまとめる

AI Data Science Machine Learning

こんにちは。

本当にクソいまさらなんですけど、アンサンブル手法とか勉強していたら復習したくなってきたので、ここで復習もかねてまとめておきます。

決定木とは

決定木の概観

決定木はおそらく機械学習とかをやったことがある人なら確実に一回は見たり使ったり聞いたりしたものではないかと思います。決定木は、ツリー構造の形で分類または回帰のモデルを構築するものです。決定木では、そのアルゴリズムによっては、カテゴリと数値の両方のデータを扱うことができます。

https://upload.wikimedia.org/wikipedia/commons/f/f3/CART_tree_titanic_survivors.png
参考：Decision tree learning - Wikipedia

決定木の目的は、変数とその値の組によって表現されたデータをいくつかのサブセットに分割していくことにあります。そして分割していく過程で、より木の深さを深くせず、且つ汎化性能の高い出力を返せるような木を構築していくことがゴールになります。

決定木はその名の通り"木"なので、木によって以下のように分割を表現します。

  • 非終端ノード：属性のラベルが付けられる
  • 枝：非終端ノードから出ている枝には、その属性の取りうる値が示されている
  • 葉：最終的な分類結果の値

決定木のメリット・デメリット

結果の可読性という観点でこの手法の右に出るものはないんじゃないかというくらい、わかりやすいです。

そもそも、木で表現してくれて、分割の基準がどうなっているかや、分割の基準となるものが上から順番に優先度が付いているのでこれもまたわかりやすいです。

また、あたいのスケールにそれほど依存をしないという点も決定木を作るときのメリットと言えます。

ただ、学習データへの依存が激しく、並列化などもできないというデメリットもあります。

参考

基本となるアルゴリズム

あとで紹介するように、決定木には色々種類があるわけなんですが、最も基本となるアルゴリズムであるID3 (Iterative Dichotomiser 3)についてここでは紹介します。

ここで紹介するアルゴリズムはこちらでも簡潔にわかりやすく書かれています。

ID3は、1986 年に、Ross Quinlan によって開発されました。逆戻りをしないという制約の中で実現可能なブランチ空間を、 あるステップにおいて局所的に評価の高いパターンを選択する、トップダウンの貪欲な探索をします。

探索を行っていく過程で、どの変数のどんな値を使って分割していくかが重要になってくるわけで、すなわち識別能力が大事になってきます。

それではどうやって識別能力を定義するかが大事なのだが、ID3はEntropyとInformation Gainを使用して決定木を構築していきます。

エントロピー

情報の乱雑さを表す指標としてエントロピーというものがあります。エントロピーは以下の式で定義されます。

$$
I(p_1, ..., p_n) = \sum_{i=1}^{n} P_i \log_2 \frac{1}{P_i}
$$

ちなみに底数は2でなくても良くて、分類するクラスの数と等しくすると値の最大値が1になって便利。どのような値の時にこのエントロピーが高くなるのかをみるために、この式をコイン投げの例に従って可視化させます。

# coding: utf-8
import numpy as np
import matplotlib.pyplot as plt

# 表の出る確率
P1 = np.linspace(0, 1, 1000)

# 裏の出る確率
P2 = 1 - P1

# エントロピー
I = lambda p1, p2: -p1 * np.log2(p1) - p2 * np.log2(p2)

# エントロピーの値の計算
result = np.array([I(p1, p2) for p1, p2 in zip(list(P1), list(P2))])
result[np.isnan(result)] = 0

# 可視化
plt.scatter(P1, result)
plt.show()

上を実行させたのが以下の図。

f:id:St_Hakky:20170810171002p:plain

この図から、エントロピーの値が大きくなるのは、表か裏、どちらがでるかわからない時ということがわかります。すなわち、情報がよりランダムに近いほど、値が大きくなり、逆に情報がよりランダムで無く偏っている時、値が小さくなります。極端な話、ノードのサンプルが全て同じクラスに属している場合は、エントロピーは0となります。

これを使って決定木の各ノードにおいて識別力を求め、どのような識別を行うかを決めるわけなのですが、それは情報量ゲインで話します。

情報量ゲイン

決定木の構造を決定していく過程では、葉ノードにて分類結果を返すことが目標なので、出来る限り葉ノードでは結果が偏っていてほしいとなります。

つまり、エントロピーが根ノードから葉ノードに行くに連れて徐々に下がっていってほしいわけです。この時、あるノードからあるノードに分割した時にそれらのエントロピーの差を情報量ゲインといい、この情報量ゲインの値が大きければ大きいほどより良い分割ができているということになります。

情報量ゲインの式は以下のアルゴリズムで参照します。ID3のアルゴリズムでは、この情報量ゲインが最大になる分割のための変数とその値を貪欲に探していきます。

ID3のアルゴリズム

アルゴリズムについては、こちらの方の記事をベースにさせていただきました(ありがとうございます)。

1. ルートノード $N$ を作成して全ての訓練データ集合を $N$ に所属させる。

2. もし $N$ に所属するクラスが全て同じ決定 $X$ を与えるなら $N$ に $X$ とラベル付けして処理を終了する。

3. 訓練データ集合 $C$ に対するエントロピーを求める、即ち以下の式を計算する。

$$
M(C)=- \sum_{x \subset D} p_x(C) \log p_x(C)
$$

4. $C$ を変数 $a_i$ の値に応じて分割する。$a_i$ が $v_1 … v_n$ の $n$ 通りの値を持つ場合は以下の通りに分割する。

$$
C_{ij} \subset C (a_i = v_j)
$$

5. 分割した $C_{ij}$ に応じて平均情報量を求める。

$$
M(C)=-\sum_{x \subset D} p_x(C_{ij}) log p_x(C_{ij})
$$

6. 計算した平均情報量から独立変数 $a_i$ の平均情報量の期待値 $M_i$ を以下の式で求める。

$$
M_i= M(C) - \sum_{j = 1}^n M(C_{ij}) \times \frac{\mid C_{ij} \mid }{ \mid C\mid}
$$

※上の式が情報量ゲインの式になります。この式を見ると、親ノードから子ノードに写った時のエントロピーの差の期待値という、情報量ゲインのが式から読み取れると思います。

7. $M_i$ が最大となる独立変数を $a_k$ とする。

8. $N$ のラベルを $a_k$ として、$N$ の子ノード $N_j$ を作成し、それぞれに$C_{kj}$ を所属させる。

9. それぞれの子ノードに対して $N = N_j$, $C = C_{kj}$ として、2 以下の操作を再帰的に行う。

これが、決定木の基本となるアルゴリズムです。このように何かしらの基準に従ってノードの変数とその分割基準を選んでいき、決定木を構築していきます。

参考

決定木のアルゴリズムの種類

決定木のアルゴリズムの概観

決定木のアルゴリズムにはいくつか種類があるのですが、そのアルゴリズムの種類と違いを簡単に表でまとめておきたいと思います。

ID3 C4.5(C5.0) CART CHAID
目的変数の型 離散値 離散値 離散値,連続値 離散値,連続値
説明変数の型 離散値 離散値,連続値 離散値,連続値 離散値,連続値
分岐の数 多分岐可能 多分岐可能 ２分岐のみ 多分岐可能
評価基準 情報量ゲイン 情報量ゲイン Gini係数 カイ２乗値
欠損値への対応 不可 可 可 可
枝刈りするか しない する する する

大きく異なるのは、目的変数の型として使用可能なものと、ノードの分割条件を決定する際の評価基準というとこでしょうか。それぞれの手法のメリットやデメリットについては以下の各アルゴリズムで触れたいと思います。

参考

決定木アルゴリズムの選択方法

どの決定木のアルゴリズムを選ぶかは、以下の観点で選ぶと良さそうです。

  1. Will tree be binary or not?
  2. Which attribute will be node?
  3. How missing data will be handled?
  4. If tree becomes too large,how to prune it?

参考：What are the differences between ID3, C4.5 and CART? - Quora

上記の問いに、与えられたデータセットや課題を基にどのように答えたかで、アルゴリズムを選べばいいと思います。それぞれのアルゴリズムがどのような特徴をそなえているかどうかは以下で詳細に触れます。

ID3

アルゴリズム

上で説明したため、割愛。

メリット

上位互換がありすぎてここではあまりとりあげることがないかも…汗

デメリット
  • データ数が少ないとデータが過学習しやすい
  • 分岐を決定する時に一つの変数しか考慮することができない
  • 連続値を取り扱うことができず、また欠損値に弱い
参考文献

C4.5(C5.0)

C4.5 は、ID3 を基に改良されたもので、数値データの特徴量を動的に離散化するロジックを導入し、全ての特徴量がカテゴリカル変数でなればならないという制約を取り除きました。C4.5 は学習済みの木を if-then で表されるセットに変換し、評価や枝刈り (決定木における不要な部分(枝)を取り除くこと) に用いられます。

アルゴリズム：C4.5とC5.0の違い

まず、このアルゴリズムがあると知った時に、最初に気になったのはこの２つがよく並列でとりあげられていることです。なので、この２つに果たして違いはあるのだろうかというのがふつうに疑問として上がります。

もともと、C4.5はID3の改良版で、C4.5は1997年に商用のC5.0に改善され、以下のような変更点がありました。

  • ブースティングを組み込むことで精度が格段に上がった
  • スケーラビリティが向上しているのでマルチコアCPUで有用

詳細はこちらの記事でみることができますが、実行時間が格段に早くなり、しかもメモリ消費量も抑えられ、精度も向上していることがわかります。

メリット
  • ID3と違い、連続値・離散値の両方を扱うことができ、また欠損値にも対応することができる
  • 過学習の問題を枝刈りで防ぐことができる
  • CARTは木の剪定をクロスバリデーションによって行うため時間がかかるがC4.5は二項信頼限界を使うため一方行でできる
デメリット
  • ゼロの値を持つ空のブランチを構築してしまう
  • 異常値を持つデータでモデルを構築すると、過学習が発生してしまう。これは特にデータにノイズが含まれていた際に、起こる。
参考文献

CART

CART (Classification and Regression Trees) は、C4.5 によく類似した手法ですが、数値データで表現される目的変数 (=回帰) にも対応している特徴があります。CART は、ルールセットを計算するのではなく、バイナリ・ツリーを構築します。なお、scikit-learn は最適化したバージョンの CART を実装しています。

アルゴリズム

CART は ID3 とほぼ同じアルゴリズムですが、指標として、Gini係数という不純度を表す指標を用いて分岐を行います。

$$
Gini Index(t) = 1 - \sum_{j=1}^{k} p^{2}(j | t)
$$

$p(j | t)$ は、ノード $t$ 内におけるクラス $j$ の割合です。この値が大きいほど、クラス内の不純度が小さくなります。

つまり、不純度が最も低ければジニ係数の値は0，不純度が高くなればなるほどジニ係数の値が1に漸近することがわかります．

このGini係数を計算して、親ノードと子ノードの差が大きくなるようなものを分岐の条件として選ぶことで、決定木を構築します。

メリット

[工事中]

デメリット
  • 一つの変数でしか分岐条件を作成できない
  • 構築された木が不安定
参考文献

Boosting algorithm: GBM – Towards Data Science

CHAID

[工事中]

決定木の可視化

先日、こんな記事を見つけて、取ってもびっくりしました。

sckit-learnとかを使っての可視化って結構微妙だなぁって思っていたんですが、ここまでわかりやすくいい感じで表現してくれるのは、とっても驚きでした。以下の記事でまとめてみました。

st-hakky.hatenablog.com

その他の参考文献

書きかけ感、、笑。また更新します。