利用矩陣分解算法建模數據稀疏環(huán)境下用戶協同行為

1、分類號：TP393單位代碼：10346密 級：_Jc 學號：2012110614構州岬此亭II 11411I碩士學位論文中文論文題目：利用矩陣分解算法建模數據稀疏環(huán) 境下用戶協同行為英文論文題 目:Utilizing Matrix Factorization Methods to Model Users Sparse Collaborative Behaviors申請人姓名： 余露指導教師：張子柯教授.合作導師：專業(yè)名稱：計算機應用技術,研究方向：金融軟件與金融服務所在學院：杭州國際服務工程學院論文提交日期 2015年5月利用矩陣分解算法建模數據稀疏環(huán)境下用戶協同行為論文作者簽名:指導教師簽名

2、:論文評閱人1:評閱人2： 評閱人3： 評閱人4： 評閱人5： 答辯委員會主席：委員1： 委員2： 委員3： 委員4： 委員5： 答辯日期：杭州師范大學研究生學位論文獨創(chuàng)性聲明本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作及取得竺 研究成果。除了文中特別加以標注和致謝的地方外，論文中不包含其他人己經發(fā) 表或撰寫過的研究成果，也不包含為獲得杭州師范大學或其他教育機構關 學位或證書而使用過的材料c與我一同丁作的同志對本研究所做的任何貢獻均己 在論文中作了明確的說明并表示謝意。學位論文作者簽名:簽字日期：年。亍月7 H學位論文版權使用授權書本學位論文作者完全了解杭州師范大學有權保留并向國家

3、有關部門 或機構送交本論文的復印件和磁盤，允許論文被查閱和借閱。本人授權 杭州師 芨大更可以將學位論文的全部或部分內容編入有關數據庫進行檢索和傳播，可 以采用影印、縮印或掃描等復制手段保存、匯編學位論文。（保密的學位論文在解密后適用本授權書）學位論文作者簽名:導師簽名:簽字Fi期：年g月簽字fi期vT年廠月7/致謝三年的研究生時光給予我繼續(xù)追逐新夢想的機會。在此之際，感謝導師張子 柯教授、張翼成教授對我的知遇之恩，以及科研道路上毫無保留的支持與鼓勵。 沒有他們給予我廣闊的自由空間，我很難想象現在的自己是否還能走在逐夢路 o感謝劉闖老師無微不至的關懷與鼓舞，他就是我們實驗室的全民大哥，無私 地與

4、我們分享，交流切身之所學，所感，和他相處的日子十分開心，充實。感謝 遠在美國的張初旭博士生，我們都著迷于數據挖掘的魔力，期待在這片廣闊的天 空中迎接不斷涌現的挑戰(zhàn)，制造更多有意思，切實可用的智能工具。感謝我的師 弟周鴿，他的睿智與勤懇讓我們的合作十分愉快，我們經常在一塊進行激烈的頭 腦風暴，探討來自數據挖掘領域的不同挑戰(zhàn)，以及可能的解決思路。在此期間， 他成長十分迅速，我相信在不久的未來，他會成為一名閃亮的數據科學家。感謝 孫月鳳同學提供全面周到的行政支持，這對整個實驗室的正常運作意義重大，也 讓我們更加專注學術研究。感謝阿里巴巴復雜科學研究中心的詹秀秀，孫嘩，孫 月鳳，尤志強，任曉龍，葉章輝

5、，管遠盼，朱燕燕，訪問學生謝瑤，訪問博士鄧 小方，劉金虎，與他們共同度過的愉悅而又輕松的時光宛如一陣清風，吹走百般 纏繞的煩惱，我們就像一個大家庭一樣，充滿溫馨和快樂。最后也是最多的，感謝養(yǎng)育我的父母對我無私的愛，遠在美國的姐姐以及姐 夫給予我的莫大支持與關愛，未婚妻徐錦葉對我的無限關愛與包容，他們就是照 亮我人生的太陽。摘要隨著近幾年來社交媒體的流行，信息的產生、傳播、分享變得越發(fā)容易。人 們只需要通過發(fā)布微博，更新自己的社交狀態(tài)就能同來自世界各地的人們通信， 交朋友，甚至進行商業(yè)貿易。電子商務的盛行，網絡購物正逐漸地成為人們生活 中不可或缺的一部分，也在顛覆著傳統的產業(yè)結構。然而，人們在受

6、益于信息爆 炸所帶來的便利的同時，也在面臨信息過載所帶來的困擾：該如何從龐大的信息 池中獲取有價值的資源呢？推薦系統的出現正是為了解決這個問題，也在逐漸成 為很多商業(yè)應用的重要組件，自動地通過分析用戶偏好，為人們推送最為喜歡， 符合個人口味的信息。本文主要探討推薦系統研發(fā)過程中所面臨的數據稀疏性問題，并從評分預測 和排序預測的角度探討了如何設計緩解該問題的個性化算法。本文的主要貢獻如下：探討了如何利用矩陣分解算法刻畫用戶評分決策過程，從反饋數據中進一 步捕捉用戶與物品以外信息的交互作用，緩解顯性評分反饋不足所帶來的預測缺 陷，并設計了相應的實驗。研究如何利用排序學習解決比傳統協同過濾數據稀疏性

