探索推薦引擎内部的秘密-第 2 部分: 深入推薦引擎相關算法 - 協同過濾

本系列的第一篇為讀者概要介紹了推薦引擎，下面幾篇文章将深入介紹推薦引擎的相關算法，并幫助讀者高效的實作這些算法。 在現今的推薦技術和算法中，最被大家廣泛認可和采用的就是基于協同過濾的推薦方法。它以其方法模型簡單，資料依賴性低，資料友善采集 , 推薦效果較優等多個優點成為大衆眼裡的推薦算法“No.1”。本文将帶你深入了解協同過濾的秘密，并給出基于 Apache Mahout 的協同過濾算法的高效實作。Apache Mahout 是 ASF 的一個較新的開源項目，它源于 Lucene，建構在 Hadoop 之上，關注海量資料上的機器學習經典算法的高效實作。

集體智慧和協同過濾

什麼是集體智慧

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

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

Wikipedia 是一個知識管理的百科全書，相對于傳統的由領域專家編輯的百科全書，Wikipedia 允許最終使用者貢獻知識，随着參與人數的增多，Wikipedia 變成了涵蓋各個領域的一本無比全面的知識庫。也許有人會質疑它的權威性，但如果你從另一個側面想這個問題，也許就可以迎刃而解。在發行一本書時，作者雖然是權威，但難免還有一些錯誤，然後通過一版一版的改版，書的内容越來越完善。而在 Wikipedia 上，這種改版和修正被變為每個人都可以做的事情，任何人發現錯誤或者不完善都可以貢獻他們的想法，即便某些資訊是錯誤的，但它一定也會盡快的被其他人糾正過來。從一個宏觀的角度看，整個系統在按照一個良性循環的軌迹不斷完善，這也正是集體智慧的魅力。

Google：目前最流行的搜尋引擎，與 Wikipedia 不同，它沒有要求使用者顯式的貢獻，但仔細想想 Google 最核心的 PageRank 的思想，它利用了 Web 頁面之間的關系，将多少其他頁面連結到目前頁面的數目作為衡量目前頁面重要與否的标準；如果這不好了解，那麼你可以把它想象成一個選舉的過程，每個 Web 頁面都是一個投票者同時也是一個被投票者，PageRank 通過一定數目的疊代得到一個相對穩定的評分。Google 其實利用了現在 Internet 上所有 Web 頁面上連結的集體智慧，找到哪些頁面是重要的。

什麼是協同過濾

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

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

如何确定一個使用者是不是和你有相似的品位？

如何将鄰居們的喜好組織成一個排序的目錄？

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

深入協同過濾的核心

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

首先，要實作協同過濾，需要一下幾個步驟

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

收集使用者偏好

要從使用者的行為和偏好中發現規律，并基于此給予推薦，如何收集使用者的偏好資訊成為系統推薦效果最基礎的決定因素。使用者有很多方式向系統提供自己的偏好資訊，而且不同的應用也可能大不相同，下面舉例進行介紹：

表 1 使用者行為和使用者偏好

使用者行為	類型	特征	作用
評分	顯式	整數量化的偏好，可能的取值是 [0, n]；n 一般取值為 5 或者是 10	通過使用者對物品的評分，可以精确的得到使用者的偏好
投票	顯式	布爾量化的偏好，取值是 0 或 1	通過使用者對物品的投票，可以較精确的得到使用者的偏好
轉發	顯式	布爾量化的偏好，取值是 0 或 1	通過使用者對物品的投票，可以精确的得到使用者的偏好。 如果是站内，同時可以推理得到被轉發人的偏好（不精确）
儲存書簽	顯式	布爾量化的偏好，取值是 0 或 1	通過使用者對物品的投票，可以精确的得到使用者的偏好。
标記标簽  (Tag)	顯式	一些單詞，需要對單詞進行分析，得到偏好	通過分析使用者的标簽，可以得到使用者對項目的了解，同時可以分析出使用者的情感：喜歡還是讨厭
評論	顯式	一段文字，需要進行文本分析，得到偏好	通過分析使用者的評論，可以得到使用者的情感：喜歡還是讨厭
點選流  ( 檢視 )	隐式	一組使用者的點選，使用者對物品感興趣，需要進行分析，得到偏好	使用者的點選一定程度上反映了使用者的注意力，是以它也可以從一定程度上反映使用者的喜好。
頁面停留時間	隐式	一組時間資訊，噪音大，需要進行去噪，分析，得到偏好	使用者的頁面停留時間一定程度上反映了使用者的注意力和喜好，但噪音偏大，不好利用。
購買	隐式	布爾量化的偏好，取值是 0 或 1	使用者的購買是很明确的說明這個項目它感興趣。

