scikit-learn機械学習⑪決定木（Decision Tree）

前回は、ナイーブ・ベイズを実装しました。今回は、決定木（Decision Tree）を解説します。

決定木は、データセットを分割し、木構造を作ります。下図は、アイリス（Iris）のデータセットを使用して訓練された決定木モデルの可視化です。scikit-learnで生成することが出来ます。

詳細は記事の中で解説しますが、この決定木モデルは、花の特徴（花弁とがく片の長さと幅）に基づいて、アイリスの3種類（Setosa、Versicolor、Virginica）に分類しています。よって、入力データに対して木構造にある条件をたどっていけば、花の予測が出来ます。

では、決定木は何を持ってデータセットを分割しているのでしょうか。

木構造の生成

決定木によるデータセット分割のプロセスの基本的な考え方は、データセットを２つに分割ためにどの特徴を使うべきかを決定し、最終的な判断が可能になるまで分割を続けることです。

ここでは、アイリスの訓練用のデータセットを作成したとして、決定木がどのようにデータを分割していくかを説明します。

ルートノードの選定：決定木の作成はルート（根）ノードから始まります。このノードでは、データを最もよく分割できる特徴と分割のための閾値しきいちを選びます。

下図はルートノードを示しています。

Setosa、Versicolor、Virginicaがそれぞれ31、37、37（value = [31, 37, 37]）あることが表示されています。また、その合計は105（samples = 105）です。数が一番多いのは、Versicolor(37) と Virginica(37)ですが、このノードで一番多いクラスとしてVersicolor（class = versicolor）と表示されています。

このノードでは、分割条件として「花弁の長さが2.45 cm以下」（petal length (cm) <= 2.455）で判断しています。

分割されたノードは子ノードとして表示されます。分割条件を満たしているものは、左の子ノードになり、他は右の子ノードになります。

左の子ノードのクラスは、Setosa(31)しかないので、これ以上の分割は行われません。これをリーフ（葉）ノード（あるいは、終端ノード）と呼びます。よって、ここに属するデータはSetosaであると予測されます。

右の子ノードには、Versicolor(37) と Virginica(37)があります。新たな分割条件として「花弁の長さが4.75 cm以下」（petal length (cm) <= 2.455）で判断しています。よって、さらにこノードが生成されます。

左の子ノードのクラスには、Versicolor(32) と Virginica(1)があり、まだ葉ノードではありません。新たな分割条件として「花弁の幅が1.6 cm以下」（petal width (cm) <= 1.6）が設定されています。ここで「花弁の幅」という特徴が使われており、以前の「花瓶の長さ」だけでは全てを判断できないのが分かります。

左の子ノードのクラスには、Versicolor(5) と Virginica(36)があり、まだ葉ノードではありません。新たな分割条件として「花弁の幅が1.75 cm以下」（petal width (cm) <= 1.75）が設定されています。ここでも「花弁の幅」が条件の中で使われています。

最終的に以下のようになります。なお、数が多いクラスによって色分けされているのが分かります。

こうして得られて木構造は、訓練データの構造を反映しています。これを未知のデータ（例えば、テストセット）に適用すればクラスの予測ができます。

つまり、訓練データから判断のためのルールを作り上げているわけです。判断の仕方は、条件を一つ一つ追いかけて葉ノードに到達するまで続けます。プログラムを作るときのフローチャートにちょっと似ています。

ところで、どのようにして分割条件を作るのでしょうか。そこで、先ほど説明を飛ばした gini が登場します。

ジニ係数（ジニ不純度）

gini は、ジニ係数（Gini index）またはジニ不純度（Gini impurity）のことで、決定木を作成する際に使用される尺度の一つで、ノードの純粋度を評価するために使われます。

ジニ不純度は0から1の範囲の値をとり、値が低いほどそのノードは純粋であるとされます。

もう一度、図を見ると gini の値が下の方の子ノードに行くにつれて小さくなっているのが分かります。つまり、データセットを分割する際には、gini の値が小さくなる特徴を選んでいます。

完全に純粋なノード（つまり、ノードに含まれる全てのサンプルが同じクラスの場合）ではジニ不純度は0になります。逆に、クラスが完全に混在している（例えば二つのクラスが50%ずつ含まれる）場合はジニ不純度が最大値に近づきます。

よく見ると、一番したの右２つのノードは、gini が０ではありません。これは、まだ複数のサンプルが含まれているからです。実は、この図を生成する際に、木構造の最大の深さを３に設定したので、それ以上の深さの子ノードは生成しないことになっています。

ジニ不純度は次の式で計算されます。

$$
\text{gini} = 1 - \sum_{i=1}^{n} (p_i)^2
$$

ここで、$${p_i}$$は$${i}$$番目のクラスのサンプル割合、$${n}$$はクラスの数です。アイリスで考えると、$${n=3}$$で$${p_i}$$は各クラスの割合です。

各クラスの割合の二乗を計算したものを合計して1から引いているので、複数のクラスが混じっているとgini の値が大きくなります。つまり、クラスの割合が均等になればなるほど、ジニ不純度は大きくなります。

例えば、ルートノードでは、Setosa、Versicolor、Virginicaがそれぞれ31、37、37（value = [31, 37, 37]）で、合計は105（samples = 105）でした。よって、gini の値は次のように計算できます。

$$
\text{gini} = 1 - \left( \left( \frac{31}{105} \right)^2 + \left( \frac{37}{105} \right)^2 + \left( \frac{37}{105} \right)^2 \right) \approx 0.664
$$

さて、決定木のアルゴリズムでは、このジニ不純度が最小となるような特徴と閾値を探して、ノードを分割する基準としているのが分かりましたが、どのようにしてその基準を探すのでしょうか。

これも訓練データから選びます。各特徴に対して、ユニークな値を選び順番に並べ、その中間値を基準値として gini を計算し最も gini が小さくなる値を採用します。

例えば、特徴値が  [ 1.0, 1.2, 1.2, 1.6, 1.9 ] というリストであった場合、ユニークな値は [ 1.0, 1.2, 1.6, 1.9 ] となります。分割点の候補は、1.0 と 1.2 の間、1.2 と 1.6 の間、1.6 と 1.9 の間の中間値、すなわち 1.1, 1.4, 1.75 となります。

また、scikit-learn の決定木ではジニ係数（ジニ不純度）をデフォルトで使いますが、そのほかにエントロピーを選ぶことも可能です。

エントロピー

エントロピー（Entropy）の概念は、もともとは情報理論から来ていますが、決定木の文脈ではデータセットの無秩序さを測る指標です。

エントロピーが高いほどデータセットの無秩序さが高いことを示し、クラスが完全に混在している場合（つまり、全てのクラスが均等な確率で現れる場合）は完全に無秩序なので値が最大になります。

エントロピーは次の式で計算されます。

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

$${p_i}$$は$${i}$$番目のクラスのサンプル割合を表し、$${n}$$はクラスの総数です。

エントロピーの値が0の場合、データセットは純粋であり（つまり、全てのサンプルが同じクラスに属する）、値が高くなるほどデータセットの不純度が高くなります。

ジニ不純度とエントロピーの間で、どちらの基準を選ぶかは、実際に両方を試してみて、検証セット上での性能を比較するなどする必要があります。多くの場合、両者の違いは微小です。また、エントロピーは対数の計算が含まれているので、巨大なデータセットでは計算コストが多くなる可能性はあります。なので、特に問題がなければデフォルトの gini を選ぶのが良いでしょう。

次回予告

次回は、scikit-learnのDecisionTreeClassifierを使って簡単な実装と実験を行います。

お楽しみに！