NetflixPrize中的

協(xié)同過濾算法吳金龍導(dǎo)師：鄂維南、李鐵軍2010-05-28目前一頁\總數(shù)五十三頁\編于十五點(diǎn)目錄PartI：背景介紹推薦系統(tǒng)NetflixPrize協(xié)同過濾（CollaborativeFiltering）問題PartII：協(xié)同過濾（CollaborativeFiltering）模型評分預(yù)測模型模型組合方法PartIII：三維協(xié)同過濾：立方填補(bǔ)應(yīng)用背景評分預(yù)測模型PartIV：總結(jié)與展望吳金龍@SMS.(2010-05-28)2NetflixPrize中的協(xié)同過濾算法目前二頁\總數(shù)五十三頁\編于十五點(diǎn)PartI：背景介紹推薦系統(tǒng)NetflixPrize協(xié)同過濾（CollaborativeFiltering）問題吳金龍@SMS.(2010-05-28)3NetflixPrize中的協(xié)同過濾算法目前三頁\總數(shù)五十三頁\編于十五點(diǎn)Yep，推薦系統(tǒng)!PartI：背景介紹——推薦系統(tǒng)依據(jù)信息檢索的方式，互聯(lián)網(wǎng)的發(fā)展可分為三個(gè)階段門戶網(wǎng)站階段，典型代表為Yahoo為互聯(lián)網(wǎng)上的重要信息提供導(dǎo)航搜索引擎階段，典型代表為Google依據(jù)用戶輸入的關(guān)鍵詞，返回給用戶與關(guān)鍵詞相關(guān)的網(wǎng)頁個(gè)性化推薦階段依據(jù)用戶的特點(diǎn)和需求，為用戶提供個(gè)性化的服務(wù)推薦系統(tǒng)作用利用歷史，預(yù)測現(xiàn)在與未來常用領(lǐng)域傳統(tǒng)的零售行業(yè)互聯(lián)網(wǎng)行業(yè)搜索引擎：Google電子商務(wù)：Amazon社會化網(wǎng)絡(luò)服務(wù)（SNS）：Facebook吳金龍@SMS.(2010-05-28)4NetflixPrize中的協(xié)同過濾算法目前四頁\總數(shù)五十三頁\編于十五點(diǎn)推薦系統(tǒng)的分類PartI：背景介紹——推薦系統(tǒng)基于內(nèi)容的過濾（content-basedfiltering，簡記為CBF）根據(jù)事先抽取出的產(chǎn)品或用戶特征產(chǎn)生推薦主要缺點(diǎn)需要預(yù)處理產(chǎn)品以得到代表它們的特征無法發(fā)現(xiàn)用戶并不熟悉但具有潛在興趣的產(chǎn)品種類協(xié)同過濾（collaborativefiltering，簡記為CF）收集用戶過去的行為以獲得其對產(chǎn)品的顯式或隱式信息優(yōu)點(diǎn)不需要預(yù)處理產(chǎn)品或用戶的特征，故而不依賴于特定的應(yīng)用領(lǐng)域主要缺點(diǎn)冷啟動：對于新用戶或新產(chǎn)品，無法產(chǎn)生可靠推薦可擴(kuò)展性：算法往往需要較大的時(shí)間和空間復(fù)雜度兩者的組合（hybrid）組合上面兩種方法，以克服它們各自的缺點(diǎn)，并融合它們特有的優(yōu)點(diǎn)吳金龍@SMS.(2010-05-28)5NetflixPrize中的協(xié)同過濾算法目前五頁\總數(shù)五十三頁\編于十五點(diǎn)NetflixPrize介紹PartI：背景介紹——NetflixPrizeNetflix