在一般應用中，我們提取的使用者行為一般都多于一種，關于如何組合這些不同的使用者行為，基本上有以下兩種方式：以上列舉的使用者行為都是比較通用的，推薦引擎設計人員可以根據自己應用的特點添加特殊的使用者行為，并用他們表示使用者對物品的喜好。

将不同的行為分組：一般可以分為“檢視”和“購買”等等，然後基于不同的行為，計算不同的使用者 / 物品相似度。類似于當當網或者 Amazon 給出的“購買了該圖書的人還購買了 ...”，“檢視了圖書的人還檢視了 ...”

根據不同行為反映使用者喜好的程度将它們進行權重，得到使用者對于物品的總體喜好。一般來說，顯式的使用者回報比隐式的權值大，但比較稀疏，畢竟進行顯示回報的使用者是少數；同時相對于“檢視”，“購買”行為反映使用者喜好的程度更大，但這也因應用而異。

收集了使用者行為資料，我們還需要對資料進行一定的預處理，其中最核心的工作就是：減噪和歸一化。

減噪：使用者行為資料是使用者在使用應用過程中産生的，它可能存在大量的噪音和使用者的誤操作，我們可以通過經典的資料挖掘算法過濾掉行為資料中的噪音，這樣可以是我們的分析更加精确。

歸一化：如前面講到的，在計算使用者對物品的喜好程度時，可能需要對不同的行為資料進行權重。但可以想象，不同行為的資料取值可能相差很大，比如，使用者的檢視資料必然比購買資料大的多，如何将各個行為的資料統一在一個相同的取值範圍中，進而使得權重求和得到的總體喜好更加精确，就需要我們進行歸一化處理。最簡單的歸一化處理，就是将各類資料除以此類中的最大值，以保證歸一化後的資料取值在 [0,1] 範圍中。

進行的預處理後，根據不同應用的行為分析方法，可以選擇分組或者權重處理，之後我們可以得到一個使用者偏好的二維矩陣，一維是使用者清單，另一維是物品清單，值是使用者對物品的偏好，一般是 [0,1] 或者 [-1, 1] 的浮點數值。

找到相似的使用者或物品

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

相似度的計算

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

• 歐幾裡德距離（Euclidean Distance）

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

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

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

• 皮爾遜相關系數（Pearson Correlation Coefficient）

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

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

• Cosine 相似度（Cosine Similarity）

Cosine 相似度被廣泛應用于計算文檔資料的相似度：

• Tanimoto 系數（Tanimoto Coefficient）

Tanimoto 系數也稱為 Jaccard 系數，是 Cosine 相似度的擴充，也多用于計算文檔資料的相似度：

相似鄰居的計算

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

固定數量的鄰居：K-neighborhoods 或者 Fix-size neighborhoods

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

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

與計算固定數量的鄰居的原則不同，基于相似度門檻的鄰居計算是對鄰居的遠近進行最大值的限制，落在以目前點為中心，距離為 K 的區域中的所有點都作為目前點的鄰居，這種方法計算得到的鄰居個數不确定，但相似度不會出現較大的誤差。如圖 1 中的 B，從點 1 出發，計算相似度在 K 内的鄰居，得到點 2，點 3，點 4 和點 7，這種方法計算出的鄰居的相似度程度比前一種優，尤其是對孤立點的處理。

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

計算推薦

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

基于使用者的 CF（User CF）

基于使用者的 CF 的基本思想相當簡單，基于使用者對物品的偏好找到相鄰鄰居使用者，然後将鄰居使用者喜歡的推薦給目前使用者。計算上，就是将一個使用者對所有物品的偏好作為一個向量來計算使用者之間的相似度，找到 K 鄰居後，根據鄰居的相似度權重以及他們對物品的偏好，預測目前使用者沒有偏好的未涉及物品，計算得到一個排序的物品清單作為推薦。圖 2 給出了一個例子，對于使用者 A，根據使用者的曆史偏好，這裡隻計算得到一個鄰居 - 使用者 C，然後将使用者 C 喜歡的物品 D 推薦給使用者 A。

圖 2.基于使用者的 CF 的基本原理

基于物品的 CF（Item CF）

