前言

由于 Spark MLlib 中協(xié)同過濾算法只提供了基于模型的協(xié)同過濾算法，在網(wǎng)上也沒有找到有很好的實現(xiàn)，所以嘗試自己實現(xiàn)基于物品的協(xié)同過濾算法（使用余弦相似度距離）

算法介紹

基于物品的協(xié)同過濾算法是目前業(yè)界應用最多的算法，亞馬遜網(wǎng)、Netflix、Hulu、YouTube 都使用該算法作為推薦系統(tǒng)的基礎算法。算法核心思想是根據(jù)用戶對物品的歷史行為記錄，先計算物品之間的相似度，得到與物品最相似的 TopN 個物品，再利用用戶對物品的歷史行為，將用戶訪問過的物品的相似物品推薦給用戶。也就是說，算法分為 2 步：

1. 計算物品之間的相似度
2. 為用戶生成推薦列表

計算物品之間的相似度

計算物品的相似度有很多種算法，如余弦相似度、皮爾森相關度、歐式距離相似度、Tanimoto系數(shù)等，這里我們使用的是余弦相似度。

假設有向量A（x₁,x₂,...x_n）和向量B（y₁,y₂,...y_n）,A、B 之間的余弦相似度為：

余弦相似度公式

雖然物品很多，但并不是每兩個物品都有被相同的用戶訪問過， 也就是說，很多物品直接余弦相似度等于0，為了避免這些計算，我們引入倒排表來解決這一問題。

假設有物品 Item₁、Item₂、Item₃、Item₄，用戶 U₁、U₂、U₃、U₄：
Item₁ 被 U₁、U₂ 訪問，偏好分分別是2、3，轉(zhuǎn)化為向量是（2，3，0，0）
Item₂ 被 U₃、U₄ 訪問，偏好分分別是1、4，轉(zhuǎn)化為向量是（0，0，1，4）
Item₃ 被 U₂，U₃ 訪問，偏好分分別是2、2，轉(zhuǎn)化為向量是（0，2，2，0）
Item₄ 只被 U₃ 訪問，用戶對其的偏好分是5，轉(zhuǎn)化為向量是（0，0，5，0）

1. 先計算每個 Item 的模，即上圖余弦相似度公式中的分母部分，緩存

| Item₁ | = √(2² + 3²) = √13
| Item₂ | = √17
| Item₃ | = √8
| Item₄ | = 5

2. 轉(zhuǎn)化為用戶訪問物品關系，將相同用戶訪問過的 Item 列出，即：

U₁：Item₁(2)
U₂：Item₁(3)，Item₃(2)
U₃：Item₂(1)，Item₃(2)，Item₄(5)
U₄：Item₂(5)

3. 針對同一用戶，計算兩兩物品之間的相似度，輸出<物品對，分數(shù)>，即：

U₁：輸出空
U₂：輸出 <(Item₁, Item₃), 3x2=6>
U₃：輸出 <(Item₂, Item₃), 2>，<(Item₂, Item₄), 5>，<(Item₃, Item₄), 10>
U₄：輸出空
注意：可以將所有物品對 id 小的放前面，以減少后面一半的計算量

4. 將物品對作為 key 聚合，將分數(shù)相加，得到每個物品對的分數(shù)和，即上圖余弦相似度公式中的分子部分。再從緩存中取出分母部分相除，即兩兩物品的相似度。如 Item₂ 和 Item₄ 的余弦相似度=5/(√17 x 5) = 1/√17
5. 如果要取物品的 TopK 相似的物品，可將得到的兩兩相似度結果（其實是半個相似度矩陣）擴展，然后按 key 聚合取 TopK 個。另外，實踐表明針對同一物品，如果將相似度進行歸一化 similary_i/similary_max 有助于提高最終推薦結果的精度。

為用戶生成推薦列表

現(xiàn)在已經(jīng)有每個物品的 TopK 個相似的物品信息，結合用戶對物品的訪問情況，將用戶訪問過的每個物品的相似物品取出，按相似度加權，排除已經(jīng)訪問過的物品，就可以得到用戶的推薦列表，具體計算步驟如下：

1. 將<物品，相似物品列表> 與 <物品，訪問過該物品的用戶列表> join，得到<物品，（相似物品列表，訪問過該物品的用戶列表）>
2. 交叉遍歷相似物品列表和訪問過該物品的用戶列表，得到很多 <用戶，（物品，分數(shù)）>
3. 按用戶聚合，將相同物品的分數(shù)相加，按分數(shù)排序，取 TopK，即該用戶的推薦列表

實現(xiàn)

基于以上的算法，本人嘗試用 java 實現(xiàn)，代碼放在 GitHub，希望讀者指正。