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

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

ItemCF算法并 不利用物品的內(nèi)容屬性計(jì)算物品之間的相似度啸罢，它主要通過(guò)分析用戶的行為記錄計(jì)算物品之間的 相似度镀脂。該算法認(rèn)為簇抵，物品A和物品B具有很大的相似度是因?yàn)橄矚g物品A的用戶大都也喜歡物品 B阐斜。

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

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

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

在協(xié)同過(guò)濾中兩個(gè)物品產(chǎn)生相似度是因?yàn)樗鼈児餐缓芏嘤脩敉瑫r(shí)喜歡，带饱，也就是說(shuō)每個(gè)用戶都可以通過(guò)他們的歷史興趣列表給物品“貢獻(xiàn)”相似度毡代。（也即物品之間的相似度可以由每個(gè)用戶的興趣列表來(lái)計(jì)算）。

所用到的代碼中的k表示推薦最相似的K個(gè)列表勺疼。

隱語(yǔ)義模型

其實(shí)該算法最早在文本挖掘領(lǐng)域被提出教寂，用于找到文本的隱含語(yǔ)義。

這里將對(duì)隱含語(yǔ)義模型在Top-N推薦中的應(yīng)用進(jìn)行詳細(xì)介紹执庐，并通過(guò)實(shí)際的數(shù)據(jù)評(píng)測(cè)該模型酪耕。

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

首先通過(guò)一個(gè)例子來(lái)理解下這個(gè)模型：

用戶A的興趣涉及偵探小說(shuō)迂烁、科普?qǐng)D書以及一些計(jì)算機(jī)技術(shù)書看尼， 而用戶B的興趣比較集中在數(shù)學(xué)和機(jī)器學(xué)習(xí)方面。

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

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

? 對(duì)于ItemCF狰域，需要給他們推薦和他們已經(jīng)看的書相似的書，比如作者B看了很多關(guān)于數(shù)據(jù) 挖掘的書黄橘，可以給他推薦機(jī)器學(xué)習(xí)或者模式識(shí)別方面的書兆览。

還有一種方法，可以對(duì)書和用戶的興趣進(jìn)行分類塞关。對(duì)于某個(gè)用戶抬探，首先得到他的興趣分類， 然后從分類中挑選他可能喜歡的物品描孟。?

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

? 如何給物品進(jìn)行分類匿醒？

? 如何確定用戶對(duì)哪些類的物品感興趣场航，以及感興趣的程度？?

? 對(duì)于一個(gè)給定的類廉羔，選擇哪些屬于這個(gè)類的物品推薦給用戶溉痢，以及如何確定這些物品在 一個(gè)類中的權(quán)重？?

對(duì)于第一個(gè)問(wèn)題的簡(jiǎn)單解決方案是找編輯給物品分類憋他。以圖書為例孩饼，每本書出版時(shí)，編輯都會(huì)給書一個(gè)分類竹挡。為了給圖書分類镀娶，出版界普遍遵循中國(guó)圖書分類法①。但是揪罕，即使有很系統(tǒng)的 分類體系梯码，編輯給出的分類仍然具有以下缺點(diǎn)。

? 編輯的意見(jiàn)不能代表各種用戶的意見(jiàn)好啰。比如轩娶，對(duì)于《具體數(shù)學(xué)》應(yīng)該屬于什么分類，有 人認(rèn)為應(yīng)該屬于數(shù)學(xué)框往，有些人認(rèn)為應(yīng)該屬于計(jì)算機(jī)鳄抒。從內(nèi)容看，這本書是關(guān)于數(shù)學(xué)的， 但從用戶看许溅，這本書的讀者大部分是做計(jì)算機(jī)出身的瓤鼻。編輯的分類大部分是從書的內(nèi)容出 發(fā)，而不是從書的讀者群出發(fā)闹司。

