Ruby《で》決定木（ID3）

　周りでにわかに帰納論理プログラミングが熱いのです。おそらくこの世界の王道は述語論理の世界を実装した言語である pｒolog(Programming in Logic) や、帰納論理プログラミングシステムの progol なわけですが、自分の興味はちょっと脇道にある決定木と呼ばれる手法にあります。

◆決定木ってなに？

　決定木は学習データに潜む法則を木の形に整理する手法です。この場合の木とは質問の分岐を表す構造で、

例えば、

　卵生で恒温の場合は鳥類である。

と言った場合に、鳥類にたどり着くまでの過程に、発生形態（卵生）、体温（恒温）、の質問が存在すると考えられます。それぞれに卵生、恒温と答えると鳥類にたどり着きます。同様に色々な質問を組み合わせることによって爬虫類や哺乳類の尤もらしい説明ができるわけです。

　このような質問の組み合わで分岐を作るのですが、その構造を描くと木を逆さまにしたように見えることから木構造と呼ばれます。

(出典：Wikipedia)

　決定木のアルゴリズムは学習データから上記のような構造を導き出すことができるわけです。大量の整理のつかないデータから法則を見つけだしたり、新たに発生した未知のデータを妥当なクラスに分類することができるのです。

◆実装してみる

　一般的にはデータマイニングのソフト（こんなの）を使ったりするのですが、内容が面白いので少し勉強してみることにしました。この世界で提唱されているアルゴリズムは、ID3(Iterative Dichotomizer 3),C4.5(C5.0),CART(Classification and Regression Tree), CHAID(Chi-squared Automatic Interaction Detector),QUEST(Quick，Unbiased，Efficient， Statistivcal Tree)などがあります。

　いろいろあって目移りしますが、今回はWikipediaにも計算例が紹介されているID3をRubyで実装してみることにしました。学習集合もWikipediaに掲載されている例を使いました。

class ID3
  
  def initialize
    # 学習集合
    tset = [
      {:name=>:penguin,:a1=>:carnivore,:a2=>:egg,:a3=>:warm_blooded,:category=>:birds},
      {:name=>:lion,:a1=>:carnivore,:a2=>:viviparous,:a3=>:warm_blooded,:category=>:mammalia},
      {:name=>:cow,:a1=>:herbivory,:a2=>:viviparous,:a3=>:warm_blooded,:category=>:mammalia},
      {:name=>:lizard,:a1=>:carnivore,:a2=>:egg,:a3=>:cold_blooded,:category=>:reptilian},
      {:name=>:paddybird,:a1=>:herbivory,:a2=>:egg,:a3=>:warm_blooded,:category=>:birds}
    ]
    # 学習集合の平均情報量を計算
    @i_t = info(tset)
    puts "info(t)=#{@i_t}"
    # 決定木の作成
    p exec(tset,[:a1,:a2,:a3])
  end
  
  # ID3のアルゴリズムにより決定木を作成します。
  # 学習集合 s
  # 質問カラムのリスト xlist
  def exec(s,xlist)
    h=idx_hash(s,:category)
    # カテゴリーが1つになったら
    if h.length==1
      return [h.keys[0]]
    end
    # 質問が1つだったら
    if xlist.length==1
      h=idx_hash(s,xlist[0])
      ret=[xlist[0],{}]
      h.each_pair { |k,v|
        ret[1][k]=idx_hash(v,:category).keys
      }
      return ret
    end
    g=gain(s,xlist)
    # 利得の高い質問の部分集合を作る
    ns=idx_hash(s,g[0][0])
    ret=[g[0][0],{}]
    # 次の質問リストから既に行った質問を削除する
    xlist.delete(g[0][0])
    ns.each_pair { |k,v|  
      ret[1][k]=exec(v,xlist)
    }
    ret
  end
   
  # 集合 s の cloum の値をキーとする部分集合のハッシュを返します。 
  def idx_hash(s,cloum)
    rhash={}
    s.each{|item|
      if rhash.has_key?(item[cloum])
        rhash[item[cloum]] << item
      else
        rhash[item[cloum]] = [item]
      end
    }
    rhash
  end

  # 集合 s の平均情報量を返します。
  def info(s)
    chash=idx_hash(s,:category)
    i=0
    #puts "chash=#{chash.length}"
    chash.each_pair { |k,v|
      #puts "#{k} #{v.length} #{s.length}"
      p = v.length.to_f/s.length
      i += -p * Math.log(p)/Math.log(3)
    }
    i
  end
  
  # 質問カラム x に対する利得のリストを返します。
  # s 対象の集合
  # xlist 質問カラムのリスト
  # 戻り値
  # ex.[[:a2, 0.6126016192893442], [:a3, 0.45548591500359525], [:a1, 0.10785781643217829]]
  def gain(s,xlist)
    g={}
    xlist.each{|x|
      h = idx_hash(s,x)
      ix_t=0
      h.each_pair { |k,v|
        ix_t+=v.length.to_f/s.length*info(v)
      }
      g[x]=@i_t-ix_t
      #puts "#{x}=#{g[x]}"
    }
    g.sort{|a,b| b[1]<=>a[1]}
  end
  
