決定木 人間の思考に近いアルゴリズム

決定木 人間の思考に近いアルゴリズム

こんにちは。エンジョイワークス、システム開発部 MLエンジニアのしゅんです。

今日は機械学習の中でも、最も有名なアルゴリズム、決定木を紹介します。

決定木は、分類問題でも回帰問題でも使えます。しかも、我々の思考に近いプロセスで意思決定しますので、ニューラルネットワークなどと比べると、非常にわかりやすいです。例えば、「外は曇り?」もし「はい」ならば「傘を持って行こう」、「いいえ」ならば「持っていかない」のように条件分岐します。

つまり決定木は、二択の質問を繰り返すことによって、データを分類していきます。

ただのif文じゃないか、と思うでしょうが、ここの機械学習の本質があります。if文は人間が判定条件を決めますよね。決定木は、データから判定条件を自動的に計算します。

実際に、二択の質問は、どうやって決めるのでしょうか?決定木の考え方は、ある閾値を基準に、これ以上分割できなくなるまで、繰り返し処理をおこなっていきます。人間の脳は判断する時に、過去の経験を参考にします。一方で、決定木は情報利得が、最大になるように決定していきます。情報利得については、後ほど触れます。

簡単な例を見ていきましょう。例えば、犬か猫かを、体重と身長によって分類したいとします。体重15lbs(7kg)以上だと、間違いなく犬でしょう(今回のような単純なデータセットの場合)。条件に当てはまらない場合、猫が2匹、犬が1匹となります。この場合さらに分割が必要です。これを不純度が0になるまで繰り返します。

この不純度とはなんでしょう?分割後のデータセットが、全部「犬」または「猫」になった状態を不純度を0と表現します。つまり、これ以上分割できないと言うことです。逆に「犬」「猫」が3匹づつの均等の状態は不純度が高い状態です。

不純度は具体的に、どうやって計算しているのでしょうか?また、どうやって各ノードが分割する条件を、判断しているのでしょうか?

ここでジニ係数の登場です。ジニ係数で、各ノードの不純度を計算していきます。ジニ係数は例えば「社会における所得の不平等」などを測る指標として、一般的に使われています。

「情報利得が最大」なったことを判断する基準も、ジニ係数を元にします。

ジニ係数の計算方法ですが、各ノードの不純度を、確率p(i|t)で表し、それらを二乗した合計を1から引きます。

ノードが純粋( 4/4 = 1)であればジニ係数は0となります。つまり「混じりっけのない綺麗なノードです!」その場合、これ以上分割できないことになりますので、先端の葉の部分に達します。

犬猫データセットの例だと3つデータセットのうち、2匹が猫、1匹が犬ですね。計算すると以下のようになります。

他にもエントロピーという判断指標もあるのですが、今回はジニ係数のみを紹介します。

決定木は、情報利得が最大になるように、計算していきます。情報利得はジニ係数によって、を計算していきます。以下が計算式になります。

情報利得は、親ノードと子ノードのジニ係数の差によって定義されます。つまり、親ノードの不純度の合計と、子ノードの不純度の合計の差です。ノード間の不純度が低いほど、情報利得は大きくなります。

情報利得が最大になるパターンが、精度の高い決定木です。

親ノードのジニ係数と、子のジニ係数の差を取ります。

親ノードのジニ係数0.48から、各子ノードの重みを引き算します。

実際に計算してみました。

1- (3/5)^2 + (2/5)^2  – 2/5 *  1- (2/2)^2  – 3/5 *  1- (2/3)^2 + (1/3)^2

1-0.52 – 0.4 * 0 – 0.6 * 0.44

0.48 – 0.264 = 0.216

引き算した結果が、高ければ高いほど、綺麗に分割できたことになります。

このように、決定木とはデータから不純度を計算し、情報利得が最大になるパターンを自動で選び出すアルゴリズムです。(厳密には今回のように、2分割していくアルゴリズムをCARTと言います。)

それでは、実際にscikit learnで実装して見ましょう。

from sklearn.tree import DecisionTreeClassifier
import pandas as pd

# データセットを用意
data = [[8,8,'dog'],[50,40,'dog'],[8,9,'cat'],[15,12,'dog'],[9,9.8,'cat']]

# データセットをDataFrameに当てはめる。
df = pd.DataFrame(data, columns = ['weight','height','label'])

# 説明変数
X = df[['weight','height']]

# 目的変数:ラベルを数字にマッピング
y = df['label'].replace({'dog':1, 'cat':0})

# モデルをインスタンス化
tree = DecisionTreeClassifier() 

# 学習
model = tree.fit(X,y)

決定木のメリットは、判断基準のプロセスを、可視化できることです。export_graphvizを使うとイメージとして出力してくれます。

from sklearn.externals.six import StringIO  
from sklearn.tree import export_graphviz
import pydotplus
from IPython.display import Image


dot_data = StringIO()  

export_graphviz(
    model, 
    out_file = dot_data,  
    filled=True, rounded=True, proportion=False,
    special_characters=True, 
    feature_names=X.columns,
    class_names=["cat", "dog"]
)  

graph = pydotplus.graph_from_dot_data(dot_data.getvalue())  

Image(graph.create_png()) 

早速、plotして見ましょう。

実際に分割した結果を見ると、まず体重12lbsで分割していますね。犬だけのノードができています。次に体重8.5lbsで分割しています。ここでノード先端に達しましたね。葉のノードは、ジニ係数が0になりました。

このように決定木を用いると、どのような条件で分割していったかを可視化できます。

さて、決定木は使うべきか?使うべきでないか?

メリット

・分割したプロセスを可視化できる

・前処理が楽。きれなデータセットでなくていい。

・回帰と分類に使える。

デメリット

・過学習を起こしやすい。データセットの小さな変更が、分類パターンを変えてしまう。

実際のプロジェクトでは、単体として決定木を使うことは稀です。アサンブル学習といって、決定木を複数使用した、ランダムフォレストを使うことが一般的です。いずれにしろ、決定木はベースとなるアルゴリズムなので、理解しましょう。

如何でしたか?アルゴリズムを追う、面白さが体験できてもらえたら幸いです。

エンジョイワークスではバックエンドエンジニアを募集しております。空き家問題を自分のスキルで解決したいエンジニアは是非ご応募ください!

リクルート情報はこちら!
https://enjoyworks.jp/recruit

一覧へ戻る