7、更為嚴重的，需要 處理三元張量關系的協同檢索任務。在兩份真實數據集的結果顯示，我們提出的 算法能夠有效提升預測準確度，尤其是對那些信息含量很少的物品。為Pairwise排序學習在推薦算法的應用提出了一種基于物品的采樣策略， 并進一步定義了一種自適應采樣策略,提高了采樣效果的同時，也改善了 Pairwise 算法在稀疏數據上的預測準確率。關鍵詞：推薦系統，矩陣分解，排序學習，稀疏性AbstractThe recent unprecedented proliferation of social media makes the information extremely easy to be pro

8、duced, transformed and shared. People all around the world are connected closely because of the daily basis millions of micro-blog posts, tweets and status update of the social network. With the popularity of E-commerce, the online consumption is becoming an essential part of peoples daily life, and

9、 is also transforming the structure of traditional industries. However, people are suffering from a serious challenge from the explosive growth of information: how to acquire quality resources from the numerous information pool? The emergence of recommender systems is exactly to deal with such issue

10、, and progressively becomes a fundamental function for a variety of applications via automatically delivering personalized information to fit users after analyzing users personal preferences.This work mainly explores the challenging sparsity problem along with the design of effective recommender sys

11、tems, and discusses how to design corresponding algorithms to alleviate such problem for rating prediction and item ranking perspectives.The main contributions of this work includes:Exploring the possibility of modeling the interactions between users and each event associated with their final decisi

12、ons, incorporating those interactions into matrix factorization models to alleviate the sparsity problem caused by the lack of rating infbnuation. Experiments are conducted to demonstrate efficiency of our proposed method.Studying how to utilize learning to rank to deal with a seriously sparse scena

13、rio where ternary relationship is considered for collaborative retrieval task, in contrast with traditional collaborative filtering. Experimental results in two real-world datasets show that our proposed approach could effectively improve the prediction precision, especially fbr those items with spa

14、rse information.Designing an item-based pairwise sampling construction fbr the application of Pairwise learning to rank in recommender systems, in addition, an adaptive sampling strategy is defined to improve the sampling performance, meanwhile enhance the prediction accuracy in sparse datasets.Key

15、Words： recommender systems, matrix factorization, learning to rank, sparsity目次 TOC o 1-5 h z HYPERLINK l bookmark7 o Current Document 致謝I HYPERLINK l bookmark10 o Current Document 摘要II HYPERLINK l bookmark16 o Current Document Abstract Ill目次V HYPERLINK l bookmark60 o Current Document 1 緒論1 HYPERLINK

16、 l bookmark63 o Current Document 1.1推薦系統研究背景及意義1 HYPERLINK l bookmark66 o Current Document 1.2稀疏環(huán)境下推薦系統研究綜述 3 HYPERLINK l bookmark69 o Current Document 1.3本文研究內容和創(chuàng)新點5 HYPERLINK l bookmark74 o Current Document 1.4數據集介紹6Movielens 電影評分數據集 6Last.fm音樂收聽數據集6Yelp商鋪評分數據集7Epinions 社交網絡數據集 7 HYPERLINK l bookm

17、ark81 o Current Document 1.5論文結構7 HYPERLINK l bookmark84 o Current Document 2用戶評分決策情景的多元線性矩陣分解算法 8 HYPERLINK l bookmark87 o Current Document 概述8 HYPERLINK l bookmark93 o Current Document 2.2用戶評分決策行為分析9 HYPERLINK l bookmark96 o Current Document 2.3多元線性互作用矩陣分解推薦模型10矩陣分解算法預覽10Multi-linear Interactive M

18、atrix Factorization 13 HYPERLINK l bookmark99 o Current Document 實驗結果14評價指標14對比方法簡介15實驗參數設置16實驗結果分析17 HYPERLINK l bookmark102 o Current Document 本章小結18 HYPERLINK l bookmark105 o Current Document 3協同檢索任務中的Top-K物品推薦19 HYPERLINK l bookmark108 o Current Document 概述19 HYPERLINK l bookmark111 o Current Do

19、cument 3.2三元張量關系20 HYPERLINK l bookmark114 o Current Document 3.3基于物品淺層協同檢索張量模型21 HYPERLINK l bookmark117 o Current Document 實驗結果25實驗數據及預處理25評價方式 26實驗設置及對比方法簡介 26實驗結果分析27 HYPERLINK l bookmark125 o Current Document 本章小結29 HYPERLINK l bookmark128 o Current Document 基于物品的貝葉斯Pairwise排序推薦 31 HYPERLINK l

20、bookmark131 o Current Document 概述31 HYPERLINK l bookmark134 o Current Document 4.2用戶-物品二部圖Pairwise關系分析32 HYPERLINK l bookmark139 o Current Document 4.3基于物品貝葉斯排序推薦模型33自適應采樣策略35 HYPERLINK l bookmark154 o Current Document 實驗結果36實驗數據36評價指標36對比方法簡介 37實驗結果分析 38 HYPERLINK l bookmark163 o Current Document 本

