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

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

基于聚類和Spark框架的加權(quán)Slope One算法

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

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

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

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

Slope One算法；聚類；Spark；時間權(quán)重；項目屬性

0 引言

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

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

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

1 相關(guān)工作

1.1 用戶—項目評分矩陣

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

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

注：—表示未評分。

1.2 傳統(tǒng)的Slope One算法

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

(1)

(2)

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

以表1為例，預(yù)測用戶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；最后在預(yù)測所有的未評分項目之后根據(jù)預(yù)測評分高低為目標用戶生成Top-N推薦。

1.3 項目評分相似性

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

(3)

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

2.1 時間衰減函數(shù)

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

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

(4)

(5)

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

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

(6)

2.2 項目屬性相似性

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

(7)

2.3 項目綜合相似性

當用戶對項目的評分信息比較多時，考慮到應(yīng)該更多地傾向于使用項目評分相似性來度量項目相似度; 在新項目剛剛加入或者用戶評分信息非常少時，應(yīng)該更多地傾向于使用項目屬性相似性來度量項目相似度, 故本文將項目評分相似性和項目屬性相似性進行融合，并采用Sigmoid函數(shù)對其進行平滑過渡處理[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項目聚類算法

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

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 預(yù)測和推薦

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

(9)

(10)

2.6 基于聚類的加權(quán)Slope One算法描述

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

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

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

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

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

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

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

2.7 時間復(fù)雜度分析

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

3 基于聚類和Spark框架的加權(quán)Slope One算法

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

3.1 Spark框架

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

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

3.2 基于聚類的加權(quán)Slope One算法的并行化實現(xiàn)

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

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

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

4 實驗結(jié)果與分析

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

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

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

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

其中χ′表示測試集。

Speedup=Ts/TP

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

Scaleup=Speedup/TP

其中：P為集群節(jié)點數(shù)目。

4.2 實驗結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

注：— 表示out of memory。

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

5 結(jié)語

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

圖5 兩個數(shù)據(jù)集在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] 劉林靜, 樓文高, 馮國珍. 基于用戶相似性的加權(quán)Slope One算法[J]. 計算機應(yīng)用研究, 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]. 軟件學(xué)報, 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分布式改進聚類協(xié)同過濾推薦算法研究[J]. 計算機工程與應(yīng)用,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] 丁少衡, 姬東鴻, 王路路. 基于用戶屬性和評分的協(xié)同過濾推薦算法[J]. 計算機工程與設(shè)計, 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] 郝立燕, 王靖. 基于填充和相似性信任因子的協(xié)同過濾推薦算法[J]. 計算機應(yīng)用, 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。 基金項目:國家自然科學(xué)基金青年基金資助項目(61402258); 山東省本科高校教學(xué)改革研究項目(2015M102); 校級教學(xué)改革研究項目(jg05021*)。

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

1001-9081(2017)05-1287-05

10.11772/j.issn.1001-9081.2017.05.1287

TP391

A