曹 霞,謝穎華

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院,上海 201620)

1 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展,推薦系統(tǒng)越來越受到大家的關(guān)注,很多人都開始研究如何優(yōu)化推薦系統(tǒng).更有很多電子商務(wù)平臺也在開始使用推薦系統(tǒng),比如說Amazon、淘寶、京東,以及各種我們現(xiàn)在使用的手機(jī)軟件APP,隨處可見的推薦系統(tǒng).

協(xié)同過濾算法主要分為兩種類型,一種是基于項目(item)的協(xié)同過濾,一種是基于用戶(user)的協(xié)同過濾[1].如今這兩種已經(jīng)不能滿足各類網(wǎng)站的推薦效率,有很多人陸續(xù)提出了對協(xié)同過濾算法的改進(jìn)方法.如有人提出基于聚類模型的協(xié)同過濾算法[2],原理就是用聚類對user或item分組,然后用協(xié)同過濾算法是對一件item評分,將評分最高的item推薦給user.還有人提出了基于用戶的Hadoop協(xié)同過濾算法[3],也就是本文將進(jìn)行詳細(xì)描述的思想.更有人提出的基于ALS(Alternating Least Squares)的協(xié)同過濾[4],ALS算法是基于矩陣分解的協(xié)同過濾算法中的一種,在Soven的oryx框架中,推薦算法便是采用的這種算法.

隨著海量信息的暴增,數(shù)據(jù)沒有辦法能夠很好地儲存和計算,這個時候就需要我們對推薦算法做一些改進(jìn).不光對算法本身做出優(yōu)化,也要在運(yùn)行平臺上做出很大的變化,這時我們就加入了Hadoop平臺.正如我們所知道的,其實(shí)一直以來我們的協(xié)同過濾算法都是以單機(jī)的形式來運(yùn)行的,這在某種程度上就會影響運(yùn)行速率,隨著數(shù)據(jù)的增多,也越來越不能滿足如此大量數(shù)據(jù)的運(yùn)算.因此本文提出基于Hadoop這樣的云平臺來實(shí)現(xiàn)基于用戶的協(xié)同過濾的并行化.因此多機(jī)形式下運(yùn)行推薦算法成為推薦算法研究中一個新的研究方向.

本文將傳統(tǒng)的協(xié)同過濾在Hadoop平臺下實(shí)現(xiàn)并行化,也就是基于MapReduce的推薦過程,各個部分功能分模塊開發(fā),互不影響,從而方便地進(jìn)行推薦算法的擴(kuò)展.

2 相關(guān)概念

2.1 關(guān)于協(xié)同過濾

協(xié)同過濾算法的推薦主要有5步,第一步為根據(jù)原理建立評分模型,第二步為選出可作為模型中的中間標(biāo)準(zhǔn)項目,第三步是根據(jù)公式計算中間項目的最近鄰居項目集,第四步是從最近項目集選出最優(yōu)解,第五步是推薦完成.本文采用普遍應(yīng)用的統(tǒng)計學(xué)的準(zhǔn)確性度量——平均絕對誤差(MAE)以及單機(jī)運(yùn)行時間和Hadoop集群運(yùn)行時間的加速比.

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

上面已經(jīng)提到過,協(xié)同過濾算法的推薦過程分以上5個過程這五步當(dāng)中最重要的就是第三步,也就是最近鄰居集的計算.一般常見的相似性度量方法有三種: 皮爾遜(Pearson)相關(guān)相似性、余弦相似性、修正的余弦相似性等,下面依次介紹這3種度量方法.

(1) 皮爾遜相關(guān)相似性

皮爾遜相關(guān)相似性是度量兩個變量的線性相關(guān)性的方法,計算公式[5]如下:

其中表示用戶m和用戶n共同評分的項目集合,分別表示用戶n和用戶m對項目p的評分;則分別代表用戶n和用戶m對系統(tǒng)中所有項目的評分均值.

(2) 余弦相似性

在協(xié)同過濾中,用戶的評分向量是用戶的興趣描述,通過計算兩用戶的評分向量之間的夾角余弦來度量用戶的相似度.計算公式[5]如下:

(3) 修正的余弦相似性

在實(shí)際的推薦系統(tǒng)中,對同一項目,用戶的評分尺度可能不同.修正的余弦相似度將該問題考慮在內(nèi),通過用戶的評分均值來消除評分尺度的不同.計算公式[5]如下:

