アンサンブル学習アルゴリズム入門〜〜決定木その1〜〜

アンサンブル学習とは

アンサンブル学習とは、複数の機械学習モデルを組み合わせて使用するタイプの機械学習アルゴリズムのことです。
Kaggleのようなデータ分析コンペティションでもよく使われているLightGBMなどもアンサンブル学習アルゴリズムの一つです。

この記事のシリーズは2019年6月に出版された「作ってわかる！アンサンブル学習アルゴリズム入門」の内容に沿っています。

作者: 坂本俊之
出版社/メーカー: シーアンドアール研究所
発売日: 2019/05/28
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

この本では、Pythonを使用して、複数のアンサンブル学習アルゴリズムを1からスクラッチで作成します。

アンサンブル学習の系譜

アンサンブル学習の中にもいくつかの種類があり、基本的な手法として、バギング、ブースティング、スタッキングなどの手法が知られています。
さらに、ブースティングとして分類されるアルゴリズムの中にも、AdaBoost系のある、勾配ブースティング系のアルゴリズムなどと複数の種類があります。

アンサンブル学習のアルゴリズムでは、一般的に決定木アルゴリズムをベースのアルゴリズムとして使用するので、本シリーズでも基本的に決定木アルゴリズムをベースとして採用します。

決定木

決定木アルゴリズムは、条件による分岐を根からたどることで、最も条件に合致する葉を検索するというアルゴリズムで、IF-THENルーチンと同じです。
機械学習における決定木は、学習データをもとにして、説明変数からなる条件式をノードとすることで説明変数に対するモデルを含む葉を検索することになります。

枝と葉

決定木アルゴリズムで作成されるモデルは、ある一つのノードが根となり、そのノードから伸びる複数の枝が、次のノードまたは葉を示す構造となっています。

f:id:rikeiin:20190923112813p:plain — https://datachemeng.com/decisiontree/

決定木を使用した機械学習では、各ノードには、からなる条件式が入ることになります。そうすると、ある入力に対して決定木をたどっていけば、いずれかの葉にたどり着くことになります。

決定木によるデータの分割

言い換えるとデータセットに含まれるデータは、全ていずれかの葉に属することになり、このことは決定木はデータを葉の数に分割するということを表しています。そしてデータを葉の数に分割し、それぞれの葉でクラス分類や回帰のモデルを適用することで全体としてより望ましいモデルを構築することが決定木アルゴリズムの目的です。

決定木にはそれが単体が機械学習モデルというわけではなく、基本的にはデータの分割に関するアルゴリズムであり、葉となる機械学習モデルと組み合わせて利用されます。

葉の部分で利用できるモデルはデータの部分集合に対して学習と実行行えるモデルであれば何でも良いのですが決定木の葉の部分にあまり複雑なモデルを使用することは一般的には行われません。本記事ではZeroRule(クラス分類であれば「学習時に最も多かったクラス」、回帰であれば「学習した正解データの平均値」)と線形回帰モデルという二つのアルゴリズムをモデルとして使用します。

木の分割

決定木による分割それ自体も機械学習アルゴリズムの一種であり学習データからモデルを作成します。決定木の学習ではまず深さの浅い決定木を作成しその葉の部分に新しいノードを追加していくことで順次より深さの深い決定木を作成しますこのような葉を新しいノードとしてデータを分割していくことを木の分割と呼びます。

f:id:rikeiin:20190923114951p:plain — http://codecrafthouse.jp/p/2014/09/decision-tree/

上記の決定木ではそれぞれのノードでは一度に説明変数内の一つの値しか見ていません。つまりノード内にある条件式は横軸または縦軸のどちらかの値によって処理を振り分けるので図中の全ての分割線は水平または垂直になっています。そのように単純な条件式のみからなるのノードでも、気の深さを深くしてやることで複雑なデータでも分割を可能とするのが決定木アルゴリズムの特徴です。

Metics関数

決定木アルゴリズムでは説明変数からなる条件式で最もよく目的変数を分割できる条件をもとにノードを作成します。ここで「最もよく」目的変数を分割するために目的変数の分割の良さを数値で比較できるスコアが必要になりますが、そのために使用するのが損失関数またはMetrics関数と呼ばれる関数になります（本記事では以後Metics関数と呼びます）。この関数でノード内の条件式を評価し、最もよく目的変数を分割できるように学習を行います。

よく用いられるMetics関数にはいくつか種類があります。

