第 7 章 ディリクレ過程混合モデルに基づく共クラスタリング 56
7.7 本章のまとめ
本稿では，ディリクレ過程混合モデルに基づく離散データに対する共クラスタリ ング手法を提案した．提案手法は，事前にクラス数を与えることなく，ユーザとア イテムを同時にクラスタリングする．映画の評価データを用いた実験により，無限 関係モデルと比べて，より適切な共クラスタリング結果が得られることを確認した．
今後は，頻度データに適したモデル化や，大規模データへ適用した際には計算時間 が課題となるため，学習の効率化・高速化などについて検討したい．
第 8 章 考察
本章では，第6章と第7章で提案した推薦方式の応用について述べる．いずれも 単独で動作する推薦方式であるが，第4章において提案した推薦方式のサブルーチ ンとしても組み込み可能である．
8.1 第 6 章で提案した推薦方式の応用
第5章における割引総利得，
∑∞ t=1
γt−1r(xt),
において，利得r(xt)を，商品xtが購入されることによって得られる利益ではなく，
商品xtを購入することによってそのユーザが得られる満足度によって表現すると，
将来に渡ってそのユーザが得るであろう満足度を最大化するという 買い手 の立 場に基づいた推薦が行えるようになる．
ここで，各商品ごとのユーザの満足度を，その商品に対する評価値と捉える．す ると，次のような推薦方式を考えることができる：大量に存在する未評価の商品に対 して，評価値の予測を高速に行う第6章の推薦方式を適用することで，未評価商品 に対する評価値の予測を事前に行っておく．そして，得られた予測値を用いて，ユー ザの満足度によって表現された割引総利得を最大化する推薦ルールを求める．これ により，将来に渡って得られる利益を最大化するという 売り手 側の立場に立っ た推薦ではなく，ユーザのための推薦が可能となる．
この他，売り手が得る利益とユーザが得る満足度を足し合わせた割引総利得を用 いることなども考えられる．
第 8章 考察 81
8.2 第 7 章で提案した推薦方式の応用
多くの場合，各ユーザが購入している商品は，提供されている全商品数と比べて ごく少数である．そのような“疎”な履歴データを用いた場合，例えば，状態遷移確 率を精度良く求めることができず，その結果，“使えない”推薦ルールが得られてし まうことが想定される．実際，ユーザを“行”，商品を“列”で表現した購買行列にお いて，購買履歴行列の第(i, j)要素は，ユーザiが商品jを購入している場合1，購 入していない場合0として表現されているものとすると，1（購入）の占める割合は，
全要素の10%にも満たない場合が殆どである．
履歴データが持つこのような性質への対処法として，第7章で提案した，ユーザ と商品の共クラスタリングが有用となる．すなわち，履歴データのクラスタリング を事前に行い，類似した購買履歴を持つユーザ群，および，当該ユーザ群に購入さ れやすい商品群のみを抽出することで，“密”な履歴データを用意することができる
（図7.1参照）．このとき，推薦ルールは，ユーザクラスごとに導出される．履歴デー タが大規模になるほど，クラスタリングの効果が発揮されるものと考える．
第 9 章 結論
9.1 まとめ
推薦ルールの導出時には，従来手法における 空間的 な視点と，今回新たに導 入する 時間的 な視点の両方に基づき，購入商品履歴と推薦商品履歴の両履歴を 用いて，推薦ルールを学習する方式を検討することが重要である．本論文では，上 記考えに基づいた推薦方式の例として，3つの手法を提案した．
1つは，空間的な視点と時間的な視点の両方に基づく手法であり，残りの2つは，
空間的な視点に基づく手法である．なお，空間的な視点に基づく2手法は，それぞ れ単独でも推薦ルールの導出が可能であるが，1つ目の提案手法（空間的／時間的 な視点の両方を併せ持つ手法）に対するサブルーチンとしても転用可能である．
ここで，1つ目の提案手法において，推薦問題に限らず，他の分野へも適用する ことが可能なモデルを提案した．また，推薦ルールの導出に関して，当該分野にお いて初めて最適性について論じた．さらに，残りの2つの提案手法においては，実 データを用いた評価実験を通して提案手法の有効性を確認した．
商品を推薦した結果，ユーザにどのような反応（行動）を示して欲しいか，という 推薦すること自体の本来の目的について，当該分野ではこれまで殆ど考慮されてこ なかった．しかし，推薦の本質とは，推薦対象ユーザとの1 対1のやり取りの中で 得た，当該ユーザのこれまでの反応をもとに，次の推薦商品を決定することにある．
故に，本研究により，提案したモデルの下で“真の推薦”が初めて実現可能になった と言える．
結論 83
9.2 今後の課題
第5章において提案した推薦手法に関して，履歴データの蓄積期間における推薦 ルールの設定方法について検討を進めたい．運用期間における割引総利得を最大化 するためには，どのような戦略に従うべきなのか本論文では言及できていないため，
ランダム選択よりも良い推薦ルールを検討し，その推薦ルールを用いたもとで，提 案手法の評価を行う．その際には，実データを用いた評価を行うことや，実装面で の課題（計算量や計算精度）についても検討の視野に入れたい．
また，本研究を通して得られた個別の課題に関する検討を継続していくとともに，
より高い視点に立ち，生活をより豊かにするための推薦とは何かについて，広く深 く研究を進めていきたい．
9.3 将来の展望
ECサイトの他にも，携帯電話や自動販売機など，至る所で推薦システムの活用が 進んでいる．将来的には，普段の生活において，推薦システムは当たり前のように 存在するものになると思われる．推薦手法に関する研究が始まった頃は，ユーザの 反応履歴を蓄積することは技術的に困難な面もあったが，ここ最近，推薦履歴やそ の反応履歴を蓄積する仕組みが整備されつつある．本論文で主張する“空間的”と“ 時間的”という2 つの視点に基づく推薦方式の研究や実用化は今後さらに進んでい くものと考えられる．
付 録 A 第 7 章に関する付録
A.1 ディリクレ過程
分割Gを，
G={P(θ1), P(θ2), . . . , P(θK)},
と表す．ここで，Kは分割数を表し，P(θk)(k= 1,2, . . . , K)は各分割の割合を表す．
つまり，パラメータθkの出現確率がP(θk)であり，∑K
k=1P(θk) = 1．
ディリクレ過程は，任意の分割数Kとそれに対応する{θk, P(θk)}Kk=1，つまりG，
を与える分布であり，
G∼DP(α, G0),
と表現される．ここで，α(>0)は集中度パラメータ（スカラー値），G0は基底分布
（基底測度）をそれぞれ表す．すると，N個のパラメータの実現値{θ1, θ2, . . . , θN} が与えられた下での分割Gに対する事後分布の期待値は以下のようになる．
E[G|θ1, θ2, . . . , θN] = α
α+NG0+ 1 α+N
∑N i=1
δ(θi),
= α
α+NG0+ nk
α+N
∑K k=1
δ(θk). (A.1) ここで，関数δはDiracのデルタ関数を表し，nkは{θ1, θ2, . . . , θN}のうちで値がθk と一致するパラメータの数を表す．つまり，nk=∑N
i=1I(θk=θi)．ここで，Iは引数 が真のとき1，その他のとき0を返すインジケータ関数を表す．よって，式(A.1)の Kは{θ1, θ2, . . . , θN}におけるθの異なり数を表す．式(A.1)は， nk
N+αの確率で既に 得られたパラメータ値θkが出現し，Nα+αの確率で基底分布G0から新たにパラメー
付 録 A 第7章に関する付録 85
タ値θK+1が出現することを意味する．新たにパラメータ値が基底分布G0から出現 した場合，分割数はKからK + 1に変わる．
A.2 提案手法における Z, W の事後確率の導出
ベイズの定理より，
P(Z, W|B;α, β, γ, η) = P(B|Z, W;γ, η)P(Z;α)P(W;β)
∑
Z
∑
W P(B|Z, W;γ, η)P(Z;α)P(W;β), (A.2) となる．ここで，式(A.2)の分母は既知のデータBに関する分布であるため固定値 となる．そのため，式(A.2)の分子のみについて最大化することを考えればよい．こ こで，式(A.2)の分子は，
P(B|Z, W;γ, η)P(Z;α)P(W;β)
=
∫
Φ
∫
Θ
p(B|Z, W,Θ,Φ)p(Θ;γ)p(Φ;η)dΘdΦ×p(Z;α)p(W;β), と書け，上式の積分内は，
p(B|Z, W,Θ,Φ)p(Θ;γ)p(Φ;η)
= ∏
bi,j∈R
p(bi,j|θzi,wj, ϕwj,zi)×
∏K k=1
∏S s′=1
p(θk,s′;γ)
∏S s=1
∏K k′=1
p(ϕs,k′;η),
=
∏S s=1
∏K k=1
(θk,sϕs,k)l(k,s)×
∏K k=1
Γ(Sγ) Γ(γ)S
∏S s′=1
(θk,s′)γ−1
∏S s=1
Γ(Kη) Γ(η)K
∏K k′=1
(ϕs,k′)η−1,
=
∏K k=1
Γ(Sγ) Γ(γ)S
∏S s′=1
(θk,s′)l(k,s′)+γ−1×
∏S s=1
Γ(Kη) Γ(η)K
∏K k′=1
(ϕs,k′)l(k′,s)+η−1,
と計算される．l(k, s)は，式(7.3)のとおりである．ここで，ディレクレ分布に関す る以下の式，
∫
θk
Γ(Sγ) Γ(γ)S
∏S s′=1
(θk,s′)γ−1dθk= 1,
⇔
∫
θk
∏S s′=1
(θk,s′)γ−1dθk= Γ(γ)S Γ(Sγ),
を利用することにより，以下の積分結果を得る．
∫
Θ
∏S s′=1
(θk,s′)l(k,s′)+γ−1dΘ =
∏S
s′=1Γ(γ+l(k, s′)) Γ(Sγ+∑S
s′=1l(k, s′)),
∫
Φ
∏K k′=1
(ϕs,k′)l(k′,s)+η−1dΦ =
∏K
k′=1Γ(η+l(k′, s)) Γ(Kη+∑K
k′=1l(k′, s)), 以上の結果から，提案手法におけるZ, W の事後確率は，
P(Z, W|B;α, β, γ, η)
∝ P(B|Z, W;γ, η)P(Z;α)P(W;β),
=
∏K k=1
Γ(Sγ) Γ(γ)S
∏S
s′=1Γ(γ+l(k, s′)) Γ(Sγ+∑S
s′=1l(k, s′))
∏S s=1
Γ(Kη) Γ(η)K
∏K
k′=1Γ(η+l(k′, s)) Γ(Kη+∑K
k′=1l(k′, s))
× αK∏K
k=1(nk−1)!
α(α+ 1)· · ·(α+N −1)
βS∏S
s=1(ms−1)!
β(β+ 1)· · ·(β+M −1). となる．
87
参考文献
[1] G. Adomavicius and A. Tuzhilin. Towards the Next Generation of Recom-mender Systems: A Survey of the State-of-the-Art and Possible Extensions.
IEEE Transactions on Knowledge and Data Engineering, Vol. 17, No. 6, 2005.
[2] R. Bellman. Dynamic Programming (Princeton Landmarks in Mathematics).
Princeton University Press, 2010.
[3] J. M. Bernardo and A. F. M. Smith. Bayesian Theory. Wiley, 2000.
[4] David M. Blei and Michael I. Jordan. Variational Inference for Dirichlet Process Mixtures. Bayesian Analysis, Vol. 1, No. 1, pp. 121–144, 2006.
[5] G. E. P. Box and G. C. Tiao. Bayesian Inference in Statistical Analysis. Wiley, 1992.
[6] John S. Breese, David Heckerman, and Carl Kadie. Empirical Analysis of Predictive Algorithms for Collaborative Filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 43–52, Madison, Wisconsin, US, July 1998.
[7] Gang Chen, Fei Wang, and Changshui Zhang. Collaborative Filtering Using Orthogonal Nonnegative Matrix Tri-factorization. InProceedings of 7th IEEE International Conference on Data Mining (ICDM), Workshop on High Perfor-mance Data Mining, Omaha NE, US, October 2007.
[8] S. Deerwester, Susan Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman.
Indexing by Latent Semantic Analysis. Journal of the Society for Information Science, Vol. 41, No. 6, pp. 391–407, 1990.
[9] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society Series B, Vol. 34, pp. 1–38, 1977.
[10] Meghana Deodhar and Joydeep Ghosh. A Framework for Simultaneous Co-clustering and Learning from Complex Data. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), pp. 250–259, San Jose, California, US, August 2007.
[11] Mukund Deshpande and George Karypis. Item-Based Top-N Recommendation Algorithms. ACM Trans. Information Systems, Vol. 22, No. 1, pp. 143–177, January 2004.
[12] Inderjit S. Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. InProceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), pp. 269–274, San Francisco CA, US, Augst 2001.
[13] Inderjit S. Dhillon, Subramanyam Mallela, and Dharmendra S. Modha.
Information-Theoretic Co-clustering. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), pp. 89–98, Washington, DC, USA, Augst 2003.
[14] Sandrine Dudoit and Jane Fridlyand. A prediction-based resampling method for estimating the number of clusters in a dataset. Genome Biology, Vol. 3, No. 7, pp. 1–21, 2002.
[15] Lise Getoor and Mehran Sahami. Using Probabilistic Relational Models for Collaborative Filtering. In Proceedings of Workshop on Web Usage Analysis and User Profiling (WEBKDD-99), San Diego, CA, US, August 1999.
[16] G.Shani, D.Heckerman, and R. I. Brafman. An MDP-Based Recommender System. Journal of Machine Learning Research, Vol. 6, pp. 1265–1295, 2005.
参考文献 89
[17] Thomas Hofmann. Latent Semantic Models for Collaborative Filtering. ACM Trans. Information Systems, Vol. 22, No. 1, pp. 89–115, January 2004.
[18] Thomas Hofmann. Unspervised Learning by Probabilistic Latent Semantic Analysis. Machine Learning, Vol. 42, pp. 177–196, 2004.
[19] T. Iwata, K. Saito, and T. Yamada. Recommendation Method for Improving Customer Lifetime Value. IEEE Transactions on Knowledge and Data Engi-neering, Vol. 20, No. 9, pp. 1254–1263, 2008.
[20] S. Jain and R. M. Neal. A Split-Merge Markov Chain Monte Carlo Procedure for the Dirichlet Process Mixture Model. Journal of Computational and Graphical Statistics, Vol. 13, pp. 158–182, 2004.
[21] Charles Kemp, Josh Tenenbaum, Tom Griffiths, Takeshi Yamada, and Naonori Ueda. Learning Systems of Concepts with an Infinite Relational Model. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI), pp. 381–388, Boston, Massachusetts, US, July 2006.
[22] James Kennedy and Russell Eberhart. Particle swarm optimization. In Proceed-ings of the IEEE International Conference on Neural Networks, pp. 1942–1948, Piscataway, NJ, US, July 1995.
[23] S. Kullback and R.A. Leibler. On information and sufficiency. Annals of Math-ematical Statistics, Vol. 22, pp. 79–86, 1951.
[24] K. Kurihara, Y. Kameya, and T. Sato. Discovering Concepts from Word Co-occurrences with a Relational Model. Transactions of the Japanese Society for Artificial Intelligence, Vol. 22, No. 2, pp. 218–226, 2007.
[25] Greg Linden, Brent Smith, and Jeremy York. Amazon.com Recommendations:
Item-to-Item Collaborative Filtering. IEEE Internet Computing, Vol. 7, No. 1, pp. 76–80, January/February 2003.
[26] Benjamin Marlin. Modeling User Rating Profiles For Collaborative Filtering.
InProceedings of the 17th Annual Conference on Neural Information Processing Systems (NIPS-2003), British Columbia, Canada, December 2001.
[27] Benjamin Marlin. Collaborative Filtering: A Machine Learning Perspective.
Master’s thesis, University of Toronto, 2004.
[28] Toshiyasu Matsushima and Shigeich Hirasawa. Bayes universal coding algo-rithm for side information context tree models. In IEEE International Sympo-sium of Information Theory(ISIT2005), pp. 2345–2348, 2005.
[29] Jon D. McAuliffe, David M. Blei, and Michael I. Jordan. Nonparametric empir-ical Bayes for the Dirichlet process mixture model. Statistics and Computing, Vol. 16, No. 1, pp. 5–14, 2006.
[30] Radford M. Neal. Markov chain sampling methods for Dirichlet process mixture models.Journal of Computational and Graphical Statistics, Vol. 9, pp. 249–265, 2000.
[31] Sean Owen, Robin Anil, Ted Dunning, and Ellen Friedman. Mahout in Action.
Manning Publications Co., 2011.
[32] Al Mamunur Rashid, Shyong K. Lam, George Karypis, and John Riedl.
ClustKNN: A Highly Scalable Hybrid Model & Memory-Based CF Algorithm.
In Proceedings of the 8th ACM SIGKDD Workshop on Web Mining and Web Usage Analysis(WEBKDD), 2006.
[33] Carl Edward Rasmussen. The Infinite Gaussian Mixture Model. InProceedings of 12th Conference on Neural Information Processing Systems (NIPS), pp. 554–
560, Denver, CO, US, November/December 1999.
[34] Manjeet Rege, Ming Dong, and Farshad Fotouhi. Co-clustering Documents and Words Using Bipartite Isoperimetric Graph Partitioning. In Proceedings of the