推薦系統(tǒng)(1)-概述

為了使推薦結(jié)果符合用戶口味，我們需要對(duì)用戶有深入的了解。用戶留下的文字和行為可以解釋。

2. 基于用戶行為數(shù)據(jù)的最典型應(yīng)用是各種列表。這些列表是基于簡(jiǎn)單的用戶行為統(tǒng)計(jì)數(shù)據(jù)，個(gè)性化的推薦算法是通過深入分析用戶行為來帶來更好的體驗(yàn)。

3. 用戶行為不是隨機(jī)的，包含了許多模式。例如，通過對(duì)用戶購物車的分析，電子商務(wù)平臺(tái)發(fā)現(xiàn)了 購買A用戶購買商品B同時(shí)，在用戶瀏覽商品的同時(shí)A商品直接展示購買A 用戶購買的其他商品最著名的例子是啤酒和尿布的故事。

當(dāng)當(dāng)網(wǎng)在用戶瀏覽《數(shù)據(jù)挖掘?qū)д摗窌r(shí)，向用戶推薦購買本產(chǎn)品的客戶 還買了的書

4. 基于用戶行為分析的推薦算法稱為協(xié)同過濾算法。顧名思義，協(xié)同過濾是指用戶可以通過不斷與網(wǎng)站互動(dòng)，不斷過濾自己不感興趣的物品，從而越來越滿足自己的需求。

5. 網(wǎng)站上用戶行為數(shù)據(jù)最簡(jiǎn)單的存在形式是日志。網(wǎng)站在運(yùn)行過程中產(chǎn)生了大量的原始日志 (raw log)，并將其存儲(chǔ)在文件系統(tǒng)中。許多互聯(lián)網(wǎng)業(yè)務(wù)根據(jù)用戶行為將各種原始日志匯總成會(huì)話日志(session log)，每次會(huì)話都表示用戶行為和相應(yīng)的服務(wù)。這些日志記錄了用戶的各種行為。

6. 個(gè)性化推薦系統(tǒng)中的用戶行為一般分為兩種-顯性反饋行為(explicit feedback)和隱性反饋 行為(implicit feedback)。顯性反饋包括用戶明確表達(dá)對(duì)項(xiàng)目偏好的行為。

提供給用戶打分或贊/踩的功能，收集用戶喜好

7. 一個(gè)有趣的例子：YouTube最早是用5分評(píng)分系統(tǒng) 收集顯性反饋的，但后來他們的研究人員統(tǒng)計(jì)了不同評(píng)分的評(píng)分?jǐn)?shù)1，結(jié)果發(fā)現(xiàn)，用戶最常用的評(píng)分是5分，其次是1分，其他的分?jǐn)?shù)很少有用戶打。YouTube用戶主要關(guān)注視頻，所以他們只有在特別不滿意或特別滿意時(shí)才會(huì)得分，所以二級(jí)評(píng)分系統(tǒng)就足夠了。但如果它是一個(gè)評(píng)論網(wǎng)站，用戶主要關(guān)注評(píng)論，那么多級(jí)評(píng)分系統(tǒng)是必要的。

8. 與顯性反饋相對(duì)應(yīng)的是隱性反饋。隱性反饋是指無法明確反映用戶偏好的行為。最具代表性的隱性反饋行為是頁面瀏覽行為。

網(wǎng)站顯性反饋數(shù)據(jù)和隱性反饋數(shù)據(jù)的例子

互聯(lián)網(wǎng)上有許多用戶行為，如瀏覽網(wǎng)頁、購買商品、評(píng)論、評(píng)分等。很難用一種統(tǒng)一的 來表達(dá)所有這些行為。下表給出了一種表達(dá)方式，將用戶行為表達(dá)為六部分，即用戶和行為對(duì)象、行為類型、上下文、內(nèi)容和權(quán)重。

統(tǒng)一表達(dá)用戶行為

9. 一般來說，不同的數(shù)據(jù)集包含不同的行為：

無上下文信息的隱性反饋數(shù)據(jù)集 每個(gè)行為記錄僅包括用戶ID和物品ID。顯性反饋數(shù)據(jù)集 每個(gè)記錄包含用戶ID、物品ID以及用戶對(duì)項(xiàng)目的評(píng)分。每個(gè)記錄都包括用戶對(duì)上下文信息的隱藏反饋數(shù)據(jù)集 ID、物品ID時(shí)間戳用戶對(duì)物品的行為。上下文信息的顯性反饋數(shù)據(jù)集 ID、物品ID、用戶對(duì)物品進(jìn)行評(píng)分和評(píng)分的時(shí)間戳。

10. 用戶活動(dòng)和商品流行的分布

互聯(lián)網(wǎng)上的許多數(shù)據(jù)分布都被稱為Power Law在互聯(lián)網(wǎng)領(lǐng)域，這種分布也被稱為長(zhǎng)尾分布。

橫坐標(biāo)是物品的流行程度K，縱坐標(biāo)很受歡迎K的物品的總數(shù)。

11. 用戶活動(dòng)與商品流行的關(guān)系

