機械学習の勉強として、ID3アルゴリズムにより決定木を生成するプログラムを書いてみました。

ID3 - Wikipedia

ID3アルゴリズムについて軽く説明します。例えば何らかの調査を行って得た以下のデータを分類したいとします。

名前 髪の色 身長 体重 ローションを使用したか 日焼けしたか
Sarah ブロンド 平均 軽い していない した
Dana ブロンド 高い 平均 した していない
Alex 低い 平均 した していない
Annie ブロンド 低い 平均 していない した
Emily 平均 重い していない した
Pete 高い 重い していない していない
John 平均 重い していない していない
Katie ブロンド 低い 軽い した していない


これらのデータから、今回は「日焼けしたかどうか」を特定するための決定木を作ります。

決定木は木構造をしており、各ノードには質問が書かれており、それを辿っていくことで最終的な結果にたどり着くことができます。よくある「あなたにおすすめの○○」みたいなフローチャート的なやつですね。

例えば、上のデータから人物を特定するには

髪の色は? -ブロンド-> 体重は? -軽い-> 身長は? -平均-> あなたはSarah!

というような道筋をたどっていけばいいことがわかります。


このときの質問の順番についてですが、どのように質問を選べば効率よく結果を特定できるかを考えるために、エントロピーという概念を用います。

Entropy(S) := -\sum_{x \in S}x\log _2x

このエントロピーを用いて、データの集合Dを複数の互いに交わらない部分集合C_1, C_2, ..., C_nに分割(\bigcup C_i = Dということ)した際、この分割の乱雑さ(Disorder)を以下の式で決定します。

Disorder(D, C) := Entropy(\{\frac{|C_i|}{|D|} | i = 1, ..., n \})

以後、このような分割を「分類」と呼びます。ちょうど上で例示したデータを「髪の色」とか「ローションを使用したか」とかのパラメータごとに分類する感じですね。

ここで、各分類C_iをさらに最終的な結果として扱われるパラメータ(今回は「日焼けしたか」)で分類します。
結果となるパラメータがN種類の値を取れるとして、C^i_j (j = 1, ..., N)C_iをさらに結果となるパラメータで分類したものとします。

このとき、各C_iの乱雑さの平均を、以下のように求めます。

AvgDisorder(D, C) := \sum_{i = 1}^{n}Disorder(C_i, C^i)\frac{|C_i|}{|D|}

ID3アルゴリズムでは、この値が小くなる分類ほどよい分類であるとします。

例えば、上のデータを髪の色で分類してみましょう。

髪の色で分類した結果がこちら

名前 髪の色 身長 体重 ローションを使用したか 日焼けしたか
Sarah ブロンド 平均 軽い していない した
Annie ブロンド 低い 平均 していない した
Dana ブロンド 高い 平均 した していない
Katie ブロンド 低い 軽い した していない
Alex 低い 平均 した していない
Pete 高い 重い していない していない
John 平均 重い していない していない
Emily 平均 重い していない した

\[ C^{ブロンド}_{した} = \{ Sarah, Annie \} \] \[ C^{ブロンド}_{していない} = \{ Dana, Katie \} \] \[ C^{茶}_{した} = \{ \} \] \[ C^{茶}_{していない} = \{ Alex, Pete, John \} \] \[ C^{赤}_{した} = \{ Emily \} \] \[ C^{赤}_{していない} = \{\} \]

それぞれの乱雑さは、 \[ Disorder(C_{ブロンド}, C^{ブロンド}) = -\frac{2}{4}\log _2\frac{2}{4} - \frac{2}{4}\log _2\frac{2}{4} = 2 \] \[ Disorder(C_{茶}, C^{茶}) = -\frac{0}{3}\log _2\frac{0}{3} - \frac{3}{3}\log _2\frac{3}{3} = 0 \] \[ Disorder(C_{赤}, C^{赤}) = \frac{1}{1}\log _2\frac{1}{1} - \frac{0}{1}\log _2\frac{0}{1} = 0 \]  \log 0は未定義ですが、0がかかっているのでとりあえず0として扱います。

