都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。

Bayesian Setsとは

Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に”Inspired by Google Sets”と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、

どちらのクエリにも”apple”という言葉が含まれていますが、1つ目のクエリは”banana”と一緒に検索しているため、果物のapple, bananaに関連するアイテムが得られていることが分かります。また2つ目のクエリでは”macintosh”と共に検索しているため、コンピュータ関連のアイテムが結果として得られています。このように入力されたアイテムと同じ概念の集合をオンデマンドに特定し、その集合中の他のアイテムを取得することができます。

Bayesian Setsについてより詳しくは、以下のページをご参照ください。

• Bayesian Setsの原著論文(PDF)
• Bayesian Setsの詳細な解説記事

またBayesian Setsを使った他のシステムには連想検索エンジンReflexaがあり、はてなブックマークの関連エントリなどに使用されているようです。

関連文書検索システムStupa

Bayesian Setsを使用した関連文書検索システムとして、Stupa(ストゥーパ)というシステムを作成しました。昔アジアを旅行したときに見た仏塔(ストゥーパ)から取ったもので、特に検索には関係ありません。

• Stupa – C++ implementation of Bayesian Sets
• チュートリアル

StupaはBayesian Setsにより類似する文書を高精度に検索し、また転置インデックスを構築することで高速に検索を実行できます。登録された文書データや転置インデックスは圧縮して保持しているため、メモリの使用量も少なく実行できます。

例として日本語版Wikipediaから作成したデータ(約61万エントリ)を使用して、Stupaのコマンドラインツールで関連エントリを検索した結果を以下に示します。結果のリストには、関連するエントリの名前と関連度が1行1エントリで表示されます。

• 「トヨタ自動車」で検索

% bsmgr search /path/wikipedia.tsv
Read input documents ...
Query> トヨタ自動車
トヨタ・プリウス        62.243313
トヨタ・トヨエース      56.777371
トヨタ・コロナ  54.229831
張富士夫        53.586574
トヨタ・ハイラックス    51.514397
トヨタ・プロボックス    49.165956
トヨタ・パブリカ        49.076950
中村健也        47.865204
奥田碩  45.499038
特別仕様車      45.440519
...
(search time: 3.21ms)

• 「かめはめ波」と「ドラゴンボール」で検索

Query> かめはめ波       ドラゴンボール
かめはめ波      263.980312
トランクス (ドラゴンボール)     72.204788
ミスター・サタン        69.037348
ドラゴンボールのアニメオリジナルの登場人物      65.560679
ドラゴンボールZ 超悟空伝 -突激編-       62.634941
ベジット        62.190804
ドラゴンボールZ 燃えつきろ!!熱戦・烈戦・超激戦  54.983379
ダーブラ        53.873965
ギニュー特戦隊  51.688147
ドラゴンボールZ この世で一番強いヤツ    51.597809
...
(search time: 3.95ms)

上記は「トヨタ自動車」で検索した場合と、「かめはめ波」「ドラゴンボール」の2つで検索した場合の結果ですが、両方とも関連するエントリが取得できています。検索にかかった時間は3ミリ秒ほどと比較的高速に実行できていることも分かります。

Stupaは入力された文書データや転置インデックスをメモリ上で保持して動作するため、頻繁に文書の追加・削除が行われるようなリアルタイム性の高いアプリケーションでの利用を主に想定して開発しています。例えばTwitter上で、自分の発言に関連するTweetを即座に検索する、といったアプリケーションが作れるかもしれません（Twitterだと1発言あたりの文章が短すぎて精度が悪くなってしまうかもしれませんが）。

またオプションで登録できる文書の最大数を指定すると、最大登録数を超えた場合に古い文書から削除していくようになるため、使用リソースを一定に抑えつつ、常に最新の文書から関連しているものを検索することができます。

Thriftによる検索サーバ

StupaにはC++ライブラリとコマンドラインツールが含まれているのですが、これ以外にThriftを使用した検索サーバも配布しています。Perlのクライアントも同梱されていますので、Webサービス等に実際に導入することも可能だと思います。

また現在クライアントはPerl実装しかないのですが、Thrift用のインタフェース定義ファイルがパッケージに含まれていますので、RubyやPythonなど他言語のクライアントを生成することも可能です。より詳しくはThriftのマニュアルをご参照下さい。

まとめ

関連文書検索システムStupaをご紹介させていただきました。StupaはBayesian Setsを使用して、高精度かつ高速に検索を実行することが可能です。今後はmixi上での応用を考えつつ、パフォーマンスの向上等を行っていきたいと思います。もしご興味がある方がいらっしゃいましたら、ぜひご利用下さい！

先日ようやくドラクエ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アルゴリズムを使用した混合分布モデルによるクラスタリングなど様々なソフトクラスタリング手法が提案されています。

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

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

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

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

0. 入力データの確認

% 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

2. 各ドキュメントとクラスタとの類似度を計算

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

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

逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。

クラスタリングとは

クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。

例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。

様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下のページが詳しいため、そちらをご参照下さい。

• クラスタリングとは (クラスター分析とは)
• Wikipedia: データ・クラスタリング

