協(xié)同過濾（英語：Collaborative Filtering，簡稱CF），簡單來說是利用某興趣相投、擁有共同經(jīng)驗之群體的喜好來推薦用戶感興趣的信息，個人透過合作的機制給予信息相當(dāng)程度的回應(yīng)（如評分）并記錄下來以達到過濾的目的進而幫助別人篩選信息，回應(yīng)不一定局限于特別感興趣的，特別不感興趣信息的紀錄也相當(dāng)重要?！S基百科

基于物品的協(xié)同過濾算法（item-based collaborative filtering，簡稱ItemCF）是目前業(yè)界應(yīng)用最多的算法。

亞馬遜、Netflix、Hulu、YouTube的推薦算法的基礎(chǔ)都是基于物品的協(xié)同過濾算法。

基于用戶的協(xié)同過濾算法有一些缺點。

• 隨著網(wǎng)站的用戶數(shù)目越來越大，計算用戶興趣相似度矩陣將越來越困難，其運算時間復(fù)雜度和空間復(fù)雜度的增長和用戶數(shù)的增長近似于平方關(guān)系。
• 基于用戶的協(xié)同過濾算法很難對推薦結(jié)果作出解釋。

基于物品的協(xié)同過濾算法優(yōu)勢：

• 計算性能高，通常用戶數(shù)量遠大于物品數(shù)量。
• 可預(yù)先計算保留，物品并不善變。

---

$ItemCF$ 算法給用戶推薦那些和他們之前喜歡的物品相似的物品。

舉個例子：

用戶/物品物品A物品B物品C

用戶A	√		√
用戶B	√	√	√
用戶C	√		與物品A相似，推薦

$ItemCF$ 算法并不利用物品的內(nèi)容屬性計算物品之間的相似度，它主要通過分析用戶的行為記錄計算物品之間的相似度。該算法認為，物品 $A$ 和物品 $B$ 具有很大的相似度是因為喜歡物品 $A$ 的用戶大都也喜歡物品 $B$。

基于物品的協(xié)同過濾算法可以利用用戶的歷史行為給推薦結(jié)果提供推薦解釋，比如給用戶推薦《機器學(xué)習(xí)實戰(zhàn)》的解釋可以是因為用戶之前買過《統(tǒng)計學(xué)習(xí)方法》。

---

基于物品的協(xié)同過濾算法步驟：

計算物品之間的相似度。

根據(jù)物品的相似度和用戶的歷史行為給用戶生成推薦列表。

---

定義物品的相似度為$$w_{ij}=\frac{|N(i)\cap N(j)|}{|N(i)|}$$此處分母 $|N(i)|$ 是喜歡物品 $i$ 的用戶數(shù)，而分子 $|N(i)\cap N(j)|$ 是同時喜歡物品 $i$ 和物品 $j$ 的用戶數(shù)。因此，上述公式可以理解為喜歡物品 $i$ 的用戶中有多少比例的用戶也喜歡物品 $j$。

但該公式存在一個問題，如果物品 $j$ 很熱門，很多人都喜歡，那么 $w_{ij}$ 就會很大，接近1。因此，該公式會造成任何物品都會和熱門的物品有很大的相似度，這顯然不是一個好的特性。為了避免推薦出熱門的物品， 可以用下面的公式： $$w_{uv}=\frac{|N(i)\cap N(j)|}{\sqrt{|N(i)||N(j)|}}$$這個公式懲罰了物品 $j$ 的權(quán)重，因此減輕了熱門物品會和很多物品相似的可能性。

---

從上面的定義可以看到，在協(xié)同過濾中兩個物品產(chǎn)生相似度是因為它們共同地被很多用戶喜歡，也就是說每個用戶都可以通過他們的歷史興趣列表給物品“貢獻”相似度。

這里蘊涵著一個假設(shè)，就是每個用戶的興趣都局限在某幾個方面，因此如果兩個物品屬于一個用戶的興趣列表， 那么這兩個物品可能就屬于有限的幾個領(lǐng)域，而如果兩個物品屬于很多用戶的興趣列表，那么它們就可能屬于同一個領(lǐng)域，因而有很大的相似度。

---

與 $UserCF$ 算法類似，用 $ItemCF$ 算法計算物品相似度時也可以首先建立 $用戶?>物品$ 倒排表（即對每個用戶建立一個包含他喜歡的物品的列表），然后對于每個用戶，將他物品列表中的物品兩兩在共現(xiàn)矩陣 $C$ 中加 $1$。