2.2 關(guān)于MapReduce編程模型

Hadoop是Apache軟件基金會旗下的一個開源分布式計算平臺,以HDFS和MapReduce為兩大核心.MapReduce是一種編程模型,用于大規(guī)模數(shù)據(jù)集(大于1 TB)的并行運(yùn)算.當(dāng)前的軟件實(shí)現(xiàn)是指定一個Map(映射)函數(shù),用來把一組鍵值對映射成一組新的鍵值對,指定并發(fā)的Reduce(歸約)函數(shù),用來保證所有映射的鍵值對中的每一個共享相同的鍵組.

一個Map/Reduce作業(yè)(job)通常會把輸入的數(shù)據(jù)集切分為若干獨(dú)立的數(shù)據(jù)塊,由Map任務(wù)(task)以完全并行的方式處理它們.框架會對Map的輸出先進(jìn)行排序,然后把結(jié)果輸入給Reduce任務(wù).通常作業(yè)的輸入和輸出都會被存儲在文件系統(tǒng)中.整個框架負(fù)責(zé)任務(wù)的調(diào)度和監(jiān)控,以及重新執(zhí)行已經(jīng)失敗的任務(wù).

通常,MapReduce框架和分布式文件系統(tǒng)是運(yùn)行在一組相同的節(jié)點(diǎn)上的,也就是說,計算節(jié)點(diǎn)和存儲節(jié)點(diǎn)通常在一起.MapReduce框架由一個單獨(dú)的master JobTracker和每個集群節(jié)點(diǎn)一個slave TaskTracker共同組成.master負(fù)責(zé)調(diào)度構(gòu)成一個作業(yè)的所有任務(wù),這些任務(wù)分布在不同的slave上,master監(jiān)控它們的執(zhí)行,重新執(zhí)行已經(jīng)失敗的任務(wù).而slave僅負(fù)責(zé)執(zhí)行由master指派的任務(wù).應(yīng)用程序至少應(yīng)該指明輸入/輸出的位置(路徑),并通過實(shí)現(xiàn)合適的接口或抽象類提供map和reduce函數(shù).再加上其他作業(yè)的參數(shù),就構(gòu)成了作業(yè)配置 (job configuration).然后,Hadoop 的 job client提交作業(yè)(jar包/可執(zhí)行程序等)和配置信息給JobTracker,后者負(fù)責(zé)分發(fā)這些軟件和配置信息給slave、調(diào)度任務(wù)并監(jiān)控它們的執(zhí)行,同時提供狀態(tài)和診斷信息給job client.

3 基于 Hadoop 的協(xié)同過濾算法

3.1 算法原理

Hadoop是一個開源的分布式計算開源框架,它提供了分布式文件系統(tǒng) (Hadoop Distributed File System,HDFS)和支持MapReduce分布式計算的軟件架構(gòu).MapReduce框架的計算過程分為Map和Reduce兩個階段.在MapReduce作業(yè)中,輸入的數(shù)據(jù)集被切分為若干獨(dú)立的數(shù)據(jù)塊,先由Map任務(wù)并行處理,對Map的輸出數(shù)據(jù)排序后,再作為輸入數(shù)據(jù)交由Reduce任務(wù)處理,最終輸出計算結(jié)果.每個階段的輸入輸出數(shù)據(jù)格式是形式的鍵值對.開發(fā)者只需編寫Map和Reduce階段的映射函數(shù),任務(wù)裝載、調(diào)度和節(jié)點(diǎn)間的通信由Hadoop自動完成.

基于MapReduce的協(xié)同過濾,這時就需要我們輸入用戶—項目評分測試集M,項目聚類集合C以及聚類中心c0,最后得出推薦結(jié)果.用戶-項目評分矩陣如下圖,假設(shè)有n個項目和m個用戶,rij就是用戶j對第i個項目的評分,以此類推[6].

表1 用戶-項目評分矩陣

步驟如下:

(1) 根據(jù)上面所提到的公式,我們將矩陣中要計算的項目與我們所選好的目標(biāo)項目c0進(jìn)行計算得到s結(jié)果.

(2) 將計算出來的s與我們設(shè)定好的相似性閾值比較,把相似度大于等于相似性閾值的項目放到一個集合W中.

