分類木 アルゴリズム

1. home
2. python
3. machine_learning

: 2024年4月7日 : 2024年4月7日

• 分類木とは、複数の条件分岐を用いて、レコードを分類する木のこと。レコードを用いて木を作成していく
• 上のデータは花の情報から花の種類を推測するというもの(df = sns.load_dataset('iris')でだれでも入手できる)
• 花の情報(がくの長さ、がくの幅、花びらの長さ、花びらの幅)から種類を推測する時、例えば以下のような木が考えられる

• がくの長さが6.85より大きければ、花の種類は「virginica」と推測
• がくの長さが6.85以下のとき、
  • がくの長さが6.85より大きければ、花の種類は「virginica」と推測
  • がくの長さが6.85以下のとき、

できる。このとき、条件分岐に使う特徴量や具体的にどの数値を選ぶかは後で説明するが、例として上のような木が考えられることがわかるだろう。実際、上のデータの花の種類を分類木で予測すると、すべて正しく分類できる(過学習を起こしているといえるので良くはない) 例として作成した木の最初の条件では「がくの長さ ≤ 6.85」という条件を用いていた。この条件として好ましい条件はどのようなものであろうか。例として以下の二つの条件を比較してみる。 表は条件のもとで分岐されたレコードにおける、花の種類別の個数である。左の条件ではがくの長さが5.4以下のレコードにおいて、virginicaの数は0、setosaの数は1、versicolorの数は0ということを示している。 条件としてよいものはより良くレコードを分類できるものである。「がくの長さ≤6.85」がFalseのときはかなり理想的で、「がくの長さ≤6.85」がFalseでさえあれば花の種類がvirginicaと確定する。「がくの長さ≤6.85」がTrueであれば、花の種類はvirginicaかsetosaで確定する。また、virginicaとsetosaの比率も3:1でこれ以上条件分岐を追加しないならばvirginicaと予測することもできる。 これに対し、「がくの長さ≤5.4」という条件はTrueのときはsetosaに確定するが、Falseのときは三種類のどれでもありうる。 こう考えると、「がくの長さ≤6.85」という条件は「がくの長さ≤5.4」より良い条件といえるだろう。このような考えのもと、条件の良さを表す指標として

• 条件分岐後、とりうる種類の数はすくない方がいい(一つ以外は全て0個がもっともよい)
• 条件分岐後、複数の種類の可能性があったとしても、どれかに偏ってほしい

が考えられる。上を満たす指標としてジニ関数がある \[ G(I_r) = 1 - \sum_{c \in C} \left( P(c|I_r) \right)^2 \] これがジニ関数。この式の説明のため、いろいろと文字を割り当てていく

• \((y_1, y_2, \cdots, y_i, \cdots y_n)\) : n次元ベクトルで、目的変数(教師データ)。上の例ではデータの「種類」の列に該当する
• \(\left( \boldsymbol{x}_1, \boldsymbol{x}_2, \cdots \boldsymbol{x}_i,\cdots \boldsymbol{x}_n \right) \) : n個のd次元ベクトルで添え字のiでレコードを区別する。学習データである.$\bm{x}_i$が一つのレコードでd個の特徴量を持っている。上の例ではn=10,d=4
• \(C = \left\{c_1, c_2, \cdots c_j, \cdots c_m \right\} \) - : \(c_j\)をクラスラベル(virginica,setosa,versicolorなど)。Cをクラスラベルの集合する。例では、m=3
• \(r\) : rはノード番号とする。根をr=1のノードとし、以降は適当にノード番号を割り当てる
• \(I_r \) : 第rノードに属するレコードのインデックスの集合。属するとは、条件分岐をしたとき、そのノードで条件は判断したレコードのこと。第一ノード(根)には全てのレコードがあるので、\(I_1 = \left\{1,2,\cdots,n\right\}\)となる。
• \({|\left\{ i \in I_r : y_i = c \right\} | } \) 第rノードの中で、ラベルが\(c\)であるレコード数。例えば、\(I_r = \left\{1,2,5\right\}\)であるとすると、インデックス1はversicolorでインデックス2はsetosaで、インデックス5はversicolorである(一番上の表を上からインデックス付けしている)。このとき数式中の\(c\)は(versicolor,setosa,virginica)のどれかで、y=versicolorだとすると以下のようになる。 \[{| \left\{ i \in I_r : y_i = c \right\} | } = | \left\{ 1,5 \right\} | =2\]
• \(P(c|I_r) : \) これは以下で与えられる式で、第$r$ノードに属するレコードにおいて、クラスラベルがcであるレコードの割合である \[P(c|I_r) = \frac {| \left\{ i \in I_r : y_i = c \right\} | } {|I_r|} \]
• ここまで文字を割り当てれば\(G(I_r)\)が理解できる。\(G(I_r)\)は小さければ小さいほど良い指標で、\(I_r\)を引数にとっているので、ノード一つに対して定まる値。
• \(I_r\)において、同じクラスラベルのレコードが多いとき、(例えばすべてのレコードが同じクラスラベル\(c_2\)のとき、)以下のようになる。 \[ G(I_r) = 1 - \sum_{c \in C} \left( P(c|I_r) \right)^2 = 1 - \left( P(c_2|I_r)^2 + \sum_{c \in C/\{c_2\}} \left( P(c|I_r) \right)^2 \right) = 1 - (1 +0 ) = 0 \]
• \(I_r\)において、半分がクラス\(c_1\)でもう半分が\(c_2$\)のときどうようの計算をするとジニ関数は\(\frac{1}{2}\)となる
• \( \)