21、章小結39 HYPERLINK l bookmark166 o Current Document 總結和展望41 HYPERLINK l bookmark169 o Current Document 總結41 HYPERLINK l bookmark172 o Current Document 展望41 HYPERLINK l bookmark179 o Current Document 參考文獻421緒論1.1推薦系統研究背景及意義在面對近幾年來社交網絡，移動設備的爆炸式增長，龐大的互聯網信息容 量已經遠遠超越個人的信息消化效率，造成了嚴重的信息過載。人們正在逐漸 地迷失在互聯網信息叢林里中

22、，需要花費大量的時間才能找到隱藏在某個角落 中，對自己來說有價值的信息。大數據正在深入到，并嚴重影響著人們現代生 活。為了能夠有效應對大數據環(huán)境下的信息過載問題，各種各樣的工具被發(fā)明 出來。其中，搜索引擎的出現從一定程度上幫助緩解了用戶查詢信息的效率, 但無法滿足用戶日益增長的個性化需求。因為，和推薦系統比起來，搜索引擎 對所有用戶只能夠產生相同的結果，它的目標在于根據查詢項(Query)產生最為 客觀，公正的文檔排序，而非提供個性化服務。尤其在移動應用的流行，人們 脫離了傳統PC計算機的約束，可以在任何時間，任何地點獲取信息，由此對符 合自己口味，高質量信息的需求也在不斷的增長。2014年公

23、布的互聯網發(fā)展狀 況統計報告顯示，中國手機網名相比于往年從3.88億增長到5億，增長了31.4%之 多，不僅如此許多和衣食住行息息相關的智能應用吸引了大量用戶將移動手機 作為信息獲取、休閑娛樂的主要方式。為了滿足用戶的個性化需求，推薦系統 已經成為各種各樣應用產品中必不可少的一個組件，通過自動的分析用戶對物 品的偏好，提供個人層面的個性化信息服務。比如亞馬遜的item-to-item協同 過濾推薦系統為其用戶提供圖書推薦33,訂單組合等服務，為亞馬遜增加了 三分之一的收入；世界最大的搜索引擎公司谷歌利用用戶點擊歷史數據構建新 聞推薦系統11,同時也將推薦技術應用到公司的其他服務產品中，如競價廣

24、 告，Google+；亞洲最大的搜索引擎公司百度利用推薦技術構建個性化的問答社 區(qū)(百度知道)34。隨著大數據概念的普及，各種在以前看來很陌生的數據挖掘算法已經被大 規(guī)模應用于不同商業(yè)產品中，推薦技術就是其中之一。從九幾年開始，推薦系 已經逐漸成為數據挖掘領域的十分熱門的研究方向。一般來說，推薦系統可以 理解成一種十分特別的知識系統，不同于其他系統的是，它會自動分析用戶和 物品之間的關聯性，然后通過不同的推薦策略為用戶提供適合其口味的商品。 傳統的推薦算法主要分為兩類，基于內容2和協同過濾推薦算法18o基于內 容推薦算法會通過抽取物品和用戶的內容信息如人口統計屬性，產品描述等, 來構建他們的特

25、征，然后通過比較兩者特征之間的差異程度來衡量用戶和物品 之間的關系。然后，收集物品和用戶的內容信息代價很高，用戶又不愿意主動 的曝光自己的資料，基于內容的策略并沒有成為最流行的推薦算法。協同過濾 算法通過虛擬的社區(qū)結構來產生推薦結果19o虛擬社區(qū)的定義基于一種很普 通的假設，一群在過去口味相近的人，他們的口味在未來依然會很相似。此外, 協同過濾算法不受領域知識的限制，提供了很好的方式用于發(fā)現一些基于內容 推薦算法無法發(fā)現的潛在規(guī)律。根據前人的總結，協同過濾主要分為基于鄰居(Neighborhood Based Model, NBM) 51, 33和淺層因子模型(Latent Factor Mo

26、del, LFM) 20, 30o 前者顧名 思義更加突出鄰居和目標用戶之間的關系。這里的”鄰居”并不僅僅限于用戶之 間可以構成鄰居關系，也用于指代物品之間的鄰居關系。值得一提的是，基于 用戶和基于物品的協同過濾算法33是兩種典型的NBM推薦算法。NBM通過 目標用戶，或者物品的鄰居來預測用戶和未評分物品之間的關系。相比而言, LFM算法則是將系統中的所有實體重新表述為低維度的特征向量，直接通過 計算兩個實體之間的特征向量內積衡量他們之間的關系緊密程度。矩陣分解算 法(Matrix Factorization, MF)為最為流行的LFM算法。最早利用MF來構建協 同過濾推薦系統實用例子由Sar

27、war et al. 50提出，他們演示了如何利用奇異值 分解算法(Singular Value Decomposition, SVD)算法來做數據的降維處理。近年 來，Hofmann 20利用Latent Semantic Model嘗試從語義層探索實體之間的關 系。在2006年Netflix Prize早期的時候5, Brandyn Webb 60詳細闡述了他的 隊伍是如何利用正則化的矩陣分解算法獲得第三名的方案。從此以后，許多工 作30, 27, 29, 56, 57都開始基于矩陣分解算法設計不同的推薦策略，證實了矩 陣分解類算法在構建Netflix Prize解決方案的重要地位。由于矩