? 編輯很難控制分類的粒度娱仔。我們知道分類是有不同粒度的，《數(shù)據(jù)挖掘?qū)д摗吩诖至６鹊?分類中可能屬于計(jì)算機(jī)技術(shù)游桩，但在細(xì)粒度的分類中可能屬于數(shù)據(jù)挖掘牲迫。對(duì)于不同的用戶， 我們可能需要不同的粒度借卧。比如對(duì)于一位初學(xué)者盹憎，我們粗粒度地給他做推薦就可以了， 而對(duì)于一名資深研究人員铐刘，我們就需要深入到他的很細(xì)分的領(lǐng)域給他做個(gè)性化推薦陪每。

? 編輯很難給一個(gè)物品多個(gè)分類。有的書不僅屬于一個(gè)類镰吵，而是可能屬于很多的類檩禾。

? 編輯很難給出多維度的分類。我們知道疤祭，分類是可以有很多維度的盼产，比如按照作者分類、 按照譯者分類勺馆、按照出版社分類戏售。比如不同的用戶看《具體數(shù)學(xué)》原因可能不同，有些人是因?yàn)樗菙?shù)學(xué)方面的書所以才看的草穆，而有些人是因?yàn)樗谴髱烱nuth的著作所以才去 看灌灾，因此在不同人的眼中這本書屬于不同的分類。

? 編輯很難決定一個(gè)物品在某一個(gè)分類中的權(quán)重悲柱。比如編輯可以很容易地決定《數(shù)據(jù)挖掘 導(dǎo)論》屬于數(shù)據(jù)挖掘類圖書锋喜，但這本書在這類書中的定位是什么樣的，編輯就很難給出 一個(gè)準(zhǔn)確的數(shù)字來(lái)表示豌鸡。

為了解決上面的問(wèn)題跑芳，研究人員提出：為什么我們不從數(shù)據(jù)出發(fā)，自動(dòng)地找到那些類直颅，然后 進(jìn)行個(gè)性化推薦？于是怀樟，隱含語(yǔ)義分析技術(shù)（latent variable analysis）出現(xiàn)了功偿。隱含語(yǔ)義分析技術(shù) 因?yàn)椴扇』谟脩粜袨榻y(tǒng)計(jì)的自動(dòng)聚類，較好地解決了上面提出的5個(gè)問(wèn)題。

? 編輯的意見(jiàn)不能代表各種用戶的意見(jiàn)械荷，但隱含語(yǔ)義分析技術(shù)的分類來(lái)自對(duì)用戶行為的統(tǒng) 計(jì)共耍，代表了用戶對(duì)物品分類的看法。隱含語(yǔ)義分析技術(shù)和ItemCF在物品分類方面的思想 類似吨瞎，如果兩個(gè)物品被很多用戶同時(shí)喜歡痹兜，那么這兩個(gè)物品就很有可能屬于同一個(gè)類。

? 編輯很難給一個(gè)物品多個(gè)分類颤诀，但隱含語(yǔ)義分析技術(shù)會(huì)計(jì)算出物品屬于每個(gè)類的權(quán)重字旭， 因此每個(gè)物品都不是硬性地被分到某一個(gè)類中。

? 編輯很難給出多維度的分類崖叫，但隱含語(yǔ)義分析技術(shù)給出的每個(gè)分類都不是同一個(gè)維度的遗淳， 它是基于用戶的共同興趣計(jì)算出來(lái)的，如果用戶的共同興趣是某一個(gè)維度心傀，那么LFM給 出的類也是相同的維度屈暗。

? 編輯很難決定一個(gè)物品在某一個(gè)分類中的權(quán)重，但隱含語(yǔ)義分析技術(shù)可以通過(guò)統(tǒng)計(jì)用戶 行為決定物品在每個(gè)類中的權(quán)重脂男，如果喜歡某個(gè)類的用戶都會(huì)喜歡某個(gè)物品养叛，那么這個(gè) 物品在這個(gè)類中的權(quán)重就可能比較高。

LFM通過(guò)如下公式計(jì)算用戶u對(duì)物品i的興趣：?

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

使用LFM（Latent factor model）隱語(yǔ)義模型進(jìn)行Top-N推薦

