導入

機械学習案件を獲得に向けてkaggleのメダルを獲ることを目標として機械学習チームを発足し、kaggleに挑戦しています。その中で、kaggleでよく使われる機械学習関連の理論について理解し、それをアウトプットしようということになったので、理論についてしっかりと理解した記事内容を残すことにします。

注意

本記事は独学での理解をアウトプットしたもので理論の理解が正しいことは保証できません。もし誤りがあればコメントや訂正PRを投げていただけると幸いです。

対象読者

• 決定木の作成手順を具体的に理解したい人
• 決定木作成に用いられる数学的理論について理解したい人

決定木を理解する

決定木（分類木と回帰木）の作成例を用いて、決定木の作成手順と数学的理論について解説をします。

前提知識

• 分類木（Classification）：データが属するクラスを特定するための決定木
  • メールがスパムかどうかの判断、病気の診断、画像に映る物体の識別 etc
• 回帰木（Regression）：連続値の出力を予測をするための決定木
  • 住宅価格、気温、株価などの予測 etc
• 情報ゲイン（Informatino Gain）：分類木を作成する際に、なるべくノード数が少なくするために使用する指標

分類木の作成例

データセット

下記のデータセットを基に分類木を作成する。属性は「性別」「年齢」「薬物」「犯罪歴」の4つで、実刑カラムの値を目的変数とする。

分類木は複数パターン作成できてしまう

上記のデータセットを使用すると、下記のように複数の決定木を作成することができる。
どちらの決定木も、上記のデータセットに対する目的変数は同じ値となる。

しかし、未知のデータに対しては異なる結果を出力してしまう。
例えば、「女性，老人，シンナー，初犯」というデータに対しては、決定木１だとNo、決定木2だとYesという値になる。

このように、複数の決定木が作成される場合、「最も適切な決定木はどれか？」を考える必要がある。
その際に考慮するのが、「最も有りそうな仮説は、すべての観測に無矛盾な仮説の中で最も簡潔なものである」という原則（オッカムの剃刀）である。
この原則に従うと、最も単純な決定木を求める必要がある。

最も単純な分類木の求め方

とはいえ、すべての決定木のパターンを作成し、その中で最も簡潔な決定木を選択するのは、現実的ではない。（属性が増えれば増えるほど計算量的に困難になるため）

したがって、分類木を作成するにあたり、「全属性の中で、最も識別力が高いものを選び、それを根にする」という方法をとる。ここでいう「識別力」とは、「ある属性がどれだけ効果的にデータセットを異なるクラスに分類できるかという能力」のことである。この識別力のことを「情報ゲイン」という。

情報ゲインは、「特定の属性でデータセットを分類した際に、エントロピー（Entropy）がどの程度減少したか？」を表す指標でもある。

エントロピーとは、物事の不確実性を表す指標のこと。エントロピーの値が大きければ物事の不確実性は大きく、逆も然りである。

したがって、「ある属性の情報ゲインが大きい = ある属性によるエントロピーの減少量が大きい = ある属性によって不確実性が大きく減る = 根に適している」という考え方をする。

エントロピーの算出方法

エントロピー$I$は下記の式で算出できる。
このとき、$n$は事象の個数、$P_i$はある事象における確率を表す。

I(P_1, ... , P_n) = \sum_{i=1}^{n}P_i \log_2 \frac{1}{P_i} = -\sum_{i=1}^{n}P_i \log_2 P_i \tag{1}

ちなみに、$n$個の事象がある場合のエントロピー$I$の値の範囲は下記となる。

0 \leqq I \leqq \log_2 n \tag{2}

例えば、コインを投げた際のエントロピーを算出すると、
事象の個数は表と裏のみなので$n=2$、表・裏となる確率はそれぞれ$1/2$なので、下記の計算により$1$となる。

I(1/2,1/2) = \frac{1}{2} \log_2 2 +  \frac{1}{2} \log_2 2 = 1 \tag{3}

また、式$(2)$より、この場合のエントロピーの最大値は、$\log_2 n$に$n=2$を代入して$1$となる。
つまり、コイン投げにおいてはエントロピーが最大となっているおり、不確実性が最大であるということである。これは、裏または表が出る確率が等しく、どちらの結果も同じくらい予測不可能であることを意味している。

ちなみに、今回のデータセットのように、「Yes」が$p$個、「No」が$n$個の場合、Yesとなる確率を$P_1$、Noとなる確率を$P_2$とすると、式$(1)$は下記のように一般化できる。

I(P_1,P_2) = \frac{p}{p+n} \log_2 \frac{p+n}{p} + \frac{n}{p+n} \log_2 \frac{p+n}{n}  \tag{4}

分類木の作成手順

上記を踏まえて、分類木を作成する手順は以下の通りである。
①データセットのエントロピーを算出する。
②各属性のエントロピーを算出する。
③各属性の情報ゲインを算出（②-①）し、最も大きい情報ゲインを持つ属性を根とする。
④①~③を繰り返す。

• ①データセットのエントロピーを算出する。

データセットより、「Yes」が$7$個、「No」が$3$個なので、式$(4)$より、

I(7/10, 3/10) = \frac{7}{10} \log_2 \frac{10}{7} + \frac{3}{10} \log_2 \frac{10}{3} = 0.881 \tag{5}