28、陣分解的理論簡 潔，易拓展性，高準確率的特征，激發(fā)了許多工作從不同的角度挖掘矩陣分解 的潛在應用30, 27, 29, 42, 58, 36, 37, 67。雖然，大數據記錄了豐富的用戶行為信息，媒體資料，但龐大的用戶群體 和商品之間的交互行為非常少，所以實際上所有的推薦系統待處理的數據都十 分稀疏。如淘寶上有將近10億量級的商品，平均每個用戶能夠瀏覽的商品數 量會有1000件嗎？如此龐大的商品集，用戶的精力十分有限，所能夠觸及的 商品或者信息量極少。信息如此稀疏的環(huán)境也為各種推薦服務的構建帶來了 嚴重的挑戰(zhàn)。數據是不同數據挖掘算法工作的資料，面對這種情況，不同算法 的效果差異非常大，無法從根

29、本上完全克服數據稀疏性帶來的影響。但是，我 們可以根據不同的場景創(chuàng)造對應的策略緩解這個問題。本文在此背景下，分析 了目前用于克服數據稀疏性問題的解決策略，以及相關理論特點。并針對數據 稀疏性問題，基于矩陣分解算法提出了多元線性互作用評分決策模型，利用額 外的信息幫助刻畫用戶的評分決策過程；為Top-K協同檢索任務設計簡單，卻 十分有效的協同檢索算法；最后，提議更為細致地分析用戶-物品之間的關系, 為Pairwise排序學習算法提供了更為高效的采樣思路，以提高Top-K物品推薦算 法在稀疏環(huán)境中的表現。1.2稀疏環(huán)境下推薦系統研究綜述從目前的環(huán)境來看，大數據本身就包含有很多缺失信息，數據稀疏性問

30、題 是目前無法得到根本解決的問題。但為了在稀疏的環(huán)境下產生更好的推薦效果, 目前的研究主要分為開發(fā)更高效的算法和補充額外信息以提高算法預測效果。隨著近幾年來推薦技術的飛速發(fā)展，應對不同商務環(huán)境的推薦算法逐漸地 被開發(fā)出來。最早的推薦系統可以追溯到1992年由Goldberg et al. 17應用了基 于內容和協同過濾器構建的個性化郵件推薦系統。當時的推薦系統還處于十分 初級的階段，其種類和可拓展性遠不如今日，以及當時還無法面臨如此龐大的 數據資源所帶來的挑戰(zhàn)。為了能夠克服個人數據的稀疏性，協同過濾利用口味 相近的其他用戶（被稱作鄰居）來彌補單個用戶行為的缺失47, 7, 18,而基于內 容的

31、推薦系統2則通過用戶和物品的內容信息刻畫他們的內在特征。傳統的協 同過濾將用戶和物品的關系看成是一個二維的用戶-物品矩陣，基于這個關系矩 陣，很多研究人員從不同的角度嘗試構建更高效的協同過濾算法。如35所述, 為了改進協同過濾算法能夠應對不同的稀疏問題，很多種用于計算用戶之間的 相似程度的方法被提了出來，其中包括大家十分熟悉的歐幾里德距離，Jaccard 相似度，Cosine相關性，Pearson相關系數，以及前面的各種指標的改進版本。Breese et al. 8后來提出物品的評分并非等權重，需要根據物品的流行程度改變 物品的權重。最初的協同過濾都是基于用戶的角度構建，直到2001年Sarw

32、ar et al. 51提出基于物品的協同過濾算法，利用物品之間的相似性而非用戶之間的 來構建推薦系統。從A在2003年發(fā)表的關于基于物品的協同過濾的 文章來看33,這樣做能夠提升算法預測的準確率，計算量也會大大減少。雖然 如此，實際應用場對推薦系統的期望遠不止利這些，更希望能夠探索能夠準確， 高效，實時預測用戶喜好的產品，除此之外還期待推薦系統能夠帶給長尾中用 戶潛在感興趣的商品。如果將用戶對物品的偏好理解成概率分布的話，那么更 高效的推薦算法則是能夠從已觀測數據中發(fā)現潛在的數據模型，并能夠從小樣 本從很好的學習到整體樣本的概率分布。從概率分布的角度來看，要提高推薦 算法的預測準確性，就需要

33、探索具有更好擬合能力的方法。隨著2006年Netflix 舉辦的電影評分預測大賽的成功舉辦，基于模型的算法的高效擬合能力被很 多人所證實，其中包括矩陣分解(matrix factorization) 60, 53, 30, 42,概率模 型(probabilistic models) 11, 6, 49,各種機器學習算法(回歸模型，神經網絡， 深度學習4,集成模型14)等等。隨著移動設備的普及，與用戶相關的上下文場景信息如地理位置，時間， 天氣，環(huán)境信息等已經十分容易獲得，面向情景感知(Context-aware)的數據挖 掘研究也備受關注。具體地說，情景數據主要包含了，地理位置，時間，文本,