基于物品的 CF 的原理和基于使用者的 CF 類似，隻是在計算鄰居時采用物品本身，而不是從使用者的角度，即基于使用者對物品的偏好找到相似的物品，然後根據使用者的曆史偏好，推薦相似的物品給他。從計算的角度看，就是将所有使用者對某個物品的偏好作為一個向量來計算物品之間的相似度，得到物品的相似物品後，根據使用者曆史的偏好預測目前使用者還沒有表示偏好的物品，計算得到一個排序的物品清單作為推薦。圖 3 給出了一個例子，對于物品 A，根據所有使用者的曆史偏好，喜歡物品 A 的使用者都喜歡物品 C，得出物品 A 和物品 C 比較相似，而使用者 C 喜歡物品 A，那麼可以推斷出使用者 C 可能也喜歡物品 C。

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

User CF vs. Item CF

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

• 計算複雜度

Item CF 和 User CF 是基于協同過濾推薦的兩個最基本的算法，User CF 是很早以前就提出來了，Item CF 是從 Amazon 的論文和專利發表之後（2001 年左右）開始流行，大家都覺得 Item CF 從性能和複雜度上比 User CF 更優，其中的一個主要原因就是對于一個線上網站，使用者的數量往往大大超過物品的數量，同時物品的資料相對穩定，是以計算物品的相似度不但計算量較小，同時也不必頻繁更新。但我們往往忽略了這種情況隻适應于提供商品的電子商務網站，對于新聞，部落格或者微内容的推薦系統，情況往往是相反的，物品的數量是海量的，同時也是更新頻繁的，是以單從複雜度的角度，這兩個算法在不同的系統中各有優勢，推薦引擎的設計者需要根據自己應用的特點選擇更加合适的算法。

• 适用場景

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

相反的，在現今很流行的社交網絡站點中，User CF 是一個更不錯的選擇，User CF 加上社會網絡資訊，可以增加使用者對推薦解釋的信服程度。

• 推薦多樣性和精度

研究推薦引擎的學者們在相同的資料集合上分别用 User CF 和 Item CF 計算推薦結果，發現推薦清單中，隻有 50% 是一樣的，還有 50% 完全不同。但是這兩個算法确有相似的精度，是以可以說，這兩個算法是很互補的。

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

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

第二種度量方法是考慮系統的多樣性，也被稱為覆寫率 (Coverage)，它是指一個推薦系統是否能夠提供給所有使用者豐富的選擇。在這種名額下，Item CF 的多樣性要遠遠好于 User CF, 因為 User CF 總是傾向于推薦熱門的，從另一個側面看，也就是說，Item CF 的推薦有很好的新穎性，很擅長推薦長尾裡的物品。是以，盡管大多數情況，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 領域給使用者，這樣他有限的推薦清單中就可能包含了一定數量的不熱門的長尾物品，同時 Item CF 的推薦對這個使用者而言，顯然多樣性不足。但是對整個系統而言，因為不同的使用者的主要興趣點不同，是以系統的覆寫率會比較好。

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

• 使用者對推薦算法的适應度

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

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

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

通過以上的介紹，相信大家已經對協同過濾推薦的各種方法，原則，特點和适用場景有深入的了解，下面我們就進入實戰階段，重點介紹如何基于 Apache Mahout 實作協同過濾推薦算法。

基于 Apache Mahout 實作高效的協同過濾推薦

Apache Mahout 是 Apache Software Foundation (ASF) 旗下的一個開源項目，提供一些可擴充的機器學習領域經典算法的實作，旨在幫助開發人員更加友善快捷地建立智能應用程式，并且，在 Mahout 的最近版本中還加入了對 Apache Hadoop 的支援，使這些算法可以更高效的運作在雲計算環境中。

關于 Apache Mahout 的安裝和配置請參考《基于 Apache Mahout 建構社會化推薦引擎》，它是筆者 09 年發表的一篇關于基于 Mahout 實作推薦引擎的 developerWorks 文章，其中詳細介紹了 Mahout 的安裝步驟，并給出一個簡單的電影推薦引擎的例子。

Apache Mahout 中提供的一個協同過濾算法的高效實作，它是一個基于 Java 實作的可擴充的，高效的推薦引擎。圖 4 給出了 Apache Mahout 中協同過濾推薦實作的元件圖，下面我們逐漸深入介紹各個部分。

圖 4.元件圖

資料表示：Data Model

Preference

