劉佳耀，王佳斌

華僑大學(xué) 工學(xué)院，福建 泉州362021

1 引言

隨著大數(shù)據(jù)時(shí)代的到來，推薦系統(tǒng)[1]在很多領(lǐng)域的作用越來越突出，在一定程度上解決了用戶很難獲得自己真正需要的商品的問題。而協(xié)同過濾[2]技術(shù)在推薦系統(tǒng)又得到廣泛應(yīng)用。Slope One 算法[3]是協(xié)同過濾算法中的一種，在相同推薦精度下，與其他類型的協(xié)同過濾算法相比，其更高效，更易于實(shí)現(xiàn)。但隨著用戶項(xiàng)目數(shù)量大規(guī)模增長，數(shù)據(jù)稀疏性、實(shí)時(shí)性、可擴(kuò)展性等問題導(dǎo)致推薦質(zhì)量大幅下降。

由于Slope One 算法只考慮了項(xiàng)目與項(xiàng)目之間的評分偏差，推薦效果不是很理想。文獻(xiàn)[4]在原始的Slope One 算法加權(quán)已經(jīng)評過分的用戶個(gè)數(shù)，均衡了其他項(xiàng)目對目標(biāo)項(xiàng)目的影響，使得推薦效果有所改進(jìn)。文獻(xiàn)[5]利用Weighted Slope One 算法的思想填充用戶項(xiàng)目矩陣中未評分的項(xiàng)目，緩解數(shù)據(jù)稀疏的問題，緊接著在最近鄰居集合中產(chǎn)生評分預(yù)測，一定程度上提高推薦精度。文獻(xiàn)[6]對相關(guān)用戶運(yùn)用新改善的K-means 聚類方法進(jìn)行聚類實(shí)驗(yàn)，篩選出相似度高的用戶聚為一類，避免相似度低的用戶加入計(jì)算，提升推薦準(zhǔn)確性。在大數(shù)據(jù)時(shí)代，僅僅依靠單機(jī)模式很難滿足推薦系統(tǒng)的需要，因?yàn)閱螜C(jī)的內(nèi)存運(yùn)算的劣勢。文獻(xiàn)[7]通過搭建Hadoop[8]大數(shù)據(jù)集群來迭代推薦算法，可以減少推薦的時(shí)間，但是MapReduce[9]框架進(jìn)行迭代計(jì)算時(shí)速度緩慢，很大程度影響實(shí)時(shí)推薦效率。

由于加權(quán)Slope One 算法[10-11]僅利用項(xiàng)目評分值來計(jì)算項(xiàng)目之間的相關(guān)性，如果用戶項(xiàng)目數(shù)稀疏，則可能導(dǎo)致算法計(jì)算的預(yù)測評分值有較大誤差，推薦準(zhǔn)確度低。因此，本文把聚類加權(quán)的Slope One算法在Spark[12]平臺上并行化，來更好地提高Slope One算法的推薦精度、并行化和效率。

2 相關(guān)工作

2.1 用戶-項(xiàng)目評分矩陣

在傳統(tǒng)的推薦算法中，利用m×n 階用戶項(xiàng)目矩陣來存儲用戶-項(xiàng)目的具體評分信息。用ri,j來代表具體用戶對具體項(xiàng)目產(chǎn)生的評分（i 代表某個(gè)用戶，j 代表某個(gè)項(xiàng)目），n 個(gè)項(xiàng)目用集合I={i1,i2,…,in}來表示，m個(gè)用戶用集合U={u1,u2,…,um}來表示。表1為一個(gè)階用戶項(xiàng)目評分矩陣。

表1 評分矩陣

2.2 Slope One算法

原始的Slope One 算法利用一個(gè)線性函數(shù)f(x)=x+b 的形式進(jìn)行預(yù)測，其中，參數(shù)x 代表目標(biāo)用戶對項(xiàng)目形成的評分，參數(shù)b 代表項(xiàng)目之間的平均評分偏差。所以在評分預(yù)測推薦過程中，首先利用公式（1）計(jì)算出目標(biāo)項(xiàng)目與其他項(xiàng)目之間的平均評分偏差矩陣{Devj,i}（j 代表目標(biāo)項(xiàng)目，i 代表其他的某個(gè)項(xiàng)目），最后利用公式（2）預(yù)測對應(yīng)項(xiàng)目評分Prediction(u)j（j 代表某個(gè)項(xiàng)目，u 代表某個(gè)用戶）。

其中，X 為用戶項(xiàng)目評分集，count(rj)表示在rj中的項(xiàng)目總數(shù)（j 代表評分項(xiàng)目），ru,i、ru,j分別為用戶u 對具體項(xiàng)目i 和j 產(chǎn)生的評分（u 代表某個(gè)用戶，i 和j 都代表某個(gè)項(xiàng)目），rj為同時(shí)與j 被評分過的項(xiàng)目集合，Sj,i(X)為在用戶項(xiàng)目評分集中都評分過j 和i 的用戶集合（j 和i 都代表被評分過的某個(gè)項(xiàng)目）。

