此文是根據(jù)《推薦系統(tǒng)實(shí)踐》部分整理而來(lái)。

PART 1

基于鄰域的算法是推薦系統(tǒng)中最基本的算法，主要分為兩大類：

• 基于用戶的協(xié)同過(guò)濾算法
• 基于物品的協(xié)同過(guò)濾算法

第一部分介紹基于用戶的協(xié)同過(guò)濾算法。在一個(gè)在線個(gè)性化推薦系統(tǒng)中，當(dāng)一個(gè)用戶A需要個(gè)性化推薦時(shí)，可以先找到和他有相似興趣的其他用戶，然后把那些用戶喜歡的、而A沒(méi)有聽(tīng)說(shuō)過(guò)的物品推薦給A。
主要包括兩個(gè)步驟

1. 找到和目標(biāo)用戶興趣相似的用戶集合（如果有標(biāo)簽系統(tǒng)能夠就會(huì)提供很大的幫助）；
2. 找到這個(gè)集合中的用戶喜歡，且目標(biāo)用戶沒(méi)有聽(tīng)說(shuō)過(guò)的物品推薦給目標(biāo)用戶。

步驟1的關(guān)鍵就是計(jì)算兩個(gè)用戶的興趣相似度。這里，協(xié)同過(guò)濾算法主要利用行為的相似度計(jì)算興趣的相似度，給定用戶u和用戶v，令N(u)表示用戶u曾經(jīng)有過(guò)正反饋的物品集合，令N(u)為用戶v曾經(jīng)有過(guò)正反饋的物品集合。那么，我們可以通過(guò)如下的Jaccard公式簡(jiǎn)單地計(jì)算u和v的興趣相似度：

Paste_Image.png

或者通過(guò)余弦相似度計(jì)算：

Paste_Image.png

舉個(gè)例子。用戶A對(duì)物品{a,b,d}有過(guò)行為，用戶B對(duì)物品{a,c}有過(guò)行為，利用余弦相似度公式計(jì)算用戶A和用戶B的興趣相似度為：

Paste_Image.png

如果對(duì)所有兩兩用戶都利用余弦相似度計(jì)算相似度，這種方法的的時(shí)間復(fù)雜度是O(U*U)，這在用戶數(shù)大的時(shí)候非常耗時(shí)。事實(shí)上，很多用戶相互之間并沒(méi)有對(duì)同樣的物品產(chǎn)生過(guò)行為，很多的時(shí)候|N(u)∩N(v)|=0?？梢允紫群Y選出≠0的用戶對(duì)。

為此，可以首先建立物品到用戶的倒排表。對(duì)于每個(gè)物品都保存對(duì)該物品產(chǎn)生過(guò)行為的用戶列表。令稀疏矩陣C[u][v]=|N(u)∩N(v)|。那么，假設(shè)用戶u和v同時(shí)屬于倒排表中K個(gè)物品對(duì)應(yīng)的用戶列表，就有C[u][v]=K。從而，可以掃描倒排表中每個(gè)物品對(duì)應(yīng)的用戶列表，將用戶列表中的兩兩用戶對(duì)應(yīng)的C[u][v]加1。例子展示如下：

Paste_Image.png

本人再提及一點(diǎn)，在對(duì)內(nèi)容型產(chǎn)品不能直接使用以上算法，因?yàn)椤拔锲贰睌?shù)量太多，在這里可以對(duì)內(nèi)容打上標(biāo)簽，由標(biāo)簽來(lái)替代物品；同時(shí)，如果給用戶建立畫(huà)像，直接給用戶的興趣打上標(biāo)簽，那么會(huì)更加容易。

得到用戶之間的興趣相似度后，UserCF算法會(huì)給用戶推薦和他興趣最相似的K個(gè)用戶喜歡的物品。如下的公式度量了UserCF算法中用戶u對(duì)物品i的感興趣程度：

Paste_Image.png

