面試題：詳細(xì)說說協(xié)同過濾的原理

文 | 七月在線
編 | 小七

解析：

1 推薦引擎的分類

推薦引擎根據(jù)不同依據(jù)如下分類：
根據(jù)其是不是為不同的用戶推薦不同的數(shù)據(jù)，分為基于大眾行為（網(wǎng)站管理員自行推薦，或者基于系統(tǒng)所有用戶的反饋統(tǒng)計(jì)計(jì)算出的當(dāng)下比較流行的物品）、及個(gè)性化推薦引擎（幫你找志同道合，趣味相投的朋友，然后在此基礎(chǔ)上實(shí)行推薦）；

根據(jù)其數(shù)據(jù)源，分為基于人口統(tǒng)計(jì)學(xué)的（用戶年齡或性別相同判定為相似用戶）、基于內(nèi)容的（物品具有相同關(guān)鍵詞和Tag，沒有考慮人為因素），以及基于協(xié)同過濾的推薦（發(fā)現(xiàn)物品，內(nèi)容或用戶的相關(guān)性推薦，分為三個(gè)子類，下文闡述）；

根據(jù)其建立方式，分為基于物品和用戶本身的（用戶-物品二維矩陣描述用戶喜好，聚類算法）、基于關(guān)聯(lián)規(guī)則的（The Apriori algorithm算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法）、以及基于模型的推薦（機(jī)器學(xué)習(xí)，所謂機(jī)器學(xué)習(xí)，即讓計(jì)算機(jī)像人腦一樣持續(xù)學(xué)習(xí)，是人工智能領(lǐng)域內(nèi)的一個(gè)子領(lǐng)域）。

關(guān)于上述第二個(gè)分類(2、根據(jù)其數(shù)據(jù)源)中的基于協(xié)同過濾的推薦：隨著 Web2.0 的發(fā)展，Web 站點(diǎn)更加提倡用戶參與和用戶貢獻(xiàn)，因此基于協(xié)同過濾的推薦機(jī)制因運(yùn)而生。它的原理很簡單，就是根據(jù)用戶對(duì)物品或者信息的偏好，發(fā)現(xiàn)物品或者內(nèi)容本身的相關(guān)性，或者是發(fā)現(xiàn)用戶的相關(guān)性，然后再基于這些關(guān)聯(lián)性進(jìn)行推薦。

而基于協(xié)同過濾的推薦，又分三個(gè)子類：

基于用戶的推薦(通過共同口味與偏好找相似鄰居用戶，K-鄰居算法，你朋友喜歡，你也可能喜歡)，
基于項(xiàng)目的推薦(發(fā)現(xiàn)物品之間的相似度，推薦類似的物品，你喜歡物品A，C與A相似，可能也喜歡C)，
基于模型的推薦(基于樣本的用戶喜好信息構(gòu)造一個(gè)推薦模型，然后根據(jù)實(shí)時(shí)的用戶喜好信息預(yù)測推薦)。

我們看到，此協(xié)同過濾算法最大限度的利用用戶之間，或物品之間的相似相關(guān)性，而后基于這些信息的基礎(chǔ)上實(shí)行推薦。下文還會(huì)具體介紹此協(xié)同過濾。

不過一般實(shí)踐中，我們通常還是把推薦引擎分兩類：

第一類稱為協(xié)同過濾，即基于相似用戶的協(xié)同過濾推薦（用戶與系統(tǒng)或互聯(lián)網(wǎng)交互留下的一切信息、蛛絲馬跡，或用戶與用戶之間千絲萬縷的聯(lián)系），以及基于相似項(xiàng)目的協(xié)同過濾推薦（盡最大可能發(fā)現(xiàn)物品間的相似度）；
第二類便是基于內(nèi)容分析的推薦（調(diào)查問卷，電子郵件，或者推薦引擎對(duì)本blog內(nèi)容的分析）。

2 協(xié)同過濾推薦

