【Python】決定木分類器を書いてみる【Iris】

| 1件のコメント

Python機械学習プログラミング 達人データサイエンティストによる理論と実践 第3章 分類問題 の 3.6 決定木学習に関連した内容です。

決定木をサポートしたライブラリは R だと {rpart}, Pythonだと scikit-learn を初めとして数多くあります。当初は Go で書いてみようと思ったのだけど, その前にまず Python で書いてみようということで始めたら意外と時間を使ってしまったので Go は次回に回したいと思います…

なので今回の内容は, scikit-learn の DecisionTreeClassifier の Iris データに対しての分類器と同様の分類器を得る Python コードを書いてみる所までになります。

決定木学習

決定木学習は意味解釈可能性 (Interpretability) に配慮されたモデルで, 機械学習アルゴリズムの中でも事前の標準化を必要としないアルゴリズム。情報利得が最大となる特徴量でデータを分割していくのを再帰的に行う。
特徴空間を矩形に分割するため複雑な決定境界を構築できる反面, 木が深くなるほど決定境界は複雑となり過学習に陥り易い。そのため, 木の深さを制限する剪定 (prune) を行い過学習を抑制する。また, 単一の決定木と比べるとランダムフォレスト (RF) は汎化性能に優れる。

目的関数

最も情報利得の高い特徴量でノードを分割するための目的関数を定義する。二分決定木の場合は以下となる。

     \begin{eqnarray*}   IG ( D_{p}, f ) = I(D_{p}) - \frac {N_{left}} {N_{p}} I(D_{left}) - \frac {N_{right}} {N_{p}} I(D_{right}) \end{eqnarray*}

f は特徴量, Dpは親データセット, Dleft, Drightは子ノード。Iは不純度で, ノードに含まれるサンプルの異なったクラスの割合の程度。

分割条件

二分決定木でよく使われる分割条件は以下である。

  • エントロピー (entropy)
  • ジニ不純度 (gini impurity)
  • 分類誤差 (classification error)

エントロピー

ノードのサンプルが全て同じクラスiに属している場合は, エントロピーは 0 となる。c は取り得るクラス数。
逆に各クラスが一様に分布している場合は最大になる。エントロピーは相互情報量が最大化するように試みる条件である。

     \begin{eqnarray*}   I_{H} (t) = - \sum_{i=1}^{c} p (i|p) \log_{2} p (i|p) \end{eqnarray*}

適当に書いたPythonコード。

def _entropy(self, target, n_classes, n_samples):
    entropy = 0.0

    for c in n_classes:
        p = float(len(target[target==c])) / n_samples
        if p > 0.0:
            entropy -= p * np.log2(p)
    return entropy

ジニ不純度

エントロピーと同様に誤分類を最小化する条件である。エントロピーと似ている結果になる。

     \begin{eqnarray*}   I_{G} (t) = 1 - \sum_{i=1}^{c} p (i|p)^2 \end{eqnarray*}

def _gini(self, target, n_classes, n_samples):
    gini_index = 1.0
    gini_index -= sum([(len(target[target==c]) / n_samples) ** 2.0 for c in n_classes])
    return gini_index

分類誤差

ノードのクラス確率の変化にあまり敏感でないため, 決定木を成長させるのに適していない。

     \begin{eqnarray*}   I_{E} (t) = 1 - \max \{ p (i|t) \} \end{eqnarray*}

def _error(self, target, n_classes, n_samples):
    return 1.0 - max([len(target[target==c]) / n_samples for c in n_classes])

また, 回帰問題に対しては MSE (Mean Squared Error) などが使われる。

scikit-learn

本書でも登場する scikit-learn の DecisionTreeClassifier クラスによる Iris に対する多クラス分類と, 木の可視化の例。

#!/bin/python
# -*- coding: utf-8 -*-

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
from sklearn.externals.six import StringIO
from sklearn.tree import export_graphviz

def save_tree(tree):
    dot_data = StringIO()
    export_graphviz(tree, out_file='tree.dot',
        feature_names=["Sepal.Length", "Sepal.Width", "Petal.Length", "Petal.Width"])

if __name__ == "__main__":
    iris = load_iris()

    dt = DecisionTreeClassifier(max_depth=3)
    dt = dt.fit(iris.data, iris.target)

    save_tree(dt)

dotファイルをpngに変換する。

$ dot -Tpng tree.dot -o img/tree.png

scikit-learn-tree

得られた決定木と同様の決定木分類器を得るためのコードを書いてみる。

決定木分類器のPythonオレオレ実装

Code は GitHub に置いた。

Treeクラスの build() で情報利得を最大化するような分割閾値を探索し, 分割できなくなるまで再帰的に分割する。
分割条件は先ほど挙げた, エントロピー, ジニ不純度, 分類誤差の3種類。prune() で max_depth 以上の枝を剪定する。

#!/bin/python
# -*- coding: utf-8 -*-

import sys
import os
sys.path.append(os.path.join('./decision-tree/'))

import decision_tree as dt
from sklearn.datasets import load_iris

if __name__ == '__main__':
    d = load_iris()

    tree = dt.DecisionTreeClassifier(criterion='entropy', prune='depth', max_depth=3)
    tree.fit(d.data[0:150], d.target[0:150])
    tree.show_tree()

    pred = tree.predict(d.data[100:101])
    print(pred, d.target[100:101])

show_tree() で if/then/else ルールを出力する。scikit-learn と同じルールの決定木となった。

$ python classifier-example.py
 if X[2] <= 2.45
    then {value: 0, samples: 50}
    else if X[3] <= 1.75
        then if X[2] <= 4.95
            then {value: 1, samples: 48}
            else {value: 2, samples: 6}
        else if X[2] <= 4.85
            then {value: 2, samples: 3}
            else {value: 2, samples: 43}

Goの勉強のために移植してみたい。

[1] Information Gain
[2] 1.10. Decision Trees
[3] マーケターのためのデータマイニング・ヒッチハイクガイド 第14回:決定木(1)

1件のコメント

  1. ピンバック: 【Python】回帰木を書いてみる【決定木】 | FiS Project

コメントを残す

必須欄は * がついています