34、 圖片，標簽，社交媒體等信息。面對這些數據，研究人員開始了面向移動手設 備端的商務推薦系統16,利用出租車和用戶的GPS軌跡數據設計打車路徑推薦 系統65, 15, 66,融合多元環(huán)境信息1, 64, 54, 26,面向用戶社會化標簽推薦 系統研究43,面向社交網絡在用戶偏好分析方面的研究23, 24, 68, 39, 9, 67, 以及利用文本和圖像之間的語義構建推薦系統應用25, 59, 13o由于矩陣分解 的優(yōu)良特性，基于矩陣分解的情景感知研究同樣吸引了不少研究人員的目光。 Koren分析用戶與物品之間的鄰域關系27,以及用戶偏好的時間動態(tài)特性29, 并融入這些信息以提高推薦效果。Bal

35、trunas et al. 3認為物品與上下文環(huán)境信 息之間存在某種作用關系，并利用這種信息構建情景感知的矩陣分解算法。Ma et al. 39假設在社交網絡中有連邊關系的兩個用戶之間的口味十分相近，并將 這種信息作為用戶特征向量之間的約束條件融合到矩陣分解算法模型中，提高 了評分預測效果。隨著社交網絡的興起，Ma et al. 38提出融合用戶之間的信 任關系，降低模型在預測用戶評分時對冗余項做的無用功，達到過濾噪聲數據 的作用，同時也能夠利用用戶之間的社交關系進行偏好的傳播。Yang et al. 63 引入基于偏置項的矩陣分解算法，探討了利用信任社交關系更好的學習用戶與 物品的特征向量。

36、Lianeta/.32發(fā)現人們的地理活動空間存在聚集現象，在基 于地理位置的社交網絡中利用該現象提出了十分有效的地理位置興趣點的推薦 系統。綜合以上信息來看，為了克服數據稀疏性所帶來的挑戰(zhàn)，推薦系統算法還 在不斷的迭代更新，新技術如深度學習也逐漸在不同推薦應用中發(fā)揮重要作用。 豐富的數據類型為研究人員深入挖掘用戶偏好信息提供了重要幫助，驅動推薦 系統逐漸走入不僅能夠準確預測用戶的興趣點，同時能夠感知用戶所處的情景, 提供更為個性化的推薦服務。在這樣的背景下，由于矩陣分解算法具有很強的 可拓展性，對于情景數據的融合能力被許多研究所證實，這使得矩陣分解模型 成為利用場景數據克服用戶行為數據稀疏性問

37、題的重要武器。1.3本文研究內容和創(chuàng)新點本文旨在分析用戶行為數據稀疏性為推薦算法研究所帶來的挑戰(zhàn)，通過矩 陣分解算法設計更為高效的推薦算法，更加精準預測用戶的偏好分布。具體的 工作包括以下幾個方面：用戶評分決策情景的多元線性矩陣分解算法用戶在對物品進行評價的時候往往會考慮多種信息，不同的信息元素在用 戶的決策中占有不同比重。本文以矩陣分解算法為基本模型，電影評分推薦為 例子，通過分析可能會影響用戶決策的因素，通過刻畫用戶與決策因素之間的 相互作用，綜合用戶對不同因素的權重信息產生最終的推薦決策。實驗結果顯 示，在引入評分決策機制后，算法的評分預測效果得到了提高。該機制是一種 通用思想，可以融入

38、到其他的矩陣分解推薦算法中。協同檢索任務中的Top-K物品推薦目前，推薦和檢索的交叉應用越來越多，在數據挖掘領域該問題被稱作為 協同檢索任務。針對該任務的算法設計需要面臨更為嚴峻的數據稀疏性問題, 因為我們需要考慮信息更為豐富的query, user, item)三元關系，而非傳統推薦 任務中的(user, item)關系。本文從網絡的角度深入分析(query, user, item)之間 的關系，發(fā)現基于用戶和物品的協同網絡能夠彌補用戶行為，以及物品內容信 息的缺失。Pairwise排序學習的引入有效地利用矩陣分解算法有效提升協同檢 索算法的效果，尤其對信息含量較少的物品。3.基于物品的貝葉

39、斯Pairwise排序推薦近幾年，排序學習更為符合實際應用場景，正逐漸成為推薦算法研究熱點。 本文通過分析以往的Pairwise排序學習在推薦系統上的應用特點，通過深入分析 用戶-物品之間的關系，發(fā)現基于物品的樣本構建策略能夠進一步刻畫用戶-物品 之間的Pairwise關系，從而有效提升算法在稀疏數據集上的排序效果。在四份 真實的數據集上的效果顯示，我們提出的算法能夠有效提升算法效果。1.4數據集介紹Movielens電影評分數據集包括兩份不同大小的數據集，分別為MovielenslOOK和MovielenslM,由明 尼蘇達大學的數據挖掘研究項目組GoupLens收集，組織清理，并公開用于學

40、 術研究。MovielenslOOK記錄了943位真實用戶對1648部電影產生的10萬條評分 記錄，評分范圍為1-5分。每個用戶平均對至少20部電影進行過評分，數據的 稠密度為6.3%,這意味著至少93%以上的信息是不可見的。MovielenslM記錄 了 6040位M用戶對3900部電影所產生的100萬條評分記錄，數據稠 密度為4.25%O除此之外，兩份Movielens數據集還包含有電影內容信息，如電影 題目，發(fā)布年份，電影基因等。Last.fm音樂收聽數據集Last.fm是目前非常流行的音樂社交網站。本文所使用的數據集由HetRec 2011會議發(fā)布。數據包含由1892位用戶構建成的社交

