Hadoop環(huán)境下協(xié)同過濾算法的實現(xiàn)

王博文

西北工業(yè)大學(xué)

隨著當(dāng)今互聯(lián)網(wǎng)的而不斷發(fā)展，人們?nèi)绾卧诜倍嗟男畔⒅蝎@取自己需要的內(nèi)容成為了一個至關(guān)重要的問題。推薦系統(tǒng)能夠分析用戶的歷史操作，建立了用戶偏好模型，依靠算法計算預(yù)測用戶對未知商品的偏好權(quán)重，向用戶推送一個可能令其感興趣的商品推薦列表。本文章將介紹基于協(xié)同過濾的推薦策略，并且提供實現(xiàn)基于Hadoop的協(xié)同過濾算法的基本實現(xiàn)方法。

1 協(xié)同過濾推薦算法

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

傳統(tǒng)協(xié)同過濾算法的基本步驟如下：

（1）數(shù)據(jù)表述

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

圖1 用戶-項目矩陣

（2）相似度的計算

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

相關(guān)系數(shù)：

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

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

（3）產(chǎn)生推薦結(jié)果

根據(jù)目標(biāo)用戶的最近鄰用戶的所有評分項，預(yù)測其對項目iy的評分 pay，其中Ny表示目標(biāo)項目的最近鄰，rai表示目標(biāo)用戶對項目ii的評分

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

但以上算法相對較復(fù)雜，實現(xiàn)起來也往往更加困難。因此，當(dāng)開始初步了解推薦系統(tǒng)時，我們更需要一個便于快速實現(xiàn)的推薦系統(tǒng)。

2 Hadoop平臺

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

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

圖2 MapReduce作業(yè)流程圖

3 推薦系統(tǒng)在Hadoop平臺上的實現(xiàn)方法

3.1 傳統(tǒng)協(xié)同過濾算法在Hadoop平臺上的局限性

相似度的計算，是整個推薦系統(tǒng)實現(xiàn)的一個核心技術(shù)，通過分析一些傳統(tǒng)的協(xié)同過濾算法，我們發(fā)現(xiàn)這些算法的往往不適合MapReduce編程框架下的實現(xiàn)。

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

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

3.2 共詞分析方法實現(xiàn)基于物品的CF

算法的基本思想如下：

1）建立用戶與物品的同現(xiàn)矩陣

同現(xiàn)矩陣就是通過統(tǒng)計兩個項目共同出現(xiàn)在同一個元組的次數(shù)，通過統(tǒng)計同現(xiàn)次數(shù)，表達這兩個項目之間的緊密相似程度。

2）建立用戶的評分矩陣

3）計算同現(xiàn)矩陣與評分矩陣相乘

4）將結(jié)果推薦給用戶

這種推薦系統(tǒng)的實現(xiàn)算法的核心思想是推薦結(jié)果=同現(xiàn)矩陣*評分矩陣。

如下圖：

圖3 推薦結(jié)果=同現(xiàn)矩陣*評分矩陣

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

3.3 算法的設(shè)計與實現(xiàn)

以Grouplens網(wǎng)站下載的視頻數(shù)據(jù)Movielens1M為例，里面存儲了電影信息，評分信息以及用戶信息。為了推薦給用戶最迎合他們興趣的電影，我們需要實現(xiàn)這個推薦系統(tǒng)。

這里我們要提到Mahout，Mahout是Apache旗下的一個機器學(xué)習(xí)與數(shù)據(jù)挖掘的框架，包括了聚類，分類，協(xié)同過濾與關(guān)聯(lián)規(guī)則挖掘等經(jīng)典算法。Mahout提供了現(xiàn)有的算法接口，因此可以大大方便了推薦系統(tǒng)的實現(xiàn)。

基本步驟：

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

Mapper函數(shù) value：User_IDKey：Iterm_ID:Score

Reduce函數(shù) value：User_IDKey：List

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

Mapper函數(shù) value：Iterm_ID:Iterm_IDKey：1

Reduce函數(shù) value：Iterm_ID:Iterm_IDKey：累計出現(xiàn)的次數(shù)

第三步：根據(jù)第一步的輸出生成評分矩陣和根據(jù)第二步的輸出生成同現(xiàn)矩陣。

Mapper函數(shù)(生成同現(xiàn)矩陣)value：Iterm_ID:Iterm_IDKey：num

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

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

Mapper函數(shù)（計算） value：User_IDKey：Iterm_ID:Score

Combiner函數(shù)（分?jǐn)?shù)累計）value：User_IDKey：Iterm_ID:Score

Reduce函數(shù)（根據(jù)總分排序） value：User_IDKey：Iterm_ID:Score

4 結(jié)語

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

[1]唐真.基于hadoop的推薦系統(tǒng)設(shè)計與實現(xiàn)[D].成都：電子科技大學(xué)，2013.

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

[3]鄭健.基于Hadoop的協(xié)同過濾推薦系統(tǒng)研究與實現(xiàn)[D].北京：北京郵電大學(xué)，2014.

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

[5]李偉衛(wèi).基于Hadoop平臺的數(shù)據(jù)挖掘技術(shù)研究[D].西安：西北農(nóng)林大學(xué)，2013.

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

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