新用戶傾向于瀏覽熱門物品，因?yàn)樗麄儾皇煜ぞW(wǎng)站，只能點(diǎn)擊主頁上的熱門物品，而老用戶會(huì)逐漸開始瀏覽熱門物品。

圖中曲線呈明顯下降趨勢(shì)，表明用戶越活躍，越傾向于瀏覽不受歡迎的物品。

12. 基于用戶行為數(shù)據(jù)設(shè)計(jì)的推薦算法通常被稱為協(xié)同過濾算法。學(xué)術(shù)界深入研究了協(xié)同過濾算法 ，并提出了許多方法，如基于鄰域的方法(neighborhood-based)、隱語義模型 (latent factor model)、基于圖的隨機(jī)游走算法(random walk on graph)等等。在這些方法中，最著名、最廣泛應(yīng)用于行業(yè)的算法是基于鄰域的方法。

13. 推薦算法評(píng)價(jià)指標(biāo)：

對(duì)用戶u推薦N物品(記為R(u))，令用戶u在測(cè)試集上喜歡的物品 ** 為T(u)，然后通過 過準(zhǔn)確率/召回率來評(píng)估推薦算法的精度:

   召回率：

精度：

覆蓋率: (覆蓋率反映了發(fā)掘長(zhǎng)尾的能力。覆蓋率越高，推薦算法越能向用戶推薦長(zhǎng)尾項(xiàng)目。

例:一個(gè)數(shù)據(jù)庫有500個(gè)文檔，其中50個(gè)符合定義。系統(tǒng)檢索到75個(gè)文檔，但實(shí)際上只有45個(gè)符合定義。在500個(gè)文檔中，系統(tǒng)可以檢索到460個(gè)文檔。

召回率：Recall = 45/50 = 90%

精度：Precision = 45/75 = 60%

覆蓋率：Coverage = 460 / 500 = 92%

14. 基于鄰域的方法主要包括兩種算法：

基于用戶的協(xié)同過濾算法 向用戶推薦其他用戶喜歡的物品，這些物品與他的興趣相似。基于項(xiàng)目的協(xié)同過濾算法 向用戶推薦類似于他以前喜歡的項(xiàng)目的項(xiàng)目。

15. 基于用戶的協(xié)同過濾算法（UserCF）

當(dāng)一個(gè)用戶A當(dāng)你需要個(gè)性化的推薦時(shí)，你可以首先找到其他與他有類似興趣的用戶，然后找到用戶喜歡的用戶A推薦沒聽說過的物品A。

協(xié)同過濾算法主要包括兩個(gè)步驟：①找到與目標(biāo)用戶興趣相似的用戶 ** 。②找到這個(gè) ** 用戶喜歡的，目標(biāo)用戶沒聽說過的推薦給目標(biāo)用戶。

給定用戶u和用戶v，令N(u)表示用戶u曾經(jīng)有過正反饋的物品 ** ，令N(v) 為用戶v曾經(jīng)有過正反饋的物品 ** 。

通過Jaccard簡(jiǎn)單計(jì)算公式u和v興趣相似性：

或計(jì)算余弦相似度：

案例：

例如用戶行為記錄

用戶A和用戶B的相似度為：

用戶A和用戶C相似度如下：

用戶A和用戶D相似度如下：

可見，用戶A和用戶D相似度最高。使用上述算法可以給用戶A推薦A對(duì)物品c、e沒有行為，所以你可以向用戶推薦這兩個(gè)項(xiàng)目A。

在獲得用戶之間的興趣相似性后，UserCF算 ** 向用戶推薦最類似他興趣的產(chǎn)品K 用戶喜歡的物品。測(cè)量了以下公式UserCF算法中用戶u對(duì)物品i感興趣：

   

其中，S(u,K)包含和用戶u最接近興趣的K個(gè)用戶，N(i)是對(duì)物品i有過行為的用戶 ** ， 是用戶u和用戶v 代表用戶的興趣相似性v對(duì)物品i的興趣，因?yàn)槭褂玫氖菃我恍袨榈碾[反饋數(shù) 據(jù)，所以所有的 = 1。

選取K=3，用戶A對(duì)物品c、e沒有行為，所以你可以向用戶推薦這兩個(gè)項(xiàng)目A。根據(jù)UserCF算法，用戶A對(duì)物品c、e興趣是：

p(A,c) = = 0.7416

p(A,e) = = 0.7416

注意，參數(shù)K是UserCF其調(diào)整對(duì)推薦算法的各種指標(biāo)都有一定的影響。

以MovieLens可以看出，推薦系統(tǒng)的精度指標(biāo)(精度和召回率)與參數(shù)不符K成線性關(guān)系MovieLens數(shù)據(jù)集中，選擇K=80精度和召回率都比較高。因此，選擇合適的K對(duì)于獲得高推薦系統(tǒng)的精度更為重要。人氣 K越大則UserCF推薦結(jié)果越受歡迎。這是因?yàn)镵決定了UserCF在向您推薦時(shí)，請(qǐng)參考其他與您感興趣相似的用戶的興趣。K越大，參考 的人越多，結(jié)果就越接近全球的熱門物品。在三個(gè)數(shù)據(jù)集中，可以看到覆蓋率 K越大則UserCF推薦結(jié)果的覆蓋率越低。由于流行程度的增加，覆蓋率的降低，UserCF越來越傾向于推薦熱門物品，從而對(duì)長(zhǎng)尾物品的推薦越來越少，導(dǎo)致覆蓋率下降。

