基于聚類和Spark框架的加權Slope One算法

李淋淋，倪建成，于蘋蘋，姚彬修，曹 博

(1.曲阜師范大學 信息科學與工程學院，山東 日照 276826； 2. 曲阜師范大學 軟件學院，山東 曲阜 273165)

基于聚類和Spark框架的加權Slope One算法

李淋淋1，倪建成2*，于蘋蘋1，姚彬修1，曹 博1

(1.曲阜師范大學 信息科學與工程學院，山東 日照 276826； 2. 曲阜師范大學 軟件學院，山東 曲阜 273165)

(*通信作者電子郵箱nijch@163.com)

針對傳統Slope One算法在相似性計算時未考慮項目屬性信息和時間因素對項目相似性計算的影響，以及推薦在當前大數據背景下面臨的計算復雜度高、處理速度慢的問題，提出了一種基于聚類和Spark框架的加權Slope One算法。首先,將時間權重加入到傳統的項目評分相似性計算中，并引入項目屬性相似性生成項目綜合相似度；然后,結合Canopy-K-means聚類算法生成最近鄰居集；最后,利用Spark計算框架對數據進行分區迭代計算，實現該算法的并行化。實驗結果表明，基于Spark框架的改進算法與傳統Slope One算法、基于用戶相似性的加權Slope One算法相比，評分預測準確性更高，較Hadoop平臺下的運行效率平均可提高3.5～5倍，更適合應用于大規模數據集的推薦。

Slope One算法；聚類；Spark；時間權重；項目屬性

0 引言

海量信息的增長導致了嚴重的信息過載，如何從大量的信息中快速地分析出用戶的興趣愛好,主動為用戶推薦感興趣的信息成為當前研究的熱點問題。Slope One算法是由Lemire等[1]提出的一種協同過濾推薦算法，該算法具有簡單、高效、推薦準確率高并且能夠緩解冷啟動問題等優點; 但隨著數據規模的不斷增大，該算法面臨的數據稀疏性、實時性、可擴展性等問題越來越嚴重，導致推薦質量大幅下降。

針對這些問題，學者們提出了許多改進方法。劉林靜等[2]提出一種基于用戶相似性的加權Slope One算法，首先根據項目相似性進行預測填充，然后根據用戶相似性形成最近鄰居集合并進行推薦預測，有效地緩解了數據稀疏性問題。Zhang等[3]提出一種引入用戶興趣相似性計算的Slope One算法，在用戶最喜愛的項目中計算相似度矩陣，從而提高推薦準確性。文獻[4-6]通過引入聚類，從而減小算法計算復雜度，提高推薦實時性。于洪等[7]提出利用三分圖的形式結合用戶、標簽、項目屬性、時間等信息獲得個性化推薦的算法，在一定程度上解決了新項目的冷啟動問題。針對運行效率問題，文獻[8-10]提出基于Hadoop平臺的推薦算法，有效提高了算法的可擴展性。

本文基于以上研究，針對加權Slope One算法僅考慮利用項目評分來度量對象之間的相似性，較少考慮項目本身的屬性特征和用戶興趣隨時間的變化特征，這在很大程度上影響了推薦準確性。因此本文綜合項目評分、項目屬性、時間權重等信息，結合聚類算法和具有內存計算、迭代計算優勢的Spark框架[11]，提出一種改進的基于聚類和Spark框架的加權Slope One算法，以進一步提高Slope One算法的預測準確性、運行效率和可擴展性。

1 相關工作

1.1 用戶—項目評分矩陣

在傳統的協同過濾推薦算法中，利用m×n階用戶—項目矩陣儲存用戶對項目的評分信息。使用集合{u1,u2,…,um}表示m個用戶，使用集合{i1,i2,…,in}表示n個項目，使用Ri, j表示用戶對項目的評分值。表1為用戶—項目評分矩陣的一個例子。

表1 用戶—項目評分矩陣Tab. 1 User-item score matrix

注：—表示未評分。

1.2 傳統的Slope One算法

