集體智慧和協(xié)同過濾

什么是集體智慧

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

Wikipedia 和 Google 是兩個(gè)典型的利用集體智慧的 Web 2.0 應(yīng)用：

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

什么是協(xié)同過濾

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

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

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

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

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

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

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

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

收集用戶偏好

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

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

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

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

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

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

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

找到相似的用戶或物品

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

相似度的計(jì)算

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

• 歐幾里德距離（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)換：距離越小，相似度越大

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

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

s_x, s_y是 x 和 y 的樣品標(biāo)準(zhǔn)偏差。

• Cosine 相似度（Cosine Similarity）

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

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

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

相似鄰居的計(jì)算

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

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

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

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

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

計(jì)算推薦

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

基于用戶的 CF（User CF）

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

基于物品的 CF（Item CF）

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

User CF vs. Item CF

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

• 計(jì)算復(fù)雜度

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

• 適用場(chǎng)景

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

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

• 推薦多樣性和精度

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

關(guān)于推薦的多樣性，有兩種度量方法：

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

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

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

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

• 用戶對(duì)推薦算法的適應(yīng)度

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

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

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

通過以上的介紹，相信大家已經(jīng)對(duì)協(xié)同過濾推薦的各種方法，原則，特點(diǎn)和適用場(chǎng)景有深入的了解，下面我們就進(jìn)入實(shí)戰(zhàn)階段，重點(diǎn)介紹如何基于 Apache Mahout 實(shí)現(xiàn)協(xié)同過濾推薦算法。

回頁首

基于 Apache Mahout 實(shí)現(xiàn)高效的協(xié)同過濾推薦

Apache Mahout 是 Apache Software Foundation (ASF) 旗下的一個(gè)開源項(xiàng)目，提供一些可擴(kuò)展的機(jī)器學(xué)習(xí)領(lǐng)域經(jīng)典算法的實(shí)現(xiàn)，旨在幫助開發(fā)人員更加方便快捷地創(chuàng)建智能應(yīng)用程序，并且，在 Mahout 的最近版本中還加入了對(duì) Apache Hadoop 的支持，使這些算法可以更高效的運(yùn)行在云計(jì)算環(huán)境中。

關(guān)于 Apache Mahout 的安裝和配置請(qǐng)參考《基于 Apache Mahout 構(gòu)建社會(huì)化推薦引擎》，它是筆者 09 年發(fā)表的一篇關(guān)于基于 Mahout 實(shí)現(xiàn)推薦引擎的 developerWorks 文章，其中詳細(xì)介紹了 Mahout 的安裝步驟，并給出一個(gè)簡(jiǎn)單的電影推薦引擎的例子。

Apache Mahout 中提供的一個(gè)協(xié)同過濾算法的高效實(shí)現(xiàn)，它是一個(gè)基于 Java 實(shí)現(xiàn)的可擴(kuò)展的，高效的推薦引擎。圖 4 給出了 Apache Mahout 中協(xié)同過濾推薦實(shí)現(xiàn)的組件圖，下面我們逐步深入介紹各個(gè)部分。

數(shù)據(jù)表示：Data Model

Preference

基于協(xié)同過濾的推薦引擎的輸入是用戶的歷史偏好信息，在 Mahout 里它被建模為 Preference（接口），一個(gè) Preference 就是一個(gè)簡(jiǎn)單的三元組 < 用戶 ID, 物品 ID, 用戶偏好 >，它的實(shí)現(xiàn)類是 GenericPreference，可以通過以下語句創(chuàng)建一個(gè) GenericPreference。

GenericPreference preference = new GenericPreference(123, 456, 3.0f);

這其中， 123 是用戶 ID，long 型；456 是物品 ID，long 型；3.0f 是用戶偏好，float 型。從這個(gè)例子我們可以看出，單單一個(gè) GenericPreference 的數(shù)據(jù)就占用 20 bytes，所以你會(huì)發(fā)現(xiàn)如果只簡(jiǎn)單實(shí)用數(shù)組 Array 加載用戶偏好數(shù)據(jù)，必然占用大量的內(nèi)存，Mahout 在這方面做了一些優(yōu)化，它創(chuàng)建了 PreferenceArray（接口）保存一組用戶偏好數(shù)據(jù)，為了優(yōu)化性能，Mahout 給出了兩個(gè)實(shí)現(xiàn)類，GenericUserPreferenceArray 和 GenericItemPreferenceArray，分別按照用戶和物品本身對(duì)用戶偏好進(jìn)行組裝，這樣就可以壓縮用戶 ID 或者物品 ID 的空間。下面清單 1 的代碼以 GenericUserPreferenceArray 為例，展示了如何創(chuàng)建和使用一個(gè) PreferenceArray。

				 
 PreferenceArray userPref = new GenericUserPreferenceArray(2); //size = 2 

 userPref.setUserID(0, 1L); 

 userPref.setItemID(0, 101L);  //<1L, 101L, 2.0f> 
 userPref.setValue(0, 2.0f); 
 userPref.setItemID(1, 102L);  //<1L, 102L, 4.0f> 
 userPref.setValue(1, 4.0f); 

 Preference pref = userPref.get(1);   //<1L, 102L, 4.0f> 

