メモメモ

研究室のメンバー＋αの人にちょっと使ってもらったユーザ類似度判定システムについて、現在の状況と問題点と、今後の方針などメモしておく。

まず、今のところ出来てるシステムの入力、出力について簡単に説明。

入力：
・N人のユーザが持っているテキストの集合
・TEXT = {text1, text2, ..., textN}　のようなイメージ
・Twitter, Facebook, Gree, mixiなどなんでもおｋ
・言語非依存

出力：
・各ユーザごとに、そのユーザに似ているユーザ上位３０人
・各ユーザごとに、そのユーザが興味をもつトピック上位３件、各トピックについてトピック語上位５０語

で、今後は
・Twitterで似ているユーザをまとめたリストを自動作成する

など考えている。
「こういう感じの人をウォッチしたい！」という要望がワンクリックで実現する。

以下、もうちょっと細かいところ。

このシステムは大きく分けて３つのモジュールで構成される。

１．入力データの前処理
２．クラスタリング
３．類似度の計算

１について

現在の状況：
・全入力データを形態素解析し、単語の頻度を調べる
・単語の頻度上位5%と、１回しか出ない単語を入力データから除去
・単語の少ないユーザを除去
・ステップ２の入力フォーマットにデータを加工

現在の問題点：
・除去するデータの選び方が雑
・類義語はまとめた方が良いのではないか？

今後の方針：
・未定

前処理は多分一番難しく、どうするのがベストなのか検討もつかない。泥臭い工夫や作業が必要そうなところである。

２について

現在の状況：
・クラスタリングにはLDAを使っている
・推定方法はCollapsed Gibbs Sampling
・トピック数は300、イテレーション回数250回。この数字を選んだ根拠は特に無い
・（加工後の）入力データの全単語数をW、イテレーション回数をIとおくと、計算量はO(WI)

現在の問題点：
・トピック数を自動で最適化できないか？
・計算にとても時間かかるしメモリも沢山消費する。並列化できないか？理屈としてはできるし、C++実装がオープンソースで公開されている

今後の方針：
・トピック数の最適化のためノンパラベイズに手を出してしまう？
・並列計算する

３について

現在の状況：
・各ユーザごとに、他ユーザとの類似度を計算している。評価にはユークリッド距離を使っている
・トピック数をK、全ユーザ数Uとすると、O(U^2*K)オーダーの計算量
・というのも、ユーザ２人１組の組み合わせが全部でU*(U-1)/2通り。各組について、ユークリッド距離計算するのにO(K)かかる。
・各ユーザのごとに、そのユーザが興味をもつトピックを出力している。ソート処理があったりで、計算量はO(U*KlogK)

現在の問題点：
・計算にとても時間かかる。多分、ボトルネックになっているのは類似度計算するところ。せめてユーザ数の線形時間にならないか？

今後の方針：
・類似度計算を並列化。多分がんばればできる。
・何も考えずにユークリッド距離使っているけど、他の評価指標も試してみたい。