張志強(qiáng),李 改

1(順德職業(yè)技術(shù)學(xué)院 電子與信息工程學(xué)院,順德 528300)

2(華中科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,武漢 430074)

3(中山大學(xué) 信息科學(xué)與技術(shù)學(xué)院,廣州 510006)

當(dāng)今社會,基于互聯(lián)網(wǎng)技術(shù)的電子商務(wù)不斷普及,大數(shù)據(jù)分析和大數(shù)據(jù)挖掘已成為迫切要解決的問題.推薦系統(tǒng)是指根據(jù)用戶的興趣特點(diǎn)和購買行為,向用戶推薦用戶感興趣的信息和商品的系統(tǒng).其中協(xié)同過濾推薦 (collaborative filtering recommendation)是推薦系統(tǒng)中應(yīng)用最早和最為成功的技術(shù)之一,它一般采用最近鄰技術(shù),利用用戶的歷史喜好信息計(jì)算用戶之間的距離,然后 利用目標(biāo)用戶的最近鄰居用戶對商品評價(jià)的加權(quán)評價(jià)值來預(yù)測目標(biāo)用戶對特定商品的喜好程度,系統(tǒng)從而根據(jù)這一喜好程度來對目標(biāo)用戶進(jìn)行推薦.協(xié)同過濾最大優(yōu) 點(diǎn)是對推薦對象沒有特殊的要求,能處理非結(jié)構(gòu)化的復(fù)雜對象,如音樂、電影等媒體數(shù)據(jù)[1].其中的潛在因素模型 (latent factor models)的核心思想是: 通過分析歷史數(shù)據(jù)來預(yù)測事物的發(fā)展趨勢,矩陣分解算法(matrix factorization)是其中最為成功的算法之一[2].但隨著互聯(lián)網(wǎng)數(shù)據(jù)的不斷擴(kuò)大,應(yīng)用傳統(tǒng)的矩陣分解算法構(gòu)造大數(shù)據(jù)潛在因素模型,算法性能會大大下降,難以實(shí)現(xiàn)有效的協(xié)同過濾,其關(guān)鍵問題體現(xiàn)在數(shù)據(jù)稀疏性和算法可擴(kuò)展性的改進(jìn)上.

針對上述問題,國內(nèi)外學(xué)者專家們提出了一些改進(jìn)想法: Pilaszy I最先提出基于ALS的協(xié)同過濾算法,相對傳統(tǒng)算法而言,能有效提高過濾質(zhì)量和推薦速度,但該算法只考慮用戶的相似性[3]; 李改等對前者進(jìn)行改進(jìn),提出了ALS-WR 協(xié)同過濾算法,該算法考濾到可擴(kuò)展性方面,但需要專門設(shè)計(jì)迭代式算法[4]; 王輝等把用戶聚類思想引入到協(xié)同過濾算法中,改進(jìn)了傳統(tǒng)算法的數(shù)據(jù)稀疏性和可擴(kuò)展性,但精確度較低[5].

本文提出一種基于BC-AW的協(xié)同過濾推薦算法,在傳統(tǒng)算法的基礎(chǔ)上,引入聯(lián)合聚類BC(BlockClust)和正則化迭代最小二乘法(Alternating least squares with Weighted regularization,AW).首先分解原始評分矩陣的用戶項(xiàng)目雙維度,然后使用聯(lián)合聚類計(jì)算出多個同類評分塊的子矩陣,最后使用正則化迭代最小二乘法預(yù)測各個子矩陣的未知評分,從而計(jì)算出推薦結(jié)果.使用聯(lián)合聚類所求得的子矩陣遠(yuǎn)比初此矩陣規(guī)模小,可以大大減少過濾推薦的計(jì)算量.通過與BaseMF算法、RSTE算法、TidaTrust算法、MoleTrust算法進(jìn)行對比實(shí)驗(yàn),分析結(jié)果表明,本文算法可以有效緩解傳統(tǒng)算法并行化、可擴(kuò)展性差的問題.

1 AW 算法

設(shè)定矩陣代表個用戶、個對象的評分矩陣、矩陣代表用戶特征矩陣、矩陣代表推薦對象特征矩陣代表中的某個元素,代表的第i行代表的第列代表的轉(zhuǎn)置代表的逆.傳算法一般使用SVD算法來分解[6],但本文算法是通過計(jì)算低秩矩陣來逼近,使得(其中代表的特征數(shù)),一般狀態(tài)下代表的秩