16. 用戶相似度計(jì)算的改進(jìn)

首先，以圖書為例。如果兩個(gè)用戶都購買了新華字典，這并不意味著他們有相似的興趣，因?yàn)榻^大多數(shù)中國(guó)人小時(shí)候都購買了新華字典。但是，如果兩個(gè)用戶都購買了數(shù)據(jù)挖掘?qū)д摚?可以認(rèn)為他們的興趣相似，因?yàn)橹挥醒芯繑?shù)據(jù)挖掘的人才會(huì)購買這本書。換句話說，兩個(gè)用戶對(duì)不受歡迎的物品采取了相同的行為，這表明了他們興趣的相似性。

因此，John S. Breese在論文1中提出 以下公式（UserCF-IIF），用戶興趣相似性按用戶行為計(jì)算：

UserCF和UserCF-IIF各種性能對(duì)比

UserCF-IIF在各項(xiàng)性能上略優(yōu)于UserCF。這表明，在計(jì)算用戶興趣相似性時(shí)，考慮 商品的流行程度確實(shí)有助于提高推薦結(jié)果的質(zhì)量。

基于用戶協(xié)同過濾算法的缺點(diǎn)：① 隨著網(wǎng)站用戶數(shù)量的增加，計(jì)算用戶興趣相似性矩陣將變得越來越困難，其計(jì)算時(shí)間復(fù)雜性和空間復(fù)雜性的增加與用戶數(shù)量的增加相似。② 基于用戶的協(xié)同過濾很難解釋推薦結(jié)果。

17. 基于物體的協(xié)同過濾算法（ItemCF）

基于對(duì)象的協(xié)同過濾(item-based collaborative filtering)算法是目前業(yè)界應(yīng)用最廣泛的算法。無論是亞馬遜，還是亞馬遜，Netflix、Hulu、YouTube，其推薦算法的基礎(chǔ)都是該算法。基于對(duì)象的協(xié)同過濾算法可以利用用戶的歷史行為給推薦結(jié)果提供推薦解釋，Hulu推薦使用個(gè)性化視頻 ItemCF為每個(gè)推薦結(jié)果提供推薦解釋，用于解釋的視頻是用戶之前觀看或收集的視頻。

Hulu個(gè)性化視頻推薦

協(xié)同過濾算法主要分為兩個(gè)步驟：①計(jì)算物體之間的相似性。②根據(jù)物品的相似性和用戶的歷史行為，向用戶生成推薦列表。

用以下公式定義項(xiàng)目的相似性：

分母|N(i)|是喜歡物品i而分子 N(i) N(j) 同時(shí)喜歡物品i和物品j用戶數(shù)。因此，上述公式可以理解為喜歡的物品i有多少用戶也喜歡商品？j。

雖然上面的公式看起來很有道理，但是有一個(gè)問題。假如物品j很受歡迎，很多人喜歡，所以 會(huì)很大，接近1。因此，該公式將導(dǎo)致任何項(xiàng)目與流行項(xiàng)目非常相似，這顯然不是致力于挖掘長(zhǎng)尾信息的推薦系統(tǒng)的好特點(diǎn)。

為避免推薦流行物品，可使用以下公式：

該公式懲罰了物品j因此，它減輕了流行物品與許多物品相似的可能性。在協(xié)同過濾中，這兩個(gè)項(xiàng)目之所以相似，是因?yàn)樗鼈児餐艿皆S多用戶的喜愛，也就是說，每個(gè)用戶都可以通過他們的歷史興趣列表貢獻(xiàn)項(xiàng)目的相似性。

下圖最左邊是輸入用戶行為記錄，每行代表用戶感興趣的物品 ** 。然后，對(duì)于每一件物品 ** ，我們把里面的物體加成兩兩加一，得到一個(gè)矩陣。最后，將這些矩陣加到上面C矩陣。其中C[i][j]記錄同時(shí)喜歡的物品i 和物品j用戶數(shù)將C矩陣歸一化可以獲得物體之間的余弦相似度矩陣W。

   獲得物品之間的相似性后，ItemCF用戶通過以下公式計(jì)算u對(duì)一個(gè)物品j的興趣:

這里N(u) 是用戶喜歡的物品** ，S(j,K)是和物品j最相似的K個(gè)物品的 ** ， 是物品j和i 相似性， 是用戶u對(duì)物品i對(duì)隱反饋數(shù)據(jù)集的興趣u對(duì)物品i有過行為，就可以下令了=1。)該公式的含義是，與用戶歷史上感興趣的物品越相似，在用戶推薦列表中排名越高。

示例：

