鐘桂鳳,龐雄文,孫道宗,劉宇東

(1.廣州理工學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院,廣東 廣州 510540;2.華南師范大學(xué) 計(jì)算機(jī)學(xué)院,廣東 廣州 530631;3.華南農(nóng)業(yè)大學(xué) 電子工程學(xué)院,廣東 廣州 510642)

互聯(lián)網(wǎng)高速發(fā)展,網(wǎng)絡(luò)數(shù)據(jù)量迅速增長(zhǎng),用戶對(duì)網(wǎng)絡(luò)的依賴程度及數(shù)據(jù)獲取便捷度的需求明顯提升,用戶主動(dòng)搜索獲取服務(wù)的方式正逐漸改變[1],平臺(tái)推薦服務(wù)方式被用戶青睞。對(duì)于區(qū)塊鏈和資源共享等網(wǎng)絡(luò)服務(wù)平臺(tái)來說,數(shù)據(jù)資源需要進(jìn)行聚類歸檔,并根據(jù)用戶在平臺(tái)的訪問和使用習(xí)慣[2],對(duì)用戶進(jìn)行類別評(píng)分,然后根據(jù)相似度計(jì)算獲得用戶和資源的相似關(guān)系,最后為用戶推薦相似度最高的資源。這種基于數(shù)據(jù)聚類的智能推薦系統(tǒng)是當(dāng)前網(wǎng)絡(luò)推薦系統(tǒng)的主流模式,這種模式因?yàn)樯婕暗骄垲愡\(yùn)算,在類別較多且數(shù)據(jù)規(guī)模較大的情況下,推薦的準(zhǔn)確率和效率均會(huì)受到影響,因此多類別聚類和大規(guī)模運(yùn)算效率是該推薦模式需要重點(diǎn)解決的問題。

當(dāng)前,基于聚類挖掘的智能推薦技術(shù)研究較多,Liu等[3]采用深度模型來實(shí)現(xiàn)K-means聚類挖掘,并用于在線學(xué)習(xí)資源推薦,能夠根據(jù)用戶短時(shí)間的學(xué)習(xí)習(xí)慣進(jìn)行資源推薦,但是受模型限制,推薦的準(zhǔn)確率并不高;Liu等[4]采用深度學(xué)習(xí)算法來提升K-means聚類的準(zhǔn)確率,對(duì)網(wǎng)站在線用戶提供廣告推薦,具有一定的智能推薦效果,但也出現(xiàn)了輕度誤判;Ming等[5]根據(jù)用戶歷史點(diǎn)歌情況,利用聚類挖掘算法實(shí)現(xiàn)了不同用戶的歌單推薦,取得了良好效果,但其采用的方法處于封閉歌單庫(kù)訓(xùn)練,導(dǎo)致適用度有一定局限。上述方法均在一定程度上提高了聚類的準(zhǔn)確率,但是均沒有效利用云計(jì)算平臺(tái)來提升推薦效率。

狼群算法是近期提出的一種新型群體智能優(yōu)化算法,能夠解決全局尋優(yōu)和局部極值問題。本文嘗試引入狼群算法來對(duì)K-means聚類算法進(jìn)行優(yōu)化,以提高多類別聚類的準(zhǔn)確率,同時(shí)引入Spark平臺(tái)的多節(jié)點(diǎn)并行計(jì)算來提高聚類和推薦效率。

1 Spark結(jié)構(gòu)

Spark作為大規(guī)模數(shù)據(jù)處理常用引擎,采用主-從節(jié)點(diǎn)管理模式共同完成數(shù)據(jù)處理任務(wù),但是在功能結(jié)構(gòu)上,主-從節(jié)點(diǎn)具有同等的運(yùn)算能力,其主要結(jié)構(gòu)[6,7],如圖1所示。

圖1 Spark結(jié)構(gòu)

除了這種主-從節(jié)點(diǎn)協(xié)同工作模式之外,Spark平臺(tái)還有一個(gè)優(yōu)點(diǎn)就是大部分?jǐn)?shù)據(jù)運(yùn)算都在其平臺(tái)節(jié)點(diǎn)內(nèi)存的彈性分布式數(shù)據(jù)集(Resilient distributed datasets,RDD)中完成,這種方式極大地提升了數(shù)據(jù)存取效率,完成大規(guī)模數(shù)據(jù)的聚類與推薦,解決了聚類中頻繁迭代造成的運(yùn)算效率不高問題,同時(shí)也解決了智能推薦的實(shí)時(shí)性問題。

2 基于狼群優(yōu)化的K-means聚類挖掘的協(xié)同過濾推薦

2.1 K-means算法

