SPYSEEのつながりマイニングのはなし。
まえおき
http://spysee.jp/のなかのひとです。
フロントエンドやインフラ系はシャッチョーやid:amachangがやっているので、それ以外のところやってます。主にアルゴリズム。つながりの抽出手法や同姓同名処理手法を開発しました。
時々、なかのひととしていろんな会合に出没してます。そのたびに、
「つながりどうやってできてんのー？」
「同姓同名どうなってんのー？」
など聞かれますが、詳細に答えたことはありませんでした。about SPYSEE的な話はIVSのLaunch Pad(動画)などで話したことはありますが、アルゴリズムの詳しいところまでは時間なくて話しておりません。
さて先日、オーマ×クックパッド合同勉強会 を開催しました。そこでお時間いただき、「SPYSEEのつながりマイニング手法」という題目で講演させていただきました。参加されなかった方や、参加した方のおさらい用に当日の発表のまとめを公開できる範囲で用意いたしましたので、ご興味ある方はぜひご覧になっていただければと思います。
SPYSEEは学術研究をベースにしたアルゴリズムに支えられている
SPYSEEの歴史については、id:amachangが詳細に書いてくれている・・・ハズです。僕が博士課程に在学中に研究していた、研究者間の人間関係（共著や同所属、学会参加など）をウェブから自動抽出する、というものがスパイシーのつながりの原型になっています。その後、いくつもの研究開発を重ねてアルゴリズムを精錬したものが今のスパイシーのコアエンジンとして稼動しています。
SPYSEEは（ほぼ）すべての情報を自動で抽出している
SPYSEEで人物のページでは、以下の情報を見ることができます。
-
- 顔写真
- プロフィール
- 相関図（つながり）
- タグ
- 関連商品
- みんなのうわさ（Twitter）
- キーワード
- etc...
このうち、ユーザさんに入力してもらうタグ、メイン顔写真（クロールしてきた顔写真から最適なものを選ぶ）を除き、すべての情報を自動的に取得しています。それぞれその人物に最適な情報を抽出するためのアルゴリズムを開発し、人物名が追加されるたびに自動的に取得する仕組みになっています。SPYSEEが運用開始から2010年12月15日正午までに、自動で取得した情報の量をスライドにまとめました。
つながり抽出のベースとなる考え方
ここからが本題です。ひととひとのつながり自動抽出の方法について説明します。SPYSEEでつながりを抽出するときにベースとなった考え方があります。それは・・・
「たくさんのウェブページで名前が一緒に出てくる人はつながりがあるはずだ」
というものです。二人の名前を検索エンジンに入れると、その二人のひとの名前が一緒に出現するページの数がわかります。
ここで、市川海老蔵さんと小林麻央さんで検索すると、６０万件を超えるウェブページがあることがわかります。一方で、市川海老蔵さんと僕の名前で検索すると、ほとんどヒットしません（当然、面識もなにもないので・・・）。このことから、「市川海老蔵さんと僕」のつながりよりも「市川海老蔵さんと小林麻央さん」のつながりの方が強い、ということが予想されます。これがベースとなる考え方です。この、二人の名前が一緒に出現するウェブページの数を共起ヒット件数と呼びます。
ただし、実はこの共起ヒット件数だけではひとのつながりをうまく抽出することができません。というのも、有名人同士の共起ヒット件数は、そうでない人との共起ヒット件数に比べて、大きい数字になる傾向があるからです。そこで、SPYSEEではウェブ検索のヒット件数をつかってつながりの強さを抽出する指標を開発しました。ただ、こちらはもちろん公表できないものですので、参考によく使われる指標を挙げておきます。
スライドにもかいてありますが、SPYSEEではこれらの指標の組み合わせでつながりの強さを算出しています。
クローリングの問題
さて、氏名を組み合わせて共起ヒット件数などを取得すればつながりを抽出できることがわかりました。しかし実際にやろうとするとすぐに問題にぶちあたります。それは・・・
「クローリング回数が膨大な数になる」
というものです。先ほどSPYSEEが取得したデータ数を挙げましたが、登録人数は853,542人です。これで二人の氏名の組み合わせを作ると、
853,542 x (853,542 - 1) / 2 = 364,266,546,111
3600億回・・・。これは絶望的な数字です。どうしよう。
クローリングする候補を絞り込む
そこで、クローリングする候補を絞り込むことを考えます。最初のベースとなる考え方のところで出した例を思い出してください。市川海老蔵さんと小林麻央さんは共起ヒット件数が６０万件以上でしたが、共起ヒット件数がこれだけたくさん取れる例は珍しいです。先ほど計算した3600億の組み合わせのうち多くの場合が、市川海老蔵さんと僕のように、ほとんど共起ヒット件数がないものでしょう。そこで、効率よくクローリングするため事前にクローリング候補を絞り込む手法を考えました。
これにより、一人当たり８０万人以上クローリングしなければならなかったものが、１００人程度に抑えることができます。実は、候補となる氏名が取得できるウェブページの集め方には工夫が必要だったり、集めてきたウェブページから氏名を抽出するところにも工夫が必要だったりします。
ページの中まで読む
以上でだいたいのつながりは抽出できますが、それでもまだ問題があります。同じページ、しかも同じ文に二人の名前が出てくるケースを例に挙げます。
まとめ