下圖是一個(gè)基于項(xiàng)目推薦的簡(jiǎn)單例子。用戶喜歡這個(gè)例子《C Primer中文版和編程之美。ItemCF將為這兩本書找出最相似的三本書，然后根據(jù)公式的定義計(jì)算用戶對(duì)每本書的興趣。ItemCF因?yàn)檫@本書和《C Primer中文版相似，相似度為0.4，而且這本書和《編程之美》差不多，相似性是0.5。考慮到用戶是對(duì)的《C Primer中文版的興趣是1.3，對(duì)編程之美的興趣是0.9，那么用戶對(duì)算法導(dǎo)論的興趣就是1.3 × 0.4 0.9×0.5 = 0.97。

從這個(gè)例子可以看出，ItemCF一個(gè)優(yōu)點(diǎn)是可以提供推薦解釋，即用戶歷史上喜歡的 項(xiàng)目來解釋當(dāng)前的推薦結(jié)果。

MovieLens數(shù)據(jù)集中ItemCF結(jié)果精度(精度和召回率) ItemCF推薦結(jié)果的精度也不和諧K正相關(guān)或負(fù)相關(guān)，所以選擇合適的K獲得最高精度是非常重要的。 流行度 和UserCF不同，參數(shù)K對(duì)ItemCF推薦結(jié)果流行度的影響也不是完全正相關(guān)的。 隨著K的增加，結(jié)果流行度會(huì)逐漸提高，但當(dāng)K增加到一定程度，流行度就不會(huì)再有明顯變化。覆蓋率 K增加會(huì)降低系統(tǒng)的覆蓋率。

18. 用戶活躍度對(duì)物品相似度的影響

在協(xié)同過濾中兩個(gè)物品產(chǎn)生相似度是因?yàn)樗鼈児餐霈F(xiàn)在很多用戶 的興趣列表中。換句話說，每個(gè)用戶的興趣列表都對(duì)物品的相似度產(chǎn)生貢獻(xiàn)。

那么，是不是每個(gè)用戶的貢獻(xiàn)都相同呢?

假設(shè)有這么一個(gè)用戶，他是開書店的，并且買了當(dāng)當(dāng)網(wǎng)上80%的書準(zhǔn)備用來自己賣。那么， 他的購物車?yán)锇?dāng)當(dāng)網(wǎng)80%的書。假設(shè)當(dāng)當(dāng)網(wǎng)有100萬本書，也就是說他買了80萬本。從前面 對(duì)ItemCF的討論可以看到，這意味著因?yàn)榇嬖谶@么一個(gè)用戶，有80萬本書兩兩之間就產(chǎn)生了相似 度，也就是說，內(nèi)存里即將誕生一個(gè)80萬乘80萬的稠密矩陣。

另外可以看到，這個(gè)用戶雖然活躍，但是買這些書并非都是出于自身的興趣，而且這些書覆 蓋了當(dāng)當(dāng)網(wǎng)圖書的很多領(lǐng)域，所以這個(gè)用戶對(duì)于他所購買書的兩兩相似度的貢獻(xiàn)應(yīng)該遠(yuǎn)遠(yuǎn)小于一 個(gè)只買了十幾本自己喜歡的書的文學(xué)青年。

為了解決這個(gè)問題，John S. Breese一個(gè)稱為IUF(Inverse User Frequence)，即用戶活躍度對(duì)數(shù)的倒數(shù)的參數(shù)，他認(rèn)為活躍用戶對(duì)物品相似度的貢獻(xiàn)應(yīng)該小于不活躍的用戶，他提出應(yīng)該增加IUF 參數(shù)來修正物品相似度的計(jì)算公式（ItemCF-IUF）:

上面的公式只是對(duì)活躍用戶做了一種軟性的懲罰，但對(duì)于很多過于活躍的用戶，比如上面那位買了當(dāng)當(dāng)網(wǎng)80%圖書的用戶，為了避免相似度矩陣過于稠密，我們?cè)趯?shí)際計(jì)算中一般直 接忽略他的興趣列表，而不將其納入到相似度計(jì)算的數(shù)據(jù)集中。

19. 物品相似度的歸一化

如果將ItemCF的相似度矩陣按最大值歸一化，可以提高推薦的準(zhǔn)確率。

如果已經(jīng)得到了物品相似度矩陣w，那么可以用如下公式得到歸一化之后的相似度矩陣w':

歸一化的好處不僅僅在于增加推薦的準(zhǔn)確度，它還可以提高推薦的覆蓋率和多樣性。 一般來說，物品總是屬于很多不同的類，每一類中的物品聯(lián)系比較緊密。舉一個(gè)例子，假設(shè)在一個(gè)電影網(wǎng)站中，有兩種電影——紀(jì)錄片和動(dòng)畫片。那么，ItemCF算出來的相似度一般是紀(jì)錄片和 紀(jì)錄片的相似度或者動(dòng)畫片和動(dòng)畫片的相似度大于紀(jì)錄片和動(dòng)畫片的相似度。但是紀(jì)錄片之間的 相似度和動(dòng)畫片之間的相似度卻不一定相同。假設(shè)物品分為兩類——A和B，A類物品之間的相似 度為0.5，B類物品之間的相似度為0.6，而A類物品和B類物品之間的相似度是0.2。在這種情況下， 如果一個(gè)用戶喜歡了5個(gè)A類物品和5個(gè)B類物品，用ItemCF給他進(jìn)行推薦，推薦的就都是B類物品， 因?yàn)锽類物品之間的相似度大。但如果歸一化之后，A類物品之間的相似度變成了1，B類物品之 間的相似度也是1，那么這種情況下，用戶如果喜歡5個(gè)A類物品和5個(gè)B類物品，那么他的推薦列表中A類物品和B類物品的數(shù)目也應(yīng)該是大致相等的。從這個(gè)例子可以看出，相似度的歸一化可以提高推薦的多樣性。