聚類空間中任意兩點(diǎn)i和j的距離Sij數(shù)學(xué)[8]表示

(1)

設(shè)中心點(diǎn)xi包含n個(gè)屬性,表示方法為(xi1,xi2,…,xin)和待聚類點(diǎn)xj(xj1,xj2,…,xjn),xi與xj的距離為

(2)

根據(jù)式(2)可以計(jì)算所有待聚類的樣本點(diǎn)至中心點(diǎn)距離集,根據(jù)距離dij來判定xi與xj是否同類。然后根據(jù)距離集建立聚類目標(biāo)函數(shù),求解式(3)的最小值

(3)

xj∈N(xi)意思是:xj為N個(gè)樣本點(diǎn)中除了中心點(diǎn)xi的剩余樣本點(diǎn),滿足:∑j,xj∈N(xi)Sijxj=1,Sij≥0。

將式(3)進(jìn)一步展開得[9]

(4)

最后得到目標(biāo)函數(shù)為

minε

(5)

K均值聚類的效率取決于待聚類點(diǎn)的維度與樣本數(shù)據(jù)量。一般而言,聚類的準(zhǔn)確率和效率隨著待聚類樣本的數(shù)量及維度增加而降低。在處理大規(guī)模聚類精度問題和聚類時(shí)間問題僅采用K-means算法不夠,因?yàn)?除了待聚類的數(shù)據(jù)量外,K均值聚類算法初始中心點(diǎn)的選擇也很重要,它影響著聚類的效率,所以,有必要對(duì)K-means算法進(jìn)行一定改進(jìn)。

2.2 狼群算法

設(shè)狼群總量為N,數(shù)據(jù)維度為D,則第i只狼位置為Xi=(xi1,xi2,…,xid,…xiD),其中1≤i≤N,1≤d≤D。

xid=xmin+rand*(xmax-xmin)

(6)

式中:xmax和xmin分別表示d維空間的上下限。rand為[0,1]隨機(jī)值。

根據(jù)適應(yīng)度值最高的狼作為頭狼,其周圍的為探狼,數(shù)量為Tnum,其游走步長(zhǎng)[10]為

StepG(d)=|maxd-mind|/S

(7)

式中:1≤d≤D,S為可設(shè)置的權(quán)重常量。

探狼位置更新

(8)

式中:i=1,2,…,Tnum,h為游走方向數(shù)。

狼群中剩余狼移動(dòng)步長(zhǎng)

StepB(d)=2×|maxd-mind|/S

(9)

位置更新為

式中:i=1,2,…,N-Tnum-1。si,d為d維空間中第i只狼與頭狼距離,si,d∈Dd。

(10)

式中:ω為距離因子常量。

當(dāng)狼群找到獵物,頭狼號(hào)令圍攻,運(yùn)動(dòng)步長(zhǎng)和位置更新計(jì)算方式[11]為

StepW(d)=|maxd-mind|/(2×S)

(11)

(12)

式中:si,d∈Dd,i=1,2,…,N-1,λ∈[-1,1]隨機(jī)值。

2.3 協(xié)同過濾推薦

通過狼群優(yōu)化的K-means算法進(jìn)行聚類后,可以獲得用戶對(duì)所有待推薦的資源或服務(wù)的評(píng)分,然后采用協(xié)同過濾算法進(jìn)行有效推薦。

設(shè)推薦的用戶集合為U={u1,u2,…,um},待推薦的資源集合為I={i1,i2,…,in},rm,n表示第m個(gè)用戶對(duì)第n個(gè)資源的評(píng)分,那么用戶a和b的相似關(guān)系[12]為

(13)

在協(xié)同過濾時(shí),除了可以對(duì)用戶之間的相似性進(jìn)行分析之外,最重要的是需要求解用戶對(duì)資源的評(píng)分,用戶j對(duì)資源k的評(píng)分方法為

(14)

根據(jù)資源評(píng)分分?jǐn)?shù),為用戶推薦評(píng)分高的資源,從而完成智能推薦。該算法的智能性體現(xiàn)在無需所有用戶對(duì)所有資源進(jìn)行評(píng)分,而是通過用戶訪問網(wǎng)絡(luò)的習(xí)慣數(shù)據(jù),采用狼群優(yōu)化的K-means聚類來預(yù)測(cè)用戶對(duì)資源的評(píng)分值。

2.4 聚類及推薦流程

首先,分析客戶端的智能推薦任務(wù)需求,然后搭建Spark平臺(tái),部署合適規(guī)模的分布式節(jié)點(diǎn),接著建立聚類運(yùn)算模型,并通過狼群算法對(duì)初始聚類中心點(diǎn)進(jìn)行優(yōu)化,通過聚類結(jié)果獲取用戶-屬性評(píng)分?jǐn)?shù)據(jù),最后采用協(xié)同過濾完成智能推薦。Spark平臺(tái)下聚類挖掘的智能推薦流程主要如圖2所示。

