基于Spark的Slope One算法優(yōu)化與實現(xiàn)

梁化強 唐堅剛

摘 要：傳統(tǒng)Slope One算法未考慮用戶相似性和項目相似性對評分效果的影響，從而導(dǎo)致推薦準(zhǔn)確率不高，并且在當(dāng)前大數(shù)據(jù)背景下，傳統(tǒng)Slope One算法運行效率低下。針對以上問題，提出一種基于Spark的改進(jìn)加權(quán)Slope One算法，該算法融入了相似性計算、活躍用戶篩選和用戶聚類等技術(shù)，并在Spark平臺上實現(xiàn)了并行化。通過在MovieLens數(shù)據(jù)集上進(jìn)行試驗驗證，并比較算法在Spark和Hadoop平臺并行化的運行效率，證實了該算法可以有效降低MAE，且在Spark平臺下運行效率更高，更適用于大數(shù)據(jù)處理場景。

關(guān)鍵詞：Slope One；聚類；用戶相似性；項目相似度；Spark

DOI：10.11907/rjdk.172877

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2018）006-0092-03

Abstract：The traditional slope one algorithm does not consider low user similarity and item similarity on scoring effect， which leads to low recommendation accuracy， and in the current big data background， it suffers from low efficiency of operation. In order to solve the above problems， an improved weighted Slope One algorithm based on Spark is proposed in this paper. The algorithm integrates similarity computing， active user filtering and user clustering technology， and implements parallelization on Spark platform. Through the experiments on MovieLens data sets， this article confirms that the algorithm can effectively reduce MAE， and compares the running efficiency of the parallel algorithm in Spark and Hadoop platform to confirm this algorithm in Spark platform runs more efficiently， more suitable for big data processing.

Key Words：Slope One； clustering； user similarity； project similarity； Spark

0 引言

隨著信息資源的爆炸式增長，人們對個性化服務(wù)的需求逐漸增加，推薦系統(tǒng)已成為電子商務(wù)、社交網(wǎng)絡(luò)等領(lǐng)域的重要技術(shù)。Slope One算法是由Lemire等在2005年提出的一種推薦算法，其是一種基于項目的算法，且原理簡單，推薦準(zhǔn)確率高。但該算法也存在一些不足，如未考慮數(shù)據(jù)稀疏性，以及用戶與物品相似性等問題。

因此，很多人對Slope One算法進(jìn)行了優(yōu)化改進(jìn)。例如，劉偉江[1]采用平均值和SVD技術(shù)對用戶項目評分矩陣進(jìn)行填充，但未考慮項目相似度和用戶相似度的影響；李劍鋒[2]提出一種局部近鄰Slope One算法，該算法需要計算用戶針對不同商品的鄰居用戶，但是對于每一次推薦都要計算目標(biāo)用戶的近鄰用戶，對于一個有幾百萬活躍用戶的電子商務(wù)網(wǎng)站而言，計算量非常大；蔣宗禮[3]提出一種基于聚類的Slope One算法，但沒有對用戶進(jìn)行篩選，將全部用戶進(jìn)行聚類容易混入噪聲數(shù)據(jù)，聚類效果并不理想。

本文提出一種基于聚類與Spark的改進(jìn)加權(quán)Slope One算法，首先依據(jù)活躍函數(shù)篩選出活躍用戶，采用K-means算法確定k個聚類中心。因為在現(xiàn)實環(huán)境中，用戶是很少評分或不評分的，用那些評分較多的優(yōu)質(zhì)用戶進(jìn)行聚類，不僅可以減少計算量，而且可以去除噪聲，提高聚類效果；然后分別計算每個聚類的項目評分偏差表和物品相似度表。因為相似用戶對物品具有相似偏好，因此不同類用戶應(yīng)該使用不同的項目評分偏差表和項目相似度表。上述兩步都可以離線計算，并將計算結(jié)果保存在數(shù)據(jù)庫或文件系統(tǒng)中，方便以后使用；最后對于目標(biāo)用戶確定其所屬聚類，采用該類的項目評分偏差表和項目相似度表，并將項目相似度權(quán)重乘以共同評價物品數(shù)作為混合權(quán)重，運行Slope One算法。

1 Slope One算法理論

1.1 基本Slope One算法

Slope One算法基本思想是用一元線性方程計算兩物品之間的平均偏差，對所有用戶在不同項目間的評分?jǐn)?shù)據(jù)計算得到最終偏移值參數(shù)b的平均值，最后結(jié)合目標(biāo)用戶對已有商品的評分，將偏移值帶入一元方程，以估計目標(biāo)用戶對待推薦商品的評分情況。定義項目i和j之間的平均評分偏差為dev-i，j，（u）-j代表目標(biāo)用戶u對項目j的預(yù)估評分。