：美國一家提供在線電影租賃服務(wù)的公司2006年10月，Netflix建立了NetflixPrize競賽，并對外發(fā)布了一個(gè)電影評分（評分為1,…,5的整數(shù)）數(shù)據(jù)集NetflixPrize競賽最終的目標(biāo)是在Cinematch推薦系統(tǒng)的基礎(chǔ)上獲得10%的改進(jìn)，其預(yù)測精度由均方根誤差（RMSE）來衡量：GrandPrize，獎金為一百萬美元第一個(gè)達(dá)到10%改進(jìn)的參賽團(tuán)隊(duì)ProgressPrize，獎金為五萬美元每年排名第一的參賽團(tuán)隊(duì)

吳金龍@SMS.(2010-05-28)6NetflixPrize中的協(xié)同過濾算法目前六頁\總數(shù)五十三頁\編于十五點(diǎn)NetflixPrize數(shù)據(jù)集的結(jié)構(gòu)PartI：背景介紹——NetflixPrize給出了整體訓(xùn)練數(shù)據(jù)集（WTS）中的評分值及對應(yīng)的評分時(shí)間參賽團(tuán)隊(duì)提交整個(gè)QualifyingSet上的預(yù)測評分值CompleteNetflixPrizeDataset480,189個(gè)用戶17,770部電影FirstPartofTrainingSet(FPTS)99,072,112個(gè)評分HeldOutSet(HOS)4,225,526個(gè)評分WholeTrainingSet(WTS)100,480,507個(gè)評分ProbeSetQuizSetTestSet吳金龍@SMS.(2010-05-28)7NetflixPrize中的協(xié)同過濾算法目前七頁\總數(shù)五十三頁\編于十五點(diǎn)NetflixPrize競賽的里程碑PartI：背景介紹——NetflixPrize2009年6月26日團(tuán)隊(duì)BellKor’sPragmaticChaos(BPC)的提交在QuizSet上獲得0.8558的預(yù)測誤差，改進(jìn)首次超過10%，競賽進(jìn)入最后三十天角逐2009年9月10日NetflixPrize官方正式宣布BPC為競賽的最終勝利者，獲得GrandPrize，整個(gè)競賽正式結(jié)束已頒發(fā)的獎項(xiàng)及獲獎團(tuán)隊(duì)獎項(xiàng)獲獎團(tuán)隊(duì)TestRMSEProgressPrize2007KorBell0.8723ProgressPrize2008BellKorinBigChaos0.8627GrandPrizeBellKor’sPragmaticChaos0.8567吳金龍@SMS.(2010-05-28)8NetflixPrize中的協(xié)同過濾算法目前八頁\總數(shù)五十三頁\編于十五點(diǎn)NetflixPrize數(shù)據(jù)集的特點(diǎn)PartI：背景介紹——NetflixPrize極度稀疏性WTS中包括了480,189個(gè)用戶對17,770部電影的評分，而評分值只有100,480,507個(gè)，也即近99%的評分值未知長尾性大部分用戶只對極少的電影進(jìn)行了評分四分之一的用戶只對少于36部電影進(jìn)行了評分大部分電影只收到極少的用戶評分四分之一的電影只收到少于190個(gè)用戶的評分時(shí)間性數(shù)據(jù)集中評分的特點(diǎn)隨著時(shí)間的變化在不斷變化吳金龍@SMS.(2010-05-28)9NetflixPrize中的協(xié)同過濾算法目前九頁\總數(shù)五十三頁\編于十五點(diǎn)Ha，協(xié)同過濾（CF）?PartI：背景介紹——推薦系統(tǒng)矩陣填補(bǔ)問題給定矩陣的少部分元素，預(yù)測其它未知元素的值E.Candèsetal.(Found.ofComput.Math.,2008;SIAMJ.onOptimization,2008;Proc.ofIEEE,2009;…)探討了矩陣填補(bǔ)的理論和算法但他們的算法目前還無法應(yīng)用于實(shí)際數(shù)據(jù)集產(chǎn)品1產(chǎn)品2產(chǎn)品3……產(chǎn)品M用戶113??用戶22?24用戶3??4?用戶45?53…………………………用戶U?3?2吳金龍@SMS.(2010-05-28)10NetflixPrize中的協(xié)同過濾算法目前十頁\總數(shù)五十三頁\編于十五點(diǎn)PartII：協(xié)同過濾（CollaborativeFiltering）模型常用模型鄰居（kNN）模型受限玻爾茲曼機(jī)（RBM）模型因子模型矩陣分解（MF）模型二項(xiàng)矩陣分解（BMF）模型修正模糊聚類（MFCM）模型模型組合方法吳金龍@SMS.(2010-05-28)11NetflixPrize中的協(xié)同過濾算法目前十一頁\總數(shù)五十三頁\編于十五點(diǎn)常用模型PartII：CF模型——常用模型鄰居（kNN）模型（R.Belletal.,ICDM,2007;G.Takácsetal.,SIGKDD,2007;…）根據(jù)相似用戶對此電影的評分（或此用戶對相似電影的評分）獲得推薦特點(diǎn)易于編程實(shí)現(xiàn)好的可解釋性空間復(fù)雜度很高受限玻爾茲曼機(jī)（RBM）模型