41、網絡，該網絡擁有12717條 社交關系;所有用戶對17632位藝術家的音樂產生的92834條收聽記錄；用戶對藝 術家所打的 11946個音樂標簽，如 “pop” , rock” , “alternative , “electronic” 等。Yelp商鋪評分數據集Yelp是美國著名商戶點評網站，囊括各地餐館、購物中心、酒店、旅游等 領域的商戶，用戶可以在Yelp網站中給商戶打分，提交評論，交流購物體驗 等。本文所采用的數據集為Yelp官方公布的學術數據，該數據包含70746位用戶 對Phoenix和AZ地區(qū)15470個商鋪所產生的335022條評論記錄，社交網絡，以及 商鋪的類目屬性信息。Ep

42、inions社交網絡數據集Epinions是一個非常流行的基于信任機制的社交網絡，用戶可以免費 注冊，對物品進行評分，或者撰寫評論信息。本文所使用的Epinions數據來 自 HYPERLINK /wiki/Epinions,%e5%8c%85%e5%90%ab%e6%9c%8949289%e4%bd%8d%e7%94%a8%e6%88%b7%e5%af%b9139738%e4%b8%aa%e7%89%a9%e5%93%81%e6%89%80%e4%ba%a7%e7%94%9f /wiki/Epinions,包含有49289位用戶對139738個物品所產生 的664823條評分記錄。1.5論文

43、結構本文的正文內容由一下五章構成：第一章首先介紹推薦系統研究現狀，然后按照不同類別介紹了主要的推薦 算法以及相關工作，并著重闡述了構建能夠應對數據稀疏環(huán)境下的高效推 薦算法的重要性，最后介紹了實驗中所采用的數據集信息。第二章討論了如何利用矩陣分解算法捕捉用戶的決策過程，并給出了相關 的實驗結果及分析。第三章主要討論了協同檢索情景中的Top-K物品推薦問題，并設計相關的 實驗及結果分析。第四章介紹了如何利用Pairwise排序學習解決Top-K推薦問題，提出從物 品角度構建貝葉斯Pairwise關系，設計相關的實驗，并對結果進入了深入 分析。第五章是論文的結束和展望，總結了目前的工作，并提出了下

44、一步的研究方向和任務。2用戶評分決策情景的多元線性矩陣分解算法2.1概述在線用戶的反饋是構建個性化推薦系統的必要因素，典型的反饋方式是讓 用戶給物品評分，評分行為也被稱為顯性反饋，因為這樣做能夠十分明確的獲 取用戶對不同信息的興趣。不同的網站會采取不同的方式收集用戶的意見，在 線DVD租賃公司Netflix利用5顆星打分系統，有些網站則只讓用戶選擇喜歡或者 不喜歡。由于用戶對一個商品進行評分的成本十分高，系統中的評分數據是十 分稀少的。我們從幾個真實的數據集上可以看到，在線應用所能夠獲取的顯性 反饋十分的稀疏，幾乎有90%以上的信息都是未知。而評分預測問題的主要任 務就是在給定數量十分稀少的評

45、分信息的情況下，預測用戶對其他未評分物品 的偏好情況。目前，很多工作都單純的關注用戶-物品評分矩陣，通過構建推薦算法來擬 合觀測到的用戶偏好分布。但這樣做往往忽略了用戶評分決策背后的故事。拿 用戶對自己看過的電影進行評分為例子，我們對一部電影的評價會根據許多不 同的因素綜合做決策，然后轉化成一個具體的分值。其中，不同的因素在評分 決策中所占有的比重是不一樣的，有些人可能更看重電影的導演，有些人則更 看重演員，或者電影的發(fā)布年份。如果能夠提出一種機制能夠刻畫用戶的評分 決策過程，通過該機制能夠引入更為豐富的信息，這在一定程度上可以緩解評 分數據稀疏性的問題。下面幾個章節(jié)，我們會介紹如何刻畫用戶的

46、決策行為， 并通過矩陣模型利用決策因素(Decision Factor)以提高預測效果。本章的主要內容如下：通過真實的評分數據分析用戶可能會影響用戶決策行為的因素。介紹評分預測問題中最常用的矩陣分解模型(也被稱為Latent Factor Model) o基于矩陣分解模型，提出多元線性矩陣算法(Multi-Linear Interactive Matrix Factorization,簡寫為MLIMF),以及優(yōu)化該推薦模型的方法。本章提出了我們提出的MLIMF算法，并在兩個真實的電影評分數據集上 驗證了算法的效果。實驗對比了最為經典的矩陣分解算法，以及傳統的基于用 戶，基于物品的協同過濾算法，

