Twitterスパムフィルターの実装

1 Star2 Stars3 Stars4 Stars5 Stars (まだ評価されていません)
Loading...

以下では自分が運用しているトレンド解析システムで使用しているスパムフィルターの実装方法について解説していきます。

スパムフィルターで用いる機械学習

スパムフィルターの実装では機械学習の中でも「教師あり学習」と言われるものを用います。これはラベル特徴量からなるデータから、どのような特徴を持つものがどのようなラベル(カテゴリ)に当たるかを自動的に学習するものです。
具体的に見ていきましょう。例えばTwitterには以下の様なツイートがあります。

1.眠い……でも起きなきゃ
2.同点から中田の3ランホームラン!
3.[無料でカンタン]に魔法石ゲット♪ ⇒http://xxx.xyz/999
4.相互フォローで繋がれる人募集中です!すぐフォロー返しますのでよろしくお願いします! リツイートもしてほしいな♪ #followme #refollow #followback #相互フォロー #sougo #相互 #フォロー返し #拡散希望 #リフォロー #出会い"

1,2番のような普通のツイートと違って3,4番のようなスパムツイートは「無料」「ゲット 」「相互フォロー」などなんとなく使用されている単語に特徴があることに気づくと思います。この時、1,2番に「スパムでない」とラベルをつけ「眠い」「中田」「ホームラン」などの単語(特徴量)を取り出し、3,4番に「スパムである」とラベルをつけて同じく「無料」「ゲット」「相互フォロー」などの単語(特徴量)を取り出し、そこから「特徴量(今回の場合は単語)からラベル(カテゴリ、今回の場合はスパムかどうか)を判定する」という学習を行わせることを考えます。

形態素解析

まずスパムツイートと普通のツイートでは出現単語にどのような違いがあるかを知らなければいけません。そこで形態素解析というツールを使います。例えばkuromojiでは「寿司が食べたい。」という文を次のように分析してくれます。

寿司  名詞,一般,*,*,*,*,寿司,スシ,スシ
が 助詞,格助詞,一般,*,*,*,が,ガ,ガ
食べ  動詞,自立,*,*,一段,連用形,食べる,タベ,タベ
たい  助動詞,*,*,*,特殊・タイ,基本形,たい,タイ,タイ
。 記号,句点,*,*,*,*,。,。,。

このように単語ごとに分割するだけでなく品詞(名詞、動詞などの単語の種類)や読みなども知ることができます。これを使って以下のようにツイートを単語に分割します。

    val UNNECESSARY_PATTERN = "<.*?>|\\[\\[.*?\\]\\]|\\[.*?\\]||\\{\\{.*?\\}\\}|\\=\\=.*?\\=\\=|&gt|&lt|&quot|&amp|&nbsp|-|\\||\\!|\\*|'|^[\\:\\;\\/\\=]$|;|\\(|\\)|\\/|:"
val URL_PATTERN = "(https?|ftp)(://[-_.!~*\\'()a-zA-Z0-9;/?:@&=+$,%#]+)"
val tokenizer = new Tokenizer.Builder().build
tokenizer.tokenize(text.replaceAll(UNNECESSARY_PATTERN, "").replaceAll(URL_PATTERN, " UURRLL ")).toArray(new Array[Token](0))
//非自立語(「の」「が」「ます」などの単語)を除く
.filter(token => {
val pos = token.getPartOfSpeechLevel1
pos != "記号" && pos != "助動詞" && pos != "助詞"
})
.map(_.getBaseForm)//原型に戻す(例:暑く→暑い)

ワードベクトル

次に単語のインデックス化を行います。例えば「今日 -> 0, 明日 -> 1, 暑い -> 2, 寒い -> 3, 涼しい -> 4」というように番号付けすると「今日寒いんだけど」という文は「今日(0)」と「寒い(3)」という単語が出ているので(1,0,0,1,0)(0番目と3番目が1のベクトル)と表せ、「明日は暑くなるらしい」という文は(0,1,1,0,0)、「寒い、寒すぎる」という文は(0,0,0,2,0)(「寒い(3)」が2回出てくるため)と表せます。
実際には単語はたくさんあるので数千、数万という単位の次元になりますが、とにかくこうすることで文章という扱いづらいものをベクトルという数学の表現にすることができ、いろいろな処理を行えるようになります。コードは次のとおりです。

val WORD_COUNT_LOWER_THRESHOLD = 5
val wordIndexes = wordArray.map((_, 1)) //(各単語, 1)というtupleにする
.reduceByKey(_ + _) //同じkey(単語)のtupleのvalue(上の1)を足し合わせる、すなわち単語の出現数を数える
.filter(_._2 > WORD_COUNT_LOWER_THRESHOLD) //2番目(単語の出現数)が一定数以上のもののみを取り出す
.keys //key, すなわち単語を取り出す
.zipWithIndex() //Index化:(0番目の単語,0), (1番目の単語,1), (2番目の単語,2) ...というtupleに変換
.collectAsMap() //mapに変換

SVM

