什么是集體智慧

集體智慧 (Collective Intelligence) 并不是 Web2.0 時代特有的，只是在 Web2.0 時代，大家在 Web 應用中利用集體智慧構(gòu)建更加有趣的應用或者得到更好的用戶體驗。集體智慧是指在大量的人群的行為和數(shù)據(jù)中收集答案，幫助你對整個人群得到統(tǒng)計意義上的結(jié)論，這些結(jié)論是我們在單個個體上無法得到的，它往往是某種趨勢或者人群中共性的部分。

Wikipedia 和 Google 是兩個典型的利用集體智慧的 Web 2.0 應用：

• Wikipedia 是一個知識管理的百科全書，相對于傳統(tǒng)的由領域?qū)＜揖庉嫷陌倏迫珪琖ikipedia 允許最終用戶貢獻知識，隨著參與人數(shù)的增多，Wikipedia 變成了涵蓋各個領域的一本無比全面的知識庫。也許有人會質(zhì)疑它的權(quán)威性，但如果你從另一個側(cè)面想這個問題，也許就可以迎刃而解。在發(fā)行一本書時，作者雖然是權(quán)威，但難免還有一些錯誤，然后通過一版一版的改版，書的內(nèi)容越來越完善。而在 Wikipedia 上，這種改版和修正被變?yōu)槊總€人都可以做的事情，任何人發(fā)現(xiàn)錯誤或者不完善都可以貢獻他們的想法，即便某些信息是錯誤的，但它一定也會盡快的被其他人糾正過來。從一個宏觀的角度看，整個系統(tǒng)在按照一個良性循環(huán)的軌跡不斷完善，這也正是集體智慧的魅力。
• Google：目前最流行的搜索引擎，與 Wikipedia 不同，它沒有要求用戶顯式的貢獻，但仔細想想 Google 最核心的 PageRank 的思想，它利用了 Web 頁面之間的關系，將多少其他頁面鏈接到當前頁面的數(shù)目作為衡量當前頁面重要與否的標準；如果這不好理解，那么你可以把它想象成一個選舉的過程，每個 Web 頁面都是一個投票者同時也是一個被投票者，PageRank 通過一定數(shù)目的迭代得到一個相對穩(wěn)定的評分。Google 其實利用了現(xiàn)在 Internet 上所有 Web 頁面上鏈接的集體智慧，找到哪些頁面是重要的。

什么是協(xié)同過濾

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

協(xié)同過濾一般是在海量的用戶中發(fā)掘出一小部分和你品位比較類似的，在協(xié)同過濾中，這些用戶成為鄰居，然后根據(jù)他們喜歡的其他東西組織成一個排序的目錄作為推薦給你。當然其中有一個核心的問題：

• 如何確定一個用戶是不是和你有相似的品位？
• 如何將鄰居們的喜好組織成一個排序的目錄？

協(xié)同過濾相對于集體智慧而言，它從一定程度上保留了個體的特征，就是你的品位偏好，所以它更多可以作為個性化推薦的算法思想。可以想象，這種推薦策略在 Web 2.0 的長尾中是很重要的，將大眾流行的東西推薦給長尾中的人怎么可能得到好的效果，這也回到推薦系統(tǒng)的一個核心問題：了解你的用戶，然后才能給出更好的推薦。

深入?yún)f(xié)同過濾的核心

前面作為背景知識，介紹了集體智慧和協(xié)同過濾的基本思想，這一節(jié)我們將深入分析協(xié)同過濾的原理，介紹基于協(xié)同過濾思想的多種推薦機制，優(yōu)缺點和實用場景。

首先，要實現(xiàn)協(xié)同過濾，需要一下幾個步驟

• 收集用戶偏好
• 找到相似的用戶或物品
• 計算推薦

收集用戶偏好