Slope One 算法的預測形如一個線性函數f(x)=x+b，假設一個用戶對兩個項目的評分分別為x、y(該算法假設x和y之間是線性的，形如y=x+b)。通過將這兩個項目有過共同評分的用戶評分集進行線性擬合，得到b的估計值，從而對未評分項目預測評分。因此，在進行推薦預測時，只需要在預處理過程中根據式(1)計算出所有項目之間的平均偏好差異值矩陣{devj,i}，然后再根據式(2)即可計算出目標用戶對某個未評分項目的預測評分值P(u)j。

(1)

(2)

其中:χ表示訓練集，Sj,i(χ)表示評價過項目i,j的用戶集合，Ru, j、Ru,i分別表示用戶u對項目j，i的評分值(u∈Sj,i(χ))，Rj為用戶u已經評價過的項目集合，card(N)表示集合N中的元素個數。

以表1為例，預測用戶u1對項目i3的評分?？紤]對項目i3已評分的用戶u2、u3，則首先使用式(1)計算評分偏差值dev3,2=[(3-3)+(4-2)]/2=1，dev3,4=(3-3)/1=0；然后使用式(2)計算用戶u1對項目i3的評分P(u1)3=[(4+1)+(5+0)]/2=5；最后在預測所有的未評分項目之后根據預測評分高低為目標用戶生成Top-N推薦。

1.3 項目評分相似性

相似性的度量是推薦算法中非常重要的一部分，用來衡量項目之間的相關程度, 其計算結果的準確性決定了最近鄰居集合的準確性，因而也決定了評分預測值的準確性。相關相似性(Pearson系數)是以用戶評分為基礎，并在此基礎上減去項目的平均評分，保留了用戶的打分偏好，更能反映出項目之間的相關性，因此本文使用式(3)計算項目之間的評分相似性:

(3)

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

2.1 時間衰減函數

由于時間的變化，用戶的關注點會隨之改變,而用戶最近的行為對用戶影響程度相對較大，對推薦貢獻的作用也相對較高，所以應該賦予較大權重[12]。然而傳統Slope One算法并沒有考慮到用戶興趣隨時間的變化，同等看待不同時間的評分值，因此得到的平均偏好差異值矩陣和評分預測值在某種程度上是不準確的，嚴重降低了推薦準確性。

本文采用改進的時間衰減函數對項目評分值進行加權處理，對距離當前時間較近的評分值賦予較大的權重，對距離當前時間較遠的評分值賦予較小的權重，以此來反映用戶興趣隨時間的變化。時間衰減函數如式(4)、(5)所示：

(4)

(5)

其中：t0表示當前的時間；t(Ru,i)表示用戶u對項目i的評分時間；t(Ru, j)表示用戶u對項目j的評分時間；α是時間衰減因子，α值的大小代表用戶興趣變化的快慢。用戶興趣變化大，α取較大值；用戶興趣變化小，α取較小值。

本文在項目評分相似性計算時考慮時間因素的影響，為每個項目評分值賦予相應的時間權重, 這樣更能體現出項目之間的實際相似程度，從而進一步提高相似性度量的準確率。優化后的Pearson系數計算公式如式(6)所示：

(6)

2.2 項目屬性相似性

對于系統剛剛加入的新項目，由于用戶對其進行評分的信息相對較少，僅利用評分相似性加權實現預測和推薦，會造成較大誤差，影響推薦質量。因此，本文考慮引入項目屬性相似性來緩解此問題。對于任何一個項目，不管是被用戶評價過的項目還是剛剛加入系統的新項目，都具備相應的屬性信息。故本文在相似度計算時加入項目屬性信息，利用n×g階矩陣儲存該信息[7]，使用集合{i1,i2,…,in}表示n個項目，集合{p1,p2,…,pg}表示g個屬性，Attri,k表示項目i具備第k個屬性。那么項目i和項目j之間的屬性相似性計算公式如式(7)所示：

(7)

2.3 項目綜合相似性