1.2 兩種SlopeOne改進(jìn)算法

（1）加權(quán)Slope One算法。基本的Slope One算法并沒有考慮到共同評分的項目數(shù)量，假如有100個用戶同時對項目j和i進(jìn)行評分，而只有10個用戶對項目j和k進(jìn)行評分，顯然dev-j，i比dev-j，k效果更好。因此，將用戶數(shù)目card（U-i，j）作為權(quán)重，則目標(biāo)用戶u對j的評分公式如下：

（2）雙極Slope One算法。雙極Slope One的基本思想是將用戶評分矩陣劃分為“l(fā)ike”和“dislike”兩類，并將用戶對該項目評分與用戶對所有商品的平均評分進(jìn)行對比，大于平均評分記為“l(fā)ike”，小于平均評分則記為“dislike”。

其中，式（4）、式（5）中，S（u）表示用戶u有評分記錄的項目集合，r-u 表示用戶u對所有物品的平均評分。

2 基于聚類與Spark的加權(quán)Slope One算法

2.1 項目相似度計算

相似度可用來衡量項目之間的相似程度，皮爾遜相關(guān)相似性是以用戶評分減去項目平均評分，從而更好地反映出項目之間的相關(guān)程度。因此，本文使用皮爾遜相似性計算項目之間的相似度：

2.2 項目綜合權(quán)重

加權(quán)Slope One算法中使用項目之間的共同評分?jǐn)?shù)量作為權(quán)重。例如，項目i和j的共同評分?jǐn)?shù)量為10，項目i與k的共同評分?jǐn)?shù)量為100，但項目j與i的相似度很高，項目j有可能是新加入的項目，用戶對項目j的評分?jǐn)?shù)量并不多，從而導(dǎo)致評分越少的項目被推薦的可能性越低。因此，本文使用項目綜合權(quán)重如式（11）所示：

2.3 活躍用戶評定

在實際生產(chǎn)環(huán)境中，存在活躍性極小的用戶，他們對項目的評分?jǐn)?shù)據(jù)極少，這些用戶大多是新用戶。在對新用戶進(jìn)行推薦時，往往推薦熱門產(chǎn)品效果較好。因此，為了減少時間消耗并提高聚類效果，本文在預(yù)測評分前篩選出活躍用戶，從而既能提高預(yù)測精度，又能減少時間消耗。

當(dāng)用戶的項目評分?jǐn)?shù)量小于0.01%時為不活躍用戶，定義為Uina；當(dāng)用戶項目評分?jǐn)?shù)量大于0.01%時為活躍用戶，定義為Uact。因此，用戶總集合U=Uina∪Uact。用戶u對所有項目的評分總數(shù)記為Num（itemu），所有項目總數(shù)為Num（item），則：

在預(yù)測評分時，僅對Uact集合中的用戶進(jìn)行聚類。

2.4 K-means用戶聚類

K-means算法是典型的基于距離的聚類算法，采用距離作為相似性評價指標(biāo)，即認(rèn)為兩個對象的距離越近，其相似度越大。k個初始類聚類中心點的選取對聚類結(jié)果具有較大影響，因為K-means算法容易產(chǎn)生局部最優(yōu)，為此本文對k進(jìn)行多次選取，并對每個選定的k值進(jìn)行多次重復(fù)試驗。

2.5 算法流程

綜上所述，基于聚類的加權(quán)Slope One算法的具體步驟如下：①在總項目集中查找目標(biāo)用戶u的未評分項目集合記為Items；②利用公式（13）篩選出活躍用戶集Uact；③對活躍用戶集Uact進(jìn)行K-means聚類，得到k個聚類中心，以及k個用戶集合U-1，U-2，…，U-k；④根據(jù)式（1）、（10）分別計算k個用戶集合的項目評分偏差矩陣與項目相似度矩陣，得到項目評分偏差矩陣K-U-1，K-U-2，…，K-U-k，項目相似度矩陣L-U-1，L-U-2，…，L-U-k；

⑤計算用戶u到k個聚類中心的距離，確定用戶u所屬的用戶集合U-u，U-u為U-1，U-2，…，U-k其中之一；⑥根據(jù)K-U-u、L-U-u（K-U-u為用戶u所在用戶集合的項目評分偏差矩陣，L-U-u為用戶u所在用戶集合的項目相似度矩陣）可以計算式（11）、（12），其中dev-ij在K-U-u中查找，得到p（u）-j；⑦根據(jù)P（u）-j為目標(biāo)用戶u生成前N個推薦項目。

3 試驗結(jié)果與分析

3.1 實驗環(huán)境、測試數(shù)據(jù)集及評價指標(biāo)

