基于物品的協(xié)同過濾算法：（item-based collaborative filtering）

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

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

基于物品的協(xié)同過濾算法主要分為兩步。

(1) 計算物品之間的相似度。

(2) 根據(jù)物品的相似度和用戶的歷史行為（即用戶之前沒有看過的視頻）給用戶生成推薦列表。?

在協(xié)同過濾中兩個物品產(chǎn)生相似度是因為它們共同被很多用戶同時喜歡，，也就是說每個用戶都可以通過他們的歷史興趣列表給物品“貢獻”相似度。（也即物品之間的相似度可以由每個用戶的興趣列表來計算）。

所用到的代碼中的k表示推薦最相似的K個列表。

隱語義模型

其實該算法最早在文本挖掘領域被提出，用于找到文本的隱含語義。

這里將對隱含語義模型在Top-N推薦中的應用進行詳細介紹，并通過實際的數(shù)據(jù)評測該模型。

隱語義模型是最近幾年推薦系統(tǒng)領域最為熱門的研究話題，它的核心思想是通過隱含特征 (latent factor)聯(lián)系用戶興趣和物品。

首先通過一個例子來理解下這個模型：

用戶A的興趣涉及偵探小說、科普圖書以及一些計算機技術書， 而用戶B的興趣比較集中在數(shù)學和機器學習方面。

那么如何給A和B推薦圖書呢？

? 對于UserCF，首先需要找到和他們看了同樣書的其他用戶（興趣相似的用戶），然后給他 們推薦那些用戶喜歡的其他書。

? 對于ItemCF，需要給他們推薦和他們已經(jīng)看的書相似的書，比如作者B看了很多關于數(shù)據(jù) 挖掘的書，可以給他推薦機器學習或者模式識別方面的書。

還有一種方法，可以對書和用戶的興趣進行分類。對于某個用戶，首先得到他的興趣分類， 然后從分類中挑選他可能喜歡的物品。?

總結(jié)一下，這個基于興趣分類的方法大概需要解決3個問題。

? 如何給物品進行分類？

? 如何確定用戶對哪些類的物品感興趣，以及感興趣的程度？?

? 對于一個給定的類，選擇哪些屬于這個類的物品推薦給用戶，以及如何確定這些物品在 一個類中的權重？?

對于第一個問題的簡單解決方案是找編輯給物品分類。以圖書為例，每本書出版時，編輯都會給書一個分類。為了給圖書分類，出版界普遍遵循中國圖書分類法①。但是，即使有很系統(tǒng)的 分類體系，編輯給出的分類仍然具有以下缺點。

? 編輯的意見不能代表各種用戶的意見。比如，對于《具體數(shù)學》應該屬于什么分類，有 人認為應該屬于數(shù)學，有些人認為應該屬于計算機。從內(nèi)容看，這本書是關于數(shù)學的， 但從用戶看，這本書的讀者大部分是做計算機出身的。編輯的分類大部分是從書的內(nèi)容出 發(fā)，而不是從書的讀者群出發(fā)。

? 編輯很難控制分類的粒度。我們知道分類是有不同粒度的，《數(shù)據(jù)挖掘?qū)д摗吩诖至６鹊?分類中可能屬于計算機技術，但在細粒度的分類中可能屬于數(shù)據(jù)挖掘。對于不同的用戶， 我們可能需要不同的粒度。比如對于一位初學者，我們粗粒度地給他做推薦就可以了， 而對于一名資深研究人員，我們就需要深入到他的很細分的領域給他做個性化推薦。

? 編輯很難給一個物品多個分類。有的書不僅屬于一個類，而是可能屬于很多的類。

? 編輯很難給出多維度的分類。我們知道，分類是可以有很多維度的，比如按照作者分類、 按照譯者分類、按照出版社分類。比如不同的用戶看《具體數(shù)學》原因可能不同，有些人是因為它是數(shù)學方面的書所以才看的，而有些人是因為它是大師Knuth的著作所以才去 看，因此在不同人的眼中這本書屬于不同的分類。

? 編輯很難決定一個物品在某一個分類中的權重。比如編輯可以很容易地決定《數(shù)據(jù)挖掘 導論》屬于數(shù)據(jù)挖掘類圖書，但這本書在這類書中的定位是什么樣的，編輯就很難給出 一個準確的數(shù)字來表示。