當用戶對項目的評分信息比較多時，考慮到應該更多地傾向于使用項目評分相似性來度量項目相似度; 在新項目剛剛加入或者用戶評分信息非常少時，應該更多地傾向于使用項目屬性相似性來度量項目相似度, 故本文將項目評分相似性和項目屬性相似性進行融合，并采用Sigmoid函數對其進行平滑過渡處理[13]，融合后的綜合相似度計算公式如(8)所示：

sim(i,j)_mix=γ·tsim_score(i,j)+β·sim_attr(i,j)

(8)

其中:β=1-1/[1+e-card(Ui)];γ=1-β。

2.4 Canopy-K-means項目聚類算法

隨著項目數量的不斷增長，在全局計算平均偏好差異值矩陣將更加費時費力，不能滿足推薦實時性的要求[4]。故本文引入聚類算法，通過聚類，將特征、評分值相似的項目快速劃分到相同的簇中。然后在與目標項目相似的部分類中查找最近鄰居，從而縮短查找時間，提高算法的實時響應速度。由于傳統K-means聚類算法初始中心點的選擇是隨機的，不確定性較大，因此本文利用Canopy算法對其進行優化，避免初始聚類中心和k值選取的盲目性，提高聚類準確性。其具體實現的偽代碼描述如下。

Input：項目評分向量集I={I1,I2,…,In}，Canopy距離閾值T1,T2(采用交叉檢驗方式獲得)

Output：個項目聚類集合，聚類中心集合W′

1)

If(Q=null)

2)

從I中任取一個向量,加入Q并從中刪除

3)

End If

4)

While(I！=null)

5)

遍歷I,利用歐氏距離快速計算每個向量點與Q中點的距離dist[i]

6)

If (dist[i]

7)

Else If (dist[i]>T1),將該點加入Q，并從中刪除

8)

Else 將該點加入到此點所屬的Canopy

9)

End If

10)

End While

11)

K-means算法初始中心點W←Q

12)

While(I！=null)

13)

按式(8)依次計算I中其他向量點到W中各點的相似度，并將其劃分到相似度最高的類中

14)

For(W!=W′)

15)

對每個類重新計算均值，并作為新的聚類中心W′

16)

End For

17)

End While

2.5 預測和推薦

傳統加權Slope One算法評分預測時將項目之間的共同評分用戶數作為權重，共同評分用戶較多的項目所占權重相對較大，容易產生較大的誤差，而且該方法忽略了項目相似性的問題，其對目標項目的評分預測影響作用更大。為進一步提高預測準確性，本文將項目綜合相似度作為評分預測權重，并結合時間衰減函數，進一步優化Slope One模型，優化后的平均偏好差異值矩陣{devj,i}計算公式和預測評分值計算公式分別為式(9)、(10)：

(9)

(10)

2.6 基于聚類的加權Slope One算法描述

綜合上述所述，基于聚類的加權Slope One算法的具體步驟如下：

1)初始化數據集，構造目標用戶u的未評分項目集合Items。

2)利用式(6)、(7)分別計算評分相似性、屬性相似性，再利用式(8)計算綜合相似度。

3)根據2.4節所示，利用Canopy-K-means算法完成項目聚類。

4)利用式(8)計算目標項目Ij與每個聚類中心的相似度，在相似度大于閾值ε的部分聚類中搜索該項目的最近鄰居集合，并選取k個相似度較高的項目Ij構成目標項目的最近鄰居集合Nei={I1,I2,…,In}，其中sim(i,j)_mix(I1,Ij)最高，sim(i,j)_mix(I2,Ij)次之，相似度依次遞減。

5)在目標項目Ij的最近鄰居集合中利用式(9)、(10)進行評分預測。

6)根據預測評分值P(u)j,為目標用戶u生成Top-N個推薦項目。

2.7 時間復雜度分析

