3章おまけ日本語blogの階層的クラスタリング

日本語データを扱うなら、テキストファイルじゃなくてちゃんとRDBに保存した方が良いですね。区切り文字とかが面倒をかけてきて、今回はクロールしてきたデータの一部を手動で修正してしまった。

できた。→大きいサイズ http://www.flickr.com/photos/shokai/3028846281/sizes/o/

英語blogはHTML除去してsplit(/[^A-Z^a-z]+/)で分割すれば単語が取り出せたが、日本語blogはMeCabで形態素解析し、名詞だけを取り出すようにした。

feedリストはLDRの自分のOPML http://reader.livedoor.com/user/shokaishokai からできるだけ日本語で本文が長いblogを手動で選んできた
http://www.bitbucket.org/shokai/collective-intelligence-study/src/1f1d1ed30fe5/03/feedlistjp.txt
適当に使って下さい

そしてgeneratefeedvector.rbの単語取得部分だけをMeCabで置き換え generatefeedvector-jp.rb として保存
http://www.bitbucket.org/shokai/collective-intelligence-study/src/1f1d1ed30fe5/03/generatefeedvector-jp.rb

#!/usr/local/bin/ruby

require 'rubygems'
require 'simple-rss'
require 'open-uri'
require 'cgi'
require 'pp'
require 'hpricot'
require 'MeCab'
require 'kconv'

class FeedVectorGeneratorJp
  
  # RSSフィードのタイトルと、単語の頻度のディクショナリを返す
  def getwordcounts(url)
    # フィードをパースする
    rss = SimpleRSS.parse(open(url).read)
    wc = Hash.new(0) # 初期値0設定
    
    # 全てのエントリをループする
    rss.items.each{ |item|
      # 本文を読み出す
      summary = item.content if item.content != nil # atomの時
      summary = item.description if item.description != nil # rssの時

      # 単語のリストを取り出す
      words = getwords(item.title + ' ' + summary)
      words.each{ |word|
        wc[word] += 1
      }
    }
    return CGI.unescapeHTML(rss.channel.title.toutf8), wc
  end
  
  def getWordsByKind(node, kind)
    list = Array.new
    while node do
      f = node.feature.split(/,/) 
      if /#{kind}/ =~ f[0]
        list.push(node.surface)
      end
      node = node.next
    end
    return list.uniq
  end

  
  # HTMLからアルファベット小文字のみを抜き出し配列として返す
  def getwords(html)
    # HTMLタグを全て取り除く
    doc = Hpricot(html)
    txt = doc.inner_text
    
    # 単語を取り出す
    mecab = MeCab::Tagger.new('-Ochasen')
    n = mecab.parseToNode( CGI.unescapeHTML(txt.toutf8) )
    # verbs = getWordsByKind(n, '動詞')
    nouns = getWordsByKind(n, '名詞') # 名詞のみ
    return nouns
  end
  
  # Feedから単語頻出表を生成する
  def generate(filename='blogdatajp.txt')
    apcount = Hash.new(0) # それぞれの単語が出現するblogの数
    wordcounts = Hash.new
    feedlist = Array.new
    open('feedlistjp.txt'){ |file|
      file.each{ |line|
        line = line.gsub(/\r|\n/,'') # 改行を削除
        feedlist.push(line)
      }
    }
    
#    feedlist = ['http://www.daito.ws/weblog/atom.xml',
#                'http://www.ok.kmd.keio.ac.jp/feed/',
#                'http://d.hatena.ne.jp/kyoro353/rss',
#                'http://www.uchidayu.net/diary/?feed=rss2',
#                'http://d.hatena.ne.jp/makaronisan/rss']
#
    # feed処理
    feedlist.each{ |feedurl|
      begin
        title, wc = getwordcounts(feedurl)
        wordcounts[title] = wc
        wc.each{ |word, count|
          if count > 1
            apcount[word] += 1
          end
        }
      rescue
        puts 'Failed to parse feed ' + feedurl
      else
        puts 'Success to parse feed ' + feedurl
      end
    }
    
    wordlist = Array.new
    
    apcount.each{ |w,bc|
      frac = Float(bc)/feedlist.length
      if frac > 0.1 && frac < 0.5
        wordlist.push(w)
      end
    }
    
    File.open(filename, 'w'){ |out|
      out.write('Blog')
      
      # 単語リスト出力
      wordlist.each{ |word|
        out.write("\t" + word)
      }
      out.write("\n")
      
      # 単語毎の出現数出力
      wordcounts.each{ |blog, wc|
        out.write(blog)
        wordlist.each{ |word|
          if wc.key?(word)
            out.write("\t" + wc[word].to_s)
          else
            out.write("\t0")
          end
        }
        out.write("\n")
      }
    }
    
  end
  