其中，S(u,K)包含和用戶u興趣最接近的K個(gè)用戶，N(i)是對(duì)物品i有過(guò)行為的用戶集合，wuv是用戶u和用戶v的興趣相似度，rvi代表用戶v對(duì)物品i的興趣，因?yàn)槭褂玫氖菃我恍袨榈碾[反饋數(shù)據(jù)，所以所有的rvi=1。

根據(jù)上圖的用戶為例，選取K=3，用戶A對(duì)物品c、e沒(méi)有過(guò)行為，因此因此可以把這兩個(gè)物品推薦給用戶A。根據(jù)UserCF算法，用戶A對(duì)物品c、e的興趣是：

Paste_Image.png

下表的離線實(shí)驗(yàn)來(lái)評(píng)測(cè)基礎(chǔ)算法的性能。UserCF只有一個(gè)重要的參數(shù)K，即為每個(gè)用戶選出K個(gè)和他興趣最相思的用戶，然后推薦那K個(gè)用戶感興趣的物品。因此離線實(shí)驗(yàn)測(cè)量了不同K值下UserCF算法的性能指標(biāo)：

Paste_Image.png

為了反映該數(shù)據(jù)集上離線算法的基本性能，下圖給出兩種基本推薦算法的性能。其中，Random算法每次都隨機(jī)挑選10個(gè)用戶沒(méi)有產(chǎn)生過(guò)行為的物品推薦給當(dāng)前用戶，MostPopular算法則按照物品的流行度給用戶推薦他沒(méi)有產(chǎn)生過(guò)行為的物品中最熱門的10個(gè)物品。這兩個(gè)算法都是非個(gè)性化的推薦算法：

Paste_Image.png

可以看出，UserCF的準(zhǔn)確率和召回率相對(duì)MostPopular算法提高了將近1倍。同時(shí)，UserCF的覆蓋率遠(yuǎn)遠(yuǎn)高于MostPopular，推薦結(jié)果相對(duì)MostPopular不太熱門。同時(shí)可以發(fā)現(xiàn)參數(shù)K是UserCF 的一個(gè)重要參數(shù)，它的調(diào)整對(duì)推薦算法的各種指標(biāo)都會(huì)產(chǎn)生一定的影響：

• 準(zhǔn)確率和召回率?？梢钥吹?，推薦系統(tǒng)的精度指標(biāo)病不和參數(shù)K成線性關(guān)系。在MovieLens數(shù)據(jù)集中，選擇K=80左右會(huì)獲得比較高的準(zhǔn)確率和召回率。
• 流行度?？梢钥吹?，在3個(gè)數(shù)據(jù)集上K越大UserCF推薦結(jié)果就越熱門。這是因?yàn)镵決定了UserCF在給你做推薦時(shí)參考多少和你興趣相似的其他用戶的興趣，那么K越大，參考人越多，結(jié)果就越來(lái)越趨近于全局熱門的物品。
• 覆蓋率?？梢钥吹?，在3個(gè)數(shù)據(jù)集上K越大UserCF推薦結(jié)果的覆蓋率越低。覆蓋率降低是因?yàn)榱餍卸鹊脑黾樱瑢?duì)長(zhǎng)尾物品的推薦越來(lái)越少，造成了覆蓋率的降低。

上一段中用余弦相似公式計(jì)算用戶興趣相似度比較粗略，這段主要介紹下公式的改進(jìn)。當(dāng)兩個(gè)用戶對(duì)冷門物品采取過(guò)同樣的行為，更能說(shuō)明他們興趣的相似度。因此公式如下：（log1+N(i)什么意思？沒(méi)有底數(shù)）

Paste_Image.png

可以看到，該公式通過(guò) 1/log1+|N(i)| 懲罰了用戶u和v共同興趣列表中熱門物品對(duì)他們相似度的影響。這種算法作者記為：User-IIF 算法。

