読者です 読者をやめる 読者になる 読者になる

中年engineerの独り言 - crumbjp

LinuxとApacheの憂鬱

自然言語処理の落書き(canopy問題)

やはりcanopyが厄介だ。。

T2サンプリングの問題

自然言語処理では物凄くスパースなベクトルを扱ってるので
canopy(T2)の段階で、クラスタ数が必要以上に増える。

その後、canopy(T1)で重心算出すると、20個以上の重心がT2内に入ってる状態になったりする。

後処理しても、、

後からそれらを纏めてしまう事もできるが、そもそも必要以上の重心を作ってしまったT2サンプリングに問題があるように思える。

只でさえ、並列化の難しいアルゴリズムなのに、
本来必要な比較回数の数十倍の比較回数を処理しなければならないのが無駄だ。

代替案

T2サンプリング時に、逐一、重心算出をしながら行えば、ベクトルのスパース問題が緩和されると思いきや、精々1/2程度。
ヒドイとクラスタ数が増えたりする。
(ベクトルのスパースが埋まってくる前にクラスタ数が爆発的に増えてしまう為)

あまり効果が無い上に、重心算出コストが比較コストよりも高く、やってられない。

結論としては並列化するしかない

なんとかMapperに食わせる形にするしかないな。
やりたいのは、Kmeansに食わせる初期クラスタ算出であって、純粋なcanopy実装ではない。

canopyベースで色々変形させてみようか。。


<追記1>

canopy(T2)を並列化

厳密さを捨てる事で並列化出来そうな方法

  • MAPプロセスが立ち上がった時に、現クラスタ情報を読んでキャッシュ
    • ベクトル毎にMAP
      1. クラスタと比較し最初にT2近いものの所属とする
      2. クラスタと近くなかった場合は、クラスタ中心候補だが、隣のMAPが更新してるかもしれない。
      3. クラスタ情報を読み直してをキャッシュ更新。
      4. もう一度暮クラスタと比較。
      5. それでも近くなかったらクラスタ中心として追加。
    • 次のベクトル処理

隙間があったり、処理順が一定ではないので結果は安定しないが、実用レベルのクラスタにはなるようだ。

明らかに並列可能なメリットの方が大きい。
ただ、ベクトル数と並列度を上げていった時に、クラスタ読み直し負荷がどうなるか?
要検証・・・

<追記2>

上の、無駄クラスタを減らす努力の話はどうもダメダメっぽいな。
canopyは並列化し難い代わりに、スパースなベクトルのcos距離(≒内積)という軽量な比較処理が魅力に感じてきた。

スパースなベクトル同士の内積は関与する項が少ない


   V1 , V2 を比較しようとしてて、それぞれ1000次元だとしても
   共通項が"foo"一つなら、V1["foo"] * V2["foo"] でおしまいということ。

よって、無駄クラスタが多少増えようと、並列化のアプローチが正しそう。

<追記3>

T2サンプリングの際に、クラスタ数が多くなり過ぎる無駄に対応するために
T2半径を大きく取る試みは大きな間違いだったのようだ。

canopy(T2サンプリング)ではスパースな重心とスパースなベクトルのcos距離(実用:1-cos距離)を取るので、基本的には距離が遠い。

1-cos距離
cos距離は、最大距離が0で、最小距離が1。
ユークリッド距離の同様の計算処理に通したいので、値が大きいほど遠く扱える『1-cos距離』を用いている

しかしT1サンプリング後の重心算出では、ベクトルの平均を取るので、スパースではない重心が生成される。
この重心らは非常に距離が近くなる。

よってT2を大きく取ってしまうと、T1サンプリングの段階で、それぞれの重心に大半のベクトルが所属してしまう事になる。

こうなると元々近く、クラスタとして不適切な上に、スパースベクトルで無い分、データサイズも大きくなってしまう。

不適切
後続のk-meansの収束が遅くなるし、結果も悪くなる。
サイズ
同数のクラスタを抽出する場合でも、下記の方法と比べて10〜100ものデータ量になる場合もある

よって、比較的小さい半径のT2を取り、T2 -> T1 -> T2 と処理するのが良い模様。

補足
サイズ的にも配置的にもk-means中に出現するクラスタに近く、収束が早くなる傾向もある。
ある1000ドキュメントからクラスタを抽出する場合の(1-cos距離)

== T2 -> T1 ==
T2 : 0.99
T1 : 0.995
で、約10クラスタ
各々のクラスタのT1内には約700個程度のベクトル
そのときのデータサイズが10MB程度。

== T2 -> T1 -> T2 ==
T2 : 0.93
T1 : 0.94
で、約180クラスタ
180のクラスタ重心を更にT2サンプリングすると、約10程度になる。
各々のクラスタのT1内には約30個程度のベクトル
そのときのデータサイズが200KB程度。