為了解決上面的問題，研究人員提出：為什么我們不從數(shù)據(jù)出發(fā)，自動地找到那些類，然后 進行個性化推薦？于是，隱含語義分析技術（latent variable analysis）出現(xiàn)了。隱含語義分析技術 因為采取基于用戶行為統(tǒng)計的自動聚類，較好地解決了上面提出的5個問題。

? 編輯的意見不能代表各種用戶的意見，但隱含語義分析技術的分類來自對用戶行為的統(tǒng) 計，代表了用戶對物品分類的看法。隱含語義分析技術和ItemCF在物品分類方面的思想 類似，如果兩個物品被很多用戶同時喜歡，那么這兩個物品就很有可能屬于同一個類。

? 編輯很難給一個物品多個分類，但隱含語義分析技術會計算出物品屬于每個類的權重， 因此每個物品都不是硬性地被分到某一個類中。

? 編輯很難給出多維度的分類，但隱含語義分析技術給出的每個分類都不是同一個維度的， 它是基于用戶的共同興趣計算出來的，如果用戶的共同興趣是某一個維度，那么LFM給 出的類也是相同的維度。

? 編輯很難決定一個物品在某一個分類中的權重，但隱含語義分析技術可以通過統(tǒng)計用戶 行為決定物品在每個類中的權重，如果喜歡某個類的用戶都會喜歡某個物品，那么這個 物品在這個類中的權重就可能比較高。

LFM通過如下公式計算用戶u對物品i的興趣：?

Preference( u, i)=?Pu,k*Qi,k從f=1到F求和，這里Pu,k和Qk,i是模型的參數(shù)，其中pu,k度量了用戶u的興趣和第k第k個隱類的關系，而Qk,i度量了第k個隱類和物品i之間的關系。那么，下面的問題就是如何計算這兩個參數(shù)。

使用LFM（Latent factor model）隱語義模型進行Top-N推薦

對最優(yōu)化理論或者機器學習有所了解的讀者，可能對如何計算這兩個參數(shù)都比較清楚。這兩 個參數(shù)是從數(shù)據(jù)集中計算出來的。要計算這兩個參數(shù)，需要一個訓練集，對于每個用戶u，訓練 集里都包含了用戶u喜歡的物品和不感興趣的物品，通過學習這個數(shù)據(jù)集，就可以獲得上面的模 型參數(shù)。

推薦系統(tǒng)的用戶行為分為顯性反饋和隱性反饋。LFM在顯性反饋數(shù)據(jù)（也就是評分數(shù)據(jù)）上解決評分預測問題并達到了很好的精度。不過本章主要討論的是隱性反饋數(shù)據(jù)集，這種數(shù)據(jù)集的 特點是只有正樣本（用戶喜歡什么物品），而沒有負樣本（用戶對什么物品不感興趣）。

那么，在隱性反饋數(shù)據(jù)集上應用LFM解決TopN推薦的第一個關鍵問題就是如何給每個用戶 生成負樣本。

對于這個問題，Rong Pan在文章①中進行了深入探討。他對比了如下幾種方法。

?? 對于一個用戶，用他所有沒有過行為的物品作為負樣本。?

? 對于一個用戶，從他沒有過行為的物品中均勻采樣出一些物品作為負樣本。

?? 對于一個用戶，從他沒有過行為的物品中采樣出一些物品作為負樣本，但采樣時，保證 每個用戶的正負樣本數(shù)目相當。

?? 對于一個用戶，從他沒有過行為的物品中采樣出一些物品作為負樣本，但采樣時，偏重 采樣不熱門的物品。?

對于第一種方法，它的明顯缺點是負樣本太多，正負樣本數(shù)目相差懸殊，因而計算復雜度很 高，最終結(jié)果的精度也很差。對于另外3種方法，Rong Pan在文章中表示第三種好于第二種，而 第二種好于第四種。?

后來，通過2011年的KDD Cup的Yahoo! Music推薦系統(tǒng)比賽，我們發(fā)現(xiàn)對負樣本采樣時應該 遵循以下原則。

?? 對每個用戶，要保證正負樣本的平衡（數(shù)目相似）。