下圖展示了UserCF和UserCF-IIF的對(duì)比推薦性能，在這里選取K=80：

Paste_Image.png

如圖所示，User-IIF 在各方面略優(yōu)于 User-CF，說(shuō)明在計(jì)算用戶興趣相似度時(shí)考慮物品的流行度對(duì)提升推薦結(jié)果的質(zhì)量確實(shí)有幫助。

本段介紹下實(shí)際使用UserCF 推薦算法的實(shí)例。最著名的使用者是Digg ，系統(tǒng)設(shè)計(jì)主要通過(guò)頂和踩。這種簡(jiǎn)單的推薦算法的效果在Digg的微博中公布出來(lái)：

• 用戶反饋增加：頂和踩的行為增加了40%
• 平均你每個(gè)用戶將從34個(gè)具相似興趣的好友那獲得200條推薦結(jié)果
• 用戶和好友的交互活躍度增加了24%
• 用戶評(píng)論增加了11%
  雖然我個(gè)人不知道這個(gè)效果是因?yàn)楫a(chǎn)品設(shè)計(jì)，還是推薦算法造成的，但是對(duì)推薦系統(tǒng)還是抱有積極的態(tài)度的。

PART 2

第二部分介紹基于物品的協(xié)同過(guò)濾算法。這個(gè)算法是目前業(yè)界引用最多的算法。
基于物品的協(xié)同過(guò)濾算法給用戶推薦那些和他們之前喜歡的物品相似的物品。ItemCF算法并不利用物品的內(nèi)容屬性計(jì)算物品直接的相似度，它主要通過(guò)分析用戶的行為記錄計(jì)算物品之間的相似度。該算法認(rèn)為，物品A和物品B具有很大的相似度是因?yàn)橄矚g物品A的用戶大都也喜歡B。算法主要分為兩步：

1. 計(jì)算物品之間的相似度；
2. 根據(jù)物品的相似度和用戶的歷史行為給用戶生成推薦列表。

定義物品的相似度可以用如下公式，其中 N(i) 是喜歡物品 i 的用戶數(shù)，如下公式表示了喜歡物品 i 的用戶中有多少的比例用戶也喜歡 j ：

Paste_Image.png

上面的公式存在一個(gè)問(wèn)題，那么就是如果物品 j 很熱門，那么 Wij 就會(huì)很大，接近1，因此為了避免馬太效應(yīng)，可以用下面的公式：

Paste_Image.png

這個(gè)公式懲罰了物品 j 的權(quán)重，因此減輕了熱門物品會(huì)和很多物品相似的可能性。
和之前的例子一樣，下圖中最左邊是輸入的用戶行為記錄，每一行代表一個(gè)用戶感興趣的物品集合。然后對(duì)于每個(gè)物品集合，我們將里面的物品兩兩加一，得到一個(gè)矩陣。最終將這些矩陣想家得到上面的 C 矩陣。其中 C[i][j] 記錄了同時(shí)喜歡物品 i 和物品 j 的用戶數(shù)。最后，將 C 矩陣歸一化可以得到物品之間的余弦相似度矩陣 W 。

Paste_Image.png

得到物品之間的相似度之后，ItemCF 通過(guò)如下公式計(jì)算用戶 u 對(duì)一個(gè)物品 j 的興趣。這里的 N(u) 表示用戶喜歡的物品的集合， S(j,k) 是和物品 j 最相似的 K 個(gè)物品的集合， Wij 是物品 j 和 i 的相似度，rui 是用戶 u 對(duì)物品 i 的興趣。（對(duì)于隱反饋數(shù)據(jù)集，如果用戶 u 對(duì)物品 i 有過(guò)行為，即可令 rui=1。）該公式的含義是，和用戶歷史上感興趣的物品越相似的物品，越有可能在用戶的推薦列表中獲得比較高的排名：

Paste_Image.png

