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

文 | 七月在線
編 | 小七

解析：

1 推薦引擎的分類

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

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

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

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

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

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

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

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

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

2 協(xié)同過濾推薦

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

?

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

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

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

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

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

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

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

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

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


所以說，很簡單，找物品間的相似度，用戶不變，找多個用戶對物品的評分；找用戶間的相似度，物品不變，找用戶對某些個物品的評分。

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

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

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

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

其中Ru,i 為用戶u 對項目 i 的評分，對應(yīng)帶橫杠的為這個用戶集U對項目i的評分評分。

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


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

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

2.2 基于基于用戶相似度與項目相似度

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


（其中，為0的表示未評分）

基于項目相似度計算式計算如Item3，Item4兩列向量相似度；
基于用戶相似度計算式計算如User3，User4量行向量相似度。

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

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

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


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

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

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

當我們把第一個用戶和其他五個用戶進行比較時，就能直觀的看到他和其他用戶的相似程度。

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


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


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

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


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

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

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


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

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