IR の階層的クラスタリングを試すの続きです。
"efficient" な HAC(hiererachical agglomerative clustering) を実装してみます。
今回は、コード全体をぺたぺた貼り付けるのも見にくいし面倒だしということで、github に置いてみました。
git://github.com/shuyo/iir.git
前回作った corpus パックも commit してありますので、 clone すればいきなり動く、はず。
git clone git://github.com/shuyo/iir.git cd iir/hac ruby hac.rb 4million.corpus
おのおの手元でちょこちょこ改変して試してみるには CodeRepos より git の方が向いてるんじゃあないかなあと思ったんですが、git まだ使いこなせてないのでなんか色々間違ってるかも。
実装の説明に行く前に、まず前回の naive HAC (=single-link clustering) はなぜ inefficient だったか、という話を簡単に。
クラスタを近い(=類似度が高い)順に結合していくのが HAC の基本ですが、そうなると当然「クラスタ同士の類似度」を計算しなくてはならなくなります。
一番素直で簡単のだと、「クラスタ間で最も近い(類似度が高い)ベクトル同士の類似度を、クラスタ間の類似度とする」という方法があるのですが(これが single-link clustering)、これが「大きいクラスタほど有利」な計算方法であることは明らかでしょう。
このため、「大きいクラスタが、対象を一つずつ拾っていってしまう」という現象(chaining)が発生してしまい、クラスタリングとして役に立たなくなってしまうことがあるわけです。
それを解消するための方法として、IIR の 17.2～17.4 では single-link clustering 以外に complete-link clustering, centroid, group-average など、チェインニングが起きにくい「クラスタ同士の類似度」を紹介しています。これらの詳細については、ここでは省きますね。
前回も紹介した「クラスタリングとは (クラスター分析とは)」にもこれらの方法が載っています。ただし、こちらは類似度として(ユークリッド)距離を使用しているので、IIR の cosine similarity とは大小が逆だったり、距離の場合に有効な「ウォード法」が紹介されていたりします。
また、IIR 17.2.1 では、前回の naive HAC の計算量は Θ(N^3) だったのですが、priority queue を導入すると Θ(N^2 log N) にできるよ、という話をしています。
それらを合わせたアルゴリズムの pseudo code が掲載されているので、今回はそれに沿って実装してみるわけです。
実装
まず。
前回は余計なキャッシュとかして追いかけにくいコードになってしまって反省なので、今回は「対象な２値ハッシュ」のようなものをこしらえてみました。
a = SymmetricHash.new a[1, 2] = 3 puts a[2, 1] # => 3
このように、キーとして２つの値を取りつつ、それを入れ替えたものも同じ値へのアクセスになる、というもの。
前回より読みやすくなってると思います。
あと、priority queue ですが……それっぽいインターフェースの「自動ソート配列」で簡易にやっつけました。手抜きです(汗)。
誰かが高速な priority queue の実装を教えてくれるのを期待(苦笑)。
HAC のキモ、IIR の pseudo code にちょうど対応する部分のソースです。
def pq_hac(docs)
sim = SymmetricHash.new # 類似度
clusters = Hash.new # クラスタに属するドキュメント。centroid などの計算に使用
pqueue = Hash.new # priority queue
# calcurate similarity & priority queue
docs.each do |d1|
t1 = d1[:title]
clusters[t1] = [d1]
pqueue[t1] = PriorityQueue.new
docs.each do |d2|
next if d1 == d2
v = sim[t1, d2[:title]]
unless v
sim[t1, d2[:title]] = v = calc_sim(d1[:vector], d2[:vector])
end
pqueue[t1].insert( [v, d1, d2] )
end
end
# hac
merged = [] # マージ列。dendrogram 生成に使用
while docs.size > 1
# 類似度最大のクラスタの組を取得
maxsim = [0]
docs.each do |d1|
t1 = d1[:title]
maxsim = pqueue[t1].max if pqueue[t1].max[0] > maxsim[0]
end
v, d1, d2 = maxsim
t1, t2 = d1[:title], d2[:title]
# マージ
merged << [t1, t2, v]
docs.delete(d2)
clusters[t1] += clusters[t2]
pqueue[d1[:title]].clear # ←★問題有り！★(後述)
docs.each do |d|
next if d==d1
t = d[:title]
pqueue[t].delete_if_3rd(d1)
pqueue[t].delete_if_3rd(d2)
v = yield sim, clusters, d, d1, d2 # clustering algorism はブロックで与える
pqueue[t].insert( [v, d, d1] )
pqueue[t1].insert( [v, d1, d] )
end
end
merged
end
今回は pseudo code とかなり１対１に対応するので、見比べやすいです。
ポイントは、clustering algorism はブロックで与えられるようにしているところ。
clustering algorism を色々切り替えて楽しめるようになっています。
# complete_link clusters = pq_hac(docs) do |sim, clusters, d, d1, d2| t, t1, t2 = d[:title], d1[:title], d2[:title] v = sim[t, t1] v = sim[t, t2] if v > sim[t, t2] v end # centroid centroid = Proc.new do |sim, clusters, d, d1, d2| calc_sim(calc_centroid(clusters[d1[:title]]), calc_centroid(clusters[d[:title]])) end clusters = pq_hac(docs, ¢roid)
実行
前回と同じ "4 Millions" の 25 短編を "Group-average agglomerative clustering" で分類させてみると次のような結果が得られました。
------------------------- TOBIN'S PALM
|| |||||| | | | | | |+- BETWEEN ROUNDS
|| |||||| | | | | | +-- THE FURNISHED ROOM
|| |||||| | | | | +---- THE SKYLIGHT ROOM
|| |||||| | | | +------- AN UNFINISHED STORY
|| |||||| | | +--------- LOST ON DRESS PARADE
|| |||||| | +----------- MAMMON AND THE ARCHER
|| |||||| +-------------- MEMOIRS OF A YELLOW DOG
|| |||||+---------------- AN ADJUSTMENT OF NATURE
|| ||||| | +------ THE BRIEF DEBUT OF TILDY
|| ||||| +------------ SPRINGTIME A LA CARTE
|| ||||| +----- THE GREEN DOOR
|| ||||+----------------- BY COURIER
|| |||+------------------ A COSMOPOLITE IN A CAFE
|| ||| +------------- MAN ABOUT TOWN
|| ||+------------------- THE LOVE-PHILTRE OF IKEY SCHOENSTEIN
|| |+-------------------- THE ROMANCE OF A BUSY BROKER
|| +--------------------- FROM THE CABBY'S SEAT
|+----------------------- THE GIFT OF THE MAGI
| +-------- SISTERS OF THE GOLDEN CIRCLE
+------------------------ A SERVICE OF LOVE
+---------------------- THE COMING-OUT OF MAGGIE
| | +--- AFTER TWENTY YEARS
| +---------- THE COP AND THE ANTHEM
+--------------- THE CALIPH, CUPID AND THE CLOCK
前回の naive HAC の結果よりは改善の兆しが見られますね。 "AFTER TWENTY YEARS" と "THE COP AND THE ANTHEM" が独立したクラスタに属しているあたりなんか、ちょっとは進歩したな、という感じです。
でも、まだまだ不満足。
これはやっぱり 8000次元もあるせいでしょうか……(次元の呪い、というやつ？)。
少なくとも「8000次元もあるせい」で、これがデータ由来の自然な結果なのかどうかを検証するのが難しくなっているので、次回は feature selection で次元を落とすのを試してみるべきですね。
問題(ばぐ？)
IIR の pseudo code には１つ問題があるように思えます。【追記：すいません勘違いでした→後述】
前回の naive HAC と、今回の priority queue + single-link は同じ結果になることが期待されるわけですが、実はそうはなりません。
上のコードで「★問題アリ★」と書いた部分で t1 (=マージ先のクラスタ) の類似度をため込んでいる priority queue をクリアしてしまっているんですが、これによって以下のような現象が起きてしまいます。
- A, B, C, D の４つのドキュメントがある
- 各の類似度が (A, B)=0.9, (A, C)=0.6, (A, D)=0.2, (B, C)=0.5, (B, D)=0.4, (C, D)=0.1 とする
- このとき HAC により (((A+B)+C)+D) の順にマージされる
- C までマージされたときの (A+B+C) と D の類似度は max(*, D)=(B, D)=0.4 のはず(naive HAC ではこの値になります)
- だが priority queue を用いた方では、C をマージしたときに queue に格納されていた 0.4 が消えてしまい、(A, D) と (C, D) のうち大きい方の 0.2 という評価になってしまう
centroid と group-average では、クラスタ内の全てのベクトルを使って計算しているのでこの問題は起きません。
ので、single-link や complete-link であっても、同じようにクラスタ内の全てのベクトルで再計算すれば問題ないんですが、"max(sim(i, k1), sim(i, k2))" のように２つの値だけの比較で済ませようとするなら、priority queue を単純にクリアするだけでは上述のような問題が起きます。
まあ、single-link を使うなら、同じ 17.2 で紹介されている NBM(next-best-merge) array を使った algorism を当然採用するんでしょうから(計算量 Θ(N^2))、実用上は問題ないと思いますけどね。
【追記】
pseudo code の18行目、20行目の解釈が抜けていました。これらをちゃんと実装すれば、B をマージしたときに (A, D) が 0.2 から 0.4 に更新されるので問題なくなります。すいません……。
逆に言えば、18行目、20行目は centroid や group-average を採用する場合には不要ですね。と言って少しでも取り繕ってみる(苦笑