推薦算法之基于物品的協調過濾

基于物品的協調過濾( item-based collaborative filtering )算法是此前業界應用較多的算法。無論是亞馬遜網,還是Netflix 、Hulu 、 YouTube ,其推薦算法的基礎都是該算法。為行文方便,下文以英文簡稱ItemCF表示。本文將從其基礎算法講起,一步步進行改進并基于MovieLens 數據集給出代碼實現,帶你領略這一經典算法的美。

1.基本原理

前面我們簡單講解了一下基于用戶的協調過濾推薦(UserCF),并且給出了實現代碼。還不了解的朋友可以轉到鏈接----推薦算法之基于用戶的協調過濾。但是我們也講到該算法存在一些缺點,首先,隨著網站的用戶數目越來越大,計算用戶興趣相似度矩陣將越來越困難,其運算時間復雜度和空間復雜度的增長和用戶數的增長近似于平方關系。其次,基于用戶的協調過濾很難對推薦結果作出解釋。因此,著名的電子商務公司亞馬遜提出了另一個算法——ItemCF 。

ItemCF 給用戶推薦那些和他們之前喜歡的物品相似的物品。比如,該算法會因為你購買過《統計學習方法》而給你推薦《機器學習》。不過,ItemCF算法并不利用物品的內容屬性計算物品之間的相似度,它主要通過分析用戶的行為記錄計算物品之間的相似度。該算法認為,物品 A 和物品 B 具有很大的相似度是因為喜歡物品 A 的用戶大都也喜歡物品B 。

基于物品的協調過濾算法可以利用用戶的歷史行為給推薦結果提供推薦解釋,比如給用戶推薦《迷迭香》的解釋可以是因為用戶之前喜歡《她的睫毛》。

該算法主要分為兩步

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

購買了該商品的用戶也經常購買的其他商品這句話的定義出發,我們可以用下面的公式定義物品的相似度:

\[w_{ij}=\frac{|N(i) \bigcap N(j)|}{|N(i)|} \]

這里,分母\(|N(i)|\)是喜歡物品i的用戶數,而分子\(N(i) \bigcap N(j)\)是同時喜歡物品i和物品j的用戶數。因此,上述公式也可以理解為喜歡物品i的用戶中有多少比例的用戶也喜歡物品j。

上述公式雖然看起來很有道理,但是卻存在一個問題。如果物品 j 很熱門,很多人都喜歡,那么 \(w_{ij}\)就會很大,接近 1 。因此,該公式會造成任何物品都會和熱門的物品有很大的相似度,這對于致力于挖掘長尾信息的推薦系統來說顯然不是一個好的特性。為了避免推薦出熱門的物品,可以用下面的公式:

\[w_{ij}=\frac{|N(i) \bigcap N(j)|}{\sqrt{|N(i)||N(j)|}} \]

這個公式懲罰了物品 j 的權重,因此減輕了熱門物品會和很多物品相似的可能性。

從上面的定義可以看到,在協調過濾中兩個物品產生相似度是因為它們共同被很多用戶喜歡,也就是說每個用戶都可以通過他們的歷史興趣列表給物品貢獻相似度。這里面蘊涵著一個假設,就是每個用戶的興趣都局限在某幾個方面,因此如果兩個物品屬于一個用戶的興趣列表,那么這兩個物品可能就屬于有限的幾個領域,而如果兩個物品屬于很多用戶的興趣列表,那么它們就可能屬于同一個領域,因而有很大的相似度。

UserCF算法類似,不過這里是建立用戶-物品倒排表,然后計算物品的相似度。ItemCF通過如下公式計算用戶u對一個物品j的興趣:

\[p_{uj}=\sum_{i \in N(u) \bigcap S(j,K)}{W_{ji}r_{ui}} \]

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

2.算法改進

2.1 引入IUF參數軟性懲罰活躍用戶

在前面的篇幅中可以看到,在ItemCF中兩個物品產生相似度是因為它們共同出現在很多用戶的興趣列表中。換句話說,每個用戶的興趣列表都對物品的相似度產生貢獻。但是,在現實生活中并不是每個用戶的貢獻都相同。

于是John S. Breese在論文中提出了一個稱為 \(IUF\)(Inverse User Frequence ),即用戶活躍度對數的
倒數的參數,他也認為活躍用戶對物品相似度的貢獻應該小于不活躍的用戶,他提出應該增加 IUF
參數來修正物品相似度的計算公式:

\[w_{ij}=\frac{\sum_{u \in N(i) \bigcap N(j)}{\frac{1}{\log1 + |N(u)|}}}{\sqrt{|N(i)||N(j)|}} \]

當然,上面的公式只是對活躍用戶做了一種軟性的懲罰,但對于很多過于活躍的用戶,比如上面那位買了當當網 80% 圖書的用戶,為了避免相似度矩陣過于稠密,我們在實際計算中一般直接忽略他的興趣列表,而不將其納入到相似度計算的數據集中。

2.2 歸一化相似矩陣

Karypis在研究中發現如果將 ItemCF相似度矩陣按最大值歸一化,可以提高推薦的準確率。其研究表明,如果已經得到了物品相似度矩陣 w ,那么可以用如下公式得到歸一化之后的相似度矩陣 'w' :

\[w'_{ij} = \frac{w_{ij}}{\max_{j}w_{ij}} \]

歸一化的好處不僅僅在于增加推薦的準確度,它還可以提高推薦的覆蓋率和多樣性。一般來說,物品總是屬于很多不同的類,每一類中的物品聯系比較緊密。

舉一個例子,假設在一站中,有兩種電影——紀錄片和動畫片。那么, ItemCF 算出來的相似度一般是紀錄片和紀錄片的相似度或者動畫片和動畫片的相似度大于紀錄片和動畫片的相似度。但是紀錄片之間的相似度和動畫片之間的相似度卻不一定相同。假設物品分為兩類—— 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 類物品的數目也應該是大致相等的。從這個例子可以看出,相似度的歸一化可以提高推薦的多樣性。

那么,對于兩個不同的類,什么樣的類其類內物品之間的相似度高,什么樣的類其類內物品相似度低呢?一般來說,熱門的類其類內物品相似度一般比較大。如果不進行歸一化,就會推薦比較熱門的類里面的物品,而這些物品也是比較熱門的。因此,推薦的覆蓋率就比較低。相反,如果進行相似度的歸一化,則可以提高推薦系統的覆蓋率。

3.小結

ItemCF的推薦結果著重于維系用戶的歷史興趣,即推薦更加個性化,反映了用戶自己的興趣傳承。在圖書、電子商務和電影網站,比如亞馬遜、豆瓣、Netflix 中, ItemCF 則能極大地發揮優勢。首先,在這些網站中,用戶的興趣是比較固定和持久的。這些網站中個性化推薦的任務是幫助用戶發現和他研究領域相關的物品。

Item算法適用于物品數明顯小于用戶數的場合,長尾物品豐富,用戶個性化需求強烈的領域。該算法可實時性強,用戶有新行為,一定會導致推薦結果的實時變化。并且可以給出良好的推薦解釋。冷啟動方面,新用戶只要對一個物品產生行為,就可以給他推薦和該物品相關的其他物品。但沒有辦法在不離線更新物品相似度表的情況下將新物品推薦給用戶。

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

posted @ 2020-01-01 12:17  川南煙雨  閱讀(...)  評論(...編輯  收藏
美人江湖手游