ZDD上のあいまい検索に基づく情報推薦機能

ZDD上のあいまい検索に基づく情報推薦機能
JST-ERATO 湊離散構造処理系プロジェクト / 北海道大学 / 九州大学
白井康之，鶴間浩二，小山聡，高嶋宏之，櫻井祐子
協調フィルタリングと集合推薦
差分に基づく集合推薦
Collaborative Filtering (ex. Internet Shopping)
(Frequent Patterns)
a,b,f
b,c,h
f
h
a,b,c,d,e
Class α (Positive)
a, b, c
Set Recommendation (ex. University Course Guide) [M. Xie 2010], [A. Parameswaran2011])
b, c
(Frequent Patterns)
a,b,c,d,e
f,g
a,b,c,f,g
h,j
b,c,d,h,j
d, e
Class β (Negative)
e
a, c
a, b, d
e
b, c
e
Problem :
find the modification of D=ac so that the
modified D’ belongs to Cα-Cβ > 0,
under the constraints of :
coefficient weight ≧2,
number of additional items ≦ 1
number of deleted items ≦ 1
d, e
Incremental Set Recommendation (ex. Recipe, Health Care, …)
a,b,c,d,e
b,c,d,h,j
b,c,d,h,k
ZDDを使ったあいまいマッチングの実装
F
等価なノードの共有
b, f, g, h, k
a, c, d, j, m
d, e, g, s, t
….
 ZDD上であいまい検索を行うアルゴリズムを実装．
Ex. ) ‘ac’ に対して， F>0となるような modification を
探索する．探索条件として， Nadd, Ndelete, 係数制約 m
を指定
1
X
b
0
c
0
1
0
1
0
b
0
0
1
0
1
c
c
c
1
0
0
0
1
1
0
1
X
1
0
1
0
a
1
0
1
0
f
g
1
0
f
g
f
1
1
Data Size
>>
Data Size
Data Size
Data Size
ZDD Node Size
f
ZDD Reduction Rules
否定のみで出現するノードの削
除
Binary data set :
F = (a∧b)∨(a∧c)∨c
= ab + ac + c
≒
1
0
0
ZDD based search
1
0
X
0
b
c
バイアス
パタン
a, b, c, e, f
a, b, d, d, g
b, c, f, n, k
b, c, g, s, m
….
F
X
Sequential Search
with sorted data
ランダム
パタン
a
0
探索アルゴリズム
データ
差分に基づく情報推薦は， ZDD (Zero Suppressed Binary
Decision Diagram) [Minato 93] 上のあいまい検索として実装
されている．
ZDD は積和集合に対するコンパクトな表現を可能とする．特
に，スパースなデータ構造に対して効率的に表現できること
が知られている．
ZDD実装の効率性評価
クラス差分 α-β は以下のような多項式で表現すること
ができる．
Exec. Time
+h,+j,-a,-e
a,b,c,f,g
Exec. Time
a,b,c,d,e
(Class β)
Exec. Time
(Class β)
Possible Solution : D’ = bc (add b and delete a to/from D)
(Class α)
Exec. Time
β→ α
+f,+g,-d,-e
ZDD Representation
for F
bc （add ‘b’ and delete ‘a’）
→M=1,2において推薦候補
1M
2,696,527
313,594
Random Data Set
Fixed Pattern Set
abc（add ‘b’)
→M=1において推薦候補
5M
11,789,288
363,112
10M
20,738,481
377,979
c （delete ‘a’）
→M=1 において推薦候補
実行結果（例）
実験：レシピデータの推薦
対象レシピ（推薦の対象）
ポジション
タイトル
食材
(www.cookpad.com)
(www.cookpad.com)
スキムミルク,ドライイースト,バター,レーズン,卵,塩,強力粉
材料
入手しやすい食材を
使いたい
？
フィードバックを増
やしたい
より簡易なクッキン
グステップに
？
？
○食材の入手
カスタード
×コメント数
クッキー
○ステップ数
条件：
もとのレシピに（食材の構成が）類似していること．
改善の大きさを定量的に条件として指定できる．
参考：食材の分類
食材の入手可能性を定量化（ランキング付け）するために，
lancers.jp を使ってアンケート調査を実施．
全員が入手が容易と 約半数が入手が容易 全員が入手困難と回
回答した食材
と回答した食材
答した食材
サラダ油
うす口醤油
ドリュール
胡麻油
塩こんぶ
マヌカハニー
白飯
鷹のつめ
コリンキー
小麦粉
三温糖
ヌクマム
玉子
冷凍海老
キャロブ粉
パン
白ごま
雪塩
わさび
いりこだし
イサキ
玉葱
味噌みりん
五香粉
砂糖
ピーマン
たかきび
卵
馬鈴薯
羅漢果
材料が入手しやすい
削除
追加
かぶの葉
白菜
かぼちゃとにん
生クリー
ステップ数 じんのほっこり
ム
スープ
豆乳
かぼちゃとにん
食材の入手
生クリー
じんのポター
しやすさ
ム
ジュ
コンソメ
キューブ
ココアパ
ウダー
チョコ
レート
三温糖
板チョコ
バター
インスタ
ントコー
ヒー
ごはんで作る
卵
レーズン食パン
ご飯
バターシュガー
卵
レーズンパン
天然酵母
材料が入手しにくい
ミルクはちみつ
レーズン
コメント数
スキムミルク,ドライ
パン
イースト,バター,
レーズン,卵,塩,強力
ふんわり甘いた
粉
レーズン
まごパン
×食材の入手
×コメント数 レーズンパン
×ステップ数
ステップが
容易
食物繊維とカル
シウムが豊富な レーズン
イチジクのパン
ステップが
複雑
食材の入手 イタリア伝統の スキムミ
しやすさ 味 パネトーネ ルク
対象レシピ（推薦の対象）
ポジション
いろいろな課題
 必ずしもすべての食材が網羅的に記述されているとは限らない．
 全く異なったレシピになってしまう例がある．
 食材（アイテム）の関連，頻度も考慮されるべき．
 レシピの大まかな方向性（料理分野？）を制約として追加すべき？
