Slope One算法的改進及其在大數據平臺的實現

劉佳耀，王佳斌

華僑大學 工學院，福建 泉州362021

1 引言

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

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

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

2 相關工作

2.1 用戶-項目評分矩陣

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

表1 評分矩陣

2.2 Slope One算法

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

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

通過表1 的用戶-項目評分矩陣實例來得到項目的預測評分值。因為已知用戶u2、u3對項目i2的評分，先用公式（1）計算評分之間的偏差值Dev2,1=[(4-2)+(3-3)]/2=1，Dev2,3=(4-2)/1=1；接著用公式（2）計算用戶u1對項目i2的評分值為P(u1)2=[(2+1)+(3+1)]/2=3.5；最后對未評分的項目都進行評分預測并比較評分值大小為相應用戶產生項目TOP-N推薦。

2.3 Weighted Slope One算法

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

其中，P(u)j代表用戶u 對項目j 的預測評分（j 代表某個項目，u 代表某個用戶），ui是具體的評分值（i 代表某個項目）， ||Cji是相應的用戶具體數量的權值（i 和j都代表某個用戶）。

3 本文方法

3.1 Slope One算法加權項目的相似性

僅僅在算法的預測評分公式中加權相關用戶個數，在進行推薦預測時沒有考慮到項目與項目之間的差別，使相關性很低的項目對推薦預測產生干擾，而真正相關性高的項目被忽略。本文先運用文獻[11]提出改進的Slope One算法，將項目相似性當作一個有效的權值加權到Slope One算法的評分預測中，相關計算公式如下：

項目之間相似性的計算是推薦系統中的關鍵部分，可以區分出項目之間的相似程度的高低。最近鄰集合的準確性很大程度取決于相似性計算的結果，并也決定了最終評分預測值的準確性。Pearson相關相似性公式利用用戶評分值減去對項目的平均評分值，留下了用戶的評分偏好，更能體現出各個項目的相關程度，所以用式（5）求得各個項目的相似度大小：

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

3.2 結合Canopy和K-medoids的聚類算法

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

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

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

（3）根據第（2）步中所求的距離D，把距離小于T1的向量分到一個Canopy中，同時把距離小于T2的向量從項目評分向量集中移除。

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

（5）獲得項目聚類集合，聚類中心集合C′。

3.3 在單機上改進的Slope One算法

把改進的Slope One算法在單機上運行的相關步驟：

（1）對要進行實驗的電影數據集進行預處理，形成項目評分矩陣。

（2）通過式（4）計算項目與項目之間的評分相似性。

（3）利用Canopy和K-medoids的聚類算法得到K個聚類，并將目標項目劃分到最相似的聚類中。

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

（5）利用式（3）在目標項目Ij所屬的最近鄰居集合中進行評分預測，產生Top-N項目。

4 基于聚類的加權Slope One推薦算法及其在大數據平臺上的實現

隨著用戶和項目的數量以驚人的速度增長，執行Slope One 算法時產生的中間結果也會快速增多，內存的壓力就越來越大，當內存容量不足時就只能先存儲到磁盤中，大大地降低了推薦效率。因此，利用分布式計算Spark平臺，讓數據只在內存中計算，不在磁盤中來回讀取，提高算法的運行速率和推薦效率。

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

通常情況下一般的推薦算法訓練模型都要進行大量的迭代計算，利用傳統的單機或者MapReduce計算框架，已經很難滿足海量數據的實時處理，所以基于Spark計算框架能夠有效提高推薦效率。

4.1 改進算法的算法描述

對改進的推薦算法標準的算法描述如下：

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

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

Outout：K 個最近鄰用戶聚類集合

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 加權的Slope one算法的描述

Input:K 個最近鄰用戶聚類集合，用戶項目評分矩陣

Output:用戶u 對項目j 的預測評分ru,j

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

2. If Iu是個空集或者不存在

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平臺的聚類加權Slope One算法

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

結合Canopy 和K-medoids 聚類算法并行計算過程中的任務劃分和匯聚。

Map 1 過程：計算數據對象到中心點的距離，生成若干個Canopy；Reduce1 匯聚過程：將中心點的數據對象匯聚，生成Canopy中心點的集合。

Map 2 過程：把Canopy 算法快速得到的中心點分發到每個分區當作K-medoids的最初的中心點進行聚類計算，計算數據對象到中心點的距離并且進行歸類；Combine 過程：將中心點的數據對象匯聚，計算同一個中心點數據對象之和。Reduce2 匯聚過程：匯聚聚類局部結果，繼續計算新的中心點。并判斷是否收斂，直到算法結束。

結合Canopy和K-medoids聚類算法偽代碼：

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

2.Val data=lines.map（Vector_）//把文本數據轉化成向量形式

3.Val CanopyMapCenterList=new HashSet（）//計算對象到中心點的距離

4.Val Centers=datas.map{

X=＞(x._1，Canopy_1（x，CanopyMapCenterList，T1））} //當兩者距離大于閾值T1，把新的中心點加入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 //計算每個對象和Canopy中心點的距離，把小于T2的對象加入子集；

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

Centercluster（index）=Canopy_1（centerList，T2）}//計算各個新中心點的Canopy 子集，計算新舊中心點的平方差，進而更新中心點。