軽量データクラスタリングツールbayon

シンプルなデータクラスタリングツールとして、bayonというツールを作成しました。名前は、筆者が好きなアンコール・ワット遺跡のバイヨン寺院から拝借したもので、特にクラスタリングには関係ありません。

• bayon – simple and fast clustering tool

bayonはシンプルな構成で、かつ大規模なデータでも実用的なスピードで実行できるようにすることを目標に作成しています。手元の環境でいくつかのデータセットを用意して簡単に実行時間を測ってみたところ、以下の結果が得られました。50万件のデータでも12分程度で完了できており、用途にもよるとは思いますが、実用に耐えるだけの速度は得られていると思います。

bayonはクラスタリング手法として、後述するRepeated Bisection法を採用しているのですが、これは他のクラスタリングツールCLUTOで使用されている手法です。CLUTOは高速かつ精度もよいクラスタリングツールで、GUIでの利用や様々なオプションなどを利用することができる非常に便利なツールです。じゃあそもそもCLUTOを使えばいいのでは？となりそうですが、CLUTOは商用で利用する場合は事前許可が必要となり、使用の際はライセンスに注意しなければなりません。その点bayonはライセンスにGPL2を採用しているため、商用のサービスでの利用も問題ありません。

また手元の環境で試した限りでは、クラスタリングの実行速度はCLUTOよりもbayonの方が上回っています。ただCLUTOは精度向上のためにさらに複雑なことをしているので、単純な比較はできないのですが、さくっと傾向を確認したい場合等にはbayonも一つの選択肢として考慮していただければ幸いです。

実行方法

実際にbayonでクラスタリングを行う際は、まず入力として以下のようなタブ区切りのテキストファイルを用意してください。1行に1つのドキュメントの情報を表し、行の先頭にドキュメントのID、それ以降はそのドキュメントの特徴を表すキーとポイントをペアで記入します。

% 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ユーザの情報を1つのドキュメントと考え、ユーザが聞く音楽のジャンルによってそのユーザの特徴を表しています。「阿佐田」「小島」「古川」が各ユーザのID(名前)で、「阿佐田」の特徴を表すキーとして「J-POP」「J-R&B」「ロック」が挙げられています。

次にこの入力ファイルを使って、クラスタリングを実行します。以下ではクラスタ数を3に指定して実行しています。

% bayon -n 3 input.tsv > output.tsv

クラスタリング結果は、以下のようなタブ区切りのテキストになります。1行が1つのクラスタを表し、行の先頭がクラスタのID、それ以降はそのクラスタに所属するドキュメントのIDのリストです。

% cat output.tsv
1       小島    田村
2       阿佐田  青柳
3       古川    三輪

それぞれ、ジャズ好き、J-POP・ロック好き、クラシック好きのクラスタに分割できていることが分かります。

より詳しく知りたい方は、チュートリアルを用意してありますので、そちらをご参照下さい。

クラスタリング手法

bayonでは、Repeated Bisectionと呼ばれるクラスタリング手法を採用しています。Repeated BisectionはクラスタリングツールCLUTOで使用されているクラスタリング手法で、データ集合を繰り返し2分割することでクラスタリングを実行します。K-means法などと比較して、高速に実行でき、また精度も良好なようです。

Repeated Bisectionではまずすべてのデータを1つのクラスタに格納し、その後は以下の1-4の処理を実行して、繰り返してクラスタを2分割してクラスタリングを行います。

1. 分割するクラスタを1つ選択する(一番クラスタ内のまとまりが悪いものを選択)
2. クラスタ中からランダムに2つ要素を選択し、それぞれが格納したクラスタを2つ作成する
3. 元のクラスタ中の全ての要素に対し、2で選んだ要素との類似度を求め、類似度が高い方のクラスタに要素を追加する
4. 2クラスタ間で要素の移動を行い、分割結果の洗練を行う(移動できる要素がなくなるまで続ける)

ここで、2-4のプロセスだけに注目してみると、これはクラスタの中心を2つとしてK-means法を実行しているのと同じことをしています。つまりRepeated BisectionはK-meansを繰り返し実行しているだけなのです。

プロセス1でまとまりの悪いクラスタを選択するとき、プロセス4で要素を移動してクラスタの洗練を行うときは、クラスタのまとまり具合を評価する必要があります。このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほどクラスタの中心に凝集しているようになり、クラスタ中のデータが似た者同士の集まりである、と考えるわけです。ただし、クラスタ中の各要素と中心との類似度をまじめに全て比較するのは計算量も高くなってしまいます。実際には、この値はクラスタ中のベクトルをすべて足した複合ベクトルの長さと同値になり、そのため計算量も少なく評価値を求めることができます。評価値についてはCLUTOの論文に詳しく書かれているため、そちらをご参照下さい。

また、既存のクラスタリング手法には、確率・統計な枠組みを使用したより精度が高いと思われる手法が存在します。今回はシンプルさと実用的なスピードを主な目的としたためそれらは採用しませんでしたが、今後は他の手法も組み込み、実行時に自由に切り替えられるようにできればと考えています。

まとめ