（R.Salakhutdinovetal.,ICML,2007）一層隱藏單元（hiddenunits）H代表用戶特征一層可視化單元（visibleunits）R代表評分特點(diǎn)好的預(yù)測精度時(shí)間復(fù)雜度很高吳金龍@SMS.(2010-05-28)12NetflixPrize中的協(xié)同過濾算法目前十二頁\總數(shù)五十三頁\編于十五點(diǎn)因子（Factor）模型PartII：CF模型——Factor因子模型假設(shè)（R.Bell&Y.Koren,ICDM,2007;A.Paterek,1st

Netflix-KDDWorkshop,2007;…）每個(gè)用戶和電影都可由少數(shù)若干個(gè)因子來刻畫當(dāng)一個(gè)用戶和某部電影的因子向量相匹配時(shí)，此用戶會對該部電影給予高的評分原始因子模型（通常稱為矩陣分解模型）的表達(dá)式為其中和分別為用戶和電影的潛在因子矩陣上述表達(dá)式是奇異值分解的一種簡化形式吳金龍@SMS.(2010-05-28)13NetflixPrize中的協(xié)同過濾算法目前十三頁\總數(shù)五十三頁\編于十五點(diǎn)因子（Factor）模型的特點(diǎn)PartII：CF模型——Factor因子模型vs.鄰居模型因子模型可以獲得更高的預(yù)測精度因子模型vs.受限玻爾茲曼機(jī)模型因子模型需要更少的訓(xùn)練時(shí)間吳金龍@SMS.(2010-05-28)14NetflixPrize中的協(xié)同過濾算法目前十四頁\總數(shù)五十三頁\編于十五點(diǎn)矩陣分解（MF）模型PartII：CF模型——Factor——MF矩陣分解模型（MatrixFactorization，簡記為MF）可以看成是一種有向圖模型（D.Lin&L.Mackey,2007;R.Salakhutdinov&A.Mnih,NIPS,2008;ICML,2008）吳金龍@SMS.(2010-05-28)15NetflixPrize中的協(xié)同過濾算法目前十五頁\總數(shù)五十三頁\編于十五點(diǎn)矩陣分解（MF）的模型假設(shè)PartII：CF模型——Factor——MF用戶和電影的因子向量各自滿足正態(tài)分布且相互獨(dú)立用戶u對電影m的評分隨機(jī)變量滿足均值為，方差為的正態(tài)分布以上的正態(tài)分布對于不同的