對(duì)最優(yōu)化理論或者機(jī)器學(xué)習(xí)有所了解的讀者掉缺，可能對(duì)如何計(jì)算這兩個(gè)參數(shù)都比較清楚卜录。這兩 個(gè)參數(shù)是從數(shù)據(jù)集中計(jì)算出來(lái)的。要計(jì)算這兩個(gè)參數(shù)眶明，需要一個(gè)訓(xùn)練集艰毒，對(duì)于每個(gè)用戶u，訓(xùn)練 集里都包含了用戶u喜歡的物品和不感興趣的物品搜囱，通過(guò)學(xué)習(xí)這個(gè)數(shù)據(jù)集丑瞧，就可以獲得上面的模 型參數(shù)。

推薦系統(tǒng)的用戶行為分為顯性反饋和隱性反饋蜀肘。LFM在顯性反饋數(shù)據(jù)（也就是評(píng)分?jǐn)?shù)據(jù)）上解決評(píng)分預(yù)測(cè)問(wèn)題并達(dá)到了很好的精度绊汹。不過(guò)本章主要討論的是隱性反饋數(shù)據(jù)集，這種數(shù)據(jù)集的 特點(diǎn)是只有正樣本（用戶喜歡什么物品）扮宠，而沒(méi)有負(fù)樣本（用戶對(duì)什么物品不感興趣）西乖。

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

對(duì)于這個(gè)問(wèn)題获雕，Rong Pan在文章①中進(jìn)行了深入探討薄腻。他對(duì)比了如下幾種方法。

?? 對(duì)于一個(gè)用戶届案，用他所有沒(méi)有過(guò)行為的物品作為負(fù)樣本庵楷。?

? 對(duì)于一個(gè)用戶，從他沒(méi)有過(guò)行為的物品中均勻采樣出一些物品作為負(fù)樣本楣颠。

?? 對(duì)于一個(gè)用戶尽纽，從他沒(méi)有過(guò)行為的物品中采樣出一些物品作為負(fù)樣本，但采樣時(shí)球碉，保證 每個(gè)用戶的正負(fù)樣本數(shù)目相當(dāng)蜓斧。

?? 對(duì)于一個(gè)用戶肮柜，從他沒(méi)有過(guò)行為的物品中采樣出一些物品作為負(fù)樣本汰扭，但采樣時(shí)歇拆，偏重 采樣不熱門的物品等限。?

對(duì)于第一種方法聘惦，它的明顯缺點(diǎn)是負(fù)樣本太多源葫，正負(fù)樣本數(shù)目相差懸殊检疫，因而計(jì)算復(fù)雜度很 高九杂，最終結(jié)果的精度也很差施禾。對(duì)于另外3種方法脚线，Rong Pan在文章中表示第三種好于第二種，而 第二種好于第四種弥搞。?

后來(lái)邮绿，通過(guò)2011年的KDD Cup的Yahoo! Music推薦系統(tǒng)比賽，我們發(fā)現(xiàn)對(duì)負(fù)樣本采樣時(shí)應(yīng)該 遵循以下原則攀例。

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

?? 對(duì)每個(gè)用戶采樣負(fù)樣本時(shí)粤铭，要選取那些很熱門挖胃，而用戶卻沒(méi)有行為的物品。?

一般認(rèn)為梆惯，很熱門而用戶卻沒(méi)有行為更加代表用戶對(duì)這個(gè)物品不感興趣酱鸭。因?yàn)閷?duì)于冷門的物 品，用戶可能是壓根沒(méi)在網(wǎng)站中發(fā)現(xiàn)這個(gè)物品垛吗，所以談不上是否感興趣凹髓。

那么，接下去的問(wèn)題就是如何計(jì)算矩陣P和矩陣Q中參數(shù)值怯屉。一般做法就是最優(yōu)化損失函數(shù)來(lái)求參數(shù)扁誓。在定義損失函數(shù)之前防泵，我們需要準(zhǔn)備一下數(shù)據(jù)集并對(duì)興趣度的取值做一說(shuō)明。

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

這里：