標準偏差

回帰に使用されるMetics関数として標準偏差の合計が挙げられます。これは目的変数を分割する際に、分割後のグループごとの標準偏差を取り、その合計が少ないほどよくデータ分割できているとするものです。
ここで作成するMetics関数は「entropy.py」という名前のファイルに作成して、後で紹介する決定木アルゴリズムでインポートして使用します。

import numpy as np
def deviation(y):
    return y.std()

Gini impurity (ジニ不純物)

クラス分類では目的変数はクラスを表す番号であり、値そのものの比較には意味がないので与えられた目的変数のリスト内がどのくらい単一のクラスからなっているかを評価することになります。
そのために使用されるのがGini impurityです。経済学で使われるジニ係数 (Gini coefficient)とは異なるので注意してください。

$n$ をデータに含まれるクラスの個数、 $p_i$ をデータがクラス $i$ である確率とするとGini impurityは以下の式で表されます。

$\displaystyle{ Gini(p) = \sum_{i=1}^n p_i (1-p_i)=\sum_{i=1}^n p_i - \sum_{i=1}^n p_i^2 = 1 - \sum_{i=1}^n p_i^2 }$

[決定木]ジニ不純度と戯れる - Qiita

上記の式をpythonで実装すると下記のようになります。

def gini(y):
    # compute gini impurity
    m = y.sum(axis=0)
    size = y.shape[0]
    e = (m / size) ** 2
    return 1.0 - np.sum(e)

Information gain

クラス分類で使用される metrics 関数としてInformation Gainもあります。
これは情報理論で使用するエントロピーに基づく関数で、分割後の目的変数に含まれる情報量が少なくなるように分割点を求めます。

Information Gainの正しい定義は、元の集合のエントロピーから分割後の集合のエントロピーの重み付き合計を引いた値でその値が大きくなるような分割を目指します。
決定木の場合親ノードから与えられたデータのエントロピーから子ノードに渡すデータのエントロピーの合計を引いたものがノード内の条件式が持っている情報量ということになるので、Information gainはノード内の条件式が持つ情報量を最大化するようにデータを分割するMetics関数とも言えます。
ここでは決定木のノードにノートの一つの分割を考えるので単純に分割後のエントロピーの合計が小さくなるように目的変数を分割します。

エントロピーは乱雑度とも考えられるので、乱雑度を小さくするように分割する、と考えてもいいかもしれません。

情報量 - Wikipedia
情報理論の基礎～情報量の定義から相対エントロピー、相互情報量まで～ | Logics of Blue

$n$ をデータに含まれるクラスの個数、 $p_i$ をデータがクラス $i$ である確率とするとエントロピーは以下の式で表されます。

$\displaystyle{ Entropy(p) = - \sum_{i=1}^n p_i \log_2 (p_i) }$

上記の式をpythonで実装すると下記のようになります。

def infgain(y):
    m - y.sum(axis=0)
    size = y.shape[0]
    e = [p * np.log2(p / size) / size for p in m if p != 0.0]
    return -np.sum(e)

scipyでも計算できます。
【python】pythonで情報エントロピーの計算 - 静かなる名辞

DecisionStump

DecisionStumpとはアルゴリズムの評価に使用される最もシンプルな構造をした決定木で、深さが1の決定木のことです。
DecisionStumpにはノードが一つと葉が二つの要素しかありませんが、データの分割と葉によるモデルの結合という決定木アルゴリズムの基礎が含まれており、データの分割アルゴリズムなども評価に用いられます。
またDecisionStumpはアンサンブル学習のアルゴリズムを評価する際のベースにも使用されます。
アルゴリズムを評価する際のベースとしては複雑なモデルを使用してもベースのモデルの性能として良い結果が出ているのか、アンサンブル学習アルゴリズムの性能としていい結果が出ているのかわからないため、最もシンプルな構造をした決定木であるDecisionStumpが使用されます。

木分割の実装

実際にDecisionStumpの実装を行っていきます。
dstump.pyというファイルに下記クラスを実装します。

class DecisionStump:
    def __init__(self, metric=entropy.gini, leaf=ZeroRule):
        self.metric = metric # 使用するMetics関数
        self.leaf = leaf # 葉のモデル
        self.left = None # 左の葉のモデルインスタンス
        self.right = None # 右の葉のモデルインスタンス
        self.feat_index = 0 # 分割に使用する目的変数の位置を表す
        self.feat_val = np.nan # 分割に使用する目的変数の値を表す
        self.score = np.nan # 分割の際のMetics関数の値を表す（今後使用）

