3章その9 階層的クラスタを作成

単語出現回数のリストを要素(vec)に持つ2分木ノードbiclusterをつなぎあわせて、p.36で解説されている内容が近いblog同士の階層的クラスタを作る。

距離の計算は関数ポインタになっていたので、Object#method関数を使って http://www.ruby-lang.org/ja/man/html/Method.html self.method(distance).call()した。

p.39より、cluster.rbにhcluster関数を追加
http://www.bitbucket.org/shokai/collective-intelligence-study/src/82884830d372/03/clusters.rb

  # 階層的クラスタを作る
  def hcluster(rows, distance=:pearson)
    distances = Hash.new
    currentclustid = -1
    
    # クラスタは最初は行たち
    clust = Array.new
    for i in 0...rows.length
      c = Bicluster.new(rows[i])
      c.id = i
      clust.push(c)
    end
    
    while clust.length > 1
      lowestpair = [0,1]
      closest = self.method(distance).call(clust[0].vec, clust[1].vec)
      # すべての組をループし、もっとも距離の近い組を探す
      for i in 0...clust.length
        for j in i+1...clust.length
          # 距離をキャッシュしてない時、新しく計算する
          if !distances.key?([clust[i].id, clust[j].id]) # hashのkeyとして配列を使う
            distances[[clust[i].id, clust[j].id]] = self.method(distance).call(clust[i].vec, clust[j].vec)
          end
          
          d = distances[[clust[i].id, clust[j].id]]
          if d < closest
            closest = d
            lowestpair = [i,j]
          end
        end
      end
      
      # 2つのクラスタの平均を計算する
      mergevec = Array.new
      for i in 0...clust[0].vec.length
        m = (clust[lowestpair[0]].vec[i] + clust[lowestpair[1]].vec[i])/2.0
        mergevec.push(m)
      end
      
      # 新たなクラスタを作る
      newcluster = Bicluster.new(mergevec, clust[lowestpair[0]], clust[lowestpair[1]], closest, currentclustid)
      
      # 元のセットではないクラスタのIDは負にする
      currentclustid -= 1
      clust.delete_at(lowestpair[1])
      clust.delete_at(lowestpair[0])
      clust.push(newcluster)
    end
    return clust[0]
  end

動くか試す

#!/opt/local/bin/ruby

require 'rubygems'
require 'pp'
require 'clusters.rb'

cs = Clusters.new
blognames,words,data = cs.readline('myblogdata.txt')

clust = cs.hcluster(data)
pp clust

clustの中身は5万行ぐらいある

#<Bicluster:0x16a8d98
 @distance=1.01344976546645,
 @id=-96,
 @left=
  #<Bicluster:0x118f5dc
   @distance=0.942133193351032,
   @id=-92,
   @left=
    #<Bicluster:0x6ecf80
     @distance=0.0,
     @id=17,
     @left=nil,
     @right=nil,
     @vec=
      [0,
       0,
       0,
       1,
       0,
       2,
       0,
       0,
       1,
       1,
       10,
       0,
       0,
       0,

長いので略