協(xié)同過濾是利用集體智慧的一個(gè)典型方法。要理解什么是協(xié)同過濾 (Collaborative Filtering, 簡稱 CF)，首先想一個(gè)簡單的問題，如果你現(xiàn)在想看個(gè)電影，但你不知道具體看哪部，你會(huì)怎么做？大部分的人會(huì)問問周圍的朋友或者稱之為廣義上的鄰居(neighborhood)，看看最近有什么好看的電影推薦，而我們一般更傾向于從口味比較類似的朋友那里得到推薦。這就是協(xié)同過濾的核心思想。如下圖，你能從圖中看到多少信息？

?

2.1 協(xié)同過濾推薦步驟

做協(xié)同過濾推薦，一般要做好以下幾個(gè)步驟：

1）若要做協(xié)同過濾，那么收集用戶偏好則成了關(guān)鍵?？梢酝ㄟ^用戶的行為諸如評(píng)分（如不同的用戶對(duì)不同的作品有不同的評(píng)分，而評(píng)分接近則意味著喜好口味相近，便可判定為相似用戶），投票，轉(zhuǎn)發(fā)，保存，書簽，標(biāo)記，評(píng)論，點(diǎn)擊流，頁面停留時(shí)間，是否購買等獲得。如下面第2點(diǎn)所述：所有這些信息都可以數(shù)字化，如一個(gè)二維矩陣表示出來。

2）收集了用戶行為數(shù)據(jù)之后，我們接下來便要對(duì)數(shù)據(jù)進(jìn)行減噪與歸一化操作(得到一個(gè)用戶偏好的二維矩陣，一維是用戶列表，另一維是物品列表，值是用戶對(duì)物品的偏好，一般是 [0,1] 或者 [-1, 1] 的浮點(diǎn)數(shù)值)。

下面再簡單介紹下減噪和歸一化操作。

所謂減噪：用戶行為數(shù)據(jù)是用戶在使用應(yīng)用過程中產(chǎn)生的，它可能存在大量的噪音和用戶的誤操作，我們可以通過經(jīng)典的數(shù)據(jù)挖掘算法過濾掉行為數(shù)據(jù)中的噪音，這樣可以是我們的分析更加精確（類似于網(wǎng)頁的去噪處理）。

所謂歸一化：將各個(gè)行為的數(shù)據(jù)統(tǒng)一在一個(gè)相同的取值范圍中，從而使得加權(quán)求和得到的總體喜好更加精確。最簡單的歸一化處理，便是將各類數(shù)據(jù)除以此類中的最大值，以保證歸一化后的數(shù)據(jù)取值在 [0,1] 范圍中。至于所謂的加權(quán)，很好理解，因?yàn)槊總€(gè)人占的權(quán)值不同，類似于一場唱歌比賽中對(duì)某幾個(gè)選手進(jìn)行投票決定其是否晉級(jí)，觀眾的投票抵1分，專家評(píng)委的投票抵5分，最后得分最多的選手直接晉級(jí)。

3）找到相似的用戶和物品，通過什么途徑找到呢？便是計(jì)算相似用戶或相似物品的相似度。

4）相似度的計(jì)算有多種方法，不過都是基于向量Vector的，其實(shí)也就是計(jì)算兩個(gè)向量的距離，距離越近相似度越大。在推薦中，用戶-物品偏好的二維矩陣下，我們將某個(gè)或某幾個(gè)用戶對(duì)莫兩個(gè)物品的偏好作為一個(gè)向量來計(jì)算兩個(gè)物品之間的相似度，或者將兩個(gè)用戶對(duì)某個(gè)或某幾個(gè)物品的偏好作為一個(gè)向量來計(jì)算兩個(gè)用戶之間的相似度。


所以說，很簡單，找物品間的相似度，用戶不變，找多個(gè)用戶對(duì)物品的評(píng)分；找用戶間的相似度，物品不變，找用戶對(duì)某些個(gè)物品的評(píng)分。

5）而計(jì)算出來的這兩個(gè)相似度則將作為基于用戶、項(xiàng)目的兩項(xiàng)協(xié)同過濾的推薦。

