自然言語処理の落書き（canopy問題）
やはりcanopyが厄介だ。。
T2サンプリングの問題
自然言語処理では物凄くスパースなベクトルを扱ってるので
canopy(T2)の段階で、クラスタ数が必要以上に増える。
その後、canopy(T1)で重心算出すると、２０個以上の重心がT2内に入ってる状態になったりする。
後処理しても、、
後からそれらを纏めてしまう事もできるが、そもそも必要以上の重心を作ってしまったT2サンプリングに問題があるように思える。
只でさえ、並列化の難しいアルゴリズムなのに、
本来必要な比較回数の数十倍の比較回数を処理しなければならないのが無駄だ。
代替案
T2サンプリング時に、逐一、重心算出をしながら行えば、ベクトルのスパース問題が緩和されると思いきや、精々1/2程度。
ヒドイとクラスタ数が増えたりする。
（ベクトルのスパースが埋まってくる前にクラスタ数が爆発的に増えてしまう為）
あまり効果が無い上に、重心算出コストが比較コストよりも高く、やってられない。
結論としては並列化するしかない
なんとかMapperに食わせる形にするしかないな。
やりたいのは、Kmeansに食わせる初期クラスタ算出であって、純粋なcanopy実装ではない。
canopyベースで色々変形させてみようか。。
＜追記１＞
＜追記２＞
上の、無駄クラスタを減らす努力の話はどうもダメダメっぽいな。
canopyは並列化し難い代わりに、スパースなベクトルのcos距離（≒内積）という軽量な比較処理が魅力に感じてきた。
スパースなベクトル同士の内積は関与する項が少ない
V1 , V2 を比較しようとしてて、それぞれ1000次元だとしても
共通項が"foo"一つなら、V1["foo"] * V2["foo"] でおしまいということ。
よって、無駄クラスタが多少増えようと、並列化のアプローチが正しそう。
＜追記３＞
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中に出現するクラスタに近く、収束が早くなる傾向もある。