47、驗證了利用用戶的決策因素不僅可以提高評分的預測精度，同時能夠刻畫用戶與物品信息之間存在的多元關系。為其他需要 利用用戶與物品信息之間的作用關系的應用提供了可以利用的資源。Collected Datauser-itemInteraction strengthInteraction strength between user and other factors(a)(b)(c)圖2.1:該示意圖描繪了用戶做評分決策時考慮的因素。（a）描述了可能會影響 用戶評分的因素。（b）展示了經過轉換處理以后的數據形式。（c）幫助我們形象 化的理解用戶如何對不同決策因素賦予不同的權重。2.2用戶評分決策行為分析

48、在現實生活中，人們在決定購買一樣東西前往往會考慮不同的因素，對比 不同的產品之間的差異，然后綜合地做出選擇。而這些因素對于用戶來說的重 要影響力是不均等的。例如，一個星球大戰(zhàn)電影的超級粉絲可能會十分關 注由同一個導演所拍攝的經典科幻片THX1138，此時對該用戶來說“導演” 是誰對他來說可能更加說明一部電影的質量。圖2.1簡易的示意了用戶在做決策 的過程中可能會受到哪些因素的影響，以及如何將這些信息轉換城不同的權重 比例，直到做出最終的決策。然后，在真實的應用場景下，我們卻很難將這些 信息融入到機器學習算法中，因為缺少用戶愿意去將時間花費在點擊反饋上面。 盡管如此，在線服務供應商還是會十分仔細

49、的打磨自己的產品，盡可能多的捕 捉用戶的在線行為信息，以便更好的理解用戶的口味，與此同時提高自身產品 的競爭力。記錄在數據庫的用戶日志數據提供了十分豐富的信息來幫助我們理 解用戶行為。由此，我們的任務就轉換成了分析，獲取可能會影響用戶評分行 為的信息，并利用這些信息來更好的預測用戶對商品的偏好。以用戶在站點上的評分行為為例，我們來分析下，除了用戶對 物品的評分外，還有哪些信息能夠幫助我們獲取用戶偏好。我們在1.3.1章節(jié)中 提到過，MovieLens數據集中包含有用戶的評分決策，以及豐富的電影信息。顯 示的評分反饋明確的反應了用戶對一部電影的喜好程度，這從側面也體現了對 電影中如導演，發(fā)布年份

50、等信息的關注程度。基于該假設，我們定義了幾種可 能和用戶評分決策密切相關的因素，并分析了用戶與這些決策因素之間的關系。 圖2.2.a顯示了用戶的評分分布與電影的發(fā)布年限之間的關系，我們可以清晰的 發(fā)現用戶更加關注比較新的電影，而且對剛剛發(fā)布的沒多久的電影的評分會更 為苛刻，對已經發(fā)布有段時間的電影評分更加松弛一些。通過觀測數據我們發(fā) 現，一部電影可能即是喜劇，又是愛情劇，這說明一部電影的基因可以是多元 的。我們還分析了電影基因的多元化程度和用戶評分的關系。通過圖2.2.b我們 可以看到用戶比較喜歡基因明確的電影，對于定位不太明確的電影更不喜歡。 由此我們可以看到，通過提取并分析數據中蘊含的信息

51、是可以在一定程度上捕 捉到用戶的評分決策過程。在下一章節(jié)，我們會詳細的描述我們的解決方案。Release DateSize of Genre group(a)(b)圖2.2:該示意圖描繪了可能會影響用戶評分決策的因素。(a)電影的發(fā)布年 份(Release Date)。(b)電影基因多元性(Size of Genre group)o2.3多元線性互作用矩陣分解推薦模型2.3.1矩陣分解算法預覽在協同過濾領域，用戶對物品的偏好會表示成一個評分矩陣，其中和分 別表示用戶集U和物品集/的大小。矩陣R對應于位置的評分元素凡/表 示用戶對物品的顯示偏好，通常該值越大表示用戶對物品的偏好越強烈。不 同的系

52、統該分值的表示方式會有很大的差異，典型的有5分制，或者0,1制。 在實際應用中，R是一個十分稀疏的矩陣，我們只能觀測到很少一部分的數 據。推薦算法需要基于這些數據來猜測剩下的大量未知數值，矩陣分解(Matrix Factorization)算法是目前處理該問題的最好算法。在矩陣分解算法中，每一 個實體被映射成一個低維度的特征向量，兩個實體之間的相互作用通過他 們對應特征向量的內積來表示。拿評分預測問題為例，我們用/表示特征向 量的維度，Puf來表示用戶的特征矩陣，其中每一個行向量都對應一個用 戶的特征向量饑，Qixf表示物品的特征向量，其中每個行向量都對應一個 物品的特征向量如一般來說用戶特征

53、向量參數要遠小于用戶或者物品的個 數(/弟(|叫，|/|)。矩陣分解模型主要包含兩部分，分別是評分函數以及學 習框架。用戶對物品的評分函數可以通過以下公式來表示：rui = puq7(2.1)其中分心表示對用戶真實評分的估計值。一般來說，特征矩陣F和Q的未知 參數可以用十分高效的梯度下降法(Stochastic gradient decent,以下簡稱SGD), 通過優(yōu)化目標函數min J(P, Q) = ： W f 1(心)(站一，微)2 +打|如|情 + |%|=),(2.2)ueu iei其中| T|f表示Frobenius范數。l(iz,i)是一個指示函數,如果用戶對物品= 1,否則l