end

日本語版単語頻出表を作る

>> load 'generatefeedvector-jp.rb'
>> gen = FeedVectorGeneratorJp.new
>> gen.generate
> true
>> gen.generate
Success to parse feed http://rubyist.g.hatena.ne.jp/yuiseki/rss
Failed to parse feed http://moyashi.air-nifty.com/hitori/atom.xml
Success to parse feed http://blog.chabudai.com/atom.xml
Success to parse feed http://design-sub-semi.blogspot.com/feeds/posts/default
Success to parse feed http://d.hatena.ne.jp/next49/rss
Success to parse feed http://www.ruwon.net/feeds/posts/default
Success to parse feed http://shi-sa-0710hiranonaoki.blogspot.com/feeds/posts/default
Success to parse feed http://www.j-tokkyo.com/feed
Success to parse feed http://www.daito.ws/weblog/atom.xml
Success to parse feed http://www.ok.kmd.keio.ac.jp/feed/
Success to parse feed http://d.hatena.ne.jp/kyoro353/rss
Success to parse feed http://www.uchidayu.net/diary/?feed=rss2
Success to parse feed http://d.hatena.ne.jp/makaronisan/rss
Success to parse feed http://blog.huojin.com/index.rdf
Success to parse feed http://www.ok.kmd.keio.ac.jp/ruby/?feed=rss2
Success to parse feed http://twwatcher.blog20.fc2.com/?xml
Success to parse feed http://73714.at.webry.info/rss/index.rdf
Success to parse feed http://www.kagaya.com/?feed=rss2
Success to parse feed http://kamadango.com/atom.xml
Failed to parse feed http://www.ok.kmd.keio.ac.jp/DIY/?feed=rss2
Success to parse feed http://pochigarden.blogspot.com/feeds/posts/default
Failed to parse feed http://generation1986.g.hatena.ne.jp/jj1bdx/rss2
Success to parse feed http://techtalk.jp/atom.xml
Success to parse feed http://blog.progression.jp/feed
Success to parse feed http://web.sfc.keio.ac.jp/~t05907sm/en-pr/atom.xml
Success to parse feed http://hwhack.blogspot.com/feeds/posts/default
Success to parse feed http://makingthingstalkpochi.blogspot.com/feeds/posts/default
Success to parse feed http://xtel.sfc.keio.ac.jp/theory/atom.xml
Success to parse feed http://blogs.yahoo.co.jp/sowaka_chan/rss.xml
（略）

文字化けしていたので

cat blogdatajp.txt > myblogdatajp.txt

したら直ってできたのがこれ http://www.bitbucket.org/shokai/collective-intelligence-study/src/1f1d1ed30fe5/03/myblogdatajp.txt

clusters.rbも、日本語なのでフォントをヒラギノに変更したりした
http://www.bitbucket.org/shokai/collective-intelligence-study/src/1f1d1ed30fe5/03/clusters.rb

#!/usr/bin/ruby

require 'bicluster.rb'
require 'rubygems'
require 'pp'
require 'RMagick'
include Magick

