3章 その15 K平均法でblogをクラスタリング
データ群をK個のクラスタに分けるために、「いちばんしっくり来るK個の重心」を再帰で見つけるK平均法を使う。
このページのインデントわかりづらくてイライラした。
このアルゴリズムは階層的クラスタリングより全然速い。
p.47~48より
clusters.rbにkcluster関数を追加した
http://www.bitbucket.org/shokai/collective-intelligence-study/src/aea87de2da8d/03/clusters.rb
def kcluster(rows, distance=:pearson, k=4) # それぞれのポイントの最小値と最大値を決める ranges = Array.new for i in 0...rows[0].length cols = Array.new for row in rows cols.push(row[i]) end ranges.push([cols.min, cols.max]) end # 重心をランダムにk個配置する clusters = Array.new k.times do tmp = Array.new for i in 0...rows[0].length tmp.push( rand()*(ranges[i].max-ranges[i].min)+ranges[i].min ) end clusters.push(tmp) end # 重心を再計算しながら100回、もしくは変化が無くなるまで移動させる lastmatches = nil for t in 0...100 puts 'Iteration ' + t.to_s bestmatches = Array.new # 空の配列作成 k.times do bestmatches.push(Array.new) end # それぞれの行に対して、もっとも近い重心を探し出す for j in 0...rows.length row = rows[j] bestmatch = 0 for i in 0...k d = self.method(distance).call(clusters[i],row) # 距離計算 bestmatch = i if d < self.method(distance).call(clusters[bestmatch],row) end bestmatches[bestmatch].push(j) end # 結果が前回と同じであれば完了 return bestmatches if bestmatches == lastmatches lastmatches = bestmatches # 重心をそのメンバーの平均に移動する for i in 0...k avgs = Array.new(rows[0].length, 0.0) # 初期値0.0の配列をいくつか作る if bestmatches[i].length > 0 for rowid in bestmatches[i] for m in 0...rows[rowid].length avgs[m] += rows[rowid][m] end end for j in 0...avgs.length avgs[j] /= bestmatches[j].length if bestmatches[j] != nil end clusters[i] = avgs end #return bestmatches # 誤植？ここでreturnすると1回しか計算しない気がする end end end
ピアソン相関距離の計算に要素数1の配列が行く事があったので修正。diffの下の方参照
http://www.bitbucket.org/shokai/collective-intelligence-study/diff/03/clusters.rb?diff2=aea87de2da8d&diff1=1f1d1ed30fe5
p.48より、ピアソン相関距離で計算して10クラスタに分ける
irbで
>> load 'clusters.rb' >> cs = Clusters.new >> blognames,words,data = cs.readline('myblogdata.txt') >> kclust = cs.kcluster(data, :pearson, 10) Iteration 0 Iteration 1 Iteration 2 Iteration 3 Iteration 4 Iteration 5 Iteration 6 => [[0, 1, 2, 7, 8, 9, 22, 25, 29, 35, 57, 72, 78, 79, 82, 90, 94], [5, 14, 16, 24, 30, 39, 47, 48, 58, 69, 73, 75, 80, 87], [10, 46, 62, 68, 74], [93], [6, 12, 15, 23, 27, 31, 36, 38, 49, 55, 56, 59, 65, 66, 67, 71, 77, 86, 95], [4, 11, 33, 34, 45, 52, 63, 84], [17, 20, 21, 28, 42, 44, 50, 53, 54, 64, 81, 88, 89], [3, 18, 26, 41, 60, 61, 83, 91], [13, 19, 32, 37, 40, 43, 51, 70, 76, 92], [85, 96]]
クラスタとしてIDの配列の配列が手に入ったので
それぞれblog名に置き換えて表示してみる
>> for r in kclust[0]; p blognames[r]; end "Micro Persuasion" "Creating Passionate Users" "Kotaku" "SpikedHumor - Today's Videos and Pictures" "Deadspin" "Signal vs. Noise" "Valleywag" "Lifehacker" "Search Engine Roundtable" "we make money not art" "Gizmodo" "Dave Shea's mezzoblue" "Gawker" "456 Berea Street" "Schneier on Security" "TreeHugger" "Seth's Blog" => [0, 1, 2, 7, 8, 9, 22, 25, 29, 35, 57, 72, 78, 79, 82, 90, 94] >> for r in kclust[1]; p blognames[r]; end "The Superficial - Because You're Ugly" "Celebrity gossip juicy celebrity rumors Hollywood gossip blog from Perez Hilton" "NewsBusters.org - Exposing Liberal Media Bias" "The Daily Dish | By Andrew Sullivan" "Power Line" "Hot Air \302\273 Top Picks" "Think Progress" "Daily Kos" "Crooks and Liars" "Wonkette: The D.C. Gossip" "Little Green Footballs" "Slashdot" "Michelle Malkin" "Instapundit.com (v.2)" => [5, 14, 16, 24, 30, 39, 47, 48, 58, 69, 73, 75, 80, 87] >> for r in kclust[2]; p blognames[r]; end "The Blotter" "Eschaton" "ScienceBlogs : Combined Feed" "Cool Hunting" "Giga Omni Media, Inc." => [10, 46, 62, 68, 74]
重心K個の初期配置はランダムなので、毎回微妙に違うクラスタができる
>> kclust = cs.kcluster(data, :pearson, 10) Iteration 0 Iteration 1 Iteration 2 Iteration 3 Iteration 4 => [[35, 42, 44, 50, 54, 88, 89], [5, 6, 12, 13, 15, 19, 27, 31, 32, 36, 37, 38, 40, 43, 49, 51, 55, 56, 65, 66, 67, 70, 71, 74, 76, 77, 85, 86, 92, 95, 96], [14, 16, 24, 30, 39, 47, 48, 58, 61, 69, 73, 87, 91], [26, 60, 75, 83], [3, 8, 10, 18, 41], [23, 59, 80, 93], [7, 21, 28, 46, 52, 53, 62, 64, 81], [4, 11, 33, 34, 45, 63, 68, 84], [17], [0, 1, 2, 9, 20, 22, 25, 29, 57, 72, 78, 79, 82, 90, 94]] >> kclust = cs.kcluster(data, :pearson, 10) Iteration 0 Iteration 1 Iteration 2 Iteration 3 Iteration 4 Iteration 5 Iteration 6 Iteration 7 => [[0, 1, 9, 20, 29, 58, 74, 79, 82, 90, 94], [21, 48, 53, 64, 75, 81, 91], [4], [2, 17, 22, 25, 28, 35, 42, 44, 50, 54, 57, 72, 78, 89], [11, 33, 34, 45, 63, 84], [46, 52, 68], [3, 7, 10, 18, 41, 43, 60, 61, 62, 73], [8], [16, 26, 51, 83, 93], [5, 6, 12, 13, 14, 15, 19, 23, 24, 27, 30, 31, 32, 36, 37, 38, 39, 40, 47, 49, 55, 56, 59, 65, 66, 67, 69, 70, 71, 76, 77, 80, 85, 86, 87, 88, 92, 95, 96]] >> kclust = cs.kcluster(data, :pearson, 10) Iteration 0 Iteration 1 Iteration 2 Iteration 3 Iteration 4 => [[5, 14, 24, 30, 39, 47, 59, 69, 87, 96], [4, 11, 45, 63, 84], [3, 18, 21, 41, 48, 53, 60, 61, 64, 73, 81, 83, 91], [7], [26, 33, 34, 46, 52, 58, 68], [10, 16, 51, 62, 74, 75], [6, 12, 13, 15, 19, 27, 31, 32, 36, 37, 38, 40, 43, 49, 55, 56, 65, 66, 67, 70, 71, 76, 77, 85, 86, 92, 95], [0, 1, 2, 8, 9, 22, 25, 29, 57, 72, 78, 79, 82, 90, 94], [17, 20, 28, 35, 42, 44, 50, 54, 88, 89], [23, 80, 93]]
せっかく日本語の単語頻出表もあるんだから、やってみよう
require 'rubygems' require 'pp' require 'clusters.rb' cs = Clusters.new blognames,words,data = cs.readline('myblogdatajp.txt') kclust = cs.kcluster(data, :pearson, 10) p kclust puts '******' # クラスタ毎に表示 for c in kclust for r in c print blognames[r] + "\n" end puts '******' end
Iteration 0 Iteration 1 Iteration 2 Iteration 3 Iteration 4 Iteration 5 Iteration 6 Iteration 7 [[53, 56, 88, 95, 118, 137, 139, 150, 195, 286], [266, 270], [91, 94, 102, 117, 141, 143, 193, 214, 252, 276], [63, 65, 81, 120, 127, 133, 151, 161, 168, 171, 191, 192, 197, 204, 219, 231, 238, 245, 282], [38, 42, 46, 71, 76, 87, 100, 111, 121, 132, 169, 188, 202, 210, 226, 227, 244, 263, 279, 289], [0, 3, 6, 10, 11, 15, 16, 21, 25, 29, 33, 34, 40, 52, 66, 67, 70, 79, 80, 82, 85, 93, 96, 99, 109, 134, 140, 148, 149, 164, 167, 178, 179, 182, 183, 185, 189, 190, 194, 203, 208, 215, 217, 220, 225, 242, 246, 251, 264, 277, 287, 288, 294], [30, 32, 60, 128, 259, 283, 285], [1, 2, 4, 7, 12, 13, 18, 19, 20, 24, 28, 31, 35, 36, 44, 45, 73, 77, 86, 89, 98, 105, 106, 129, 131, 135, 142, 145, 147, 152, 153, 157, 159, 163, 177, 207, 209, 218, 221, 223, 239, 240, 247, 248, 249, 250, 254, 255, 258, 260, 265, 273, 278], [5, 8, 9, 14, 22, 23, 26, 27, 39, 41, 43, 47, 48, 50, 51, 54, 55, 57, 59, 62, 64, 68, 69, 74, 75, 78, 83, 84, 97, 101, 103, 104, 107, 108, 112, 113, 114, 115, 116, 119, 122, 123, 124, 125, 126, 130, 136, 138, 146, 155, 158, 160, 162, 165, 170, 173, 174, 175, 176, 180, 181, 186, 187, 196, 198, 199, 200, 201, 206, 211, 212, 213, 216, 222, 224, 228, 229, 230, 233, 234, 235, 237, 241, 253, 256, 257, 261, 262, 267, 268, 269, 271, 272, 274, 275, 280, 281, 284, 290, 291, 292, 293, 295], [17, 37, 49, 58, 61, 72, 90, 92, 110, 144, 154, 156, 166, 172, 184, 205, 232, 236, 243]] ****** 安藤日記 CNET Japan ブログネットワーク YouTube Search - oklab 続!!!ノエル吉田のコマネチ!!! 逆転写無縁仏 電子工作推進マガジン エレキジャック Making Things Talk POCHI 平野巨樹のブログ そしてシーサー 奥出研@mixi も〜っと！失言小町 ****** ここにいるよ。めも hwhack ****** Haida's weblog やすこのすこやか日記 POCHI dotdotdot || architettura || design || allestimento || interaction design || milano || dot.dot.dot. сино Блог マスラックス開発メモ ロカポ ブログ sugi.log るをぐ もちろぐ ****** Kirainet.com - A geek in Japan ActionScriptCheatSheet.com 古川 享 ブログ Google LatLong Putting people first scruffy days Imoos _soomipark.com The How 2.0 Blog 古川享ブログ Sunfox AVR Freaks TED | TEDBlog narupeko.jp がらぱごす＊デザイン bulknews.typepad.com dux 2007 Paja 家電 Watch Google Japan Blog ****** PSoC.info PICとインドア・プレーンの世界 FPGAの部屋 Bird-Soft Weblog bkブログ 最速インターフェース研究会 やっぱギークでナイト！ 秘密(の)研究所 aki77の日記 naoyaの日記 Sound Candy hori-uchi.com nyaxtのPC作業ログ polog fladdict.net 3mpの乱筆帳 Fenrir's BLog Rails RecipeBookはてな版 yuisekiのいまさらruby厨日記 KRYM LOG ****** Project MCX : Blog bashlog Chuckの電子工作 Daito Manabe Nakamura-KU ADDICT ゆいせきデジタルネイティブにっき Muibrog YAPAN.org gainer.forum たつをの ChangeLog amayan note サイボウズ・ロボ戦記 たたみラボ masuidrive on rails 王様の耳はロバの耳 hibomaのはてなダイアリー nod::ぶろぐ:RIA::Flex/AIR/Flash 000studio 鯨뺣ꓣ莳뿣莼闣芧볣芹门궰 unknownplace.org blog.nium.jp Piroya Diary www.textfile.org en-pr dotimpact::journalprinter ウノウラボ Unoh Labs collisions.doppac.cc BeInteractive! 3.14 otsune's SnakeOil *Acme::Person::Bonnu 亮 memo TORIGOE DESIGN. doc 西尾泰和のはてなダイアリー jkondoの日記 naoyaのはてなダイアリー バーチャルネット右翼きぬ１４歳 将来が不安 Webプログラミング日記 ひげぽん OSとか作っちゃうかMona- らいおんの隠れ家 ついったーじゃんくしょん 橋本詳解 YappoLogs 8時40分が超えられない ひびろぐ ver.2 Dot Programming ゆーすけべーのナニゲニ 続・みずかみ小屋 Yappo::Hatena::Group::Subtech 100SHIKI 川o・-・）＜2nd life Tech Talk Blog ****** blog.bulknews.net Shibuya.js Saqoosha.net Drkcore 第10回文化庁メディア芸術祭特設ブログ ユビキタスの街角 MorosanSoft ****** SFC 慶應義塾大学 湘南藤沢キャンパス - NEWS 総合政策学部・環境情報学部の学生の方 blog.progression.jp Rimo（リィモ）開発日記 きりかノート MEMO 王様の耳はロバの耳！ EDN Japan 最新情報 fklab.net Rekimoto Lab ほげめも SFC 慶應義塾大学 湘南藤沢キャンパス - NEWS 政策・メディア研究科の学生の方 本屋のほんね VRSJ Special Interest Group on Arts & Entertainment Self-Reference ENGINE pqrs.org: 最近更新したページ Indoor airplane world MAKE: Japan 極楽トンボの独り言 jj1bdx: life beyond Japan TABlog JA ussylog hagylog t07521kk 迷走の果て・Tiny Objects たまごまごごはん 作業日誌（みすみロボット研究所） 8million IDs CoCoNet液晶工房 TechTalk.jp てっく煮ブログ 角谷HTML化計画(without comments) TAKESAKO @ Yet another Cybozu Labs diary | inakage.net GAINER.cc 発声練習 東京あみこタワー 株式会社秋葉原 電子工作&マイコン活用 NextReality moo-pong blog しょこたん☆ぶろぐ 大人なクロログ 折れ日記 Infrared Control Helicopter NyaRuRuの日記 Indoor Airplane Memo EE Times Japan 電音の工場ブログ shunp.com 試行空間 工学ナビの中の人の研究と周辺 はじめての動画処理プログラミング 登 大遊＠筑波大学情報学類の SoftEther VPN 日記 ****** TENORI-ON開発日誌 shingog 5cifen kamadango.com Cirius Lab. ブログ 東浩紀の渦状言論 みかログ すぅこ日報（仮） はるかにおあつらえむき blog.bulkneets.net ぬるり。 O'Reilly Japan - New & Upcomming すｚのAVR研究 世界を小さく使う。フオジンのビジネスブログ。 shirouの現実touhi[ｗｐ] Sue co. MIYADAI.com Blog 渦状言論＠はてな mark-wada blog 橋本所懐 KAGAYA.COM IDEA FARM.S CASE-CAKE-CANT ismlog にぽたん研究所 ノエル吉田のコマネチ！！ 最速転職研究会 松岡正剛の千夜千冊 DIGITAL DJ D Think Lab DSAS開発者の部屋 はかますたいる！【きょろの技的雑記】 森 秀樹::電子工作の日記 uri-log ism*diary 上海編 MiracleFM:721MHz Fight with life -人生との戦い- Myrmecoleon in Paradoxical Library. はてな新館 （ ´∀｀）＜はなざきのBLOG。 doggie's blog 平野耕太ブログ アナルVS外国人 ぼくはまちちゃん！(Hatena) X51.ORG : Occult News for Nerds, Truth is Out There SFC CLIP ゆーすけべー日記 ハンダ付け（半田付け）職人の はんだ付けｂｌｏｇ Synvie開発者のブログ ゆるてむ Yuichiro Katsumoto bricklife.* 更新頻度にあまりにもムラがありすぎるなゆたにっき 京開 シリコンハウスへようこそ ポッチリ村 OL編 Information void element blog メディアテクノロジーラボ ブログ すがメモ/SUGAMEMO にぽたん休憩所 TMデイズ ism*diary ここギコ！ 鿣芿鏯벚뛦莰 革新的発明と製品情報 DESIGN IT! w/LOVE xtel Theory: Design Theory of Ubiquitous Content maku 居酒屋ガレージ日記 どうにもやるきのおきない脱力日記 JP 教員ブログ YOPPA BLOG レゴ マインドストーム NXT 体験ブログ GE Maniacs 川瀬浩介 生きる。 勉強堂雑記 超小型飛行体研究所 やまけんの出張食い倒れ日記 33分日記 おいっ す ぺ Pfirsichverliebt 粋俺一生 もるろぐ ミゾグリブログ 彦龍の憲彦さん world yu-yu- uchidayu.net マイコン工作実験日記 hatayanlog 中辛発言 たこやきのなかみ?U memo 難 民 チ ャ ン プ 題材不新鮮 ＳＦ作家 飛浩隆のweb録 RJBlog 親子で紐解くWeb2.0 実用書には載ってないイラストレーターの使い方。 ザイーガ Matzにっき オンテナ 最新記事リスト 80%日記 インターフェイス批評 中原淳ブログ / critique on interfaces - atsushi nakahara weblog 404 Blog Not Found ****** FAX 橋本商会 はこべにっき# Yusukebe::Tech Rails Agile Cooking Flashマインドマップ開発ブログ Bulknews::Subtech 四谷工作研究所 Haida’s private weblog TokuLog 改めB日記 robo-tan*Diary hoelog IT戦記 spiritlooseのはてなダイアリー べにんじょのやっぽ FLASH 留 Team J 平日更新 日刊“mylo” bits and bytes ******
結果はあんまり階層的クラスタリングの時と変わらない気がするけど、確かにこっちの方が速い。10倍ぐらい速い。
