基于用戶的協(xié)同過濾推薦算法原理和實(shí)現(xiàn)

在推薦系統(tǒng)眾多方法中，基于用戶的協(xié)同過濾推薦算法是最早誕生的，原理也較為簡(jiǎn)單。該算法1992年提出并用于郵件過濾系統(tǒng)，兩年后1994年被 GroupLens 用于新聞過濾。一直到2000年，該算法都是推薦系統(tǒng)領(lǐng)域最著名的算法。

本文簡(jiǎn)單介紹基于用戶的協(xié)同過濾算法思想以及原理，最后基于該算法實(shí)現(xiàn)園友的推薦，即根據(jù)你關(guān)注的人，為你推薦博客園中其他你有可能感興趣的人。

基本思想

俗話說“物以類聚、人以群分”，拿看電影這個(gè)例子來說，如果你喜歡《蝙蝠俠》、《碟中諜》、《星際穿越》、《源代碼》等電影，另外有個(gè)人也都喜歡這些電影，而且他還喜歡《鋼鐵俠》，則很有可能你也喜歡《鋼鐵俠》這部電影。

所以說，當(dāng)一個(gè)用戶 A 需要個(gè)性化推薦時(shí)，可以先找到和他興趣相似的用戶群體 G，然后把 G 喜歡的、并且 A 沒有聽說過的物品推薦給 A，這就是基于用戶的系統(tǒng)過濾算法。

原理

根據(jù)上述基本原理，我們可以將基于用戶的協(xié)同過濾推薦算法拆分為兩個(gè)步驟：

1. 找到與目標(biāo)用戶興趣相似的用戶集合

2. 找到這個(gè)集合中用戶喜歡的、并且目標(biāo)用戶沒有聽說過的物品推薦給目標(biāo)用戶

1. 發(fā)現(xiàn)興趣相似的用戶

通常用 Jaccard 公式或者余弦相似度計(jì)算兩個(gè)用戶之間的相似度。設(shè) N(u) 為用戶 u 喜歡的物品集合，N(v) 為用戶 v 喜歡的物品集合，那么 u 和 v 的相似度是多少呢：

Jaccard 公式：

余弦相似度：

假設(shè)目前共有4個(gè)用戶： A、B、C、D；共有5個(gè)物品：a、b、c、d、e。用戶與物品的關(guān)系（用戶喜歡物品）如下圖所示：

如何一下子計(jì)算所有用戶之間的相似度呢？為計(jì)算方便，通常首先需要建立“物品—用戶”的倒排表，如下圖所示：

然后對(duì)于每個(gè)物品，喜歡他的用戶，兩兩之間相同物品加1。例如喜歡物品 a 的用戶有 A 和 B，那么在矩陣中他們兩兩加1。如下圖所示：

計(jì)算用戶兩兩之間的相似度，上面的矩陣僅僅代表的是公式的分子部分。以余弦相似度為例，對(duì)上圖進(jìn)行進(jìn)一步計(jì)算：

到此，計(jì)算用戶相似度就大功告成，可以很直觀的找到與目標(biāo)用戶興趣較相似的用戶。

2. 推薦物品

首先需要從矩陣中找出與目標(biāo)用戶 u 最相似的 K 個(gè)用戶，用集合 S(u, K) 表示，將 S 中用戶喜歡的物品全部提取出來，并去除 u 已經(jīng)喜歡的物品。對(duì)于每個(gè)候選物品 i ，用戶 u 對(duì)它感興趣的程度用如下公式計(jì)算：

其中 rvi 表示用戶 v 對(duì) i 的喜歡程度，在本例中都是為 1，在一些需要用戶給予評(píng)分的推薦系統(tǒng)中，則要代入用戶評(píng)分。

舉個(gè)例子，假設(shè)我們要給 A 推薦物品，選取 K = 3 個(gè)相似用戶，相似用戶則是：B、C、D，那么他們喜歡過并且 A 沒有喜歡過的物品有：c、e，那么分別計(jì)算 p(A, c) 和 p(A, e)：

看樣子用戶 A 對(duì) c 和 e 的喜歡程度可能是一樣的，在真實(shí)的推薦系統(tǒng)中，只要按得分排序，取前幾個(gè)物品就可以了。

園友推薦

在社交網(wǎng)絡(luò)的推薦中，“物品”其實(shí)就是“人”，“喜歡一件物品”變?yōu)椤瓣P(guān)注的人”，這一節(jié)用上面的算法實(shí)現(xiàn)給我推薦 10 個(gè)園友。

1. 計(jì)算 10 名與我興趣最相似的園友

由于只是為我一個(gè)人做用戶推薦，所以沒必要建立一個(gè)龐大的用戶兩兩之間相似度的矩陣了，與我興趣相似的園友只會(huì)在這個(gè)群體產(chǎn)生：我關(guān)注的人的粉絲。除我自己之外，目前我一共關(guān)注了23名園友，這23名園友一共有22936個(gè)唯一粉絲，我對(duì)這22936個(gè)用戶逐一計(jì)算了相似度，相似度排名前10的用戶及相似度如下：

2. 計(jì)算對(duì)推薦園友的興趣度

這10名相似用戶一共推薦了25名園友，計(jì)算得到興趣度并排序：

只需要按需要取相似度排名前10名就可以了，不過看起來整個(gè)列表的推薦質(zhì)量都還不錯(cuò)！