王博文

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

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

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

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

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

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

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

圖1 用戶-項(xiàng)目矩陣

（2）相似度的計(jì)算

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

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

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

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

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

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

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

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

2 Hadoop平臺(tái)

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

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

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

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

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

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

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

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

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

算法的基本思想如下：

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

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

2）建立用戶的評(píng)分矩陣

3）計(jì)算同現(xiàn)矩陣與評(píng)分矩陣相乘

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

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

如下圖：

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

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

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

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

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

基本步驟：

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

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

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

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

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

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

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