要從用戶的行為和偏好中發(fā)現(xiàn)規(guī)律，并基于此給予推薦，如何收集用戶的偏好信息成為系統(tǒng)推薦效果最基礎的決定因素。用戶有很多方式向系統(tǒng)提供自己的偏好信息，而且不同的應用也可能大不相同，下面舉例進行介紹：

表 1 用戶行為和用戶偏好

以上列舉的用戶行為都是比較通用的，推薦引擎設計人員可以根據(jù)自己應用的特點添加特殊的用戶行為，并用他們表示用戶對物品的喜好。

在一般應用中，我們提取的用戶行為一般都多于一種，關于如何組合這些不同的用戶行為，基本上有以下兩種方式：

• 將不同的行為分組：一般可以分為“查看”和“購買”等等，然后基于不同的行為，計算不同的用戶 / 物品相似度。類似于當當網(wǎng)或者 Amazon 給出的“購買了該圖書的人還購買了 ...”，“查看了圖書的人還查看了 ...”
• 根據(jù)不同行為反映用戶喜好的程度將它們進行加權(quán)，得到用戶對于物品的總體喜好。一般來說，顯式的用戶反饋比隱式的權(quán)值大，但比較稀疏，畢竟進行顯示反饋的用戶是少數(shù)；同時相對于“查看”，“購買”行為反映用戶喜好的程度更大，但這也因應用而異。

收集了用戶行為數(shù)據(jù)，我們還需要對數(shù)據(jù)進行一定的預處理，其中最核心的工作就是：減噪和歸一化。

• 減噪：用戶行為數(shù)據(jù)是用戶在使用應用過程中產(chǎn)生的，它可能存在大量的噪音和用戶的誤操作，我們可以通過經(jīng)典的數(shù)據(jù)挖掘算法過濾掉行為數(shù)據(jù)中的噪音，這樣可以是我們的分析更加精確。
• 歸一化：如前面講到的，在計算用戶對物品的喜好程度時，可能需要對不同的行為數(shù)據(jù)進行加權(quán)。但可以想象，不同行為的數(shù)據(jù)取值可能相差很大，比如，用戶的查看數(shù)據(jù)必然比購買數(shù)據(jù)大的多，如何將各個行為的數(shù)據(jù)統(tǒng)一在一個相同的取值范圍中，從而使得加權(quán)求和得到的總體喜好更加精確，就需要我們進行歸一化處理。最簡單的歸一化處理，就是將各類數(shù)據(jù)除以此類中的最大值，以保證歸一化后的數(shù)據(jù)取值在 [0,1] 范圍中。

進行的預處理后，根據(jù)不同應用的行為分析方法，可以選擇分組或者加權(quán)處理，之后我們可以得到一個用戶偏好的二維矩陣，一維是用戶列表，另一維是物品列表，值是用戶對物品的偏好，一般是 [0,1] 或者 [-1, 1] 的浮點數(shù)值。

找到相似的用戶或物品

當已經(jīng)對用戶行為進行分析得到用戶喜好后，我們可以根據(jù)用戶喜好計算相似用戶和物品，然后基于相似用戶或者物品進行推薦，這就是最典型的 CF 的兩個分支：基于用戶的 CF 和基于物品的 CF。這兩種方法都需要計算相似度，下面我們先看看最基本的幾種計算相似度的方法。

相似度的計算

關于相似度的計算，現(xiàn)有的幾種基本方法都是基于向量（Vector）的，其實也就是計算兩個向量的距離，距離越近相似度越大。在推薦的場景中，在用戶 - 物品偏好的二維矩陣中，我們可以將一個用戶對所有物品的偏好作為一個向量來計算用戶之間的相似度，或者將所有用戶對某個物品的偏好作為一個向量來計算物品之間的相似度。下面我們詳細介紹幾種常用的相似度計算方法：

• 歐幾里德距離（Euclidean Distance）

最初用于計算歐幾里德空間中兩個點的距離，假設 x，y 是 n 維空間的兩個點，它們之間的歐幾里德距離是：

可以看出，當 n=2 時，歐幾里德距離就是平面上兩個點的距離。

