曾志浩　張瓊林　姚貝　孫琪

摘要：隨著信息技術(shù)和互聯(lián)網(wǎng)的發(fā)展，在信息過(guò)載的時(shí)代，用戶面對(duì)海量的信息，難以正確選擇。協(xié)同過(guò)濾推薦是個(gè)性化推薦中比較成熟的算法，但其稀疏性、冷啟動(dòng)、可擴(kuò)展性問(wèn)題仍然存在，尤其是不能應(yīng)用于分布式推薦。在Hadoop平臺(tái)上，Mahout實(shí)現(xiàn)了分布式基于項(xiàng)目的協(xié)同過(guò)濾推薦算法，該算法能夠有效解決傳統(tǒng)算法的海量數(shù)據(jù)處理的效率問(wèn)題和可擴(kuò)展性問(wèn)題。實(shí)驗(yàn)結(jié)果表明，Mahout上基于項(xiàng)目的協(xié)同過(guò)濾推薦算法具有較好的計(jì)算高效性和可擴(kuò)展性。

關(guān)鍵詞：分布式協(xié)同過(guò)濾；Mahout；推薦系統(tǒng)

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

1引言

互聯(lián)網(wǎng)和電子商務(wù)系統(tǒng)的興起與發(fā)展，將人們帶入了網(wǎng)絡(luò)經(jīng)濟(jì)發(fā)展時(shí)代，同時(shí)網(wǎng)絡(luò)中的信息量也在爆炸式地增長(zhǎng)。網(wǎng)絡(luò)信息雖然給人們帶來(lái)了更多的選擇，但數(shù)量龐大及自身質(zhì)量差異，越來(lái)越呈現(xiàn)一種信息過(guò)載的趨勢(shì)，使得如何從這些海量信息中識(shí)別出真正有價(jià)值的信息變得越來(lái)越困難。然而，推薦系統(tǒng)的出現(xiàn)改變了這一狀況，尤其是個(gè)性化推薦服務(wù)技術(shù)的發(fā)展，成為解決信息過(guò)載問(wèn)題最有效的工具，它能夠收集和分析用戶的信息，主動(dòng)地推薦用戶可能感興趣的信息。

個(gè)性化推薦中的協(xié)同過(guò)濾推薦是比較成功的一種，它的概念是由Goldberg、Nicols、Oki以及Terry在1992年首次提出的，主要思想是，利用已有用戶群過(guò)去的行為或意見(jiàn)預(yù)測(cè)當(dāng)前用戶最可能喜歡哪些東西或?qū)δ男〇|西感興趣。不到兩年，Grouplens系統(tǒng)展示了協(xié)同過(guò)濾方法既能跨網(wǎng)計(jì)算又能自動(dòng)完成，該系統(tǒng)是基于用戶評(píng)分的自動(dòng)化協(xié)同過(guò)濾推薦系統(tǒng)，用于推薦電影和新聞。麻省理工學(xué)院的Ringo系統(tǒng)針對(duì)音樂(lè)唱片和藝術(shù)家進(jìn)行推薦。雖然傳統(tǒng)的協(xié)同過(guò)濾推薦算法在信息過(guò)濾方面呈現(xiàn)出了極大的優(yōu)勢(shì)，但隨著信息量的增加，算法在不同領(lǐng)域的應(yīng)用中出現(xiàn)了很多的問(wèn)題，包括稀疏性問(wèn)題、冷啟動(dòng)問(wèn)題、可擴(kuò)展性問(wèn)題。

為了解決這些問(wèn)題，文獻(xiàn)基于動(dòng)態(tài)規(guī)劃思想，根據(jù)用戶以及產(chǎn)品的相似性，自適應(yīng)地選擇預(yù)測(cè)目標(biāo)的近鄰對(duì)象作為推薦群，同時(shí)計(jì)算把握率較高的信任子群，提出了一種不確定近鄰的協(xié)同過(guò)濾推薦算法，來(lái)對(duì)預(yù)測(cè)結(jié)果進(jìn)行平衡的推薦，有效緩解了用戶評(píng)分?jǐn)?shù)據(jù)稀疏的情況。文獻(xiàn)在基于弱關(guān)系的微博類社交網(wǎng)絡(luò)中，提出兩階段聚類的推薦算法GCCR，將圖摘要方法和基于內(nèi)容相似度的算法相結(jié)合，實(shí)現(xiàn)基于用戶興趣的主題推薦，有效緩解了矩陣稀疏性和冷啟動(dòng)問(wèn)題。文獻(xiàn)采用傳播的思想，提出了一種改進(jìn)的基于內(nèi)存的協(xié)同過(guò)濾推薦算法SPCF，該算法通過(guò)相似度傳播，尋找到更多，更可靠的鄰居，從用戶和項(xiàng)目?jī)煞矫嫘畔⒖紤]對(duì)用戶進(jìn)行推薦，緩解了數(shù)據(jù)稀疏性問(wèn)題。

