基于物品的协同过滤演算法

第五章推薦王海目錄1推薦系統的出現2推薦引擎的分類3主流推薦演算法4結束語推薦系統的出現推薦：把使用者模型中興趣需求資訊和推薦對象的特徵資訊匹配，同時使用相應的推薦演算法進行計算刷選，找到使用者可能感興趣的推薦對象，然後推薦給使用者。推薦系統應運而生…比如，早上買包子的時候，老闆就經常問我要不要來杯豆漿。推薦在生活中無處不在推薦在生活中無處不在社交網站：向他推薦可能感興趣的人；基於社交圖譜的推薦：根據其好友的偏好來向其推薦人、群組、內容、商品等。電子商務：個性化推薦6推薦在生活中無處不在7推薦對企業的價值•亞馬遜：35%的銷售來自推薦。–貝索斯：“如果我有一百萬的用戶，我就會做一百萬個不同的網站！”。•Netflix：75%的觀看來自推薦。推薦與搜索的差別•推薦滿足的是非明確的需求。因此，推薦結果的點擊率低於搜索結果。常用推薦演算法推薦技術發展至今已經歷了十餘年。開發者們試過各種各樣的方法。經過大量的實踐，人們發現似乎沒有任何一個方法可以獨領風騷、包打天下。不過，目前，協同過濾使用最普遍。10基於用戶的協同過濾•適於物品比用戶多、物品時效性較強的情形，例如：新聞網站、新網站。否則計算慢•推薦結果的個性化較弱、較寬泛，但能實現跨領域、驚喜度高的結果Digg的文章推薦、Last.fm的音樂推薦基於物品的協同過濾•應用最廣泛，尤其以電商行業為典型。•適於用戶多、物品少的情形，否則計算慢•在物品冷開機、數據稀疏時效果不佳•推薦精度高，更具個性化；但傾向於推薦用戶購買過商品的類似商品，所以推薦的多樣性和驚喜度不足，用戶永遠看不到新穎的物品Amazon等電商、Netflix、Youtube11基於內容的演算法•是最直觀的演算法•容易受限於對文本、圖像、音視頻的內容進行描述的詳細程度。•常借助文本相似度計算，文本可來自物品描述、UGC等。•但推薦精度通常墊底•主題過於集中，驚喜度不足新聞網站（例如百度新聞）、百度文檔基於統計思想的方法•例如：SlopeOne、關聯規則、分類熱門推薦。•其線上部分計算速度快；直觀。•對個性化偏好的描述能力弱（精度低）一些電商網站隱含因數模型•難以即時對模型做增量更新•可解釋性差Netflix、YahooMusic基於協同過濾的推薦——基於用戶的協同過濾推薦核心思想：基於用戶對物品的偏好找到相鄰鄰居用戶，然後將鄰居用戶喜歡的推薦給當前用戶•和我興趣相似的人喜歡的商品我也會喜歡。步驟：1.根據用戶對各種物品的偏好值的相似程度，對每兩個用戶之間進行相似度計算，為每個用戶找到與之相似度最高的幾個鄰居用戶，2.然後將鄰居用戶對每個物品的偏好值的加權平均作為目標使用者的偏好值的預測值。把預測值最高的多個商品作為目標使用者的推薦清單。其中，每個鄰居用戶的權重取決於該鄰居使用者與目標使用者之間的相似度。基於協同過濾的推薦——基於用戶的協同過濾推薦•如何計算用戶間的相似度：基於協同過濾的推薦——基於用戶的協同過濾推薦設N(u)為用戶u有過正回饋的物品集合，設N(v)為用戶v有過正回饋的物品集合，u和v的興趣相似度可以用Jaccard公式或余弦相似度計算，)()()()(vNuNvNuNuv)()()()(vNuNvNuNuvJaccard公式余弦公式基於協同過濾的推薦——基於用戶的協同過濾推薦舉例：下圖表示用戶A對物品{a,b,d}有過行為，用戶B對物品{a,c}有過行為利用余弦相似度計算可得：用戶A和用戶B的興趣相似度為：同理，61},{},,{},{},,{ABcadbacadba61},{},,{},{},,{ACebdbaebdba31},,{},,{},,{},,{ADedcdbaedcdba基於協同過濾的推薦——基於用戶的協同過濾推薦舉例：下圖表示用戶A對物品{a,b,d}有過行為，用戶B對物品{a,c}有過行為給用戶推薦和他興趣最相似的K個用戶喜歡的物品其中，p(u,i)表示用戶u對物品i的感興趣程度，S(u,k)表示和用戶u興趣最接近的K個用戶，N(i)表示對物品i有過行為的使用者集合，wuv表示用戶u和用戶v的興趣相似度，Rvi表示用戶v對物品i的興趣（這裡簡化，所有的Rvi都等於1）。可以算出，用戶A對物品c、e的興趣是：)(),(),(iNKuSvviuvriup7416.0),(ADABcAp7416.0),(ADACeAp基於使用者的協同過濾的一大缺點•形成有意義的鄰居集合很難。–很多用戶兩兩之間只有很少幾個共同評分。–而僅有的共同打了分的物品，往往是票房大片。–再者，用戶之間的距離可能變得很快。這種離線演算法難以瞬間更新推薦結果。R實戰-基於使用者的協同過濾演算法##（0）安裝載入R包install.packages('recommenderlab')library(recommenderlab)##（1）載入數據集data(Jester5k)#該數據集包含5000個樣本數據，來源於Jester線上笑話推薦系統搜集的1999年4月至2003年5月期間的匿名使用者對笑話的評價數據#數據集包含對100個笑話的評價，評分從-10至+10#數據集中所有用戶至少評價36個笑話#Jester5k包含362106個評分##（2）基於用戶的推薦#hist(getRatings(Jester5k),main=Distributionofratings)rU-Recommender(Jester5k[1:1000],method=UBCF)rUR實戰-基於使用者的協同過濾演算法#向第1001和1002用戶推薦的5個物品recomU-predict(rU,Jester5k[1001:1002],n=5)recomUas(recomU,list)#預測評分recomU-predict(rU,Jester5k[1001:1002],type=ratings)recomUas(recomU,matrix)[,1:10]R實戰-基於使用者的協同過濾演算法##（3）評價方案：1000個樣本，90%作為訓練集，10%作為測試集#測試集中15個物品用於推薦演算法中，另外的用於計算誤差e-evaluationScheme(Jester5k[1:1000],method=split,train=0.9,given=15,goodRating=5)e#應用訓練集產生基於用戶的推薦r1-Recommender(getData(e,train),UBCF)#對已知部分的測試數據（每個使用者對15個物品的評分）用基於使用者的推薦演算法計算預測評分p1-predict(r1,getData(e,known),type=ratings)errorU-calcPredictionAccuracy(p1,getData(e,unknown))errorURMSE：標準差MSE：方差MAE：平均絕對誤差基於協同過濾的推薦——基於物品的協同過濾推薦核心思想：在計算鄰居時採用物品本身，即基於用戶對物品的偏好找到相似的物品，然後根據用戶的歷史偏好，推薦相似的物品給他。•這個方法由亞馬遜公司最早提出。在電商中得到了廣泛使用。•基於用戶對物品的偏好計算出物品之間的相似度，然後根據當前使用者的偏好，推薦相似的物品給他。–例：購買手機的人也都購買了iPad，則說明這兩個物品相似。–當使用者搜索或流覽手機，系統會向他推薦iPad。•調參：採用何種相似度度量？基於協同過濾的推薦——基於物品的協同過濾推薦)()()()(jNiNjNiNij其中是喜歡物品的用戶數，是同時喜歡物品i和物品j的用戶數。)(jN)()(jNiN基於協同過濾的推薦——基於物品的協同過濾推薦舉例：用戶A對物品a、b、d有過行為，用戶B對物品b、c、e有過行為，等等；依此構建用戶--物品倒排表：物品a被用戶A、E有過行為，等等0)()()()(21)()()()(0)()()()(61)()()()(eNaNeNaNdNaNdNaNcNaNcNaNbNaNbNaNeaaedaadcaacbaab基於協同過濾的推薦——基於物品的協同過濾推薦在得到物品之間的相似度後，進入第二步：根據物品的相似度和用戶的歷史行為給用戶生成推薦列表：ItemCF通過如下公式計算用戶u對一個物品j的興趣：其中，puj表示用戶u對物品j的興趣，N(u)表示使用者喜歡的物品集合（i是該用戶喜歡的某一個物品），S(i,K)表示和物品i最相似的K個物品集合（j是這個集合中的某一個物品），wji表示物品j和物品i的相似度，Rui表示用戶u對物品i的興趣（這裡簡化Rui都等於1）。),()(KiSuNiuijiujrp基於協同過濾的推薦——基於物品的協同過濾推薦舉例：用戶A喜歡《C++Primer中文版》和《程式設計之美》兩本書，然後ItemCF會為這兩本書分別找出和它們最相似的3本書，並根據公式計算使用者對每本書的感興趣程度。比如ItemCF給使用者推薦《演算法導論》，是因為這本書和《C++Primer中文版》相似--相似度為0.4，而且這本書也和《程式設計之美》相似--相似度是0.5。考慮到用戶對《C++Primer中文版》的興趣度是0.3，對《程式設計之美》的興趣度是0.9，那麼使用者對《演算法導論》的興趣度就是1.3×0.4+0.9×0.5=0.97。以此類推可得用戶A對《C++程式設計思想》、《代碼大全第二版》、《EffectiveC++中文版》、《程式設計珠璣》的感興趣度分別為0.91、0.45、0.78和0.54。基於此便可以確定對使用者A的物品推薦順序為：《演算法導論》、《C++程式設計思想》、《EffectiveC++中文版》、《程式設計珠璣》、《代碼大全第二版》。•優點：一對物品之間的距離可能是根據成百上千萬的用戶的評分計算得出，往往能在一段時間內保持穩定。–因此，這種演算法可以預先計算距離，其線上部分能更快地生產推薦列表。•缺點：不同領域的最熱門物品之間經常具有較高的相似度。這樣，可能會給喜歡《演算法導論》的同學推薦《哈利波特》。–為此，在運行這種演算法時可以不納入最暢銷商品。26基於協同過濾的推薦——基於物品的協同過濾推薦R實戰-基於物品的協同過濾演算法##（0）安裝載入R包install.packages('recommenderlab')library(recommenderlab)##（1）載入數據集data(Jester5k)#該數據集包含5000個樣本數據，來源於Jester線上笑話推薦系統搜集的1999年4月至2003年5月期間的匿名使用者對笑話的評價數據#數據集包含對100個笑話的評價，評分從-10至+10#數據集中所有用戶至少評價36個笑話#Jester5k包含362106個評分##（2）基於物品的推薦rI-Recommender(Jester5k[1:1000],method=IBCF)rIR實戰-基於物品的協同過濾演算法#向第1001和1002用戶推薦的5個物品recomI-predict(rI,Jester5k[1001:1002],n=5)recomIas(recomI,list)#預測評分recomI-predict(rI,Jester5k[1001:1002],type=ratings)recomIas(recomI,matrix)[,1:10]R實戰-基於物品的協同過濾演算法##（3）評價方案：1000個樣本，90%作為訓練集，10%作為測試集#測試集中15個物品用於推薦演算法中，另外的用於計算誤差e-evaluationScheme(Jester5k[1:1000],method=split,train=0.9,given=15,goodRating=5)#應用訓練集產生基於物品的推薦r2-Recommender(getData(e,train),IBCF)#對已知部分的測試數據（每個使用者對15