《推薦系統 - 技術、評估及高效演算法》 - 第4章 基於近鄰推薦方法綜述

近鄰(nearest-neighbor)演算法廣泛應用於協同推薦。基於近鄰的方法是基於評分間關聯性的,對相同物品進行評分的用戶可作為近鄰,被近鄰用戶評價過的物品會被推薦。

一、簡介:

1.1 用戶對物品反饋類型:

  • 分級反饋:如1-5星、強烈同意/同意/一般/反對/強烈反對;

  • 二元反饋:喜歡/不喜歡;

  • 一元反饋:買;

1.2 獲得用戶反饋的方法:

  • 觀影后提示打分(獲得分級反饋)、及評論(通過評論分析主要觀點,提取觀點關鍵詞);

  • 購買歷史;

  • 訪問模式:如用戶在為一類物品或某一個物品花費較長時間瀏覽(雖然沒有購買,但也很有興趣);

1.3 評估效果:準確率、召回率、驚喜度

1.4 推薦方法概要:

  • 基於內容(content-based):通過用戶已評分的物品確定這些物品的共同特點,通過這些特點為用戶推薦新物品;利用「餘弦相似度」或「最小描述長度」等方法推薦「特徵向量」與「偏好向量」最相似的新物品;
  1. 受限內容分析(limited content analysis):用戶及物品信息有限,如用戶提供的個人信息有限、好文章與差文章間有相同短語,而不能區分文章質量;
  2. 特化(over-specialization):豐富度不高,加入隨機或過濾掉過於相似的物品,用以解決此問題;
  • 協同過濾方法(col-laborative filtering):利用系統中其他用戶評分過的物品,可以克服基於內容方法的一些局限。據和用戶自己興趣相同的人或其他可信息源獲得新物品推薦。

  1. 基於近鄰的協同過濾:在預測中直接使用已有數據預測,User CF(基於評分相似的用戶,再推薦近鄰用戶喜歡的物品,如「推薦用戶A喜歡的電影」)、Item CF(基於評化相似的物品,如「高分電影片單間的推薦」、「推薦相同演員/導演的電影「);
  2. 基於模型的協同過濾:使用用戶對物品的評分學習預測模型,使用屬性構建用戶和物品間關聯,屬性代表在系統中用戶和物品的潛在特徵,如用戶喜愛的類別和物品屬於的類別。這種模型是通過數據訓練的,然後為用戶預測新的物品。如貝葉斯聚類(Bayesian Clustering)、潛在語義分析(Latent Semantic Analysis)、潛在狄利克雷分布(Latent Dirichlet Allocation)、最大熵(Maximum Entropy)、玻爾茲曼機(Boltzmann Machines)、支持向量機(Support Vector Machines)、奇異值分解(Singular Value Decomposition);

1.5 基於近鄰方法的優勢:驚喜度高、簡單、合理、高效、穩定;

二、基於近鄰推薦:

2.1 基於近鄰推薦類型:

  • 基於用戶對某物品的評分:推薦對應物品;

  • 基於用戶對物品分類的評分:推薦對應物品分類;

  • 回歸與分類:如對A類物品評分是0-10,對B類物品評分是好/不好;利用回歸方法使物品評分較平均;分類則是輸出物品的最頻繁評分,如物品C有10次評分是好,11次評分是不好,則輸出不好(此方法比較冒險,但也比較有吸引力,產生驚喜度的概率偏高)

  • 基於物品推薦:通過評分相近物品做預測;

2.2 基於用戶和基於物品的對比:

  • 準確性:用戶量 遠遠 > 物品量(如亞馬遜) -- 基於物品推薦更準確;物品量 > 用戶量(如論文系統) -- 基於用戶推薦更準確;

  • 效率:用戶量 遠遠 > 物品量 -- 基於物品的推薦更省時間;在線計算依賴有限的物品量和近鄰數最大值,所以兩個方法效率相同;
  • 穩定性:若物品列表穩定變化小則基於物品推薦更穩定,若物品列表變化快(新增較快)則基於用戶推薦更穩定;
  • 合理性:基於物品的方法易於證明合理性(近鄰物品列表、與被推薦項的相似度權重等都可做為解釋),但用基於用戶的方法很難做到這點;
  • 驚喜度:基於物品推薦相對來說較安全,基於用戶推薦驚喜度更高;

3、近鄰方法的要素:

3.1 評分標準化:

  • 原因:用戶對物品評分並不公正,會給自己喜歡的物品評分較高,給自己不喜歡的評分較低(如不喜歡某個主演,即使作品還不錯,仍會給低分);
  • 選擇哪種標準化方法:用戶對物品的評分不稀疏(如用戶A給予評分的物品過少)可選擇「均值中心化」方法,更新研究顯示「Z-score」更有優勢;
  • 補充方法:若標準化方法對結果改進結果無力,則可選擇「基於偏好的過濾(preference-based filtering)」,此方法更關注預測用戶的相對偏好,而不需要標準化評分;

均值中心化:

  • 方法:(用戶A對物品A的評分) 減去(用戶A對所有物品的評分的平均分);

  • 經驗:用戶對物品的喜好,標準化後得分仍為正值,說明用戶喜歡此物品;標準化後得分為負值,說明用戶並不喜歡此物品;

Z-score標準化:

  • 原理:考慮個人評分範圍不同帶來的差異性(方差);如用戶A和用戶B打分均值是3,用戶A的打分區間是1-5,用戶B給每個物品打分都是3,那麼若用戶B給物品C打分是5,則說明用戶特別喜歡這個物品;