在VMware中創(chuàng)建4臺虛擬機(jī)，包含1個Master節(jié)點和3個Slave節(jié)點。操作系統(tǒng)均為Ubuntu14，Spark版本為2.1.0，JDK版本為1.8。實驗數(shù)據(jù)采用GroupLensMovieLens數(shù)據(jù)集中的ml-100k數(shù)據(jù)。本文采用十折交叉驗證法，將數(shù)據(jù)集隨機(jī)分為10等份，并將其中9份作為訓(xùn)練數(shù)據(jù)集，最后1份作為測試數(shù)據(jù)集，每次試驗重復(fù)執(zhí)行10次，采用10次試驗結(jié)果的平均值作為最后結(jié)果。

3.2 試驗結(jié)果

實驗一：驗證本文算法的準(zhǔn)確性、有效性。本文算法與傳統(tǒng)Slope One算法以及加權(quán)Slope One算法在不同K值選擇下的MAE比較如表1與圖1所示。

圖1中k為對活躍用戶劃分的聚類個數(shù)，可以看出隨著聚類個數(shù)k的增大，本文優(yōu)化的Slope One算法MAE值降低，但當(dāng)k≥11時，MAE值有所回升，且當(dāng)k取11左右時得到最低的MAE。試驗證明將用戶分為11個類時，Slope One算法運行效果最好，MAE值最低。

試驗二：比較本文算法在不同平臺上的運行效率。比較本文算法在Hadoop平臺和Spark平臺的運行效率，試驗結(jié)果如表2所示，說明Spark平臺的執(zhí)行性能優(yōu)于Hadoop平臺。

4 結(jié)語

針對傳統(tǒng)Slope One算法未考慮用戶與物品相似性，以及在當(dāng)前大數(shù)據(jù)環(huán)境下運行效率較低的問題，提出一種基于聚類與Spark的改進(jìn)加權(quán)Slope One算法。該算法通過少而精的數(shù)據(jù)從數(shù)據(jù)來源角度提升算法的性能和準(zhǔn)確率。試驗結(jié)果表明，本文算法相比于其它Slope One算法，預(yù)測精度有所提高。而且通過在Hadoop和Spark大數(shù)據(jù)平臺上的比較，說明基于Spark的Slope One算法更適用于大數(shù)據(jù)場景。然而，該算法還存在不足之處，例如如何在數(shù)據(jù)稀疏性條件下產(chǎn)生精確推薦，將是以后需要完善的地方。

參考文獻(xiàn)：

[1] 劉偉江，王穎.奇異值分解法在預(yù)測用戶頁面興趣度中的應(yīng)用[J].數(shù)理統(tǒng)計與管理， 2012，31（2）：325-332.

[2] 李劍鋒，秦拯. 一種基于局部近鄰Slope One協(xié)同過濾推薦算法[J].計算機(jī)工程與科學(xué)， 2017，39 （7）：1346-1351.

[3] 蔣宗禮，杜倩. 基于聚類和項目相似性的Slope One算法優(yōu)化[J].計算機(jī)與現(xiàn)代化，2016（8）：22-26.

[4] 陸勝偉，唐振民，呂建勇. 基于時間因子的Slope One協(xié)同過濾推薦算法[J].信息技術(shù)，2016（10）：1-5.

[5] LEMIRE D， MACLACHLAN A. Slope One predictors for online rating-based collaborative filtering[J]. Computer Science， 2007.

[6] ZHANG Z，TANG X，CHEN D.Applying user-favorite-item-based similarty into Slope One scheme for collaborative filtering[C]. Proceeding of the 2014 World Congress on Computing and CommunicationTechnologies.Washington，DC：IEEE Computer Society，2014：5-7.

[7] YOU H，LI H，WANG Y，et al.An improved collaborative filtering recommendation algorithm combining item clustering and Slope One scheme[J].Lecture Notes in Engineering & Computer Science，2015，2215（1）：313-316.

[8] ZHANGY L，MA M M，WANG S P.Research of userbased co11aborative filtering recommendation algorithm based on Hadoop [EB/OL].[2016-06-20].http：∥www.atlantis-press.Com/php/downloadpaper.php？id=22451.

[9] WANG Y，LOU H Y.Improved Slope One algorithm for collaborative filtering[J]. Computer Science，2011，38（A1）：192-194.

[10] LIU QI，CHEN ENHONG，XIONG HUI，et al.Enhancing collaborative filtering by user interestexpansion personalized ranking[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2012，42（1）：218-233.

[11] GOLDBERG K，ROEDER T，GUPTA D，et al.Eigentaste：a constant time collaborative filtering algorithm[J].Information Retrieval，2001，4（2）：133-151.

（責(zé)任編輯：黃 ?。?/p>