関連研究その４
丹羽智史(2006)、情報処理学会論文誌 Vol47 No5 PP1382-1392, 2006/5
Folksonomyマイニングに基づくWebページ推論システム
1. はじめに
Webの爆発的普及→推薦システムの開発。発展途上。
多くのシステムが核にCFを利用。Li(2004), Kazienko(2004), Golovin(2004)
大まかな手順。（ユーザベース）
Sparcity問題の説明。（ページM＞＞ユーザNが原因）
本稿では、
・タグを用いるソーシャルブックマークシステム（SBM)を活用し、Sparcity問題への対処を行う。
・タグのクラスタ化で表記ゆれに対応
2. Folksonomyとソーシャルブックマーク
2.1 Folksonomy
Taxonomy（Yahooのディレクトリなど）の逆。これを代わる分類手法→Folksonomy
特徴：ユーザが自由に決めたKW、１文書複数タグ
課題：表記ゆれ
2.2 ソーシャルブックマーク(SBM)
3. システムの仕組み
3.1 システムの概要
Sparcity問題対策
従来：ユーザの嗜好を情報との親和性で直接的に表現。 ユーザ類似度がほぼゼロ。
本稿：ユーザの嗜好をタグとの親和性で間接的に表現。
表記ゆれ対策
タグのクラスタリング。 ユーザ嗜好をタグクラスタとの親和性で、より抽象化。
ステップ
(1)データ収集、(2)ユーザとタグの親和度計算、(3)タグ間の親和度計算、(4)タグのクラスタ化、
(5)ユーザとタグクラスタ、(6)タグクラスタ別の推薦生成、(7)ユーザ別推薦ページ生成
3.2 各ステップの詳細
3.2.1 データ収集
公開データから、ページ(P)・タグ(T)・ユーザ(A)のグラフ構造を生成。
タグ・ページ間の重み：異なるユーザにより関連づけられた回数 w(P,T)
bookmark(A)：ユーザAのブックマーク
3.2.2 ユーザとタグの親和度を計算
親和度 rel(A, T) = Σ rel(P_i, T)
親和度 rel(P, T) = TF(P, T) × IDF(T)
TF(P, T) ： Pにつく全タグの中のTの占める割合 w(P,T) / Σw(P,T_i)
IDF(T) ：Tの希少性 ΣΣw(P_i, T_i) / Σw(P_i, T)
3.2.3 タグ間の類似度を計算
類似度 rel(T, t) = Σ w(P_i, T) × rel(P_i, t)
※rel(T, t) ≡ rel(t, T)ではない。
3.2.4 タグのクラスタ化
タグt間類似度(＞閾値V_limit )の最大タグT → 親タグ
if ＜閾値 → t自信がtの親タグ
if rel(T,t) ＜ rel(t,T) → T側が親
クラスタサイズが閾値C_maxを超えるまで、親方向にマージしていく。
V_limit、C_maxの大きさでクラスタ粒度を調整
3.2.5 ユーザとタグクラスタの親和度を計算
親和度 rel(A, C) = Σ rel(A, T_i)
3.2.6 タグクラスタ別に推薦ページを計算
推薦ポイント point(C, P) = Σ w(P, T_i)
3.2.7 ユーザ別に推薦ページを計算
ユーザ別推薦ポイント point(A, P) = Σ rel(A, C_i) × point(C_i, P)
4. 実験
実験(A)：ブックマークデータから精度を評価 ー クラスタリング粒度の影響の評価
実験(B)：推薦ページをユーザにより評価 ー 実験Aで求めた粒度パラメータ設定で評価
4.1 実験概要（実験(A)(B)共通部分）
4.1.1 データ収集
はてなブックマークの公開データを利用
500K人、1Mページ 以上 (2005/8時点)
アクティブユーザ 5.8K人分のデータ。 5K人、57K頁分、Tag9.3K個(6回以上利用は2175個)を訓練データ。
タグ⇔頁のリンク 84K本、 ユーザ⇔頁のリンク210K本
4.1.2 タグのクラスタリング
クラスタリングを５段階に調整。 図６。
3.2.2〜3.2.6の処理に１〜２時間程度かかった。ここが前処理。 3.2.7のみが体感速度に影響。
クラスタリング結果を具体例を見ながら検討すると、
・小さなクラスタで同義語クラスタが見られる。 表記ゆれを吸収できている。
・大きなクラスタで独立性が高い話題も吸収された。
→適切なクラスタリングが行われている。
4.2 実験(A)
4.2.1 実験(A)の評価方法
・訓練データとテストデータにはランダムに分ける。
・訓練データから 推薦システムを作る。
・テストデータのブックマークをクエリ頁とテスト頁の２つに分ける。
・クエリ頁から推薦システムにより推薦頁を生成し、テスト頁と比較する。
(1)再現率 ＝ 一致頁数(H) / テスト頁数(T)
(2)適合率 ＝ 一致頁数(H) / 推薦頁数(R =30)
4.2.2 実験(A)の結果
ユーザのブックマーク頁数毎にクラス分けし評価。
ブックマーク数少ユーザ：クラスタリング粒度小さい方が結果よし。（★ブックマーク数が少ないので一致しずらい）
・テスト頁の話題の集計効果が効かないため。
・同意語クラスタは効果あり
ブックマーク数多ユーザ：クラスタリング粒度大きいのが効く。
・集計、抽象化が狙い通り効いている。
4.3 実験(B)
4.3.1 実験(B)の評価方法
パラメータは実験Aのを利用。 参加者は１０人。
実験Aで構築した推奨システムに、ブックマークデータを入力。
・その頁に親和性の高いタグ３０個
・ユーザへの推奨頁３０個
を計算。 それぞれを、(a)興味あり自分向け (b)興味あり万人向け (c)興味なし でユーザに評価してもらう。
4.3.2 実験(B)の結果
システムにあった頁と一致するブックマーク数で、ユーザを分類(≧50 <50)
一致数が多いユーザ側の方が適合率が良い。
5. 考察と関連研究
タグクラスタリングは
・推薦精度に直接の影響はない。（★？？？）
・計算時間短縮に効果あり。
・表記ゆれを吸収できた。
・実用の際も実験Aと類似の実験でクラスタリング粒度を決定できる。（★？？？）
本システムのユーザテストによる精度は、他方式と遜色なく、コストも低い。
他システムはアクセス履歴を主要な情報源とする。→特定サイトに限定される。
Li(2004)は、さらにWeb頁内容、リンク構造を解析している。
Zhu(2005)はサイト限定はない。端末側での履歴記録を行う。
本手法と精度も近い。 端末側の処理がないこと、訓練データにSBMが使えることが本方式の優位点。
Nicolas(2004)では、Taxonomyでの抽象化でユーザ間類似度を計算している。
6. 結論
SBMを元にWeb全体を対象にした推薦システムを構築。
タグでのユーザ嗜好表現でSparcity問題を対策
タグのクラスタリングで(計算時間短縮と)表記ゆれを対策。
-
- -
コメント
良い点
・Webページの数に比べ、より小さなタグ集合に着目してSparsity問題の解決をしている点。(1.右)
・タグの表記ユレへの対処を行い（3.2.4）、実現できている点（図８）。
・前処理とユーザクエリ応答に処理を分け、体感速度を考慮している点。(4.1.2)
・はてなブックマークで公開されているデータを使って分析している点。 類似実験の際、データソースとして有用では？
・再現率、適合率のような計測性が高いが、正しい評価をしていない可能性のある実験だけでなく、
推奨ページ自体を人間に評価させる実験の両方を行っている点。
悪い点
★タグ間の類似度計算に個人の情報が反映されていない。（3.2.3）
全ユーザの総意としてのタグ構造になっている。
例えば、DesignPatternをJavaのサブクラスとして扱う点。他言語利用や言語非依存の人々には適切な階層構造ではない。
・クラスタリングが適切でない可能性大。(3.2.4、4.1.2)
タグクラスタをクラスタサイズで閾値を決めている。 これではタグ表記のゆれのバリエーションの多さの影響を受ける。
★タグの多次元性が失われている。
例えば、rubyはオブジェクト指向言語であり、スクリプト言語であり、クラウドサービス言語である。
・実験Aで、クエリ用ページ内に推薦ページと一致するものがある場合の考慮がないのではないか。(4.2.1)
・クラスタリングサイズを大きくすると、ブックマーク数が多いユーザは再現性があがるのは当たり前。
それが、それらのユーザにとって有用かは疑問。ブックマーク数が多いユーザは、詳細に情報を分類しており、
抽象度が高い推薦が話題ズレと解釈される可能性が高い。
逆に、ブックマーク数が少ないユーザでは、抽象度をあげることにより再現率の低下が見られるが、有用な情報を
提供できている可能性は否定できない。
・実験Bで、テストユーザが提供したブックマークに対応するタグ情報を提供していない。(4.3.1)
それでは、推薦精度が悪くなるのではないか。
・クラスタリングは推薦制度に直接影響ないとしているが、間違いでは。
ユーザによる評価の際、クラスタリングサイズの大小により、ブックマークしていなかったが関係ある頁を紹介される
確率が変化する可能性があるが、その実験ができていない。(5.)
・適切なクラスタリング粒度は実験Aでは求められない。
関心ある頁をすべてブックマークしているわけではないので、実験Aで粒度を求めるのは危険。