u或m是相互獨(dú)立的吳金龍@SMS.(2010-05-28)16NetflixPrize中的協(xié)同過濾算法目前十六頁\總數(shù)五十三頁\編于十五點(diǎn)矩陣分解（MF）模型假設(shè)的不合理性PartII：CF模型——Factor——MFMF假設(shè)在給定因子向量時(shí)，用戶u對電影m的評分變量滿足正態(tài)分布此假設(shè)對于離散協(xié)同過濾（CF）問題并不合理例如，對于NetflixPrize問題，真實(shí)的評分只在{1,2,3,4,5}內(nèi)使用多項(xiàng)分布表示評分（Marlin,NIPS,2003;master’sthesis,2004）但多項(xiàng)分布的各個(gè)取值之間是無序的，它可能是多峰的（multimodal）的我們建議使用二項(xiàng)分布表示評分（

J.Wu,ICDM,2009）吳金龍@SMS.(2010-05-28)17NetflixPrize中的協(xié)同過濾算法目前十七頁\總數(shù)五十三頁\編于十五點(diǎn)二項(xiàng)矩陣分解（BinomialMF）PartII：CF模型——Factor——BMF使用二項(xiàng)分布表示評分的直觀意義對于NetflixPrize問題，用戶可以給予一部電影1至5顆用戶以某個(gè)固定的喜好程度把每顆星星放入兩籃（“喜愛”與“不喜愛”）中的其中一個(gè)其中的喜好程度與相應(yīng)的用戶和電影有關(guān)最終獲得的評分即滿足二項(xiàng)分布，如上圖中評分為3喜愛不喜愛吳金龍@SMS.(2010-05-28)18NetflixPrize中的協(xié)同過濾算法目前十八頁\總數(shù)五十三頁\編于十五點(diǎn)二項(xiàng)矩陣分解（BMF）的模型假設(shè)PartII：CF模型——Factor——BMF用戶和電影的因子向量各自滿足正態(tài)分布且相互獨(dú)立用戶u對電影m的評分隨機(jī)變量滿足二項(xiàng)分布其中的S為界定允許評分范圍的定值（對于NetflixPrize問題，S=5），而偏好參數(shù)吳金龍@SMS.(2010-05-28)19NetflixPrize中的協(xié)同過濾算法目前十九頁\總數(shù)五十三頁\編于十五點(diǎn)二項(xiàng)矩陣分解（BMF）的模型訓(xùn)練PartII：CF模型——Factor——BMFBMF中因子P和Q的對數(shù)后驗(yàn)分布為使用兩種方法最大化此后驗(yàn)分布或數(shù)據(jù)似然梯度上升法（GradientAscent）BMF算法變分EM法（VariationalEM）PBMF算法算法的具體過程見博士論文P56-60或J.Wu(ICDM,2009)吳金龍@SMS.(2010-05-28)20NetflixPrize中的協(xié)同過濾算法目前二十頁\總數(shù)五十三頁\編于十五點(diǎn)實(shí)驗(yàn)結(jié)果：算法MFvs.算法BMFPartII：CF模型——Factor——實(shí)驗(yàn)結(jié)果當(dāng)固定因子數(shù)K=40，懲罰系數(shù)λ分別為0.025和0.0015時(shí)，算法MF和BMF獲得的預(yù)測誤差見下表對于兩個(gè)算法，更小的學(xué)習(xí)率都可以產(chǎn)生更低的預(yù)測誤差，但同時(shí)算法的收斂速度也變得更慢逐漸降低學(xué)習(xí)率經(jīng)過77次迭代后算法BMF的ProbeRMSE降至0.9098具體過程見博士論文P70-71或J.Wu(ICDM,2009)學(xué)習(xí)率η算法MF算法BMF迭代步數(shù)ProbeRMSE迭代步數(shù)ProbeRMSE0.004470.923738270.9181980.002910.916908560.9133620.0011820.9136631150.9107210.00053610.9119192310.909483吳金龍@SMS.(2010-05-28)21NetflixPrize中的協(xié)同過濾算法目前二十一頁\總數(shù)五十三頁\編于十五點(diǎn)實(shí)驗(yàn)結(jié)果：算法PMFvs.算法PBMFPartII：CF模型——Factor——實(shí)驗(yàn)結(jié)果當(dāng)因子數(shù)K

