Hadoop環境下協同過濾算法的實現

王博文

西北工業大學

隨著當今互聯網的而不斷發展，人們如何在繁多的信息中獲取自己需要的內容成為了一個至關重要的問題。推薦系統能夠分析用戶的歷史操作，建立了用戶偏好模型，依靠算法計算預測用戶對未知商品的偏好權重，向用戶推送一個可能令其感興趣的商品推薦列表。本文章將介紹基于協同過濾的推薦策略，并且提供實現基于Hadoop的協同過濾算法的基本實現方法。

1 協同過濾推薦算法

協同過濾(Collaborative Filtering,簡稱CF)是利用集體智慧的一個典型方法。協同過濾算法主要分為基于用戶的協同過濾算法與基于項目的協同過濾算法，其實質是極為相似的。該算法通過分析所有用戶的歷史行為，生成項目—用戶矩陣；根據項目之間的相似度，計算項目的最近N鄰居；根據最近N鄰居和被預測用戶的歷史行為，預測用戶對新項目的評分，并產生推薦列表。基于用戶的CF的基本思想相當簡單，基于用戶對物品的偏好找到相鄰鄰居用戶，然后將鄰居用戶喜歡的推薦給當前用戶。基于物品的CF的原理和基于用戶的CF類似，只是在計算鄰居時采用物品本身，而不是從用戶的角度，即基于用戶對物品的偏好找到相似的物品，然后根據用戶的歷史偏好，推薦相似的物品給他。

傳統協同過濾算法的基本步驟如下：

（1）數據表述

根據不同的用戶對不同項目的評分，將輸入數據表述為一個M*N的用戶—項目評分矩陣R，M是用戶數，N是項目數，矩陣元素Rij表示第i個用戶對第j個項目的評分。

圖1 用戶-項目矩陣

（2）相似度的計算

得出目標項目的最鄰近集合，即計算某項目與其它項目的相似度，根據相似度的大小進行排序從而確定目標項目的最鄰近，比較常用的方法有以下幾種：

相關系數：

其中Uij表示對Ii表達偏好的用戶集合與對Ij表達偏好的用戶集合的交集；-PI，----PJ分別表示對Ii，Ij的平均偏好。余弦相似度計算：

通過以上幾種方法，我們就可以得到各項目之間的相似度，并且依據相似度，確定其最近鄰。

（3）產生推薦結果

根據目標用戶的最近鄰用戶的所有評分項，預測其對項目iy的評分 pay，其中Ny表示目標項目的最近鄰，rai表示目標用戶對項目ii的評分

得出用戶對所有項目的預測評分后，根據pay的大小排序，給出最佳的推薦結果給用戶。

但以上算法相對較復雜，實現起來也往往更加困難。因此，當開始初步了解推薦系統時，我們更需要一個便于快速實現的推薦系統。

2 Hadoop平臺

Hadoop平臺是Apache基金會對于云計算創建的解決方案。Hadoop的核心包括HDFS與MapReduce，分別是Google公司提出的GFS和MapReduce理論的開源實現。HDFS是分布式存儲系統，可以實現對超大文件的存儲與管理。MapReduce是建立在HDFS上的一個可用于大規模數據集并行計算的軟件編程框架。Hadoop平臺的主從式架構可以運行在幾十或者幾百甚至更多臺計算機上，能充分利用節點擴展存儲和計算資源。

MapReduce是Google提出的一個編程框架，用于大規模數據集的并行運算。其核心作業為Map與Reduce兩個階段。Map階段將輸入數據進行分布式處理映射成鍵值對，經過一定處理后交給Reduce階段，然后Reduce對key值相同的value進行處理后再輸出鍵值作為最后的結果。

圖2 MapReduce作業流程圖

3 推薦系統在Hadoop平臺上的實現方法

3.1 傳統協同過濾算法在Hadoop平臺上的局限性

相似度的計算，是整個推薦系統實現的一個核心技術，通過分析一些傳統的協同過濾算法，我們發現這些算法的往往不適合MapReduce編程框架下的實現。

以皮爾遜算法為例，我們需要預先計算出來每一個-PI，----PJ，而且計算公式相對復雜，因此要在MapReduce下實現，頗為困難。

