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

(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)

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

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

0 引言

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

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

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

1 相關(guān)工作

1.1 用戶—項(xiàng)目評(píng)分矩陣

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

表1 用戶—項(xiàng)目評(píng)分矩陣Tab. 1 User-item score matrix

注：—表示未評(píng)分。

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

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

(1)

(2)

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

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

1.3 項(xiàng)目評(píng)分相似性

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

(3)

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

2.1 時(shí)間衰減函數(shù)

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

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

(4)

(5)

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

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

(6)

2.2 項(xiàng)目屬性相似性

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

(7)

2.3 項(xiàng)目綜合相似性

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

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

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

Output：個(gè)項(xiàng)目聚類集合，聚類中心集合W′

1)

If(Q=null)

2)

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

3)

End If

4)

While(I！=null)

5)

遍歷I,利用歐氏距離快速計(jì)算每個(gè)向量點(diǎn)與Q中點(diǎn)的距離dist[i]

6)

If (dist[i]

7)

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

8)

Else 將該點(diǎn)加入到此點(diǎn)所屬的Canopy

9)

End If

10)

End While

11)

K-means算法初始中心點(diǎn)W←Q

12)

While(I！=null)

13)

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

14)

For(W!=W′)

15)

對(duì)每個(gè)類重新計(jì)算均值，并作為新的聚類中心W′

16)

End For

17)

End While

2.5 預(yù)測(cè)和推薦

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

(9)

(10)

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

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

1)初始化數(shù)據(jù)集，構(gòu)造目標(biāo)用戶u的未評(píng)分項(xiàng)目集合Items。

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

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

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

5)在目標(biāo)項(xiàng)目Ij的最近鄰居集合中利用式(9)、(10)進(jìn)行評(píng)分預(yù)測(cè)。

6)根據(jù)預(yù)測(cè)評(píng)分值P(u)j,為目標(biāo)用戶u生成Top-N個(gè)推薦項(xiàng)目。

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

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

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

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

3.1 Spark框架

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

其中χ′表示測(cè)試集。

Speedup=Ts/TP

其中：Ts是單節(jié)點(diǎn)運(yùn)行時(shí)間，TP是P個(gè)節(jié)點(diǎn)運(yùn)行時(shí)間。

Scaleup=Speedup/TP

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

4.2 實(shí)驗(yàn)結(jié)果

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

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

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

實(shí)驗(yàn)二 驗(yàn)證本文算法的準(zhǔn)確性、有效性。

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

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

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

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

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

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

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

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

注：— 表示out of memory。

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

5 結(jié)語(yǔ)

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

圖5 兩個(gè)數(shù)據(jù)集在Spark框架的擴(kuò)展比比較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] 劉林靜, 樓文高, 馮國(guó)珍. 基于用戶相似性的加權(quán)Slope One算法[J]. 計(jì)算機(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] 于洪, 李俊華. 一種解決新項(xiàng)目冷啟動(dòng)問題的推薦算法[J]. 軟件學(xué)報(bào), 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ìn)聚類協(xié)同過濾推薦算法研究[J]. 計(jì)算機(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] 丁少衡, 姬東鴻, 王路路. 基于用戶屬性和評(píng)分的協(xié)同過濾推薦算法[J]. 計(jì)算機(jī)工程與設(shè)計(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] 郝立燕, 王靖. 基于填充和相似性信任因子的協(xié)同過濾推薦算法[J]. 計(jì)算機(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。 基金項(xiàng)目:國(guó)家自然科學(xué)基金青年基金資助項(xiàng)目(61402258); 山東省本科高校教學(xué)改革研究項(xiàng)目(2015M102); 校級(jí)教學(xué)改革研究項(xiàng)目(jg05021*)。

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

1001-9081(2017)05-1287-05

10.11772/j.issn.1001-9081.2017.05.1287

TP391

A