由于項目數量很多，導致綜合相似度計算的時間復雜度非常大，為O(mn2)。但考慮到項目更新緩慢，故可對其進行離線并行計算，從而不會影響在線推薦效率。另外對于比較耗時的聚類，本文也選擇進行離線周期并行化聚類，離線計算聚類中心，在線計算目標項目與k個類別內的p個項目的相似度，p是每個類中的項目數。因為k?n，p?n，所以計算目標項目與聚類中心、聚類內項目相似度的時間復雜度O(k*n)+O(p*n)?O(mn2)，故本文算法可有效降低時間復雜度。

3 基于聚類和Spark框架的加權Slope One算法

隨著項目數和用戶數的不斷增多，Slope One算法在執行過程中的中間結果也隨之增多，當超過內存容量時只能先寫到讀取速度緩慢的磁盤中，嚴重影響了推薦效率。因此本文利用具有內存計算優勢的Spark框架，加快數據處理速度，提高算法的運行效率。

3.1 Spark框架

Spark是一套開源的、基于內存的可以運行在分布式集群上的并行計算框架，具有高效性、通用性、高容錯性等優點[14]。利用彈性分布式數據集(Resilient Distributed Dataset, RDD)實現應用任務調度、遠程過程調用(Remote Procedure Call, RPC)、序列化和壓縮等操作；利用有向無環圖(Directed Acyclic Graph, DAG)實現各階段任務的并行執行；利用Cache機制降低數據共享和迭代計算中的I/O負載問題，從而有效提高了數據處理速度。

每個Spark應用由驅動器程序(drive program)發起并負責創建相應的SparkContext。在獲取到集群進行所需的資源后，SparkContext將得到集群中工作節點上對應的Executor，之后再將應用程序代碼發送到各Executor,最后將任務(Task)分配給executors執行。本文中使用基于YARN的Spark，具體工作流程如圖1所示。

3.2 基于聚類的加權Slope One算法的并行化實現

在推薦過程中由于項目數量非常多，在聚類、尋找K近鄰和預測過程中需要進行大量的相似度計算和平均偏好差異值計算，因此本文利用并行化來提高計算效率，提高算法的運行速率。該過程具體化為兩個階段: 階段一為Canopy-K-means聚類并行化，階段二為加權Slope One算法的并行化。

在階段一中，首先對數據集進行預處理形成〈key,value〉鍵值對，并將結果存入HadoopRDD中。然后調用groupBykey()函數獲取User-Item，Attribute-Item的倒排表，并調用reduceBykey()函數統計Item之間的共同評分的User及自己的評分用戶數、屬性數等。然后利用 Similaritymap()函數計算評分相似性、屬性相似性，并在此基礎上計算綜合相似性并存入 SimilarityRDD中。接著利用Clustermap()迭代執行Canopy-K-means算法，直到完成所有數據向量點的聚類，利用ClusterReduce ()歸并、匯總最終聚類結果，并將其廣播到各子節點中。

圖1 Spark工作流程Fig. 1 Working flow chart of Spark

4 實驗結果與分析

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

實驗平臺是在Hadoop2.6.0的YARN基礎上部署Spark框架，在Vcenter中創建4臺虛擬機，包含1個Master節點和3個Slave節點。操作系統版本均為Ubuntu 14.04.3-Server-AMD 64，Hadoop版本為2.6.0，Spark版本為1.4.0，Java開發包版本為JDK1.7.0_79。