常見的計(jì)算相似度的方法有：歐幾里德距離，皮爾遜相關(guān)系數(shù)（如兩個(gè)用戶對(duì)多個(gè)電影的評(píng)分，采取皮爾遜相關(guān)系數(shù)等相關(guān)計(jì)算方法，可以抉擇出他們的口味和偏好是否一致），Cosine相似度，Tanimoto系數(shù)。

下面，簡單介紹其中的歐幾里得距離與皮爾遜相關(guān)系數(shù)：
歐幾里德距離（Euclidean Distance）是最初用于計(jì)算歐幾里德空間中兩個(gè)點(diǎn)的距離，假設(shè) x，y 是 n 維空間的兩個(gè)點(diǎn)，它們之間的歐幾里德距離是：
可以看出，當(dāng) n=2 時(shí)，歐幾里德距離就是平面上兩個(gè)點(diǎn)的距離。當(dāng)用歐幾里德距離表示相似度，一般采用以下公式進(jìn)行轉(zhuǎn)換：
距離越小，相似度越大（同時(shí)，避免除數(shù)為0）：
余弦相似度Cosine-based Similarity
兩個(gè)項(xiàng)目 i ，j 視作為兩個(gè)m維用戶空間向量，相似度計(jì)算通過計(jì)算兩個(gè)向量的余弦夾角，那么，對(duì)于m*n的評(píng)分矩陣，i ，j 的相似度sim( i , j ) 計(jì)算公式：
（其中 " · "記做兩個(gè)向量的內(nèi)積）

皮爾遜相關(guān)系數(shù)一般用于計(jì)算兩個(gè)定距變量間聯(lián)系的緊密程度，為了使計(jì)算結(jié)果精確，需要找出共同評(píng)分的用戶。記用戶集U為既評(píng)論了 i 又評(píng)論了 j 的用戶集，那么對(duì)應(yīng)的皮爾森相關(guān)系數(shù)計(jì)算公式為：

其中Ru,i 為用戶u 對(duì)項(xiàng)目 i 的評(píng)分，對(duì)應(yīng)帶橫杠的為這個(gè)用戶集U對(duì)項(xiàng)目i的評(píng)分評(píng)分。

6）相似鄰居計(jì)算。鄰居分為兩類：
1、固定數(shù)量的鄰居K-neighborhoods （或Fix-size neighborhoods），不論鄰居的“遠(yuǎn)近”，只取最近的 K 個(gè)，作為其鄰居，如下圖A部分所示；
2、基于相似度門檻的鄰居，落在以當(dāng)前點(diǎn)為中心，距離為 K 的區(qū)域中的所有點(diǎn)都作為當(dāng)前點(diǎn)的鄰居，如下圖B部分所示。


再介紹一下K最近鄰(k-Nearest Neighbor，KNN)分類算法：這是一個(gè)理論上比較成熟的方法，也是最簡單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。

7）經(jīng)過4)計(jì)算出來的基于用戶的CF(基于用戶推薦之用：通過共同口味與偏好找相似鄰居用戶，K-鄰居算法，你朋友喜歡，你也可能喜歡)，基于物品的CF(基于項(xiàng)目推薦之用：發(fā)現(xiàn)物品之間的相似度，推薦類似的物品，你喜歡物品A，C與A相似，那么你可能也喜歡C)。

2.2 基于基于用戶相似度與項(xiàng)目相似度

    上述3.1節(jié)中三個(gè)相似度公式是基于項(xiàng)目相似度場景下的，而實(shí)際上，基于用戶相似度與基于項(xiàng)目相似度計(jì)算的一個(gè)基本的區(qū)別是，基于用戶相似度是基于評(píng)分矩陣中的行向量相似度求解，基于項(xiàng)目相似度計(jì)算式基于評(píng)分矩陣中列向量相似度求解，然后三個(gè)公式分別都可以適用，如下圖：


（其中，為0的表示未評(píng)分）

基于項(xiàng)目相似度計(jì)算式計(jì)算如Item3，Item4兩列向量相似度；
基于用戶相似度計(jì)算式計(jì)算如User3，User4量行向量相似度。