取不同值時(shí)，算法PMF和PBMF獲得的ProbeRMSE隨著迭代步數(shù)的變化圖吳金龍@SMS.(2010-05-28)22NetflixPrize中的協(xié)同過濾算法目前二十二頁\總數(shù)五十三頁\編于十五點(diǎn)MF和BMF模型的優(yōu)勢與劣勢PartII：CF模型——Factor優(yōu)勢程序容易實(shí)現(xiàn)較低的時(shí)間和空間復(fù)雜度（使用梯度上升法求解）可以獲得很好的預(yù)測精度劣勢推薦結(jié)果沒有很好的可解釋性結(jié)果中的用戶和電影因子到底是什么吳金龍@SMS.(2010-05-28)23NetflixPrize中的協(xié)同過濾算法目前二十三頁\總數(shù)五十三頁\編于十五點(diǎn)MF模型vs.FuzzyC-means模型PartII：CF模型——Factor——MFCM較之MF模型的因子解釋，聚類思想更被人認(rèn)可典型的聚類模型包括k-means和fuzzyc-means（FCM）聚類模型在NetflixPrize上不能獲得很高的預(yù)測精度能否構(gòu)造單一模型，使得它擁有MF模型的精度，并具有聚類模型好的可解釋性具體地說，如何組合MF模型和FCM模型吳金龍@SMS.(2010-05-28)24NetflixPrize中的協(xié)同過濾算法目前二十四頁\總數(shù)五十三頁\編于十五點(diǎn)FuzzyC-means（FCM）聚類模型介紹PartII：CF模型——Factor——MFCMFCM最小化目標(biāo)函數(shù)（

D.Lin&L.Mackey,2007）使用下面的步驟迭代更新中心矩陣C和概率矩陣Z更新每個(gè)類的中心向量（k=1,...,K）：更新每個(gè)用戶屬于各類的概率值（u=1,...,U;k=1,...,K）：在獲得了模型參數(shù)值后，使用下式獲得預(yù)測評分吳金龍@SMS.(2010-05-28)25NetflixPrize中的協(xié)同過濾算法目前二十五頁\總數(shù)五十三頁\編于十五點(diǎn)修正模糊聚類（ModifiedFCM）模型PartII：CF模型——Factor——MFCM如何改進(jìn)FCM既然最終使用

獲得預(yù)測評分，為什么不直接最小化訓(xùn)練數(shù)據(jù)集上的預(yù)測誤差相比于FCM的目標(biāo)函數(shù)，一個(gè)更加直接且自然的目標(biāo)函數(shù)為其中Z為概率矩陣，滿足Z≥0，且Z1=1。修正模糊聚類（MFCM）模型求解優(yōu)化問題吳金龍@SMS.(2010-05-28)26NetflixPrize中的協(xié)同過濾算法目前二十六頁\總數(shù)五十三頁\編于十五點(diǎn)FCM模型vs.MFCM模型PartII：CF模型——Factor——MFCM如果取FCM目標(biāo)函數(shù)中的指數(shù)參數(shù)α=2，并取其中的范數(shù)為2-范數(shù)，則目標(biāo)函數(shù)而MFCM的目標(biāo)函數(shù)可以寫為MFCM不能使用交替更新中心C和概率Z的方法進(jìn)行求解使用（非）零動量梯度下降法求解MFCM使用兩種方法處理其中的約束條件懲罰處理約束方法MFCM1算法指數(shù)融入約束方法MFCM2算法具體算法見博士論文P64-66或J.Wu&T.Li(2ndNetflix-KDDWorkshop,2008)吳金龍@SMS.(2010-05-28)27NetflixPrize中的協(xié)同過濾算法目前二十七頁\總數(shù)五十三頁\編于十五點(diǎn)MF模型vs.MFCM模型PartII：CF模型——Factor——實(shí)驗(yàn)結(jié)果當(dāng)因子數(shù)K=40，算法MF和MFCM1的懲罰系數(shù)λ=0.025

