概念グラフを使った推薦 - 廣川研究室へ

社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS
信学技報
TECHNICAL REPORT OF IEICE.
概念グラフを使った推薦
下司
義寛†
廣川佐千男††
† 九州大学大学院システム情報科学府 〒 819-0395 福岡市西区大字元岡 744
†† 九州大学情報基盤研究センター 〒 812-8581 福岡市東区箱崎 6-10-1
E-mail: †[email protected], ††[email protected]
あらまし
本稿で は , 利用者ごと の 好みの 映 画リストを文書, リストに 含まれる映 画を単語と 考え, 単語の 上位下位関
係を抽出し可視化する概念グラフを映 画の 推薦に 応用する. 映 画タイトルを入力すると , MovieLense の データから関
連する映 画を求め, 共起頻度に 基づ き上位下位の 関係を可視化するシステムを実装した. ユーザが面白いと 思う映 画の
推測を行な い, ユーザの 類似度を用いる協調フィルタリングに よる推薦方法と 比較して , 提案手法は 10 倍の 効果があ
ること を検証した.
キーワード
推薦, MovieLens, 概念グラフ, 協調フィルタリング
Recommendation System using Concept Graph
Yoshihiro SHIMOJI† and Sachio HIROKAWA††
† Graduate School of Information Science and Electrical Engineering, Kyushu University
†† Research Institute of Information Technology, Kyushu University
E-mail: †[email protected], ††[email protected]
Abstract This paper presents a recommendation system of movies based on the notion of Concept Graph, which
extracts important keywords from given a set of documents and visualizes their relationships as a directed graph.
When titles of movies are sent as query, the system retrieves the list of users who like the movies from the MovieLens
dataset and recommends related movies as a directed graph. Effectiveness is evaluated by ROC(Rate of Collecting),
which is the percentage of the successful guess of favourite movies of the user. The proposed system is ten times
effective compared to a naive method which recommends favourite movies of similar users.
Key words Recommendation, MovieLens, Concept Graph, Collaborative Filtering
1. ま え が き
今日, WWW 上は 我々がいつで も自由に 閲覧可能な 情報で 溢
れて いる. しかし, 大量の 情報の 中から, 自分の 必要と する情報
を効率よく入手すること は 容易で は な い. 情報検索は ユーザが
自らの 必要と する情報をクエリを使って 手に 入れる技術で ある
各ユーザの 好みの 映 画タイトルの リストを文書, 映 画タイト
ルを単語と すること で , ユーザに と って 未知の 映 画を発見する
システムを実装し, 評価実験を行った.
2. 関 連 研 究
協調フィルタリングは ユーザの 各アイテムに 対する好みの 情
が, クエリをユーザが単語と 記号を使って 表現する必要がある.
報から, 特定の ユーザの 好みと 類似した別の ユーザあるいは そ
ユーザが未知の 単語を使うこと は 出来ず, 全く知らな いこと は
の ユーザの 好きな アイテムと 類似した別の アイテムを抽出し,
検索で きな い. また, 空白区切りに よる AND 検索な ど 検索シ
ユーザの まだ知らな いがおそらく気に 入るで あろうアイテムの
ステム上で の 特殊な 表現に ついて の 理解が必要で ある. そこで ,
集合を発見する研究で ある [2]. 本稿で 利用する MovieLens の
ユーザの 必要と する情報をシステムが推測し, ユーザに 提示す
データは , インターネットが始った当初から協調フィルタリン
る推薦の 研究が期待されて いる.
グを行な って いるグループが提供して いるもの で ある（ 注 1）. イ
概念グラフは , 単語と それを含む文書群の 関係からある単語
ンターネットバブル崩壊で 一時は 下火に な ったようだが, 近年,
の 関連を抽出し, 関連語間の 上位下位の 関係を可視化するシス
顧客に 応じたサービスの 提供と いう観点からも再び注目を集め
テムで ある [5]. 本稿で は , 概念グラフの 推薦システムへの 応用
を提案する.
（ 注 1）：http://www.grouplens.org
るように な って いる [1], [3], [4], [6]∼[9]. 学術的な 研究だけで な
く, Amazon の ように 顧客への 商品推薦の ための 技術と して , 期
待されて いる.
P (u|v) > 0.5
(3)
ただし, 本稿で は 単語間の 関係は 前節の 特徴語抽出と 同様に ,
特定の 分野, 文書集合に 着目して 行う. その ため, 式 (2), (3) は
協調フィルタリングで は ユーザがど の アイテムに 何点をつけ
て いるかを表の ような 情報と して と らえ, ユーザ-アイテム行列
ユーザの 入力キーワード q を含む文書集合 D(q) で の 文書頻度
を用いて 次の 用に 書き換える.
を作り, アイテムあるいは ユーザの ベクトルを用いて 推薦を行
う. 協調フィルタリングは ユーザベクトル, アイテムベクトル
ど ちらを利用するかで 分類される.
2. 1 ユーザベース 協調フィルタリング
あるユーザ u に 類似したユーザ集合 N eighbor(u) を抽出し,
N eighbor(u) に 属するユーザ達が高い点数をつけて いる映 画を
u に 推薦する協調フィルタリングをユーザベース協調フィルタ
df (u, D(q)) > df (v, D(q))
(4)
P (u|v) = df (u ∗ v, D(q))/df (v, D(q)) > 0.5
(5)
ここで df (u ∗ v, D(q)) は D(q) で の u, v の 共起頻度を表す.
つまり, v よりも u が D(q) で より多く出現し, v が出現する
過半数で u も出現して いると き, u は v の 上位で ある. また,u
リングと 呼ぶ.
を v の 上位語と 呼ぶ.
2. 2 アイテムベース協調フィルタリング
あるユーザ u が高い点数をつけて いるアイテムの 集合 I(u)
の 要素 i と 類似したアイテム集合 SimilarItem(i) を i の アイ
テムベクトルを用いて 抽出し, ∪i∈I(u) SimilarItem(i) の 中で
高いスコアをもつアイテムを u に 推薦する協調フィルタリング
式 (4), (5) を満たす全て の 特徴語の ペアを上位下位関係に あ
る単語の ペアと して 抽出する.
3. 3 隣接上位関係
前節の 上位下位関係の 定義に より抽出された単語 w の 上位語
から隣接する上位語を抽出する. これに より, 単語の 上位下位
を協調フィルタリングと 呼ぶ.
本稿で は , 比較対象の ベースラインと して ユーザベースの 協
の 階層構造を構築する.
隣接上位関係の 定式化の ために 単語 v の 上位語集合 U P (v)
調フィルタリングを実装した.
と 隣接上位語集合 DU P (v) を定義する.
3. 概念グラフ
本稿で は , 単語を節と して 上位下位の 関係を枝と する有向グ
U P (v) = {u ∈ D(q)|u は v の 上位語 }
(6)
DU P (v) = {u|∀w ∈ U P (v).u ∈
/ U P (w)}
(7)
ラフを概念グラフと 呼ぶ.
3. 1 特 徴 語
同じ単語で も, それが使われる環境に よって 意味がかわり, 二
v の 上位語 u が u 以外の 上位語の 上位で は な いと き
つの 単語の 間の 上位下位関係も異な る. そこで 本研究で は 全て
u ∈ DU P (v) で あり, u は v の 隣接上位で ある. また, u を
の 単語の 階層構造を扱わず一部の 単語の 階層構造を構築する.
v の 隣接上位語と 呼ぶ.
一部と は 特定の 文書群の 特徴を表す単語で ある. ユーザの 必要
と する分野に 特徴的な 単語の 関係を提示すること が有用で ある.
本研究で は ユーザの 必要と する分野をユーザの 入力キーワード
q を含む文書集合と する. これに よりユーザの 入力に あわせた
動的な 特徴語抽出が可能と な る. 今後単語 q を含む文書集合を
D(q) と 表記する.
全て の 特徴語間の 隣接上位関係に ついて 下位の 単語から上位
の 単語に 向いた枝を引き有向グラフと して 可視化する.
4. 概念グラフを使った推薦システム
前節の 概念グラフの 定式化に おける, 文書と 単語をそれぞれ,
ユーザと その ユーザの 評価して いるアイテムと 捉えること で ,
ユーザの 入力キーワード q に よって 決定される文書集合 D(q)
に 対し, w が D(q) の 特徴語で あると は 次の 条件 (1) を満たす
概念グラフの 推薦システムへの 応用が可能で ある.
概念グラフで は 単語 q を入力と し, それを含む文書 D(q) に
こと と する. ここで , df (w, D(q)) は , 単語 w の D(q) で の 文書
特徴的な 単語群を抽出し, それらの 関係を可視化した. 推薦シス
頻度, df (w, U ) は 全文書集合 U で の 文書頻度を表す.
テムで は アイテム i を入力と し, それを好むユーザの 集合 U (i)
から特徴的な アイテム群を抽出し, それらの 関係を可視化する.
df (w, D(q))/df (w, U ) > 0.5
(1)
つまり, 単語 w が出現する過半数が文書集合 D(q) に 含まれ
て いると き, w は D(q) の 特徴語と いう.
図 1 は , ミッション・インポシブル (1996) をキーワードと し
て 検索した結果で ある. この 映 画に 4 点以上の 評価を付けた人
が 648 人いて , その 中で 100 人以上の 人が 4 点以上の 評価を付
けて いる映 画が 14 タイトルあり, ダイハードやゴールデンアイ
3. 2 上位下位関係
な ど アクション系の 傾向の 映 画が図 1 に 表示されて いる. 上に
本節で は 単語間の 上位下位関係の 抽出法を説明する.
単語 u が v の 上位で あること を, より一般的な 単語で あるこ
と 式 2 と v から見た u の 関連が強いこと 式 3 で 定義する.
あるもの が頻度, つまり人気が高い.
図 2 は , トイ・ストーリーを入力と したもの で , トイ・ストー
リー 2, ベイブ, ライオンキング, アラジン, 美女と 野獣な ど の
ファンタジー系ディズニー映 画が表示されて いる. MovieLens
df (u) > df (v)
(2)
の 映 画データに は アクション, アドベンチャー, アニメーション
図1
Mission Impossible に ついて の 概念グラフ
図2
Toy Story に ついて の 概念グラフ
な ど の ジャンルが付けられて いるが, 本システムは この ような
スコアつけて いる (表 1). ただし, 本稿で は 4 点以上の スコア
ジャンル情報は 利用して いな いに も関わらず, 同じジャンルの
を 1, 3 点以下を 0 と して 2 値の ユーザ-アイテム行列を作りシ
映 画が得られて いる.
ステムを実装した.
1,000,209 件の 評価データから 10 万件をランダムに 選択し,
5. 評 価 実 験
それらを 10 個に 分割し, その うちの 9 割の データを用いて , 概
本稿で は MovieLens の データを用いて , 提案システムの 評価
念グラフの システムを実装し, システムが残りの 1 割を予測可
を行った. 1,000,029 件の ユーザ ID, 映 画 ID, スコアの 3 つか
能かど うか評価した.
5. 1 ベースラインと して の 協調フィルタリング
らな るデータを利用した.
評価の ための 比較対象と して , 以下の ような 協調フィルタリ
ング手法を実装した.
ユーザ ID
映 画 ID
スコア
1
661
3
入力と な るユーザ u と 映 画の 好みの 類似するユーザ集合 N (u)
1
914
3
をコサイン類似度を用いて 求める. ユーザ u, u0 の 間の コサイ
1
1193
5
2
1687
3
2
1213
2
2
3578
5
表1
MovieLens データ形式
ン類似度 cos(u, u0 ) は ユーザの レーティングベクトル を用
いて 計算する.
cos(u, u0 ) =
·
| |∗|
|
(8)
cos(u, u0 ) の 上位 10 人の ユーザ u0 を N (u) の 要素と した.
6,040 人の ユーザが 3,883 種類の 映 画に 1 から 5 の 整数値で
ui ∈ N (u) に ついて 各 ui の 映 画 mj に ついて の スコアの 平
均を mj の ユーザ u に 対する推薦度 r(u, mj ) を求め, 上位 k 個
を推薦する.
5. 3 ROC に よる評価
ユーザー u に ついて 上位 k 個の 推薦をしたと きに , ans(u, k)
個の 推薦が出来たと する. 上位 k 個に よる推薦の ROC(k) は ,
r(u, mj ) =
ans(u, k) の 総和を, テストデータ中の 正解の 個数 (今の 実験の
Σui ∈N (u) rating(ui , mj )
|N (u)|
(9)
ただし,rating(ui , mj ) は ui の mj に 対するスコアが 4 点以上
の 時 1, ui の mj に 対するスコアが 3 点以下の 時 0 と する.
5. 2 テスト・データ
推定対象の テスト・データで ある (ユーザ, 映 画, 評価) の 組
は 10000 件ある. 各ユーザに ついて , これ以外の 訓練データに
基づ きその ユーザに あった映 画を推定し, 上位 k 個を推薦する.
と ころが, 大半の テストデータに ついて , 正解の 数が 1,2 個しか
場合 10,000) で 割ったもの と して 評価した (表 3, 図 4). これ
は , 各ユーザに ついて の 適合率の 加重平均と 一致する. 表 3 は ,
k ∗ 10 件推薦したと きの ROC の 値をまと めたもの で ある.
協調フィルタリングで は , システムが推薦する候補数を上げ
て も, ROC は 0.01 程度以上に は 増えな い. 一方, 提案手法で は
70 個の 推薦で 0.10 と な り, 10 倍の 効果がある. 図 4 からも分
かるように , 提案手法の 方は 協調フィルタリングよりも 10 倍以
上の 映 画を推定で きて いる.
な い (表 2, 図 3). これは , もと もと 各ユーザが 4 点以上の 評価
概念グラフ CG
点をつけて いる映 画の 数が少な いこと に よる.
映 画の 数
表2
人数 映 画の 数
k 正解数
人数
協調フィルタリング CF
ROC 正解数
ROC
1
85 0.0085
64
0.0064
2
302 0.0302
93
0.0093
1 2207
10
16
3
488 0.0488
99
0.0099
2
991
11
10
4
659 0.0659
100
0.0100
3
558
12
4
5
824 0.0824
100
0.0100
4
313
13
3
6
951 0.0951
100
0.0100
5
136
14
2
7
1076 0.1076
101
0.0101
6
104
15
3
8
1212 0.1212
102
0.0102
7
79
16
2
9
1313 0.1313
102
0.0102
8
31
21
2
10
1413 0.1413
102
0.0102
9
28
24
1
表3
ROC(Rate of Collecting)
ユーザーごと の 好きな 映 画数の 分布 (テスト・データ)
図4
図3
概念グラフと 協調フィルタリングの ROC
ユーザーごと の 映 画件数分布 (全データ)
従って , 検索システムの 性能評価で 用いられる 11 点平均適
6. 考
察
合率の ような 方法で 適合率と 再現率の 評価を行な うこと は 意味
6. 1 推薦候補の 数の 比較
がな い. そこで , アルゴリズムで 得られる候補の から上位 k 個
k の 値に 応じて 各ユーザーごと に 推薦で きた件数をプロット
を推薦したと き, テストデータ中で ユーザーが面白いと 思った
したの が図 6. 1 で ある. 協調フィルタリングで は , k の 値が大き
（ つまり 4 以上の 評価を付けた） 映 画の うちの 予測で きた割合
ROC(Rate of Collecting [1]) で 評価すること に する.
くな って も推薦で きる件数は 10 件程度しかな い. 一方, 概念グ
ラフで は , 協調フィルタリングに 較べ 10 倍以上の 推薦候補があ
る. これは , トレーニングデータに 含まれる映 画の OR 検索す
ること に よる. つまり, あるユーザーが好むそれぞれの 映 画に
ついて 関連映 画を求めて いるからだと 思われる. 一方, 協調フィ
ルタリングで は , その ユーザーに 類似したユーザーを 10 人と
限定し, それらの ユーザーが共通に 好む映 画を候補と して いる.
そもそも, 各ユーザーが上げた映 画の 数は ベキ分布と な って お
7. まと めと 今後の 課題
り, 大半の ユーザーは ごく少数の 映 画しか上げて いな い. 平均
単語と それを含む文書群の 関係からある特定の 単語の 関連語
の 数と して も, 21 件しかな い. この 二つで 図 6 の ような 差が出
を抽出し, 関連語間の 上位下位の 関係を可視化する概念グラフ
たと 考えられる.
の 推薦への 応用を提案した. 概念グラフを映 画の 推薦システム
MovieLens の データに 適用し, ユーザの ID を指定すること で ,
ユーザの 好みと 関連する映 画を出力するシステムを実装した.
また, 推薦結果をユーザ数と ユーザの 共起情報を用いて 可視化
するシステムを実装した.
評価実験に 関して , 今回は ランダムに 選んだ 100,000 件の デー
タを 10 分割し,9 割で システムを構築し, 残り 1 割の ユーザが 4
点以上の スコアをつけた映 画を予測する評価実験を行った. 分
割の 方法を 1 通りしか, 試して おらずその 他の 分割の 方法を試
す必要がある. また, 分割の 割合を変化させること で , システム
の 推定精度がど の ように 変化するかも実験する必要がある. ま
た, 本稿で は OR 検索を用いて 関連する他の ユーザーを求め, そ
図5
概念グラフ, 協調フィルタリングに よる推薦候補数
こから関連映 画を求めた. その 結果, 推薦候補の 映 画の 数が協調
フィルタリングに よるよりも二桁多くな った. 関連ユーザーの
6. 2 推定が成功した対象ユーザーの 特性
協調フィルタリングに ついて , 100 件以内の 推薦で 正解が得
られた映 画は , 4,490 人に ついて 102 件で あった. それらの ユー
検索まで を協調フィルタリングと 同様に すること も考えられる.
概念グラフの 特徴は , 共起頻度に 基づ く有向グラフと して の
可視化で あるが, 本稿で 数量的な 評価をしたの は 関連映 画の 抽
ザーの テストデータを見ると , 正解の 個数が 1,2 件しかな いも
出に ついて だけで ある. 推薦映 画の 上位下位関係の 評価も今後
の が大半で あった. さらに , 協調フィルタリングに よる推薦の 個
の 課題で ある.
数は 10∼20 個程度しかな い. 一方, 概念グラフに よる推薦で 正
解が得られた映 画は 1413 件で , 推測が成功したほと んど の ユー
ザーに ついて , テストデータの 正解の 個数は 4 個以上で あった.
そして , 概念グラフに よる推薦の 個数は 数百個程度で あった (図
7). また, 協調フィルタリングと 概念グラフの 二つの 手法の ど
ちらで も正解を得ること がで きたの は , 11 人しかいな かった.
つまり, 協調フィルタリングは 少数の 映 画をしか評価して いな
いユーザーに ついて の 推定が得意で あり, 一方, 概念グラフは 多
数の 映 画を評価して いるユーザに ついて の 推定が得意と 考えら
れる.
図6
推定成功ユーザーデータ特性
文
献
[1] 平山巧馬, 小柳滋, 協調フィルタリングに おける相関係数法の
予測性能向上, 電子情報通信学会論文誌 D, Vol.J90-D, No.2,
pp.223-232, 2007.
[2] Paul Resnick, Neophytos Iacovou, Mitesh Suchak, Peter
Bergsrom, John Riedl, GroupLens: An Open Architecture
for Collaborative Filtering of Netnews, Proc. of the 1994
ACM conference on Computer supported cooperative work,
pp. 175–186, 1994.
[3] Badrul Sarwar, George Karypis, Joseph Konstan, John
Riedl, Analysis of Recommendation Algorithms for ECommerce, Proc. of the ACM E-Commerce 2000 Conference, pp.158–167, 2000,
[4] Badrul Sarwar, George Karypis, Joseph Konstan, John
Riedl, Item-based Collaborative Filtering Recommendation
Algorithms, Proc. of the 10th International World Wide
Web Conference (WWW10), 2001.
[5] 下司義寛, 和多大樹, 廣川佐千男, 英 和辞典からの 知識抽出, 第 68
回情報処理学会全国大会講演論文集 3, pp. 19–20, 2006.
[6] Jun Wang, Arjen P. de Vries, Marcel J. T. Reinders, A UserItem Relevance Model for Log-based Collaborative Filtering, Proc. of European Conference on Information Retrieval
(ECIR 2006), pp. 37-48, 2006.
[7] Gui-ROng Xue, Chenxi Lin, Qiang Yan, WenSi Xi, Hua-Jun
Zeng, Yong Yu, Zhen Chen, Scalable Collaborative Filtering Using Cluster-based Smoothing, SIGIR’05, pp.114–121,
2005.
[8] 柳原正，帆足啓一郎，松本一則，菅谷史昭, 潜在クラスを利用し
たクロスメディアレコメンデーション方式の 提案, 情報処理学会
全国第 68 回大会, 2006.
[9] C-N Ziegler, S.M. McNee, J.A. Konstan, and G. Lausen,
Improving Recommendation Lists Through Topic Diversification, Proc. of the Fourteenth International World Wide
Web Conference (WWW2005), pp. 22–32, 2005