tsux.me 現役京大生エンジニア精進の日々

AIを作る #1 【決定木 CARTアルゴリズム】 【ゼロから実装・AI・機械学習】

単純明快でありながら、実際にかなり使われていたりもする決定木のアルゴリズムを簡単に説明し、実装していきます。
決定木とは何かを抑え、その中でも今回は CART アルゴリズムを紹介します。

「」内は覚えておきたい言葉です。

アルゴリズム解説

決定木(分類木)とは何か

「決定木(分類木ともいう)」は、データを分類するのによく使われるアルゴリズム(方法)です。
チャートに近いものだと思ってください。

見た目が木のようなので、そのまま「木」と呼ばれます。
実際に計算を行う、四角の部分を「ノード」、計算結果が下へと進む経路、線の部分を「エッジ」と呼びます。
上のように頂点のノードから下向きに進んでいくことで分類できます。

分類とは何か

さて、これを使ってデータを分類するとしましょう。
とは言っても実際には分類って何をするのでしょうか?
説明して行きたいと思います。

データは例えば、花についてのデータだとしましょう。

ここで、データの種類(花の『がくの長さ』や『花びらの大きさ』さなど)を「特徴量」と言います。
各種類のデータの組を「サンプル」と言います。

それでは、4種類の特徴量で、サンプル数は150組のデータから、
そのサンプルが『3種類のうちどの花か』予測することを考えます。
この3種類は「ラベル」などと言われます。

つまり、「特徴量」をみて「サンプル」に「ラベル」をつける。
これこそが機械学習に置ける「分類」です。

決定木による分類

さて、決定木を用いて綺麗に分類するためには、どう分ければいいののでしょうか?
以下の条件を満たすように分けるのがベストです。

  • 純度を高く分ける(なるべく分けた結果は一種類がいい)
  • なるべく均等に分ける(効率よく分類したい)

これを意識しながら決定木の代表的なアルゴリズムをみていきます。

  1. データを頂点のノードに渡す
  2. 計算して最適な方法で分ける
  3. 分けたデータをそれぞれ次のノードに渡す
  4. 計算して分ける
  5. 3 ~ 4 を繰り返す
  6. いい感じのところでやめる

1、2 も内容的には 3、4 と同じなのがわかります。
そう僕らがチャートをやるように進めていくだけなのです。
問題は「分け方」と「止め方」だけです。

分け方で決めないといけないのは、『どの特徴量をどの境界線で分けるか』です。
つまり最適な「特徴量」と「境界線」を計算によって決めるわけです。
次に各ノードでどのような計算をしているか詳しく見てみます。

  1. 各々の特徴量に対して、色々な値を境界線にして、一旦分けてみる
  2. その色々な分け方について、分けた後の「不純度」を求める
  3. そのうち一番「ゲイン」が高くなるものを選択する

ここで、出てきた「不純度」と「ゲイン」についても簡単に説明します。

不純度

まあ、簡単に説明すると「純度」の逆です。
金でも、なんでも、色々混じっているものは『純度が低い』ですよね?
それはつまり『不純度が高い』わけです。
ので、決定木では、『不純度が低く』、つまり『純度が高く』なるように分けるのです。

しかし、ここで厄介なことに、不純度にも色々あるんです。
単純に割合だけでも不純度は表せそうですが、
都合の良いものにするために、研究者が色々考えてきたわけですね。

ここでようやく今回の話題にもなる「 CART アルゴリズム」の話になります。
「 CART アルゴリズム」はこの「不純度」を考える上での指標として「 Gini 係数」というものを使います。

Gini 係数 (ちょっと数学します)

Gini 係数はあるサンプルの不純度を一番簡単に表したものだと言えます。

例えばあるノード t に渡された 30 個のサンプルのうち

  • 8 個がラベル A
  • 20 個がラベル B
  • 2 個がラベル C

だとするとそれらの確率は

  • $p(A|t)=\frac{n_A}{N}=\frac{8}{30}$
  • $p(B|t)=\frac{n_B}{N}=\frac{20}{30}$
  • $p(C|t)=\frac{n_C}{N}=\frac{2}{30}$

このまま足してしまうと合計が 1 なのは当たり前なので、2乗して和をとります。

$(\frac{8}{30})^2+(\frac{20}{30})^2+(\frac{2}{30})^2=\frac{64+400+4}{900}=\frac{468}{900}=0.52$

この値はそれぞれが均等に分散していると0に近づき、
逆に完全に分類されている(ラベルが1種類しかない)と、
当たり前ですが $\frac{30}{30}^2+\frac{0}{30}^2+\frac{0}{30}^2=1$ のように 1 になります。
つまり、『どれくらい純粋な結果か』を表しています。

そのためこの値をさらに 1 から引けば、『分けた結果がどれくらい純粋でないか』の度合いになります。
つまり「不純度」の指標として使えそうです。
1 から引くのは数学的に『最小化問題』のたぐいに持って行きたいからとか、
「不純度」という指標で用いやすくするためでしょう(だと思ってるんですけど、その辺の由来はよくわからないです)。

以上より、
ノード $t$ の不純度( Gini 係数)は、
サンプル総数を $N$ 、
ラベル $i$ のサンプル数を $n_i$ として、

$$
I(t) = 1 - \Sigma_{i}{(\frac{n_i}{N})^2}
$$

と表せます(I: Impurity 不純度)。

これを用いて次のゲインを考えます。

ゲイン