(3) 在W中進(jìn)行我們的最后一步,基于Hadoop平臺上的MapReduce分塊計算.系統(tǒng)自動將一個作業(yè)待處理的大數(shù)據(jù)劃分為很多個數(shù)據(jù)塊,每個數(shù)據(jù)塊對應(yīng)于一個計算任務(wù),并自動調(diào)度計算節(jié)點(diǎn)來處理相應(yīng)的數(shù)據(jù)塊.作業(yè)和任務(wù)調(diào)度功能主要負(fù)責(zé)分配和調(diào)度計算節(jié)點(diǎn)(Map節(jié)點(diǎn)或Reduce節(jié)點(diǎn)),同時負(fù)責(zé)監(jiān)控這些節(jié)點(diǎn)的執(zhí)行狀態(tài),并負(fù)責(zé)Map節(jié)點(diǎn)執(zhí)行的同步控制,這樣就可以實(shí)現(xiàn)協(xié)同過濾的并行化.

圖2 推薦過程流程圖

3.2 基于MapReduce的協(xié)同過濾算法

本文研究的用戶-類矩陣中的數(shù)據(jù)反映了用戶對項目的喜愛程度,但是其中的數(shù)據(jù)可能會有一定的差異,所以基于MapReduce就在一定程度上可以解決這個問題.并且可以計算用戶相似度,可以查找領(lǐng)居,進(jìn)行興趣推薦,那么就需要多輪MapReduce任務(wù).

(1) 第1輪Map任務(wù): 原始的用戶數(shù)據(jù)處理后會統(tǒng)一存放在HBase數(shù)據(jù)庫的信息表中,這里面會有一系列的用戶對項目的評分.Map任務(wù)是將用戶的評分信息讀取出來 (String),以的形式讀入數(shù)據(jù),經(jīng)過對字符串分析,挖掘客戶信息,以的形式輸出給接下來的Reduce任務(wù).

(2) 第1輪Reduce任務(wù): 此任務(wù)的輸入就是上面Map 的輸出,形式為,Reduce 讀取任務(wù)后,對序列求平均數(shù),作為新的輸出,以的形式.

(3) 第2輪Map任務(wù): 此任務(wù)的輸入也是上一任務(wù)的輸出,分別以和方式輸入,經(jīng)處理后,以和的形式輸出,其中@符號是為了區(qū)分.

(4) 第 2輪Reduce任務(wù): 此任務(wù)的輸入是的形式輸.

(5) 第3個MapReduce任務(wù): 這個任務(wù)是對上一個MapReduce的結(jié)果做出整理,計算用戶相似度以及鄰居,并且進(jìn)行排序,然后得到我們想要的矩陣集合.

(6) 第4個 MapReduce任務(wù): 該任務(wù)是結(jié)合信息表中的信息和上一任務(wù)計算的用戶相似度和鄰居,輸出<(UserID + ClassID),(Rating + Similarity)>,然后完成預(yù)測評分.

(7) 第5個MapReduce: 對最終的數(shù)據(jù)進(jìn)行排序,通過找到預(yù)測評分最高的k個類得出推薦結(jié)果.

3.3 預(yù)測評分原理

在協(xié)同過濾最后一步就是產(chǎn)生推薦,推薦的過程中要對用戶未評分的項目進(jìn)行預(yù)測,預(yù)測的方法如下,我們可以用公式表示[7]:

其中u表示用戶,i表示未被用戶評分過的項目,n為與項目i相似的項目,N是與項目i相似的項目集合.

上面公式中我們將進(jìn)行一個矩陣的乘法,在基于MapReduce框架中,我們要先對矩陣分塊處理,使得不同模塊在不同節(jié)點(diǎn)進(jìn)行處理,因此在利用預(yù)測評分公式前需要對輸入的向量進(jìn)行預(yù)處理,會調(diào)用到Mahout API中的partialMultiply接口,這個將會啟動了兩個Map任務(wù)和一個Reduce任務(wù).

第一個Map負(fù)責(zé)讀取訓(xùn)練集的用戶向量.主要是讀取關(guān)鍵字為用戶編號,向量值為用戶對各個項目的評分向量.

第二個Map任務(wù)是負(fù)責(zé)讀取項目相似度向量,關(guān)鍵字為項目索引,值為相似度向量.

Reduce任務(wù)的輸入是上面兩個Map任務(wù)的輸出結(jié)果,將關(guān)鍵字一致的向量聚集到一起,組成一個新的矩陣,然后計算最緊鄰居集.

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