以上からわかるとおり、ジニ関数はある条件によって分割されたレコードのクラスラベルを調べることで、その条件の良さを評価することができる。 そして、ジニ関数が最小になるような条件を探していくことが次なる課題である。 以下ノードの不純度はノードをジニ関数に入力したあとの出力とする。不純度という名前は、ノードが単一のクラスラベルのみを含む(純度が高い)ときに1となり、多くのクラスラベルを含むとき(純度が低いとき)ジニ関数の値は小さい
実際のジニ関数を計算すると のようになる。丸はノード番号を表している。レコード数に応じた加重平均を計算すると

• 「がくの長さ≤5.4」 : \(G(I_2) \frac{1}{10} + G(I_3)\frac{9}{10} = 0.5444444...\)
• 「がくの長さ≤6.85」: \(G(I_2) \frac{8}{10} + G(I_3)\frac{2}{10} = 0.5\)

となり「がくの長さ≤6.85」の方が加重平均のジニ関数のが小さい 全探索である。LightGBMでは書く特徴量をヒストグラム化することで、計算量を削減しているが、とりあえず全探索について解説する。

1. 一つ特徴量(がくの長さ、がくの幅、花びらの長さ、花びらの幅)を選ぶ。どれから選んでもよい
2. 選んだ特徴量を基準にソートをする。例としてがくの長さでソートすると以下のようになる
3. がくの長さを基準としたので、条件を「がくの長さ≤n」(nは次のリストの数[5.4, 5.6, 5.7, 5.8, 6.0, 6.1, 6.2, 6.8, 6.9, 7.7])として全てのジニ関数を求める
4. ほかの全ての特徴量に対してもソートを行い、全てのジニ関数を求める。
5. そうして、全てのジニ関数の中でもっともジニ関数が小さい条件分岐を採用する。

ここまでで説明してきたことは、条件の良さを測る尺度ジニ関数と、ジニ関数を最小にする条件の探索方法である。しかし、実際に木を作るとき、根ノードは単純にジニ関数が最小となる条件を使えばいいが、その後、どのノードを分割したらいいかということは説明していない。

• がくの長さが6.85より大きければ、花の種類は「virginica」と推測
• がくの長さが6.85以下のとき、
  • 花びらの長さが2.65以下のとき、花の種類は「setosa」推測
  • 花びらの長さが2.65より大きいとき、花の種類は「versicolor」推測

できる。このとき、条件分岐に使う特徴量や具体的にどの数値を選ぶかは後で説明するが、例として上のような木が考えられることがわかるだろう。実際、上のデータの花の種類を分類木で予測すると、すべて正しく分類できる(過学習を起こしているといえるので良くはない) ここまでで説明してきたことは、条件の良さを測る尺度ジニ関数と、ジニ関数を最小にする条件の探索方法である。しかし、実際に木を作るとき、根ノードは単純にジニ関数が最小となる条件を使えばいいが、その後、どのノードを分割したらいいかということは説明していない。 この木では、ジニ関数が最小となるよう、根ノードを分割したが、その後、根ノードの左の子を分割することの妥当性が問題。いまから、どのノードを分割すべきかという話をする。 考え方としては、ある葉を引数にとる関数\(f(I_r)\)を用意し、その値が判断するというもの

• \(I_r\): fの引数になる葉ノード
• \(I_{r+1}\) : \(I_r\)をある条件で分割したときの左の子。このときの条件は全探索により探す
• \(I_{r+2}\) :\(I_r\)をある条件で分割したときの右の子
• \(P_L(I_r)\) :\(I_r\) を条件である条件で分割したとき、左の子に属するレコードの割合
• \(P_R(I_r)\) :\(I_r\)を条件である条件で分割したとき、右の子に属するレコードの割合

