2013年10月23日水曜日

Jaccard係数

ここ最近、社内の技術発表会の準備で忙しく、
カフェ勉が全然できませんでしたが、
ようやく落ち着いてきたので、再開してみます。

とは言っても、発表会が終わったら
特許出願の準備が控えているので、
またまた忙しい日々になりそうですが
亀ペースでも勉強を続けていきたいところです。


さて、今日はちょっと主旨を変えて、データ検索の話です。


Smart Newsのアルゴリズムに関する資料を
Twitterで知ったので読んでみました。

これです↓
http://www.slideshare.net/kouheinakaji/webmining-27353727


そのうち、複数のほぼ同一の記事を1つにまとめるための技法として
b-bit Minwise Hashingという技術があったので、
少し勉強してみました。

この技法は、Jaccard係数やMinHashの軽量版のような位置づけです。
このため、まずはJaccard係数について説明してみたいと思います。


Jaccard係数とは何か?
これは、2つの集合の類似度を表す1つの数値表現です。
具体的には、分母には2つの集合のORをとったときの要素数,
分子には2つの集合のANDをとったときの要素数が該当します。

例えば、集合A = { a, c, e, f, h}  集合B = {b , c, d, g, h} である場合の
Jaccard係数は、

| A∩B | = | { c, h } | = 2

| A∪B | = | { a,b,c,d,e,f,g,h } | = 8

なので、

2/8 = 1/4 = 0.25

となります。

ここで、| 集合X | は、集合Xの要素数を指します。


この係数の取り得る範囲は、[ 0 , 1 ] となります。
0となるのは、2つの集合が互いに独立な場合です。
逆に1となるのは、2つの集合が完全一致している場合です。

このJaccard係数は、例えば2つの文書の類似度を調べるときに用いられます。
以下は、2つの文書に対するBag Of Words(BoW)です。

文書1={ Apple:1 , 年末商戦:1, パソコン:1 , 売上: 1  }
文書2={ Windows8 :1 , パソコン:1, 激安: 1  }

※↑このBoWは架空の文書をもとにして作っています。

この場合のJaccard係数は

| 文書1∩文書2 | = 1;
| 文書1∪文書2 | = 6;

なので、1/6です。

そのため、この2つの文書はあまり似ていないという解釈が妥当そうな結果です。
実際に類似判定する際は、予めしきい値を設定して、それ以上になる2つの文書を
「類似」と判定するのが一般的です。

しきい値そのものの設定は、システムの用途や設計者の思想で
決めれば良いのではないでしょうか。


余談ですが、Jaccardの読み方は何が正しいんでしょうか。。。
Google先生に聞いてみると「ジャッカード」に票が集まっています。
私は、ヤコビアンのスペルがJacobianなので、
「ヤッカード係数」って読んでいたんですが、自信はありません(笑)

別の読み方としては、「ジャックカード」とも読めなくもないです。
でも、何だかクレジットカードの名前と勘違いしそうですね(笑)

実際のところはどうなんでしょう。