傳統(tǒng)的協(xié)同過(guò)濾推薦算法雖然從一定程度上減少了矩陣稀疏和冷啟動(dòng)問(wèn)題，但隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大，可擴(kuò)展性方面仍然表現(xiàn)的比較差，無(wú)法適應(yīng)海量數(shù)據(jù)的處理，尤其是無(wú)法應(yīng)用于分布式平臺(tái)。為此，國(guó)內(nèi)外研究者進(jìn)行了一系列的研究，這些研究大多是針對(duì)Hadoop平臺(tái)和MapReduce并行編程模型，提出相關(guān)的分布式協(xié)同過(guò)濾算法。文獻(xiàn)提出了MapReduce范式可擴(kuò)展的基于相似性的鄰居算法，該算法中，針對(duì)分割數(shù)據(jù)設(shè)計(jì)出運(yùn)行在并行處理平臺(tái)上的基本比較對(duì)，并采用降低采用率的interaction-cut技術(shù)，處理“超級(jí)用戶”的計(jì)算開(kāi)銷，有效地解決了用戶或項(xiàng)目大規(guī)模增長(zhǎng)的情況下擴(kuò)展性和產(chǎn)生推薦的速度問(wèn)題。文獻(xiàn)針對(duì)基于User-based的協(xié)同過(guò)濾算法的伸縮性問(wèn)題，實(shí)現(xiàn)了基于Hadoop平臺(tái)的User-based協(xié)同過(guò)濾算法，從而實(shí)現(xiàn)了算法的線性伸縮。文獻(xiàn)提出了Hadoop平臺(tái)上擴(kuò)展的Item-based協(xié)同過(guò)濾推薦算法，將單機(jī)上基于項(xiàng)目的協(xié)同過(guò)濾算法的三個(gè)最密集的計(jì)算分割為四個(gè)MapReduce階段，有效地解決了文獻(xiàn)提出的算法的擴(kuò)展性和效率問(wèn)題，但是MapReduce階段的項(xiàng)目相似度計(jì)算要求兩個(gè)項(xiàng)目在同一節(jié)點(diǎn)機(jī)器上，并且要求用戶數(shù)量遠(yuǎn)大于項(xiàng)目數(shù)量，對(duì)于項(xiàng)目不斷增長(zhǎng)的情況下，會(huì)增加算法的計(jì)算量。

本文所要介紹的就是Mahout在Hadoop框架下基于項(xiàng)目的協(xié)同過(guò)濾推薦算法的實(shí)現(xiàn)，該算法是基于MapReduce并行編程模型，不僅有效地解決了在海量數(shù)據(jù)下算法處理的效率問(wèn)題，而且解決了隨著大量用戶和項(xiàng)目的增加產(chǎn)生的可擴(kuò)展性問(wèn)題。

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

協(xié)同過(guò)濾推薦算法主要包括基于用戶和項(xiàng)目的推薦，其中基于項(xiàng)目的協(xié)同過(guò)濾推薦算法是目前業(yè)界應(yīng)用最多的算法，所以本節(jié)內(nèi)容以基于項(xiàng)目的協(xié)同過(guò)濾推薦算法為介紹對(duì)象，它主要分析用戶的行為記錄來(lái)計(jì)算項(xiàng)目之問(wèn)的相似度。推薦系統(tǒng)首先建立基于項(xiàng)目的數(shù)據(jù)模型，然后針對(duì)目標(biāo)項(xiàng)目計(jì)算項(xiàng)目與項(xiàng)目之間的相似性，得到目標(biāo)項(xiàng)目的若干最近鄰，最后根據(jù)最近鄰來(lái)預(yù)測(cè)用戶對(duì)項(xiàng)目的評(píng)分，產(chǎn)生對(duì)應(yīng)的推薦列表。

