NetflixPrize中的

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

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

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

（R.Salakhutdinovetal.,ICML,2007）一層隱藏單元（hiddenunits）H代表用戶特征一層可視化單元（visibleunits）R代表評分特點好的預測精度時間復雜度很高吳金龍@SMS.(2010-05-28)12NetflixPrize中的協同過濾算法現在是12頁\一共有53頁\編輯于星期一因子（Factor）模型PartII：CF模型——Factor因子模型假設（R.Bell&Y.Koren,ICDM,2007;A.Paterek,1st

Netflix-KDDWorkshop,2007;…）每個用戶和電影都可由少數若干個因子來刻畫當一個用戶和某部電影的因子向量相匹配時，此用戶會對該部電影給予高的評分原始因子模型（通常稱為矩陣分解模型）的表達式為其中和分別為用戶和電影的潛在因子矩陣上述表達式是奇異值分解的一種簡化形式吳金龍@SMS.(2010-05-28)13NetflixPrize中的協同過濾算法現在是13頁\一共有53頁\編輯于星期一因子（Factor）模型的特點PartII：CF模型——Factor因子模型vs.鄰居模型因子模型可以獲得更高的預測精度因子模型vs.受限玻爾茲曼機模型因子模型需要更少的訓練時間吳金龍@SMS.(2010-05-28)14NetflixPrize中的協同過濾算法現在是14頁\一共有53頁\編輯于星期一矩陣分解（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中的協同過濾算法現在是15頁\一共有53頁\編輯于星期一矩陣分解（MF）的模型假設PartII：CF模型——Factor——MF用戶和電影的因子向量各自滿足正態分布且相互獨立用戶u對電影m的評分隨機變量滿足均值為，方差為的正態分布以上的正態分布對于不同的

u或m是相互獨立的吳金龍@SMS.(2010-05-28)16NetflixPrize中的協同過濾算法現在是16頁\一共有53頁\編輯于星期一矩陣分解（MF）模型假設的不合理性PartII：CF模型——Factor——MFMF假設在給定因子向量時，用戶u對電影m的評分變量滿足正態分布此假設對于離散協同過濾（CF）問題并不合理例如，對于NetflixPrize問題，真實的評分只在{1,2,3,4,5}內使用多項分布表示評分（Marlin,NIPS,2003;master’sthesis,2004）但多項分布的各個取值之間是無序的，它可能是多峰的（multimodal）的我們建議使用二項分布表示評分（

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

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

D.Lin&L.Mackey,2007）使用下面的步驟迭代更新中心矩陣C和概率矩陣Z更新每個類的中心向量（k=1,...,K）：更新每個用戶屬于各類的概率值（u=1,...,U;k=1,...,K）：在獲得了模型參數值后，使用下式獲得預測評分吳金龍@SMS.(2010-05-28)25NetflixPrize中的協同過濾算法現在是25頁\一共有53頁\編輯于星期一修正模糊聚類（ModifiedFCM）模型PartII：CF模型——Factor——MFCM如何改進FCM既然最終使用

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

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

也即分片線性回歸把X中的評分按照某種規則進行分片，然后在每片中使用簡單線性回歸通常使用評分支持度進行分片神經網絡其輸出層只有一個神經單元其他預測模型吳金龍@SMS.(2010-05-28)32NetflixPrize中的協同過濾算法現在是32頁\一共有53頁\編輯于星期一實驗結果PartII：CF模型——模型組合方法我們選出93個模型預測結果，這些結果來源于鄰居模型（12個）受限玻爾茲曼機模型（15個）因子模型（41個）聚類模型（7個）幾個模型的（序貫）組合結果（18個）使用簡單線性回歸方法組合這93個預測結果，最終的組合預測評分在ProbeSet上的RMSE為0.8717

在QuizSet上的RMSE為0.8747這93個模型名稱具體見博士論文P84-85吳金龍@SMS.(2010-05-28)33NetflixPrize中的協同過濾算法現在是33頁\一共有53頁\編輯于星期一PartIII：三維協同過濾——立方填補立方填補的實際應用立方填補模型鄰居（kNN）模型貝葉斯聚類（BayesianClustering）模型立方聚類（CubeClustering）模型立方分解（CubeFactorization）模型實驗結果吳金龍@SMS.(2010-05-28)34NetflixPrize中的協同過濾算法現在是34頁\一共有53頁\編輯于星期一三維協同過濾：立方填補PartIII：立方填補從數學上來講，二維的協同過濾問題是矩陣填補問題把矩陣填補擴展至三維的立方填補（CubeCompletion）現實中存在立方填補的應用嗎存在！吳金龍@SMS.(2010-05-28)35NetflixPrize中的協同過濾算法現在是35頁\一共有53頁\編輯于星期一實際應用1——個性化網頁搜索PartIII：立方填補——實際應用關鍵詞網頁用戶吳金龍@SMS.(2010-05-28)36NetflixPrize中的協同過濾算法現在是36頁\一共有53頁\編輯于星期一實際應用2——個性化廣告投放PartIII：立方填補——實際應用用戶產品廣告吳金龍@SMS.(2010-05-28)37NetflixPrize中的協同過濾算法現在是37頁\一共有53頁\編輯于星期一術語和記號PartIII：立方填補記三個維度分別為X、Y和Z統稱三個維度上的事物為對象記三個維度上的對象數量分別記為I、J

和K只考慮評分取二態值，即0或1吳金龍@SMS.(2010-05-28)38NetflixPrize中的協同過濾算法現在是38頁\一共有53頁\編輯于星期一鄰居（kNN）模型PartIII：立方填補——KNN難以應用：已知評分過于稀疏（≤2X10-4）無法獲得可靠的相似度吳金龍@SMS.(2010-05-28)39NetflixPrize中的協同過濾算法現在是39頁\一共有53頁\編輯于星期一貝葉斯聚類（BayesianClustering）模型PartIII：立方填補——BC貝葉斯聚類（BC）模型是一種圖模型，它假設每個方向上的對象都可以被聚類吳金龍@SMS.(2010-05-28)40NetflixPrize中的協同過濾算法現在是40頁\一共有53頁\編輯于星期一貝葉斯聚類（BC）的模型假設PartIII：立方填補——BC假設每個方向上的對象分別來源于不同的類別而評分只依賴于相應對象所屬的類別具體模型訓練方法見博士論文P90-92吳金龍@SMS.(2010-05-28)41NetflixPrize中的協同過濾算法現在是41頁\一共有53頁\編輯于星期一立方聚類（CubeClustering）模型PartIII：立方填補——CC立方聚類（CC）模型使用聯合聚類（Co-clustering,I.Dhillonetal.,SIGKDD,2003）的思想，同時聚類不同維度上的對象它的目標函數為其中表示X

方向上的第i

個對象所屬的類別通過迭代更新對象的類別標識及其喜好參數β

最小化此目標函數具體更新方法見博士論文P93-95吳金龍@SMS.(2010-05-28)42NetflixPrize中的協同過濾算法現在是42頁\一共有53頁\編輯于星期一立方分解（CubeFactorization）模型PartIII：立方填補——CFLathauweretal.

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

，它的第(i,j,k)

個元素可以表達為其中X、Y

和Z

為酉矩陣，而C

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