舉一個(gè)簡(jiǎn)單的例子。用戶喜歡《C++ Primer 中文版》和《編程之美》兩本書(shū)。然后ItemCF 會(huì)為這兩本書(shū)分別找出和它們最相似的 3 本書(shū)，然后根據(jù)公式的定義計(jì)算用戶對(duì)每本書(shū)的感興趣程度。

Paste_Image.png

下表列出了MovieLens數(shù)據(jù)集上 ItemCF 算法離線實(shí)驗(yàn)的各項(xiàng)性能指標(biāo)的評(píng)測(cè)結(jié)果：

Paste_Image.png

其中我們可以得出一些結(jié)論：

• 精度（準(zhǔn)確率和召回率）。不和K成正相關(guān)或者負(fù)相關(guān)，選擇合適的K對(duì)獲得最高精度是非常重要的。
• 流行度。參數(shù)K對(duì)該算法的推薦結(jié)果流行度的影響也不是完全正相關(guān)的。
• 覆蓋率。K增加會(huì)降低系統(tǒng)的覆蓋率。

接下來(lái)需要進(jìn)行算法的優(yōu)化。有一個(gè)問(wèn)題是，是不是每個(gè)用戶對(duì)于物品相似度的貢獻(xiàn)都是一樣的呢？假設(shè)有一個(gè)用戶買了大批書(shū)，但是他買這些書(shū)都不是出自自己的興趣，可能是代購(gòu)之類；而另一個(gè)用戶雖然只買了十幾本書(shū)，但是領(lǐng)域相似，都是該用戶確實(shí)喜歡的書(shū)。

因此用戶活躍度對(duì)物品相似度也是有影響， John S.Breese 認(rèn)為活躍用戶對(duì)物品相似度的貢獻(xiàn)小于不活躍的用戶，因此提出 IUF 參數(shù)，即用戶活躍度對(duì)數(shù)的倒數(shù)的參數(shù)。修正后的公式如下：

Paste_Image.png

作者將概述算法記為 ItemCF-IUF，在下表中用離線實(shí)驗(yàn)評(píng)測(cè)這個(gè)算法，在這里參數(shù)K=10：

Paste_Image.png

如表所示，優(yōu)化后的算法整體有所提升，明顯提升覆蓋率，降低流行度。

Karypis在研究中發(fā)現(xiàn)如果將ItemCF的相似度矩陣按最大值歸一化，可以提高推薦的準(zhǔn)確率。其研究表明，如果已經(jīng)得到了物品相似度矩陣w，那么可以用胡夏公式得到歸一化之后的相似度矩陣w'：

Paste_Image.png

歸一化是指，將不同的參考系變成統(tǒng)一的參考系，便于建立標(biāo)量。假設(shè)物品分為兩類：A和B，A類之間的物品相似度為0.5，B類之間的為0.6，而A類和B類物品之間的相似度是0.2 。在這種情況下，如果一個(gè)用戶喜歡5個(gè)A類和5個(gè)B類物品，那么推薦的就都是B類物品，因?yàn)锽類物品之間的相似度大，但是歸一化之后，A類物品之間的相似度變成了1，B類物品之間的相似度也是1，如果用戶同樣喜歡5個(gè)A類5個(gè)B類，推薦列表中的A類和B類物品的數(shù)目也應(yīng)該是大致相等的。

一般熱門的類內(nèi)物品的相似度一般比較大，如果不進(jìn)行歸一化，就會(huì)推薦比較熱門的類里面的物品，而這些物品也是比較熱門的，這樣推薦的覆蓋率就會(huì)降低。

下圖對(duì)比了ItemCF算法和ItemCF-Norm算法的離線實(shí)驗(yàn)性能：

Paste_Image.png

實(shí)驗(yàn)結(jié)果可以看到，歸一化確實(shí)能提高ItemCF的性能，其中各項(xiàng)指標(biāo)都有了明顯的提高。

PART 3