54、(u,z) = 0o公式2.2的第二項是正則項，起到防止過擬合的作 用，能夠提高學習得到的模型在新樣本上的預測效果。根據文獻56,人是正則 項的權重參數。對于每一個訓練樣本，我們首先需要計算估計值和真實值之間 的誤差eui = rui-puql.(2.3) 然后按照相應參數梯度的反方向進行更新參數，更新的方式如下： TOC o 1-5 h z 9J、7； = &ui . Qi + XPu OPuQJ、= ui Pu + Qi& 弗(2)PuPu- ?7T-OPudJQi Qi 7-7,oqi其中7表示學習速率，相當于參數更新的幅度。參數7是十分關鍵的參數，它不 僅會影響算法的學習過程，也會影響

55、目標函數的收斂速率。然而，要選擇合適 的7是一項十分困難的工作，就像許多基于矩陣分解的工作一樣，我們通過Grid Search的方法，在Validation數據集上驗證不同選項的效果，然后經驗性的確 定合適的選擇。同樣，為了能夠防止過擬合，訓練過程需要在達到一定條件的 時候就停止，這樣能夠得到更好的訓練效果。以上描述的是最為基本的，帶有正則項的矩陣分解算法(Regularized Matrix Factorization, RMF),它的高準確率，可拓展性已經被許多工作驗證。然后，在 真實的系統中存在大量的用戶只有很少的評分數據，這讓學習他們的個人品 味變得十分困難。慶幸的是，矩陣分解算法是一

56、種十分靈活的算法，能夠融 入很多除評分之外的信息。在實際應用中，除了用戶提供的少量顯性反饋信 息，推薦系統也能夠十分容易的獲取大量的隱性數據，如點擊，瀏覽等行為。 Koren 28就提出了 SVD+算法將用戶的隱性反饋數據融和到模型中，大幅 度提高了預測效果。Jamali et al. 23也探討了如何利用好友之間的信任關系 提高推薦效果。這些工作將額外資源看成是能夠很大程度上影響用戶和物品 之間相互作用的因素。在本文中，我們假設用戶會更傾向于根據不同信息的重 要程度，衡量它們在最終評分決策的權重。這就好像是評委會根據運動員在不 同方面的表現程度，綜合評價運動員的最終表現。于是，我們基于矩陣分

57、解算 法，刻畫用戶與可能會影響他/她最終決策的信息之間相互作用關系，提出了 多元線性互作用矩陣分解推薦模型(Multi-linear Interactive Matrix Factorization Recommendation Method),以下簡稱MLIMFo2.3.2 Multi-linear Interactive Matrix Factorization在矩陣分解的框架下，用戶勿和某個決策因素頂之間的相互作用可以表示成 相應的特征向量之間的內積，因此，MLIMF的評分函數九/可以定義為：岫戒,(2.5)djEDj其中。表示決策因子集合。公式2.5的第一項表示用戶iz對物品，的偏好，

58、在 符號后面的一項表示用戶iz與其他可能的決策因子頂之間的相互作用。決策因子 通常都是一些類目屬性，某個決策因子頂可能的取值情況表示成為有限集合。頂。 其中指示函數1(壽,婦=1如果用戶iz在對物品虧進行評價的時候，關注了決策 因子項的具體值dj G Dj,否則l(u,令，婦=0。換句話說，山表示了某個環(huán)境決策 因子的具體值。舉個例子，一個對成龍的尖峰時刻1電影評5分的用戶很可 能也會對其他成龍主演的電影給予比較高的評價。在這個例子中的決策因子可 以理解為演員，演員的具體值為成龍。為了刻畫用戶與其他信息之間的相互作 用，我們需要引入一組新的特征向量參數，其中決策因子頂的具體值對應的 特征向量為

59、q% fDj表示決策因子Q項集合中每個決策因子對應的特征向 量的維度。對應地，我們也為每個用戶1/定義了另外一組特征向量pudj G , 用于刻畫用戶與某個決策因子之間的關系。最終，MLIMF的目標函數，為：-Pu(s 一 EE婦Pu%q*)2Jueu ieljeDdjeDjueu jeD djDjjeD djCDj+ (IIpIIf + IIIIf)其中，)和的關系可以由圖2.1b來展現。左側藍色矩形表示用戶 選擇過哪些物品，右側灰色矩形又進一步指出了在對物品評分的時候可能考慮 的因素。為了進一步的表達該意思，我們可以理解成，用戶在對物品做出評價 的同時，也考慮了相關的信息。在融入了額外信息

60、號，公式2.6比公式2.2要復雜的多。雖然如此, 在SGD學習框架下，模型參數任然能夠高效的學習到。類似于2.4我們先通過以下公式計算不同參數的梯度：=ui , Qi +=ui , Pu +(2-7) =ui , Qdj + Pudj=ui , Pudj + 禎志dJ dpu dJ_ dqi % dPudj dJ g%對于每個訓練樣本，格式為u, i, dr, dD,更新模型參數的方式為：Pu Pu- 7(e - qi Xpu)q qi + 7(eUz pu 一梅)(2.8) Pudj Pudj + Qdj Pudj )q% q% +- Pu 一 沖)通過公式2.7和公式2.8,模型參數可以在