推薦算法之基于用戶的協調過濾

基于用戶的的協調過濾算法是推薦統統最古老的算法,簡稱UserCF。該算法的誕生一定程度上標志著推薦系統的誕生。本文將對UserCF算法原理進行講解,并且基于Movielens數據集給出實現代碼供大家交流學習。

基本原理

在一個在線個性化推薦系統中,當一個用戶A需要個性化推薦時,先找到和他相似興趣的其他用戶,然后把那些用戶喜歡的而用戶A沒有聽說過的物品推薦給用戶A。這種方法就稱為基于用戶的協調過濾算法。該算法主要包括兩個步驟:

  1. 找到和目標用戶興趣相似的用戶集合
  2. 找到這個集合中用戶喜歡的且目標用戶沒有聽說過的物品推薦給目標用戶。

步驟1的關鍵為計算兩個用戶之間的興趣相似度。那么如何度量兩個用戶的興趣相似度呢,該算法主要利用用戶行為的相似度計算興趣的相似度。給定用戶\(u\)和用戶\(v\),令\(N(u)\)表示用戶\(u\)曾經有過正反饋的物品集合,\(N(v)\)表示用戶\(v\)曾經有過正反饋的物品集合。那么,可通過如下的\(Jaccard\)公式簡單計算興趣相似度:

\[W_{uv} = \frac{|N(u)\bigcap N(V)|}{|N(u)\bigcup|N(v)} \]

或者通過余弦相似度:

\[w_{uv} = \frac{|N(u) \bigcap N(v)|}{\sqrt{|N(u)|| N(v)|}} \]

下面通過表1.1的用戶行為記錄為例,舉例說明UserCF計算用戶興趣相似度的例子。在該例中,用戶A對物品{a, b, d}有過行為,用戶B對物品{a,c}有過行為,利用余弦相似度公式計算用戶A和用戶B的興趣相似度為:

\[W_{AB} = \frac{|{a,b,d} \bigcap {a,c}|}{\sqrt{|{a,b,d}|| {a,c}|}}=\frac{1}{\sqrt{6}} \]

表 1.1

user item
A a,b,d
B a,c
C b,c
D c,d,e

由于對兩兩用戶都計算余弦相似度,時間復雜度太高。可以在\(N(u)\bigcap N(v)=0\)時不計算余弦相似度。為此,可以首先建立物品到用戶的倒排表,對于每個物品都保存對該物品產生過行為的用戶列表。令稀疏矩陣\(C[u][v]=|N(u) \bigcap N(v)|\)。假設用戶u和用戶v同時屬于倒排表中K個物品對應的用戶列表,就有\(C[U][V]=K\)。從而,可以掃描倒排表每個物品對應的用戶列表,將用戶列表中的兩兩用戶對應的\(C[u][v]\)加1,最終得到所有用戶之間不為零\(C[u][v]\)。

得到用戶之間的興趣相似度后,UserCF算法會給用戶推薦和他興趣最相似的K個用戶喜歡的物品。如下公式度量了UserCF算法中用戶u對物品i的感興趣程度:

\[p(u, i)=\sum_{v\in{S(u,K) \bigcap N(i)}}{w_{uv}r_{vi}} \]

其中,\(S(u,K)\)包含和用戶u興趣最接近的K個用戶,N(i)是對物品i有過行為的用戶集合,\(w_{uv}\)是用戶u和用戶v的興趣相似度,\(r_{vi}\)代表用戶v對物品i的興趣,對于單一行為的隱反饋數據,所有的\(r_{vi}=1\)。

算法改進

使用\(Jaccard\)公式(或者余弦相似度)計算用戶興趣度,會帶來一定的缺陷??紤]這種情況,以圖書為例,如果兩個用戶都曾買過《新華字典》,這絲毫不能說明他們興趣相似,因為絕大多數中國人小時候都買過。但是如果兩個用戶都買過《數據挖掘導論》,那可以認為他們的興趣比較相似,因為只有研究數據挖掘的人才會買這本書。換句話說,兩個用戶對冷門物品采取過同樣的行為更能說明他們興趣的相似度。因此,John S. Breese在論文中提出了如下公式,根據用戶行為計算用戶的興趣相似度:

\[W_{uv} = \frac{\sum_{i \in {N(u) \bigcap N(v)}}{\frac{1}{\log1+|N(i)|}}} {\sqrt{|N(u)||N(v)|}} \]

可以看到,該公式通過\(\frac{1}{\log1+|N(i)|}\)懲罰用戶u和用戶v共同興趣列表中熱門物品對他們相似度的影響。

作者基于MovieLens數據集(顯性反饋數據集)實現了該算法,地址詳見:UserCF算法實現

小結

UserCF是推薦系統領域較為古老的算法,1992 年就已經在電子郵件的個性化推薦系統Tapestry 中得到了應用,1994 年被GroupLens用來實現新聞的個性化推薦,后來被著名的文章分享網站Digg用來給用戶推薦個性化的網絡文章。UserCF 給用戶推薦那些和他有共同興趣愛好的用戶喜歡的物品,從算法的原理可以看出UserCF的推薦結果著重于反映和用戶興趣相似的小群體的熱點,換句話說, UserCF的推薦更社會化,反映了用戶所在的小型興趣群體中物品的熱門程度。

UserCF適用于用戶較少的場景,時效性較強且用戶個性興趣不太明顯的領域。當用戶有新行為時,它不一定能夠實時更新用戶的推薦結果。并且無法給出令用戶信服的推薦解釋。

(PS:(???)覺得作者文章還不錯的話,請點一下推薦哦!萬分感謝?。?/p>

posted @ 2019-12-29 16:21  川南煙雨  閱讀(...)  評論(...編輯  收藏
美人江湖手游