• ②各属性のエントロピーを算出する。
  例として、属性が薬物の場合のエントロピーを算出する。
  覚醒剤のデータセット数は3つ。そのうち「Yes」が1個、「No」が2個なので、エントロピーは下記の通り。

I_{覚醒剤} = I(1/3, 2/3) = 0.918  \tag{6}

同様に、$I_{麻薬} = 0.811$、$I_{シンナー} = 0$となる。

属性が薬物の場合のエントロピーは、下記のように各薬物のエントロピーの平均（加重平均）から算出する。

I_{薬物} = I_{覚醒剤} \times 3/10 + I_{麻薬} \times 4/10 + I_{シンナー} \times 3/10  = 0.600  \tag{7}

同様の手順で、他の属性のエントロピーを算出してまとめたものが下記の表である。

• ③各属性の情報ゲインを算出する。（②-①）
  式$(5)$と各属性のエントロピーから、情報ゲインを算出する。算出結果をまとめたものが下記の表である。

上述した通り、

「ある属性の情報ゲインが大きい = ある属性によるエントロピーの減少量が大きい = ある属性によって不確実性が大きく減る = 根に適している」という考え方をする。

ため、最も根に適した属性は「犯罪歴」となる。

• ④①~③を繰り返す。
  繰り返した結果、下記が決定木となる。

回帰木の作成例

回帰木のイメージ

回帰木は、既存のデータセットの値が近しいものでグルーピングし、未知の値がどのグループに所属するか？を判定することで予測を行う方法である。

例として、特徴量が「carat」と「y」、目的変数を価格とした場合の回帰木のイメージが下記である。

上記の境界線（赤色）で作成したグループに①~④の番号をふると、作成される回帰木は次のようになる。

未知のデータに対する目的変数の値は、グルーピングされた値の平均値となる。

グループの境界を算出するためには、分散を使用する。

分散とは「データのばらつきの度合い」のことで、分散の値が小さければデータセットが近しい、逆もしかりである。

データセットをグループに分ける境界値は無数に存在するが、最も適切な境界値は、各グループの分散の値が最も小さくなるような値である。（その境界値によって、データのばらつきが最も小さくなる=まとまりがあるということだから）

データセット

下記のデータセットを基に回帰木を作成する。簡単のため、属性は「家のサイズ」の1つで、価格カラムの値を目的変数とする。

分散の算出方法

分散$s^2$は下記によって算出できる。

s^2 = \frac{1}{N} \sum_{i=1}^{N}(x_i - \bar{x})^2 \tag{7}

このとき、$s$：偏差、$N$：データ数、$x_i$：各データの目的変数の値、$\bar{x}$：目的変数の平均値 である。

回帰木の作成手順

上記を踏まえて、分類木を作成する手順は以下の通りである。
①各属性の値から、分割点の候補を洗い出す。
②すべての分割点候補を基にグループを作成し、それぞれのグループで分散を算出する。
③すべてのグループ内の分散を合計し、最小となる分割点を選択する。
④①~③を繰り返す。

• ①各属性の値から、分割点の候補を洗い出す。
  分割点の候補は、各データの値の中間値として「$55$」「$65$」「$75$」「$85$」の4つとする。

• ②すべての分割点候補を基にグループを作成し、それぞれのグループで分散を算出する。
  式$(7)$より、①で洗い出した候補の値で分割した場合の分散を算出する。

(1)$55$で分割する場合
グループ1（$<55$）だと、

分散_1 = \frac{1}{1}(300-300)^2 = 0

グループ2（$55\leq$）だと、

分散_2 = \frac{1}{4}[(350-395)^2+(380-395)^2+(400-395)^2+(450-395)^2]^2 = 1325

合計分散は、$分散_1 + 分散_2 = 1325$となる。

(2)$65$で分割する場合
グループ1（$<65$）だと、 $分散_1 = 625$
グループ2（$65\leq$）だと、$分散_2 = 867$
合計分散は、$分散_1 + 分散_2 = 1492$となる。

(3)$75$で分割する場合
グループ1（$<75$）だと、 $分散_1 = 1089$
グループ2（$75\leq$）だと、$分散_2 = 625$
合計分散は、$分散_1 + 分散_2 = 1714$となる。

(4)$85$で分割する場合
グループ1（$<85$）だと、 $分散_1 = 1419$
グループ2（$85\leq$）だと、$分散_2 = 0$
合計分散は、$分散_1 + 分散_2 = 1419$となる。

• ③すべてのグループ内の分散を合計し、最小となる分割点を選択する。
  ②より、合計分散が最小となるのは、分割点が$55$の場合であることがわかる。

• ④①~③を繰り返す。
  境界線を増やしたい場合、残りのグループに対して、上記の手順を繰り返せば良い。
  ただ、分割点を増やしすぎると過学習になる可能性が高いので、どこまで分割するかは、実際のグラフを眺めてみて判断するらしい。

繰り返さなかった場合、作成される回帰木は以下の通りである。

線形データセットにおける回帰木の精度

• 線形データについては、回帰分析（直線を利用して予測する手法）のほうが精度が高い
• 回帰木は、非線形のデータセットにて本領を発揮する。
• 今回は簡単のため、線形のデータセットを使用した

結び

具体例を用いて、決定木（分類木と回帰木）の作成までの手順を数学的理論を用いて解説してみました。

脚注

• https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/IntelligentInformationProcessing-2005-Note-11.pdf
• https://datawokagaku.com/decision_tree/#Python