左右のインデックスを取得する

上記のDecisionStumpクラス内に決定木アルゴリズムに必要となる機能を実装します。
まず作成するのは、目的変数から取得した値の配列を特定の値より小さなものとそれ以外に分ける関数で「make_split」という名前の関数を作成します。
この関数は1次元の数値からなる配列を与えられた値で分割した際のインデックスを返します。

def make_split(self, feat, val):
        # featをval以下と以上で分割するインデックスを返す
        left, right = [], []
        for i, v in enumerate(feat):
            if v < val:
                left.append(i)
            else:
                right.append(i)
        return left, right

分割した後のスコアを計算する

次に作成するのは記事上部で作成したMetics関数を使用して、分割した後のスコアを計算する「make_loss」という名前の関数です。
この関数では「self.metric」に代入されているMetics関数でそのスコアの重み付き合計を求めます。
関数の引数は左右に分割した目的変数となります。

def make_loss(self, y1, y2):
        y1_size = y1.shape[0]
        y2_size = y2.shape[0]
        if y1_size == 0 or y2_size == 0:
            return np.inf
        totol = y1_size + y2_size
        m1 = self.metric(y1) * (y1_size / totol)
        m2 = self.metric(y2) * (y2_size / totol)
        return m1 + m2

データを左右に分割する

次に作成するのは説明変数と目的変数からデータを左右の枝に振り分ける「split_tree」関数です。
この関数では説明変数内の全ての次元に対して、その中の値でデータを分割した際のスコアを計算します。
そして、そのスコアが最も小さくなる説明変数内の次元の位置と分割値を「self.feat_index」と「self.feat_val」変数に保存しておきます。
最後に、分割した後の左右の葉に振り分けられるデータのインデックスを返します。

def split_tree(self,x, y):
        # データを分割して左右の枝に属するインデックスを返す。
        self.feat_index = 0
        self.feat_val = np.inf
        score = np.inf
        left, right = list(range(x.shape[0])), []
        # 説明変数内のすべての次元に対して
        for i in range(x.shape[1]):
            feat = x[:, i]
            for val in feat:
                # 最もよく分割する値を探す
                l, r = self.make_split(feat, val)
                loss = self.make_loss(y[l], y[r])
                if score > loss:
                    score = loss
                    left = l
                    right = r
                    self.feat_index = i
                    self.feat_val = val
        self.score = score
        return left, right

学習部分の実装

DecisionStumpは深さが1の決定木なので、学習のためのコードはデータを左右の端に振り分けてそれぞれの葉の学習を行うだけです。
self.leaf変数に葉となるモデルが入っているので、それを呼び出してインスタンス化しておき、 split_tree()で左右の端に振り分けたデータを学習させます。
また、必ずしも左右に値が振り分けられるとは限らず、どちらか一方の端にのみデータが集中する可能性もあるので if 文でデータの長さをチェックしてから学習を行います。

def fit(self, x, y):
        # 左右の葉のモデルをインスタンス化
        self.left = self.leaf()
        self.right = self.leaf()

        # データを左右の葉に振り分ける
        left, right = self.split_tree(x, y)
        # 左右の葉を学習
        if len(left) > 0:
            self.left.fit(x[left], y[left])
        if len(right) > 0:
            self.right.fit(x[right], y[right])
        return self

推論部分の実装

DecisionStumpの推論は、左右の端へデータを振り分けて、それぞれの葉のモデルの実行結果から最終的な出力を作成します。
データを左右の端に振り分けるのはmake_split()を使用し、左右ともにデータがあれば左右の葉の実行結果をそのインデックスに代入して最終的な結果とします。
また左右のどちらかのみにデータがある場合は左右の葉のいずれかの実行結果が最終的な結果となります。

def predict(self, x):
        feat = x[:, self.feat_index]
        val = self.feat_val
        l, r = self.make_split(feat, val)
        z = None
        if len(l) > 0 and len(r) > 0:
            left = self.left.predict(x[l])
            right = self.right.predict(x[r])
            z = np.zeros((x.shape[0], left.shape[1]))
            z[l] = left
            z[r] = right
        elif len(l) > 0:
            z = self.left.predict(x)
        elif len(r) > 0:
            z = self.right.predict(x)
        return z