したがって、髪の色による分類の平均の乱雑さは以下のようになります。

 AvgDisorder(D, C) = \frac{4}{8} \times 2 + \frac{3}{8} \times 0 + \frac{1}{8} \times 0 = 1

同様に他のパラメータによる分類の平均の乱雑さも求めていきます。

このように平均の乱雑さを求めて行った結果、最終的に髪の色で分類すると最も平均の乱雑さが小さくなることがわかります。

そこで、日焼けしたかどうかを同定するための最初の質問を「髪の色」にします。

また、こうして出来た分類分け \( C_{ブロンド}, C_{茶}, C_{赤} \) を、残りのパラメータを使って同様にさらに細かく分類していきます。

こうして、これ以上分類できない所まで分類しきったものが、求める決定木となります。

実際にID3アルゴリズムを用いて分類を行うプログラムをHaskellで書いてみました。

gomicode/DTree.hs at master · monamonamonad/gomicode · GitHub

先ほどのデータは上のコードの下に以下のように定義されています。

data SunBurn = SunBurn {
    name :: String
  , hairColor :: HairColor
  , height :: HML
  , weight :: HML
  , lotionUsed :: Bool
  , sunBurned :: Bool
  } deriving (Eq, Show, Data, Typeable)

-- 髪の色
data HairColor = Blonde | Brown | Red
  deriving (Eq, Show, Ord, Data, Typeable)

-- 3段階(High / Mid / Low)
data HML = High | Mid | Low
  deriving (Eq, Show, Ord, Data, Typeable)

example = [
    SunBurn "Sarah" Blonde Mid  Low  False True
  , SunBurn "Dana"  Blonde High Mid  True  False
  , SunBurn "Alex"  Brown  Low  Mid  True  False
  , SunBurn "Annie" Blonde Low  Mid  False True
  , SunBurn "Emily" Red    Mid  High False True
  , SunBurn "Pete"  Brown  High High False False
  , SunBurn "John"  Brown  Mid  High False False
  , SunBurn "Katie" Blonde Low  Low  True  False
  ]

instance FiniteFields SunBurn where
  type FieldTypes SunBurn = [String, HairColor, HML, Bool] -- SunBurnのフィールドの型の候補
_name:_hairColor:_height:_weight:_lotionUsed:_sunBurned:_
  = selectors $ SunBurn u u u u u u where u = undefined

下4行はSunBurn型を使って決定木を出力するために必要なものの定義です。
このコードはData.Typeable, Data.Dataを利用してかなり一般的に作られているため、ユーザの定義した独自の型についてもFieldTypes tにフィールドの型の候補を指定するだけで、自動的に各フィールドへのアクセサ(上でいう_name, _hairColor等)が生成され、決定木を構築できるようになっています。

build関数を実行すると、以下のような決定木が出力されます

>>> build [_hairColor, _height, _weight, _lotionUsed] _sunBurned example
DTree (hairColor :: HairColor) [(Blonde,DTree (lotionUsed :: Bool) [(False,DLeaf [SunBurn {name = "Sarah", hairColor = Blonde, height = Mid, weight = Low, lotionUsed = False, sunBurned = True},SunBurn {name = "Annie", hairColor = Blonde, height = Low, weight = Mid, lotionUsed = False, sunBurned = True}]),(True,DLeaf [SunBurn {name = "Dana", hairColor = Blonde, height = High, weight = Mid, lotionUsed = True, sunBurned = False},SunBurn {name = "Katie", hairColor = Blonde, height = Low, weight = Low, lotionUsed = True, sunBurned = False}])]),(Brown,DLeaf [SunBurn {name = "Pete", hairColor = Brown, height = High, weight = High, lotionUsed = False, sunBurned = False},SunBurn {name = "John", hairColor = Brown, height = Mid, weight = High, lotionUsed = False, sunBurned = False},SunBurn {name = "Alex", hairColor = Brown, height = Low, weight = Mid, lotionUsed = True, sunBurned = False}]),(Red,DLeaf [SunBurn {name = "Emily", hairColor = Red, height = Mid, weight = High, lotionUsed = False, sunBurned = True}])]

図にしてみると以下のような感じになります。

f:id:cloudear8:20160613204242p:plain