，而算法MFCM2的懲罰系數(shù)λ=0.0002且對應(yīng)的動量μ=0.85時(shí)，各個(gè)算法獲得的預(yù)測誤差見下表結(jié)果表明算法MFCM1的預(yù)測精度高于MF，但MFCM1最終獲得的概率矩陣并不嚴(yán)格滿足約束條件算法MFCM2的預(yù)測精度低于MF，但MFCM2最終獲得的概率矩陣嚴(yán)格滿足約束條件算法迭代步數(shù)ProbeRMSEMF370.920124MFCM1400.918029MFCM21120.922317吳金龍@SMS.(2010-05-28)28NetflixPrize中的協(xié)同過濾算法目前二十八頁\總數(shù)五十三頁\編于十五點(diǎn)MF模型vs.MFCM模型PartII：CF模型——Factor——實(shí)驗(yàn)結(jié)果類似于MF算法，對于更小的學(xué)習(xí)率，MFCM1和MFCM2算法獲得更低的預(yù)測誤差，但同時(shí)收斂速度也變得更慢同樣可以使用逐漸降低學(xué)習(xí)率的方法在更少的迭代次數(shù)中獲得更高的預(yù)測精度具體見J.Wu&T.Li(2ndNetflix-KDDWorkshop,2008)算法學(xué)習(xí)率η迭代步數(shù)ProbeRMSEMFCM10.004400.9180290.002850.9160280.0011760.915017MFCM20.006810.9232330.0041120.9223170.0021990.921644吳金龍@SMS.(2010-05-28)29NetflixPrize中的協(xié)同過濾算法目前二十九頁\總數(shù)五十三頁\編于十五點(diǎn)模型組合方法PartII：CF模型——模型組合方法單個(gè)模型通常只考慮可以產(chǎn)生推薦的因素中的某個(gè)方面鄰居模型只考慮評分?jǐn)?shù)據(jù)中的局部作用因子模型只考慮評分?jǐn)?shù)據(jù)中的全局作用組合多個(gè)模型的預(yù)測結(jié)果以便同時(shí)考慮多種因素吳金龍@SMS.(2010-05-28)30NetflixPrize中的協(xié)同過濾算法目前三十頁\總數(shù)五十三頁\編于十五點(diǎn)組合方法的基本框架PartII：CF模型——模型組合方法訓(xùn)練利用FPTS分別訓(xùn)練各個(gè)模型；記第k個(gè)模型對ProbeSet的預(yù)測評分為，并記把ProbeSet放回FPTS，使用WTS重新訓(xùn)練每個(gè)模型（訓(xùn)練過程中所使用的模型參數(shù)完全同上一步）；記第k個(gè)模型對QualifyingSet的預(yù)測評分為，并記組合利用各個(gè)模型獲得的ProbeSet上的預(yù)測評分X以及ProbeSet上的真實(shí)評分b，訓(xùn)練模型組合方法f(·)；最終獲得QualifyingSet上的組合預(yù)測評分f(Y)FirstPartofTrainingSet(FPTS)ProbeSetQuizSetTestSetFirstPartofTrainingSet(FPTS)ProbeSetQualifyingSet吳金龍@SMS.(2010-05-28)31NetflixPrize中的協(xié)同過濾算法目前三十一頁\總數(shù)五十三頁\編于十五點(diǎn)組合模型預(yù)測結(jié)果的常用方法PartII：CF模型——模型組合方法線性回歸簡單線性回歸即f(X)=Xβ，其中回歸系數(shù)β可以通過最小化如下目標(biāo)函數(shù)獲得：

