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

のんびり読書日記

日々の記録をつらつらと

Wikipediaのデータでk-means++を試す

前にPerlでk-means++を書いたのですが、今回はk-means++をC++で書き直してみました。でも愚直に作ったので、非常に遅い…。大きめのデータだとちょっと使い物にならないのですが、せっかくなので作成したコードはgithubに置いてみました。

ハッシュ関数のところは、下記のページで使用されていたものを拝借してます。

では、実際に動かしてみます。入力は、以前の記事で作成した、wikipediaの各キーワードの特徴量をTFIDFで抽出したデータからランダムに1000キーワード分だけ抽出したものを使用しています。ただし、ワードとポイントの間のデリミタを":"からタブに変更しています。":"とかを混ぜるんじゃなくて、全部タブ区切りの簡単でしたね。うーん、失敗。

またベクトルの比較関数は、Perl版ではベクトルの距離を2乗したものを使用していましたが、今回はcosineを使用しています。

% g++ -Wall -O5 `tcucodec conf -l` kmeanspp.cc -o kmeanspp 
% kmeanspp -i ~/data/wikipedia/tfidf.hdb -o out.txt -n 100
Open input dbm and output text file
Choose initial centers
 center No.2
 center No.3
...
Do k-means clustering
 k-kmeans loop No.1
 k-kmeans loop No.2
 k-kmeans loop No.3
 k-kmeans loop No.4
 k-kmeans loop No.5
 k-kmeans loop No.6
 k-kmeans loop No.7
 k-kmeans loop No.8
 k-kmeans loop No.9
Save clusters

% sort -k 1 -g out.txt
0       2時間ワイドじゃんけんぽん
0       BEMANIシリーズ
0       FCシェリフ・ティラスポリ
0       Mach-O
0       NSTスーパータイム
0       SORA! -フライトアテンダント物語-
...
93      茨城県立伊奈養護学校
93      茨城県立美浦養護学校
93      八幡養護学校
94      5050
94      66
94      ピッチクラス
94      高度合成数
99      スチーブン合成

クラスタ何個か見てみたのですが、精度はいまいち。綺麗に分かれてるクラスタもあるのですが、ゴミがくっつきすぎですね。どれくらいのクラスタ数にすればいいのかの判断もできないですし。うーん、TFIDFで抽出した特徴量があまりきれいにとれていなかったのか、k-means++のソースがおかしいのか…。気が向いたら調べてみようと思います。

せっかくなので、うまくいってそうなクラスタの例を書きます。

24      2007年のJリーグカップ
24      FIBAアジアチャンピオンズカップ
24      アメリカン・アソシエーション (曖昧さ回避)
24      アンドレス・エスコバル
24      インターナショナルリーグ
24      コルチェスター・ユナイテッドFC
24      ササ・サルセード
24      ショーン・マリオン
24      ジョージ・ライト (内野手)
24      ベン・テイラー (ニグロリーグ)
24      ボビー・ドーア
24      雁部竜太
24      橋川健
24      真田雅則
24      清水都貴
24      竹中里奈
24      東レ・アローズ (女子バレーボール)
24      富士通レッドウェーブ
24      北野貴之
51      奥阿仁駅
51      花崎駅
51      海崎駅
51      紀伊小倉駅
51      玉野駅
51      金上駅
51      後庄駅
51      梧柳洞駅
51      高雄臨港線
51      黒山駅分岐新潟東港専用線
51      三多商圏駅
51      山下駅 (宮城県)
51      鹿児島交通枕崎線
66      高梨氏
66      三宅御土居
66      上杉持房
66      清水城 (出羽国)
66      足利藤氏
66      丹羽氏音
66      朝比奈泰煕
66      浜村蔵六 (二世)

次は階層的クラスタリングあたりを試してみますかね。