Scalaで集合知プログラミング その13
Scala de 集合知プログラミングの第３章を続けていきますよ(´・ω・｀)
今回は前回に引き続き階層的クラスタリングをやっていきますデス
階層的クラスタリング
前回までにはクラスタリングのための準備として以下の４項目を行って来ました
なので今回はこれらの定義を利用して実際のクラスタリングを行っていきたいと思います(｀・ω・´)
それではPython de クラスタリング
まずはPythonコードを写経して、実際に階層的クラスタリングを行っていきます(｀・ω・´)
具体的な手順としては全部の要素を比較→一番類似度の高いペアをグループ化、を延々と繰り返していくだけです…けっこう力技ですな(´・ω・｀)
# clusters.pyに追記します # クラスタのグループ化処理を定義します def hcluster(rows, distance=pearson): distances = {} currentclustid = -1 # 各行を初期クラスタとして定義 clust = [bicluster(rows[i], id = i) for i in range(len(rows))] # クラスタリングの処理を開始 while 1 < len(clust): # 探索条件の初期値として # クラスタ内の0番目と1番目が最も近いペアと仮定する lowestpair = (0, 1) closest = distance(clust[0].vec, clust[1].vec) # 全ての組をループして最も距離が近い組を探索 for i in range(len(clust)): # 頭から2つ取り出して比較開始 for j in range(i + 1, len(clust)): # 計算した距離をキャッシュして # 存在する場合はソレを使用する if (clust[i].id, clust[j].id) not in distances: distances[(clust[i].id, clust[j].id)] = distance(clust[i].vec, clust[j].vec) d = distances[(clust[i].id, clust[j].id)] # ピックアップした2つのペアの類似度が最も大きければ # 最近傍のペアとして保存 if d < closest: closest = d lowestpair = (i, j) # 最近傍のペアの各ベクトル要素の平均値を取得 mergevec = [ (clust[lowestpair[0]].vec[i] + clust[lowestpair[1]].vec[i]) / 2.0 for i in range(len(clust[0].vec))] # 新たなクラスたの作成 newcluster = bicluster(mergevec, left=clust[lowestpair[0]], right=clust[lowestpair[1]], distance=closest, id=currentclustid) # 新しくつくられたクラスタのIDは負の数として管理する # カウントダウン（負の数的にインクリメント） currentclustid -= 1 # 統合元のクラスタを計算用クラスタ群から削除 del clust[lowestpair[1]] del clust[lowestpair[0]] # 統合先クラスタを計算用クラスタ群に追加 clust.append(newcluster) return clust[0]
とりあえず実行してみましょうかね(´・ω・｀)
# モジュールをインポートします >>> import cluster # データファイルを読み込んで各種データを取得します >>> blognames, words, data = cluster.readfile('blogdata.txt') # クラスタリングを行います >>> clust = cluster.hcluster(data) # とりあえず何かはできました >>> clust <cluster.bicluster instance at 0x9c8aecc>
とりあえずクラスタリングできたっぽい雰囲気です(´・ω・｀)
Pythonクラスタリングの結果表示
計算されたクラスタ群はオブジェクトでしか確認できないので、生成されたクラスタ群を確認するための簡易表示メソッドを用意してやることにします(´・ω・｀)
# クラスタリングの結果を確認表示する処理 # 再帰的に下にさかのぼって行きます def printclust(clust, labels=None, n=0): # 階層表示するためのインデントを出力 for i in range(n): # 改行しない場合は,を指定 print ' ', # 負のidは作成したグループなので枝の途中 if clust.id < 0: print '-' # 正のidは初期からあるアイテムなので末端として表示 else: # ラベルの設定によって表示方法を変更 if labels == None: print clust.id else: print labels[clust.id] # 右と左の枝を再帰的にたどって処理 if clust.left != None: printclust(clust.left, labels=labels, n=n+1) if clust.right != None: printclust(clust.right, labels=labels, n=n+1)
それでは実際にクラスタリングの結果を表示してみますよ
>>> cluster.printclust(clust, labels=blognames)
-
flagrantdisregard
-
-
SpikedHumor - Today's Videos and Pictures
-
Hot Air Top Picks
Celebrity gossip juicy celebrity rumors Hollywood gossip blog from Perez Hilton
<以下省略>
うん、階層構造にクラスタリングできたっぽい雰囲気です(´・ω・｀)
Scala de クラスタリング
それでは本題のScalaによるクラスタリングをしていきマス(｀・ω・´)
とりあえずこんな感じで書きなおしてみました…再帰が最適化されているか不安ですが(´・ω・｀)
import scala.collection.mutable // クラスタリング処理を実行 def hcluster(rows:List[List[Double]], distance:(List[Double], List[Double]) => Double = pearson):Cluster = { // アイテムを初期クラスタとして登録 val clust = (for(i <- Range(0, rows.size)) yield { Cluster(rows(i), id = Some(i)) }).toList // 類似度のキャッシュ用変数を準備 val distances = mutable.Map.empty[(Int, Int), Double] // 再帰的ループでクラスタリングを実行 def clustring(clust:List[Cluster], cid:Int = -1):List[Cluster] = { // クラスタが一つになった時点で終了 val length = clust.size if(length <= 1){ clust } else { // 一番類似度の高いペアを取得 val closest = (for(i <- Range(0, length)) yield { clust.takeRight(length - i).map(x =>{ if(!distances.contains((clust(i).id.get, x.id.get))) distances((clust(i).id.get, x.id.get)) = distance(clust(i).vec, x.vec) (distances(clust(i).id.get, x.id.get), clust(i), x) }) }).flatMap(x => x).filter(x => x._2 != x._3 ).toList.sort(_._1 < _._1).head // 類似度の高いペアをマージしてグループを作成 // 初期アイテムと区別するためにIdは負の数 val c1 = closest._2 val c2 = closest._3 val mergevec = (for(i <- Range(0, c1.vec.size)) yield { (c1.vec(i) + c2.vec(i)) / 2}).toList val c0 = Cluster(mergevec, Some(c1), Some(c2), closest._1, Some(cid)) // 再帰処理をしますが、処理が長いので進捗表示つけます println(closest._2.id.get + " & " + closest._3.id.get + " is deleted") println(clust.size) clustring(c0 :: clust - closest._2 - closest._3, cid -1) } } // 処理を開始してルートクラスタを返す clustring(clust)(0) }
(´ε｀；)ｳｰﾝ…まだまだ効率化出来ていない気がする上に…きちんと動くのか不安です(´・ω・｀)
とりあえず処理が出来るか確認したいので、表示用処理もScalaで書いてみますよ(｀・ω・´)
// クラスタ表示用の処理です def printclust(clust:Cluster, labels:Option[List[String]], n:Int=0):Unit = { // 階層をインデントスペースで表現します for(i <- Range(0, n)) print(" ") // IDが負の数の場合はまとめたグループなので枝です if(clust.id.get < 0){ println("-") // IDが正の場合はアイテムなので情報を表示します } else { // ラベルが存在する場合で表示を変更します if(labels == None) println(clust.id.get) else println(labels.get(clust.id.get)) } // 左右の枝がある場合は再帰的に表示していきます if(clust.left != None) printclust(clust.left.get, labels=labels, n=n+1) if(clust.right != None) printclust(clust.right.get, labels=labels, n=n+1) }
んじゃ、実行してみます(´・ω・｀)
// インポートしてみます scala> import org.plasticscafe.collective.cluster._ // データソースを読み込みます scala> val (b,w,d) = Cluster.readfile("blogdata.txt") b: List[String] = List(Joystiq, Neil Gaiman's Journal, Search Engine Watch Blog, The Superficial - Because You're Ugly, Online Marketing Report, TreeHugger, Joh <省略＞ // 階層的クラスタリングを実行します scala> val clust = Cluster.hcluster(d) 26 & 64 is deleted 91 2 & 27 is deleted 90 <省略＞ // クラスタリングの結果を表示します(´・ω・｀) scala> Cluster.printclust(clust, Some(b)) - - - - - ThinkProgress The Official Google Blog kottke.org - The Viral Garden A Consuming Experience (full feed) Google Operating System -
あれ？Pythonのときと結果が違うのはなんででしょ？
いくつかの処理ポイントがあるから、どこでひっかかってるのか(´・ω・｀)わからん
...と、いうことで時間あるときに治す方向で一端ペンディングしますデス
追記 途中途中の中間データは同様の結果が出ているので、リストからの値の取り出し順あたりに差が出てきている雰囲気が… 根本的なリストの使い方に原因がありそうなので、少し時間をかけて見ていきたいと思います(´・ω・｀)