end

ID3.new

　実行結果はこんな感じになります。

info(t)=0.9602297178607612
[:a2, {:egg=>[:a3, {:warm_blooded=>[:birds], :cold_blooded=>[:reptilian]}], :viviparous=>[:mammalia]}]

　決定木は配列とハッシュの組み合わせで表現されます。ノードが質問で枝が質問の回答、葉が分類結果となります。

　配列の第一要素に質問のカラム名、第二要素は分岐先のハッシュになります。ハッシュのキーは枝を表現し、値にノード配列を所有します。結果をよーく見るとWikipediaの図と同じになっていることがわかります。

◆Ruby《で》決定木

　6月の行われたRuby会議2008で東大の増原英彦先生による「Ruby《を》教えてるんじゃない、Ruby《で》教えてるんだってば」のセッションがありましたね。

　Rubyは配列やハッシュの記述、操作方法が簡潔で、言語の部品を操作することが目的の記述が少なくなるように設計されていると感じられます。つまり、Rubyで作るとコード量が少ないのです。その意味で、何か考えながらプログラムを作る時に本質であるアルゴリズムに集中することができるわけです。Ruby《で》教えたくなる気持ちがちょっと分ったような！？（とりあえず実行速度のことは目をつむっておりますですhi）

◆アルゴリズムを感じる

　Wikipediaを読みながらコードを書くことはできるわけですが、それだけではID3を十分楽しんだとは言えない気がします。少しだけ中身を感じてみたいと思いました。

　このアルゴリズムには難しそうな式が登場するのですが、本質は平均情報量（情報エントロピー）に注目したことだと考えられます。エントロピーとは、熱力学の第二法則に登場する常に増大するアレです。情報の立場からの感覚的な理解は、ある集合が取りうる状態が不確定であるほど大きな値になる、です。つまり、答えが一意に決まらず色々な種類存在する場合は大きな値となります。エントロピーの式は状態が全て同じ確率を示す時に最大を示します。

　ID3は決定木の分岐を決めるルールとしてこの性質を利用しました。ある質問をした結果エントロピーが低くかった。そして、質問による分岐結果の量が少なかったものから優先的に採用していく考え方です。Wikipediaには期待値が最大と書かれています。これは、期待値を求める式で、学習集合全体のエントロピーから質問結果のエントロピーが引かれるために、最大と表現されています。真意はエントロピーが低い物を選ぶと理解することが自然と思います。

　ID3の改良版はC4.5,C5.0と続きます。時間があればこちらも見ていきたいと思いつつ、今回はこの辺でお開きにします。
Latest update at 2008/08/02