實驗采用由GroupLens Reaearch提供的MovieLens數據集(http://grouplens.org/dataset/)，包括ml-100k的數據包(包含943個用戶對1 682部電影的100 000條評分記錄)和ml-1M的數據集(包含6 040個用戶對3 952部電影的1 000 209條評分記錄)。實驗采用十折交叉驗證法進行驗證，將數據集隨機分為不相交的10個包，輪流將其中的9份作為訓練集，其余1份作為測試集，每次實驗重復執行10次，最后的實驗結果采用10次實驗結果的平均值。

本文使用平均絕對誤差(Mean Absolute Error，MAE)來衡量算法的評分預測準確性，MAE值越小，預測精度越高；反之，則越差；并在此基礎上探究本文算法在不同平臺和不同節點下的運行時間和加速比(Speedup)、擴展比(Scaleup)，以驗證算法的執行效率。

其中χ′表示測試集。

Speedup=Ts/TP

其中：Ts是單節點運行時間，TP是P個節點運行時間。

Scaleup=Speedup/TP

其中：P為集群節點數目。

4.2 實驗結果

實驗一 探究時間衰減因子權重α、相似度閾值ε對實驗結果的影響。

采用ml-100k的數據集，假定在聚類未引入時間權重情況下，最近鄰居數k=30時，將α從0.1依次遞增到0.9，分別觀察ε=0.2，ε=0.3，ε=0.4時MAE的變化。實驗結果如圖2所示，無論ε為何值，當α逐漸增大時，MAE都是先減小后增大，并在α=0.3時取得最小值，而且變化幅度不大，這說明該系統用戶對電影的興趣變化比較緩慢。另外，在ε=0.4時，MAE較高，推薦準確性較差。這是因為相似度閾值設置較高，在構造最近鄰居集時，只需要在符合閾值條件的幾個候選聚類中查詢、計算即可，提高了算法的響應速度。但另一方面，由于查詢候選聚類過少，在某種程度上造成一部分真正鄰居項目的遺漏，從而影響了推薦結果的準確性。因此，基于保證推薦準確性和提高算法響應速度兩方面的考慮，設定α=0.3，ε=0.3。

圖2 不同α下的MAE比較Fig. 2 MAE with different α

實驗二 驗證本文算法的準確性、有效性。

采用ml-100k的數據集，將本文算法與傳統Slope One算法、文獻[2]中基于用戶相似性的加權Slope One算法、本文提出的優化算法、基于Spark框架的該算法(4個節點)在不同的鄰居數下k的MAE比較(α=0.3，ε=0.3，最近鄰居數k從25依次遞增到200，間隔為25)如表2所示。

表2 不同算法的MAE比較Tab. 2 MAE of different algorithms

從表2可以看出，隨著k值的增大，各個算法的MAE值都是會隨之降低: 當k≥50時，本文算法MAE值小于傳統Slope One算法；當k≥75時，其MAE值小于文獻[2]算法；當鄰居數k≥150時，其MAE值慢慢趨于穩定。另外，基于Spark框架下的優化算法MAE值和串行方式下基本相平，這說明基于Spark框架的該算法在保證準確率的同時更適合用于大規模數據的推薦預測中。

另外，為進一步驗證本文算法的有效性，將傳統Slope One算法、基于聚類的Slope One算法、本文優化的Slope One算法(引入聚類和綜合相似度)在不同鄰居數k下的MAE值進行比較。如圖3所示，在k=175時，引入聚類后的算法MAE值降低了9.9%，進一步引入綜合相似度后，MAE值又降低了4.2%，這說明引入聚類和綜合相似度，可有效提高算法的預測準確性。

圖3 三種算法的有效性比較Fig. 3 Comparison of validity by three algorithms

實驗三 比較本文算法在不同平臺、不同數據集的運行效率。

采用ml-100k、ml-1M的數據集，分別統計本文算法在Hadoop平臺和Spark框架下不同節點數時的運行時間。實驗結果如表3所示，隨著節點數目增多，兩種框架下的運行時間都逐漸減小，并且Spark框架下的運行時間更短。這說明Spark框架的執行性能要優于Hadoop平臺，運行效率平均可提高3.5～5倍。主要原因是算法在Hadoop平臺中的數據計算、I/O傳輸時花費時間較多，這在大樣本數據集中尤為明顯。而Spark框架將中間結果緩存在內存中，減少了數據讀取和傳輸時間，從而大幅提高了運行速度。

表3 兩個數據集在不同平臺的運行時間比較 sTab. 3 Running time of two datasets in different platform s

注：— 表示out of memory。

為進一步測試Spark框架下本文算法的可擴展性，分別測試ml-100k、ml-1M數據集在不同節點下的加速比、擴展比。實驗結果如圖4、圖5所示，隨著節點數目的增加，較大規模的數據集加速比提高更快，基本呈線性增長，擴展比變化趨勢也比較平緩。這說明Spark框架在處理本文算法上具有良好的可擴展性，并且這種優勢會隨節點數目的增加、數據集的增大而更加明顯。

5 結語

本文主要對影響Slope One算法的預測準確性和可擴展性等各因素進行優化，將項目綜合相似度與Slope One算法相結合，利用Canopy-K-means聚類算法生成最近鄰居集合; 并在相似度計算、預測過程中引入時間權重，有效地提高了Slope One算法的推薦準確性。另一方面針對可擴展性問題，結合Spark框架實現其并行化，有效地提高了該算法對大規模數據集的處理效率，提高了算法的可擴展性。下一步工作將在改善數據稀疏性方面[15]展開研究，以進一步提高算法的綜合性能。

圖5 兩個數據集在Spark框架的擴展比比較Fig. 5 Scaleup of two date sets in Spark

References)