関数fとして使うのは以下 \[f(I_r) = G(I_r) -P_L(I_r)G(I_{r+1}) -P_R(I_r)G(I_{r+2})\] 意味としては、\(I_r\)の不純度から、分割後の子ノードの不純度の加重平均を引いている。この\(f(I_r)\)が大きいとき、\(G(I_r)\)が\(P_L(I_r)G(I_{r+1}) +P_R(I_r)G(I_{r+2})\)よりも大きいということであり、不純度が下がっている

• \(I_a\) : 属するレコードがとても少ないノード
• \(I_b\) : 属するレコードがとても多いノード

そして、\(f(I_a)\)と\(f(I_b)\)を比較すると、\(f(I_a)\)の方が大きいとする。\(I_a\)ノードを分割することにより、不純度が減り、分類の精度が上がるというのは間違った主張ではないが、\(f(),G()\)の内容を見ればわかる通り、レコードの割合にしか着目していない。少し\(f(I_a)\)の方が大きいくらいならば、要素数が多い\(I_b\)を分割した方が分割の精度が高くなるだろう。よって、新しい関数\(f\)として以下を用いる \[f(I_r) = \frac{|I_r|}{|I_1|} \left( G(I_r) -P_L(I_r)G(I_{r+1}) -P_R(I_r)G(I_{r+2}) \right)\] そのノードに属するレコード数が多いほど正のバイアスがかかるようになる。全ての葉ノードに対し、関数fの値を求め、その値が最も大きいノードを分割する

• \(N_{leaf}\) :葉ノード番号の集合。初期状態は\(N_{leaf} = \{1\}\)
• \(n\) : レコード数
• \(I_r\) : 第rノードに属するレコードのインデックス。第一ノードは\(I_1 = \{1,2,\cdots,n\}\)
• \(N_{min}\) : ハイパラで、葉ノードに含まれる最大のレコード数
• \(\hat{y_a}\) : aを葉ノードのインデックスとして、条件分岐を経てその葉ノードにたどり着いたレコードの予測ラベル

1. 第一ノードの左の子を\(I_1\)、右の子を\(I_2\)として、\(P_L(I_1)G(I_{2}) +P_R(I_1)G(I_{2})\)という値がもっとも大きくなるような条件を全探索で探し、その条件でノードを分割する。根ノードが葉ノードでなくなったので、 \(N_{leaf} = N_{leaf} - \{1\} + \{2,3\}\)のようにして、葉ノードの集合を更新する
2. \(r = \mathrm{arg}\mathrm{max}_{a \in N_{}leaf} f(I_a)\)と定義する。つまり、葉ノードの中で、f(葉ノード)の値が最大になるような葉ノードのインデックス。\(f(I_a)\)を計算するとき、全ての条件での不純度を求めるので、葉ノードに対して、その葉の\(f(I_a)\)を記憶しておくことで、計算量を削減できる
3. ここで新しく葉ノード\(I_{n+1},I_{n+2}\)を作成する。これは\(I_r\)の子で、\(N_{leaf} = N_{leaf} - \{r\}+ \{n+1, n+2\}\)のように葉ノードを更新する
4. もし、 \(max_{a \in N_{leaf}} |I_r| <= N_{min}\)を満たしたとき、5.を実行する。満たしていないとき、2.から4.までを繰り返し実行する
5. 各葉ノードに対して、予測ラベルを以下のよう設定する。つまり葉ノードにおいて、もっと多いクラスラベルを予測値とする \[a \in N_{leaf}, \quad \hat{y_a} = \mathrm{argmax}_{y \in C} P(y|I_a)\]

    
#!/usr/bin/env python
# coding: utf-8

# In[1]:


# ライブラリのインポート
get_ipython().run_line_magic('matplotlib', 'inline')
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import graphviz
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error


# In[3]:


import seaborn as sns


# In[4]:


from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
df =  sns.load_dataset('iris')


# In[5]:


df


# In[6]:


X = df.drop(['species'], axis=1)
y = df['species']


# In[11]:


X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, shuffle=True, random_state=0)

classifier = DecisionTreeClassifier(random_state=42,  max_depth=3, min_samples_leaf=1)
classifier.fit(X_train, y_train)


# In[12]:


from sklearn import tree
dot_data = tree.export_graphviz(classifier, out_file=None,
                                feature_names=X.columns, 
                                class_names=classifier.classes_,
                                filled=True, rounded=True)

graphviz.Source(dot_data, format='png')


# In[13]:


y_pred = classifier.predict(X_test)
accuracy = accuracy_score(y_test, y_pred)
print(accuracy)