アルゴリズムには『「ゲイン」が一番高い分類の仕方を選択する』、とありました。

ゲインは「情報利得」とも呼ばれ、『その分類でどれほどの利益があったか』、を表します。

これは分類前と分類後の不純度を用いて求めます。

ノード p をノード l と r に分類した場合を考えます。

p のサンプル数 150 、
l のサンプル数 120 、
r のサンプル数 30 とします。

すると全体に対するノード l の重み(重要度)は単純に $w_l=\frac{120}{150}=0.8$
同様に全体に対するノード r の重み(重要度)は単純に $w_r=\frac{30}{150}=0.2$

もともとの不純度を $I_p$ として(p: parent)、
分類した結果の不純度が、 $I_l$ 、 $I_r$ になったとします(l: left, r: right)。

以上のようなとき、ゲインは、

$$
\Delta I = I_p - (w_lI_l + w_rI_r)
$$

つまり、うまく分ければ、 $()$ 内の部分の不純度が小さくなるので、ゲイン全体は増加します。

これが最も大きくなるような分け方で分類を進めていくわけです。

終了条件

どんな場合にノード上の計算をやめるかを考えます。

わけようがないものをそれ以上分類しようとしても意味がないので、
ラベルが 1 種類になってしまった場合( Gini が 0 )には計算を止めます。

また、あまりにも細かく分けてしまうと、
その学習したデータについてしか予測できない「過学習」の状態になってしまうので、
ノードの層の深さを決めてしまい、それ以上の深さになるようであれば計算をやめて、
それ以降の分類は諦めます(そもそも 100% の分類は普通できません)。

以上で決定木の CART アルゴリズムについてはだいたい説明が終わりました!
それでは Python で実装してみましょう!

実装

もう一度アルゴリズムを復習します。

  1. データを頂点のノードに渡す
  2. 計算して最適な方法で分ける
  3. 分けたデータをそれぞれ次のノードに渡す
  4. 計算して分ける
  5. 3 ~ 4 を繰り返す
  6. いい感じのところでやめる

計算(分類)の方法は以下の通りです。

  1. 各々の特徴量に対して、色々な値を境界線にして、一旦分けてみる
  2. その色々な分け方について、分けた後の「不純度」を求める
  3. そのうち一番「ゲイン」が高くなるものを選択する
# 不純度を計算します
def calc_impurity(data, labels):
    feature_num = data.shape[1]
    threshold = None
    feature = None
    impurity = 1
    for index in range(feature_num):
        for value in data[:, index]:
            sum_impurity = 0
            # ここではゲインを求める必要がないので不純度と重みの積の和まで求めます
            condition = data[:, index] >= value
            all_samples_num = len(labels)
            for column in [condition, np.logical_not(condition)]:
                I = 1
                partial_samples = labels[column]
                partial_samples_num = len(partial_samples)
                w = partial_samples_num/all_samples_num
                for _class in np.unique(partial_samples):
                    p = np.sum(partial_samples==_class)/partial_samples_num
                    I -= p**2
                sum_impurity += w*I
            # 最小の不純度となるものを記憶します
            if impurity > sum_impurity:
                impurity = sum_impurity
                threshold = value
                feature = index
    return impurity, threshold, feature

# 各ノードで計算は行われるのでノードをクラス化しました
class Node:

    def __init__(self, data, labels, max_depth):
        self.data = data
        self.labels = labels
        self.max_depth = max_depth
        self.children = []
        self.threshold = None
        self.feature = None
        self.depth = None
        self.impurity = None
        self.label = np.argmax(np.bincount(labels))

    # CART アルゴリズムの実行部分です
    def cart(self, depth=0):
        self.depth = depth
        self.impurity, self.threshold, self.feature = calc_impurity(self.data, self.labels)
        if self.impurity == 0 or self.depth == self.max_depth:
            return
        condition = self.data[:, self.feature] >= self.threshold
        for column in [condition, np.logical_not(condition)]:
            next_node = Node(self.data[column],  self.labels[column], self.max_depth)
            self.children.append(next_node)
            next_node.cart(self.depth + 1)

    # 予測します、自分が木の端点となるノードなら自分のクラス、子のノードがいるならそのノードの予測結果に委ねます
    def predict(self, data):
        if self.impurity == 0 or self.depth == self.max_depth:
            return self.label
        child_node_index = int(not data[self.feature] >= self.threshold)
        next_node = self.children[child_node_index]
        return next_node.predict(data)


# 決定木クラスです
class DecicsionTree:

    # インスタンスを作る際に「最大の深さ」を指定します
    def __init__(self, max_depth):
        self.max_depth = max_depth
        self.tree = None

    # fit(データ, ラベル)とすることでノードクラスを呼び出し、学習します
    def fit(self, data, labels):
        self.tree = Node(data, labels, self.max_depth)
        self.tree.cart()

    # predict(テストデータ)とすることで予測を行います
    def predict(self, data):
        return np.array([self.tree.predict(sample) for sample in data])

以上をテストしてみます!

iris データセットを用いて『3種類の花の分類』を行ってみます!

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

iris = load_iris()
x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.2, random_state=0)

model = DecisionTree(max_depth=4)
model.fit(x_train, y_train)
predict = model.predict(x_test)
score = sum(predict == y_test)/float(len(y_test))
print('acc: {}'.format(score))
acc: 0.9666666666666667

予測結果 97% くらいの結果になりました!

COMMENT

コメントはありません