Magicode logo
Magicode
0

Twitter上の話題を発見するアルゴリズム

以下では自分の修士研究で開発した話題解析システム( https://twitter.com/lamrongol/lists/trend-analysis )について解説していきます。

#そもそも話題とはなにか さて、話題を解析する前にまず「話題」とは何か、を定義しなければいけません。例えば地震が起きた時みんなが一斉に地震だとつぶやきます。さらに大きさや震源なども言及されるでしょう。つまりあるものが話題になってるとは、それに関連する 単語の出現数がいつもより大きくなっている ということを意味します。

異常検知アルゴリズム

「そんなの当たり前じゃないか」と思うかもしれませんが、ではどうやったら「単語の出現数がいつもより大きくなっている」と判断できるかを考え始めると実はこれが意外に厄介な問題であることに気が付きます。例えば簡単に思いつくものとして(単語の出現数)-(普段の単語の出現数)とすればどうでしょう。 この場合、普段1万ツイート中1回しか出現しない単語が11回出現した場合と普段100回出現している単語が110回出現している場合が同じ「話題度」とみなされます。しかし前者は少し話題になってると考えられますが、後者は「たまたまそうなった」という可能性を捨て切れません。では(単語の出現数)/(普段の単語の出現数)と「出現率」を使えばどうでしょう。しかしこれも問題があります。例えば普段100回出現している単語が200回出現している場合、出現率が2倍で何らかの話題になってると考えられます。しかし普段1回しか出現しない単語がたまたま2回出現した場合も「出現率」は2倍です。この二つが同じ規模の話題とは到底思えません。

ではどうしたらいいのでしょう。実はこれは機械学習では一種の異常検知問題と考えられるのでその手法を使うことができます。それは単語の出現数の確率分布を仮定し、出現数の情報量-log(p)を「異常の度合い」(今回の場合は話題になってる度合い)と考える手法です(-log(p)は確率pが小さくなるほど大きくなる関数であることに注意)。

例えば「今日」という単語が1万ツイート中平均100回出現し、以下の図のような確率分布に従っているとします(画像はWikipediaから転載)。

Lognormal_geological_basic.png

この場合、出現数が100の場合は「出現数が100回以上になる確率」を考えて-log(p)を計算するとだいたい-log(0.5)=0.693...となります。pは以下の図の黒く塗りつぶした部分の面積です。

Lognormal_geological_basic_100.png

出現数が150回の場合は同様に「出現数が150回以上になる確率」を考えて-log(p)を計算します。これによって「話題になってる度合い」を定量的に表すことができます。

Lognormal_geological_basic_150.png

対数正規分布

では「単語の出現数の確率分布」は何でどうやったら計算できるでしょうか。これはあくまで自分が色々試してみて調べた結果ですが、どうやら対数正規分布に従っているようです。そのため、単語の出現数の対数正規分布を計算しそれを元に「話題度」を計算できることになります。

以下、少し数学的な話になりますが対数正規分布はモーメント法(en:Wikipedia)を用いて計算できます。例えば1万ツイートごとの平均出現数が100回の単語があった時、それが101,98,103,100,...というように出現していたとします。この時、単純な平均を「1次のモーメント(m1)」、101^2+98^2+103^2+100^2...と2乗したものの平均を「2次のモーメント(m2)」と呼びます。 ここで、確率分布のパラメータはわからなくても対数正規分布であるということはわかっている(と仮定している)ので、モーメントはパラメータから計算すると以下のようになります。

すると、これをパラメータについて解くと逆にモーメントからパラメータを以下のように計算できることになります。

Apache Commons Math3には対数正規分布のライブラリがあるのでこれを使って「話題度」を計算できます。

共起

さて、以上の方法で「話題度」を計算してもそれをただ上から順に並べていくだけでは「台湾、清原、ミサイル、ベッキー、ロケット、麻薬、地震、不倫……」というようになって何がどう話題になってるのかよくわかりません。これがもし「台湾、地震」「清原、麻薬」「ベッキー、不倫」というようにグループ分けされていれば「台湾で地震が起きたんだな」とか「清原が麻薬で捕まったんだな」とわかりやすくなります。 これは機械学習で言うところのクラスタリングなので、検索すれば方法はいろいろ出てくると思います。自分の場合は以下のようにしてクラスタリングを行っています。

1.「片共起率」を各単語ごとに計算する

2.「片共起率」がともにしきい値(例えば0.10)以上の単語同士を階層的クラスタリングする

さらなる応用

このようにクラスタリングを行うと更に「必修科目『公共』新設」のようなニュース文を自動生成したり、その話題に言及しているツイートを(URLに頼ることなく)抽出することができますがとりあえずここまで。

続く(?)

Discussion

コメントにはログインが必要です。