DEIM Forum 2016 E6-3
Locality-Sensitive Hashing を用いた大規模な著者推定の高速化
田中
博己
†1石山 雄大
†2上里 和也
†2山名 早人
†3†4†1 早稲田大学基幹理工学部 〒169-8555 東京都新宿区大久保 3-4-1
†2 早稲田大学大学院基幹理工学研究科 〒169-8555 東京都新宿区大久保 3-4-1
†3 早稲田大学理工学術院 〒169-8555 東京都新宿区大久保 3-4-1
†4 国立情報学研究所 〒101-8430 東京都千代田区一ツ橋 2-1-2
E-mail: {mizurin, k.uesato, ishiyama, yamana}@yama.info.waseda.ac.jp
あらまし インターネット上で行われる犯罪捜査を行うために，近年Web コンテンツを対象とした著者推定の研究が盛んに 行われている．しかし，Web コンテンツを対象とした著者推定では，従来の論文や小説を対象とした著者推定と比べて対象とな る著者の数が多いことから，著者数を𝑛とすると，推定の所要時間が𝑂(𝑛)と長くなる．そのため，大規模著者群に対して著者推 定を行うためには，精度を可能な限り落とさず高速に推定できるアルゴリズムが必要となる．そこで本研究では，高速な近似近 傍探索を可能にする Locality-Sensitive Hashing (LSH)を用いて推定対象の候補者を絞ることで大規模著者群に対しても著者推定 を高速に行う手法を提案する．マイクロブログを対象とした10,000 人規模の比較実験を行った結果，既存研究と比べ，p@1 が 5.8%低下する代わりに，実行時間を 54.7%削減することに成功した．以上から，本手法をリカーシブに適用すると，ある時間 T が与えられると，その時間T 内で最適な結果を返し，時間 T 以降も候補者の推定精度を，時間の経過とともに向上させるシス テムの制作が可能になると考えられる． キーワード Twitter，著者推定
1. は じ め に
近 年 ， イ ン タ ー ネ ッ ト を 利 用 し た 犯 行 予 告 な ど の サ イ バ ー 犯 罪 が 社 会 問 題 と な っ て い る ． サ イ バ ー 犯 罪 等 に 関 す る 相 談 件 数 は 平 成 26 年 で 118,100 件 と ，平 成 25 年 の 85,863 件 と 比 べ 39.2％ も 増 加 し て い る [1]． こ の よ う に サ イ バ ー 犯 罪 に つ い て 社 会 的 な 不 安 が 高 ま っ て い る と い え る ． サ イ バ ー 犯 罪 捜 査 の 難 し い 点 に は ， イ ン タ ー ネ ッ ト の 匿 名 性 が 高 い た め に 犯 人 特 定 が 困 難 な こ と が 挙 げ ら れ る ． サ イ バ ー 犯 罪 捜 査 で 広 く 用 い ら れ て い る も の に IP ア ド レ ス が あ る ． し か し ， IP ア ド レ ス を 他 の 値 に な り す ま す こ と は 容 易 な こ と で あ り ，IP ア ド レ ス の 偽 装 に よ る 他 人 へ の な り す ま し も 可 能 で あ る ．現 に 真 犯 人 が IP ア ド レ ス を 偽 装 し た こ と に よ る 誤 認 逮 捕 も 起 き て い る[2]．そ こ で ，サ イ バ ー 犯 罪 捜 査 に は IP ア ド レ ス の み な ら ず ，よ り 偽 装 が 困 難 な 証 拠 を 併 用 す る 必 要 性 が あ る ． そ の た め 近 年 で は ，Web コ ン テ ン ツ を 対 象 と し た コ ン テ ン ツ の 著 者 を 特 定 す る 著 者 推 定 の 研 究 が 盛 ん に 行 わ れ て い る ．著 者 推 定 の 研 究 で は ， 各 個 人 の 文 章 ス タ イ ル を 表 す 文 体 を 利 用 し て 推 定 が 行 わ れ る ．文 体 は 個 々 人 で 特 徴 が 現 れ る[3]た め ，他 人 の 文 体 の 真 似 は し に く い と 言 え る ． そ の た め ， 犯 罪 捜 査 に 著 者 推 定 を 利 用 す る こ と で ， 犯 人 の 特 定 が 行 い や す く な る と 考 え ら れ る ． 従 来 行 わ れ て き た 小 説 や 論 文 を 対 象 に し た 著 者 推 定 に 比 べ ，Web コ ン テ ン ツ を 対 象 と し た 著 者 推 定 は 候 補 者 と な る 著 者 が 多 い ．Web コ ン テ ン ツ を 対 象 と し た 著 者 推 定 に 関 す る 研 究 で は ， 著 者 推 定 の 際 ， 推 定 対 象 候 補 者 全 員 の デ ー タ を 比 較 し て い る ． そ の た め ， 一 人 の 著 者 を 推 定 す る 際 に ， 推 定 対 象 と な る 候 補 者 の 人 数 を𝑛人 と し た と き に ，計 算 量 は 𝑂(𝑛)と な る ．こ の こ と は 𝑛の 値 が 小 さ い 時 は そ れ ほ ど 問 題 に は な ら な い が ，𝑛の 値 が 大 き く な る と 計 算 時 間 が 膨 大 に な る こ と を 意 味 す る ． そ れ ゆ え ， 精 度 を 落 と さ ず に 著 者 推 定 を 高 速 に 行 う ア ル ゴ リ ズ ム が 必 要 と な る ． こ れ ま で の 研 究[4]で は ，あ る 著 者 を 推 定 す る た め に ， 全 員 を 候 補 者 と し て 類 似 度 を 計 算 し ， 類 似 度 が 一 番 高 い 候 補 者 を 抽 出 し て い る ． 本 研 究 で は ， こ の 著 者 推 定 を 高 速 化 す る た め に ， ま ず 推 定 対 象 の 候 補 者 の 数 を 絞 る ．そ し て ，絞 っ た あ と の 候 補 者 群 に 対 し て[4]と 同 様 な 著 者 推 定 を 行 う こ と を 提 案 す る ． 具 体 的 に は ， 推 定 対 象 の 候 補 者 を 絞 る た め に ， 高 速 な 近 似 近 傍 探 索 問 題 を 可 能 に す る Locality-Sensitive Hashing (LSH)[5]を 用 い る ． こ の 手 法 を 用 い る こ と に よ っ て ， 推 定 し た い ユ ー ザ の デ ー タ と 類 似 度 が 高 い 候 補 者 の み を 入 手 す る こ と が 可 能 に な る ． そ の 後 ， テ ス ト デ ー タ と 類 似 度 が 高 い 候 補 者 の 中 で の み ， 既 存 手 法 と 同 様 に 著 者 推 定 を 行 う ． こ れ ら の 手 法 に よ り ， 推 定 対 象 の 著 者 を 絞 っ た 後 に ， 最 も 正 解 で あ る 可 能 性 が 高 い 著 者 を 推 定 す る こ と が で き る ． 本 研 究 で は ，代 表 的 なWeb コ ン テ ン ツ で あ る Twitter を 実 験 デ ー タ と し て 利 用 す る ．そ し て ，LSH で 候 補 と な る 著 者 を 絞 っ た 提 案 手 法 と ， 既 存 手 法 で 著 者 推 定 の 精 度 と 計 算 時 間 を 比 較 し ， 本 研 究 の 有 用 性 を 示 す ． 本 稿 で は 以 下 の 構 成 を 取 る ．2 節 で 関 連 研 究 に つ い て 述 べ る ．3 節 で 提 案 手 法 に つ い て 述 べ た あ と ，4 節 で 評 価 実 験 を 行 う ． 最 後 に5 節 で ま と め る ．2. 関 連 研 究
本 節 で は ，2.1 項 で 著 者 推 定 に 関 す る 関 連 研 究 ， 2.2 項 で 近 似 領 域 探 索 問 題 に 関 す る 関 連 研 究 を 述 べ る ．2.1. 著 者 推 定 に関 する関 連 研 究
著 者 推 定 と は ， 未 知 で あ る 文 章 の 著 者 を 著 者 候 補 者 群 か ら 推 定 す る こ と で あ る ． 日 本 に お け る 著 者 推 定 は 計 量 文 体 学 の 一 分 野 と し て 扱 わ れ て い た[3]．計 量 文 体 学 に お け る 著 者 推 定 で は ， 文 体 を 文 章 間 で 比 較 す る こ と で ， 著 者 を 定 量 的 に 推 定 し た ． 文 体 と は ， 各 個 人 の 文 章 ス タ イ ル を 表 す も の で あ る ． 文 章 ス タ イ ル に は 語 彙 の 選 び 方 や ， 句 読 点 の 打 ち 方 ， 文 章 の 構 成 方 法 が 挙 げ ら れ る ． テ キ ス ト マ イ ニ ン グ を 利 用 す る 前 の 著 者 推 定 で は ， そ れ ら の 文 体 を 人 力 で 比 較 し て い た ． 従 来 の 手 動 に よ る 比 較 で は ， 小 説 や 論 文 の 著 者 を 数 人 規 模 で し か 比 較 す る こ と が で き な か っ た ． し か し ， 近 年 に お け る コ ン ピ ュ ー タ の 発 達 に よ り ， 長 い 文 章 で の 比 較 が 可 能 と な り ， よ り 大 規 模 な 著 者 群 に 対 し 推 定 す る こ と が で き る よ う に な っ た ． ま た ， イ ン タ ー ネ ッ ト の 発 達 に 伴 い ，小 説 や 論 文 だ け で は な く Web コ ン テ ン ツ を 対 象 と し た 著 者 推 定 が 盛 ん に 行 わ れ て い る ． テ キ ス ト マ イ ニ ン グ を 利 用 し た 著 者 推 定 手 法 は ， Stamatatos ら [6] に よ る と ， Profiled-Based Approach(PBA)と Instance-Based Approach (IBA)の 2 つ の 手 法 に 分 類 さ れ る ．2.1.1. PBA に よ る 著 者 推 定
PBA に よ る 著 者 推 定 は ，事 前 に 用 意 さ れ て い る 候 補 者 の 文 章 群 と ， 推 定 対 象 文 章 と の 間 で 文 体 の 相 違 度 を 比 較 す る も の で あ る[4]．比 較 さ れ た 候 補 者 の 文 章 群 と 最 も 文 体 が 類 似 し て い る も の を 推 定 候 補 者 と し て 出 力 す る ．図 1 は PBA に よ る 著 者 推 定 の 概 略 図 で あ る ．具 体 的 に は 以 下 の よ う に 行 う ． 1. 候 補 者 の 文 章 群 全 て と 推 定 対 象 文 章 の そ れ ぞ れ に 対 し て 定 量 化 を 行 う ．図1 に お け る 𝑥&, 𝑥(は ， そ れ ぞ れ 既 知 の 著 者 A の 全 て の 文 章 ，既 知 の 著 者 B の 全 て の 文 章 を 定 量 化 し た も の ，𝑥)は 未 知 の 著 者 の 文 章 を 定 量 化 し た も の を 意 味 す る ． 2. 候 補 者 そ れ ぞ れ の 文 章 と ，推 定 対 象 の 文 章 そ れ ぞ れ に 対 し て 文 体 相 違 度 を 計 算 す る ． 文 体 相 違 度 と は ，2 つ の 文 章 群 の 間 で ど の 程 度 文 体 が 異 な っ て い る か を 定 量 的 に 表 現 し た も の で あ る ． 図 1 で は ， 推 定 モ デ ル の 部 分 に お い て 文 体 相 違 度 の 計 算 を 行 う ． 文 体 相 違 度 の 計 算 方 法 は 著 者 推 定 手 法 に よ っ て 異 な る ． 3. 2.で 求 め た 文 体 相 違 度 が 小 さ い 順 に 候 補 者 を ソ ー ト す る ． 4. 並 び 替 え た 結 果 ，1 位 で あ る 候 補 者 を 推 定 対 象 の 著 者 と し て 出 力 す る ． 図 1 PBAに よ る 著 者 推 定 ([6]FIG.1よ り ト レ ー ス)2.1.2. Ragel ら の 手 法
Ragel ら [8]は ， SMS に 投 稿 さ れ た 70 人 の 文 章 を 対 象 に 著 者 推 定 を ，PBA を 利 用 し て 行 っ て い る ．特 徴 量 と し て 単 語 N-gram を 利 用 し ， 式 (1)(2)に よ っ て 文 章 の 類 似 度 を 計 算 し て い る ．な お ，式(1)(2)に お け る𝐴+, 𝐵+は そ れ ぞ れ ベ ク ト ル𝑨, 𝑩の 𝑖番 目 の 要 素 を 表 す ． l コ サ イ ン 類 似 度 𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑡𝑦 = cos 𝜃 = 𝛴+=> ? 𝐴 +𝐵+ 𝛴+=>? 𝐴+@ 𝛴+=>? 𝐵+@ (1) l ユ ー ク リ ッ ド 距 離 𝐸𝑢𝑐𝑙𝑖𝑑𝑒𝑎𝑛 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 𝛴+=>? 𝐴+− 𝐵+ @ (2) Regal ら に よ る と ， コ サ イ ン 類 似 度 を 利 用 し て 比 較 し た 場 合 の 方 が 精 度 を 高 く で き ，p@1 で 40%程 度 で あ る ．し か し な が ら ，推 定 候 補 者 数 が 70 人 程 度 と ，大 規 模 著 者 推 定 と し て 扱 う た め に は 規 模 が 小 さ い ．2.1.3. 奥 野 ら の 手 法
奥 野 ら[4]は ， Twitter に 投 稿 さ れ た 文 章 を 利 用 し た 100,000 人 レ ベ ル の 候 補 者 群 に 対 す る 著 者 推 定 を ，PBA を 利 用 し て 行 っ て い る ．文 体 定 量 化 方 法 は 文 字n-gram 頻 度 分 布 を 利 用 し て い る ．ま た ，文 体 相 違 度 計 算 に は ， コ サ イ ン 類 似 度 を 用 い て い る 文 体 定 量 化 方 法 奥 野 ら は ， 著 者 推 定 に お け る 文 体 定 量 化 に 文 字 n-gram 頻 度 分 布 を 利 用 し て い る ． 複 数 併 用 文 字 {1,2,3}-gram を 利 用 し て い る ． そ の 際 ， 少 な い 情 報 か ら よ り 多 く の 情 報 を 取 得 す る た め に ，n-gram の n に 応 じ て 重 み 付 け を 行 う ．一 般 に ，文 章 か らn-gram を 取 得 す る 場 合 ，n-gram の n が 大 き く な る ほ ど ，頻 度 は 小 さ く な る ．一 方 で ，文 字n-gram の n が 大 き い 場 合 ，著 者 の 特 徴 語 を 表 す 未 知 語 を 取 得 で き る 可 能 性 が 高 い た め で あ る ． Twitter の メ ッ セ ー ジ に 対 す る 著 者 推 定 を 行 う 場 合 ， 各 デ ー タ セ ッ ト に 含 ま れ る メ ッ セ ー ジ の 話 題 を 統一 す る こ と が で き な い 問 題 が あ る ． そ の た め ， 文 体 相 違 度 の 計 算 に 用 い る デ ー タ セ ッ ト と 学 習 デ ー タ セ ッ ト の 話 題 は 異 な る と 考 え ら れ る ． し か し ， 異 な る 話 題 間 で の 著 者 推 定 の 精 度 は 低 下 す る こ と が わ か っ て い る [13]． そ の た め ， ユ ー ザ 毎 に ツ イ ー ト 時 刻 が 異 な る 複 数 の 学 習 デ ー タ セ ッ ト を 用 意 し ， テ ス ト デ ー タ セ ッ ト 比 較 す る 際 に ， よ り 類 似 す る 話 題 分 布 と の 比 較 が で き る よ う 工 夫 し て い る ． 文 体 相 違 度 計 算 方 法 奥 野 ら に よ る 文 体 相 違 度 の 計 算 は ， 文 章 p， 文 章 q に お け る 文 字 n-gram の 集 合 を 指 す 𝑫𝒑= {𝒅𝒑𝟏, 𝒅𝒑𝟐… , 𝒅𝒑 𝑪𝒑𝒒}， 𝑫𝒒= {𝒅𝒒𝟏, 𝒅𝒒𝟐… , 𝒅𝒒 𝑪𝒑𝒒}だ け で な く ， 𝑘も 利 用 す る ． 𝐶TUと は 文 章 p と 文 章 q の 各 々 に 存 在 す る 全 て の 文 字 n-gram の 和 集 合 で あ る ．𝑘と は ， 1 つ の デ ー タ セ ッ ト に 含 ま れ る ツ イ ー ト 数 の こ と で あ る ． 以 上 の 定 義 を 利 用 し て ，2 つ の 文 章 p, q に お け る 文 体 相 違 度 を 式(3)(4)(5)に よ り 定 義 し て い る ． 𝐷𝑖𝑠𝑠𝑖𝑚WXY 𝑝, 𝑞 = 𝛴+∈]^_ 𝑓T+ @ 𝛴+∈]^_ 𝑓U+ @ 𝛴+∈]^_𝑓T+∙ 𝑓U+ (3) 𝑓T+= 0.4 (𝑓T+e > 0.4) 𝑓T+e (𝑓T+e ≤ 0.4) (4) 𝑓T+e = 𝑑T+ 𝑘 (5) 文 体 相 違 度𝐷𝑖𝑠𝑠𝑖𝑚WXY 𝑝, 𝑞 は ， そ の 値 が 小 さ い ほ ど 2 つ の 文 章𝑝, 𝑞の 文 体 が 似 て い る こ と を 示 す ． こ の 研 究 で は 100,000 人 の Twitter ユ ー ザ に 対 し て MRR0.646 を 達 成 し て い る が ， 一 人 の 著 者 を 推 定 す る の に ，100,000 人 と 文 体 相 違 度 を 比 較 す る 必 要 が あ る ． そ の た め ， 推 定 の 計 算 に 時 間 が か か っ て し ま う ． 文 体 相 違 度 の 計 算 の 実 行 時 間 は ， Six-Core AMD OpteronTM8425HE*8i (44 ス レ ッ ド ) を 用 い て ， 平 均 43,272 秒（ 10 万 人 か ら テ ス ト ユ ー ザ と し て 選 ん だ 1 万 人 に 対 す る 推 定 に か か っ た 延 べ 時 間 ） か か っ て い る ． す な わ ち ，1 人 の 著 者 の 推 定 に 平 均 4.3 秒 か か っ て い る ．
2.1.4. IBA に よ る 著 者 推 定
IBA に よ る 著 者 推 定 は ， 事 前 に 用 意 さ れ て い る 候 補 者 の 文 章 群 で 分 類 器 を 生 成 し ， 機 械 学 習 に よ っ て 図 2 の よ う に 分 類 を 行 う ．具 体 的 に は 以 下 の 手 順 で 行 う ． 1. 候 補 者 の 文 章 群 全 て と 推 定 対 象 文 章 の そ れ ぞ れ に 対 し て 定 量 化 を 行 う ．𝑥&>, 𝑥&@, 𝑥&hは 既 知 の 著 者A の 文 章 を そ れ ぞ れ 定 量 化 し た も の ，𝑥(>, 𝑥(@は 既 知 の 著 者 B の 文 章 を そ れ ぞ れ 定 量 化 し た も の を 表 し ， 𝑥)は 未 知 の 著 者 の 文 章 を 定 量 化 し た も の を 表 す ． 2. 定 量 化 さ れ た 候 補 者 の 文 章 群 に よ っ て 分 類 器 を 生 成 す る ． 分 類 器 の 生 成 方 法 は 著 者 推 定 の 手 法 に よ っ て 異 な る ． 3. 定 量 化 さ れ た 推 定 対 象 文 章 を 分 類 器 に 入 力 す る ． 図 2 に お け る 入 力 は 推 定 モ デ ル に 対 応 す る ． 図 2 IBAに よ る 著 者 推 定 ([6]FIG.2よ り ト レ ー ス)
2.1.5. Narayanan ら の 手 法
Narayanan ら [7]は ，100,000 人 の ブ ロ グ を 対 象 と し て ， IBA に 基 づ く 著 者 推 定 を 行 っ た ． Narayanan ら は ， 文 体 定 量 化 の 方 法 に ，以 下 の 表1 に 示 さ れ る 10 種 類 の 特 徴 量 を 使 用 し て い る ． そ れ ぞ れ の 特 徴 量 を 正 規 化 す る た め に ，0 で あ る も の 以 外 の 特 徴 量 の 平 均 値 で 割 っ た ． Narayanan ら は ， こ れ ら の 特 徴 量 を 利 用 し ， 複 数 の 分 類 器 に よ っ て 著 者 推 定 を 行 っ た ． こ の 時 ，2-NN と RLSC を 組 み 合 わ せ た 分 類 器 を 利 用 し た 際 に 最 も precision が 高 く な り ，p@1 で 約 20％ の 精 度 で あ っ た と 報 告 し て い る ． Narayanan ら の 研 究 結 果 PBA に よ る 著 者 推 定 手 法 と 比 較 す る と ， 推 定 精 度 が あ ま り 高 く な い ．Narayanan ら の よ う に IBA を 利 用 し た 著 者 推 定 で は ，不 均 衡 デ ー タ に 対 し て 機 械 学 習 を 行 っ て い る ． 不 均 衡 デ ー タ に 対 す る 機 械 学 習 は う ま く い か な い た め ， 精 度 を あ ま り 高 く す る こ と が で き な い ．2.1.6. 著 者 推 定 手 法 の ま と め
IBA と PBA を 利 用 し た 著 者 推 定 の 手 法 を そ れ ぞ れ 説 明 し た ． 本 研 究 の 目 的 で あ る 大 規 模 著 者 推 定 の 高 速 化 に 適 し た 手 法 に IBA は 適 し て い な い と 考 え ら れ る ． IBA を 利 用 し た 著 者 推 定 で は ， あ る 特 定 の 候 補 者 １ 人 の 文 章 を 正 例 と し ， そ れ 以 外 の 多 数 の 候 補 者 の 文 章 を 負 例 と す る ． し た が っ て ， 正 例 と 負 例 の 数 に 大 き な 差 が あ る デ ー タ セ ッ ト(不 均 衡 デ ー タ )が 生 ま れ る ． 不 均 衡 デ ー タ を 利 用 し た 機 械 学 習 は 上 手 く 機 能 し な い と 報 告 さ れ て い る ． し た が っ て ， 著 者 推 定 で 扱 う 学 習 デ ー タ セ ッ ト が 大 き く な る ほ ど 精 度 が 下 が っ て し ま う ． 実 際 に ， 大 規 模 な 著 者 推 定 に 対 し て の 精 度 を 比 較 す る と ，IBA よ り も PBA の 方 が 高 い 精 度 で 推 定 を 行 う こ と が 可 能 で あ る ． 奥 野 ら の 手 法 は 100,000 人 規 模 の 推 定 に お い て ，MRR0.646 と 関 連 研 究 と 比 べ 高 い 精 度 を 達 成 し て い る ． し た が っ て ， 本 研 究 で は 奥 野 ら の 手 法 を ベ ー ス に 高 速 化 す る 手 法 を 提 案 す る ．2.2. 近 似 領 域 探 索 問 題 の関 連 研 究
領 域 探 索 問 題 と は ， ク エ リ を 中 心 と し た あ る 一 定 の 範 囲 に 含 ま れ る デ ー タ を 全 て 取 得 す る 問 題 で あ る ． し か し ， 領 域 探 索 問 題 は 近 傍 探 索 問 題 と 同 様 に ， 高 次 元 に な る に つ れ て 計 算 量 が 指 数 的 に 増 大 す る ．そ の た め ， 高 速 に 検 索 す る 手 法 が 必 要 に な る ． そ こ で ， 近 似 的 な 領 域 探 索 を 行 う 近 似 領 域 探 索 問 題 を 解 く こ と で ， 高 速 な 検 索 を 実 現 す る ． 近 似 領 域 探 索 問 題 で は ， 近 似 近 傍 探 索 問 題 と 同 様 に 若 干 の 誤 判 定 を 許 容 す る こ と で 高 速 な 探 索 を 実 現 す る ．Locality-Sensitive Hashing (LSH)は ハ ッ シ ュ 関 数 を 利 用 し て 近 似 近 傍 探 索 問 題 を 達 成[9] す る ．LSH で 用 い ら れ る ハ ッ シ ュ 関 数 は「 距 離 が 近 い 入 力 同 士 は 高 い 確 率 で 衝 突 す る 」 と い う 性 質 を 持 っ て い る ． そ の 時 の ハ ッ シ ュ 関 数 を 以 下 の よ う に 定 義 す る ． l 任 意 の 点𝒑, 𝒒𝜖𝐑kに 対 し て ，𝑑 𝒑, 𝒒 ≤ 𝑟な ら ば Pr ℎ 𝒑 = ℎ 𝒒 ≥ 𝑃> l 任 意 の 点𝒑, 𝒒𝜖𝐑kに 対 し て ，𝑑 𝒑, 𝒒 > 𝑟な ら ば Pr ℎ 𝒑 = ℎ 𝒒 ≤ 𝑃@ l 𝑃>≥ 𝑃@で あ る こ こ で𝑑 𝒑, 𝒒 は 元 デ ー タ に よ っ て 定 義 さ れ た 2 点 間 の 距 離 関 数 を 表 し ，Pr ℎ 𝒑 = ℎ 𝒒 は ℎ 𝒑 = ℎ 𝒒 が 成 り 立 つ 時 の 確 率 を 表 す ． コ サ イ ン 類 似 度 を 2 点 間 の 距 離 関 数 と す る 場 合 ， 元 の ベ ク ト ル𝒖に 対 し て 同 一 次 元 数 の 単 位 ラ ン ダ ム ベ ク ト ル𝒓を 用 い て ， 式 (6)の ハ ッ シ ュ 関 数 を 定 義 す る [10]． ℎs 𝒖 = 1 (𝒖 ∙ 𝒓 ≥ 0) 0 (𝒖 ∙ 𝒓 < 0) (6) 式(6)に て 計 算 す る ハ ッ シ ュ 関 数 を 定 義 し た 時 ，ベ ク ト ル𝒑と ベ ク ト ル 𝒒に 関 し て 式 (7)が 成 立 す る ． Pr ℎ 𝒑 = ℎ 𝒒 = 1 −𝜃 𝒑, 𝒒 𝜋 (7) こ こ で𝜃 𝒑, 𝒒 は ， ベ ク ト ル 𝒑とベ ク ト ル𝒒の 間 の 角 度 を 表 す ．し た が っ て ，コ サ イ ン 類 似 度 は 式(8)の よ う に 求 め ら れ る ． 𝑐𝑜𝑠𝜃 𝒑, 𝒒 = 𝑐𝑜𝑠 ( 1 − 𝑃𝑟 ℎ 𝒑 = ℎ 𝒒 𝜋) (8) 上 記 に よ っ て 生 成 さ れ た ビ ッ ト を 複 数 生 成 す る こ と に よ っ て ， ビ ッ ト 列 が 生 成 さ れ る ． は じ め に𝑘個 の ハ ッ シ ュ 関 数 を 選 び ，任 意 の 点 𝒑に 対 し て ，𝑔 𝒑 = (ℎ+> 𝒑 , ℎ+@ 𝒑 , … , ℎ+y 𝒑 )を 構 成 す る ．𝑔 𝒑 を 𝜏個 作 成 し ， そ れ ぞ れ の 関 数 を 𝑔>, 𝑔@, … , 𝑔{と す る ． こ れ ら の 関 数 を 用 い て ハ ッ シ ュ テ ー ブ ル を 作 成 す る ． 実 際 の 探 索 時 に は ， 𝑖 = 1 か ら 𝑖 = 𝜏ま で バ ケ ッ ト𝑔+(𝒑)の 点 を チ ェ ッ ク す る ク エ リ𝒒が 与 え ら れ た 時 ， 𝑔+ 𝒑 = 𝑔+ 𝒒 な る 𝒑 を 探 索 し ， あ れ ば 出 力 す る こ こ ま で 繰 り 返 す と い う ア ル ゴ リ ズ ム を 利 用 し て 探 索 す る ．3. LSH を 利 用 し た 著 者 推 定 手 法
本 節 で は ，LSH を 利 用 し た 精 度 を 可 能 な 限 り 落 と さ ず ， 高 速 に 著 者 推 定 を 行 う 手 法 を 提 案 す る ．3.1. 概 要
著 者 推 定 手 法 を 高 速 化 す る た め に は ， 推 定 す る 候 補 者 の 数 を 減 ら す 必 要 が あ る ． そ の た め に ， 本 研 究 で は LSH を 利 用 し て 候 補 者 の 数 を 絞 る ．本 研 究 の 概 要 を 以 下 の 図3 に 示 す ． 図 3 は ， 全 て の 候 補 者 の デ ー タ か ら 絞 る 範 囲 の デ ー タ を 選 択 し ， 絞 っ た 範 囲 の 中 で の み 著 者 推 定 を 行 う と い う 概 念 を 示 し て い る ． 図 3 提 案 手 法 の 概 要 LSH に よ っ て 著 者 を 絞 っ た 後 ， 奥 野 ら [4]と 同 様 に ， コ サ イ ン 類 似 度 で 著 者 推 定 を 行 う ． 提 案 手 法 の 流 れ は 以 下 の よ う に な る ． l 前 処 理 l LSH に よ る 著 者 の 絞 り 込 み l 絞 っ た 著 者 に お け る 著 者 推 定3.2. 前 処 理
Twitter の 発 言 に は ，Twitter 特 有 の 表 現 が 数 多 く 含 ま れ て い る ． 著 者 推 定 の 精 度 を 向 上 さ せ る た め に は ， Twitter 特 有 の 表 現 を 可 能 な 限 り 除 去 を 行 い ，各 々 の 候 補 者 特 有 の 文 体 が 表 れ や す い 形 に し な け れ ば な ら な い ． 具 体 的 に は 以 下 の 処 理 を 行 っ た ． l URL(http(s)://〜 )の 除 去 l Screen Name(@ScreenName)の 除 去 l Hash Tag(#HashTag)の 除 去 ま た ，Twitter に は ，他 人 の 投 稿 を 自 分 の タ イ ム ラ イ ン 上 に 表 示 す る リ ツ イ ー ト 機 能 や ， 特 定 時 間 に 自 動 的 に 投 稿 を 行 う こ と の で き る ツ ー ル が 存 在 す る ． そ れ ら は ，Twitter API か ら 取 得 し た JSON に 含 ま れ る retweeted_status が null で な い こ と ， JSON に 含 ま れ る source の 値 が 「 リ プ ラ イ 数 チ ェ ッ カ 」，「 twittbot.net」 な ど ， 自 動 投 稿 に 用 い ら れ る ク ラ イ ア ン ト 名 で あ る こ と か ら 判 断 し ， 取 り 除 い た ．3.3. データセットの作 成 方 法
き さ は 30 ツ イ ー ト と す る ． 1 人 の ユ ー ザ の 最 新 30 ツ イ ー ト を テ ス ト デ ー タ セ ッ ト と す る ．最 新 30 ツ イ ー ト か ら 過 去 に 遡 り ，新 し い 順 に 30 ツ イ ー ト ず つ ，6 個 の 学 習 デ ー タ セ ッ ト を 作 成 す る ． こ れ に よ り ， 多 様 な 話 題 に 対 応 す る デ ー タ セ ッ ト の 生 成 が 可 能 に な る[4]．以 上 に よ り ，1 ユ ー ザ に 対 し 6 種 類 の 学 習 デ ー タ セ ッ ト を 用 意 す る こ と に な る ．
3.4. LSH を利 用 した候 補 者 の絞 込
著 者 の 絞 込 を 行 う た め に ，LSH を 利 用 す る ．は じ め に LSH の ビ ッ ト 列 を 生 成 す る ．ビ ッ ト 列 は コ サ イ ン 類 似 度 で 定 義 す る ． 利 用 す る コ ー パ ス は 学 習 デ ー タ セ ッ ト の 文 字{1,2,3}-gram と し ， テ ス ト デ ー タ セ ッ ト の 文 字{1,2,3}-gram 頻 度 分 布 と 比 較 を 行 い ， 双 方 に 含 ま れ て い る も の だ け を カ ウ ン ト す る ． 加 え て ， 特 徴 量 を よ り 効 率 よ く 取 得 す る た め に ，n-gram の n の 長 さ に 応 じ て 重 み 付 け を す る ． そ の 時 の 概 略 を 図 4 に 示 す ． 図 4 LSHの コ ー パ ス 作 成 の イ メ ー ジ 図 コ ー パ ス を 学 習 デ ー タ セ ッ ト の 文 字{1,2,3}-gram と し ， テ ス ト デ ー タ セ ッ ト の 文 字{1,2,3}-gram 頻 度 分 布 と 比 較 を 行 い ， 双 方 に 含 ま れ て い る も の の カ ウ ン ト 数 を ビ ッ ト 列 生 成 に 必 要 な ベ ク ト ル と す る ． そ の 後 ， そ の ベ ク ト ル を 元 に ビ ッ ト 列 を 生 成 す る ． こ の 時 の ビ ッ ト 列 生 成 の イ メ ー ジ を 図 5 に 示 す ． 図 5 は ， あ る 1 ビ ッ ト を 生 成 す る と き の 流 れ を 表 し て い る ． 図 5ビ ッ ト 列 生 成 の イ メ ー ジ 図3.5. 絞 った候 補 者 における著 者 推 定
3.4 項 で 絞 っ た 候 補 者 の 中 か ら も っ と も ら し い 著 者 を 推 定 す る ． こ の 節 の 手 法 は 既 存 研 究 で 説 明 し た 奥 野 ら の 手 法[4]を 踏 襲 す る ． 文 字 {1,2,3}-gram を 特 徴 量 と し ，コ サ イ ン 類 似 度 を 用 い て 文 体 相 違 度 の 計 算 を 行 う ．4. 評 価 実 験
本 章 で は ，3 節 で 提 案 し た 手 法 に 対 す る 著 者 推 定 実 験 を 10,000 人 規 模 で 行 う ． 4.1 項 で 評 価 手 法 の 説 明 を し ，4.2 項 で 評 価 に 用 い る デ ー タ セ ッ ト の 説 明 を 行 う ． 4.3 項 で 評 価 実 験 の 結 果 を 述 べ る ．4.1. 評 価 手 法
PBA を 利 用 し た 著 者 推 定 手 法 の 1 つ で あ る Ragel ら の 研 究[8]で は ， 評 価 手 法 に precision@1 を 指 標 と し て 利 用 し て い る ．こ れ は ，2.1.1 項 の 3.で 並 び 替 え た 候 補 者 の 中 で 1 位 の も の を 推 定 対 象 著 者 と し て 推 定 す る た め で あ る ．一 方 奥 野 ら[4]の 研 究 で は ，大 規 模 著 者 群 に 対 す る 推 定 で は ， 最 終 的 に は 人 力 で の 精 査 の 必 要 性 を 述 べ て い る ． そ の た め ， 推 定 順 位 が 1 位 で な い も の に 関 し て も ， 2 位 以 下 の 上 位 に 正 解 が 含 ま れ る 必 要 が あ る と 述 べ て い る ． そ の た め ， 累 積 相 対 度 数 分 布 を 定 量 的 に 評 価 す るMRR も 評 価 手 法 と し て 用 い て い る ． 大 規 模 著 者 群 に 対 し て の 著 者 推 定 は ， 奥 野 ら が 述 べ る よ う に ，MRR を 推 定 手 法 と し て 利 用 す る の が 適 し て い る ． し か し な が ら 本 研 究 の 目 的 は ， 著 者 推 定 を 行 う 前 の 絞 込 に あ り ， 絞 込 に よ っ て 「 本 来 の 正 解 が 間 違 っ て 削 除 さ れ る こ と が ど の 程 度 あ っ た か 」 の み を 評 価 し た い た め ，precision@N を 評 価 手 法 と し て 用 い る こ と と す る ． 本 研 究 の 目 的 は ，LSH を 用 い て ，推 定 精 度 を 落 と さ ず ， か つ 高 速 に 推 定 を 行 う こ と で あ る ． 著 者 の 絞 込 に LSH を 利 用 す る こ と で ど れ だ け 精 度 が 低 下 す る か 評 価 す る た め に ， 絞 込 を せ ず ， 全 デ ー タ に 対 し て 3.5 節 で 説 明 し た 著 者 推 定 を 行 っ た 時 の precision@1 と precision@10， LSH で の 絞 込 後 に 著 者 推 定 著 者 推 定 を 行 っ た 時 のprecision@1 と precision@10 の 比 較 を 行 う ． 全 テ ー タ を 対 象 と し た 推 定 精 度 に ， 絞 込 後 の デ ー タ を 対 象 と し た 推 定 精 度 を ど れ だ け 近 づ け る こ と が で き る か の 評 価 を 行 い ，LSH の 有 用 性 を 検 証 す る ． 加 え て ， 高 速 に 推 定 を 行 え る こ と を 検 証 す る た め ，LSH に よ る 絞 込 に か か る 計 算 時 間 ，4.5 項 で 説 明 し た 著 者 推 定 の 実 行 時 間 も 評 価 手 法 と す る ．4.2. データセット
奥 谷 ら[14] が 収 集 し た Twitter の デ ー タ の う ち ， 10,000 人 の Twitter ユ ー ザ を 利 用 し た ．予 備 実 験 を 行 っ た 際 の デ ー タ セ ッ ト の 概 要 は 以 下 の 通 り で あ る ． l ユ ー ザ 数: 10,000 人 l 言 語: 日 本 語 l ツ イ ー ト 数: 1 人 あ た り 最 大 2,000 件 l 収 集 期 間: 2013 年 11 月 か ら 12 月 実 験 を 行 う 際 に は ， テ ス ト デ ー タ は そ れ ぞ れ の ユ ー ザ の 最 新 の 30 ツ イ ー ト を 利 用 し ，学 習 デ ー タ は テ ス トデ ー タ を 除 く ツ イ ー ト か ら 利 用 す る も の と す る ．
4.3. 評 価 実 験
本 節 で は 10,000 人 に よ る 著 者 推 定 実 験 の 結 果 に つ い て 述 べ る ．2.2 項 で 述 べ た LSH 探 索 を 利 用 す る と ，𝑘 の 値 が 同 じ 場 合 ，𝜏の 値 を 大 き く し た 方 が ，絞 込 デ ー タ 数 は 大 き く な る ． 𝜏の 値 を 大 き く し ， 絞 込 デ ー タ 数 を 大 き く し た 方 が ，推 定 精 度 を 高 く で き る ．一 方 で ，𝜏の 値 を 大 き く し ， 絞 込 デ ー タ 数 を 大 き く し た 場 合 は ， 実 行 時 間 が 長 く な る ． 本 節 で は ， 𝑘 = 8と し ， 𝜏の 値 を 変 更 し て ， precision と 実 行 時 間 の 関 係 を 調 べ る ． 本 実 験 で は ，10,000 人 の 候 補 者 に 対 し て ， 推 定 を 行 う ユ ー ザ 数 を 1,000 人 と し て 実 験 を 行 う ． 実 験 結 果 を 図 6 に 示 す ． 図 6 に お け る 実 行 時 間 は ，3.4 項 で 行 っ た LSH に よ る 著 者 の 絞 込 に か か る 時 間 で あ る 絞 込 時 間 と ， ユ ー ザ の 絞 込 後 に 3.5 項 で 説 明 し た 著 者 推 定 を 1,000 人 に 対 し て 行 っ た 合 計 の 時 間 を 指 す 推 定 時 間 の 合 計 時 間 を 表 す ． な お ，LSH を 利 用 し た 推 定 に 関 し て は ，，LSH に よ る 著 者 の 絞 込 に は ラ ン ダ ム 性 が あ り ， 実 験 結 果 が 一 定 の 値 に は な ら な い ． 場 合 に よ っ て は 実 験 結 果 に 特 異 な も の が 現 れ る 可 能 性 が あ る ． 特 異 な 結 果 の 影 響 を 排 除 す る た め に ， 本 実 験 で は ， 推 定 精 度 ， 実 行 時 間 と も に 5 回 の 平 均 を 取 っ た 結 果 を 示 し て い る ． な お ， 実 験 で 利 用 し た 時 の LSH の ビ ッ ト 長 は 64 bit で あ り ， 利 用 し た 計 算 機 の CPU は Core i7 4790(3.6GHz, 4 コ ア 8 ス レ ッ ド )で あ る ． 図 6 precisionと 実 行 時 間 の 関 係 図 6 の 結 果 よ り ，実 行 時 間 を 短 く 過 ぎ る と ，precision が 大 き く 低 下 す る こ と が わ か る ． 𝑘, 𝜏 = 8,11 の よ う に ，𝜏の 値 が 小 さ い 場 合 に は ，実 行 時 間 が 87.9%短 縮 で き る が ，p@1 は 31.0%，p@10 は 31.7%も 低 下 す る ．一 方 で ，𝑘, 𝜏 = 8, 67 の よ う に ，𝜏の 値 を 大 き く し 絞 込 デ ー タ 数 を 大 き く し た 場 合 に つ い て は ，p@1 が 5.8%， p@10 で 6.6%し か 低 下 し て い な い の に も 関 わ ら ず ， 実 行 時 間 は 54.6%の 短 縮 が で き て い る ．し た が っ て ，𝜏の 値 を 大 き く し 絞 込 デ ー タ 数 を 大 き く す る よ う な 絞 込 の 方 法 を 用 い る の が 良 い ．以 上 の 結 果 か ら ，LSH で の 絞 込 は ， 大 規 模 な 著 者 を 推 定 す る 際 ， 推 定 精 度 の 若 干 の 低 下 を 許 容 し て も 問 題 が な い 場 合 ， 実 行 速 度 を 数 倍 程 度 向 上 さ せ る こ と が で き る と 考 え ら れ る ．5. お わ り に
本 研 究 で は ， 大 規 模 な 著 者 に 対 し て ， 著 者 推 定 を 高 速 化 す る 手 法 に LSH を 利 用 し た 手 法 を 提 案 し た ． 既 存 研 究 で は ， 著 者 推 定 を 行 う 際 に 全 て の 候 補 者 と 文 体 相 違 度 を 比 較 し て い た た め に ， 計 算 に 時 間 が か か っ て い た ． こ の よ う な 問 題 に 対 処 す る た め に ， 多 数 存 在 す る 候 補 者 を ，LSH を 利 用 し て 候 補 者 を 絞 る こ と を 提 案 し た ．LSH に よ っ て 候 補 者 を 絞 る こ と に よ り ，推 定 精 度 は 低 下 す る 一 方 で ， 実 行 時 間 を 短 縮 す る こ と が で き た ． 具 体 的 に は ，64bit の LSH を 利 用 し た 際 ， ビ ッ ト 長𝑘と 比 較 回 数 𝜏の 値 の 組 み 合 わ せ が 𝑘, 𝜏 = 8, 67 の 時 に ，p@1 が 5.8%低 下 す る 代 わ り に ，実 行 時 間 は 54.6% の 短 縮 を 可 能 に し た ． 大 規 模 著 者 群 に 対 す る 推 定 で は ， 最 終 的 に は 人 力 で の 結 果 検 証 の 必 要 が あ る ． し か し ， 人 力 で の 結 果 検 証 に は ， 長 時 間 が か か る こ と が 問 題 に な る ． 以 下 の よ う に 本 研 究 を 応 用 す る と ， 計 算 機 に よ る シ ス テ ム と ， 人 間 に よ る 結 果 検 証 の 作 業 を 並 列 し て 進 め る こ と が で き る ． 特 に ，10,000 人 で は な く 100 万 人 や ， 1,000 万 人 規 模 な ど ， 大 規 模 な 著 者 に 対 す る 著 者 推 定 を 行 う 際 に 有 用 で あ る ． 1. LSH で 候 補 者 を 絞 込 む ． 2. 1.で の 絞 込 後 の 候 補 者 に 対 し て ， 類 似 度 判 定 を 行 っ て 著 者 推 定 を す る ． 3. 2.の 結 果 の 上 位 N 件 を 人 間 が 検 証 す る ． 4. 3.で 人 間 が 検 証 し て い る 最 中 に LSH で 絞 り こ ま れ な か っ た デ ー タ 群 か ら ， 再 度 絞 込 を 行 う ． 5. 4.で の 絞 込 後 の 候 補 者 に 対 し て ， 類 似 度 判 定 を 行 っ て 著 者 推 定 を す る ． 6. 6.の 結 果 の 上 位 N 件 を 人 間 が 検 証 す る ． 7. 4.か ら 6.を ， 絞 込 む デ ー タ が な く な る ま で 繰 り 返 す ． 以 上 の 手 法 を 取 る と ， 全 て の 結 果 を 出 し て か ら ， 人 間 が 上 位 の 候 補 者 を 検 証 す る の で は な く ， 一 定 の 時 間 の 経 過 後 に ， 類 似 度 が 上 位 と 考 え ら れ る ユ ー ザ を 出 力 し ， 時 間 が 経 過 す る と と も に ， よ り 正 確 に 結 果 を 出 力 す る こ と が 可 能 に な る ．す な わ ち ，あ る 時 間 T が 与 え ら れ る と ， そ の 時 間T 内 で 最 適 な 結 果 を 返 し ， 時 間 T 以 降 も 候 補 者 の 推 定 精 度 を ， 時 間 の 経 過 と と も に 向 上 さ せ る と い う シ ス テ ム の 制 作 が 可 能 に な る と い え る ． 絞 込 デ ー タ 数 と 正 解 デ ー タ 含 有 率 と い う 評 価 手 法 で は ， 全 デ ー タ に 対 す る 推 定 順 位 が 高 い も の で あ っ て も ， 正 解 デ ー タ の 含 有 率 が 向 上 し な い 結 果 に な っ た ． (k,$τ)=(8,11) (k,$τ)=(8,19) (k,$τ)=(8,27) (k,$τ)=(8,35)(k,$τ)=(8,43) (k,$τ)=(8,51)(k,$τ)=(8,59) (k,$τ)=(8,67) (k,$τ)=(8,11) (k,$τ)=(8,19) (k,$τ)=(8,27) (k,$τ)=(8,35)(k,$τ)=(8,43) (k,$τ)=(8,51)(k,$τ)=(8,59) (k,$τ)=(8,67) 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0 1000 2000 3000 4000 5000 pr ec is io n [s] p@1 p@10そ の た め ， パ ラ メ ー タ の 決 定 の 際 に 利 用 し た 評 価 手 法 の 改 善 が 今 後 の 課 題 に 挙 げ ら れ る ． さ ら に ， あ る 著 者 1 人 に 対 す る 著 者 推 定 を 行 う た び に ，LSH で 検 索 す る 範 囲 を 変 え る こ と の で き る Resizable-LSH[11]を 利 用 し ， よ り 効 率 よ く 著 者 の 絞 込 を 行 う 手 法 の 考 案 や ， 近 似 領 域 探 索 問 題 を 利 用 し な い 著 者 の ク ラ ス タ リ ン グ に よ っ て 候 補 者 数 を 絞 る こ と が で き る か の 検 討 を す る 必 要 が あ る ．
参 考 文 献
[1] 平 成 26 年 中 の サ イ バ ー 空 間 を め ぐ る 脅 威 の 情 勢 に つ い て ， http://www.npa.go.jp/kanbou/cybersecurity/H26_jou sei.pdf (2015 年 12 月 17 日 ア ク セ ス ) [2] Ｐ Ｃ 遠 隔 操 作 、被 告 に 懲 役 ８ 年 「 悪 質 な サ イ バ ー 犯 罪 」 ， http://www.asahi.com/articles/ASH234QP0H23UTIL 025.html (2015 年 12 月 17 日 ア ク セ ス ) [3] 金 明 哲 , 村 上 征 勝 : “ラ ン ダ ム フ ォ レ ス ト 法 に よ る 文 章 の 書 き 手 の 同 定 ”, 統 計 数 理 , Vol.55, No.2, pp.255-268, 2007. [4] 奥 野 峻 弥 ， 浅 井 洋 樹 ， 山 名 早 人 : “マ イ ク ロ ブ ロ グ を 対 象 と し た 100,000 人 レ ベ ル で 著 者 推 定 手 法 の 提 案”, DEIM2015, D8-1, 2015.[5] A. Gionis, P. Indyk and M. Rajeev: “Similarity search in high dimensions via hashing”, International Conference on Very Large Data Bases, pp.518-529, 1999.
[6] E. Stamatatos: “A Survey of Modern Authorship Attribution Methods, J. of the American Society for Information Science and Technology”, Vol.60, No.3, pp.538-556, 2009.
[7] A Narayanan., H. Paskov, N.Z. Gong, J. Bethencourt, E. Stefanov, E.C.R. Shin and D. Song “On the Feasibility of Internet-Scale Author Identification”, Proc. of IEEE Symp. on Security & Privacy, pp.300-314, 2012.
[8] R. Ragel, P. Herath and, U. Senanayake: “Authorship detection of SMS messages using unigrams” Proc. of IEEE Industrial and Information Systems, pp.387-392, 2013.
[9] P. Indyk and R. Motwani: “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality”, Proceedings of the 30th annual ACM symposium on Theory of Computing, pp.604-613, May 1998.
[10] Moses S. Charikar: “Similarity estimation techniques from rounding algorithms” In Proceedings of STOC, pp. 380–388, 2002.
[11] 山 崎 邦 弘 ，山 名 早 人 : “ Resizable-LSH に よ る 閾 値 可 変 の 近 似 的 類 似 検 索 手 法 の 高 速 化”, 情 報 処 理 学 会 研 究 報 告 vol.2010-AL-131 No.5, 2010. [12] J. L. Bentley: “Multidimensional Binary Search Trees
Used for Associative Searching”, Communications of the ACM, Vol.18 No.9, pp.509-517, September 1975. [13] 井 上 雅 翔 ，山 名 早 人 : “大 規 模 候 補 者 群 に 対 す る 著 者 推 定 手 法 の 提 案 と 評 価”, DEIM2013, C6-6, 2013. [14] 奥 谷 貴 志 ，山 名 早 人 : “メ ン シ ョ ン 情 報 を 利 用 し た Twitter ユ ー ザ プ ロ フ ィ ー ル 推 定 ”, DEIM2014, C2-3, 2014.