為了提高性能 Mahout 還構(gòu)建了自己的 HashMap 和 Set：FastByIDMap 和 FastIDSet，有興趣的朋友可以參考 Mahout 官方說明。

DataModel

Mahout 的推薦引擎實(shí)際接受的輸入是 DataModel，它是對(duì)用戶偏好數(shù)據(jù)的壓縮表示，通過創(chuàng)建內(nèi)存版 DataModel 的語句我們可以看出：

DataModel model = new GenericDataModel(FastByIDMap<PreferenceArray> map);

他保存在一個(gè)按照用戶 ID 或者物品 ID 進(jìn)行散列的 PreferenceArray，而 PreferenceArray 中對(duì)應(yīng)保存著這個(gè)用戶 ID 或者物品 ID 的所有用戶偏好信息。

DataModel 是用戶喜好信息的抽象接口，它的具體實(shí)現(xiàn)支持從任意類型的數(shù)據(jù)源抽取用戶喜好信息，具體實(shí)現(xiàn)包括內(nèi)存版的 GenericDataModel，支持文件讀取的 FileDataModel 和支持?jǐn)?shù)據(jù)庫讀取的 JDBCDataModel，下面我們看看如何創(chuàng)建各種 DataModel。

				 
 //In-memory DataModel - GenericDataModel 
 FastByIDMap<PreferenceArray> preferences = new FastByIDMap<PreferenceArray>(); 

 PreferenceArray prefsForUser1 = new GenericUserPreferenceArray(10);  
 prefsForUser1.setUserID(0, 1L); 
 prefsForUser1.setItemID(0, 101L); 
 prefsForUser1.setValue(0, 3.0f);  
 prefsForUser1.setItemID(1, 102L); 
 prefsForUser1.setValue(1, 4.5f); 
… (8 more) 
 preferences.put(1L, prefsForUser1);   //use userID as the key 
… (more users) 

 DataModel model = new GenericDataModel(preferences); 

 //File-based DataModel - FileDataModel 
 DataModel dataModel = new FileDataModel(new File("preferences.csv"); 

 //Database-based DataModel - MySQLJDBCDataModel 
 MysqlDataSource dataSource = new MysqlDataSource(); 
 dataSource.setServerName("my_user"); 
 dataSource.setUser("my_password"); 
 dataSource.setPassword("my_database_host"); 
 JDBCDataModel dataModel = new MySQLJDBCDataModel(dataSource, "my_prefs_table", 
 "my_user_column", "my_item_column", "my_pref_value_column"); 

支持文件讀取的 FileDataModel，Mahout 沒有對(duì)文件的格式做過多的要求，只要文件的內(nèi)容滿足以下格式：

• 每一行包括用戶 ID, 物品 ID, 用戶偏好
• 逗號(hào)隔開或者 Tab 隔開
• *.zip 和 *.gz 文件會(huì)自動(dòng)解壓縮（Mahout 建議在數(shù)據(jù)量過大時(shí)采用壓縮的數(shù)據(jù)存儲(chǔ)）

支持?jǐn)?shù)據(jù)庫讀取的 JDBCDataModel，Mahout 提供一個(gè)默認(rèn)的 MySQL 的支持，它對(duì)用戶偏好數(shù)據(jù)的存放有以下簡(jiǎn)單的要求：

• 用戶 ID 列需要是 BIGINT 而且非空
• 物品 ID 列需要是 BIGINT 而且非空
• 用戶偏好列需要是 FLOAT

建議在用戶 ID 和物品 ID 上建索引。

實(shí)現(xiàn)推薦：Recommender

介紹完數(shù)據(jù)表示模型，下面介紹 Mahout 提供的協(xié)同過濾的推薦策略，這里我們選擇其中最經(jīng)典的三種，User CF, Item CF 和 Slope One。

User CF

前面已經(jīng)詳細(xì)介紹了 User CF 的原理，這里我們著重看怎么基于 Mahout 實(shí)現(xiàn) User CF 的推薦策略，我們還是從一個(gè)例子入手：

				 
 DataModel model = new FileDataModel(new File("preferences.dat")); 
 UserSimilarity similarity = new PearsonCorrelationSimilarity(model); 
 UserNeighborhood neighborhood = new NearestNUserNeighborhood(100, similarity, model); 
 Recommender recommender = new GenericUserBasedRecommender(model, 
 neighborhood, similarity); 

