Twitter アクティブ認証精度向上のための

DEIM Forum 2016 F5-2
Twitter アクティブ認証精度向上のための
文字 N-gram IDF の提案
石山 雄大†1
韓 正圭†1
山名 早人†12
†1 早稲田大学 理工学術院 〒169-8050 東京都新宿区大久保 3-4-1
†2 国立情報学研究所 〒101-8430 東京都千代田区一ツ橋 2-1-2
E-mail:
†1, †2, †3{ishiyama, jirnan, yamana}@yama.info.waseda.ac.jp
あ ら ま し アクティブ認証とはユーザとのインタラクションを最小限にしながら継続的な認証を行うことで，ア
カウント乗っ取りの被害を早期発見する技術である．特に Twitter のようなマイクロブログサービスではメッセージ
が短いため，文体などユーザ個人の特徴を抽出し継続的に認証することは難しい．既存研究では，メッセージから
語彙的・文法的な特徴量を抽出し，機械学習を利用しユーザの真偽を判定している．しかし，不均一なデータセッ
トを利用した機械学習では，負例の割合が大きくなるほどエラー率が上がってしまう．そこで，本研究では機械学
習を使わず，本人の過去のメッセージ投稿データとの比較により判定を行う．そして，特徴量として文字 n-gram を
単純に利用するだけでなく，文字 n-gram に𝐼𝐷𝐹(𝐼𝑛𝑣𝑒𝑟𝑠𝑒 𝐷𝑜𝑐𝑢𝑚𝑒𝑛𝑡 𝐹𝑟𝑒𝑞𝑢𝑒𝑛𝑐𝑦)を適用する手法を提案する．
キーワード Twitter, アクティブ認証，𝐼𝐷𝐹
れている．同研究では，初期特徴量としてテキストか
1. は じ め に
1
Twitter と は ，ツ イ ー ト と 呼 ば れ る 140 文 字 以 内 の 短
ら 972 の 語 彙 的・文 法 的 な 特 徴 量 を 抽 出 す る ．そ の 後 ，
Information
Gain(IG)[2] 及 び
Mutual
いメッセージを投稿するマイクロブログサービスであ
特 徴 量 は
る ． 2015 年 10 月 時 点 に お い て ， Twitter の 月 間 ア ク テ
Information(MI)[3]に よ り 特 徴 選 択 さ れ る ． そ し て ， ユ
ィ ブ ユ ー ザ は 3 億 1600 万 人 ， 使 用 さ れ て い る 言 語 は
ー ザ 本 人 を 正 例 ， 偽 物 の ユ ー ザ を 負 例 と し ， Support
35 以 上 と 報 告 さ れ て い る ． 近 年 ， フ ィ ッ シ ン グ サ イ
Vector Machine (SVM)を 利 用 し ユ ー ザ の 真 偽 を 分 類 す
ト 等 か ら 不 正 に ID 及 び パ ス ワ ー ド が 入 手 さ れ ， SNS
る ． 既 存 研 究 [1]で は ， 100 人 の デ ー タ セ ッ ト に 対 し ，
のアカウントが乗っ取られてしまう被害が増加してい
ブ ロ ッ ク サ イ ズ 280文 字 ，１ ユ ー ザ あ た り 100 ブ ロ ッ ク
る．アカウントが乗っ取られてしまうと，ユーザの身
を 利 用 し ，等 価 エ ラ ー 率 (Equal Error Rate: EER) 13.27%
に覚えのない内容のツイートが勝手に投稿されてしま
を達成している．しかし，アクティブ認証では偽物ユ
う ．Twitter の サ ー ビ ス の 特 徴 で あ る リ ア ル タ イ ム 性 と
ーザである負例のデータが正例に比べ極端に多い不均
拡散性がゆえ，アカウント乗っ取りにおける被害は時
一なデータのため，分類器の学習が難しい．したがっ
間とともに拡大していく．そこで，アカウントの乗っ
て，分類器を使ったアクティブ認証では，負例である
取 り に お け る 被 害 軽 減 の た め に ，ID 及 び パ ス ワ ー ド に
偽物のユーザを増やすにつれ，判定精度が下がってし
よる一回限りの認証ではなく，アクティブ認証という
まう．
2
認証技術が研究されている．アクティブ認証とはユー
我々はこれまでに，過去のツイート群との比較をも
ザとのインタラクションを最小限にしながら継続的な
っ て ユ ー ザ の 本 人 判 定 を 行 う 手 法 を 提 案 し て き た [4]．
認証を行うことで，アカウント乗っ取りの被害を早期
ツイートのテキスト情報のみを利用する場合，これま
発 見 す る 技 術 で あ る ．Twitter に お け る ア ク テ ィ ブ 認 証
で に 単 純 な 文 字 n-gram を 抽 出 す る こ と で 過 去 ツ イ ー
では，ツイート投稿から語彙的・文法的な特徴量を多
ト の 比 較 を 行 っ て き た ．し か し ，単 純 に 文 字 n-gram を
数抽出し，投稿をしたユーザが本物か偽物かを一定間
利用するだけではユーザ独特の特徴量を抽出できない．
隔 に て 継 続 的 に 判 定 す る ．Twitter の よ う な マ イ ク ロ ブ
そ こ で ，代 表 的 な 語 の 重 み づ け 手 法 で あ る IDF（ Inverse
ログでは，投稿のある一定の文字数を間隔とする．し
Document Frequency）[5]を 利 用 し ，文 字 n-gram に 適 用
たがって，より短いツイート投稿からより低い誤認率
す る ． 𝐼𝐷𝐹は 代 表 的 な 語 の 重 み づ け 手 法 で あ り ， 多 く
でのユーザの真偽判定をする技術が求められる．
の文書に出現する語の重みを下げ，特定の文書にしか
既 存 研 究 [1]で は ，e-mail 及 び ユ ー ザ の ツ イ ー ト 投 稿
出 現 し な い 後 の 重 み を 上 げ る 効 果 が あ る ． 𝐼𝐷𝐹を 単 語
におけるテキスト情報から特徴量を抽出し，一定長の
n-gram に 適 用 す る と ，連 続 す る 単 語 の 繋 が り が 不 自 然
ブロックサイズでの連続的な認証を行う手法が提案さ
であるほど重みが大きくなる．不自然な繋がりの単語
n-gram に 大 き な 重 み を 与 え て し ま う こ と は ， 𝐼𝐷𝐹本 来
1
2
https://twitter.com/
https://investor.twitterinc.com/releases.cfm
の重みづけに適さない．しかし，アクティブ認証では
連続する語の繋がりが不自然なほどユーザ独特な特徴
量 と す る こ と が で き る た め ， 𝐼𝐷𝐹に よ る 重 み づ け の 効
著者候補群から推定する研究である．著者推定の研究
果に期待できる．そこで，本研究では単純に文字
で利用される文体相違度の計算方法を提案手法にて利
n-gram を 利 用 す る だ け で な く ， 文 字 n-gram に 対 し て
用するため，本節にて文体相違度の計算方法を説明す
IDF（ Inverse Document Frequency） に よ る 重 み づ け を
る．
行う手法を提案する
著 者 推 定 の 研 究 で は ，人 々 の 文 章 を 書 く ス タ イ ル (文
本稿では以下の構成をとる．まず第２節にて，本研
体 )を 特 徴 量 と し て 定 量 化 し ，文 体 の 相 違 度 を 計 算 し 推
究の既存研究について説明する．第３節では提案手法
定 を 行 う ．我 々 は こ れ ま で に ，複 数 の 文 字 n-gram に 対
で利用する先行研究について述べ，続く第４節にて本
し て n に 比 例 し た 重 み づ け を 行 い ，Twitter の よ う な 短
研 究 の シ ス テ ム 概 要 及 び 提 案 す る n-gram IDF を 説 明 す
いメッセージから多くの特徴量を抽出しコサイン類似
る．第５節では，評価結果及び既存研究との比較を述
度を用いて文体相違度を計算する手法を提案している
べ，最後に第６節にてまとめる．
[7]． メ ッ セ ー ジ か ら の 特 徴 量 抽 出 で は ， 1) 複 数 併 用
文 字 {1, 2, 3}-gram， 2) 重 み 付 き n-gram 頻 度 分 布 を 利
2. 分 類 器 を 利 用 し た ア ク テ ィ ブ 認 証 に 関 す
用 す る ． 複 数 併 用 文 字 {1, 2, 3}-gram と は ， n を 変 化 さ
る研究
せて複数併用することで，特徴量を増加させる手法で
本節では，ツイート投稿から語彙的・文法的な特徴
あ る ．重 み 付 き n-gram 頻 度 分 布 と は ，取 得 し た n-gram
量を抽出し，任意ユーザの投稿を入力とし、分類器を
について，n の大きさに比例して重み付けを行う手法
利用して投稿が本人のものかを判定する先行研究を説
で あ る ． 一 般 に 文 章 か ら 文 字 n-gram を 取 得 す る 場 合 ，
明する．
n-gram の n が 大 き く な る ほ ど 頻 度 が 小 さ く な る ．し か
Borcardo ら [1]は ，ツ イ ー ト 投 稿 に お け る テ キ ス ト 情
し ，n-gram の n が 大 き い 場 合 ，著 者 の 特 徴 と な る 未 知
報から特徴量を抽出し，一定長のブロックサイズでの
語を特徴量として取得できる可能性が高くなる．そこ
連続的な認証を行う手法を提案した．まず，初期特徴
で ， n-gram の n に 応 じ て ， 当 該 n-gram の 出 現 頻 度 を
量 と し て テ キ ス ト か ら 972 の 語 彙 的 ・ 文 法 的 な 特 徴 量
大きくしていく．
を抽出する．抽出した特徴量は高次元であるため，
奥 野 ら [7]は 文 体 相 違 度 の 計 算 手 法 と し て ，コ サ イ ン
Information Gain(IG)[2]及 び Mutual Information(MI)[3]
類似度を利用している．コサイン類似度は２つのデー
に よ り 特 徴 選 択 す る ．IG を 利 用 す る こ と で 良 い 特 徴 量
タセット間で重複する特徴量のみが考慮されるため，
を 選 択 す る こ と が で き る ．ま た ，MI を 利 用 す る こ と で
より２つのデータセット間の差異を際立たせられる．
相関性を持つ特徴を捨てることができる．データセッ
２ つ の デ ー タ セ ッ ト 集 合 P， Q に お け る 具 体 的 な 文 体
ト と し て Twitter ユ ー ザ 100 ア カ ウ ン ト を 収 集 し ， あ
相 違 度 の 計 算 手 法 を 説 明 す る ．集 合 P, Q は そ れ ぞ れ メ
る 一 人 の ユ ー ザ を 正 例 ，本 人 以 外 の ユ ー ザ を 負 例 と し ，
ッ セ ー ジ 𝑡を 𝑘件 含 む 集 合 と す る ．集 合 P, Q に 含 ま れ る
𝑆𝑢𝑝𝑝𝑜𝑟𝑡 𝑉𝑒𝑐𝑡𝑜𝑟 𝑀𝑎𝑐ℎ𝑖𝑛𝑒(𝑆𝑉𝑀)[6]を 利 用 し ユ ー ザ の 真 偽
全 て の メ ッ セ ー ジ か ら ，文 字 {1, 2, 3}-gram の 集 合 𝐶!" を
を判定する二値分類器を作成する．アクティブ認証の
作 成 す る ．集 合 P, Q そ れ ぞ れ に 対 し ，生 起 回 数 を 取 得
研 究 で は ， 評 価 指 標 に 等 価 エ ラ ー 率 (Equal Error Rate:
し n-gram の n に 応 じ て 重 み づ け を す る ．取 得 し た 重 み
づ け 生 起 回 数 を そ れ ぞ れ 𝐷! = {𝑑!! , 𝑑!! , … , 𝑑! !!" } と
EER) が 利 用 さ れ る ． EER は 他 人 受 入 率 (False
Acceptance Rate: FAR) と 本 人 拒 否 率 (False Rejection
𝐷! = {𝑑!! , 𝑑!! , … , 𝑑! !!" }と す る ．式 (1)(2)(3)の コ サ イ ン 類
Rate: FRR)が 等 し く な る 点 に お け る エ ラ ー 率 で あ る ．
似 度 を 用 い て ， 文 体 相 違 度 𝐷𝑖𝑠𝑠𝑖𝑚(𝑝, 𝑞)を 計 算 す る ．
Twitter ユ ー ザ 100 人 そ れ ぞ れ の ユ ー ザ に 対 し 分 類 器 を
作 成 し 評 価 を 行 っ た 結 果 ，EER 13.27%を 達 成 し て い る ．
な お ， ブ ロ ッ ク サ イ ズ は 280 文 字 ， １ ユ ー ザ あ た り の
ブ ロ ッ ク 数 は 100 ブ ロ ッ ク で あ る ． し か し ， ア ク テ ィ
ブ認証では偽物ユーザである負例のデータが正例に比
べ極端に多い不均一なデータのため，分類器の学習が
難しい．したがって，分類器を使ったアクティブ認証
で は ，負 例 で あ る 偽 物 の ユ ー ザ を 増 や す に つ れ ，𝐸𝐸𝑅が
向上してしまう問題がある．
3. 提 案 手 法 で 利 用 す る 先 行 研 究
3.1. 著 者 推 定 に 関 す る 研 究
著者推定の研究とは，著者が既知である文章から特
徴量を抽出し，著者が未知である文章の著者を複数の
𝐷𝑖𝑠𝑠𝑖𝑚!"# 𝑝, 𝑞 = ! ∈!!" (𝑓!" )
!
! ∈!!" (𝑓!" )
!
(1)
! ∈!!" 𝑓!" ∙ 𝑓!"
0.4 (𝑓!!! > 0,4)
(2)
𝑓!"! (𝑓!"! ≤ 0.4)
𝑑
(3)
!"
𝑓!"! = 𝑘
文 体 相 違 度 𝐷𝑖𝑠𝑠𝑖𝑚!"# 𝑝, 𝑞 は 値 が 小 さ い ほ ど ， ２ つ の
𝑓!" = 文 章 が 似 て い る こ と を 示 す ．こ こ で ，式 (2)で 用 い る 0.4
と い う 値 は 井 上 ら [8] が 経 験 的 に 決 定 し た パ ラ メ ー タ
である．著者候補の中から最も文体相違度が小さい文
章を書いた著者を探し，真の著者として推定する．
3.2. 過 去 ツ イ ー ト と の 比 較 に よ る 乗 っ 取 り ツ イ ー
り ツ イ ー ト 」と 判 定 す る ．無 作 為 に 抽 出 し た 100 ア カ
ウ ン ト に 対 し 実 験 を 行 い ， F 値 0.8570 を 達 成 し た ．
ト検 知 に関 する研 究
本項では，我々がこれまでに提案してきた過去ツイ
ートとの比較による乗っ取りツイート検知に関する研
4. 提 案 手 法
本 節 で は ，3.1 項 及 び 3.2 項 で 説 明 し た 我 々 の 従 来 手
究 [4]を 説 明 す る ．
我々はアカウントの所持者以外が投稿したツイー
法を拡張し，アクティブ認証の精度を向上させる方法
トを「乗っ取りツイート」と定義し，これを検出する
について説明する．
手法を提案した．アカウント所持者の過去のツイート
4.1. デ ー タ セ ッ ト の 前 処 理
どうしの文体相違度の標準偏差を計算し閾値を定める．
本 項 で は ， 2 節 で 説 明 し た 関 連 研 究 [1]と 比 較 す る た
アカウント所持者自身のツイートどうしを比較した場
め，関連研究と同じ条件でのデータセット作成方法に
合，どれだけ相違しているかを閾値は表す．したがっ
関して述べる．
て，新たなツイートと過去のツイートの文体相違度を
本 研 究 で は ， Twitter API1.1 3 を 用 い て Twitter デ ー タ
計算し閾値より離れている場合，偽物のツイートと判
の 収 集 を 行 い ， 2014 年 11 月 に ツ イ ー ト 投 稿 し た ユ ー
断する．文体相違度は，ユーザによって値の広がりが
ザ 1632 ア カ ウ ン ト を 取 得 し た ．取 得 し た ア カ ウ ン ト か
ことなるため，ユーザごとに閾値を計算する．
ら ラ ン ダ ム に 100 ユ ー ザ を 選 択 し 実 験 に 使 用 す る ． 選
具 体 的 に は ，対 象 ア カ ウ ン ト の 1,000ツ イ ー ト を 過 去
択 し た ユ ー ザ の 集 合 を 𝑈{𝑢! , 𝑢! , … , 𝑢! , … , 𝑢!"" }と す る ．選
の ツ イ ー ト 100 ツ イ ー ト と 残 り の 900 ツ イ ー ト に 分 割
択したユーザのツイートデータを繋ぎ合わせ，ある一
し ，後 者 は 閾 値 を 決 め る た め の ベ ー ス ツ イ ー ト と す る ．
定のブロックサイズごとに分割する．その際，ブロッ
過 去 ツ イ ー ト の 集 合 を 𝑃 = {𝑝! , 𝑝! , … , 𝑝!"" }， ベ ー ス ツ イ
クサイズでの区切りがツイートの途中にある場合，該
ー ト の 集 合 を 𝐵 = {𝑏! , 𝑏! , … , 𝑏!"" }と す る ．ツ イ ー ト 𝑏! に 対
当ツイートの最後までを既存ブロックに入れる．作成
す る ツ イ ー ト 𝑝! の 文 体 相 違 度 𝑑𝑖𝑠𝑠𝑖𝑚(𝑏! , 𝑝! )を 式 (4) に よ
したブロック群をさらに訓練データとテストデータ
っ て 算 出 す る ． 式 (5)に よ っ て 1 ≤ 𝑖 ≤ 900の 文 体 相 違 度
𝑇 !! に 分 割 す る ．本 研 究 で は ，10-fold cross validation に
𝑑𝑖𝑠𝑠𝑖𝑚(𝑏! , 𝑝! )の 中 央 値 を 求 め ，各 ツ イ ー ト 𝑝! の ベ ー ス ツ
て評価を行うため，訓練データ９対テストデータ１の
イ ー ト 集 合 𝐵に 対 す る 文 体 相 違 度 𝐷𝑖𝑠𝑠𝑖𝑚(𝐵, 𝑝! )と す る ．
比 率 で 分 割 す る ．分 割 し た テ ス ト デ ー タ の 集 合 を 𝑇!! と
文 体 相 違 度 𝐷𝑖𝑠𝑠𝑖𝑚(𝐵, 𝑝! )の 値 が 小 さ い ほ ど ツ イ ー ト の
す る ． 訓 練 デ ー タ を さ ら に ， 過 去 デ ー タ
文体が似ていることを示す．
1
𝑑𝑖𝑠𝑠𝑖𝑚 𝑏! , 𝑝! = 𝐶
𝑃!! {𝑝! , 𝑝! , … , 𝑝! , … }と ベ ー ス デ ー タ 𝐵!! {𝑏! , 𝑏! , … , 𝑏! , … }と 閾
!∈!
𝑃! (𝑥)
𝑙𝑜𝑔!" !
𝑃!! (𝑥)
(4)
(5)
𝐷𝑖𝑠𝑖𝑚 𝐵, 𝑝! = 𝑑𝚤𝑠𝑠𝚤𝑚 𝑏! , 𝑝!
1 ≤ 𝑖 ≤ 900
𝑃!! (𝑥)は ，ツ イ ー ト 𝑏! に 出 現 す る 全 て の 文 字 2-gram 中
に 含 ま れ る 文 字 2-gram 𝑥の 割 合 で あ り ，同 じ く 𝑃!! (𝑥)は ，
文 章 𝑝! に 出 現 す る 全 て の 文 字 2-gram 中 に 含 ま れ る 文 字
2-gram 𝑥の 割 合 と す る ．こ こ で 文 字 n-gram の n の 値 と
し て 用 い て い る 2 は ，実 験 的 に 求 め た 最 適 な 値 で あ る ．
ま た ， 文 章 𝑏! と 𝑝! 双 方 に 現 れ る 文 字 2-gram の 和 集 合 を
集合 C とする．
計 算 し た 𝐷𝑖𝑠𝑖𝑚 𝐵, 𝑝! に 対 し て ， ツ イ ー ト を 投 稿 し た
ク ラ イ ア ン ト の 種 類 及 び 投 稿 時 間 帯 ，リ プ ラ イ の 相 手 ，
そしてハッシュタグの種類により重みづけを行う．重
み づ け を し た 𝑝! 100 件 の 文 体 相 違 度 の 平 均 値 を 閾 値
𝛼(𝐵, 𝑃)と す る ． 評 価 実 験 で は ， 本 人 の 最 新 ツ イ ー ト 30
件 ， 本 人 以 外 の ユ ー ザ 30 人 か ら 1 ツ イ ー ト ず つ 計 30
件 の ツ イ ー ト を 使 用 す る ．こ の 合 計 60 件 の テ ス ト ツ イ
ー ト 集 合 を 𝑻 = {𝒕𝟏 , 𝒕𝟐 , … , 𝒕𝒌 , … , 𝒕𝟔𝟎 }と す る ． 式 (4) ， (5) を
使 用 し ， 新 着 ツ イ ー ト 𝒕𝒌 の 過 去 ツ イ ー ト 群 に 対 す る 文
体 相 違 度 𝑫𝒊𝒔𝒊𝒎 𝑩, 𝒕𝒌 を 計 算 す る ．計 算 し た 文 体 相 違 度
値 を 決 め る た め の テ ス ト デ ー タ 𝑇!!! に 分 割 す る ． な お ，
閾 値 を 決 め る た め の テ ス ト デ ー タ 𝑇!!! は テ ス ト デ ー タ
𝑇!! と 同 じ 大 き さ に 分 割 す る ． そ し て ， 分 割 し た 残 り を
過去データ 2 対ベースデータ 1 の比率で分割する．分
割の際，訓練データの一番古いデータが過去データに
分割されるようにする．
4.2. ツ イ ー ト か ら の 特 徴 量 抽 出
本 研 究 で は ， 3.1 項 で 説 明 し た 我 々 の 従 来 手 法 [7]を
ベ ー ス に 特 徴 量 の 抽 出 を 行 う ．具 体 的 に は ，1) 複 数 併
用 文 字 {4, 5, 6}-gram， 2) 重 み 付 き n-gram 頻 度 分 布 を
利 用 し ，メ ッ セ ー ジ か ら 特 徴 量 を 抽 出 し て い く ．な お ，
本研究では英語データセットを利用するため，従来手
法 で 使 用 し て い た 文 字 {1, 2, 3}-gram で は な く ，文 字 {4,
5, 6}-gram を 利 用 す る ．
ま ず ， 4.1 項 に て 作 成 し た 集 合 𝑃 !! と 𝐵 !! の 各 ブ ロ ッ ク
に 含 ま れ る メ ッ セ ー ジ か ら ， ブ ロ ッ ク 毎 に 文 字 {4, 5,
6}-gram を 取 得 す る ．そ し て ，ブ ロ ッ ク ご と に 文 字 {4, 5,
6}-gram の 出 現 回 数 を 数 え ， ブ ロ ッ ク ご と の 頻 度 ベ ク
ト ル 𝑓! {𝑓!! , 𝑓!! , … , 𝑓!! ,… }と 𝑓! {𝑓!! , 𝑓!! , … , 𝑓!! ,… }を 作 成 す る ．
𝑓!! は ブ ロ ッ ク 𝑝! に 含 ま れ る 文 字 {4, 5, 6}-gram の 出 現 回
𝑫𝒊𝒔𝒊𝒎 𝑩, 𝒕𝒌 が 閾 値 𝜶(𝑩, 𝑷)よ り 高 い 場 合 ， 𝒕𝒌 を 「 乗 っ 取
3
https://dev.twitter.com/rest/public
数（ 頻 度 ス コ ア ）を 値 と し た ベ ク ト ル で あ る ．そ し て ，
𝑑𝑖𝑠𝑠𝑖𝑚(𝑝! , 𝑏! )を 式 (8)に よ っ て 算 出 す る ．式 (9)に よ っ て ，
[7] に 基 づ き 作 成 し た 頻 度 ベ ク ト ル に 対 し ， そ れ ぞ れ
文 体 相 違 度 𝑑𝑖𝑠𝑠𝑖𝑚(𝑝! , 𝑏! )の 中 央 値 を 求 め ， 各 ツ イ ー ト 𝑏!
n-gram の n に 応 じ て 頻 度 ス コ ア を 3n 倍 す る ．
の 過 去 ツ イ ー ト 集 合 𝑃に 対 す る 文 体 相 違 度 𝐷𝑖𝑠𝑠𝑖𝑚(𝑃, 𝑏! )
4.3. 文 字 n-gram に 対 す る IDF 適 用
と す る ．文 体 相 違 度 𝐷𝑖𝑠𝑠𝑖𝑚(𝑃, 𝑏! )の 値 が 小 さ い ほ ど ツ イ
4.2 項 で 述 べ た 特 徴 量 抽 出 の 手 法 で は ， ユ ー ザ 独 特
ートの文体が似ていることを示す．
の特徴量を抽出することが難しい．そこで，本研究で
は 4.2 項 で 述 べ た 手 法 を 拡 張 し ， さ ら に Inverse
Document Frequency(IDF)[5] に て 重 み づ け を 行 う 手 法
を提案する．
𝐼𝑛𝑣𝑒𝑟𝑠𝑒 𝐷𝑜𝑐𝑢𝑚𝑒𝑛𝑡 𝐹𝑟𝑒𝑞𝑢𝑒𝑛𝑐𝑦 (𝐼𝐷𝐹)は ，式 (6)に て 計 算 す
る 代 表 的 な 語 の 重 み づ け 手 法 で あ る ． 𝐼𝐷𝐹に は ， 多 く
の文書に出現する語の重みを下げ，特定の文書にしか
出現しない後の重みを上げる効果がある．
𝐷
𝐼𝐷𝐹(𝑡) = 𝑙𝑜𝑔
(6)
𝑑𝑓(𝑡)
こ こ で ，𝐷は 文 書 集 合 を 表 し ，𝑑𝑓 𝑡 は 文 書 集 合 𝐷に お
𝑑𝑖𝑠𝑠𝑖𝑚!"# 𝑝! , 𝑏! = ! ∈!!" (𝑤𝑓!! )
!
! ∈!!" (𝑤𝑓!! )
(9)
𝐷𝑖𝑠𝑖𝑚 𝑃!! , 𝑏! = 𝑑𝚤𝑠𝑠𝚤𝑚 𝑝! , 𝑏!
こ こ で ， 𝑤𝑓!! と 𝑤𝑓!! は 4.3 項 に て 取 得 し た ， 𝐼𝐷𝐹重 み
づ け を 伴 っ た 文 字 {4, 5, 6}-gram の 頻 度 ベ ク ト ル を 表
す ．計 算 し た 文 体 相 違 度 𝐷𝑖𝑠𝑠𝑖𝑚(𝑃!! , 𝑏! )を 用 い て ，式 (10)
によりユーザが本人か偽物かを判定するための閾値
𝛼!! (𝑃!! , 𝐵!! )を 算 出 す る ．
(10)
𝛼!! (𝑃!! , 𝐵!! ) = 𝜕!! ∙ 𝐷𝚤𝑠𝑠𝚤𝑚(𝑃!! , 𝑏! )
式 (10)に お け る 𝜕!! は ，0.5〜 1.5 の 間 で 0.1 ず つ 変 化 さ
せユーザごとに最適な値を実験で求める．
から，代表的な語の重み付け手法として採用されてい
5. 評 価 実 験
文書を特徴づける単語に重みを与える．このような用
(8)
! ∈!!" 𝑤𝑓!! ∙ 𝑤𝑓!!
け る 語 𝑡の 文 書 頻 度 を 表 す ． 𝐼𝐷𝐹は 簡 潔 さ と ロ バ ス ト 性
る ． 𝐼𝐷𝐹は 多 数 の 文 書 集 合 が 存 在 す る と き そ れ ぞ れ の
!
本節では，提案手法の有効性を評価実験にて示す．
5.1. 評 価 方 法
途 に IDF を 利 用 す る ，単 語 n-gram は ，連 続 す る 単 語 の
本研究では，認証技術の評価手法として一般的に使
繋がりが不自然であるほど文書頻度が小さくなる．し
用 さ れ る Equal Error Rate (EER)に よ り 評 価 を 行 う ．
た が っ て ， 単 語 n-gram に 𝐼𝐷𝐹を 適 用 し て し ま う と ， 不
EER と は False Acceptance Rate(FAR)と False Rejection
自 然 な 繋 が り の 単 語 n-gram に 大 き な 重 み を 与 え る こ
Rate (FRR)が 等 し く な る 点 に お け る エ ラ ー 率 で あ る ．
とになってしまう．このため，一般的な特徴量という
𝐹𝐴𝑅と は ， シ ス テ ム が 間 違 っ て 偽 物 を 受 け 入 れ て し ま
意 味 で は ，単 語 n-gram に IDF を 適 用 す る こ と は 難 し い ．
う 割 合 で あ る ． 𝐹𝑅𝑅と は ， シ ス テ ム が 間 違 っ て 本 人 を
しかし，本研究の場合，不自然な単語の繋がりをユー
拒 否 し て し ま う 割 合 で あ る 𝐹𝐴𝑅と FRR は そ れ ぞ れ 式
ザ独特の特徴量として捉えることができるため，不自
ユーザ独特の特徴量に対して重みを与える手法を提案
(11)及 び 式 (12)に て 計 算 す る ．
𝑇𝐴
(11)
𝐹𝐴𝑅 = 𝑇𝐴 + 𝐹𝐴
𝐹𝑅
(12)
𝐹𝑅𝑅 =
𝐹𝑅 + 𝑇𝑅
𝑇𝐴は True Acceptance つ ま り 本 人 を 正 し く 受 け 入
する．
れ る こ と が で き た 数 を 示 す ． 𝐹𝐴は False Acceptance つ
然 な 単 語 の 繋 が り に 対 し て 大 き な 重 み を 与 え る 𝐼𝐷𝐹は
ユーザの特徴をより浮彫にする．したがって，本研究
で は ， 文 字 n-gram に 対 し て ， 𝐼𝐷𝐹を 適 用 す る こ と で ，
本 研 究 で は ， 𝐷を ツ イ ー ト の 集 合 と し ， 𝑑𝑓(𝑡)を ツ イ
ま り 偽 物 を 間 違 っ て 受 け 入 れ て し ま っ た 数 を 示 す ．𝐹𝑅
ー ト 集 合 𝐷に お け る 文 字 n-gram 𝑡の 文 書 頻 度 と し て 式
は 𝐹𝑎𝑙𝑠𝑒 𝑅𝑒𝑗𝑒𝑐𝑡𝑖𝑜𝑛つ ま り 間 違 っ て 本 人 を 拒 否 し て し ま
(6)の 𝐼𝐷𝐹を 計 算 す る ．そ し て ，計 算 し た 𝐼𝐷𝐹(𝑡)を 使 用 し ，
っ た 数 を 示 す ． 𝑇𝑅は 𝑇𝑟𝑢𝑒 𝑅𝑒𝑗𝑒𝑐𝑡𝑖𝑜𝑛つ ま り 正 し く 偽 物 を
3.2 節 で 計 算 し た 頻 度 ベ ク ト ル 𝑓に 式 (7)に 従 い 重 み づ
拒 否 で き た 数 を 示 す ． 𝐹𝐴𝑅が 高 い と シ ス テ ム の 信 頼 性
け を 行 う ． 計 算 し た 重 み づ け 頻 度 ベ ク ト ル 𝑤𝑓と す る ．
𝑤𝑓(𝑡) = 𝑓 ∙ 𝐼𝐷𝐹 𝑡 (7)
が 揺 ら ぎ ， 𝐹𝑅𝑅が 高 い と シ ス テ ム の 利 便 性 が 下 が っ て
し ま う ．し た が っ て ，𝐹𝐴𝑅と 𝐹𝑅𝑅は 互 い に ト レ ー ド オ フ
の 関 係 に あ る た め ，𝐹𝐴𝑅と 𝐹𝑅𝑅が 一 致 す る 点 𝐸𝐸𝑅が 認 証
4.4. ユ ー ザ 判 定 の た め の 閾 値 計 算
技術を評価するのに最適な指標とされている．
本 項 で は ， 2.2 項 で 述 べ た 手 法 と 同 様 の 手 順 に て ，
5.2. 閾 値 の パ ラ メ ー タ 調 整
ユーザ判定のための閾値を計算する方法を説明する．
本 稿 では，4.1 項 で分 割 した閾 値 を 決 め る た め の テ ス
3.2 項 に て 分 割 し た ， 過 去 の ツ イ ー ト 集 合
ト デ ー タ 𝑇!!! を利 用 し，𝐸𝐸𝑅を 最 小 に す る 最 適 な パ ラ メ ー
𝑃!! {𝑝! , 𝑝! , … , 𝑝! , … }と 閾 値 を 決 め る た め の ベ ー ス と な る
タ 𝜕!! を 求 め る ．な お ，閾 値 を 決 め る た め の テ ス ト デ ー
ツ イ ー ト 集 合 𝐵!! {𝑏! , 𝑏! , … , 𝑏! , … }か ら ，ユ ー ザ の 真 偽 を 判
タ 𝑇!!! は 訓 練 デ ー タ の 一 部 で あ り ，最 終 的 な テ ス ト を 行
定 す る た め の 閾 値 を 計 算 す る ．文 体 相 違 度 の 計 算 に は ，
う デ ー タ を 含 ん で い な い ． 具 体 的 に は ， 式 (10)に お け
3.3 項 に て 説 明 し た 複 数 併 用 文 字 {4, 5, 6}-gram IDF を
る 𝜕!! を ， 0.5〜 1.5 の 間 で 0.1 ず つ 変 化 さ せ ユ ー ザ ご と
利 用 す る ．ツ イ ー ト 𝑏! に 対 す る ツ イ ー ト 𝑝! の 文 体 相 違 度
に最適な値を求めていく．
ユ ー ザ 𝑢! に 最 適 な パ ラ メ ー タ 𝜕!! を 実 験 的 に 求 め る 方
れば偽物と判定し，低ければ本人と判定する．なお，
法を具体的に説明する．閾値のパラメータ調整のため
𝛼!! (𝑃!! , 𝐵!! )の パ ラ メ ー タ で あ る 𝜕!! は ，5.2 節 に て ユ ー ザ
項 に て 作 成 し た 𝑇!!! を 利 用 す る ． 𝑇!!! は
ご と に 求 め た 値 を 利 用 す る ． 判 定 結 果 か ら 𝐹𝐴𝑅お よ び
の 実 験 に は ， 4.1
ユ ー ザ 𝑢! の 正 解 の デ ー タ セ ッ ト で あ る ． 不 正 解 の デ ー
𝐹𝑅𝑅を 計 算 し 平 均 値 を も っ て 最 終 的 な 𝐸𝐸𝑅と す る ．
タ セ ッ ト と し て ， ユ ー ザ 𝑢! 以 外 の ユ ー ザ の テ ス ト デ ー
5.6. 実 験 結 果
タ 𝑇!! ! を 使 用 す る ． 𝑢! は 𝑢! 以 外 の ユ ー ザ を 表 す ． 𝑇!!! と 𝑇!! !
ユ ー ザ 100 人 に 対 し て ， 5.5 項 で 説 明 し た 実 験 を 行
を 合 わ せ た 集 合 を 𝑇 ! {𝑡!! , 𝑡!! , … , 𝑡!! , … }と す る ． な お ， 𝑇 ! に
う．なお，ユーザの真偽判定に利用する閾値のパラメ
含 ま れ る 不 正 解 の デ ー タ セ ッ ト は ，𝑇!! ! か ら そ れ ぞ れ の
ー タ は ， 5.2 項 で ユ ー ザ ご と に 実 験 的 に 算 出 し た も の
ユーザに対しランダムに１つのブロックを選出したも
を 利 用 す る ． ま た ， ブ ロ ッ ク サ イ ズ は 280 文 字 ， ブ ロ
の と す る ． ま ず ， テ ス ト デ ー タ 𝑇 ! か ら 4.2 項 及 び 4.3
ッ ク 数 は 100 と し た ． 評 価 実 験 で は 提 案 す る 文 字
項 と 同 様 の 手 順 で 重 み 付 き 頻 度 ベ ク ト ル 𝑤𝑓!! を 作 成 す
n-gram IDF を 適 用 し な い 場 合 と 適 用 す る 場 合 に て 比 較
る ．式 (8)(9)を 利 用 し 過 去 ツ イ ー ト 集 合 𝑃!! に 対 す る ブ ロ
を 行 う ．Twitter ユ ー ザ 100 ア カ ウ ン ト に 対 し て 行 っ た
ッ ク 𝑡!! の 文 体 相 違 度 𝐷𝑖𝑠𝑠𝑖𝑚(𝑃!! , 𝑡!! )を 計 算 す る ．計 算 し た
実験結果を表に示す．
𝐷𝑖𝑠𝑠𝑖𝑚(𝑃!! , 𝑡!! )が 閾 値 𝛼!! (𝑃!! , 𝐵!! )よ り 高 け れ ば 偽 物 と 判
定 し ，低 け れ ば 本 人 と 判 定 す る ．こ の 際 ，閾 値 𝛼!! (𝑃!! , 𝐵!! )
に お け る パ ラ メ ー タ 𝜕!! の 値 を 0.5〜 1.5 の 間 で 0.1 ず つ
変 化 さ せ る ． パ ラ メ ー タ を 変 化 さ せ る こ と で ， 𝐹𝐴𝑅お
よ び 𝐹𝑅𝑅の 値 が 変 化 す る 𝐹𝐴𝑅と 𝐹𝑅𝑅が 一 致 す る 点 に 最
も 近 い パ ラ メ ー タ を 最 適 な パ ラ メ ー タ 𝜕!! と す る ．
5.3. 提 案 手 法 を 評 価 す る た め の デ ー タ セ ッ ト
評 価 実 験 に は ，4.1 項 に て 作 成 し た テ ス ト デ ー タ 𝑇!! を
利 用 す る ．𝑇!! は ユ ー ザ 𝑢! の 正 解 の デ ー タ セ ッ ト で あ る ．
不 正 解 の デ ー タ セ ッ ト と し て ， ユ ー ザ 𝑢! 以 外 の ユ ー ザ
の テ ス ト デ ー タ を 使 用 す る ． ユ ー ザ 𝑢! の テ ス ト デ ー タ
と ユ ー ザ 𝑢! 以 外 の ユ ー ザ の テ ス ト デ ー タ を 合 わ せ た 集
合 を 𝑇{𝑡! , 𝑡! , … , 𝑡! , … }と す る ． な お ， 𝑇に 含 ま れ る 不 正 解
の デ ー タ セ ッ ト は ， ユ ー ザ 𝑢! 以 外 の ユ ー ザ の テ ス ト デ
表 1 提 案 手 法 の 実 験 結 果
手法
文 字 n-gram IDF を 適 用 し な い 場 合
文 字 n-gram IDF を 適 用 す る 場 合
𝐸𝐸𝑅
0.291
0.127
文 字 n-gram IDF を 適 用 す る こ と で ， 𝐸𝐸𝑅を 0.164 低
下させることができた．
6. ま と め
本 稿 で は ， 既 存 の Twitter に お け る ス パ ム ツ イ ー ト
検出手法を拡張し，アクティブ認証に応用しエラー率
を低下させる手法を提案した，具体的には，単純な
n-gram に よ る 特 徴 抽 出 に 対 し ， 𝐼𝐷𝐹を 利 用 し た 重 み づ
け を 行 う 手 法 を 提 案 し た ． 𝐼𝐷𝐹を 利 用 し た 重 み づ け に
ータからそれぞれのユーザに対しランダムに１つのブ
よりユーザ独特の特徴量が抽出でき，アクティブ認証
ロックを選出したものとする．
のエラー率低下に繋がった．
5.4. ユ ー ザ 判 定 方 法
テ ス ト デ ー タ の 集 合 𝑇の そ れ ぞ れ の ブ ロ ッ ク に 対 し
て ， 4.2 項 及 び 4.3 項 の 手 法 を 利 用 し ， 重 み づ け 頻 度
ベ ク ト ル 𝑤𝑓(𝑡! )を 作 成 す る ．式 (8)(9)を 利 用 し ，過 去 ツ
イ ー ト 集 合 𝑃!! に 対 す る ブ ロ ッ ク 𝑡! の 文 体 相 違 度
𝐷𝑖𝑠𝑠𝑖𝑚(𝑃!! , 𝑡! )を 計 算 す る ．計 算 し た 𝐷𝑖𝑠𝑠𝑖𝑚(𝑃!! , 𝑡! )が 閾 値
𝛼!! (𝑃!! , 𝐵!! )よ り 高 け れ ば 偽 物 と 判 定 し ，低 け れ ば 本 人 と
判定する．
5.5. 提 案 手 法 の 評 価 方 法
提 案 手 法 の 評 価 実 験 に は ，4.1 項 に て 作 成 し た テ ス ト
デ ー タ 𝑇!! を 利 用 す る ． 𝑇!! は ユ ー ザ 𝑢! の 正 解 の デ ー タ セ
ッ ト で あ る ．不 正 解 の デ ー タ セ ッ ト と し て ，ユ ー ザ 𝑢! 以
外 の ユ ー ザ の テ ス ト デ ー タ 𝑇!! を 使 用 す る ． 𝑢! は 𝑢! 以 外
の ユ ー ザ を 表 す ． 𝑇!! と 𝑇!! を 合 わ せ た 集 合 を
𝑇{𝑡! , 𝑡! , … , 𝑡! , … }と す る ． ま ず ， テ ス ト デ ー タ 𝑇か ら 4.2
項 及 び 4.3 項 と 同 様 の 手 順 で 重 み 付 き 頻 度 ベ ク ト ル
𝑤𝑓! を 作 成 す る ． 式 (8)(9)を 利 用 し 過 去 ツ イ ー ト 集 合 𝑃!!
に 対 す る ブ ロ ッ ク 𝑡! の 文 体 相 違 度 𝐷𝑖𝑠𝑠𝑖𝑚(𝑃!! , 𝑡! )を 計 算
す る ．計 算 し た 𝐷𝑖𝑠𝑠𝑖𝑚(𝑃!! , 𝑡! )が 閾 値 𝛼!! (𝑃!! , 𝐵!! )よ り 高 け
今後の課題として，ブロックサイズを短くすること
が挙げられる．ブロックサイズを短くすることで，短
い間隔での連続的な認証が可能となる．
参 考 文 献
[1] Brocardo, Marcelo Luiz, Issa Traore, and Isaac
Woungang, "Authorship verification of e-mail and
tweet
messages
applied
for
continuous
authentication", Journal of Computer and System
Sciences, Vol. 81, No. 8, pp.1429-1440, 2014.
[2] T. Mitchell. Machine Learning. McGraw-Hill, New
York, 1997.
[3] Cover, Thomas M., and Joy A. Thomas. "Entropy,
relative entropy and mutual information" Elements of
Information Theory, New York: Wiley, pp. 12-49,
1991.
[4] 上 里 和 也 ， 奥 谷 貴 志 ， 浅 井 洋 樹 ， 奥 野 峻 弥 ， 田 中
正 浩 ， 山 名 早 人 ， “文 体 及 び ツ イ ー ト 付 随 情 報 を
用 い た 乗 っ 取 り ツ イ ー ト 検 出 “， 情 報 処 理 学 会 研
究 報 告 ，デ ー タ ベ ー ス・シ ス テ ム 研 究 会 報 告 ， Vol.
158, No. 21, pp. 1-8, 2013.
[5] Salton, Gerard, Anita Wong, and Chung-Shu Yang,
"A vector space model for automatic indexing",
Communications of the ACM, Vol.18, No.11, pp.
613-620, 1975.
[6] Vapnik, Vladimir Naumovich, “Estimation of
dependences based on empirical data”, New York:
Springer-verlag, Vol. 40, 1982.
[7] 奥 野 峻 弥 ， 浅 井 洋 樹 ， 山 名 早 人 ，“ マ イ ク ロ ブ ロ
グ を 対 象 と し た 著 者 推 定 手 法 の 提 案 -10,000 人 レ
ベ ル で の 著 者 推 定“ ，情 報 処 理 学 会 研 究 報 告 ，デ
ー タ ベ ー ス・シ ス テ ム 研 究 会 報 告 ，Vol. 115, No. 12,
pp.1-6, 2014.
[8] 井 上 雅 翔 ，山 名 早 人 ，”大 規 模 候 補 者 群 に 対 す る
著 者 推 定 手 法 の 提 案 と 評 価 ”，DEIM，C6-6, 2013．