通過表1 的用戶-項(xiàng)目評分矩陣實(shí)例來得到項(xiàng)目的預(yù)測評分值。因?yàn)橐阎脩魎2、u3對項(xiàng)目i2的評分，先用公式（1）計(jì)算評分之間的偏差值Dev2,1=[(4-2)+(3-3)]/2=1，Dev2,3=(4-2)/1=1；接著用公式（2）計(jì)算用戶u1對項(xiàng)目i2的評分值為P(u1)2=[(2+1)+(3+1)]/2=3.5；最后對未評分的項(xiàng)目都進(jìn)行評分預(yù)測并比較評分值大小為相應(yīng)用戶產(chǎn)生項(xiàng)目TOP-N推薦。

2.3 Weighted Slope One算法

在計(jì)算項(xiàng)目之間的偏差devj,i（j 和i 都代表某個(gè)項(xiàng)目）時(shí)，沒有考慮到加權(quán)用戶具體個(gè)數(shù)得到的devj,i，Slope One算法的準(zhǔn)確程度是不同的。如果有500個(gè)用戶同時(shí)評分了項(xiàng)目i 和項(xiàng)目k，另外一個(gè)只有50個(gè)用戶同時(shí)評分了項(xiàng)目i 和項(xiàng)目j，得到的devi,k肯定比devi,j更精確。所以用評分過的用戶數(shù)的平均數(shù)進(jìn)行加權(quán)，如式（3）所示：

其中，P(u)j代表用戶u 對項(xiàng)目j 的預(yù)測評分（j 代表某個(gè)項(xiàng)目，u 代表某個(gè)用戶），ui是具體的評分值（i 代表某個(gè)項(xiàng)目）， ||Cji是相應(yīng)的用戶具體數(shù)量的權(quán)值（i 和j都代表某個(gè)用戶）。

3 本文方法

3.1 Slope One算法加權(quán)項(xiàng)目的相似性

僅僅在算法的預(yù)測評分公式中加權(quán)相關(guān)用戶個(gè)數(shù)，在進(jìn)行推薦預(yù)測時(shí)沒有考慮到項(xiàng)目與項(xiàng)目之間的差別，使相關(guān)性很低的項(xiàng)目對推薦預(yù)測產(chǎn)生干擾，而真正相關(guān)性高的項(xiàng)目被忽略。本文先運(yùn)用文獻(xiàn)[11]提出改進(jìn)的Slope One算法，將項(xiàng)目相似性當(dāng)作一個(gè)有效的權(quán)值加權(quán)到Slope One算法的評分預(yù)測中，相關(guān)計(jì)算公式如下：

項(xiàng)目之間相似性的計(jì)算是推薦系統(tǒng)中的關(guān)鍵部分，可以區(qū)分出項(xiàng)目之間的相似程度的高低。最近鄰集合的準(zhǔn)確性很大程度取決于相似性計(jì)算的結(jié)果，并也決定了最終評分預(yù)測值的準(zhǔn)確性。Pearson相關(guān)相似性公式利用用戶評分值減去對項(xiàng)目的平均評分值，留下了用戶的評分偏好，更能體現(xiàn)出各個(gè)項(xiàng)目的相關(guān)程度，所以用式（5）求得各個(gè)項(xiàng)目的相似度大小：

其中，用戶對項(xiàng)目j 和i 的評分的均值用rˉj和rˉi（i 和j都代表某個(gè)項(xiàng)目）來表示，即評價(jià)過j 和i 的用戶集合用Ui,j（i 和j 都代表某個(gè)項(xiàng)目）來表示。

3.2 結(jié)合Canopy和K-medoids的聚類算法

由于用戶項(xiàng)目數(shù)量規(guī)模急速增加，在計(jì)算用戶偏好矩陣時(shí)時(shí)間復(fù)雜度很高，很難滿足實(shí)際的推薦場景。Kmeans 聚類算法由于簡單，收斂的速度快，有很大的運(yùn)用優(yōu)勢，但K-means聚類算法也有很大的弊端。然而Kmedoids 聚類算法跟傳統(tǒng)的K-means 算法相比，它能快速地找到噪聲點(diǎn)，減少聚類結(jié)果受噪聲點(diǎn)的干擾，而且K-medoids 算法的質(zhì)心肯定是數(shù)據(jù)中一個(gè)明確的點(diǎn)，聚類效果是比較好的。與傳統(tǒng)的聚類算法不同，Canopy聚類最大的特點(diǎn)是對大規(guī)模的數(shù)據(jù)集只需遍歷一遍，就能得到簇的個(gè)數(shù)，不需要事先指定K 值[13]，直接用簇的個(gè)數(shù)當(dāng)作K值，具有很大的使用價(jià)值。所以本文結(jié)合兩種算法，先運(yùn)用Canopy[14]算法對數(shù)據(jù)集進(jìn)行遍歷得到相應(yīng)的簇的個(gè)數(shù)和全局的中心點(diǎn)，接著用K-medoids 算法計(jì)算到各個(gè)中心點(diǎn)的距離，進(jìn)行劃分，可以有效提高聚類效果。選擇初始距離閾值時(shí)，需要把T1設(shè)為大于T2。當(dāng)T1過大時(shí)，會使許多點(diǎn)屬于多個(gè)Canopy，可能會造成各個(gè)簇的中心點(diǎn)間距離較近，各簇間區(qū)別不明顯；當(dāng)T2過大時(shí)，增加強(qiáng)標(biāo)記數(shù)據(jù)點(diǎn)的數(shù)量，會減少簇個(gè)個(gè)數(shù)；T2過小，會增加簇的個(gè)數(shù)，同時(shí)增加計(jì)算時(shí)間。其算法的基本步驟如下。