基于協同過濾的推薦引擎的輸入是使用者的曆史偏好資訊，在 Mahout 裡它被模組化為 Preference（接口），一個 Preference 就是一個簡單的三元組 < 使用者 ID, 物品 ID, 使用者偏好 >，它的實作類是 GenericPreference，可以通過以下語句建立一個 GenericPreference。

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

這其中， 123 是使用者 ID，long 型；456 是物品 ID，long 型；3.0f 是使用者偏好，float 型。從這個例子我們可以看出，單單一個 GenericPreference 的資料就占用 20 bytes，是以你會發現如果隻簡單實用數組 Array 加載使用者偏好資料，必然占用大量的記憶體，Mahout 在這方面做了一些優化，它建立了 PreferenceArray（接口）儲存一組使用者偏好資料，為了優化性能，Mahout 給出了兩個實作類，GenericUserPreferenceArray 和 GenericItemPreferenceArray，分别按照使用者和物品本身對使用者偏好進行組裝，這樣就可以壓縮使用者 ID 或者物品 ID 的空間。下面清單 1 的代碼以 GenericUserPreferenceArray 為例，展示了如何建立和使用一個 PreferenceArray。

清單 1. 建立和使用 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 還建構了自己的 HashMap 和 Set：FastByIDMap 和 FastIDSet，有興趣的朋友可以參考 Mahout 官方說明。

DataModel

Mahout 的推薦引擎實際接受的輸入是 DataModel，它是對使用者偏好資料的壓縮表示，通過建立記憶體版 DataModel 的語句我們可以看出：

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

他儲存在一個按照使用者 ID 或者物品 ID 進行散列的 PreferenceArray，而 PreferenceArray 中對應儲存着這個使用者 ID 或者物品 ID 的所有使用者偏好資訊。

DataModel 是使用者喜好資訊的抽象接口，它的具體實作支援從任意類型的資料源抽取使用者喜好資訊，具體實作包括記憶體版的 GenericDataModel，支援檔案讀取的 FileDataModel 和支援資料庫讀取的 JDBCDataModel，下面我們看看如何建立各種 DataModel。

清單 2. 建立各種 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 沒有對檔案的格式做過多的要求，隻要檔案的内容滿足以下格式：

• 每一行包括使用者 ID, 物品 ID, 使用者偏好
• 逗号隔開或者 Tab 隔開
• *.zip 和 *.gz 檔案會自動解壓縮（Mahout 建議在資料量過大時采用壓縮的資料存儲）

支援資料庫讀取的 JDBCDataModel，Mahout 提供一個預設的 MySQL 的支援，它對使用者偏好資料的存放有以下簡單的要求：

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

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

實作推薦：Recommender

介紹完資料表示模型，下面介紹 Mahout 提供的協同過濾的推薦政策，這裡我們選擇其中最經典的三種，User CF, Item CF 和 Slope One。

User CF

前面已經詳細介紹了 User CF 的原理，這裡我們着重看怎麼基于 Mahout 實作 User CF 的推薦政策，我們還是從一個例子入手：

清單 3. 基于 Mahout 實作 User CF

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);
           

從檔案建立 DataModel，我們采用前面介紹的 FileDataModel，這裡假設使用者的喜好資訊存放在 preferences.dat 檔案中。

基于使用者偏好資料計算使用者的相似度，清單中采用的是 PearsonCorrelationSimilarity，前面章節曾詳細介紹了各種計算相似度的方法，Mahout 中提供了基本的相似度的計算，它們都 UserSimilarity 這個接口，實作使用者相似度的計算，包括下面這些常用的：

• PearsonCorrelationSimilarity：基于皮爾遜相關系數計算相似度
• EuclideanDistanceSimilarity：基于歐幾裡德距離計算相似度
• TanimotoCoefficientSimilarity：基于 Tanimoto 系數計算相似度
• UncerteredCosineSimilarity：計算 Cosine 相似度

ItemSimilarity 也是類似的：

根據建立的相似度計算方法，找到鄰居使用者。這裡找鄰居使用者的方法根據前面我們介紹的，也包括兩種：“固定數量的鄰居”和“相似度門檻鄰居”計算方法，Mahout 提供對應的實作：

• NearestNUserNeighborhood：對每個使用者取固定數量 N 的最近鄰居
• ThresholdUserNeighborhood：對每個使用者基于一定的限制，取落在相似度門限内的所有使用者為鄰居。

基于 DataModel，UserNeighborhood 和 UserSimilarity 建構 GenericUserBasedRecommender，實作 User CF 推薦政策。

