決定木とは

目的変数と説明変数のデータセットから、木構造の分類器を生成して入力データを分類していく手法です。

と言ってもわからなかったので、まずは用語の説明から

目的変数 : 分類先の変数 (メールならスパムか否か, 0 or 1) みたいな
説明変数 : データの特徴を表している変数 ( 宛先? 本文? よくわかりません )

だいたい、上記はベクトルになってることが多いと思います。 (機械学習全般そうですが)

決定木をもう少し噛み砕いて

要は if - else を大量に作る。ってことです。

もう少し流れを細かく書きます。

データをある説明変数で2つに分けてみる
分け方が正しいかどうかわからないので、ある関数を使って評価してみる
一番正しそうな分け方で分ける
分けたもの(2つ)に関して上記2つを繰り返し行う
... (分割できなくなるまで続ける)

以上です。

分け方　/ 評価関数

ここが今回の肝、だと思っています。

分け方

データを分ける方法について述べていきます。
以下のデータはsklearnのirisデータを元に作っています。

from sklearn import datasets
iris = datasets.load_iris() # irisデータ読み込み
iris.data # 説明変数
iris.target # 目的変数

以下のようなデータセットを考えてみます。
5次元目が目的変数(0, 1, 2:花の種類)を表していて、それ以外が説明変数(花弁の長さ等)を表しています。

[
[5.1, 3.5, 1.4, 0.2, 0], 
[4.9, 3.0, 1.4, 0.2, 1], 
[4.7, 3.2, 1.3, 0.2, 0]
...
]

さて、このデータを分割するときにすることは以下の通りです。

分割する説明変数を決める
- 1 ~ 4次元まで順番でいいです。
分割する説明変数を小さい(?)順に並べる ( = Aとする)
Aのそれぞれの間をとり、分類して評価してみる
- (A[0] + A[1]) / 2 で分けてみる
分割後、評価関数のもと数値化して保存しておく
- この後説明します
最後まで分割が終わったら、一番分離できていたもの(評価関数)で分離する

評価関数

決定木の評価にはいくつか使われる手法があるらしいですが、今回は「ジニ不純度」というのを使っていきます。

不純度??

「不純度」という言葉が始めて出てきましたが、簡単です。
説明変数の間をとり分割してみたのはいいものの、これは分割方法として正しいのかどうか？という疑問が残るかと思います。それを数値化してくれたものがジニ不純度です。

ちなみに、「Gini係数」という言葉が他のサイトでは使われていましたがそこでは微分がどうとかとか出てくるので検索の際は気をつけて下さい (人口と所得のローレンツ曲線のグラフが出てきます. ※あまり知識ないので、そこらへん詳しいかた教えてください..)

Gini不純度については、参考にも載せてありますが以下のサイトがわかりやすかったです。全編/後編に分かれています。

統計ハニージニ係数って・・・？（前編）

このジニ不純度というものを、集合Aを分割した集合L, R に対して計算して、平均値をとりジニ不純度:G(x)が

G(A) > G(L)とG(R)の平均値

となればうまく分割できたことになります。

ソースコード

まだ粗がありますが、一応ソースコード載せておきます。なにかあれば是非コメントしてください！！

# -*- coding: utf-8 -*-

from collections import defaultdict

class Sample:

    def __init__(self, label=0, features=[]):
        self.label    = label
        self.features = features

# ----------------------------------------------------------------------------