1. 從文件建立 DataModel，我們采用前面介紹的 FileDataModel，這里假設(shè)用戶的喜好信息存放在 preferences.dat 文件中。
2. 基于用戶偏好數(shù)據(jù)計(jì)算用戶的相似度，清單中采用的是 PearsonCorrelationSimilarity，前面章節(jié)曾詳細(xì)介紹了各種計(jì)算相似度的方法，Mahout 中提供了基本的相似度的計(jì)算，它們都 UserSimilarity 這個(gè)接口，實(shí)現(xiàn)用戶相似度的計(jì)算，包括下面這些常用的：

• PearsonCorrelationSimilarity：基于皮爾遜相關(guān)系數(shù)計(jì)算相似度
• EuclideanDistanceSimilarity：基于歐幾里德距離計(jì)算相似度
• TanimotoCoefficientSimilarity：基于 Tanimoto 系數(shù)計(jì)算相似度
• UncerteredCosineSimilarity：計(jì)算 Cosine 相似度

ItemSimilarity 也是類似的：

1. 根據(jù)建立的相似度計(jì)算方法，找到鄰居用戶。這里找鄰居用戶的方法根據(jù)前面我們介紹的，也包括兩種：“固定數(shù)量的鄰居”和“相似度門檻鄰居”計(jì)算方法，Mahout 提供對(duì)應(yīng)的實(shí)現(xiàn)：
   • NearestNUserNeighborhood：對(duì)每個(gè)用戶取固定數(shù)量 N 的最近鄰居
   • ThresholdUserNeighborhood：對(duì)每個(gè)用戶基于一定的限制，取落在相似度門限內(nèi)的所有用戶為鄰居。
2. 基于 DataModel，UserNeighborhood 和 UserSimilarity 構(gòu)建 GenericUserBasedRecommender，實(shí)現(xiàn) User CF 推薦策略。

Item CF

了解了 User CF，Mahout Item CF 的實(shí)現(xiàn)與 User CF 類似，是基于 ItemSimilarity，下面我們看實(shí)現(xiàn)的代碼例子，它比 User CF 更簡(jiǎn)單，因?yàn)?Item CF 中并不需要引入鄰居的概念：

				 
 DataModel model = new FileDataModel(new File("preferences.dat")); 
 ItemSimilarity similarity = new PearsonCorrelationSimilarity(model); 
 Recommender recommender = new GenericItemBasedRecommender(model, similarity); 

Slope One

如前面介紹的，User CF 和 Item CF 是最常用最容易理解的兩種 CF 的推薦策略，但在大數(shù)據(jù)量時(shí)，它們的計(jì)算量會(huì)很大，從而導(dǎo)致推薦效率較差。因此 Mahout 還提供了一種更加輕量級(jí)的 CF 推薦策略：Slope One。

Slope One 是有 Daniel Lemire 和 Anna Maclachlan 在 2005 年提出的一種對(duì)基于評(píng)分的協(xié)同過濾推薦引擎的改進(jìn)方法，下面簡(jiǎn)單介紹一下它的基本思想。

圖 5 給出了例子，假設(shè)系統(tǒng)對(duì)于物品 A，物品 B 和物品 C 的平均評(píng)分分別是 3，4 和 4?；?Slope One 的方法會(huì)得到以下規(guī)律：

• 用戶對(duì)物品 B 的評(píng)分 = 用戶對(duì)物品 A 的評(píng)分 + 1
• 用戶對(duì)物品 B 的評(píng)分 = 用戶對(duì)物品 C 的評(píng)分

基于以上的規(guī)律，我們可以對(duì)用戶 A 和用戶 B 的打分進(jìn)行預(yù)測(cè)：

• 對(duì)用戶 A，他給物品 A 打分 4，那么我們可以推測(cè)他對(duì)物品 B 的評(píng)分是 5，對(duì)物品 C 的打分也是 5。
• 對(duì)用戶 B，他給物品 A 打分 2，給物品 C 打分 4，根據(jù)第一條規(guī)律，我們可以推斷他對(duì)物品 B 的評(píng)分是 3；而根據(jù)第二條規(guī)律，推斷出評(píng)分是 4。當(dāng)出現(xiàn)沖突時(shí)，我們可以對(duì)各種規(guī)則得到的推斷進(jìn)行就平均，所以給出的推斷是 3.5。

這就是 Slope One 推薦的基本原理，它將用戶的評(píng)分之間的關(guān)系看作簡(jiǎn)單的線性關(guān)系：