2.1相似性度量方法

相似性度量方法是計(jì)算用戶或項(xiàng)目問(wèn)的相似性計(jì)算，本節(jié)內(nèi)容是以項(xiàng)目之問(wèn)的相似的研究為例，即基于項(xiàng)目的協(xié)同過(guò)濾算法?；陧?xiàng)目i和項(xiàng)目j通常有3種相似性度量方法：標(biāo)準(zhǔn)的余弦相似性（式（1））、修正的余弦相似性（式（2））、相關(guān)相似性（式（3））。其中，R_u，i表示用戶u對(duì)項(xiàng)目i的評(píng)分，R_i和R_j分別表示項(xiàng)目i和項(xiàng)目j上所有用戶的平均評(píng)分，U_ij為項(xiàng)目i和項(xiàng)目j共同評(píng)分的用戶集合，U_i和U_j分別為項(xiàng)目i和項(xiàng)目j評(píng)分的用戶集合。

2.2產(chǎn)生推薦

基于項(xiàng)目i的k個(gè)最近鄰居，采用基于項(xiàng)目均值的加權(quán)平均值Pu，i，來(lái)預(yù)測(cè)用戶u對(duì)其未評(píng)分或?yàn)g覽項(xiàng)目的評(píng)分。

其中，kNN_i表示項(xiàng)目i的k最近鄰居集合，R_i，R_i分別表示項(xiàng)目i和j上所有用戶打分的平均值。

3Mahout中分布式協(xié)同過(guò)濾推薦算法實(shí)現(xiàn)

3.1Hadoop和Mahout開(kāi)源框架

Hadoop是Apache軟件基金會(huì)旗下的一個(gè)開(kāi)源分布式計(jì)算平臺(tái)。Hadoop以分布式文件系統(tǒng)HDFS和MapReduce為核心，為用戶提供了系統(tǒng)底層細(xì)節(jié)透明的分布式基礎(chǔ)架構(gòu)。HDFS的高容錯(cuò)性、高伸縮性等優(yōu)點(diǎn)允許用戶將Hadoop部署在低廉的硬件上，形成分布式系統(tǒng)；MapReduce分布式編程模型允許用戶在不了解分布式系統(tǒng)底層細(xì)節(jié)的情況下開(kāi)發(fā)并行應(yīng)用程序。所以用戶可以利用Hadoop輕松地組織計(jì)算機(jī)資源，從而搭建自己的分布式計(jì)算平臺(tái)，并且可以充分利用集群的計(jì)算和存儲(chǔ)能力，完成海量數(shù)據(jù)的處理。

Mahout是2008年作為Apache Lucene的子項(xiàng)目出現(xiàn)的，到2010年4月成為了Apache的頂級(jí)開(kāi)源項(xiàng)目。Apache Mahout的分布式計(jì)算的主要目標(biāo)是建立可伸縮性的機(jī)器學(xué)習(xí)算法，通過(guò)Map Reduce模式運(yùn)行在Hadoop平臺(tái)上。目前Apache Mahout項(xiàng)目包含聚類、分類、協(xié)同過(guò)濾推薦、頻繁子項(xiàng)挖掘和頻繁模式挖掘五個(gè)部分。

本文意在結(jié)合Hadoop平臺(tái)和Mahout開(kāi)源框架，對(duì)Mahout中分布式基于項(xiàng)目的協(xié)同過(guò)濾推薦算法進(jìn)行分析并通過(guò)實(shí)驗(yàn)實(shí)現(xiàn)其算法。

3.2算法實(shí)現(xiàn)

在Mahout中，實(shí)現(xiàn)的是基于項(xiàng)目的分布式協(xié)同過(guò)濾算法，該算法一共包含6個(gè)過(guò)程，這個(gè)6個(gè)過(guò)程使用了7個(gè)Map Reduce的Job任務(wù)來(lái)進(jìn)行數(shù)據(jù)處理。數(shù)據(jù)流程圖如圖1所示：

1）用戶矩陣

