A-17 検索履歴のプライバシーを秘匿した ユーザクラスタリング 菊池研究室 相羽研次
研究背景 みんなどういう検索してるのかな？ 検索履歴から僕と似たような趣味を持った人を調べられないかな？ とても 見せられないよ！ ＞＜；
研究目的 検索履歴を 暗号化して、 自分と似たような傾向のある人を抽出できるツールを開発 しよう！ 検索の傾向が 近い！
開発概要 使用言語：Java 暗号化：Paillier暗号 クラスタリング：コサイン尺度を用いた最短距離法 データ：GoogleやYahooなどの検索履歴を対象
暗号化について 問題点：情報を暗号化したまま利用するには？ 解決策：準同型性暗号 復号する事なく比較・演算ができなくてはならない 情報を秘匿したまま、演算可能な暗号方式 今回はPaillier暗号を利用 (情報を秘匿したまま、乗算が可能)
クラスタリングについて データ解析手法の1つ 特定の傾向を持った集団(クラスタ)を生成する事 今回は最短距離法を使用、類似度の近さで形成 2 4 7 クラスタリング例 11 13 20
データ(検索履歴)について 利点 ”嗜好や性格などが反映されやすい”個人情報のほうが 欠点 検索意図の解釈が困難、単語の解析etc… クラスタ生成に利用しやすい (具体例：amazonのリコメンドシステム) 欠点 検索意図の解釈が困難、単語の解析etc… (例：検索単語”Youtube”→音楽？映像？)
データ(検索履歴)について 解決策 検索履歴のジャンル分けを行い、傾向を抽出する ジャンル分けの方法 「Yahooカテゴリー」 の分類を利用 検索履歴の単語を 約15項目から選択 データをカテゴリー別の検索割合に分けることで 検索傾向・意図が把握しやすくなる
実験について 目的 検索履歴を秘匿したままクラスタリングし、 形成したクラスタの傾向が被験者の特徴と一致するか 被験者 東海大学の学生5名(文系2名・理系3名) 期間・データ量 1ヶ月分の検索履歴約200件 精度の調査方法 理系を正解とみなし、適合率・再現率を算出 理系={A、B、D} 文系={C、E}
実験の流れ 相手 自分 検索 データ 検索 データ Step1 Step3 Step2 Enc 計算 Step4 クラスタリング 計算 類似度
実験中… ツールはCUI形式 データファイルを 読み込み、 暗号化 15項目を暗号化 時間がかかる (1回約25秒x10≒250秒)
実験結果 - 類似度 Dさんは みんなと異なる 傾向？ Aさんは 一般性が最も 高い A B C D E 0.912 0.785 0.183 0.713 0.613 0.152 0.725 0.258 0.673 0.269 類似度 最大 類似度 最小
実験結果 - クラスタリング クラスタ 文系 クラスタ 理系 0.183 0.725 0.785 0.912 クラスタ 文系 クラスタ 理系 A B C E D 適合率=2/4(クラスタ内の理系/クラスタ内全体)=50% 再現率=2/3(クラスタ内の理系/理系人数)=66%
検索履歴比率 最も類似度が平均的に高かった被験者A 最も類似度が低かった被験者D
より大量のデータ・期間・人で実験を行う 必要がある 実験結果 – まとめ マイナージャンルに偏った検索者Dは孤立 AB間が最も類似性高く、BD間が最も低い 検索は人気カテゴリーに集中 文・理での区分けはそれなりの精度だった しかし、理系としての傾向での繋がりはあまり無かった より大量のデータ・期間・人で実験を行う 必要がある
今後の課題 検索履歴の収集自動化 検索カテゴリーの細分化 暗号化ツールの改善点(GUI化など) より細分化したクラスタ構築方法の模索