在所屬聚類的最近鄰集合中進行加權項目相似度的Slope One 算法評分預測的并行計算過程中的任務劃分和匯聚。

Map1過程：把電影數據集轉化成向量的形式，并分發給各個節點，獲得用戶-項目的倒排表，一一得到各節點的項目之間共同評分的用戶；Reduce1匯聚過程：匯聚所有項目之間的共同評分用戶。

Map2過程：計算項目之間的相似性。

Reduce2匯聚過程：匯聚所有項目之間的相似性。

Map3過程：計算各個項目之間的喜好差異值。

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

Map4過程：把項目相似性和喜好差異值進行加權。

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

具體的偽代碼如下：

1.Parttion=C； //劃分為C 個分區并行計算

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

3.Ratings=sc.textFile（）.map（split）.cache（） //格式化評分數據

//并行化實現，得到用戶-物品倒排表，數據cache

4.Item_user=lines1.parallenlize（0 until

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

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

//計算項目之間的相似性

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））；//預測評分

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

//根據相似度的大小，為用戶推薦最感興趣的前N個項目

7.Val recommendations=bestModel.get

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

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

4.3 改進算法在Spark 中Map 和Reduce 的 實現代碼

在spark 平臺中實現的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 平臺搭建與實驗結果分析

搭建大數據Spark 平臺，在VMware 中創建三臺虛擬機，把其中一臺設為主節點，另外兩臺設為從節點。操作系統版本均為Centos7，在操作系統上采用Scala-2.11.4，Spark-1.6.0，JAVA-JDK1.8 和Hadoop-2.6.1 等來創建集群環境。

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

5.1 大數據平臺下改進算法程序流程圖

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

算法具體步驟描述如下：

圖1 算法流程圖

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

（2）先把相應的數據集上傳到HDFS 上，把用戶項目評分數據集預處理成key-value 鍵值對，并將鍵值對轉化為RDD的形式。接著根據相應的各個鍵值生成用戶—項目對應倒排表，在倒排表中項目和項目的評分用reduceByKey（_+_）的形式得出。然后調用Similaritymap（）函數計算項目評分相似性。

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

5.2 運行時間

根據不同大小電影數據集在Spark平臺下推薦模型的運行訓練時間，如圖2、3所示。

從圖2 中可以看出，用同一個電影數據集在Spark集群中進行實驗，增加集群中節點數可以大大減少數據的處理時間，從而加快算法的執行速度而且Spark 集群節點數越多優勢越顯著。從圖3 看出隨著集群中節點的增加，處理大數據集的速度越來越快。

5.3 加速比

圖3 大數據集運行時間

實驗根據加速比參數的大小來判斷并行化算法的性能，加速比Speedup根據單節點串行時間與多節點并行時間之比來判斷算法的并行化性能好壞，加速比越大則代表并行化越好，其計算方式如公式（6）所示：

其中Tp為多個并行節點運行的時間，T1為單個節點運行的時間，實驗結果如圖4所示。

圖4 加速比對比

從圖4可以看出Spark集群中的機器節點從一個節點增加到三個節點，加速比也隨之升高，并且電影數據集由小到大，加速比增長變快。

5.4 運行效率

在Spark平臺和單機環境下對比本文優化算法的運行效率，以具體改進算法完成的運行時間長短來比較運行效率的高低，如表2所示。

表2 本文優化算法運行時間 s

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

圖5 運行效率對比

從圖5 中可以得出，隨著Spark 集群中的節點數增加，運行時間也降低了，而且僅包含一臺節點的集群的運行效率也比單機環境的運行效率高。

5.5 平均絕對誤差

在評測推薦系統質量好壞時，推薦質量的好壞常用平均絕對誤差（MAE）來作為評價指標。MAE的指標是用來計算推薦過程中得到的實際評分和預測評分的評分之間的差異，通過具體數值的大小來代表推薦的準確性，計算公式如下：

其中，N 為測試集中的總個數，pi為用戶對物品i 預測評分值，qi為對應的用戶對物品i 的實際評分值。因此，MAE越小代表預測值與實際值越接近，推薦結果越準確。

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

表3 對比算法的MAE值變化

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

5.6 單機的算法對比

為了對比改進后算法與其他算法的推薦效果，在單機上對同一個數據集ml-100K 進行了算法推薦精確度的比較，對比的算法分別為加權項目相似性的Slope One 算法、傳統的Slope One[22]算法以及本文的優化算法，采用評價指標MAE，如圖6所示。

圖6 在單機上算法推薦精度對比

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

5.7 單機上和Spark平臺上的優化算法對比

為了對比改進后的算法在Spark平臺上和單機上的推薦效果，對同一個數據集ml-100k和ml-1M進行了實驗，評價指標為MAE，如圖7、8所示。

圖7 本文算法在單機環境下和Spark平臺的MAE值對比

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

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

5.8 集群環境下的算法對比

為了對比改進后算法與其他算法在Spark平臺上推薦效果，對同一個數據集ml-100k進行了實驗，選用的算法分別是Spark ML 庫中的ALS 機器學習算法[23]、文獻[24]中加權項目相似性的Slope One算法以及本文優化算法，評價指標為MAE，如圖8所示。

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

6 結論

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