ItemCF算法和ItemCF-Norm算法的離線實(shí)驗(yàn)性能。

20. UserCF和ItemCF的綜合比較

UserCF是推薦系統(tǒng)領(lǐng)域較為古老的算法，1992年就已經(jīng)在電子郵件的個(gè)性化推薦系統(tǒng) Tapestry中得到了應(yīng)用，1994年被GroupLens1用來實(shí)現(xiàn)新聞的個(gè)性化推薦，后來被著名的文章分 享網(wǎng)站Digg用來給用戶推薦個(gè)性化的網(wǎng)絡(luò)文章。ItemCF則是相對(duì)比較新的算法，在著名的電子商 務(wù)網(wǎng)站亞馬遜和DVD租賃網(wǎng)站Netflix中得到了廣泛應(yīng)用。

那么，為什么Digg使用UserCF，而亞馬遜網(wǎng)使用ItemCF呢?

首先回顧一下UserCF算法和ItemCF算法的推薦原理。UserCF給用戶推薦那些和他有共同興 趣愛好的用戶喜歡的物品，而ItemCF給用戶推薦那些和他之前喜歡的物品類似的物品。從這個(gè)算法的原理可以看到，UserCF的推薦結(jié)果著重于反映和用戶興趣相似的小群體的熱點(diǎn)，而ItemCF 的推薦結(jié)果著重于維系用戶的歷史興趣。換句話說，UserCF的推薦更社會(huì)化，反映了用戶所在的小型興趣群體中物品的熱門程度，而ItemCF的推薦更加個(gè)性化，反映了用戶自己的興趣傳承。

在新聞網(wǎng)站中，用戶的興趣不是特別細(xì)化，絕大多數(shù)用戶都喜歡看熱門的新聞。即使是個(gè)性 化，也是比較粗粒度的，比如有些用戶喜歡體育新聞，有些喜歡社會(huì)新聞，而特別細(xì)粒度的個(gè)性化一般是不存在的。比方說，很少有用戶只看某個(gè)話題的新聞，主要是因?yàn)檫@個(gè)話題不可能保證每天都有新的消息，而這個(gè)用戶卻是每天都要看新聞的。因此，個(gè)性化新聞推薦更加強(qiáng)調(diào)抓住新聞熱點(diǎn)，熱門程度和時(shí)效性是個(gè)性化新聞推薦的重點(diǎn)，而個(gè)性化相對(duì)于這兩點(diǎn)略顯次要。因此，UserCF可以給用戶推薦和他有相似愛好的一群其他用戶今天都在看的新聞，這樣在抓住熱點(diǎn)和時(shí)效性的同時(shí)，保證了一定程度的個(gè)性化。這是Digg在新聞推薦中使用UserCF的最重要原因。

UserCF適合用于新聞推薦的另一個(gè)原因是從技術(shù)角度考量的。因?yàn)樽鳛橐环N物品，新聞的更 新非常快，每時(shí)每刻都有新內(nèi)容出現(xiàn)，而ItemCF需要維護(hù)一張物品相關(guān)度的表，如果物品更新很 快，那么這張表也需要很快更新，這在技術(shù)上很難實(shí)現(xiàn)。絕大多數(shù)物品相關(guān)度表都只能做到一天 一次更新，這在新聞?lì)I(lǐng)域是不可以接受的。而UserCF只需要用戶相似性表，雖然UserCF對(duì)于新 用戶也需要更新相似度表，但在新聞網(wǎng)站中，物品的更新速度遠(yuǎn)遠(yuǎn)快于新用戶的加入速度，而且 對(duì)于新用戶，完全可以給他推薦最熱門的新聞，因此UserCF顯然是利大于弊。

但是，在圖書、電子商務(wù)和電影網(wǎng)站，比如亞馬遜、豆瓣、Netflix中，ItemCF則能極大地發(fā) 揮優(yōu)勢(shì)。首先，在這些網(wǎng)站中，用戶的興趣是比較固定和持久的。一個(gè)技術(shù)人員可能都是在購買技術(shù)方面的書，而且他們對(duì)書的熱門程度并不是那么敏感，事實(shí)上越是資深的技術(shù)人員，他們看的書就越可能不熱門。此外，這些系統(tǒng)中的用戶大都不太需要流行度來輔助他們判斷一個(gè)物品的好壞，而是可以通過自己熟悉領(lǐng)域的知識(shí)自己判斷物品的質(zhì)量。因此，這些網(wǎng)站中個(gè)性化推薦的任務(wù)是幫助用戶發(fā)現(xiàn)和他研究領(lǐng)域相關(guān)的物品。因此，ItemCF算法成為了這些網(wǎng)站的首選算法。此外，這些網(wǎng)站的物品更新速度不會(huì)特別快，一天一次更新物品相似度矩陣對(duì)它們來說不會(huì)造成太大的損失，是可以接受的。

