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

mixi engineer blog

ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

bayonでソフトクラスタリング

algorithm mixi bayon

先日ようやくドラクエ9をクリアしたのですが、切ない話が多くて、たまに泣きそうになってしまったfujisawaです。以前ご紹介したデータクラスタリングツールbayonにいくつか機能追加を行いましたので、その中から以下の2つをご紹介させていただきます。

  • 入力データ中の特徴的なキーを自動的に特定して、クラスタリングの精度を向上させる
  • 事前に行ったクラスタリング結果を使用して、各ドキュメントに関連するクラスタを特定する

入力データから特徴的な要素を特定

bayonでは入力データとして、各ドキュメントに対し、その特徴を表すキーとポイントを指定する必要があります。例えば以下の例では、最近食べたメニューの名前とその回数を、各ユーザの特徴として指定しています。

fujisawa  卵かけご飯 4   みそ汁   6    ソーメン 3
kimura    ステーキ   8   みそ汁   7    寿司     4
...

ここで、実は「みそ汁」は多くの人がよく食べていて、入力データ中のほとんどのドキュメントに特徴として存在しているとします。するとあるドキュメントが特徴「みそ汁」を持っていたとしても、「みそ汁」は元々みんなが食べているものなので、その人を特徴づけるものとはなりません。このようなあまり意味をなさない特徴が入力データ中に多く含まれると、クラスタリング結果の精度が悪くなる原因になりかねません。

以前のバージョンでは、ツールユーザ側で入力データの精査を行って、より特徴的なキーのポイントを上げるようにしていただく必要がありましたが、現行のバージョンでは––idfオプションを指定することでシステム側で自動的に、特徴をよく表すキーのポイントを上げ、逆にあまり特徴的でないキーのポイントを下げられるようにしています。具体的にはあるキーが含まれるドキュメントの数を調べ、その数が小さいほどポイントを上げる、と非常に基礎的な手法を使用しています。より詳しくはwikipediaのtf-idfの説明などをご参照下さい。

ただし、入力データにすでにtf-idfや他の重み付けが施されている場合は、本オプションを使用することで却って精度が下がってしまうこともありえますので、ご注意下さい。

各ドキュメントに関連するクラスタの特定

現在のbayonでは、各ドキュメントは1つのクラスタのみに所属する、ハードクラスタリングの手法を採用しています。ただ実際のデータでは、ただ1つのグループ(クラスタ)のみに属するのではなく、複数のグループに関連することがよくあります。例えば「東京駅」は交通機関というグループにも属しつつ、所在地である東京都という地域のグループにも属すと考えられます。このように関連するグループが複数あるならば、それらすべてを知りたいケースもあると思います。

複数のクラスタへの所属を許す場合をソフトクラスタリングといい、Fuzzy C-meansや、EMアルゴリズムを使用した混合分布モデルによるクラスタリングなど様々なソフトクラスタリング手法が提案されています。

hard and soft clustering

ただしbayonではそれらは用いずに、あらかじめ求めておいたハードクラスタリングの結果を使用して、ドキュメントとクラスタの中心ベクトルとの類似度を測ることで、各ドキュメントに類似するクラスタのリストを取得できるようにしました。これにより擬似的にソフトクラスタリングと同様の結果を得ることができると思います。類似度の計算の際は転置インデックスを構築して高速化を行っており、計算時間も比較的短く実行できます。以下の表は転置インデックスを使用した場合と使用しなかった場合での、類似クラスタの特定にかかった実行時間です。

データ数クラスタ数クラスタリング(秒)転置インデックスOFF(秒)転置インデックスON(秒)
1000 10 0.17 0.092 0.088
50000 1000 36 48.3 13.4
500000 10000 720 (長時間のため停止) 1385

また上記の手法ではクラスタリング・類似クラスタ特定とシステムを2回実行する手間がかかり、また既存のソフトクラスタリングの手法と比べ精度的に劣る面もあるかもしれませんが、今回は実行速度を優先し上記の手法を取りました。またいくつかのデータで試した限りでは、実用上問題のない結果が得られているのではないかと思います。このやり方では理論的に明らかにおかしい、もっとよい手法がある、などありましたらメール等でぜひご教授いただければ幸いです。

関連クラスタ特定の実行方法

実際に類似クラスタを求める際は、以下の実行例のようにまずクラスタリングを行う際に-c or ––clvectorオプションでクラスタの中心ベクトルを保存しておき、その後-C or ––classifyオプションを指定して再実行してください。また以下の例では、前回の記事と同様に各ユーザの情報を1つのドキュメントと考え、ユーザが聞く音楽のジャンルによってユーザの特徴を表しています。

    1. 入力データの確認
% cat input.tsv
阿佐田   J-POP       10   J-R&B       6   ロック  4
小島     ジャズ       8   レゲエ      9
古川     クラシック   4   ワールド    4
田村     ジャズ       9   メタル      2   レゲエ  6
青柳     J-POP        4   ロック      3   HIPHOP  3
三輪     クラシック   8   ロック      1

 

    1. クラスタリングを実行(クラスタの中心ベクトルを保存しておく)
% bayon -n 3 -c centroid.tsv input.tsv  (クラスタリングを実行)
1       田村    小島
2       阿佐田  青柳
3       三輪    古川

% cat centroid.tsv  (クラスタの中心ベクトルを確認)
1   ジャズ  0.750476    レゲエ  0.654458    メタル  0.0920378
2   J-POP   0.806401    ロック  0.451887    HIPHOP  0.277129    J-R&B   0.262137
3   クラシック  0.921175    ワールド    0.383297    ロック  0.0672347

 

    1. 各ドキュメントとクラスタとの類似度を計算
% bayon -C centroid.tsv input.tsv
阿佐田  2       0.928261        3       0.0218138
小島    1       0.987737
古川    3       0.922401
田村    1       0.987737
青柳    2       0.928262        3       0.034592
三輪    3       0.922401        2       0.0560497

その結果上記のように、「阿佐田」ドキュメントには類似度0.93でクラスタ2、類似度0.02でクラスタ3が関連していることが特定できています。

またクラスタとの類似度を求めるときの入力ドキュメントは、クラスタリングを行ったときの入力とは違うドキュメント集合も使用できます。以下の例では、クラスタリングで使用したユーザとは違うユーザの情報を記入した入力ドキュメントに対し、先ほど求めたクラスタとの類似度を測っています。

% cat input_other.tsv  (新規の入力データ)
安藤    J-POP    5    ジャズ     7     ロック  4
灘      ワールド 6    クラシック 3
荒      レゲエ   5    ロック     3
森山    J-R&B    2    レゲエ     4

% bayon -C centroid.tsv input_other.tsv
安藤    2   0.615543     1    0.55375    3   0.0283486
灘      3   0.754793
荒      1   0.561193     2    0.232494   3   0.034592
森山    1   0.585365     2    0.117231

このようにクラスタリングと類似クラスタの特定の際の入力を分けることで、クラスタリングの際は信頼性の高いドキュメント集合だけを使用してより意味のあるクラスタ結果を得ておき、その後残りのドキュメントに対しては類似クラスタ特定のフェーズで前述のクラスタ結果に寄せていく、といった利用が可能となります。

まとめ

bayonに追加した機能から、特徴的なキーの特定・類似クラスタの特定について紹介させていただきました。ご興味のある方はぜひお試し下さい!

また次回の記事では、クラスタリングと上記で紹介したドキュメントの類似クラスタ特定を組み合わせた、ユーザの嗜好分析のお話をご紹介したいと思います。