代碼如下：

def ItemSimilarity(train):# 修改相似度矩陣C = dict()N = dict()for u, items in train.items():for i in users:N[i] += 1for j in users:if i == j:continueC[i][j] += 1# 計算相似度矩陣W = dict()for i, related_items in C.items():for j, cij in related_items.items():W[u][v] = cij / math.sqrt(N[i] * N[j])return W

---

如圖是根據(jù)上面的程序計算物品相似度的簡單例子。

最左邊是輸入的用戶行為記錄，每一行代表一個用戶感興趣的物品集合。然后，對于每個物品集合，我們將里面的物品兩兩加一，得到一個矩陣。最終將這些矩陣相加得到最右邊的 $C$ 矩陣。其中 $C[i][j]$ 記錄了同時喜歡物品 $i$ 和物品 $j$ 的用戶數(shù)。最后，將 $C$ 矩陣歸一化可以得到物品之間的余弦相似度矩陣 $W$。

---

在得到物品之間的相似度后，$ItemCF$ 算法通過如下公式計算用戶 $u$ 對一個物品 $j$ 的興趣： $$p_{uj}=\sum _{i\in N(u)\cap S(j,K)}{w}_{ji}{r}_{ui}$$

這里 $N(u)$ 是用戶喜歡的物品的集合，$S(j,K)$ 是和物品 $j$ 最相似的 $K$ 個物品的集合，$w_{ji}$ 是物品 $j$ 和 $i$ 的相似度，$r_{ui}$ 是用戶 $u$ 對物品 $i$ 的興趣。（對于隱反饋數(shù)據(jù)集，如果用戶 $u$ 對物品 $i$ 有過行為，即可令 $r_{ui}=1$）

該公式的含義是，和用戶歷史上感興趣的物品越相似的物品，越有可能在用戶的推薦列表中獲得比較高的排名。

該公式的實現(xiàn)代碼如下：

def Recommendation(train, user_id, W, K):rank = dict()ru = train[user_id]for i, pi in ru.items():for j, wj in sorted(W[i].items(), key=itengetter(1), reverse=True)[0:K]:if j in ru:continuerank[j] += pi * wjreturn rank

---

此處是一個基于物品推薦的簡單例子。該例子中，用戶喜歡《C++ Primer中文版》和《編程之美》兩本書。然后 $ItemCF$ 會為這兩本書分別找出和它們最相似的 $5$ 本書，然后根據(jù)公式計算用戶對每本書的感興趣程度。

$ItemCF$ 給用戶推薦《算法導(dǎo)論》，是因為這本書和《C++ Primer中文版》相似，相似度為 $0.4$，而且這本書也和《編程之美》相似，相似度是 $0.5$。用戶對《C++ Primer中文版》的興趣度是 $1.3$，對《編程之美》的興趣度是 $0.9$，則用戶對《算法導(dǎo)論》的興趣度就是 $1.3\times 0.4+0.9\times 0.5=0.97$。 以此類推……

---

從上述例子可以看到，$ItemCF$ 的一個優(yōu)勢就是可以提供推薦解釋，即利用用戶歷史上喜歡的物品為現(xiàn)在的推薦結(jié)果進行解釋。

如下代碼實現(xiàn)了帶解釋的 $ItemCF$ 算法：

def Recommendation(train, user_id, W, K):rank = dict()ru = train[user_id]for i, pi in ru.items():for j, wj in sorted(W[i].items(), key=itengetter(1), reverse=True)[0:K]:if j in ru:continuerank[j].weight += pi * wjrank[j].reason[i] = pi * wjreturn rank

---

用戶活躍度對物品相似度的影響

在協(xié)同過濾中兩個物品產(chǎn)生相似度是因為它們共同出現(xiàn)在很多用戶的興趣列表中。換句話說，每個用戶的興趣列表都對物品的相似度產(chǎn)生貢獻。

但不是每個用戶的貢獻都相同。

假設(shè)有一個開書店的用戶，買了當(dāng)當(dāng)網(wǎng)上80%的書自己賣。則他的購物車里包含當(dāng)當(dāng)網(wǎng)80%的書。假設(shè)當(dāng)當(dāng)網(wǎng)有100萬本書，則他買了80萬本。這意味著由于存在該用戶，有80萬本書兩兩之間產(chǎn)生了相似度，那么內(nèi)存里即將誕生一個80萬乘80萬的稠密矩陣。