千言萬語不如舉個(gè)例子。我們來看一個(gè)具體的基于用戶相似度計(jì)算的例子。

假設(shè)我們有一組用戶，他們表現(xiàn)出了對(duì)一組圖書的喜好。用戶對(duì)一本圖書的喜好程度越高，就會(huì)給其更高的評(píng)分。我們來通過一個(gè)矩陣來展示它，行代表用戶，列代表圖書。

如下圖所示，所有的評(píng)分范圍從1到5，5代表喜歡程度最高。第一個(gè)用戶（行1）對(duì)第一本圖書（列1）的評(píng)分是4，空的單元格表示用戶未給圖書評(píng)分。


使用基于用戶的協(xié)同過濾方法，我們首先要做的是基于用戶給圖書做出的評(píng)價(jià)，計(jì)算用戶之間的相似度。

讓我們從一個(gè)單一用戶的角度考慮這個(gè)問題，看圖1中的第一行，要做到這一點(diǎn)，常見的做法是將使用包含了用戶喜好項(xiàng)的向量（或數(shù)組）代表每一個(gè)用戶。相較于使用多樣化的相似度量這種做法，更直接。

在這個(gè)例子中，我們將使用余弦相似性去計(jì)算用戶間的相似度。

當(dāng)我們把第一個(gè)用戶和其他五個(gè)用戶進(jìn)行比較時(shí)，就能直觀的看到他和其他用戶的相似程度。

對(duì)于大多數(shù)相似度量，向量之間相似度越高，代表彼此更相似。本例中，第一個(gè)用戶第二、第三個(gè)用戶非常相似，有兩本共同書籍，與第四、第五個(gè)用戶的相似度低一些，只有一本共同書籍，而與最后一名用戶完全不相似，因?yàn)闆]有一本共同書籍。


更一般的，我們可以計(jì)算出每個(gè)用戶的相似性，并且在相似矩陣中表示它們。這是一個(gè)對(duì)稱矩陣，單元格的背景顏色表明用戶相似度的高低，更深的紅色表示它們之間更相似。


所以，我們找到了與第一個(gè)用戶最相似的第二個(gè)用戶，刪除用戶已經(jīng)評(píng)價(jià)過的書籍，給最相似用戶正在閱讀的書籍加權(quán)，然后計(jì)算出總和。

在這種情況下，我們計(jì)算出n=2，表示為了產(chǎn)生推薦，需要找出與目標(biāo)用戶最相似的兩個(gè)用戶，這兩個(gè)用戶分別是第二個(gè)和第三個(gè)用戶，然后第一個(gè)用戶已經(jīng)評(píng)價(jià)了第一和第五本書，故產(chǎn)生的推薦書是第三本（4.5分），和第四本（3分）。


此外，什么時(shí)候用item-base，什么時(shí)候用user-base呢：http://weibo.com/1580904460/zhZ9AiIkZ?mod=weibotime？

一般說來，如果item數(shù)目不多，比如不超過十萬，而且不顯著增長的話，就用item-based 好了。為何？如@wuzh670所說，如果item數(shù)目不多+不顯著增長，說明item之間的關(guān)系在一段時(shí)間內(nèi)相對(duì)穩(wěn)定(對(duì)比user之間關(guān)系)，對(duì)于實(shí)時(shí)更新item-similarity需求就降低很多，推薦系統(tǒng)效率提高很多，故用item-based會(huì)明智些。

反之，當(dāng)item數(shù)目很多，建議用user-base。當(dāng)然，實(shí)踐中具體情況具體分析。如下圖所示（摘自項(xiàng)亮的《推薦系統(tǒng)實(shí)踐》一書）：


3 參考文獻(xiàn)
1 推薦引擎算法學(xué)習(xí)導(dǎo)論：協(xié)同過濾、聚類、分類：https://blog.csdn.net/v_july_v/article/details/7184318
2 協(xié)同過濾推薦算法和基于內(nèi)容的過濾算法：https://time.geekbang.org/article/1947

?
今日推薦：【音樂推薦系統(tǒng) 直播課】
實(shí)時(shí)直播，在線答疑！