class Node:

    def __init__(self, level=0):
        self.level       = level # 階層の深さ
        self.l_node      = None  # 子ノード(左)
        self.r_node      = None  # 子ノード(右)
        self.t_value     = None  # 閾値
        self.feature_idx = None  # どの値で分けるか
        self.label       = None  # 分類すべきラベル
        self.samples     = []    # 属するサンプル


    def __str__(self):
        if self.is_leaf():
            return "[%3s] Samples:%3s" % (self.level, len(self.samples))
        else:
            return "[%3s] Feature Idx:%3s, Threashold: %5s" % (self.level, self.feature_idx, self.t_value)


    def is_leaf(self):
        return (self.l_node is None) and (self.r_node is None)


    def child_nodes(self):
        return filter(None, [self.l_node, self.r_node])


    def classify(self, feature):
        node  = self
        label = None

        f = feature[node.feature_idx]
        while node:
            if node.is_leaf():
                label = node.label
                break
            elif f < node.t_value:
                node = node.l_node
            else:
                node = node.r_node

        return label


    def build_child_nodes(self, n_class, samples, max_depth, min_samples):
        self.samples = samples
        n_features   = len(samples[0].features) # 説明変数の数

        # 最大の深さに達したら終わり
        if self.level >= max_depth:
            self.build_leaf()
            return

        # 分類した結果で最もいいもの
        best_feature_idx = None # 最もよく分類できた説明変数
        best_t_value     = None # 最もよく分類できた閾値
        best_gini        = 1    # 0に近づくほど平等
        best_l_samples   = []
        best_r_samples   = []

        # 説明変数の数だけ 分類して評価をする
        # 各説明変数で分類する(idx = 説明変数のindex)
        for idx in range(0, n_features-1):

            # 分類する説明変数を、ユニークにして昇順に並び替える
            features = map(lambda x: x.features[idx] , samples)
            features = list(set(features))
            features.sort()

            for i in range(0, len(features)-2):

                # 各説明変数の中間値で分類する.
                t_value = (features[i] + features[i+1]) / 2

                l_samples = []; l_sample_labels = defaultdict(lambda: 0)
                r_samples = []; r_sample_labels = defaultdict(lambda: 0)
                for s in samples:

                    if s.features[idx] < t_value:
                        l_samples.append(s)
                        l_sample_labels[s.label] += 1
                    else:
                        r_samples.append(s)
                        r_sample_labels[s.label] += 1

                # どちらかに偏ったらわける意味なし, 次の説明変数の計算
                if len(l_samples) == 0 or len(r_samples) == 0:
                    continue

                # 分割したものに対しての評価(Gini係数, 交差エントロピー)
                l_gini = 0; r_gini = 0
                for idx in range(0, n_class):
                    l_gini += (float(l_sample_labels[idx]) / len(l_samples)) ** 2
                    r_gini += (float(r_sample_labels[idx]) / len(r_samples)) ** 2

                # 全体のGini係数(l, rのgini係数の平均値を求める)
                gini = (((1-l_gini) * len(l_samples)) + ((1-r_gini) * len(r_samples))) / len(samples)

                # bestを上回っていたら更新する
                if gini < best_gini:
                    best_gini        = gini
                    best_t_value     = t_value
                    best_feature_idx = idx
                    best_l_samples   = l_samples
                    best_r_samples   = r_samples

        # どちらかに偏ったら新たに木を作らない
        if len(best_l_samples) == 0 or len(best_r_samples) == 0:
            self.build_leaf()
            return

        # min_samples に達してない場合もわける必要なし. 過学習対策
        if max(len(best_l_samples), len(best_r_samples)) < min_samples:
            self.build_leaf()
            return

        # 現在のノードの設定
        self.samples     = []
        self.t_value     = best_t_value
        self.feature_idx = best_feature_idx

        # ベストなものから新規ノード作成, 次のノードへ移る
        next_level = self.level + 1

        self.r_node = Node(next_level)
        self.r_node.build_child_nodes(n_class, best_r_samples, max_depth, min_samples)

        self.l_node = Node(next_level)
        self.l_node.build_child_nodes(n_class, best_l_samples, max_depth, min_samples)


    def build_leaf(self):
        self.label = self.samples[0].label

# ----------------------------------------------------------------------------

class DecisionTree:

    def __init__(self, max_depth=10, min_samples=3):
        self.root_node   = Node(level=1) # root node
        self.max_depth   = max_depth     # Treeの最大の深さ
        self.min_samples = min_samples   # Nodeに属する最小の要素数


    def fit(self, data, target):
        # ユニークな分類クラス数
        labels = list(set(target))

        # 学習用データ生成
        samples = []
        for idx, sample in enumerate(data):
            samples.append(Sample(features=data[idx], label=target[idx]))

        # 学習
        self.root_node.build_child_nodes(n_class=len(labels), samples=samples, max_depth=self.max_depth, min_samples=self.min_samples)


    def features(self):
        # レベル毎にNodeの特徴を出力する
        print self.root_node

        current_nodes = self.root_node.child_nodes()
        child_nodes   = []
        while current_nodes:
            node = current_nodes.pop(0)
            print node
            child_nodes.extend(node.child_nodes())

            if len(current_nodes) == 0 and len(child_nodes) > 0:
                current_nodes = child_nodes
                child_nodes   = []


    def predict(self, data):
        return self.root_node.classify(data)

参考

以下のページ、大変参考にさせていただきました。