也即分片線性回歸把X中的評分按照某種規(guī)則進(jìn)行分片，然后在每片中使用簡單線性回歸通常使用評分支持度進(jìn)行分片神經(jīng)網(wǎng)絡(luò)其輸出層只有一個(gè)神經(jīng)單元其他預(yù)測模型吳金龍@SMS.(2010-05-28)32NetflixPrize中的協(xié)同過濾算法目前三十二頁\總數(shù)五十三頁\編于十五點(diǎn)實(shí)驗(yàn)結(jié)果PartII：CF模型——模型組合方法我們選出93個(gè)模型預(yù)測結(jié)果，這些結(jié)果來源于鄰居模型（12個(gè)）受限玻爾茲曼機(jī)模型（15個(gè)）因子模型（41個(gè)）聚類模型（7個(gè)）幾個(gè)模型的（序貫）組合結(jié)果（18個(gè)）使用簡單線性回歸方法組合這93個(gè)預(yù)測結(jié)果，最終的組合預(yù)測評分在ProbeSet上的RMSE為0.8717

在QuizSet上的RMSE為0.8747這93個(gè)模型名稱具體見博士論文P84-85吳金龍@SMS.(2010-05-28)33NetflixPrize中的協(xié)同過濾算法目前三十三頁\總數(shù)五十三頁\編于十五點(diǎn)PartIII：三維協(xié)同過濾——立方填補(bǔ)立方填補(bǔ)的實(shí)際應(yīng)用立方填補(bǔ)模型鄰居（kNN）模型貝葉斯聚類（BayesianClustering）模型立方聚類（CubeClustering）模型立方分解（CubeFactorization）模型實(shí)驗(yàn)結(jié)果吳金龍@SMS.(2010-05-28)34NetflixPrize中的協(xié)同過濾算法目前三十四頁\總數(shù)五十三頁\編于十五點(diǎn)三維協(xié)同過濾：立方填補(bǔ)PartIII：立方填補(bǔ)從數(shù)學(xué)上來講，二維的協(xié)同過濾問題是矩陣填補(bǔ)問題把矩陣填補(bǔ)擴(kuò)展至三維的立方填補(bǔ)（CubeCompletion）現(xiàn)實(shí)中存在立方填補(bǔ)的應(yīng)用嗎存在！吳金龍@SMS.(2010-05-28)35NetflixPrize中的協(xié)同過濾算法目前三十五頁\總數(shù)五十三頁\編于十五點(diǎn)實(shí)際應(yīng)用1——個(gè)性化網(wǎng)頁搜索PartIII：立方填補(bǔ)——實(shí)際應(yīng)用關(guān)鍵詞網(wǎng)頁用戶吳金龍@SMS.(2010-05-28)36NetflixPrize中的協(xié)同過濾算法目前三十六頁\總數(shù)五十三頁\編于十五點(diǎn)實(shí)際應(yīng)用2——個(gè)性化廣告投放PartIII：立方填補(bǔ)——實(shí)際應(yīng)用用戶產(chǎn)品廣告吳金龍@SMS.(2010-05-28)37NetflixPrize中的協(xié)同過濾算法目前三十七頁\總數(shù)五十三頁\編于十五點(diǎn)術(shù)語和記號PartIII：立方填補(bǔ)記三個(gè)維度分別為X、Y和Z統(tǒng)稱三個(gè)維度上的事物為對象記三個(gè)維度上的對象數(shù)量分別記為I、J