Step1: 我們通過最小化Frobenius的損失函數(shù)來算出一個低秩矩陣,令的得盡量接近,如公式(1)所示:

上述公式(1)中為低秩逼近中一般平方誤差項(xiàng).

Step 2: 求解的最優(yōu)化問題于是改寫公式(1)如下:

上述式(2)會產(chǎn)生過于擬合的問題,因此需要通過正則化項(xiàng)來解決這個問題,則改寫如下:

Step3: 對上面公式 (3),設(shè)定不變,對求導(dǎo)求解如公式 (4)所示:

公式(4)中,為用戶所評過影片的向量矩陣,由評分組組成,為用戶i所評過影片的特征矩陣,由特征向量組成,為用戶i所評過的影片數(shù),階的單位矩陣.

Step4: 上述對公式 (4)中,設(shè)定不變,可以通過公式(5)求解

上述公式(5)中為用戶i所評過影片的評分所形成的向量,為用戶i評過影片的特征矩陣,它由用戶群中的特征向量組成,為用戶i評過影片的用戶數(shù)量.

2 BC 算法

BC算法能夠?qū)⒂枚鄠€較小且高相似度的評分矩陣來替代原始數(shù)據(jù)[7].通過掃描該矩陣中的評分,使用聚類方法計(jì)算行和列,計(jì)算一次后,重新評估每個子矩陣中用戶、項(xiàng)目的概率,如此類推,直到產(chǎn)生收斂為止[8].然后將評分匹配到最大概率的子矩陣中.其算法思想如下:

首先掃描評分矩陣,通過計(jì)算各評分的所屬概率來判斷該評分是否屬于某個子矩陣,其參數(shù)包括: 用戶—項(xiàng)目屬于某子矩陣的概率該評分值屬于某子矩陣中的概率其算法公式如下(其中

以上公式中,表示當(dāng)前用戶,表示當(dāng)前項(xiàng)目,表示評分值表示1到5的整數(shù),表示當(dāng)前聚類表示當(dāng)前累加聚類表示對評了分的所有用戶集合,表示已評過分的所有項(xiàng)目集合.BC算法把原矩陣分為個具有高密度、高相似度的子矩因此,該算法具有一定的降維作用[9].

3 BC-AW 算法

以下通過聯(lián)合聚類和AW協(xié)同過濾兩階段來對評分矩陣的未知項(xiàng)進(jìn)行預(yù)測.

1) 聯(lián)合聚類

輸入: 子矩陣個數(shù),用戶—項(xiàng)目評分矩陣.

輸出: 子矩陣數(shù).

Step1:表示用戶量,表示項(xiàng)目數(shù)表示評分屬于聚類的概率,分別初始化使得

Step2: 應(yīng)用公式(7)計(jì)算用戶屬于聚類的概率應(yīng)用公式(8)計(jì)算用戶屬于聚類的概率應(yīng)用公式(9)算出分值概率應(yīng)用公式(6)算出

Step3: 最后選擇概率的最大值作為該評分的子矩陣.

Step4: 跳回步驟 2,直到出現(xiàn)收斂,結(jié)束循環(huán).

2) AW 協(xié)同過濾

首先用偏差小于等于的高斯隨機(jī)數(shù)初始化矩陣,接著分別用公式(4)和公式(5)更新和,重復(fù)進(jìn)行多次迭代,直到得出的RMSE值出現(xiàn)收斂為止,結(jié)束迭代.

輸出: 用戶評分矩陣,特征個數(shù).

輸出:的逼近矩陣.

Step1: 用偏差小于等于0.01的高斯隨機(jī)數(shù)初始化;

Step2: 分別用公式(4)和公式(5)更新和;

Step3: 重復(fù)迭代公式 (4)、公式 (5),判斷得出的RMSE值是否收斂,如果是,則迭代結(jié)束;

Step4: 令返回矩陣

下面我們分析該算法的時間復(fù)雜度: 設(shè)為在矩陣?yán)锏脑u分點(diǎn)個數(shù),一般情況下,矩陣稀疏).為特征個數(shù),為該算法的迭代數(shù); 設(shè)為用戶數(shù); 設(shè)為對象推薦數(shù).變量每次更新的時間為變量每次更新的時間為如此類推,在迭代次后的時間則為由此可見,在以及恒定的情況下,)取決于也就是說,算法的總時間復(fù)雜度與成正比,可證該算法具有一定的可擴(kuò)展性.在 AW 協(xié)同過濾中,Step 2 是最關(guān)鍵的步驟,在這個步聚里,每次應(yīng)用公式(4)和公式(5)只能更新和中 的一行值,效率較低.因此可以先將和分解為個列相等的子矩陣,然后,應(yīng)用公式(4)和公式(5)對每個子矩陣并行更新,這樣可以大大提高運(yùn)算效率.