?? 對每個用戶采樣負樣本時，要選取那些很熱門，而用戶卻沒有行為的物品。?

一般認為，很熱門而用戶卻沒有行為更加代表用戶對這個物品不感興趣。因為對于冷門的物 品，用戶可能是壓根沒在網(wǎng)站中發(fā)現(xiàn)這個物品，所以談不上是否感興趣。

那么，接下去的問題就是如何計算矩陣P和矩陣Q中參數(shù)值。一般做法就是最優(yōu)化損失函數(shù)來求參數(shù)。在定義損失函數(shù)之前，我們需要準備一下數(shù)據(jù)集并對興趣度的取值做一說明。

按照物品的流行度采樣出了那些熱門的、但用戶卻沒有過行為的物品。經(jīng)過采樣，可 以得到一個用戶—物品集k= {(u ,i)}? ，其中如果(u, i)是正樣本，則有 Rui =1 ，否則有 Ruir =0 。然后， 需要優(yōu)化如下的損失函數(shù)來找到最合適的參數(shù)p和q：

這里：

是用來防止過擬合的正則化項，λ可以通過實驗獲得。要最小化上面 的損失函數(shù)，可以利用一種稱為隨機梯度下降法①的算法。該算法是最優(yōu)化理論里最基礎的優(yōu)化 算法，它首先通過求參數(shù)的偏導數(shù)找到最速下降方向，然后通過迭代法不斷地優(yōu)化參數(shù)。下面介 紹優(yōu)化方法的數(shù)學推導。

然后，根據(jù)隨機梯度下降法，需要將參數(shù)沿著最速下降方向向前推進，因此可以得到如下遞推 公式：?

其中，α是學習速率，α越大，迭代下降的越快。α和λ一樣，也需要根據(jù)實際的應用場景反復實驗得到。

綜上所述，執(zhí)行LFM需要：

1.根據(jù)數(shù)據(jù)集初始化P和Q矩陣。

2.確定4個參數(shù)：分類數(shù)F，迭代次數(shù)N，學習速率α，正則化參數(shù)λ。

我們同樣通過離線實驗評測LFM的性能。首先，我們在MovieLens數(shù)據(jù)集上用LFM計算出用 戶興趣向量p和物品向量q，然后對于每個隱類找出權重最大的物品。如表2-13所示，表中展示了 4個隱類中排名最高（qik最大）的一些電影。結(jié)果表明，每一類的電影都是合理的，都代表了一 類用戶喜歡看的電影。從而說明LFM確實可以實現(xiàn)通過用戶行為將物品聚類的功能。

其次，我們通過實驗對比了LFM在TopN推薦中的性能。在LFM中，重要的參數(shù)有4個：?

? 隱特征的個數(shù)F；?

? 學習速率alpha；?

? 正則化參數(shù)lambda；?

? 負樣本/正樣本比例 ratio。?

通過實驗發(fā)現(xiàn)，ratio參數(shù)對LFM的性能影響最大。因此，固定F=100、alpha=0.02、 lambda=0.01，然后研究負樣本/正樣本比例ratio對推薦結(jié)果性能的影響。

2.6 基于圖的模型

用戶行為很容易用二分圖表示，因此很多圖的算法都可以用到推薦系統(tǒng)中。這里將重點討論 如何將用戶行為用圖表示，并利用圖的算法給用戶進行個性化推薦。

研究人員設計了很多計算圖中頂點之間相關性的方法①。這里將介紹 一種基于隨機游走的PersonalRank算法②

假設要給用戶u進行個性化推薦，可以從用戶u對應的節(jié)點vu開始在用戶物品二分圖上進行隨 機游走。游走到任何一個節(jié)點時，首先按照概率 α 決定是繼續(xù)游走，還是停止這次游走并從vu節(jié) 點開始重新游走。如果決定繼續(xù)游走，那么就從當前節(jié)點指向的節(jié)點中按照均勻分布隨機選擇一 個節(jié)點作為游走下次經(jīng)過的節(jié)點。這樣，經(jīng)過很多次隨機游走后，每個物品節(jié)點被訪問到的概率 會收斂到一個數(shù)。最終的推薦列表中物品的權重就是物品節(jié)點的訪問概率。