軽量クラスタリングツールbayonのご紹介をさせていただきました。 bayonは容易に使用することができ、また実用に耐えられるだけのスピードを備えています。精度・機能面や、汚いソースコードなどまだまだ改善の余地がたくさんありますが、データの特徴をサッと調べたいときなどには皆様のお役に立てるかもしれません。もしご興味がある方がいらっしゃいましたら、ぜひご利用下さい！

初めまして、mixi開発部のfujisawaです。

マイミクシィの友人関係を使って、mixiのスモールワールド性について調べましたので、その結果について書きたいと思います。

スモールワールド性とは

スモールワールド性とは、人間関係のネットワークなどでよく見られる性質で、文字通り「世間は狭い(It’s a small world!)」ということを表しています。「知り合いを6人介するだけで、世界中の人々と間接的につながることができる」という『6次の隔たり(Six Degrees of Separations)』という言葉でもよく知られています。

一般にスモールワールドは以下の特徴を持っています。

1. 誰に対しても少ない人数を介するだけで到達できる(平均距離が小さい)
2. 自分の友人同士が友人関係にあることが多い(クラスタ性が高い)

1の距離とは、ネットワーク中のノードをたどった回数、すなわち友人を介した回数のことで、スモールワールドネットワークではこの距離が平均して小さくなる傾向にあります。

2のクラスタ性は、内輪づきあいの多さを表し、クラスタ係数という値で表現されます。このクラスタ係数が1に近いほど人間関係が密であり、0に近いほど疎であると考えられます。そしてスモールワールドネットワークではクラスタ係数が高くなる傾向があります。

たとえば下の図ではAはB、C、Dと友人関係にありますが、B、C、Dのそれぞれ(BとC、BとD、CとDの3ペア)が友人関係にある割合がAのクラスタ係数となります。ここでBとD、CとDが友人であるとすると、全体の3ペアの内2ペアが友人関係にありますので、Aのクラスタ係数は2/3=0.66..になります。このようにして他のノードのクラスタ係数も求めて、その平均を使用してグラフのクラスタ性を測ります。

次節では実際にmixiのマイミクシィの友人ネットワークを使用して、平均距離、平均クラスタ係数を求め、mixi上でスモールワールド性が成り立つかを検証したいと思います。

調査内容

まず試しに、筆者のmixi IDから残りの各ユーザ(2008年1月時点でmixi全体で約1300万人)までの最短距離(マイミクシィをたどった回数)を求めて、各距離ごとのユーザ数の分布を求めてみました。

距離が6で全体の95.7%、距離が7では98.2%のユーザをカバーできており、ほとんどのユーザに6、7人経由する以内で到達できていることが分かります。また平均距離は5.1になりました。まだ平均クラスタ係数は求めていませんが、筆者のIDで試した限りではスモールワールド性が成り立ちそうな期待が持てます。

ただしよく見てみると、距離が161のところで到達できるユーザ数の増加がなくなり、全体の98.6%のユーザまでしか到達できていないことが分かります。おそらくユーザの退会などにより、残りの1.4%のユーザはマイミクシィのつながりが切れているようで、他の大多数のユーザからはマイミクシィをたどる方法では到達することができません。そこでこの1.4%のユーザは対象から外して、もう一度調べようと思います。

またユーザによってマイミクシィの数はさまざまですので、その差異が少なくなるようにランダムに選択したユーザ1000人(1000人では少ないかもしれないのですが…)で同様に各距離の到達ユーザ数を調べ、その平均を求めるようにしました。その結果が以下の表になります。

距離が6では88%、距離が7の段階で98%のユーザに到達できています。平均最短距離は5.4となり、平均して6人程度という非常に少ない人数を介するだけで、他のユーザにたどり着けることが分かります。

また同様にランダムに1000人を選択し、その1000人の平均クラスタ係数を求めたところ、0.2になりました。一般にスモールワールドではクラスタ係数は0.1以上であるといわれているようですので、この0.2という値はスモールワールド性を表すのに適した値であると思われます。
ちなみに平均クラスタ係数が0.2ということは、100人の友人がいる場合はその友人同士の間で990ペアが友人であるということになります(0.2 × (100 × 99 / 2))。

また距離が1の場合のユーザ数に注目してみると、距離が1ということはユーザのマイミクシィそのものであるので、1ユーザあたりのマイミクシィの数は平均して22.3人ということも分かります。

まとめ

mixi上のマイミクシィネットワークを使用して、スモールワールド性について調査しました。その結果ユーザ間の平均距離は5.4、平均クラスタ係数は0.2となり、スモールワールド性が成り立ちそうであることが分かりました。

実は今回の調査よりも前に、mixi中のネットワークの分析を行い、スモールワールド性についても検証した研究報告がすでに存在します(『「複雑ネットワーク」とは何か―複雑な関係を読み解く新しいアプローチ』の167ページに掲載されています)。ただこの研究が行われたときからユーザ数が大きく増加していること、また何より自分がミクシィに入社したらこれはぜひ調べてみたい！と思っていたので、今回の調査を行いました。やはり実際に自分で確かめると楽しいですね。

これからも面白い現象を分析しつつ、サービスの開発に活かせていければと思います。