データをコンピュータに理解できる形に変換したらいよいよ学習を行います。機械学習は理論としては数学的な難解な部分を含んでいることが多いですが、単に使うだけなら多数のライブラリが用意されてるのでそれにデータを入れるだけで行うことができます。ここではMLlibという代表的なライブラリを使い、SVMという手法を用います。
この手法についてカンタンに説明すると例えば上記の方法でベクトル化したツイートを空間上に配置したところ、普通のツイートとスパムツイートが次の図のように配置されてたとします。
svm_01.png
この場合、直感的に下のような直線を引けばベクトルがどちらの側にあるかで分類できるとわかると思います。svm_02.png
SVMとはこのような直線(正確には超平面)を計算することで分類を行う手法です。
プログラムとしては以下のようにライブラリに丸投げするだけで使うことができます。

// LabeledPoint という(カテゴリ、ベクトル)のデータ形式に変換します
val dataSet = preparedData.map {
case (label, words) =>
LabeledPoint(
if (label == "spam") 1 else 0,
convertToVector(words)
)
}
model = SVMWithSGD.train(dataSet, NUM_ITERATIONS)
model.clearThreshold()

データ収集

コードの説明は以上のとおりですが、実際に機械学習をする場合以下の様な手順を行う必要があります。
1. データの収集
2. 人手によるラベル付け
3. 機械学習
3番めの機械学習は一回プログラムを書けば自動で行ってくれますが、1.2.が通常は人手で行わなければいけないので意外に面倒です。
しかしTwitterの場合その性質によりこの作業をある程度自動化できます。まず、スパムツイートはURLを含んでることが多いですが、例えば楽天のアフェリエイトドメイン(hb.afl.rakuten.co.jp)の場合はほぼ確実にスパムだと判定できます。これ以外にもスパムのみが使うドメインがあるのでそこからスパム判定ができます。また、スパムは「#相互フォロー」のような特徴的な日本語ハッシュタグを使っていることも多いのでそれもスパム判定に使えます。
また、Twitterでは公式クライアント以外から投稿する場合APIを用いる必要がありますが、どのアプリから投稿されたかが記録されるのでそれを元にスパム判定ができます。自分が開発しているトレンド解析システムの副産物でスパムのsourceリストがあるのでそれを用います。
これらを利用したスパムフィルターで少なくとも確実にスパムであるツイートがどれかは判定できるのでそれを用いてラベルづけを行います。もちろんこれだと取りこぼすものもあるのでスパムツイートを普通のツイートと誤ってラベル付してしまう場合もありますが、普通のツイートの方が圧倒的に多いので誤り率はごくわずかになります。

使い方

以上のソースコードはGithubに置いてあるのでそれをクローンして(sbtプロジェクトの場合)build.sbtファイルに以下のように記述します。

lazy val spamFilter = RootProject(file("C:\\workspaces\\TwitterAnalysis\\SpamFilter"))//クローンした場所
val main = Project(id = "YOUR_PROJECT", base =file(".")).dependsOn(spamFilter)//YOUR_PROJECTのところは自分のプロジェクトのsbtファイルに記載されているnameに合わせる

自分で訓練データを用意せず私が作成したものを用いる場合以下のようにすればすぐ使えます。

val japaneseSpamFilter = JapaneseSpamFilter.loadDefault
japaneseSpamFilter.isSpam(status)//twitter4jで取得したstatus

訓練データの更新

スパムツイートも時間とともに少しずつ変化していくことが考えられるので訓練データの更新を行っていく必要がありますが、ここでも手動で行うのではなく自動で行うことを考えます。

val score = spamFilter.calcSpamScore(status)
if (score > 1.0) {
pw.println("spam\t" + SpamTweetCollector.statusToString(status))
}
else if (score < -1.0) {
if (tweetCount % 25 == 0)//スパムでない通常のツイートは数が多いので減らす
pw.println("ham\t" + SpamTweetCollector.statusToString(status))
}

このコードではスコア(上の図で言うと2つのカテゴリを分ける赤い直線からの距離)が大きいものを「ほぼ確実にスパムであるもの」「ほぼ確実に普通のツイートであるもの」と仮定し記録しています。

スパムフィルターの性能指標

最後にスパムフィルター(一般的にはカテゴリ分類)の性能指標について解説します。性能指標には大きくprecision(正確率)とrecall(再現率)があり、以下の式で計算されます。

precision = (スパムと判定したツイートのうち実際にスパムであった数)/(フィルターがスパムと判定したツイート数)
recall = (スパムであると正しく判定できたツイート数)/(スパムツイート全体の数)

なぜ2つ指標があるかというと、例えば楽天のアフェリエイトドメイン(hb.afl.rakuten.co.jp)を含むツイートをスパムと判定するフィルターがあった場合、そこでスパムと判定されたツイートは確実にスパムなので、precision(正確率)はほぼ100%になりますが、当然の事ながらそれ以外のスパムツイートは補足できないのでrecall(スパムツイート全体のうち実際に捕捉できた数)はとても低くなります。逆に何でもかんでもスパムと判定するフィルターがあった場合recallは高くなりますがprecisionは低くなるので、片方の指標だけではそれが良いスパムフィルターなのか判断できません。そのためこの2つを両方考慮に入れて性能を考えていく必要があります。

参考リンク


1 Star2 Stars3 Stars4 Stars5 Stars (まだ評価されていません)
Loading...
      この投稿は審査処理中  | 元のサイトへ