當用歐幾里德距離表示相似度，一般采用以下公式進行轉(zhuǎn)換：距離越小，相似度越大

• 皮爾遜相關系數(shù)（Pearson Correlation Coefficient）

皮爾遜相關系數(shù)一般用于計算兩個定距變量間聯(lián)系的緊密程度，它的取值在 [-1，+1] 之間。

sx, sy是 x 和 y 的樣品標準偏差。

• Cosine 相似度（Cosine Similarity）

Cosine 相似度被廣泛應用于計算文檔數(shù)據(jù)的相似度：

• Tanimoto 系數(shù)（Tanimoto Coefficient）

Tanimoto 系數(shù)也稱為 Jaccard 系數(shù)，是 Cosine 相似度的擴展，也多用于計算文檔數(shù)據(jù)的相似度：

相似鄰居的計算

介紹完相似度的計算方法，下面我們看看如何根據(jù)相似度找到用戶 - 物品的鄰居，常用的挑選鄰居的原則可以分為兩類：圖 1 給出了二維平面空間上點集的示意圖。

• 固定數(shù)量的鄰居：K-neighborhoods 或者 Fix-size neighborhoods

不論鄰居的“遠近”，只取最近的 K 個，作為其鄰居。如圖 1 中的 A，假設要計算點 1 的 5- 鄰居，那么根據(jù)點之間的距離，我們?nèi)∽罱?5 個點，分別是點 2，點 3，點 4，點 7 和點 5。但很明顯我們可以看出，這種方法對于孤立點的計算效果不好，因為要取固定個數(shù)的鄰居，當它附近沒有足夠多比較相似的點，就被迫取一些不太相似的點作為鄰居，這樣就影響了鄰居相似的程度，比如圖 1 中，點 1 和點 5 其實并不是很相似。

• 基于相似度門檻的鄰居：Threshold-based neighborhoods

與計算固定數(shù)量的鄰居的原則不同，基于相似度門檻的鄰居計算是對鄰居的遠近進行最大值的限制，落在以當前點為中心，距離為 K 的區(qū)域中的所有點都作為當前點的鄰居，這種方法計算得到的鄰居個數(shù)不確定，但相似度不會出現(xiàn)較大的誤差。如圖 1 中的 B，從點 1 出發(fā)，計算相似度在 K 內(nèi)的鄰居，得到點 2，點 3，點 4 和點 7，這種方法計算出的鄰居的相似度程度比前一種優(yōu)，尤其是對孤立點的處理。

圖 1.相似鄰居計算示意圖

計算推薦

經(jīng)過前期的計算已經(jīng)得到了相鄰用戶和相鄰物品，下面介紹如何基于這些信息為用戶進行推薦。本系列的上一篇綜述文章已經(jīng)簡要介紹過基于協(xié)同過濾的推薦算法可以分為基于用戶的 CF 和基于物品的 CF，下面我們深入這兩種方法的計算方法，使用場景和優(yōu)缺點。

基于用戶的 CF（User CF）

基于用戶的 CF 的基本思想相當簡單，基于用戶對物品的偏好找到相鄰鄰居用戶，然后將鄰居用戶喜歡的推薦給當前用戶。計算上，就是將一個用戶對所有物品的偏好作為一個向量來計算用戶之間的相似度，找到 K 鄰居后，根據(jù)鄰居的相似度權(quán)重以及他們對物品的偏好，預測當前用戶沒有偏好的未涉及物品，計算得到一個排序的物品列表作為推薦。圖 2 給出了一個例子，對于用戶 A，根據(jù)用戶的歷史偏好，這里只計算得到一個鄰居 - 用戶 C，然后將用戶 C 喜歡的物品 D 推薦給用戶 A。

圖 2.基于用戶的 CF 的基本原理

基于物品的 CF（Item CF）

