決定木とは

/機械学習

決定木とは

決定木とは、分類や意思決定を多段階に繰り返して行う場合、その各段の分岐を階層的に樹形図で表したものです。

分岐の条件を入力変数($x_i$)、分岐の結果を目的変数($t_j$)と呼びます。ここで、独立変数の数を $m$、独立変数のセット(データ)の数を $n$ とします。

$$t_j=t_j(x_1,x_2,\cdots,x_i,\cdots,x_m) , j=1,2,\cdots,n$$

また、決定木の始点を根ノード、端点を葉ノードと呼びます。決定木が完成した状態では、1つの葉ノードに含まれるの全てのデータは同一の目的変数を持ちます。

この目的変数が数値型か分類型かにより、決定木は2つの種類に分かれます。

種類 目的変数
回帰木 数値型 価格の見積り、所要日数、飛距離など
分類木 分類型 合格/不合格、勝ち/負け、実施/中止など

以下の説明は、分類木に限定し、入力変数を「属性」、目的変数を「クラス」と呼ぶことにします。

学習アルゴリズム

決定木の学習アルゴリズムは以下になります。

  1. 根ノードに対し属性を選択し、子ノードに分岐させる
  2. その子ノードを親ノードとして、次の属性を選択し、子コードに分岐させる
  3. 全ての子ノードが葉ノードとなるまで 2. を繰り返す

決定木の根ノードでは、全てのデータ(全てのクラス)が含まれるため、最も多様性が大きくなりいます。また、葉ノードでは、そこに含まれるデータは全て同じクラスに属するため、最も多様性が小さくなります。

従って、分岐させる際に、多様性を最も下げる属性を選択することが、最も効率の良い学習アルゴリズムを作ることにつながります。決定木の学習アルゴリズムと、それに採用されている多様性の指数は以下になります。

学習アルゴリズム 多様性指数
CART(Classification and Regression Tree) ジニ係数
ID3(Iterative Dichotomiser 3) 情報利得
C4.5 / C5 情報利得比

多様性指数

ウィキペディアに載っている、ゴルフ場の例で、各多様性指数を計算します。

この例では、データの数($n$)は14個、属性の数($m$)は4個で、それぞれ天気(晴・曇・雨)、気温(高・中・低)、湿度(高・中)、風(強・弱)、クラスは 「○:実施」または「 ×:中止」です。

ジニ係数

ジニ係数とは、経済の分野で所得格差を表すために使われていますが、多様性指標では、任意の2つのデータが異なるクラスに属する確率として解釈することができます。

ゴルフの例では、2つのデータを任意に選択して「○×」または「×○」になる確率がデータ集合の多様性を表すと考えます。「○」になる確率を $P_\circ$、「×」になる確率を $P_\times$ とすると、ジニ係数($G$)は以下で表されます。

$$G=1-(P_\circ^2+P_\times^2)=2P_\circ(1-P_\circ)$$

根ノードのジニ係数(G_0)は、「○」は9個、「×」が5個であり、$P_\circ=9/14$、$P_\times=5/14$ であるため以下になります。

$$G_0=1-\Big(\frac{9^2}{14^2}+\frac{5^2}{14^2}\Big)\cong0.459$$

情報利得

ID3の場合は多様性をエントロピー($H$)で表し、エントロピーの変化分が情報利得となります。エントロピーは、事象の発生確率($p_i$)により以下で定義されます。

$$H=-\sum_ip_i\log_2{p_i}$$

ゴルフの例では、根ノードのエントロピー(H_0)は、「○」は9個、「×」が5個であり、$p_\circ=9/14$、$p_\times=5/14$ であるため以下になります。

$$H_0=-\frac{9}{14}\log_2{\frac{9}{14}}-\frac{5}{14}\log_2{\frac{5}{14}}\cong0.940$$

分岐後のエントロピーを $H_1$ とすると、情報利得($I$)は以下で求められます。この情報利得を最大にする属性を選択することが重要です。

$$I=H_0-H_1$$

ゴルフの例を使って、天気で分岐した場合のエントロピー($H_1$)を求めます。まず、晴・曇・雨それぞれのエントロピーは、

  • 晴(×××○○):$H_{11}=-\frac{2}{5}\log_2{\frac{2}{5}}-\frac{3}{5}\log_2{\frac{3}{5}}\cong0.971$
  • 曇(○○○○):$H_{12}=-\frac{4}{4}\log_2{\frac{4}{4}}-\frac{0}{4}\log_2{\frac{0}{4}}=0$
  • 雨(○○×○×):$H_{13}=-\frac{3}{5}\log_2{\frac{3}{5}}-\frac{2}{5}\log_2{\frac{2}{5}}\cong0.971$

であり、全体のエントロピーはこの平均で求められます。

$$H_1=\frac{5}{14}H_{11}+\frac{4}{14}H_{12}+\frac{5}{14}H_{13}\cong0.693$$

 

情報・応用数学
リターン&リスク、ポートフォリオ理論、効率的フロンティア、資本資産価格モデル、先物取引、スワップ取引、ゲーム理論、ナッシュ均衡
数理の散策路
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

Wikipedia

 

タイトルとURLをコピーしました