[1] LEMIRE D, MACLACHLAN A. Slope One predictors for online rating-based collaborative filtering[EB/OL].[2016-10-20]. https://core.ac.uk/download/pdf/2423561.pdfg.

[2] 劉林靜, 樓文高, 馮國珍. 基于用戶相似性的加權Slope One算法[J]. 計算機應用研究, 2016,33(9):2708-2711.(LIU L J,LOU W G,FENG G Z. New weighted Slope One algorithm based on user similarity[J]. Application Research of Computers, 2016, 33(9):2708-2711.)

[3] ZHANG Z, TANG X, CHEN D. Applying user-favorite-item-based similarity into Slope One scheme for collaborative filtering[C]// Proceedings of the 2014 World Congress on Computing and Communication Technologies. Washington, DC:IEEE Computer Society, 2014: 5-7.

[4] ZHAO Z, LI J. Based on Slope-One hybrid recommendation[C]// Proceedings of the 2014 IEEE Workshop on Advanced Research and Technology in Industry Applications. Piscataway, NJ:IEEE, 2014:203-205.

[5] 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.

[6] YING Y, CAO Y. Collaborative filtering recommendation combining FCM and Slope One algorithm[C]// Proceedings of the 2015 International Conference on Informative and Cybernetics for Computational Social Systems. Piscataway, NJ: IEEE, 2015:1052-1060.

[7] 于洪, 李俊華. 一種解決新項目冷啟動問題的推薦算法[J]. 軟件學報, 2015, 26(6):1395-1408.(YU H, LI J H. Algorithm to solve the cold-start problem in new item recommendations[J]. Journal of Software, 2015, 26(6):1395-1408.)

[8] 孫天昊,黎安能,李明,等. 基于Hadoop分布式改進聚類協同過濾推薦算法研究[J]. 計算機工程與應用,2015,51(15):124-128.(SUN T H, LI A N, LI M, et al. Study on distributed improved clustering collaborative filtering algorithm based on Hadoop[J]. Computer Engineering and Applications, 2015, 51(15):124-128.)

[9] ZHANG Y L, MA M M, WANG S P. Research of user-based collaborative filtering recommendation algorithm based on Hadoop[EB/OL].[2016-06-20]. http://www.atlantis-press.com/php/download_paper.php?id=22451.

[10] XING C, WANG H. Clustering weighted slope one for distributed parallel computing[C]// Proceedings of the 2011 International Conference on Computer Science and Network Technology. Piscataway, NJ: IEEE, 2011, 3: 1595-1598.

[11] KUPISZ B, UNOLD O. Collaborative filtering recommendation algorithm based on Hadoop and Spark[C]// Proceedings of the 2015 IEEE International Conference on Industrial Technology. Piscataway, NJ: IEEE, 2015: 1510-1514.

[12] JIANG T Q, LU W. Improved slope one algorithm based on time weight[J]. Applied Mechanics and Materials, 2013, 347: 2365-2368.