圖2 Spark平臺(tái)下智能推薦流程圖

3 實(shí)例仿真

為了驗(yàn)證Spark平臺(tái)下聚類挖掘的智能推薦性能,分別對(duì)公共數(shù)據(jù)集和自有數(shù)據(jù)集進(jìn)行仿真,其中公共數(shù)據(jù)集為Movie Lens數(shù)據(jù)集,自有數(shù)據(jù)集為某在線教育平臺(tái)。Movie Lens數(shù)據(jù)集作為推薦系統(tǒng)仿真的經(jīng)典數(shù)據(jù)集,能夠很好地驗(yàn)證聚類挖掘的推薦性能,而在線學(xué)習(xí)平臺(tái)因?yàn)橛脩袅勘姸嗪蛯W(xué)習(xí)資源數(shù)據(jù)量大,很容易獲得大規(guī)模數(shù)據(jù)樣本,充分驗(yàn)證Spark平臺(tái)的推薦優(yōu)勢(shì)。

Spark平臺(tái)共包含1個(gè)Master節(jié)點(diǎn)和9個(gè)Work節(jié)點(diǎn),所有節(jié)點(diǎn)具有相同的硬件性能。

3.1 Movie Lens數(shù)據(jù)集仿真

為了驗(yàn)證狼群優(yōu)化的K-means聚類算法在Movie Lens數(shù)據(jù)集的智能推薦性能,采用狼群優(yōu)化的K-means算法完成聚類,然后通過協(xié)同過濾完成影片推薦。

表1 Movie Lens實(shí)驗(yàn)數(shù)據(jù)集

3.1.1 不同聚類中心數(shù)的推薦性能

聚類中心個(gè)數(shù)K對(duì)影片評(píng)分矩陣影響敏感,從而影響影片協(xié)同過濾推薦的穩(wěn)定性,因此差異化設(shè)置K,驗(yàn)證推薦準(zhǔn)確率的RMSE值。

圖3表明RMSE值隨著K值的增加先減小后增大,當(dāng)分類類別較小時(shí),影片類別分類粒度大,因此推薦的影片與用戶實(shí)際評(píng)分值偏差大,Data1和Data2在K=16時(shí)獲得了最優(yōu)RMSE,而Data3在K=18時(shí)獲得了最優(yōu)RMSE值。當(dāng)繼續(xù)增加K值后,RMSE逐漸增大,推薦穩(wěn)定性變差。因此,選擇在后續(xù)針對(duì)Movie Lens數(shù)據(jù)集仿真時(shí),K取值范圍設(shè)置為[16,18]。

圖3 不同K值的推薦準(zhǔn)確率RMSE值

3.1.2 基于公共數(shù)據(jù)集的推薦性能

設(shè)置K=16,采用狼群優(yōu)化的K-means算法進(jìn)行聚類挖掘,并采用協(xié)同過濾推薦算法對(duì)Movie Lens數(shù)據(jù)集訓(xùn)練,訓(xùn)練時(shí)共有10個(gè)節(jié)點(diǎn)組成Spark平臺(tái)進(jìn)行計(jì)算。

表2 推薦性能(Movie Lens數(shù)據(jù)集)

推薦時(shí)間性能方面,容量的差別在推薦時(shí)間上表現(xiàn)不明顯,這主要是采取了Spark平臺(tái)的作用,對(duì)于10個(gè)節(jié)點(diǎn)來說,因3個(gè)樣本數(shù)據(jù)容量差異導(dǎo)致的推薦時(shí)間變化非常小。

3.2 在線學(xué)習(xí)平臺(tái)數(shù)據(jù)集仿真

為了進(jìn)一步驗(yàn)證本文算法和Spark平臺(tái)結(jié)合的智能推薦性能,采用在線學(xué)習(xí)平臺(tái)數(shù)據(jù)集進(jìn)行仿真。分別選擇了粵港澳大灣區(qū)某大型在線學(xué)習(xí)平臺(tái)1個(gè)月的用戶學(xué)習(xí)數(shù)據(jù),組建成4個(gè)不同容量的樣本:Data1(12.95MB),Data2(656.82MB),Data3(1.42GB),Data4(8.03GB)。

3.2.1 聚類結(jié)果可視化