今後の予定
【その他のアプリケーション】
【関連研究】
 Emerging Patterns ([G. Dong 1999])
パタンのみの抽出．必ずしも emerging でなくても推薦可能．
 Set Recommendation ([M. Xie 2010], [A. Parameswaran 2011])
クラス差分に基づく推薦ではない．
 Dynamic Programming (Levenshtein Distance)
制約の与え方が異なるが，近い．ただし，ZDDアプローチではよ
り複雑な制約をかけることができるはず．
ダイエットを意識した日常生活へのリコメンデーション
運動履歴，食事履歴などをもとに，日常生活の改善を提言．
インターネットショッピングサイトの宣伝文
キーワードやサイト構成をもとに，より顧客を引き付ける構成を提言．
インターネット検索のキーワードの推薦
過去の検索キーワードとアクセスの履歴から，検索キーワードの修正を
提言
タイトル
食材
【レシピ検索に関する今後の方向性】
 定番度や珍しさ等の概念の導入（筑波大学 中岡ほか）
 ユーザの習熟度や調理環境，食材の分類，難易度等の概念の導入
（京産大ほか）
 料理レシピの構造的解析結果との融合（東工大 苅米ほか）
改善の方向
タイトル
かぶ,たまねぎ,にん
じん,コンソメスープ
の素,バター,塩、胡
椒,牛乳
×食材の入手 かぶとにんじ
×コメント数 んのポター
×ステップ数 ジュスープ
グラ
ニュー糖
ドライい
ちじく
砂糖
削除
ステップ数
追加
おいしい軟骨の
小麦粉
からあげ
塩、胡椒
かぶのミルクパ
塩、胡椒
スタ
スパゲテ
イ
おろししょうが,おろ
しにんにく,小麦粉,
ステップ数
揚げ油,片栗粉,酒,醤
おいしい鶏の唐
油
小麦粉
揚
○食材の入手
×コメント数 鰹の唐揚げ
×ステップ数
はちみつ
推薦されるレシピ
【ZDDを用いたあいまい検索】
（ZDD×ZDDのあいまいマッチングと情報推薦への応用）
ZDD - tree
time (sec)
time (sec)
70.00
ZDD - tree
7000.00
60.00
text - text
6000.00
50.00
ZDD - text
【今後の課題】
 “don’t care” や様相論理，デフォルト推論などとの拡張
（もあるが，あんまりまじめには考えていない…）
 アイテム間の制約，条件，関連性などを考慮
 ZDD間のあいまいマッチングへの拡張
（例：過去に調理したレシピ群とcookpad のレシピ群とのマッチ
ングなど）
タイトル
グラニュー糖,ココア
パウダー,ベーキング 食材の入手 ガトーショコラ
パウダ,卵,無塩バ
しやすさ 風チョコケーキ
ター,薄力粉
チョコレートパ
バター,ベーキングパ
ウンドケーキ
ウダ,三温糖,卵,薄力 コメント数
コーヒー風味の
粉
ビスコッティ
×食材の入手
口どけ良好な
○コメント数
濃厚ショコラ
○ステップ数
関連レシピで条件を満たすものを探索し，提示
ステップ
かぼちゃ,たまねぎ,
にんじん,バター,
塩、胡椒,牛乳,生ク
リーム
×食材の入手
優しい味のか
×コメント数
ぼちゃスープ
×ステップ数
フィードバックレポート
改善の方向
カブのポター
コメント数
にんじん
かぶ,たまねぎ,にん
ジュスープ
じん,コンソメスープ
冷蔵庫にあるも
の素,バター,塩、胡
食材の入手
ので作る野菜
かぶ
椒,牛乳
しやすさ
チャウダー
×食材の入手 かぶとにんじ
×コメント数 んのポター
×ステップ数 ジュスープ
レーズンパン
レシピタイトル
推薦されるレシピ
5000.00
ZDD - tree
40.00
4000.00
30.00
3000.00
20.00
2000.00
10.00
1000.00
0.00
0.00
0
200,000
400,000
600,000
# input patterns
800,000
1,000,000
0
200,000
400,000
600,000
# input patterns
800,000
1,000,000