綜上所述,本文基于矩陣分解的BC-AW協(xié)同過濾推薦算法改進(jìn)傳統(tǒng)算法的串行運(yùn)算方式,實(shí)現(xiàn)并行運(yùn)算,可以有效地解決傳統(tǒng)算法中存在的可擴(kuò)展性差問題.

4 實(shí)驗(yàn)分析

4.1 數(shù)據(jù)準(zhǔn)備

本實(shí)驗(yàn)?zāi)康氖峭ㄟ^分析比較本文算法和傳統(tǒng)算法的性能,硬件方面選用基于云計(jì)算的分布式硬件實(shí)驗(yàn)平臺,該平臺由20臺電腦組成20個運(yùn)算節(jié)點(diǎn),每個節(jié)點(diǎn)配有 4.0 Hz 的 Intel處理器和 32 G 的內(nèi)存,Linux 操作系統(tǒng).實(shí)驗(yàn)數(shù)據(jù)來自美國Minnesota大學(xué)GroupLens項(xiàng)目組的MovieLens數(shù)據(jù)集.MovieLens數(shù)據(jù)集是GroupLens項(xiàng)目組開發(fā)的一個互聯(lián)網(wǎng)研究型推薦系統(tǒng)數(shù)據(jù)集.MovieLens數(shù)據(jù)集中含有943個用戶對1682部電影的100 000條評分?jǐn)?shù)據(jù),平均每個用戶評分的電影大于等于20部[10].

4.2 評價(jià)指標(biāo)

本次實(shí)驗(yàn)采用均方根誤差RMSE和評分覆蓋率(Rating Coverage)作為算法推薦質(zhì)量的評價(jià)指標(biāo).

其中代表用戶的實(shí)際評分代表用戶對影片的預(yù)測評分,代表影片的評分?jǐn)?shù).RMSE的值越小表示算法的精度越高.Rating Coverage 是指在測試集中,推薦系統(tǒng)可預(yù)測的評分?jǐn)?shù)量占總評分的百分比[11].

4.3 實(shí)驗(yàn)結(jié)果及分析

本文算法分別與BaseMF (基于矩陣分解算法)[12];RSTE (概率矩陣分解算法)[13]; TidaTrust (基于 TidaTrust模型推薦算法)[14]; MoleTrust (基于 MoleTrust模型推薦算法)[15]這4種推薦方法通過分析RMSE和的結(jié)果值進(jìn)行分析比較.實(shí)驗(yàn)開始,首先隨機(jī)選取兩組訓(xùn)練集GROUP1和GROUP2: GROUP1為80%的Epinions數(shù)據(jù)集,GROUP1為90%的Epinions數(shù)據(jù)集.然后分別把本文算法、BaseMF 算法、RSTE算法、TidaTrust算法、MoleTrust算法所建立的模型應(yīng)用到訓(xùn)練集上進(jìn)行學(xué)習(xí),指定為潛在維度為實(shí)驗(yàn)基礎(chǔ)反復(fù)實(shí)驗(yàn)5次,求平均值作為最終實(shí)驗(yàn)結(jié)果.圖1為這5種算法得出的RMSE值比較圖.

圖1 5 種算法的 RMSE 值比較圖

從上圖可以看出,針對RMSE值,當(dāng)訓(xùn)練集為80%時,本文算法比BaseMF算法降低了22%,比RSTE算法降低了11%,比TidaTrust算法降低了8%,比 MoleTrust 算法降低了 7%; 當(dāng)訓(xùn)練集為 90%,本文算法比BaseMF算法降低了21%,比RSTE算法降低了 10%,比 TidaTrust算法降低了 7%,比 MoleTrust算法降低了7%; 由此可知,本文算法的誤差值明顯低于傳統(tǒng)的4種推薦算法.

圖2(a)、圖2(b)分別表示本文算法在GROUP1、GROUP2這兩組訓(xùn)練集中,RMSE在不同值下的變化情況.值越大,RMSE值越小,證明推薦精度越高.當(dāng)時,RMSE減小的幅度最大,迭代時間的增幅最小; 當(dāng)時,RMSE的變化幅度趨于 0.從而得出當(dāng)時,算法的推薦性能最佳.

圖2 RMSE 隨參數(shù)的變化曲線