將4種數(shù)據(jù)樣本分別進(jìn)行狼群優(yōu)化K-means聚類。根據(jù)用戶和資源的類別屬性獲得用戶-資源評(píng)分?jǐn)?shù)據(jù),差異化設(shè)置K值,取推薦準(zhǔn)確率最高K值作為聚類中心數(shù);為了直觀顯示聚類結(jié)果,對(duì)聚類結(jié)果進(jìn)行可視化,其中Data1的聚類結(jié)果如圖4所示。

圖4 Data1聚類結(jié)果可視化

狼群優(yōu)化的K-means聚類算法在三維空間內(nèi)將Data1數(shù)據(jù)集分為5類。根據(jù)分類結(jié)果,可以獲得樣本所有用戶和資源屬性的評(píng)分,然后再進(jìn)行協(xié)同過濾計(jì)算獲得推薦結(jié)果。

3.2.2 推薦性能仿真

差異化設(shè)置聚類中心數(shù),對(duì)不同K值下的推薦性能進(jìn)行仿真,取最優(yōu)K值完成5個(gè)樣本的狼群優(yōu)化K-means和協(xié)同過濾智能推薦。

從表3可以看出,推薦的準(zhǔn)確率保持在91%以上,準(zhǔn)確率受樣本容量的影響較小,而推薦時(shí)間隨著樣本容量在增加,雖然Data3和Data4樣本容量量級(jí)變大,推薦時(shí)間并未有快速增長(zhǎng),這主要是Spark平臺(tái)多節(jié)點(diǎn)運(yùn)算的原因。

表3 推薦性能(在線學(xué)習(xí)平臺(tái)數(shù)據(jù)集)

3.2.3 Spark平臺(tái)的加速性能仿真

為了驗(yàn)證Spark平臺(tái)對(duì)智能推薦速度的影響,求解Spark推薦相對(duì)于單機(jī)推薦的加速比:

(15)

Ta與Ts為單機(jī)和Spark多節(jié)點(diǎn)的各自推薦時(shí)間。

從表4可以看出,當(dāng)Worker節(jié)點(diǎn)數(shù)量增加,Spark加速效果明顯,樣本容量越大,Worker節(jié)點(diǎn)數(shù)對(duì)加速比影響越顯著。Data1的樣本容量為12.95 MB,Worker節(jié)點(diǎn)達(dá)到10時(shí),加密比只比單機(jī)增加了0.001,而當(dāng)樣本容量為8.03 GB時(shí),加速比相對(duì)于單機(jī)增加了42.907,因此Spark平臺(tái)提高了大容量樣本的推薦效率,特別適合大規(guī)模聚類挖掘及推薦。

表4 Spark加速性能

3.3 不同推薦算法性能仿真

為了繼續(xù)驗(yàn)證本文算法在智能推薦系統(tǒng)中的性能,分別從在線學(xué)習(xí)平臺(tái)的4個(gè)數(shù)據(jù)集中各抽取500個(gè)樣本組建成新的數(shù)據(jù)集Data5,將SVM算法[13]、深度神經(jīng)網(wǎng)絡(luò)(DNN)[14]、XGBoost算法[15]和本文算法分別進(jìn)行仿真。

如圖5所示,4種不同算法的推薦準(zhǔn)確率在初期時(shí)均隨著迭代次數(shù)的增加而不斷提升,然后趨于穩(wěn)定。推薦性能包括兩個(gè)方面:準(zhǔn)確率和收斂速度,可從這2個(gè)方面綜合分析。首先,在推薦準(zhǔn)確率方面,算法穩(wěn)定即收斂后,本文算法和XGBoost算法最優(yōu),均超過了0.9,而SVM算法最差,僅約為0.7;其次,在收斂速度方面,SVM表現(xiàn)最優(yōu)為190次,本文算法次之,約為230次,XGBoost算法最差。根據(jù)4種算法的綜合推薦性能對(duì)比來看,本文算法在準(zhǔn)確率和收斂速度2個(gè)方面均排名靠前,這說明其對(duì)在線學(xué)習(xí)樣本的綜合推薦性能最佳。

圖5 不同算法的推薦性能

4 結(jié)束語(yǔ)

本文采用狼群優(yōu)化的K-means算法完成聚類挖掘,并采用協(xié)同過濾算法完成智能推薦,推薦準(zhǔn)確率高;為了解決大規(guī)模數(shù)據(jù)的推薦問題,引入Spark平臺(tái)多節(jié)點(diǎn)共同完成聚類和推薦,提高了智能推薦效率。后續(xù)研究將進(jìn)一步優(yōu)化聚類參數(shù)及Spark節(jié)點(diǎn)的自適應(yīng)加入,以提高智能推薦準(zhǔn)確率,同時(shí)節(jié)省節(jié)點(diǎn)計(jì)算資源。