梁化強(qiáng) 唐堅(jiān)剛

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

關(guān)鍵詞：Slope One；聚類；用戶相似性；項(xiàng)目相似度；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年提出的一種推薦算法，其是一種基于項(xiàng)目的算法，且原理簡單，推薦準(zhǔn)確率高。但該算法也存在一些不足，如未考慮數(shù)據(jù)稀疏性，以及用戶與物品相似性等問題。

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

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

1 Slope One算法理論

1.1 基本Slope One算法

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

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

（1）加權(quán)Slope One算法?；镜腟lope One算法并沒有考慮到共同評分的項(xiàng)目數(shù)量，假如有100個用戶同時對項(xiàng)目j和i進(jìn)行評分，而只有10個用戶對項(xiàng)目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”兩類，并將用戶對該項(xiàng)目評分與用戶對所有商品的平均評分進(jìn)行對比，大于平均評分記為“l(fā)ike”，小于平均評分則記為“dislike”。

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

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

2.1 項(xiàng)目相似度計(jì)算

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

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

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

2.3 活躍用戶評定

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

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

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

2.4 K-means用戶聚類

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

2.5 算法流程

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

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

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

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

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

3.2 試驗(yàn)結(jié)果

實(shí)驗(yàn)一：驗(yàn)證本文算法的準(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。試驗(yàn)證明將用戶分為11個類時，Slope One算法運(yùn)行效果最好，MAE值最低。

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

4 結(jié)語

針對傳統(tǒng)Slope One算法未考慮用戶與物品相似性，以及在當(dāng)前大數(shù)據(jù)環(huán)境下運(yùn)行效率較低的問題，提出一種基于聚類與Spark的改進(jìn)加權(quán)Slope One算法。該算法通過少而精的數(shù)據(jù)從數(shù)據(jù)來源角度提升算法的性能和準(zhǔn)確率。試驗(yà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)計(jì)與管理， 2012，31（2）：325-332.

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

[3] 蔣宗禮，杜倩. 基于聚類和項(xiàng)目相似性的Slope One算法優(yōu)化[J].計(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>