同時(shí)，從技術(shù)上考慮，UserCF需要維護(hù)一個(gè)用戶相似度的矩陣，而ItemCF需要維護(hù)一個(gè)物品 相似度矩陣。從存儲(chǔ)的角度說，如果用戶很多，那么維護(hù)用戶興趣相似度矩陣需要很大的空間， 同理，如果物品很多，那么維護(hù)物品相似度矩陣代價(jià)較大。

在早期的研究中，大部分研究人員都是讓少量的用戶對(duì)大量的物品進(jìn)行評(píng)價(jià)，然后研究用 戶興趣的模式。那么，對(duì)于他們來說，因?yàn)橛脩艉苌伲?jì)算用戶興趣相似度是最快也是最簡(jiǎn)單 的方法。但在實(shí)際的互聯(lián)網(wǎng)中，用戶數(shù)目往往非常龐大，而在圖書、電子商務(wù)網(wǎng)站中，物品的 數(shù)目則是比較少的。此外，物品的相似度相對(duì)于用戶的興趣一般比較穩(wěn)定，因此使用ItemCF是 比較好的選擇。當(dāng)然，新聞網(wǎng)站是個(gè)例外，在那兒，物品的相似度變化很快，物品數(shù)目龐大， 相反用戶興趣則相對(duì)固定(都是喜歡看熱門的)，所以新聞網(wǎng)站的個(gè)性化推薦使用UserCF算法的 更多。

UserCF和ItemCF優(yōu)缺點(diǎn)的對(duì)比

21. 隱語義模型 LFM（latent factor model）

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

兩個(gè)用戶在豆瓣的讀書列表

上圖展示了兩個(gè)用戶在豆瓣的讀書列表。從他們的閱讀列表可以看出，用戶A的興趣涉及偵探小說、科普?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è)用戶，首先得到他的興趣分類，然后從分類中挑選他可能喜歡的物品。 基于興趣分類的方法大概需要解決3個(gè)問題：

如何給物品進(jìn)行分類如何確定用戶對(duì)哪些類的物品感興趣，以及感興趣的程度？對(duì)于一個(gè)給定的類，選擇哪些屬于這個(gè)類的物品推薦給用戶，以及如何確定這些物品在一個(gè)類中的權(quán)重？

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

編輯的意見不能代表各種用戶的意見。比如，對(duì)于《具體數(shù)學(xué)》應(yīng)該屬于什么分類，有 人認(rèn)為應(yīng)該屬于數(shù)學(xué)，有些人認(rèn)為應(yīng)該屬于計(jì)算機(jī)。編輯很難控制分類的粒度。我們知道分類是有不同粒度的，《數(shù)據(jù)挖掘?qū)д摗吩诖至６鹊?分類中可能屬于計(jì)算機(jī)技術(shù)，但在細(xì)粒度的分類中可能屬于數(shù)據(jù)挖掘。對(duì)于不同的用戶， 我們可能需要不同的粒度。比如對(duì)于一位初學(xué)者，我們粗粒度地給他做推薦就可以了， 而對(duì)于一名資深研究人員，我們就需要深入到他的很細(xì)分的領(lǐng)域給他做個(gè)性化推薦。編輯很難給一個(gè)物品多個(gè)分類。有的書不僅屬于一個(gè)類，而是可能屬于很多的類。 編輯很難給出多維度的分類。我們知道，分類是可以有很多維度的，比如按照作者分類、 按照譯者分類、按照出版社分類。編輯很難決定一個(gè)物品在某一個(gè)分類中的權(quán)重。比如編輯可以很容易地決定《數(shù)據(jù)挖掘?qū)д摗穼儆跀?shù)據(jù)挖掘類圖書，但這本書在這類書中的定位是什么樣的，編輯就很難給出一個(gè)準(zhǔn)確的數(shù)字來表示。

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

編輯的意見不能代表各種用戶的意見，但隱含語義分析技術(shù)的分類來自對(duì)用戶行為的統(tǒng) 計(jì)，代表了用戶對(duì)物品分類的看法。編輯很難控制分類的粒度，但隱含語義分析技術(shù)允許我們指定最終有多少個(gè)分類，這個(gè)數(shù)字越大，分類的粒度就會(huì)越細(xì)，反正分類粒度就越粗。編輯很難給一個(gè)物品多個(gè)分類，但隱含語義分析技術(shù)會(huì)計(jì)算出物品屬于每個(gè)類的權(quán)重， 因此每個(gè)物品都不是硬性地被分到某一個(gè)類中。 編輯很難給出多維度的分類，但隱含語義分析技術(shù)給出的每個(gè)分類都不是同一個(gè)維度的，它是基于用戶的共同興趣計(jì)算出來的，如果用戶的共同興趣是某一個(gè)維度，那么LFM給出的類也是相同的維度。編輯很難決定一個(gè)物品在某一個(gè)分類中的權(quán)重，但隱含語義分析技術(shù)可以通過統(tǒng)計(jì)用戶行為決定物品在每個(gè)類中的權(quán)重，如果喜歡某個(gè)類的用戶都會(huì)喜歡某個(gè)物品，那么這個(gè)物品在這個(gè)類中的權(quán)重就可能比較高。