3.2 相似度權重計算:

基於近鄰推薦中最重要的環節,直接影響推薦的準確性及性能。作用:相似度計算用於預測評分、對不同近鄰給予預測權重。

  • 信息檢索中:將A和B表示成向量形式,再計算兩向間的餘弦向量相似度;

  • 推薦系統中:計算用戶間的相似度(利用用戶對物品的評分)

  • 皮爾遜相似度:僅考慮用戶評分交集的標準差,而不是全部評分;如基於用戶評分交集,計算用戶及物品間的相似度;

  • 均方差(Mean Squared Difference,MSD):使用用戶U和V對相同物品評分差的平方總和均值的倒數表示兩個人的相似度;
  • 斯皮爾曼等級關聯(Spearman Rank Correlation,SRC):運用評分的排名,定義物品A在用戶U評分物品的排位(以及平均排名)。當用戶評分量少時,這種方法效果不佳;
  • 用戶間相似度加入」重要性權重「策略,當兩人共同評分物品少於某值時,則做比例懲罰;
  • 兩個用戶對物品給出一致的喜歡或不喜歡評分,可能會不如他們給出差異較大的評分時提供更多的信息量;」反用戶頻率(Inverse User Frequency)「基於信息檢索中的」反文檔頻率(Inverse Document Frequency,IDF);

3.3 近鄰的選擇:

選擇近鄰的通常方法:

  1. 用全局過濾保持最有可能的近鄰;

  2. 在預測每一步時選擇最合適的近鄰做為預測;

過濾預選近鄰數:

大型推薦系統中包含用戶和物品信息量過大,由於內存限制,不可能存儲全部用戶及物品信息,故需做預選近鄰:

  • TOP-N過濾:對於每個用戶或物品,保留N個近鄰信息。N過大會影響效率,N過小會影響推薦結果準確率;

  • 閾值過濾:保留相似度大於一定閾值的近鄰。保留重要的近鄰,但閾值的選擇也是比較困難的;

  • 負值過濾:責評分關聯被過濾;但負關聯不能顯示留下近鄰組的差異程度 ,一些實驗發現負關聯對預測準確性沒有顯示提高;

  • 以上三種方法不互斥,可為需要做結合;

用於預測的近鄰:

選擇出近鄰列表後,通過k近鄰方法得到新的評分預測。k近鄰為相似度權重最大的k個近鄰,如何選擇k值很重要。

當k值較小時(如 k<20),準確率較低;增加k值準確率會提高;加入更多近鄰(如 k>50),準確率會再度下降,因為重要的關聯會被不重要的關聯削弱;一些文獻建議,近鄰數大約在20-50間,但據不同項目,需用交叉驗證的方法再做驗證;

注意,基於少量非常相似的用戶可以得到更新穎的結果,代價是降低準確度。如找到與用戶A最相似的用戶B,將推薦用戶B評分最高的物品C給用戶A;

4、高級進階技術:

基於評分間關聯性的近鄰方法的重要缺陷:

  • 覆蓋受限:對相同物品進行評分的用戶可作為近鄰,被近鄰用戶評價過的物品會被推薦。在用戶和物品的選擇中都有覆蓋限制;

  • 對稀疏數據的敏感:冷啟動問題,新加入用戶及物品沒有評分;

  • 解決方法:提供默認數據、對於無評分確實做評分預測(如filterbots自動組件做缺失評分預測);

以下兩種方法,均是將矩陣分解為因子來表示用戶或物品所映射到的隱空間

4.1 降維方法:

  • 對用戶評分矩陣進行分解:用戶對物品的評分,分解為」用戶因子矩陣「和」物品因子矩陣「,通過對兩個矩陣的學習,計算用戶間、物品間的相似度;

  • 對相似性矩陣進行分解:設W為代表用戶或物品相似度的秩為n的」對稱矩陣「, 計算W的壓縮版本,相比W不那麼稀疏;

4.2 基於圖的方法:

將數據用圖的方法表示,用戶、物品或兩者都可用點的形式表示:

  • 邊表示用戶和物品間的交互或相似度;

  • 每個邊有不同的權重,所謂「傳播」

  • 距離越長表示相似度越低,所謂「衰減」

兩種基於圖的推薦方法:

  • 基於路徑的相似度:在系統中為用戶推薦物品,可通過找到用戶u在圖中最近的物品;

  • 隨機遊走相似性:用戶或者物品間的相似性可估算為到達這些點的隨機漫步概率。

  1. ItemRank:基於用戶在圖中隨機遊走訪問物品的概率,對用戶對新物品的喜愛程度進行排序;
  2. 平均首次通過/往返次數:據往返次數距離,尋找用戶u的近鄰用戶,為用戶u推薦這些用戶喜歡的物品;所往返次數的極小值,為用戶u推薦物品i;

參考文獻:弗朗西斯科·里奇 (Francesco Ricci) 《推薦系統:技術、評估及高效演算法》 機械工業出版社; 第1版 (2015年7月1日)

推薦閱讀:

《起點中文網》有哪幾個作者值得推薦?
關於麥克風的購買攻略有哪些?
夏天太熱,多虧它們,宅家不出門星人照樣吃好睡好|慢慢的7月好物推薦
一物多用!最大限度減輕化妝包的補妝好物推薦~
備婚攻略 | 除了酒店浴袍,婚禮當天早上還能穿什麼?

TAG:推薦 | 演算法 | 推薦演算法 |