階層型クラスタの作成
ついに本題に入ります．
今回やること
「集合知プログラミング」の3章で使われている，単語の頻度がファイルになっている"blogdata.txt"を使って，階層型クラスタを作成します．
得られる結果はp.47にあるデンドログラムと同じになるはずですが...
blogdata.txtの読み込み
blogdata.txtはTSV(Tab Separated Values)になっています．
このファイルを読み込み，URLをキーにしたHashに格納します．
def blog_data_from(file) word_counts = {} lines = File.open(file, 'r').readlines # 先頭行を読んで，単語の配列を作る words = lines.shift.chomp.split("\t") words.delete('Blog') lines.each do |line| row = line.chomp.split("\t") url = row.shift counts = row.map { |cell| cell.to_i } word_counts[url] = Hash[*words.zip(counts).flatten] end word_counts end
HierarchicalClusterクラスの作成
階層型クラスタをMy::HierarchicalClusterクラスとして実装します．
以下に全ソースを示します．ちなみにピアソン相関の計算には以前書いたものを使っています．
module My class HierarchicalCluster def initialize(word_counts) @word_counts = word_counts @leafs = word_counts.keys @branches = {} @similarities = {} @tree = Node.new('Root') end attr_reader :tree # 一番距離の近いURL同士を枝葉にしてleafsに戻す # また，作成した枝の平均値を求めてword_countsに保存する # 上記を1つの枝が残るまで，すなわち1つの木になるまで繰り返す def make_tree until @leafs.size == 1 calc_similarities left, right, similarity = closest_leaf update_branches_and_leafs(left, right, similarity) end @tree << @branches[@leafs.to_s] end private # 全ての単語の組み合わせに対して，ピアソン相関値を求める # ただし，格納する際には1から減算して格納する # 相関値のキーはペアを表現するクラス(Pair)で持つ def calc_similarities @leafs.each do |leaf1| @leafs.each do |leaf2| # 自分自身との相関は意味が無いので飛ばす next if leaf1 == leaf2 pair = Pair.new [leaf1, leaf2] unless @similarities[pair] # valuesメソッドを使うと順序が保証されないので，別変数にvalueをそれぞれ格納する leaf1_counts = [] leaf2_counts = [] @word_counts[leaf1].each do |word, count| leaf1_counts << count leaf2_counts << @word_counts[leaf2][word] end @similarities[pair] = 1 - Pearson.calc(leaf1_counts, leaf2_counts) end end end end # 2つの葉がもつword countの平均値を計算する def average_counts_between(leaf1, leaf2) average_counts = {} @word_counts[leaf1].each do |word, count| average_counts[word] = (count + @word_counts[leaf2][word]).quo(2) end average_counts end # leafsに残っている葉同士の相関値から，最も距離の短いものを返す def closest_leaf @similarities.select { |pair, similarity| @leafs.include?(pair.left) and @leafs.include?(pair.right) }.sort_by { |pair, similarity| similarity }.first.flatten end # 枝を作って，branchesに登録する def update_branches_and_leafs(url1, url2, similarity) branch = "#{url1}_#{url2}" # 枝を作る際，葉がURLの場合と枝の場合があるので注意する @branches[branch] = Node.new_branch(branch, (@branches[url1] or url1), (@branches[url2] or url2)) @word_counts[branch] = average_counts_between(url1, url2) @leafs << branch @leafs.delete(url1) @leafs.delete(url2) end end end
ポイント解説
まずはmake_treeを見てください．
ここで全体の処理の流れを記述しています．
def make_tree until @leafs.size == 1 calc_similarities left, right, similarity = closest_leaf update_branches_and_leafs(left, right, similarity) end @tree << @branches[@leafs.to_s] end
@leafsはクラスタ対象が配列になっているもの，と思ってほしいのですが，その@leafsに対して，
それぞれの相関値を計算 (calc_similarities)
最も相関が高い組み合わせを探す (closest_leaf)
クラスタを表現する木に継ぎ足す (update_branches_and_leafs)
という処理を繰り返しています．
しかし，このままではループが終わりません．
そこでupdate_branches_and_leafsメソッドで最も相関の高かったurl1とurl2をbranchとしてくっつけてから削除します．
その代わりに，url1とurl2の枝になっているbranchを挿入します．
def update_branches_and_leafs(url1, url2, similarity) ... @leafs << branch @leafs.delete(url1) @leafs.delete(url2) end
こうすることで@leafsの要素がどんどん減っていき，最終的には1つだけ残るようになります．
階層型クラスタの定義からすれば当たり前なのですが，Pythonですっきりと書かれたソースを読んだ時は感心しました．
メソッドチェーン
今回のテーマとは関係ないのですが，closest_leafを見てください．
少々見づらいかもしれませんが，メソッド呼び出しが途切れずに最後まで続いています，
しかも，連続したメソッド呼び出しで得られた結果を，そのままclosest_leafメソッドの返り値としています．
def closest_leaf @similarities.select { |pair, similarity| @leafs.include?(pair.left) and @leafs.include?(pair.right) }.sort_by { |pair, similarity| similarity }.first.flatten end
このようにメソッドチェーンで記述すると，
やりたい処理を(ほぼ)そのまま書き連ねることができる
余計な一時変数が要らない
という恩恵があり，何でもオブジェクトなRubyだと書いてて気持ちがいいです．
ただ，やりすぎると後で何が書いてあるのか分からなくなるので，程々にしておきましょう．
最後に動作確認
このプログラムを実行すると，デンドログラムがずらずら〜っと表示されます．
require 'pair' require 'node' require 'pearson' cluster = My::HierarchicalCluster.new(blog_data_from('blogdata.txt')) cluster.make_tree cluster.tree.printTree
本に掲載されている結果と同じはずですが，いかがでしょうか?
(とても長いので非表示にしてあります．↓からどうぞ)
Root
+----+
|----> gapingvoid: "cartoons drawn on the back of business cards"
+----+
|----+
| |----> Schneier on Security
| +----> Instapundit.com
+----+
|----> The Blotter
+----+
|----+
| |----> MetaFilter
| +----+
|----> SpikedHumor
+----+
|----> Captain's Quarters
+----+
|----> Michelle Malkin
+----+
|----+
| |----> NewsBusters.org - Exposing Liberal Media Bias
| +----+
|----+
| |----> Crooks and Liars
| +----> Hot Air
+----+
|----> Power Line
+----> Think Progress
+----+
|----> Andrew Sullivan | The Daily Dish
+----+
|----> Little Green Footballs
+----+
|----> Eschaton
+----+
|----> Daily Kos
+----> Talking Points Memo: by Joshua Micah Marshall
+----+
|----> 43 Folders
+----+
|----> TechEBlog
+----+
|----+
| |----> Mashable!
| +----> Signum sine tinnitu--by Guy Kawasaki
+----+
|----+
| |----+
| |----> Slashdot
| +----+
|----> MAKE Magazine
+----> Boing Boing
| +----+
|----+
| |----> Oilman
| +----+
|----> Online Marketing Report
+----+
|----> Treehugger
+----+
|----> SimpleBits
+----+
|----> Cool Hunting
+----+
|----> Steve Pavlina's Personal Development Blog
+----+
|----+
| |----> Pharyngula
| +----> ScienceBlogs : Combined Feed
+----+
|----> BuzzMachine
+----+
|----> Copyblogger
+----+
|----+
| |----> Seth's Blog
| +----> The Viral Garden
+----+
|----+
| |----> Bloggers Blog: Blogging the Blogsphere
| +----+
|----> Sifry's Alerts
+----> ProBlogger Blog Tips
+----+
|----+
| |----> Scobleizer - Tech Geek Blogger
| +----> Valleywag
+----+
|----+
| |----> O'Reilly Radar
| +----> 456 Berea Street
+----+
|----> Lifehacker
+----+
|----> Quick Online Tips
+----+
|----> Publishing 2.0
+----+
|----> Micro Persuasion
+----+
|----> A Consuming Experience (full feed)
+----+
|----> John Battelle's Searchblog
+----+
|----> Search Engine Watch Blog
+----+
|----> Read/WriteWeb
+----+
|----> Official Google Blog
+----+
|----> Search Engine Roundtable
+----+
|----> Google Operating System
+----> Google Blogoscoped
+----+
|----+
| |----+
| |----+
| |----> Blog Maverick
| +----+
|----> Download Squad
+----+
|----> CoolerHeads Prevail
+----+
|----> Joystiq
+----> The Unofficial Apple Weblog (TUAW)
| +----+
|----> Autoblog
+----+
|----> Engadget
+----> TMZ.com
| +----+
|----> Matt Cutts: Gadgets, Google, and SEO
+----+
|----> PaulStamatiou.com
+----+
|----+
| |----> TechCrunch
| +----> GigaOM
+----+
|----+
| |----> Creating Passionate Users
| +----> Techdirt
+----+
|----> Joho the Blog
+----+
|----+
| |----> Jeremy Zawodny's blog
| +----> PerezHilton.com
+----+
|----> Joi Ito's Web
+----+
|----> ongoing
+----+
|----> Joel on Software
+----+
|----+
| |----> we make money not art
| +----+
|----> plasticbag.org
+----+
|----> Signal vs. Noise
+----+
|----> kottke.org
+----+
|----> Neil Gaiman's Journal
+----+
|----+
| |----> The Huffington Post | Raw Feed
| +----+
|----> Wonkette
+----+
|----> Gawker
+----+
|----> Go Fug Yourself
+----> The Superficial - Because You're Ugly
+----+
|----> Deadspin
+----> Gothamist
+----+
|----> Kotaku
+----> Gizmodo
+----+
|----> Shoemoney - Skills to pay the bills
+----+
|----> flagrantdisregard
+----+
|----> WWdN: In Exile
+----+
|----> Derek Powazek
+----+
|----> lifehack.org
+----> Dave Shea's mezzoblue
+----+
|----> Wired News: Top Stories
+----+
|----> Bloglines | News
+----> Topix.net Weblog
