🤔

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

2022/08/06に公開約4,800字

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

https://twitter.com/trend_words_jp/status/1542967393860722688

https://twitter.com/trend_words_jp/status/1542909008788348936

https://twitter.com/trend_words_jp/status/1515135352331071489

そもそも話題とはなにか

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

異常検知アルゴリズム

「そんなの当たり前じゃないか」と思うかもしれませんが、ではどうやったら「単語の出現数がいつもより大きくなっている」と判断できるかを考え始めると実はこれが意外に厄介な問題であることに気が付きます。例えば簡単に思いつくものとして(単語の出現数)-(普段の単語の出現数)とすればどうでしょう。
この場合、普段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)」と呼びます。
ここで、確率分布のパラメータはわからなくても対数正規分布であるということはわかっている(と仮定している)ので、モーメントはパラメータから計算すると以下のようになります。

m_1 = e^{\mu+\sigma^2/2}
m_2 = e^{2\mu+2\sigma^2}

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

\mu = \log({m_1^2/\sqrt{m_2}})
\sigma = \sqrt{\log({m2/m1^2})}

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

    public static double calcLogNormalMu(double m1, double m2) {
        return Math.log(Math.pow(m1, 2) / Math.sqrt(m2));
    }

    public static double calcLogNormalSigma(double m1, double m2) {
        return Math.sqrt(Math.log(m2 / Math.pow(m1, 2)));
    }

    public static double logNormalProbabilityLn(double mu, double sigma, double x) {
        return -Math.log(new LogNormalDistribution(mu, sigma).probability(x, Double.POSITIVE_INFINITY));
    }

単語をグループ分けし、どんな話題かわかりやすく

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

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

(単語Aの片共起率)=(単語A・Bが共に出現するツイート数)/(単語Aが出現するツイート数)
(単語Bの片共起率)=(単語A・Bが共に出現するツイート数)/(単語Bが出現するツイート数)

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

話題に言及しているツイートを判別

例えば「事変 東京 解散」という単語グループが得られ、「話題度/(グループ内の全単語の話題度の合計)」が以下のようになっていたとします。
事変:0.45
東京:0.35
解散:0.20

この場合、「事変」「東京」が特に大きい話題度を持ってるので、これらが含まれているツイートは「この話題に言及しているツイート」である可能性が高いと考えられます。
この時、それらのツイートを集めた結果以下のようになったとします。

  • 東京事変解散、公式HPで発表 http://t.co/xxxxxxxx
  • えっ、東京事変解散したの
  • そんな、東京事変が……
  • 東京事変解散とかショックすぎる
  • 東京事変好きだったのに……

ここで、最も話題度が高い「事変」を中心に、隣接する単語、さらにそれに隣接する単語……と見ていき出現回数を調べていくと以下のようなグラフを作ることができます。
フレーズ、文の抽出.png
この時、特に出現回数が高い「東京」-「事変」の連なりは フレーズ とみなすことができます。さらにしきい値を少し下げて『解散」まで含めると「東京事変解散」という ニュース文 も取り出すことができます。
ただし少し文が長くなってくると以下のように同じニュースでも

  • 「遊戯王」作者の高橋和希さん死去 海に浮かんだ状態で発見
  • 週刊少年ジャンプ漫画『遊戯王』作者・高橋和希さん海で死去
  • 人気漫画「遊戯王」の作者 遺体で見つかる

というようにメディアによって文面が異なってくるのでこの方法は使えません。
ただし、しきい値を低くしたり、何らかの理由で特定のメディアだけ注目されてる場合は以下のように長いニュース文を抽出できることもあります。

https://twitter.com/trend_words_jp/status/1544376946250813441

応用

そもそもこの話題分析システムはTwitter上でのデマ検知のために作ったもので、その構想案を以下の記事にまとめておきました。
「Twitter上のデマらしき情報を自動検知し、同時に判断材料を提供するシステム」の構想案 - Qiita

Discussion

ログインするとコメントできます