4.1 實(shí)驗(yàn)方案

本文實(shí)驗(yàn)數(shù)據(jù)采用開源的美國Minnesota大學(xué)GronpLens項目組提供的Movielens(ml-lm)數(shù)據(jù)集,該數(shù)據(jù)集已經(jīng)被廣泛應(yīng)用在推薦系統(tǒng)的測評中.其包含了6040名用戶對3952部電影的超過1000 000的評價,分值為1到5的整數(shù),分?jǐn)?shù)越高表示用戶對電影的評價越高.該數(shù)據(jù)集有3張數(shù)據(jù)表組成: Users(用戶特征信息)、Movies(電影特征信息)、Ratings(評價信息).每一條記錄中包含用戶標(biāo)識、電影標(biāo)識、評價數(shù)值和時間,從中可以獲取本文所需的用戶基本信息、評價和時間等數(shù)據(jù)進(jìn)行進(jìn)一步的分析與處理.

本系統(tǒng)研究協(xié)同過濾算法的MapReduce并行化.通過Python操作HDFs上的文件,首先在HDFs上創(chuàng)建保存數(shù)據(jù)的文件夾; 然后MapReduce程序的每個輸出文件作為下一個MapReduce的輸入文件.

本實(shí)驗(yàn)中,主要考察傳統(tǒng)的基于用戶的利用余弦相似度計算的協(xié)同過濾和在此基礎(chǔ)上的協(xié)同過濾并行化的推薦質(zhì)量.實(shí)驗(yàn)分別為一臺PC構(gòu)建的單機(jī)模式以及三個節(jié)點(diǎn)構(gòu)成的Hadoop集群.本文主要通過兩種方法來證實(shí)并行化的基于Hadoop的協(xié)同過濾算法的推薦系統(tǒng)及其推薦結(jié)果比傳統(tǒng)的協(xié)同過濾算法的推薦系統(tǒng)其推薦結(jié)果更能符合用戶的預(yù)期,與此同時比較單節(jié)點(diǎn)和3個節(jié)點(diǎn)的運(yùn)行時間以及加速比.

一種方法就是用運(yùn)行時間作為衡量算法擴(kuò)展性的指標(biāo),同時也采用了加速比來衡量算法的擴(kuò)展性,加速比定義為單機(jī)運(yùn)行時間和Hadoop集群的運(yùn)行時間的比值,計算公式如下:

另外一種就是根據(jù)平均絕對誤差協(xié)MAE值,MAE的值越小,表明算法的推薦精度越高.這種方法就是衡量推薦與真實(shí)的用戶賦給值的偏差.對于每一對評分預(yù)測數(shù)據(jù)的具體誤差也就是|pi-qi|進(jìn)行處理.平均絕對誤差的計算方法是先計算N對評分-預(yù)測數(shù)據(jù)對的誤差之和,然后計算平均值,如下式:

一般來說,平均絕對誤差越小,推薦結(jié)果越準(zhǔn)確,系統(tǒng)性能就越好.

4.2 預(yù)測評分原理

(1) 一方面,選取平均絕對誤差協(xié)(MAE)作為算法推薦質(zhì)量的評價指標(biāo),MAE的值越小,表明算法的推薦精度越高.從1 MB數(shù)據(jù)集中分別選取數(shù)據(jù)集為1000、10 000、15 000、20 000、40 000 和 60 000 作為6組實(shí)驗(yàn)數(shù)據(jù),分別用余弦相似度和修正余弦相似度以及本文方法(利用兩個節(jié)點(diǎn)并行)進(jìn)行MAE值比較,如圖3 所示.

圖3 MAE 值

從圖3可以看出,實(shí)驗(yàn)數(shù)據(jù)集越稀疏,MAE值越大,這就說明數(shù)據(jù)越多,可參考的就越多,平均絕對誤差也就越小; 當(dāng)然,我們將單機(jī)模式與并行模式作比較,也不難發(fā)現(xiàn)在Hadoop環(huán)境下MAE的值也會相應(yīng)的減少,可以得知修正的余弦相似度是比傳統(tǒng)的余弦相似度這種算法更加提升了推薦質(zhì)量,并且基于Hadoop平臺,推薦性能也會隨著節(jié)點(diǎn)數(shù)增加而得到改善.

