分類を行う決定木（CART）について丁寧に理解しようとした

#はじめに
　これまでロジスティック回帰、サポートベクトルマシン、ニューラルネットワーク等をまとめてきました。
　今回、XGBoostやLightGBM、ランダムフォレストなどの基礎となる決定木についてまとめます。

　

##決定木とは
　決定木とは、「段階的にデータを分別して、木のような分析結果を出力する」アルゴリズムになります。

　この決定木によって分析を行うことの利点は下記です。

• 理解が容易である（分類の根拠が可視化可能）
• 分類・回帰いずれにも適用できる
• あらゆる問題に広く対応可能

といった特徴があります。
　特に、一番目の利点が大きいように思います。他の分類器（サポートベクトルマシンやニューラルネットワーク等）は、中で行われている計算が非常に複雑かつブラックボックスであるため、そのモデルの中身に精通している人でないと中身について理解しにくい面があります。
　一方で、決定木は分割した際の根拠が上記の図のように明確であるため、理解しやすい特徴となります。この理解しやすいことは非常に大きい利点であると思います。
　モデルを使う立場の人間が、中身がよくわからないものを使って結果を出すことは、技術者としては良い態度ではないと思うからです。

　この決定木は分類と回帰いずれにも適用可能なアルゴリズムですが、今回は分類についてまとめたいと思います。
　また、決定木はCART、C４．５と呼ばれるアルゴリズムがあります。今回はCARTについて取り上げています。

##分割する基準をどう決めるのか

　
　分割後の要素（分けたいデータ）が、分けたい要素ごととなっている（＝分割後の不純度が最小）となるように分割を行います。
　不純度とは、いろいろなクラスの要素がまじりあっているかを示す指標です。

　例で簡単に考えてみたいと思います。散布サンプルを与えてくれるscikit learnのmake_blobs()メソッドを読み込んで作りたいと思います。

RF.ipynb

#Imports
%matplotlib inline
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn

from sklearn.datasets import make_blobs

X, y = make_blobs(n_samples=500, centers=4,
                  random_state=8, cluster_std=2.2)

#Scatter plot the points
plt.figure(figsize=(10,10))
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='jet')

元の散布図はこちらです。

さて、この散布図に関して分け方を考えます。

　左の分割線によって、要素$[0],[1]$が多く含まれている（逆に$[2],[3]$が含まれていない）グループと逆に要素$[2],[3]$が多く含まれている（逆に$[0],[1]$が含まれていない）グループに分けることができていることが分かります。このような分割が不純度が少ない分け方です。
　一方、右の分割線の場合だと、分けた後のグループに$[0]～[3]$の要素がそれぞれ混在していることが分かります。これを不純度が多いと表現します。
　左のような分割線を探して、分類していくことを何回か行い（＝決定木の深さと呼びます）目的の分類を行います。

##不純度の求め方

