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

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

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

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

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

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

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

7、更為嚴重的，需要 處理三元張量關(guān)系的協(xié)同檢索任務(wù)。在兩份真實數(shù)據(jù)集的結(jié)果顯示，我們提出的 算法能夠有效提升預測準確度，尤其是對那些信息含量很少的物品。為Pairwise排序?qū)W習在推薦算法的應(yīng)用提出了一種基于物品的采樣策略， 并進一步定義了一種自適應(yīng)采樣策略,提高了采樣效果的同時，也改善了 Pairwise 算法在稀疏數(shù)據(jù)上的預測準確率。關(guān)鍵詞：推薦系統(tǒng)，矩陣分解，排序?qū)W習，稀疏性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推薦系統(tǒng)研究背景及意義1 HYPERLINK l bookmark66 o Current Document 1.2稀疏環(huán)境下推薦系統(tǒng)研究綜述 3 HYPERLINK l bookmark69 o Current Document 1.3本文研究內(nèi)容和創(chuàng)新點5 HYPERLINK l bookmark74 o Current Document 1.4數(shù)據(jù)集介紹6Movielens 電影評分數(shù)據(jù)集 6Last.fm音樂收聽數(shù)據(jù)集6Yelp商鋪評分數(shù)據(jù)集7Epinions 社交網(wǎng)絡(luò)數(shù)據(jù)集 7 HYPERLINK l bookm

17、ark81 o Current Document 1.5論文結(jié)構(gòu)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 實驗結(jié)果14評價指標14對比方法簡介15實驗參數(shù)設(shè)置16實驗結(jié)果分析17 HYPERLINK l bookmark102 o Current Document 本章小結(jié)18 HYPERLINK l bookmark105 o Current Document 3協(xié)同檢索任務(wù)中的Top-K物品推薦19 HYPERLINK l bookmark108 o Current Document 概述19 HYPERLINK l bookmark111 o Current Do

19、cument 3.2三元張量關(guān)系20 HYPERLINK l bookmark114 o Current Document 3.3基于物品淺層協(xié)同檢索張量模型21 HYPERLINK l bookmark117 o Current Document 實驗結(jié)果25實驗數(shù)據(jù)及預處理25評價方式 26實驗設(shè)置及對比方法簡介 26實驗結(jié)果分析27 HYPERLINK l bookmark125 o Current Document 本章小結(jié)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關(guān)系分析32 HYPERLINK l bookmark139 o Current Document 4.3基于物品貝葉斯排序推薦模型33自適應(yīng)采樣策略35 HYPERLINK l bookmark154 o Current Document 實驗結(jié)果36實驗數(shù)據(jù)36評價指標36對比方法簡介 37實驗結(jié)果分析 38 HYPERLINK l bookmark163 o Current Document 本

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

42、inions社交網(wǎng)絡(luò)數(shù)據(jù)集Epinions是一個非常流行的基于信任機制的社交網(wǎng)絡(luò)，用戶可以免費 注冊，對物品進行評分，或者撰寫評論信息。本文所使用的Epinions數(shù)據(jù)來 自 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個物品所產(chǎn)生 的664823條評分記錄。1.5論文

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

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

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

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

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

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

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

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

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矩陣分解算法預覽在協(xié)同過濾領(lǐng)域，用戶對物品的偏好會表示成一個評分矩陣，其中和分 別表示用戶集U和物品集/的大小。矩陣R對應(yīng)于位置的評分元素凡/表 示用戶對物品的顯示偏好，通常該值越大表示用戶對物品的偏好越強烈。不 同的系

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

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

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

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

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

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

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

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

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