下面分析5種算法的我們知道直接影響用戶對影片的可選擇范圍越高,用戶對影片的可選擇范圍越廣,從而用戶滿意度越高.采用GROUP1數(shù)據(jù)集(即80%的訓(xùn)練集),實(shí)驗(yàn)結(jié)果如表1所示.

表1 5 種算法的 COVR

分析表1可以看出,當(dāng)訓(xùn)練集為80%時,本文算法的比BaseMF算法提高了68.52%,比RSTE算法提高了38.09%,比TidaTrust算法提高了4.84%,比 MoleTrust算法提高了 6.58%.由此可見,本文算法比傳統(tǒng)4種算法具有更廣的覆蓋范圍.

4 結(jié)論與展望

本文針對現(xiàn)有協(xié)同過濾算法中普遍存在的數(shù)據(jù)稀疏、可擴(kuò)展性低這兩個核心問題,提出BC-AW(基于聯(lián)合聚類和迭代最小二乘法)兩階段協(xié)同過濾算法.首先由該算法通過對原評分矩陣進(jìn)行用戶—項(xiàng)目雙維度聯(lián)合聚類后得到的若干個子矩陣(這些子矩陣均為模式相同的評分塊),其規(guī)模比原矩陣小得多,因此可以有效減少預(yù)測工作量; 再者,采用正則化迭代最小二乘法預(yù)測子矩陣的未知評分可以優(yōu)化推薦效率.該算法在模擬大數(shù)據(jù)實(shí)驗(yàn)中(美國Minnesota大學(xué)GroupLens項(xiàng)目組的MovieLens數(shù)據(jù)集),通過與幾個經(jīng)典的協(xié)同過濾算法(BaseMF算法、RSTE算法、TidaTrust、MoleTrust算法)作比較.實(shí)驗(yàn)結(jié)果表明,本文算法能有效改進(jìn)推薦系統(tǒng)的稀疏性、可擴(kuò)展性問題,系統(tǒng)預(yù)測評分與用戶實(shí)際評分接近,并能為用戶提供良好的使用體驗(yàn).

參考文獻(xiàn)

1Shuo LX,Chai BF,Zhang XD.Collaborative filtering algorithm based on improved nearest neighbors.Computer Engineering and Applications,2015,51(5): 137–141.

2Zhang HJ.The research and application of distributed matrix factorization algorithm in recommend system.Bulletin of Science and Technology,2013,29(12): 151–153.

3Wang QM,Miao Y,He M,et al.Parallelized research on collaborative filtering algorithm based on matrix factorization.Computer Technology and Development,2015,25(2): 55–59.

4Zhu X,Song AB,Dong F,et al.A collaborative filtering recommendation mechanism for cloud computing.Journal of Computer Research and Development,2014,51(10):2255–2269.

5Bi XR.Collaboration filtering recommendation algorithm of sub-similarity integration between items.Computer Systems& Applications,2015,24(1): 147–150.

6Wang L,Fu XF,Wang XM.Hybrid dynamic collaborative filtering algorithm based on big data sets.Journal of Guangdong University of Technology,2014,31(3): 44–48.

7Chen W,Shi QL.An adaptive algorithm for collaborative filtering recommendation.Journal of Xianyang Normal University,2014,29(6): 47–49.

8Li G,Li L.One-class collaborative filtering based on matrix factorization.Application Research of Computers,2012,29(5): 1662–1665.

9Ke LW,Wang J.Collaborative filtering recommendation based on user feature transfer.Computer Engineering,2015,41(1): 37–43.

10Yi ZA,Mu CM.Collaborative filtering algorithm based on subtractive clustering and genetic fuzzy.Computer & Digital Engineering,2014,42(8): 1363–1367.

11Xu W,Duan F.Combining clustering and collaborative filtering for implicit recommender system.Computer Engineering and Design,2014,35(12): 4181–4185.

12Liu L.A collaborative filtering recommender algorithm based on iterative kernel method.Information Technology &Informatization,2014,(12): 76–81.

13Zha J,Li ZB,Xu GQ.An optimised collaborative filtering algorithm based on combined similarity.Computer Applications and Software,2014,31(12): 323–328.

14Wu HC,Wang XJ,Cheng Y,et al.Advanced recommendation based on collaborative filtering and partition clustering.Journal of Computer Research and Development,2011,48(S3): 205–212.

15Luo Q,Miao XJ,Wei Q.Further research on collaborative filtering algorithm for sparse data.Computer Science,2014,41(6): 264–268.