和K只考慮評分取二態(tài)值，即0或1吳金龍@SMS.(2010-05-28)38NetflixPrize中的協(xié)同過濾算法目前三十八頁\總數(shù)五十三頁\編于十五點(diǎn)鄰居（kNN）模型PartIII：立方填補(bǔ)——KNN難以應(yīng)用：已知評分過于稀疏（≤2X10-4）無法獲得可靠的相似度吳金龍@SMS.(2010-05-28)39NetflixPrize中的協(xié)同過濾算法目前三十九頁\總數(shù)五十三頁\編于十五點(diǎn)貝葉斯聚類（BayesianClustering）模型PartIII：立方填補(bǔ)——BC貝葉斯聚類（BC）模型是一種圖模型，它假設(shè)每個(gè)方向上的對象都可以被聚類吳金龍@SMS.(2010-05-28)40NetflixPrize中的協(xié)同過濾算法目前四十頁\總數(shù)五十三頁\編于十五點(diǎn)貝葉斯聚類（BC）的模型假設(shè)PartIII：立方填補(bǔ)——BC假設(shè)每個(gè)方向上的對象分別來源于不同的類別而評分只依賴于相應(yīng)對象所屬的類別具體模型訓(xùn)練方法見博士論文P90-92吳金龍@SMS.(2010-05-28)41NetflixPrize中的協(xié)同過濾算法目前四十一頁\總數(shù)五十三頁\編于十五點(diǎn)立方聚類（CubeClustering）模型PartIII：立方填補(bǔ)——CC立方聚類（CC）模型使用聯(lián)合聚類（Co-clustering,I.Dhillonetal.,SIGKDD,2003）的思想，同時(shí)聚類不同維度上的對象它的目標(biāo)函數(shù)為其中表示X

方向上的第i

個(gè)對象所屬的類別通過迭代更新對象的類別標(biāo)識及其喜好參數(shù)β

最小化此目標(biāo)函數(shù)具體更新方法見博士論文P93-95吳金龍@SMS.(2010-05-28)42NetflixPrize中的協(xié)同過濾算法目前四十二頁\總數(shù)五十三頁\編于十五點(diǎn)立方分解（CubeFactorization）模型PartIII：立方填補(bǔ)——CFLathauweretal.

(SIAMJ.MatrixAnal.Appl.,2000)把二維的奇異值分解方法推廣至高維一個(gè)三階張量R

，它的第(i,j,k)

個(gè)元素可以表達(dá)為其中X、Y

和Z

為酉矩陣，而C

為滿足全正交條件的三階張量吳金龍@SMS.(2010-05-28)43NetflixPrize中的協(xié)同過濾算法目前四十三頁\總數(shù)五十三頁\編于十五點(diǎn)立方分解（CubeFactorization）模型PartIII：立方填補(bǔ)——CF把二維情形下的矩陣分解（MF）模型推廣至三維情形，得到立方分解（CubeFactorization）模型立方分解模型的目標(biāo)函數(shù)為：和二維情形類似，可以使用梯度下降法最小化此目標(biāo)函數(shù)具體算法見博士論文P96-97吳金龍@SMS.(2010-05-28)44NetflixPrize中的協(xié)同過濾算法目前四十四頁\總數(shù)五十三頁\編于十五點(diǎn)貝葉斯聚類&立方聚類&立方分解PartIII：立方填補(bǔ)——實(shí)驗(yàn)結(jié)果驗(yàn)證三個(gè)模型對數(shù)據(jù)稀疏度的敏感性實(shí)驗(yàn)數(shù)據(jù)根據(jù)模型的假設(shè)抽取得到具體抽取步驟見論文P99與P102抽取數(shù)據(jù)時(shí)所使用的參數(shù)值見下表參數(shù)含義參數(shù)取值X方向上的對象數(shù)I5,000Y方向上的對象數(shù)J5,000Z方向上的對象數(shù)K1,000訓(xùn)練數(shù)據(jù)集所占的比例見實(shí)驗(yàn)結(jié)果圖測試集與訓(xùn)練集的比例20%吳金龍@SMS.(2010-05-28)45NetflixPrize中的協(xié)同過濾算法目前四十五頁\總數(shù)五十三頁\編于十五點(diǎn)貝葉斯聚類的實(shí)驗(yàn)結(jié)果PartIII：立方填補(bǔ)——實(shí)驗(yàn)結(jié)果吳金龍@SMS.(2010-05-28)46NetflixPrize中的協(xié)同過濾算法目前四十六頁\總數(shù)五十三頁