這部分綜合對(duì)比下UserCF和ItemCF。主要從幾個(gè)角度來(lái)說(shuō)：

• 產(chǎn)品的類型
• 技術(shù)實(shí)現(xiàn)

從這兩個(gè)算法的推薦原理，來(lái)看，UserCF的推薦結(jié)果著重于反映和影虎興趣相似的小群體的熱點(diǎn)，而ItemCF的推薦結(jié)果著重于維系用戶的歷史興趣。換句話說(shuō)，UserCF的推薦更社會(huì)化，反映了用戶所在的小型興趣群體中的熱門程度，而ItemCF的推薦更加個(gè)性化，反映了用戶自己的興趣傳承。所以選擇算法要考慮社會(huì)性和個(gè)性。

比如新聞?lì)惖漠a(chǎn)品，用戶興趣不是很細(xì)化，絕大多數(shù)用戶都喜歡看熱門的新聞，即使是個(gè)性化，也是比較粗粒度的。因此，個(gè)性化新聞推薦更加強(qiáng)調(diào)抓住新聞熱點(diǎn)，熱門程度和時(shí)效性是個(gè)性化新聞推薦的重點(diǎn)，而個(gè)性化則相對(duì)次要。因此，UserCF更加適合。

比如電商網(wǎng)站如亞馬遜，用戶的興趣比較固定和持久。一個(gè)技術(shù)人員可能都是在購(gòu)買技術(shù)書(shū)，對(duì)書(shū)的熱門程度不敏感，甚至越來(lái)越傾向冷門的物品。因此，這些網(wǎng)站中個(gè)性化推薦的任務(wù)是幫助用戶發(fā)現(xiàn)和他研究領(lǐng)域相關(guān)的物品，用ItemCF算法較為合適。

從技術(shù)角度來(lái)考慮，UserCF需要維護(hù)一個(gè)用戶相似度的矩陣，而ItemCF需要維護(hù)一個(gè)物品相似度矩陣。如果用戶很多，那么需要維護(hù)用戶興趣相似度矩陣需要很大的空間；物品同理。不過(guò)如果結(jié)合標(biāo)簽的話，可以有很大的優(yōu)化空間。

下圖從不同角度比較了兩種算法：

Paste_Image.png

下面幾張圖用之前的離線實(shí)驗(yàn)結(jié)果對(duì)比兩種算法：

Paste_Image.png

Paste_Image.png

Paste_Image.png

結(jié)果顯示，ItemCF算法在各項(xiàng)指標(biāo)上不如UserCF，特別是覆蓋率和新穎度。

需要注意的是，離線實(shí)驗(yàn)的性能在選擇推薦算法時(shí)不起決定性作用，首先應(yīng)該滿足產(chǎn)品的需求，比如需要提供推薦解釋；其次，需要看實(shí)現(xiàn)代價(jià)，比如用戶太多就很難計(jì)算用戶相似度矩陣；最后，離線指標(biāo)和點(diǎn)擊率等在線指標(biāo)不一定成正比。

“對(duì)于稀疏數(shù)據(jù)集（例如delicious書(shū)簽，小眾群體收藏），基于物品的過(guò)濾方法通常要優(yōu)于基于用戶的過(guò)濾方法，而對(duì)于密集數(shù)據(jù)集而言，兩者的效果幾乎是一樣的”--摘自《集體智慧編程》

最后補(bǔ)充一點(diǎn)，ItemCF算法的覆蓋率和新穎度都不高，是因?yàn)閮蓚€(gè)不同領(lǐng)域的最熱門物品之間往往具有比較高的相似度，在這時(shí)候僅僅依靠用戶行為數(shù)據(jù)不能解決這個(gè)問(wèn)題。比如說(shuō)有一本書(shū)是最暢銷的書(shū)，那么無(wú)論什么用戶都會(huì)被推薦給這本書(shū)，消除馬太效應(yīng)是ItemCF需要考慮的。