(2) 接下來分析余弦相似性的協(xié)同過濾與并行化的協(xié)同過濾的運(yùn)行時間,因此我們將給出單節(jié)點(diǎn)、兩個節(jié)點(diǎn)和三個節(jié)點(diǎn)的運(yùn)行時間以及加速比的對比情況.

從圖4可以看出,隨著數(shù)據(jù)集的增多,運(yùn)行時間也會隨之增加,相比單節(jié)點(diǎn)、兩個節(jié)點(diǎn)以及三節(jié)點(diǎn)的Hadoop的運(yùn)行情況,總體來說,在數(shù)據(jù)集很大的情況下并行能明顯縮短時間,這也足以說明基于MapReduce的協(xié)同過濾并行化推薦更適合于大數(shù)據(jù)的推薦系統(tǒng).但是我們發(fā)現(xiàn)在數(shù)據(jù)集很小的情況下,并行化并沒有顯示出更加大的優(yōu)勢,這是因?yàn)?在數(shù)據(jù)集小的情況下,Hadoop并行還需要進(jìn)行資源配置,Map和Ruduce之間進(jìn)行數(shù)據(jù)傳輸也需要消耗時間,因此在數(shù)據(jù)集很小的情況下就沒必要進(jìn)行并行.

(3) 通過上述實(shí)驗(yàn),我們計算加速比進(jìn)行比較如圖5所示.

從圖5我們可以看出,并行化以后的協(xié)同過濾很大程度上的增大了運(yùn)行時間的加速比,并且當(dāng)數(shù)據(jù)集越大的時候,加速比就越大,也就是說并行化對越大的數(shù)據(jù)集越有優(yōu)化作用.我們還看出,理想的狀況下,要想充分地利用Hadoop集群的運(yùn)算能力,Map的個數(shù)最好是Hadoop的節(jié)點(diǎn)倍數(shù),這樣還可以防止機(jī)器被閑置.

經(jīng)過以上實(shí)驗(yàn)的分析,我們可以得出基于Hadoop的協(xié)同過濾對較大的數(shù)據(jù)集能有成效的優(yōu)化運(yùn)算能力,從而提升推薦速度.隨著現(xiàn)在互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大,這一發(fā)現(xiàn)對于推薦系統(tǒng)具有極大的應(yīng)用,我們可以通過適當(dāng)?shù)脑黾親adoop集群節(jié)點(diǎn)來提高推薦效率.

圖5 不同數(shù)據(jù)集的加速比

5 結(jié)論

本文介紹了傳統(tǒng)基于項目和用戶的協(xié)同過濾算法以及Hadoop平臺的MapReduce編程模型,分析了基于Hadoop平臺的協(xié)同過濾算法.實(shí)驗(yàn)驗(yàn)證在大規(guī)模數(shù)據(jù)的情況下,采用基于Hadoop的MapReduce編程模型進(jìn)行并行化的協(xié)同過濾算法可提高推薦效率和推薦精度.

參考文獻(xiàn)

1李濤,王建東,葉飛躍,等.一種基于用戶聚類的協(xié)同過濾推薦算法.系統(tǒng)工程與電子技術(shù),2007,29(7): 1178–1182.

2Xue GR,Lin CX,Yang Q,et a1.Scalable collaborative filtering using cluster-based smoothing.Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Salvador,Brazil.2005.114-121.

3Zhao ZD,Shang MS.User-based collaborative-filtering recommendation algorithms on hadoop.Proceedings of the Third International Conference on Knowledge Discovery and Data Mining.Phuket,Thailand.2010.478–481.

4Pan R,Zhou YH,Cao B,et al.One-class collaborative filtering.Proceedings of the Eighth IEEE International Conference on Data Mining.Pisa,Italy.2008.502–511.

5李燦.基于Hadoop的并行化協(xié)同過濾推薦算法研究.[碩士學(xué)位論文].楊凌: 西北農(nóng)林科技大學(xué),2016.

6肖強(qiáng),朱慶華,鄭華,等.Hadoop 環(huán)境下的分布式協(xié)同過濾算法設(shè)計與實(shí)現(xiàn).現(xiàn)代圖書情報技術(shù),2013,(1): 83–89.[doi:10.11925/infotech.1003-3513.2013.01.13]

7李狀.基于Hadoop的協(xié)同過濾推薦算法的設(shè)計與實(shí)現(xiàn)[碩士學(xué)位論文].南京: 南京郵電大學(xué),2016.