用戶矩陣的求解過(guò)程，就是針對(duì)圖1的用戶一項(xiàng)目評(píng)分矩陣的一個(gè)數(shù)據(jù)抽取過(guò)程，把同一個(gè)用戶評(píng)價(jià)過(guò)的所有項(xiàng)目進(jìn)行整合，針對(duì)每個(gè)用戶，形成用戶分向量itemid：pref，含義為項(xiàng)目ID：用戶評(píng)價(jià)，然后形成每個(gè)用戶的用戶向量，最終形成用戶矩陣。Mahout中使用了一個(gè)Job任務(wù)來(lái)進(jìn)行形成用戶向量的數(shù)據(jù)處理，輸出key/value對(duì)的格式是，其中的Long Writable和Vector Writable分別對(duì)應(yīng)的是itemid和用戶向量的格式。

2）項(xiàng)目矩陣

項(xiàng)目矩陣的求解過(guò)程和用戶矩陣的求解過(guò)程很相似，但兩者抽取的規(guī)則不一樣，針對(duì)每個(gè)項(xiàng)目，形成項(xiàng)目分向量userid：pref。同樣在Mahout中也使用了一個(gè)Job任務(wù)來(lái)進(jìn)行形成項(xiàng)目矩陣的數(shù)據(jù)處理，輸出的key/value對(duì)的格式是，其中的IntWritable和VectorWritable分別對(duì)應(yīng)的是userid和項(xiàng)目向量的格式。

3）項(xiàng)目矩陣平方和

在Mahout中使用了一個(gè)Job任務(wù)來(lái)對(duì)4.2中的項(xiàng)目矩陣求解平方和，針對(duì)每個(gè)項(xiàng)目的項(xiàng)目向量，項(xiàng)目矩陣平方和的求解方法為求解項(xiàng)目向量的模的平方。

4）項(xiàng)目相似度矩陣

項(xiàng)目相似度矩陣的求解在Mahout中是由兩個(gè)Job任務(wù)共同處理完成的，第一個(gè)Job任務(wù)是計(jì)算項(xiàng)目與項(xiàng)目之問(wèn)的相似度，假設(shè)有N個(gè)項(xiàng)目，首先計(jì)算項(xiàng)目1和項(xiàng)目2的相似度，以此類推，最后計(jì)算項(xiàng)目1與項(xiàng)目N的相似度，但要注意的是，在計(jì)算項(xiàng)目2與項(xiàng)目1的相似度時(shí)，因?yàn)樵谟?jì)算項(xiàng)目1與其它項(xiàng)目相似度時(shí)已經(jīng)計(jì)算過(guò)與項(xiàng)目2的相似度了，所以項(xiàng)目2只需計(jì)算除項(xiàng)目1以外的與其它項(xiàng)目的相似度。第二個(gè)Job任務(wù)是續(xù)接，所謂續(xù)接就是把沒(méi)有計(jì)算相似度的項(xiàng)目加入到其它項(xiàng)目中去，例如在第一個(gè)Job任務(wù)中，計(jì)算項(xiàng)目2與其它項(xiàng)目相似度時(shí)是沒(méi)有計(jì)算與項(xiàng)目1的相似度，所以必須將項(xiàng)目1與項(xiàng)目2的相似度續(xù)接到項(xiàng)目2中，最后輸出形成項(xiàng)目相似度矩陣表。項(xiàng)目相似度的計(jì)算公式如下：

其中，i₁，i₂分別代表項(xiàng)目1和項(xiàng)目2，U代表兩個(gè)項(xiàng)目共同有過(guò)平方的用戶集，P_ui1，代表用戶u對(duì)項(xiàng)目1的評(píng)分，P_ui2代表用戶u對(duì)項(xiàng)目2的評(píng)分，Sim代表的是兩個(gè)項(xiàng)目的相似度，squssub>i₁是對(duì)應(yīng)的項(xiàng)目1的平方和。

5）用戶一項(xiàng)目相似度矩陣

用戶一項(xiàng)目相似度矩陣是結(jié)合用戶矩陣和項(xiàng)目相似度矩陣，為每一個(gè)用戶生成用戶一項(xiàng)目向量，Mahout使用了一個(gè)Job任務(wù)來(lái)對(duì)這些矩陣進(jìn)行處理，輸出key/value對(duì)的格式為，IntWritable和VectorAndPrefsWritable分別是用戶和用戶一項(xiàng)目相似度矩陣對(duì)應(yīng)的格式。