隱含語義分析技術(shù)從誕生到今天產(chǎn)生了很多著名的模型和方法，其中和該技術(shù)相關(guān)且耳熟能 詳?shù)拿~有pLSA、LDA、隱含類別模型(latent class model)、隱含主題模型(latent topic model)、 矩陣分解( ** trix factorization)。

以LFM為例介紹隱含語義分析技術(shù)在推薦系統(tǒng)中的應(yīng)用，LFM的公式如下：

這個(gè)公式中 和 是模型的參數(shù)，其中 度量了用戶u的興趣和第k個(gè)隱類的關(guān)系，而 度量了第k個(gè)隱類和物品i之間的關(guān)系。

要計(jì)算這兩個(gè)參數(shù)，需要一個(gè)訓(xùn)練集，對(duì)于每個(gè)用戶u，訓(xùn)練集里都包含了用戶u喜歡的物品和不感興趣的物品，通過學(xué)習(xí)這個(gè)數(shù)據(jù)集，就可以獲得上面的模型參數(shù)。

推薦系統(tǒng)的用戶行為分為顯性反饋和隱性反饋。LFM在顯性反饋數(shù)據(jù)(也就是評(píng)分?jǐn)?shù)據(jù))上解決評(píng)分預(yù)測(cè)問題并達(dá)到了很好的精度。在沒有負(fù)樣本的情況下，需要對(duì)用戶沒有過行為的物品進(jìn)行采集，對(duì)負(fù)樣本采樣時(shí)應(yīng)該遵循以下原則：

對(duì)每個(gè)用戶，要保證正負(fù)樣本的平衡(數(shù)目相似)。對(duì)每個(gè)用戶采樣負(fù)樣本時(shí)，要選取那些很熱門，而用戶卻沒有行為的物品。一般認(rèn)為，很熱門而用戶卻沒有行為更加代表用戶對(duì)這個(gè)物品不感興趣。因?yàn)閷?duì)于冷門的物品，用戶可能是壓根沒在網(wǎng)站中發(fā)現(xiàn)這個(gè)物品，所以談不上是否感興趣。

由于LFM相對(duì)而言較為復(fù)雜，在這里就省略了書中的具體算法介紹，有興趣可以讀一讀《推薦系統(tǒng)實(shí)戰(zhàn)》

22. LFM和基于領(lǐng)域的方法對(duì)比

LFM是一種基于機(jī)器學(xué)習(xí)的方法，具有比較好的理論基礎(chǔ)。這個(gè)方法和基于鄰域的方法(比 如UserCF、ItemCF)相比，各有優(yōu)缺點(diǎn)。

理論基礎(chǔ) LFM具有比較好的理論基礎(chǔ)，它是一種學(xué)習(xí)方法，通過優(yōu)化一個(gè)設(shè)定的指標(biāo)建立最優(yōu)的模型。基于鄰域的方法更多的是一種基于統(tǒng)計(jì)的方法，并沒有學(xué)習(xí)過程。 離線計(jì)算的空間復(fù)雜度 基于鄰域的方法需要維護(hù)一張離線的相關(guān)表。在離線計(jì)算相關(guān)表的過程中，如果用戶/物品數(shù)很多，將會(huì)占據(jù)很大的內(nèi)存。 而LFM在建模過程中，可以很好地節(jié)省離線計(jì)算的內(nèi)存。離線計(jì)算的時(shí)間復(fù)雜度 在一般情況下，LFM的時(shí)間復(fù)雜度要稍微高于UserCF和ItemCF，這主要是因?yàn)樵撍惴ㄐ枰啻蔚５傮w上，這兩種算法在時(shí)間復(fù)雜度上沒有質(zhì)的差別。在線實(shí)時(shí)推薦 UserCF和ItemCF在線服務(wù)算法需要將相關(guān)表緩存在內(nèi)存中，然后可以在線進(jìn)行實(shí)時(shí)的預(yù)測(cè)。以ItemCF算法為例，一旦用戶喜歡了新的物品，就可以通過查詢內(nèi)存中的相關(guān)表將和該物品相似的其他物品推薦給用戶。因此，一旦用戶有了新的行為， 而且該行為被實(shí)時(shí)地記錄到后臺(tái)的數(shù)據(jù)庫系統(tǒng)中，他的推薦列表就會(huì)發(fā)生變化。而從LFM的預(yù)測(cè)公式可以看到，LFM在給用戶生成推薦列表時(shí)，需要計(jì)算用戶對(duì)所有物品的興趣權(quán)重，然后排名，返回權(quán)重最大的N個(gè)物品。那么，在物品數(shù)很多時(shí)，這一過程的時(shí)間復(fù)雜度非常高。 LFM不能進(jìn)行在線實(shí)時(shí)推薦，也就是說，當(dāng)用戶有了新的行為后，他的推薦列表不會(huì)發(fā)生變化。