　さて、続いてこの不純度の表す方法についてまとめます。今回はジニ不純度($Gini's Diversity Index$)を取り上げます。
直訳だとジニ多様性指数となります。これでも日本語的に意味は理解できるかと思いますが、不純度と呼称する場合が多いようです。

　
　決定木のある階層（＝ノード）$t$を考えます。ノードとは、分割した後のグループを指します。そして、そのノード内のサンプルが$n$個、ノード内のクラスが$c$個のときを考えます。
このとき、ノード$t$内でクラス$i$に属するサンプルの個数を$n_i$とすると、クラス$i$に属するサンプルの割合$p(i|t)$は以下のように表すことができます。

$$ p(i|t) = \frac{n_i}{n} \tag{1} $$

このとき、ジニ不純度$I_G(t)$は以下のように表記することができます。
$$ I_G(t) = 1 - \sum_{i=1}^c {p(i|t)}^2 \tag{2} $$

$p(i|t)^2$の総和は良い分割ができていると値が大きくなります。従い、$I_G(t)$が小さくなります。この評価指標を用いて良い分類器を作っていくことになります。

###グラフを見やすいようにアレンジ

クラスごとに色付けして分かりやすいようにします。

RF.ipynb

def visualize_tree(classifier, X, y, boundaries=True,xlim=None, ylim=None):
    '''
    決定木の可視化をします。
    INPUTS: 分類モデル, X, y, optional x/y limits.
    OUTPUTS: Meshgridを使った決定木の可視化
    '''
    # fitを使ったモデルの構築
    classifier.fit(X, y)
    
    # 軸を自動調整
    if xlim is None:
        xlim = (X[:, 0].min() - 0.1, X[:, 0].max() + 0.1)
    if ylim is None:
        ylim = (X[:, 1].min() - 0.1, X[:, 1].max() + 0.1)

    x_min, x_max = xlim
    y_min, y_max = ylim
    
    
    # meshgridをつくります。
    xx, yy = np.meshgrid(np.linspace(x_min, x_max, 100),
                         np.linspace(y_min, y_max, 100))
    
    # 分類器の予測をZとして保存
    Z = classifier.predict(np.c_[xx.ravel(), yy.ravel()])

    # meshgridを使って、整形します。
    Z = Z.reshape(xx.shape)
    
    # 分類ごとに色を付けます。
    plt.figure(figsize=(10,10))
    plt.pcolormesh(xx, yy, Z, alpha=0.2, cmap='jet')
    
    # 訓練データも描画します。
    plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='jet')
    
    plt.xlim(x_min, x_max)
    plt.ylim(y_min, y_max)        
    
    def plot_boundaries(i, xlim, ylim):
        '''
        境界線を描き込みます。
        '''
        if i < 0:
            return

        tree = classifier.tree_
        
        # 境界を描画するために、再帰的に呼び出します。
        if tree.feature[i] == 0:
            plt.plot([tree.threshold[i], tree.threshold[i]], ylim, '-k')
            plot_boundaries(tree.children_left[i],
                            [xlim[0], tree.threshold[i]], ylim)
            plot_boundaries(tree.children_right[i],
                            [tree.threshold[i], xlim[1]], ylim)
        
        elif tree.feature[i] == 1:
            plt.plot(xlim, [tree.threshold[i], tree.threshold[i]], '-k')
            plot_boundaries(tree.children_left[i], xlim,
                            [ylim[0], tree.threshold[i]])
            plot_boundaries(tree.children_right[i], xlim,
                            [tree.threshold[i], ylim[1]])
    
    if boundaries:
        plot_boundaries(0, plt.xlim(), plt.ylim())

###決定木で分類してみる

RF.ipynb

from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(criterion='entropy',max_depth=2,random_state=0)

visualize_tree(clf,X,y)

良い感じに分けることができました。上記においてmax_depthにて決定木の深さを決めます。このmax_depthの値を大きくする（＝深くする）と、過学習になってしまいます。試しにmax_depth=6としてみます。

　

過剰に分けられていることが分かります（特に赤のクラス）。この深さは自前で調整する必要があることがポイントになります。

###決定木の根拠可視化

　さて、先ほど深さ２で検証した場合の決定木の画像が下記になります。

分類の基準となる数値及びジニ不純度が載っています。valueはクラス[0]～[3]の要素数になります。

##決定木画像を出力させる方法

　さて、さらっと載せた画像ですが、ライブラリのインポートやソフトのインストールが必要です。

1. pydotplusのインストール
2. graphvizのインストール
3. path通し

私が保存するためには上記3つの行為が必要でした。

1.pydotplusのインストール

これは、決定木で分割した内容を.dotファイルへ保存させるライブラリです。

console

pip install pydotplus

他のライブラリと同じくpipでインストールすればOKです。

2.graphvizのインストール

こちらのURLからインストーラー（graphviz-2.38.msi）をダウンロードしました。

ダウンロードが完了したら「graphviz-2.38.msi」をダブルクリックしてインストールを行います。さらに、pip上でもgraphvizをインストールしておきます。

3.pathを通す

　そして、pdf化させるためにpathを通します。dot.exeがあるフォルダを指定します。その方法は以前もまとめましたのでこちらを参照下さい。

最後に、graphviz.py内の構文を下記に従って書き換えることが必要です。

ここまでしたら下記で決定木の.dot化及びpdf化が可能になります。

RF.ipynb

import pydotplus
import os
from graphviz import Source
from sklearn.tree import export_graphviz

export_graphviz(
        clf,
        out_file=os.path.join("text_classification.dot"),
        class_names=['1', '2','3','4'],
        rounded=True,
        filled=True
    )
with open("random.dot", 'w') as f:
    f = export_graphviz(clf, out_file=f)

data = export_graphviz(clf, out_file=None)
graph = pydotplus.graph_from_dot_data(data)
graph.write_pdf("random.pdf")

こちらのサイトを参考にさせて頂きました。

GraphVizのエラー対処（GraphViz’s executables not found）
https://niwakomablog.com/graphviz-error-handling/

#終わりに

今回は、決定木の分類について内容及び実装をまとめました。考え方も理解しやすくかつ、実装も簡単です。
　しかし、ちゃんと最後は決定木のpdf化をさせることに若干ハードルが高さを感じました。
次は、回帰を行ってみたいと思います。

プログラム全文はこちらです。
https://github.com/Fumio-eisan/RF_20200423