基于物品的 CF 的原理和基于用戶的 CF 類似，只是在計算鄰居時采用物品本身，而不是從用戶的角度，即基于用戶對物品的偏好找到相似的物品，然后根據(jù)用戶的歷史偏好，推薦相似的物品給他。從計算的角度看，就是將所有用戶對某個物品的偏好作為一個向量來計算物品之間的相似度，得到物品的相似物品后，根據(jù)用戶歷史的偏好預測當前用戶還沒有表示偏好的物品，計算得到一個排序的物品列表作為推薦。圖 3 給出了一個例子，對于物品 A，根據(jù)所有用戶的歷史偏好，喜歡物品 A 的用戶都喜歡物品 C，得出物品 A 和物品 C 比較相似，而用戶 C 喜歡物品 A，那么可以推斷出用戶 C 可能也喜歡物品 C。

圖 3.基于物品的 CF 的基本原理

User CF vs. Item CF

前面介紹了 User CF 和 Item CF 的基本原理，下面我們分幾個不同的角度深入看看它們各自的優(yōu)缺點和適用場景：

• 計算復雜度

Item CF 和 User CF 是基于協(xié)同過濾推薦的兩個最基本的算法，User CF 是很早以前就提出來了，Item CF 是從 Amazon 的論文和專利發(fā)表之后（2001 年左右）開始流行，大家都覺得 Item CF 從性能和復雜度上比 User CF 更優(yōu)，其中的一個主要原因就是對于一個在線網(wǎng)站，用戶的數(shù)量往往大大超過物品的數(shù)量，同時物品的數(shù)據(jù)相對穩(wěn)定，因此計算物品的相似度不但計算量較小，同時也不必頻繁更新。但我們往往忽略了這種情況只適應于提供商品的電子商務網(wǎng)站，對于新聞，博客或者微內(nèi)容的推薦系統(tǒng)，情況往往是相反的，物品的數(shù)量是海量的，同時也是更新頻繁的，所以單從復雜度的角度，這兩個算法在不同的系統(tǒng)中各有優(yōu)勢，推薦引擎的設計者需要根據(jù)自己應用的特點選擇更加合適的算法。

• 適用場景

在非社交網(wǎng)絡的網(wǎng)站中，內(nèi)容內(nèi)在的聯(lián)系是很重要的推薦原則，它比基于相似用戶的推薦原則更加有效。比如在購書網(wǎng)站上，當你看一本書的時候，推薦引擎會給你推薦相關的書籍，這個推薦的重要性遠遠超過了網(wǎng)站首頁對該用戶的綜合推薦。可以看到，在這種情況下，Item CF 的推薦成為了引導用戶瀏覽的重要手段。同時 Item CF 便于為推薦做出解釋，在一個非社交網(wǎng)絡的網(wǎng)站中，給某個用戶推薦一本書，同時給出的解釋是某某和你有相似興趣的人也看了這本書，這很難讓用戶信服，因為用戶可能根本不認識那個人；但如果解釋說是因為這本書和你以前看的某本書相似，用戶可能就覺得合理而采納了此推薦。

相反的，在現(xiàn)今很流行的社交網(wǎng)絡站點中，User CF 是一個更不錯的選擇，User CF 加上社會網(wǎng)絡信息，可以增加用戶對推薦解釋的信服程度。

• 推薦多樣性和精度

研究推薦引擎的學者們在相同的數(shù)據(jù)集合上分別用 User CF 和 Item CF 計算推薦結(jié)果，發(fā)現(xiàn)推薦列表中，只有 50% 是一樣的，還有 50% 完全不同。但是這兩個算法確有相似的精度，所以可以說，這兩個算法是很互補的。

關于推薦的多樣性，有兩種度量方法：

第一種度量方法是從單個用戶的角度度量，就是說給定一個用戶，查看系統(tǒng)給出的推薦列表是否多樣，也就是要比較推薦列表中的物品之間兩兩的相似度，不難想到，對這種度量方法，Item CF 的多樣性顯然不如 User CF 的好，因為 Item CF 的推薦就是和以前看的東西最相似的。