（1）項(xiàng)目評分向量集I={I1,I2,…,In}按照一定的規(guī)則進(jìn)行排序，Canopy初始距離閾值T1、T2（采用交叉檢驗(yàn)方式獲得）。

（2）在評分向量集I 中隨機(jī)挑選一個(gè)向量A，使用歐式距離公式快速計(jì)算A 和向量集中其他向量之間的距離D。

（3）根據(jù)第（2）步中所求的距離D，把距離小于T1的向量分到一個(gè)Canopy中，同時(shí)把距離小于T2的向量從項(xiàng)目評分向量集中移除。

（4）重復(fù)第（2）、（3）步，直到候選中心向量為空，算法結(jié)束。

（5）獲得項(xiàng)目聚類集合，聚類中心集合C′。

3.3 在單機(jī)上改進(jìn)的Slope One算法

把改進(jìn)的Slope One算法在單機(jī)上運(yùn)行的相關(guān)步驟：

（1）對要進(jìn)行實(shí)驗(yàn)的電影數(shù)據(jù)集進(jìn)行預(yù)處理，形成項(xiàng)目評分矩陣。

（2）通過式（4）計(jì)算項(xiàng)目與項(xiàng)目之間的評分相似性。

（3）利用Canopy和K-medoids的聚類算法得到K個(gè)聚類，并將目標(biāo)項(xiàng)目劃分到最相似的聚類中。

（4）在目標(biāo)項(xiàng)目Ij（j 代表某個(gè)項(xiàng)目）所屬的聚類中，通過步驟（2）的方法得到與Ij相似度高的相關(guān)項(xiàng)目，最近鄰居集合是從相似度最高的項(xiàng)目中由大到小選取N 個(gè)項(xiàng)目組成的。

（5）利用式（3）在目標(biāo)項(xiàng)目Ij所屬的最近鄰居集合中進(jìn)行評分預(yù)測，產(chǎn)生Top-N項(xiàng)目。

4 基于聚類的加權(quán)Slope One推薦算法及其在大數(shù)據(jù)平臺上的實(shí)現(xiàn)

隨著用戶和項(xiàng)目的數(shù)量以驚人的速度增長，執(zhí)行Slope One 算法時(shí)產(chǎn)生的中間結(jié)果也會快速增多，內(nèi)存的壓力就越來越大，當(dāng)內(nèi)存容量不足時(shí)就只能先存儲到磁盤中，大大地降低了推薦效率。因此，利用分布式計(jì)算Spark平臺，讓數(shù)據(jù)只在內(nèi)存中計(jì)算，不在磁盤中來回讀取，提高算法的運(yùn)行速率和推薦效率。

對RDD的處理，實(shí)現(xiàn)實(shí)際應(yīng)用的各種計(jì)算；RDD抽象形式數(shù)據(jù)集有兩大特點(diǎn)：（1）內(nèi)存存儲，所有數(shù)據(jù)都放在內(nèi)存中進(jìn)行操作，不經(jīng)過磁盤的讀寫，提升數(shù)據(jù)處理速度；（2）較好的容錯(cuò)性，RDD 的容錯(cuò)通過記錄日志的方式，可以避免檢查點(diǎn)的方法引起的數(shù)據(jù)冗余問題，而加大網(wǎng)絡(luò)通信開銷。

通常情況下一般的推薦算法訓(xùn)練模型都要進(jìn)行大量的迭代計(jì)算，利用傳統(tǒng)的單機(jī)或者M(jìn)apReduce計(jì)算框架，已經(jīng)很難滿足海量數(shù)據(jù)的實(shí)時(shí)處理，所以基于Spark計(jì)算框架能夠有效提高推薦效率。

4.1 改進(jìn)算法的算法描述

對改進(jìn)的推薦算法標(biāo)準(zhǔn)的算法描述如下：

算法1 Canopy-K-medoids的聚類算法

Input：電影用戶-項(xiàng)目向量集I{I1,I2,…,In}，Canopy 設(shè)置的閾值T1和T2

Outout：K 個(gè)最近鄰用戶聚類集合

1. Converged=false，iteration=0

2. While Converged is false