class Clusters

  # 行列の入れ替え
  def rotatematrix(data)
    newdata = Array.new
    # 単語数が多すぎるので100個に制限する
    for i in 0...[100, data[0].length].min
      newrow = Array.new
      for j in 0...data.length
        newrow.push(data[j][i])
      end
      newdata.push(newrow)
    end
    return newdata
  end
  
  # グラフを描く
  def drawdendrogram(clust, labels, imgfile='clusters.png')
    # 高さと幅
    h = getheight(clust) * 20
    w = 1200
    depth = getdepth(clust)
    
    # 幅は固定されているため、適宜縮尺する
    scaling = Float(w-150)/depth
    
    # 白を背景とする新しい画像を作る
    img = Image.new(w,h)
    draw = Draw.new
    draw.stroke('red')
    draw.stroke_width(1)
    draw.line(0, h/2, 10, h/2)
    
    # 最初のノードを描く
    drawnode(draw, clust, 10, (h/2), scaling, labels)
    
    # 描画、保存
    draw.draw(img)
    img.write(imgfile)
    
  end

  def drawnode(draw, clust, x, y, scaling, labels)
    if clust.id < 0
      h1 = getheight(clust.left) * 20
      h2 = getheight(clust.right) * 20
      top = y-(h1+h2)/2
      bottom = y+(h1+h2)/2
      # 直線の長さ
      ll = clust.distance*scaling
      # クラスタから子への垂直な直線
      draw.stroke('red')
      draw.line(x, top+h1/2, x, bottom-h2/2)
      
      # 左側のアイテムへの水平な直線
      draw.line(x, top+h1/2, x+ll, top+h1/2)
      
      # 右側のアイテムへの水平な直線
      draw.line(x, bottom-h2/2, x+ll, bottom-h2/2)
      
      # 左右のノードたちを描く関数を呼び出す
      drawnode(draw, clust.left, x+ll, top+h1/2, scaling, labels)
      drawnode(draw, clust.right, x+ll, bottom-h2/2, scaling, labels)
    else
      # 終点であればアイテムのラベルを描く
      #draw.font = '/Library/Fonts/Arial.ttf'
      draw.font = '/Library/Fonts/ヒラギノ角ゴ Pro W3.otf'
      draw.stroke('transparent')
      draw.fill('black')
      draw.pointsize = 10 # 文字サイズ
      label = labels[clust.id]
      draw.text(x+3, y+4, label) if label != nil
    end
  end
  
  def getdepth(clust)
    # 終端への距離は0.0
    return 0 if clust.left == nil && clust.right == nil
    
    # 枝の距離は二つの方向の大きい方にそれ自身の距離を足したもの
    return [getdepth(clust.left),getdepth(clust.right)].max + clust.distance
  end
  
  def getheight(clust)
    # 終端であれば高さは1にする
    return 1 if clust.left == nil && clust.right == nil
    
    #そうでなければ高さはそれぞれの枝の高さの合計
    return getheight(clust.left) + getheight(clust.right)
  end
  
  
  # 階層型クラスタを出力する
  def printclust(clust,labels=nil,n=0)
    # 階層型レイアウトにするためにインデントする
    n.times do
      print ' '
    end
    if clust.id < 0
      # 負のidはこれが枝である事を示している
      puts '-'
    else
      # 正のidはこれが終端だということを示している
      if labels == nil
        puts clust.id
      else
        puts labels[clust.id]
      end
    end

    # 右と左の枝を表示する
    printclust(clust.left, labels, n+1) if clust.left != nil
    printclust(clust.right, labels, n+1) if clust.right != nil
  end
  
  # 階層的クラスタを作る
  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
  
  # ピアソン相関距離を計算
  def pearson(v1,v2)
    # 単純な合計
    sum1 = 0
    v1.each{ |n|
      sum1 += n
    }
    sum2 = 0
    v2.each{ |n|
      sum2 += n
    }
    
    # 平方の合計
    sum1Sq = 0
    v1.each{ |n|
      sum1Sq += n*n
    }
    sum2Sq = 0
    v2.each{ |n|
      sum2Sq += n*n
    }
    
    # 積の合計
    pSum = 0
    for i in 0...v1.length
      pSum += v1[i]*v2[i]
    end
    
    # ピアソンによるスコアを算出
    num = pSum - (sum1*sum2/v1.length)
    den = Math::sqrt( (sum1Sq-sum1*sum1/v1.length)*(sum2Sq-sum2*sum2/v1.length) )
    return 0 if den == 0
    
    # 今回は特別に、アイテム同士が似ているほど小さい値を返す様にする
    return 1.0-num/den
    
  end
  
  def readline(filename)
    lines = Array.new
    open(filename).each{ |line|
      lines.push(line)
    }
    
    # 最初の行は列のタイトル（単語名）
    colnames = lines[0].strip().split("\t")
    colnames.shift # 最初の1つを捨てる
    
    # blog名と単語数
    rownames = Array.new
    data = Array.new
    lines[1...lines.length].each{ |line|
      tmp = line.strip().split("\t")
      # それぞれの行の最初の列は行の名前（blog名）
      rownames.push(tmp.shift)
      # 行の残りの部分がその行のデータ
      wordcount = Array.new
      tmp.each{ |c|
        wordcount.push(c.to_i)
      }
      data.push(wordcount)
    }

    return rownames,colnames,data
  end
    
end

クラスタリングして、画像に出力する

>> load 'clusters.rb'
>> cs = Clusters.new
>> blognames,words,data = cs.readline('myblogdatajp.txt')
>> clust = cs.hcluster(data)
>> cs.drawdendrogram(clust, blognames, 'myblogclustjp.png')
=> myblogclustjp.png  1200x5980 DirectClass 16-bit 714kb

drawdendrogramするとエラー

ArgumentError: missing text argument
        from /opt/local/lib/ruby/gems/1.8/gems/rmagick-2.7.1/lib/RMagick.rb:573:in `text'
        from ./clusters.rb:80:in `drawnode'
        from ./clusters.rb:71:in `drawnode'
        from ./clusters.rb:70:in `drawnode'
        from ./clusters.rb:43:in `drawdendrogram'
        from (irb):20
        from :0

が出たので、myblogdatajp.txtを見たらSFC学事のフィードなど、タイトルに改行やTAB？が入っているものがあったので適当に削除したらエラーが出なくなった。
おわり。