第二種度量方法是考慮系統(tǒng)的多樣性，也被稱為覆蓋率 (Coverage)，它是指一個推薦系統(tǒng)是否能夠提供給所有用戶豐富的選擇。在這種指標下，Item CF 的多樣性要遠遠好于 User CF, 因為 User CF 總是傾向于推薦熱門的，從另一個側(cè)面看，也就是說，Item CF 的推薦有很好的新穎性，很擅長推薦長尾里的物品。所以，盡管大多數(shù)情況，Item CF 的精度略小于 User CF， 但如果考慮多樣性，Item CF 卻比 User CF 好很多。

如果你對推薦的多樣性還心存疑惑，那么下面我們再舉個實例看看 User CF 和 Item CF 的多樣性到底有什么差別。首先，假設每個用戶興趣愛好都是廣泛的，喜歡好幾個領域的東西，不過每個用戶肯定也有一個主要的領域，對這個領域會比其他領域更加關心。給定一個用戶，假設他喜歡 3 個領域 A,B,C，A 是他喜歡的主要領域，這個時候我們來看 User CF 和 Item CF 傾向于做出什么推薦：如果用 User CF, 它會將 A,B,C 三個領域中比較熱門的東西推薦給用戶；而如果用 ItemCF，它會基本上只推薦 A 領域的東西給用戶。所以我們看到因為 User CF 只推薦熱門的，所以它在推薦長尾里項目方面的能力不足；而 Item CF 只推薦 A 領域給用戶，這樣他有限的推薦列表中就可能包含了一定數(shù)量的不熱門的長尾物品，同時 Item CF 的推薦對這個用戶而言，顯然多樣性不足。但是對整個系統(tǒng)而言，因為不同的用戶的主要興趣點不同，所以系統(tǒng)的覆蓋率會比較好。

從上面的分析，可以很清晰的看到，這兩種推薦都有其合理性，但都不是最好的選擇，因此他們的精度也會有損失。其實對這類系統(tǒng)的最好選擇是，如果系統(tǒng)給這個用戶推薦 30 個物品，既不是每個領域挑選 10 個最熱門的給他，也不是推薦 30 個 A 領域的給他，而是比如推薦 15 個 A 領域的給他，剩下的 15 個從 B,C 中選擇。所以結(jié)合 User CF 和 Item CF 是最優(yōu)的選擇，結(jié)合的基本原則就是當采用 Item CF 導致系統(tǒng)對個人推薦的多樣性不足時，我們通過加入 User CF 增加個人推薦的多樣性，從而提高精度，而當因為采用 User CF 而使系統(tǒng)的整體多樣性不足時，我們可以通過加入 Item CF 增加整體的多樣性，同樣同樣可以提高推薦的精度。

• 用戶對推薦算法的適應度

前面我們大部分都是從推薦引擎的角度考慮哪個算法更優(yōu)，但其實我們更多的應該考慮作為推薦引擎的最終使用者 -- 應用用戶對推薦算法的適應度。

對于 User CF，推薦的原則是假設用戶會喜歡那些和他有相同喜好的用戶喜歡的東西，但如果一個用戶沒有相同喜好的朋友，那 User CF 的算法的效果就會很差，所以一個用戶對的 CF 算法的適應度是和他有多少共同喜好用戶成正比的。

Item CF 算法也有一個基本假設，就是用戶會喜歡和他以前喜歡的東西相似的東西，那么我們可以計算一個用戶喜歡的物品的自相似度。一個用戶喜歡物品的自相似度大，就說明他喜歡的東西都是比較相似的，也就是說他比較符合 Item CF 方法的基本假設，那么他對 Item CF 的適應度自然比較好；反之，如果自相似度小，就說明這個用戶的喜好習慣并不滿足 Item CF 方法的基本假設，那么對于這種用戶，用 Item CF 方法做出好的推薦的可能性非常低。