3. For each Canopy(i) in Canopies

4. For each Ciin CanopyCenterList C(C1,C2,…,Ck)

5. Get the minValue of Wi：Dist(Li,Ci) in Canopy(i)

6. Add Ciinto corresponding Cluster(i)

7. End for

8. End for

9. For each Cluster(i) in Clusters

10. Get the

11. Add L′iinto L′(L′1,L′2,…,L′n)

12.End for

13.For each L′iin L′(L′1,L′2,…,L′n)

14.For each Cjin CanopyCenterList C(C1,C2,…,Ck)

15. If（Dist(L′i,Cj)＜=T1）

16. Add L into Canopy(j)

17. End if

18. End for

19.IF（L′i-Li＜Converge Dist）

20. Converged=true

21.End IF

End while

算法2 加權(quán)的Slope one算法的描述

Input:K 個(gè)最近鄰用戶聚類集合，用戶項(xiàng)目評分矩陣

Output:用戶u 對項(xiàng)目j 的預(yù)測評分ru,j

1. 在所屬聚類中得到用戶U 評分的項(xiàng)目集合Iu

2. If Iu是個(gè)空集或者不存在

3. ru,j=0

4. End if

5. For each item i in Iu

6. If cj,i＞0

7. up=up+(ru,i+devj,i)×cj,i

8. Down=down+cj,i

9. End if

10.End for

11.If down＞0

13.End if

14.Return ru,j

4.2 基于Spark平臺的聚類加權(quán)Slope One算法

在大規(guī)模數(shù)據(jù)背景下，在聚類中形成最近鄰集合、搜索最近鄰和推薦預(yù)測中都需要反復(fù)計(jì)算平均偏好差異值和項(xiàng)目相似度，這樣在單機(jī)上進(jìn)行計(jì)算效率低下。所以利用有內(nèi)存優(yōu)勢的Spark 集群來實(shí)現(xiàn)算法的并行化。實(shí)驗(yàn)可以分成兩步：第一步先實(shí)現(xiàn)基于Canopy 和K-medoids[15-16]的聚類算法在Spark 平臺上的并行化；第二步再實(shí)現(xiàn)加權(quán)了項(xiàng)目相似度[17]的Slope One 算法在Spark平臺上的并行化[18]。

結(jié)合Canopy 和K-medoids 聚類算法并行計(jì)算過程中的任務(wù)劃分和匯聚。

Map 1 過程：計(jì)算數(shù)據(jù)對象到中心點(diǎn)的距離，生成若干個(gè)Canopy；Reduce1 匯聚過程：將中心點(diǎn)的數(shù)據(jù)對象匯聚，生成Canopy中心點(diǎn)的集合。

Map 2 過程：把Canopy 算法快速得到的中心點(diǎn)分發(fā)到每個(gè)分區(qū)當(dāng)作K-medoids的最初的中心點(diǎn)進(jìn)行聚類計(jì)算，計(jì)算數(shù)據(jù)對象到中心點(diǎn)的距離并且進(jìn)行歸類；Combine 過程：將中心點(diǎn)的數(shù)據(jù)對象匯聚，計(jì)算同一個(gè)中心點(diǎn)數(shù)據(jù)對象之和。Reduce2 匯聚過程：匯聚聚類局部結(jié)果，繼續(xù)計(jì)算新的中心點(diǎn)。并判斷是否收斂，直到算法結(jié)束。

結(jié)合Canopy和K-medoids聚類算法偽代碼：

1.Val lines=sc.textFile（DataInput）//從HDFS中讀取數(shù)據(jù)生成RDD

2.Val data=lines.map（Vector_）//把文本數(shù)據(jù)轉(zhuǎn)化成向量形式

3.Val CanopyMapCenterList=new HashSet（）//計(jì)算對象到中心點(diǎn)的距離