另外，該用戶雖然活躍，但買這些書并非出于自身興趣，且這些書覆蓋了當(dāng)當(dāng)網(wǎng)圖書的很多領(lǐng)域，所以這個用戶對于他所買書的兩兩相似度的貢獻遠遠小于一個只買了十幾本自己喜歡的書的文學(xué)青年。

---

為了解決上述問題，John S. Breese 提出了一個稱為IUF（Inverse User Frequence），即用戶活躍度對數(shù)的 倒數(shù)的參數(shù)，他認為活躍用戶對物品相似度的貢獻應(yīng)該小于不活躍的用戶，他提出應(yīng)該增加IUF參數(shù)來修正物品相似度的計算公式： $$w_{ij}=\frac{\sum _{u\in N(i)\cap N(j)}\frac{1}{log1+|N(u)|}}{\sqrt{|N(i)||N(j)|}}$$

將該算法記為 $ItemCF?IUF$

上述公式對活躍用戶做了一種軟性的懲罰，但對于很多過于活躍的用戶，為了避免相似度矩陣過于稠密，在實際計算中一般直接忽略其興趣列表，不將其納入到相似度計算的數(shù)據(jù)集中。

代碼如下：

def ItemSimilarity(train):# 統(tǒng)計相似度矩陣C = dict()N = dict()for u, items in train.items():for i in users:N[i] += 1for j in users:if i == j:continueC[i][j] += 1 / math.1og(1 + len(items) * 1.0)# 計算相似度矩陣W = dict()for i, related_items in C.items():for j, cij in related_items.items():W[u][v] = cij / math.sqrt(N[i] * N[j])return W

---

物品相似度的歸一化

如果將 $ItemCF$ 的相似度矩陣按最大值歸一化，可以提高推薦的準確率。如果已經(jīng)得到了物品相似度矩陣 $w$，可以用如下公式得到歸一化之后的相似度矩陣 $w^{\prime }$：$$w_{ij}^{\prime }=\frac{w_{ij}}{ma{x}_j{w}_{ij}}$$

歸一化的優(yōu)點：

• 增加推薦的準確度。
• 提高推薦的多樣性。
• 提高推薦的覆蓋率。

多樣性：

一般來說，物品總是屬于很多不同的類，每一類中的物品聯(lián)系比較緊密。

舉一個例子，假設(shè)在某電影網(wǎng)站中，有 $A$ 類片和 $B$ 類片。那么，$ItemCF$ 算出來的相似度一般是 $A$ 類片和 $A$ 類片的相似度或者 $B$ 類片和 $B$ 類片的相似度大于 $A$ 類片和 $B$ 類片的相似度。但是 $A$ 類片之間的相似度和 $B$ 類片之間的相似度卻不一定相同。

假設(shè)物品分為兩類——$A$ 和 $B$，$A$ 類物品之間的相似度為 $0.5$，$B$ 類物品之間的相似度為 $0.6$，而 $A$ 類物品和 $B$ 類物品之間的相似度是 $0.2$。

在這種情況下， 如果一個用戶喜歡了 $5$ 個 $A$ 類物品和 $5$ 個 $B$ 類物品，用 $ItemCF$ 給他進行推薦，推薦的就都是 $B$ 類物品， 因為 $B$ 類物品之間的相似度大。但如果歸一化之后，$A$ 類物品之間的相似度變成了 $1$，$B$ 類物品之間的相似度也是 $1$，這種情況下，用戶如果喜歡 $5$ 個 $A$ 類物品和 $5$ 個 $B$ 類物品，則他的推薦列表中 $A$ 類物品和 $B$ 類物品的數(shù)目也是大致相等的。

從該例子可以看出，相似度的歸一化可以提高推薦的多樣性。

覆蓋率：

對于兩個不同的類，一般來說，熱門的類其類內(nèi)物品相似度一般比較大。如果不進行歸一化，就會推薦比較熱門的類里面的物品，而這些物品也是比較熱門的。因此，推薦的覆蓋率就比較低。相反，如果進行相似度的歸一化，則可以提高推薦系統(tǒng)的覆蓋率。

---

參考資料：《推薦系統(tǒng)實踐》

總結(jié)

以上是生活随笔為你收集整理的【推荐系统】{2} —— 基于物品的协同过滤算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。