[13] 丁少衡, 姬東鴻, 王路路. 基于用戶屬性和評分的協同過濾推薦算法[J]. 計算機工程與設計, 2015, 36(2): 487-491.(DING S H, JI D H, WANG L L. Collaborative filtering recommendation algorithm based one user attributes and scores[J]. Computer Engineering and Design, 2015, 36(2): 487-491.)

[14] ARMBRUST M, DAS T, DAVIDSON A, et al. Scaling spark in the real world: performance and usability[J]. Proceedings of the VLDB Endowment, 2015, 8(12): 1840-1843.

[15] 郝立燕, 王靖. 基于填充和相似性信任因子的協同過濾推薦算法[J]. 計算機應用, 2013, 33(3): 834-837.(HAO L Y, WANG J. Collaborative filtering recommendation algorithm based on filling and similarity confidence factor[J]. Journal of Computer Applications, 2013, 33(3): 834-837.)

This work is partially supported by the National Natural Science Foundation of China (the Youth Fund) (61402258), the Research Project of Teaching Reform in Undergraduate Colleges and Universities in Shandong Province (2015M102), the Research Project of Teaching Reform in Qufu Normal Universities (jg05021*).

LI Linlin, born in 1991, M. S. candidate. Her research interests include parallel and distributed computing, data mining.

NI Jiancheng, born in 1971, Ph. D., professor. His research interests include distributed computing, machine learning, data mining.

YU Pingping, born in 1991, M. S. candidate. Her research interests include distributed computing, data mining.

YAO Binxiu, born in 1991, M. S. candidate. His research interests include distributed computing, data mining, microblog recommendation.

CAO Bo, born in 1992, M. S. candidate. Her research interests include parallel and distributed computing, data mining.

Weighted Slope One algorithm based on clustering and Spark framework

LI Linlin1, NI Jiancheng2*, YU Pingping1, YAO Binxiu1, CAO Bo1

(1.CollegeofInformationScienceandEngineering,QufuNormalUniversity,RizhaoShandong276826,China;2.CollegeofSoftwareEngineering,QufuNormalUniversity,QufuShandong273165,China)

In view of that the traditional Slope One algorithm does not consider the influence of project attribute information and time factor on project similarity calculation, and there exists high computational complexity and slow processing in current large data background, a weighted Slope One algorithm based on clustering and Spark framework was put forward. Firstly, the time weight was added to the traditional item score similarity calculation, and comprehensive similarity was computed with the similarities of the item attributes. And then the set of nearest neighbors was generated through combining with the Canopy-K-means algorithm. Finally, the data was partitioned and iterated to realize parallelization by Spark framework. The experimental results show that the improved algorithm based on the Spark framework is more accurate than the traditional Slope One algorithm and the Slope One algorithm based on user similarity, which can improve the operating efficiency by 3.5-5 times compared with the Hadoop platform, and is more suitable for large-scale dataset recommendation.

Slope One algorithm; clustering; Spark; time weight; item attribute

2016-09-30;

2016-12-07。 基金項目:國家自然科學基金青年基金資助項目(61402258); 山東省本科高校教學改革研究項目(2015M102); 校級教學改革研究項目(jg05021*)。

李淋淋(1991—)，女，山東德州人，碩士研究生，CCF會員，主要研究方向：并行與分布式計算、數據挖掘； 倪建成(1971—)，男，山東濟寧人，教授，博士，CCF會員，主要研究方向：分布式計算、機器學習；數據挖掘； 于蘋蘋(1991—)，女，山東濟南人，碩士研究生，CCF會員，主要研究方向：分布式計算、數據挖掘； 姚彬修(1991—)，男，山東濰坊人，碩士研究生，CCF會員，主要研究方向：分布式計算、數據挖掘、微博推薦； 曹博(1992—)，女，黑龍江伊春人，碩士研究生，CCF會員，主要研究方向：并行與分布式計算、數據挖掘。

1001-9081(2017)05-1287-05

10.11772/j.issn.1001-9081.2017.05.1287

TP391

A