23. 基于圖的模型

用戶行為很容易用二分圖表示，因此很多圖的算法都可以用到推薦系統(tǒng)中。

本章討論的用戶行為 數(shù)據(jù)是由一系列二元組組成的，其中每個(gè)二元組(u, i)表示用戶u對(duì)物品i產(chǎn)生過行為。這種數(shù)據(jù)集 很容易用一個(gè)二分圖表示。

用戶物品二分圖模型：說明用戶A對(duì)物品a、b、d產(chǎn)生過行為

將個(gè)性化推薦算法放到二分圖模型上，那么給用戶u推薦物品的任務(wù)就可以轉(zhuǎn)化為度量用戶頂點(diǎn)vu和與vu沒有邊直接相連的物品節(jié)點(diǎn)在圖上的相關(guān)性，相關(guān)性越高的物品在推薦列表中的權(quán)重就越高。

度量圖中兩個(gè)頂點(diǎn)之間相關(guān)性的方法很多，但一般來說圖中頂點(diǎn)的相關(guān)性主要取決于下面3個(gè)因素:

兩個(gè)頂點(diǎn)之間的路徑數(shù)兩個(gè)頂點(diǎn)之間路徑的長(zhǎng)度兩個(gè)頂點(diǎn)之間的路徑經(jīng)過的頂點(diǎn)

相關(guān)性高的一對(duì)頂點(diǎn)一般具有如下特征:

兩個(gè)頂點(diǎn)之間有很多路徑相連連接兩個(gè)頂點(diǎn)之間的路徑長(zhǎng)度都比較短連接兩個(gè)頂點(diǎn)之間的路徑不會(huì)經(jīng)過出度比較大的頂點(diǎn)

舉一個(gè)簡(jiǎn)單的例子，如下圖所示，用戶A和物品c、e沒有邊相連，但是用戶A和物品c有兩 條長(zhǎng)度為3的路徑相連，用戶A和物品e有兩條長(zhǎng)度為3的路徑相連。那么，頂點(diǎn)A與e之間的相關(guān) 性要高于頂點(diǎn)A與c，因而物品e在用戶A的推薦列表中應(yīng)該排在物品c之前，因?yàn)轫旤c(diǎn)A與e之間有 兩條路徑——(A, b, C, e)和(A, d, D, e)。其中，(A, b, C, e)路徑經(jīng)過的頂點(diǎn)的出度為(3, 2, 2, 2)，而(A, d, D, e)路徑經(jīng)過的頂點(diǎn)的出度為(3, 2, 3, 2)。因此，(A, d, D, e)經(jīng)過了一個(gè)出度 比較大的頂點(diǎn)D，所以(A, d, D, e)對(duì)頂點(diǎn)A與e之間相關(guān)性的貢獻(xiàn)要小于(A, b, C, e)。

基于圖的推薦算法示例

基于上面3個(gè)主要因素，研究人員設(shè)計(jì)了很多計(jì)算圖中頂點(diǎn)之間相關(guān)性的方法，如 PersonalRank算法。

PersonalRank算法介紹：假設(shè)要給用戶u進(jìn)行個(gè)性化推薦，可以從用戶u對(duì)應(yīng)的節(jié)點(diǎn) 開始在用戶物品二分圖上進(jìn)行隨機(jī)游走。游走到任何一個(gè)節(jié)點(diǎn)時(shí)，首先按照概率α決定是繼續(xù)游走，還是停止這次游走并從vu節(jié)點(diǎn)開始重新游走。如果決定繼續(xù)游走，那么就從當(dāng)前節(jié)點(diǎn)指向的節(jié)點(diǎn)中按照均勻分布隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為游走下次經(jīng)過的節(jié)點(diǎn)。這樣，經(jīng)過很多次隨機(jī)游走后，每個(gè)物品節(jié)點(diǎn)被訪問到的概率會(huì)收斂到一個(gè)數(shù)。最終的推薦列表中物品的權(quán)重就是物品節(jié)點(diǎn)的訪問概率。（具體的算法和代碼屬于工程范疇，不具體一一介紹，有興趣可以去看《推薦系統(tǒng)實(shí)踐》）

以上圖為例，用PersonalRank算法給用戶A進(jìn)行推薦。

上圖給出了不同迭代次數(shù)后每個(gè)頂點(diǎn)的訪問概率。從圖中可以看到，每個(gè)頂點(diǎn)的訪問概率在9次迭代之后就基本上收斂了。在這個(gè)例子中，用戶A沒有對(duì)物品b、d有過行為。在最后的迭代結(jié)果中，d的訪問概率大于b，因此給A的推薦列表就是{d, b}。