基于Spark的Slope One算法優化與實現

梁化強 唐堅剛

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

關鍵詞：Slope One；聚類；用戶相似性；項目相似度；Spark

DOI：10.11907/rjdk.172877

中圖分類號：TP312

文獻標識碼：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 引言

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

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

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

1 Slope One算法理論

1.1 基本Slope One算法

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

1.2 兩種SlopeOne改進算法

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

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

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

2 基于聚類與Spark的加權Slope One算法

2.1 項目相似度計算

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

2.2 項目綜合權重

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

2.3 活躍用戶評定

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

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

在預測評分時，僅對Uact集合中的用戶進行聚類。

2.4 K-means用戶聚類

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

2.5 算法流程

綜上所述，基于聚類的加權Slope One算法的具體步驟如下：①在總項目集中查找目標用戶u的未評分項目集合記為Items；②利用公式（13）篩選出活躍用戶集Uact；③對活躍用戶集Uact進行K-means聚類，得到k個聚類中心，以及k個用戶集合U-1，U-2，…，U-k；④根據式（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其中之一；⑥根據K-U-u、L-U-u（K-U-u為用戶u所在用戶集合的項目評分偏差矩陣，L-U-u為用戶u所在用戶集合的項目相似度矩陣）可以計算式（11）、（12），其中dev-ij在K-U-u中查找，得到p（u）-j；⑦根據P（u）-j為目標用戶u生成前N個推薦項目。

3 試驗結果與分析

3.1 實驗環境、測試數據集及評價指標

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

3.2 試驗結果

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

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

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

4 結語

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

參考文獻：

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

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

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

[4] 陸勝偉，唐振民，呂建勇. 基于時間因子的Slope One協同過濾推薦算法[J].信息技術，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.

（責任編輯：黃 健）