6）用戶推薦矩陣

用戶推薦矩陣是由Mahout中的一個(gè)Job任務(wù)根據(jù)用戶一項(xiàng)目相似度矩陣計(jì)算產(chǎn)生的，推薦矩陣中為每一個(gè)用戶產(chǎn)生一個(gè)推薦向量，推薦向量由多個(gè)推薦項(xiàng)目及其預(yù)測(cè)評(píng)分組成，計(jì)算公式如下：

其中，simi_Im是用戶U₁針對(duì)項(xiàng)目Im的相似度矩陣，M為用戶評(píng)價(jià)過(guò)的項(xiàng)目集，pref_Im是用戶U₁針對(duì)項(xiàng)目Im的評(píng)分，公式（7）只是求用戶U₁的推薦向量，然而，可以用公式（7）為所有用戶求得推薦矩陣。

4實(shí)驗(yàn)結(jié)果及其分析

4.1實(shí)驗(yàn)配置和數(shù)據(jù)集

經(jīng)分析，在小數(shù)據(jù)集條件下通過(guò)偽分布式模式或小集群的Hadoop分布式模式調(diào)試的工程，可以勝任完全分布式模式下的大數(shù)據(jù)集分布式計(jì)算的任務(wù)。本實(shí)驗(yàn)在一臺(tái)臺(tái)式機(jī)上建立三臺(tái)虛擬機(jī)，并通過(guò)這三臺(tái)虛擬機(jī)建立3個(gè)節(jié)點(diǎn)的Hadoop集群，其中包括1個(gè)Master節(jié)點(diǎn)，2個(gè)Slave節(jié)點(diǎn)，臺(tái)式機(jī)具體配置信息如下：Intel（R）Pentium（R）CPUG2030@3.00GHz，6GRAM，80G硬盤。虛擬機(jī)操作系統(tǒng)為Ubuntu12.04，Hadoop版本為1.1.2，Mahout版本為Mahout-0.8。在我們的實(shí)驗(yàn)中，將每個(gè)Slave節(jié)點(diǎn)的map和reduce任務(wù)支持的最大數(shù)都設(shè)置為4，由于map和reduce任務(wù)不是同時(shí)執(zhí)行，所以整個(gè)集群可以支持8個(gè)map和8個(gè)reduce任務(wù)，實(shí)驗(yàn)中將這些map和reduce任務(wù)視為計(jì)算節(jié)點(diǎn)數(shù)。

本實(shí)驗(yàn)采用MovieLens數(shù)據(jù)集（http：//grou-plens.org/datasets/movielens）。MovieLens是一個(gè)基于Web的研究型推薦系統(tǒng)，用于接收用戶對(duì)電影的評(píng)分并提供相應(yīng)的電影推薦列表。我們選取的數(shù)據(jù)集包含6040個(gè)用戶對(duì)3952部電影上的1000209條評(píng)分記錄，其中，每個(gè)用戶至少對(duì)20部電影進(jìn)行了評(píng)分。另外，引入了稀疏等級(jí)的概念，其定義為用戶評(píng)分?jǐn)?shù)據(jù)矩陣中未評(píng)分條目所占的百分比，實(shí)驗(yàn)數(shù)據(jù)集的稀疏等級(jí)為1-1000209/（6040*3952）-0.9581。

4.2性能評(píng)估

首先，在相同的數(shù)據(jù)集上針對(duì)不同等級(jí)的用戶數(shù)量，比較單機(jī)和分布式的基于項(xiàng)目協(xié)同過(guò)濾推薦算法的推薦時(shí)間，并評(píng)估算法效率；然后利用分布式的推薦算法的加速比，隨著計(jì)算節(jié)點(diǎn)數(shù)的增加，評(píng)估固定數(shù)據(jù)規(guī)模下算法運(yùn)行的性能變化情況，并驗(yàn)證算法的可擴(kuò)展性。

1）推薦算法時(shí)間比較