Item CF

了解了 User CF，Mahout Item CF 的實作與 User CF 類似，是基于 ItemSimilarity，下面我們看實作的代碼例子，它比 User CF 更簡單，因為 Item CF 中并不需要引入鄰居的概念：

清單 4. 基于 Mahout 實作 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 的推薦政策，但在大資料量時，它們的計算量會很大，進而導緻推薦效率較差。是以 Mahout 還提供了一種更加輕量級的 CF 推薦政策：Slope One。

Slope One 是有 Daniel Lemire 和 Anna Maclachlan 在 2005 年提出的一種對基于評分的協同過濾推薦引擎的改進方法，下面簡單介紹一下它的基本思想。

圖 5 給出了例子，假設系統對于物品 A，物品 B 和物品 C 的平均評分分别是 3，4 和 4。基于 Slope One 的方法會得到以下規律：

• 使用者對物品 B 的評分 = 使用者對物品 A 的評分 + 1
• 使用者對物品 B 的評分 = 使用者對物品 C 的評分

基于以上的規律，我們可以對使用者 A 和使用者 B 的打分進行預測：

• 對使用者 A，他給物品 A 打分 4，那麼我們可以推測他對物品 B 的評分是 5，對物品 C 的打分也是 5。
• 對使用者 B，他給物品 A 打分 2，給物品 C 打分 4，根據第一條規律，我們可以推斷他對物品 B 的評分是 3；而根據第二條規律，推斷出評分是 4。當出現沖突時，我們可以對各種規則得到的推斷進行就平均，是以給出的推斷是 3.5。

這就是 Slope One 推薦的基本原理，它将使用者的評分之間的關系看作簡單的線性關系：

Y = mX + b;

當 m = 1 時就是 Slope One，也就是我們剛剛展示的例子。

圖 5.Slope One 推薦政策示例

Slope One 的核心優勢是在大規模的資料上，它依然能保證良好的計算速度和推薦效果。Mahout 提供了 Slope One 推薦方法的基本實作，實作代碼很簡單，參考清單 5.

清單 5. 基于 Mahout 實作 Slope One

//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. 根據 Data Model 建立資料之間線性關系的模型 DiffStorage。

2. 基于 Data Model 和 DiffStorage 建立 SlopeOneRecommender，實作 Slope One 推薦政策。

總結

Web2.0 的一個核心思想就是“集體智慧”，基于協同過濾的推薦政策的基本思想就是基于大衆行為，為每個使用者提供個性化的推薦，進而使使用者能更快速更準确的發現所需要的資訊。從應用角度分析，現今比較成功的推薦引擎，比如 Amazon，豆瓣，當當等都采用了協同過濾的方式，它不需要對物品或者使用者進行嚴格的模組化，而且不要求物品的描述是機器可了解的，是中領域無關的推薦方法，同時這個方法計算出來的推薦是開放的，可以共用他人的經驗，很好的支援使用者發現潛在的興趣偏好。基于協同過濾的推薦政策也有不同的分支，它們有不同的實用場景和推薦效果，使用者可以根據自己應用的實際情況選擇合适的方法，異或組合不同的方法得到更好的推薦效果。

除此之外，本文還介紹了如何基于 Apache Mahout 高效實作協同過濾推薦算法，Apache Mahout 關注海量資料上的機器學習經典算法的高效實作，其中對基于協同過濾的推薦方法也提供了很好的支援，基于 Mahout 你可以輕松的體驗高效推薦的神奇。

作為深入推薦引擎相關算法的第一篇文章，本文深入介紹了協同過濾算法，并舉例介紹了如何基于 Apache Mahout 高效實作協同過濾推薦算法，Apache Mahout 作為海量資料上的機器學習經典算法的高效實作，其中對基于協同過濾的推薦方法也提供了很好的支援，基于 Mahout 你可以輕松的體驗高效推薦的神奇。但我們也發現了在海量資料上高效的運作協同過濾算法以及其他推薦政策這樣高複雜的算法還是有很大的挑戰的。在面對這個問題的過程中，大家提出了很多減少計算量的方法，而聚類無疑是其中最優的選擇。是以本系列的下一篇文章将詳細介紹各類聚類算法，它們的原理，優缺點和實用場景，并給出基于 Apache Mahout 的聚類算法的高效實作，并分析在推薦引擎的實作中，如何通過引入聚類來解決大資料量造成的海量計算，進而提供高效的推薦。