是用來(lái)防止過(guò)擬合的正則化項(xiàng)拂到，λ可以通過(guò)實(shí)驗(yàn)獲得痪署。要最小化上面 的損失函數(shù)，可以利用一種稱為隨機(jī)梯度下降法①的算法兄旬。該算法是最優(yōu)化理論里最基礎(chǔ)的優(yōu)化 算法狼犯，它首先通過(guò)求參數(shù)的偏導(dǎo)數(shù)找到最速下降方向，然后通過(guò)迭代法不斷地優(yōu)化參數(shù)领铐。下面介 紹優(yōu)化方法的數(shù)學(xué)推導(dǎo)悯森。

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

其中，α是學(xué)習(xí)速率音诈，α越大幻碱，迭代下降的越快。α和λ一樣细溅，也需要根據(jù)實(shí)際的應(yīng)用場(chǎng)景反復(fù)實(shí)驗(yàn)得到褥傍。

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

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

2.確定4個(gè)參數(shù)：分類數(shù)F摔桦，迭代次數(shù)N，學(xué)習(xí)速率α承疲，正則化參數(shù)λ邻耕。

我們同樣通過(guò)離線實(shí)驗(yàn)評(píng)測(cè)LFM的性能。首先燕鸽，我們?cè)贛ovieLens數(shù)據(jù)集上用LFM計(jì)算出用 戶興趣向量p和物品向量q兄世，然后對(duì)于每個(gè)隱類找出權(quán)重最大的物品。如表2-13所示啊研，表中展示了 4個(gè)隱類中排名最高（qik最大）的一些電影御滩。結(jié)果表明鸥拧，每一類的電影都是合理的，都代表了一 類用戶喜歡看的電影削解。從而說(shuō)明LFM確實(shí)可以實(shí)現(xiàn)通過(guò)用戶行為將物品聚類的功能富弦。

其次，我們通過(guò)實(shí)驗(yàn)對(duì)比了LFM在TopN推薦中的性能氛驮。在LFM中腕柜，重要的參數(shù)有4個(gè)：?

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

? 學(xué)習(xí)速率alpha矫废；?

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

? 負(fù)樣本/正樣本比例 ratio。?

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)蓖扑，ratio參數(shù)對(duì)LFM的性能影響最大唉铜。因此，固定F=100律杠、alpha=0.02潭流、 lambda=0.01，然后研究負(fù)樣本/正樣本比例ratio對(duì)推薦結(jié)果性能的影響俩功。

2.6 基于圖的模型

用戶行為很容易用二分圖表示幻枉，因此很多圖的算法都可以用到推薦系統(tǒng)中。這里將重點(diǎn)討論 如何將用戶行為用圖表示诡蜓，并利用圖的算法給用戶進(jìn)行個(gè)性化推薦熬甫。

研究人員設(shè)計(jì)了很多計(jì)算圖中頂點(diǎn)之間相關(guān)性的方法①。這里將介紹 一種基于隨機(jī)游走的PersonalRank算法②

假設(shè)要給用戶u進(jìn)行個(gè)性化推薦蔓罚，可以從用戶u對(duì)應(yīng)的節(jié)點(diǎn)vu開(kāi)始在用戶物品二分圖上進(jìn)行隨 機(jī)游走椿肩。游走到任何一個(gè)節(jié)點(diǎn)時(shí)，首先按照概率 α 決定是繼續(xù)游走豺谈，還是停止這次游走并從vu節(jié) 點(diǎn)開(kāi)始重新游走郑象。如果決定繼續(xù)游走，那么就從當(dāng)前節(jié)點(diǎn)指向的節(jié)點(diǎn)中按照均勻分布隨機(jī)選擇一 個(gè)節(jié)點(diǎn)作為游走下次經(jīng)過(guò)的節(jié)點(diǎn)茬末。這樣厂榛，經(jīng)過(guò)很多次隨機(jī)游走后，每個(gè)物品節(jié)點(diǎn)被訪問(wèn)到的概率 會(huì)收斂到一個(gè)數(shù)丽惭。最終的推薦列表中物品的權(quán)重就是物品節(jié)點(diǎn)的訪問(wèn)概率击奶。