而且，在通常的商業運行情況下，用戶的數量會遠遠的大于項目的數量，例如淘寶網。因此建立項目-用戶矩陣往往存在著矩陣過于龐大的問題，極大的制約了系統的性能。因此，我們需要考慮一種更加適合的算法來實現。

3.2 共詞分析方法實現基于物品的CF

算法的基本思想如下：

1）建立用戶與物品的同現矩陣

同現矩陣就是通過統計兩個項目共同出現在同一個元組的次數，通過統計同現次數，表達這兩個項目之間的緊密相似程度。

2）建立用戶的評分矩陣

3）計算同現矩陣與評分矩陣相乘

4）將結果推薦給用戶

這種推薦系統的實現算法的核心思想是推薦結果=同現矩陣*評分矩陣。

如下圖：

圖3 推薦結果=同現矩陣*評分矩陣

與其他的計算相似度的算法相比，這種方法的計算復雜度明顯降低，實現起來也更加容易。尤其是在Hadoop環境下，MapRe?duce編程框架非常適合大規模矩陣運算。而且，將項目-用戶矩陣改為同現矩陣，可以減小矩陣運算的規模，提高運算的速度，這對于推薦系統來說，是極為重要的。

3.3 算法的設計與實現

以Grouplens網站下載的視頻數據Movielens1M為例，里面存儲了電影信息，評分信息以及用戶信息。為了推薦給用戶最迎合他們興趣的電影，我們需要實現這個推薦系統。

這里我們要提到Mahout，Mahout是Apache旗下的一個機器學習與數據挖掘的框架，包括了聚類，分類，協同過濾與關聯規則挖掘等經典算法。Mahout提供了現有的算法接口，因此可以大大方便了推薦系統的實現。

基本步驟：

第一步：讀入數據，根據用戶的ID分組，從而進一步生成評分矩陣。

Mapper函數 value：User_IDKey：Iterm_ID:Score

Reduce函數 value：User_IDKey：List

第二步：分別計算兩個物品同時出現的次數，從而進一步生成同現矩陣。

Mapper函數 value：Iterm_ID:Iterm_IDKey：1

Reduce函數 value：Iterm_ID:Iterm_IDKey：累計出現的次數

第三步：根據第一步的輸出生成評分矩陣和根據第二步的輸出生成同現矩陣。

Mapper函數(生成同現矩陣)value：Iterm_ID:Iterm_IDKey：num

Mapper函數（生成評分矩陣）value：Iterm_ID:Iterm_IDKey：Us?er_ID:Preference

第四步：矩陣相乘，得到推薦得分，最后根據得分排序，輸出。

Mapper函數（計算） value：User_IDKey：Iterm_ID:Score

Combiner函數（分數累計）value：User_IDKey：Iterm_ID:Score

Reduce函數（根據總分排序） value：User_IDKey：Iterm_ID:Score

4 結語

本文總結了一種基于Hadoop平臺的協同過濾推薦算法的快速實現方法，有助于入門機器學習和數據挖掘領域。目前大數據行業的快速發展，為我們提供了越來越多的開發工具與手段。例如，應用Hadoop云計算平臺可以更輕松的實現并行計算，以加快計算速度，并且還可以隨著計算規模的增加，動態的擴展集群計算能力。這都為推薦系統的更高效快速的實現，提供了條件。推薦系統是一個擁有無限潛力與良好發展前景的領域，需要更多人來進入這個領域，推進這個領域的發展。

[1]唐真.基于hadoop的推薦系統設計與實現[D].成都：電子科技大學，2013.

[2]桑治平，何聚厚.基于Hadoop的多特征協同過濾算法研究[J].計算機應用研究.201432（12）：3621-3624.

[3]鄭健.基于Hadoop的協同過濾推薦系統研究與實現[D].北京：北京郵電大學，2014.

[4]White T.Hadoop:The Definitive Guide[M].The3rdEdition.USA:O’Reilly Media，2012.

[5]李偉衛.基于Hadoop平臺的數據挖掘技術研究[D].西安：西北農林大學，2013.

[6]肖強，朱慶華，鄭華，吳克文.Hadoop環境下的分布式協同過濾算法設計與實現[J].現代圖書情報技術.2013（01）：83-89.

[7]楊志文，劉波.基于Hadoop平臺協同過濾推薦算法[J].計算機系統應用.2013，32（07）：108-112.