4.Val Centers=datas.map{

X=＞(x._1，Canopy_1（x，CanopyMapCenterList，T1））} //當(dāng)兩者距離大于閾值T1，把新的中心點(diǎn)加入Canopy中。

5.for（i＜-0 util Center.Size）{

Canopy_1（CanopyCenterList，T1）}

Val CanopyT2=datas.map{

Y=＞(y._1，Canopy_2（x，CanopyMap，T2））}

While（dist＞convergeDist || iteration＜Max）{

MapCanopyT2=CanopyT2.map //計(jì)算每個(gè)對象和Canopy中心點(diǎn)的距離，把小于T2的對象加入子集；

6.For（（index，value）＜-newCentercluster）{

Centercluster（index）=Canopy_1（centerList，T2）}//計(jì)算各個(gè)新中心點(diǎn)的Canopy 子集，計(jì)算新舊中心點(diǎn)的平方差，進(jìn)而更新中心點(diǎn)。

在所屬聚類的最近鄰集合中進(jìn)行加權(quán)項(xiàng)目相似度的Slope One 算法評分預(yù)測的并行計(jì)算過程中的任務(wù)劃分和匯聚。

Map1過程：把電影數(shù)據(jù)集轉(zhuǎn)化成向量的形式，并分發(fā)給各個(gè)節(jié)點(diǎn)，獲得用戶-項(xiàng)目的倒排表，一一得到各節(jié)點(diǎn)的項(xiàng)目之間共同評分的用戶；Reduce1匯聚過程：匯聚所有項(xiàng)目之間的共同評分用戶。

Map2過程：計(jì)算項(xiàng)目之間的相似性。

Reduce2匯聚過程：匯聚所有項(xiàng)目之間的相似性。

Map3過程：計(jì)算各個(gè)項(xiàng)目之間的喜好差異值。

Reduce3匯聚過程：匯聚所有的喜好差異值。

Map4過程：把項(xiàng)目相似性和喜好差異值進(jìn)行加權(quán)。

Reduce4匯聚過程：把最終結(jié)果匯聚成[（user，item），Dev]的形式，并進(jìn)行評分預(yù)測，完成TOP-N的推薦。

具體的偽代碼如下：

1.Parttion=C； //劃分為C 個(gè)分區(qū)并行計(jì)算

2.Sc=new SparkContext（）//初始化Spark上下文

3.Ratings=sc.textFile（）.map（split）.cache（） //格式化評分?jǐn)?shù)據(jù)

//并行化實(shí)現(xiàn)，得到用戶-物品倒排表，數(shù)據(jù)cache

4.Item_user=lines1.parallenlize（0 until

P）.map（parseVectorOnItem）.groupByKey（）.map（

Lambda x：sampleInteractions（x[0].x[1]））.cache（）

//計(jì)算項(xiàng)目之間的相似性

5.Item_sims=pairwise_users.map（

Lambda x：calcSim（x[0]，x[1]））.map（

Lambda x：keyOnFirstUser（x[0]，x[1]））.groupByKey（）.map（

Lambda x：nearestNeighbors（x[0]，x[1]，10））；//預(yù)測評分

6.Val predict=（rat+Dev）*item_sims/SumSimW

//根據(jù)相似度的大小，為用戶推薦最感興趣的前N個(gè)項(xiàng)目

7.Val recommendations=bestModel.get

.predict（candidates.map（（0，_）））.collect（）

.sortBy（-_.rating）.take（N）

4.3 改進(jìn)算法在Spark 中Map 和Reduce 的 實(shí)現(xiàn)代碼

在spark 平臺中實(shí)現(xiàn)的Map 和Reduce 主要代碼如下：

Val data=lines.map（parseVector_）.persist（StorageLevel.MEMORY_ONLY_SER）//map代碼

Val CanopyMapCenterList=new HashSet（）

Val crudeCenters=data.map{ //map代碼

X=＞（x._1，Canopy_1（x，CanopyMapCenterList，T1））}

.filter（y=＞y._2!=null）.collect（）.toList

//reduce代碼

Val ClusterCenterList=new Hashset（CanopyList）

While（tempDist＞ConvergeDist||iteration＜maxIteration）

{

MapCanopyT2=CanopyT2.map //map代碼

{do=＞（closestCenter（do，ClusterCenterList），（do，1））}

Val newClusterCenterList=mapCanopyT2.reduceByKey

{Case((s1,c1),(s2,c2))=＞(s1+s2,c1+c2)}.map

{case（index，(s,c)）=＞（index，s/c）}.collect（）

//reduce代碼

For（（index，value）＜-newClusterCenterList）{

tempDist+=ClusterCenterList.get（index）.get.SquaredDist（value）

ClusterCenterList（index）=Canopy_2（value，CanopyCenterList，T2）}

Val path=”hdfs：//hadoop1：9000//m1_100k/ratings.dat”

Val lines=sc.textFile（path，20）

Val ratings=lines.map{line=＞//map代碼

Val fields=line.split（“：：”）

（fields（3）.toLong%100，Rating（fields（0）.toInt，fields（1）.toInt，fields（2）.toDouble））

}.filter（_._2.rating＞0.0）//map代碼

Val numRatings=ratings.count（）//reduce代碼

Val Users=ratings.map（_._2.user）.distinct（）.count（）//reduce代碼

Val Item=ratings.map（_._2.product）.distinct（）.count（）//reduce代碼

Val ratings2=ratings1.flatMap{x=＞//map代碼

For（user＜-x._2）

Yield{（user._1，（x._1，user._2））}

}.groupByKey（）

.map{x=＞

Val b=x._2.toBuffer.sorted

（x._1，b）

}

Val sumSimW=userItems.map{x=＞//map代碼

Val sim=x._2._3.toInt

Val numUser=x._2._2._2

Sim*numUser

}.reduce（_+_）//reduce代碼

Val pre=userItems.map{x=＞//map代碼

Var b=-1 000 000.0

If（x._2._1._1==0）b=-x._2._2._1

Else b=x._2._2._1

Val rat=x._2._1._2

Val sim=x._2._3

Val predict=（rat+b）*sim/sumSim

Predict

}.reduce（_+_）//reduce代碼

Val myRatedMovieIds=myRatings.map（_.product）.toSet//map代碼

Val recommendations=bestModel.get.predict（candidates.map（（0，_）））.collect（）.sortBy（-_.rating）.take（10）//reduce

代碼

5 平臺搭建與實(shí)驗(yàn)結(jié)果分析

搭建大數(shù)據(jù)Spark 平臺，在VMware 中創(chuàng)建三臺虛擬機(jī)，把其中一臺設(shè)為主節(jié)點(diǎn)，另外兩臺設(shè)為從節(jié)點(diǎn)。操作系統(tǒng)版本均為Centos7，在操作系統(tǒng)上采用Scala-2.11.4，Spark-1.6.0，JAVA-JDK1.8 和Hadoop-2.6.1 等來創(chuàng)建集群環(huán)境。

實(shí)驗(yàn)運(yùn)用的是MovieLens 數(shù)據(jù)集，包括ml-100k、ml-1M和ml-10M三個(gè)不同大小規(guī)模的數(shù)據(jù)集。其中數(shù)據(jù)集ml-100k用相應(yīng)評分值大小來代表用戶對電影的滿意程度，評分值（1～5 的整數(shù)）越高，用戶對該電影越滿意。實(shí)驗(yàn)采用五折交叉驗(yàn)證法進(jìn)行驗(yàn)證，將ml-100k的數(shù)據(jù)集[19]隨機(jī)劃分為不相交的五份，隨機(jī)抽取一份當(dāng)作測試集，留下來的四份作為訓(xùn)練集，需要反復(fù)實(shí)驗(yàn)五次，最終結(jié)果是反復(fù)實(shí)驗(yàn)五次數(shù)值的均值。實(shí)驗(yàn)從運(yùn)行時(shí)間、并行化加速比和推薦指標(biāo)（MAE）這三個(gè)角度來分析實(shí)驗(yàn)結(jié)果。

5.1 大數(shù)據(jù)平臺下改進(jìn)算法程序流程圖

大數(shù)據(jù)平臺的加權(quán)Slope One和Canopy-K-medoids聚類推薦算法[20]并行化具體流程，如圖1所示。

算法具體步驟描述如下：

圖1 算法流程圖

（1）用maPartition（）函數(shù)對RDD的每個(gè)分片進(jìn)行篩選，找到canopies。接著用reduceByKey（_+_）的形式得出每個(gè)分片的canopies，產(chǎn)生總的canopies[21]。并把canopy centers 分發(fā)到各個(gè)分片中，成為K-medoids 的最初的中心點(diǎn)。然后開始不斷對改進(jìn)的聚類算法進(jìn)行迭代，等到生成相應(yīng)數(shù)據(jù)的聚類完成，再把聚類結(jié)果用Reduce（）進(jìn)行匯總，最后分發(fā)到各Slave節(jié)點(diǎn)中。

（2）先把相應(yīng)的數(shù)據(jù)集上傳到HDFS 上，把用戶項(xiàng)目評分?jǐn)?shù)據(jù)集預(yù)處理成key-value 鍵值對，并將鍵值對轉(zhuǎn)化為RDD的形式。接著根據(jù)相應(yīng)的各個(gè)鍵值生成用戶—項(xiàng)目對應(yīng)倒排表，在倒排表中項(xiàng)目和項(xiàng)目的評分用reduceByKey（_+_）的形式得出。然后調(diào)用Similaritymap（）函數(shù)計(jì)算項(xiàng)目評分相似性。

（3）各個(gè)項(xiàng)目的平均評分偏差Dev 可以通過group-ByKey（）函數(shù)一一得到，然后通過讀取上述聚完類的結(jié)果，在生成的各個(gè)聚類中形成相應(yīng)的K 近鄰集合。最后通過Predict（）函數(shù)在最近鄰集合中生成預(yù)測評分。最后利用recommendations（）函數(shù)為用戶推薦相似度高的Top-10個(gè)項(xiàng)目，并將結(jié)果存進(jìn)HDFS中。

5.2 運(yùn)行時(shí)間

根據(jù)不同大小電影數(shù)據(jù)集在Spark平臺下推薦模型的運(yùn)行訓(xùn)練時(shí)間，如圖2、3所示。

從圖2 中可以看出，用同一個(gè)電影數(shù)據(jù)集在Spark集群中進(jìn)行實(shí)驗(yàn)，增加集群中節(jié)點(diǎn)數(shù)可以大大減少數(shù)據(jù)的處理時(shí)間，從而加快算法的執(zhí)行速度而且Spark 集群節(jié)點(diǎn)數(shù)越多優(yōu)勢越顯著。從圖3 看出隨著集群中節(jié)點(diǎn)的增加，處理大數(shù)據(jù)集的速度越來越快。

5.3 加速比

圖3 大數(shù)據(jù)集運(yùn)行時(shí)間

實(shí)驗(yàn)根據(jù)加速比參數(shù)的大小來判斷并行化算法的性能，加速比Speedup根據(jù)單節(jié)點(diǎn)串行時(shí)間與多節(jié)點(diǎn)并行時(shí)間之比來判斷算法的并行化性能好壞，加速比越大則代表并行化越好，其計(jì)算方式如公式（6）所示：

其中Tp為多個(gè)并行節(jié)點(diǎn)運(yùn)行的時(shí)間，T1為單個(gè)節(jié)點(diǎn)運(yùn)行的時(shí)間，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 加速比對比

從圖4可以看出Spark集群中的機(jī)器節(jié)點(diǎn)從一個(gè)節(jié)點(diǎn)增加到三個(gè)節(jié)點(diǎn)，加速比也隨之升高，并且電影數(shù)據(jù)集由小到大，加速比增長變快。

5.4 運(yùn)行效率

在Spark平臺和單機(jī)環(huán)境下對比本文優(yōu)化算法的運(yùn)行效率，以具體改進(jìn)算法完成的運(yùn)行時(shí)間長短來比較運(yùn)行效率的高低，如表2所示。

表2 本文優(yōu)化算法運(yùn)行時(shí)間 s

從表2 看出，與單機(jī)耗時(shí)為765 s 相比，相同的改進(jìn)算法在Spark 平臺上的運(yùn)行時(shí)間更短，在實(shí)際推薦過程中可以大大減少推薦的時(shí)間，提高效率。主要是算法在Spark平臺上進(jìn)行迭代時(shí)，計(jì)算的中間結(jié)果可以緩存，進(jìn)而減少數(shù)據(jù)交換的傳輸時(shí)間，RDD 算子之間的轉(zhuǎn)換也是延遲的，只有到action 時(shí)，才會觸發(fā)運(yùn)算。而Hadoop集群，需要先用map函數(shù)把數(shù)據(jù)寫到磁盤上，在reduce函數(shù)去磁盤上讀取，增加了數(shù)據(jù)傳輸時(shí)間。從圖5可以更加直觀地對比出本文優(yōu)化算法在Spark平臺上的運(yùn)行效率比單機(jī)環(huán)境下的高。

圖5 運(yùn)行效率對比

從圖5 中可以得出，隨著Spark 集群中的節(jié)點(diǎn)數(shù)增加，運(yùn)行時(shí)間也降低了，而且僅包含一臺節(jié)點(diǎn)的集群的運(yùn)行效率也比單機(jī)環(huán)境的運(yùn)行效率高。

5.5 平均絕對誤差

在評測推薦系統(tǒng)質(zhì)量好壞時(shí)，推薦質(zhì)量的好壞常用平均絕對誤差（MAE）來作為評價(jià)指標(biāo)。MAE的指標(biāo)是用來計(jì)算推薦過程中得到的實(shí)際評分和預(yù)測評分的評分之間的差異，通過具體數(shù)值的大小來代表推薦的準(zhǔn)確性，計(jì)算公式如下：

其中，N 為測試集中的總個(gè)數(shù)，pi為用戶對物品i 預(yù)測評分值，qi為對應(yīng)的用戶對物品i 的實(shí)際評分值。因此，MAE越小代表預(yù)測值與實(shí)際值越接近，推薦結(jié)果越準(zhǔn)確。

為了比較改進(jìn)的算法（單機(jī)版）、改進(jìn)算法在Spark平臺的并行化和原始的Slope One 算法之間的推薦準(zhǔn)確性的高低，使用的數(shù)據(jù)集是ml-100k電影數(shù)據(jù)集，通過比對不同鄰居個(gè)數(shù)下，MAE 值的變化來確定推薦性能的好壞，如表3所示。

表3 對比算法的MAE值變化

從表3 中看出，隨著最近鄰居的個(gè)數(shù)不斷增加，每個(gè)算法的MAE 值都呈下降趨勢：當(dāng)最近鄰個(gè)數(shù)k ＞40時(shí)，該優(yōu)化算法的推薦精度已經(jīng)慢慢優(yōu)于傳統(tǒng)的Slope One算法；當(dāng)最近鄰個(gè)數(shù)k≥120 時(shí)，各算法的MAE值都趨向平穩(wěn)。最后，在Spark集群下該優(yōu)化算法MAE值和單機(jī)下優(yōu)化算法的MAE 值基本持平，這表明該優(yōu)化算法不僅能保證推薦預(yù)測的準(zhǔn)確性，而且能在大數(shù)據(jù)場景下能夠減少算法迭代的時(shí)間，減少推薦時(shí)間，提高效率。然而沒有結(jié)合聚類算法的加權(quán)Slope One 算法的MAE值明顯高于本文優(yōu)化的算法。

5.6 單機(jī)的算法對比

為了對比改進(jìn)后算法與其他算法的推薦效果，在單機(jī)上對同一個(gè)數(shù)據(jù)集ml-100K 進(jìn)行了算法推薦精確度的比較，對比的算法分別為加權(quán)項(xiàng)目相似性的Slope One 算法、傳統(tǒng)的Slope One[22]算法以及本文的優(yōu)化算法，采用評價(jià)指標(biāo)MAE，如圖6所示。

圖6 在單機(jī)上算法推薦精度對比

從圖6 中可以得出，隨著最近鄰居個(gè)數(shù)的不斷增加，三種算法的MAE值都呈明顯的下降趨勢，也表明了推薦精度在上升。在k ＞40 后，本文優(yōu)化算法的MAE值整體低于原始的Slope One算法和加權(quán)的Slope One算法。當(dāng)k ＞60 后，MAE 下降的趨勢漸漸趨于平緩。在k=150 時(shí)，各個(gè)算法的MAE 的值最小，此時(shí)推薦效果最好。這很好地說明在算法中加權(quán)項(xiàng)目相似度和引入聚類后，有效提高了推薦預(yù)測準(zhǔn)確性。

5.7 單機(jī)上和Spark平臺上的優(yōu)化算法對比

為了對比改進(jìn)后的算法在Spark平臺上和單機(jī)上的推薦效果，對同一個(gè)數(shù)據(jù)集ml-100k和ml-1M進(jìn)行了實(shí)驗(yàn)，評價(jià)指標(biāo)為MAE，如圖7、8所示。

圖7 本文算法在單機(jī)環(huán)境下和Spark平臺的MAE值對比

圖8 在Spark平臺上算法推薦效果對比

從圖7中可以得出，當(dāng)最近鄰個(gè)數(shù)k ＜60 時(shí)，與單機(jī)環(huán)境下相比，基于Spark 平臺的本文優(yōu)化算法推薦精度優(yōu)勢不大，但隨著k ＞60 后，基于Spark平臺的本文優(yōu)化算法的推薦精度慢慢提高并開始略優(yōu)于在單機(jī)環(huán)境下的本文優(yōu)化算法的精度。這說明在Spark 平臺下，可以稍微提升精確度，并能保持精確度不降低的情況下，還能提升算法迭代的效率。

5.8 集群環(huán)境下的算法對比

為了對比改進(jìn)后算法與其他算法在Spark平臺上推薦效果，對同一個(gè)數(shù)據(jù)集ml-100k進(jìn)行了實(shí)驗(yàn)，選用的算法分別是Spark ML 庫中的ALS 機(jī)器學(xué)習(xí)算法[23]、文獻(xiàn)[24]中加權(quán)項(xiàng)目相似性的Slope One算法以及本文優(yōu)化算法，評價(jià)指標(biāo)為MAE，如圖8所示。

從圖8中可以得出，在Spark集群環(huán)境下，隨著最近鄰居個(gè)數(shù)的不斷增加，在k ＞40 后，本文優(yōu)化算法明顯優(yōu)于Spark ML 庫中的ALS 推薦算法和文獻(xiàn)中加權(quán)項(xiàng)目相似性的Slope One算法，與MfP-CF推薦算法相比，在k ＜80 時(shí)，MfP-CF[25]推薦算法的推薦準(zhǔn)確性是明顯優(yōu)于本文改進(jìn)算法的，但當(dāng)80 ＜k ＜160 時(shí)，隨著最近鄰個(gè)數(shù)的增加，本文優(yōu)化算法明顯優(yōu)于MfP-CF推薦算法，而MfP-CF推薦算法的MAE值漸漸趨于平緩，本文優(yōu)化算法隨著最近鄰的增加，MAE 的值還在繼續(xù)減少，推薦精度逐漸變高。說明加入canopy 和K-medoids的聚類的并行算法能夠明顯提升推薦的精度，與圖7的單機(jī)環(huán)境下的MAE 值相對比也說明了在Spark 集群環(huán)境下，推薦的精確度差別不大的情況下，可以提升算法的迭代速度。

6 結(jié)論

由于原始Slope One 算法單機(jī)環(huán)境下算法迭代速度慢和在大數(shù)據(jù)集下推薦精確度較低的缺點(diǎn)，在Slope One算法的評分預(yù)測公式上加權(quán)項(xiàng)目相似度，盡量避免相似度低的噪聲點(diǎn)混入評分預(yù)測計(jì)算，然后通過Canopy和K-medoids結(jié)合的聚類并行化算法形成相似項(xiàng)目的聚類以縮短搜索最近鄰的時(shí)間，使Slope One算法的推薦精度有了一定程度的提高。并且，把本文優(yōu)化算法基于Spark 平臺實(shí)現(xiàn)并行化，得到的推薦精度要略優(yōu)于單機(jī)環(huán)境下的優(yōu)化算法，進(jìn)一步的提高了推薦準(zhǔn)確性。對比單機(jī)的效率低下，采用內(nèi)存優(yōu)勢的Spark平臺，使算法的可擴(kuò)展性明顯提高，并能較好地處理大規(guī)模數(shù)據(jù)集，加快算法的迭代效率。