Y = mX + b;

當(dāng) m = 1 時(shí)就是 Slope One，也就是我們剛剛展示的例子。

Slope One 的核心優(yōu)勢(shì)是在大規(guī)模的數(shù)據(jù)上，它依然能保證良好的計(jì)算速度和推薦效果。Mahout 提供了 Slope One 推薦方法的基本實(shí)現(xiàn)，實(shí)現(xiàn)代碼很簡(jiǎn)單，參考清單 5.

				 
 //In-Memory Recommender 
 DiffStorage diffStorage = new MemoryDiffStorage(model, Weighting.UNWEIGHTED, false, 
 Long.MAX_VALUE)); 
 Recommender recommender = new SlopeOneRecommender(model, Weighting.UNWEIGHTED, 
 Weighting.UNWEIGHTED, diffStorage);  

 //Database-based Recommender 
 AbstractJDBCDataModel model = new MySQLJDBCDataModel(); 
 DiffStorage diffStorage = new MySQLJDBCDiffStorage(model); 
 Recommender recommender = new SlopeOneRecommender(model, Weighting.WEIGHTED, 
 Weighting.WEIGHTED, diffStorage); 

1. 根據(jù) Data Model 創(chuàng)建數(shù)據(jù)之間線性關(guān)系的模型 DiffStorage。

2. 基于 Data Model 和 DiffStorage 創(chuàng)建 SlopeOneRecommender，實(shí)現(xiàn) Slope One 推薦策略。

回頁首

總結(jié)

Web2.0 的一個(gè)核心思想就是“集體智慧”，基于協(xié)同過濾的推薦策略的基本思想就是基于大眾行為，為每個(gè)用戶提供個(gè)性化的推薦，從而使用戶能更快速更準(zhǔn)確的發(fā)現(xiàn)所需要的信息。從應(yīng)用角度分析，現(xiàn)今比較成功的推薦引擎，比如 Amazon，豆瓣，當(dāng)當(dāng)?shù)榷疾捎昧藚f(xié)同過濾的方式，它不需要對(duì)物品或者用戶進(jìn)行嚴(yán)格的建模，而且不要求物品的描述是機(jī)器可理解的，是中領(lǐng)域無關(guān)的推薦方法，同時(shí)這個(gè)方法計(jì)算出來的推薦是開放的，可以共用他人的經(jīng)驗(yàn)，很好的支持用戶發(fā)現(xiàn)潛在的興趣偏好?；趨f(xié)同過濾的推薦策略也有不同的分支，它們有不同的實(shí)用場(chǎng)景和推薦效果，用戶可以根據(jù)自己應(yīng)用的實(shí)際情況選擇合適的方法，異或組合不同的方法得到更好的推薦效果。

除此之外，本文還介紹了如何基于 Apache Mahout 高效實(shí)現(xiàn)協(xié)同過濾推薦算法，Apache Mahout 關(guān)注海量數(shù)據(jù)上的機(jī)器學(xué)習(xí)經(jīng)典算法的高效實(shí)現(xiàn)，其中對(duì)基于協(xié)同過濾的推薦方法也提供了很好的支持，基于 Mahout 你可以輕松的體驗(yàn)高效推薦的神奇。

作為深入推薦引擎相關(guān)算法的第一篇文章，本文深入介紹了協(xié)同過濾算法，并舉例介紹了如何基于 Apache Mahout 高效實(shí)現(xiàn)協(xié)同過濾推薦算法，Apache Mahout 作為海量數(shù)據(jù)上的機(jī)器學(xué)習(xí)經(jīng)典算法的高效實(shí)現(xiàn)，其中對(duì)基于協(xié)同過濾的推薦方法也提供了很好的支持，基于 Mahout 你可以輕松的體驗(yàn)高效推薦的神奇。但我們也發(fā)現(xiàn)了在海量數(shù)據(jù)上高效的運(yùn)行協(xié)同過濾算法以及其他推薦策略這樣高復(fù)雜的算法還是有很大的挑戰(zhàn)的。在面對(duì)這個(gè)問題的過程中，大家提出了很多減少計(jì)算量的方法，而聚類無疑是其中最優(yōu)的選擇。所以本系列的下一篇文章將詳細(xì)介紹各類聚類算法，它們的原理，優(yōu)缺點(diǎn)和實(shí)用場(chǎng)景，并給出基于 Apache Mahout 的聚類算法的高效實(shí)現(xiàn)，并分析在推薦引擎的實(shí)現(xiàn)中，如何通過引入聚類來解決大數(shù)據(jù)量造成的海量計(jì)算，從而提供高效的推薦。