本實(shí)驗(yàn)的MovieLens數(shù)據(jù)有1000209條用戶評(píng)分記錄，為了方便觀察單機(jī)與分布式推薦時(shí)問(wèn)的比較結(jié)果，將數(shù)據(jù)分為7個(gè)等級(jí)，如表1所示，數(shù)據(jù)等級(jí)分別選取500、1000、2000、3000、4000、5000、6000、6040個(gè)用戶。實(shí)驗(yàn)就是分別對(duì)這7個(gè)等級(jí)的用戶的評(píng)分記錄數(shù)量進(jìn)行處理，為所有用戶推薦至多3個(gè)項(xiàng)目，然后比較不同條件下的推薦時(shí)問(wèn)，如圖2所示：

其中，橫坐標(biāo)表示為用戶數(shù)量，縱坐標(biāo)表示為對(duì)應(yīng)不同用戶數(shù)量推薦項(xiàng)目的推薦時(shí)間，以分鐘為單位。從圖2中可以看出，針對(duì)單機(jī)和兩節(jié)點(diǎn)的推薦時(shí)間比較接近，這是因?yàn)樵趦晒?jié)點(diǎn)的Hadoop集群環(huán)境下，只有一個(gè)主節(jié)點(diǎn)和一個(gè)從節(jié)點(diǎn)，節(jié)點(diǎn)之間除了必要的數(shù)據(jù)處理任務(wù)外，還要調(diào)度集群資源，以便合理的安排任務(wù)。三節(jié)點(diǎn)的集群整體的推薦時(shí)間要優(yōu)于前兩者，推薦項(xiàng)目時(shí)能節(jié)省很多的時(shí)間，可以得知，集群規(guī)模越大，計(jì)算的時(shí)間越少，對(duì)于單機(jī)需要幾個(gè)小時(shí)才能處理的數(shù)據(jù)，如果集群規(guī)模有上百臺(tái)，那么只需要幾分鐘就能夠?qū)?shù)據(jù)處理完，這說(shuō)明集群更適合處理海量的數(shù)據(jù)，并且效率更高。

2）加速比

加速比性能分析的計(jì)算公式如（8）所示。其中T₁代表的是單個(gè)計(jì)算節(jié)點(diǎn)并行執(zhí)行算法的總時(shí)間，T_p代表的是包含p個(gè)計(jì)算節(jié)點(diǎn)并行執(zhí)行算法的總時(shí)間。如果算法是可擴(kuò)展的，那么當(dāng)數(shù)據(jù)規(guī)模固定時(shí)，加速比與計(jì)算節(jié)點(diǎn)的增加將呈現(xiàn)線性關(guān)系。本實(shí)驗(yàn)將數(shù)據(jù)集按評(píng)分記錄數(shù)分成三個(gè)等級(jí)，分別為10000、100000、1000209，實(shí)驗(yàn)結(jié)果如圖3所示：

可以看出，三個(gè)等級(jí)數(shù)據(jù)規(guī)模的加速比與計(jì)算節(jié)點(diǎn)數(shù)的增加近似呈線性關(guān)系，而且當(dāng)數(shù)據(jù)規(guī)模增加時(shí)，加速比更大。由此可以得出，Mahout上分布式的基于項(xiàng)目的協(xié)同過(guò)濾算法在處理更大規(guī)模的數(shù)據(jù)時(shí)算法的加速比表現(xiàn)的更好，有效地解決了算法的可擴(kuò)展性問(wèn)題。

5總結(jié)

首先介紹了傳統(tǒng)協(xié)同過(guò)濾推薦算法，雖然在數(shù)據(jù)稀疏性、冷啟動(dòng)問(wèn)題等方面有所改善，但不能夠應(yīng)用于分布式平臺(tái)，處理海量數(shù)據(jù)時(shí)遇到了算法瓶頸。本文借助Hadoop平臺(tái)，分析Mahout中分布式的基于項(xiàng)目的協(xié)同過(guò)濾推薦算法，并實(shí)現(xiàn)其基本原理及方法，充分說(shuō)明了該算法在處理海量數(shù)據(jù)時(shí)表現(xiàn)出色的高效率性能，其可擴(kuò)展性也在分布式系統(tǒng)中得到了重大的改善，在商業(yè)應(yīng)用之中，具有明顯的競(jìng)爭(zhēng)優(yōu)勢(shì)。