關(guān) 菲, 周 藝, 張 晗

(河北經(jīng)貿(mào)大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)學(xué)院,河北 石家莊 050061)

0 引言

大數(shù)據(jù)時代下互聯(lián)網(wǎng)的應(yīng)用使人們的生活更加便捷與智能化。但隨之而來的“信息過載”問題亟需解決，此時推薦系統(tǒng)應(yīng)運而生。協(xié)同過濾[1]作為個性化推薦系統(tǒng)[2]中應(yīng)用較為廣泛的一種算法，因經(jīng)常面臨數(shù)據(jù)稀疏性和算法擴展性問題，近年來備受關(guān)注。因此，協(xié)同過濾算法的優(yōu)化成為了國內(nèi)外學(xué)者的研究熱點。針對數(shù)據(jù)稀疏性問題，一些學(xué)者通過降維的方法來緩解稀疏性，比如文獻(xiàn)[3]提出了基于矩陣分解的迭代最小二乘加權(quán)正則化協(xié)同過濾算法，對傳統(tǒng)矩陣分解模型加入正則化約束以防止過擬合；文獻(xiàn)[4]提出了基于矩陣分解和隨機森林的多準(zhǔn)則推薦算法；文獻(xiàn)[5]利用自適應(yīng)神經(jīng)模糊推理系統(tǒng)，結(jié)合減法聚類和高階奇異值分解提出了一種新的多準(zhǔn)則協(xié)同過濾模型。還有一些學(xué)者通過矩陣填充來緩解數(shù)據(jù)稀疏性，比如文獻(xiàn)[6]考慮了用戶對項目的興趣偏好，提出了一種結(jié)合用戶興趣偏好的矩陣填充方法；文獻(xiàn)[7]通過非負(fù)約束下的低秩矩陣填充模型對矩陣缺失項取值進(jìn)行預(yù)測。還有一些學(xué)者通過融合一些其他信息來緩解數(shù)據(jù)稀疏性帶來的問題，比如文獻(xiàn)[8～10]分別在推薦過程中融合了標(biāo)簽信息和時間效應(yīng)、物品屬性和用戶間的社交聯(lián)系、上下文對用戶的影響以及項目的相關(guān)性等，均提高了推薦系統(tǒng)的準(zhǔn)確性。針對算法擴展性問題，文獻(xiàn)[11～13]分別采用了K-means聚類、二分K-means聚類、模糊K-means聚類先對物品進(jìn)行聚類再推薦的方法，進(jìn)而提高了推薦的精度和可擴展性；文獻(xiàn)[14]提出了一種基于聚類矩陣近似的協(xié)同過濾推薦算法，通過對稠密矩陣塊進(jìn)行奇異值分解以及對各個稠密矩陣塊奇異向量進(jìn)行Schmidt正交來對原始評分矩陣進(jìn)行重新近似；文獻(xiàn)[15]將雙聚類與協(xié)同過濾相結(jié)合，將雙聚類的局部相似度和全局相似度結(jié)合在一起，構(gòu)造了一個新的候選項目排名得分；分析上述文獻(xiàn)可以看出：學(xué)者們大多采用降維、矩陣填充和融合其他信息的方法來緩解數(shù)據(jù)稀疏性。對于擴展性問題，學(xué)者們經(jīng)常采用K-means聚類方法，然而K-means聚類存在一定的不足之處，可能會出現(xiàn)因聚類的用戶簇不合理，從而導(dǎo)致推薦效果較差的現(xiàn)象?；诖耍疚膶臄?shù)據(jù)稀疏性和擴展性兩個角度對協(xié)同過濾算法進(jìn)行優(yōu)化。

本文結(jié)構(gòu)安排如下：第 1 部分介紹了本文所需用到的Slope One算法和基于K-means聚類的協(xié)同過濾推薦算法。第2部分提出了一種基于Slope One矩陣填充的協(xié)同過濾推薦優(yōu)化算法。第3部分提出了一種基于中心聚集參數(shù)的改進(jìn)K-means算法，并將該算法應(yīng)用到協(xié)同過濾推薦中。第4部分，結(jié)論與研究展望，總結(jié)了本文算法的有效性并討論了本文下一步的研究方向。

1 預(yù)備知識

1.1 Slope One算法

2005年，Daniel Lemire教授提出了Slope One算法[16]。其基本原理是計算不同物品間的一個評分差，用評分差預(yù)測最終用戶對物品的評分。若將整個評分?jǐn)?shù)據(jù)標(biāo)記為R，主要分以下兩步：

①在兩個物品同時被評分的前提下，將兩物品i、j的評分差取均值，記做評分偏差：

(1)

其中，rui和ruj表示用戶u對項目i、j的評分，N(i)是對物品i評過分的用戶，|N(i)∩N(j)|是對物品i、j都評過分的用戶數(shù)。

②根據(jù)用戶歷史評分和由(1)得出的評分偏差，預(yù)測用戶對沒有做出過評分的物品的分值。

(2)

1.2 基于K-means聚類的協(xié)同過濾推薦算法

設(shè)X={xi|xi∈Rp,i=1,2,…,n}為原數(shù)據(jù)集，每個數(shù)據(jù)由用戶、項目、評分3部分組成。設(shè)目標(biāo)用戶為u，用戶集合是U={u1,u2,…,um}，K-means聚類得出的用戶集合可以表示為U={C1,C2,…,Ck}，k為聚類個數(shù)。算法步驟[17]如下：

(1)在X中隨機選出個樣本作為初始簇心Mi(i=1,2,…,k)；

(2)用初始簇心Mi(i=1,2,…,k)對用戶-項目評分矩陣Rm×n執(zhí)行經(jīng)典K-means算法，得到k個類；

(3)使用歐氏距離計算目標(biāo)用戶u與k個簇心間的距離，根據(jù)最小距離，找到u所屬的類別；

(4)在u所屬類中，計算u與其他用戶的相似性，獲取u的最近鄰居集Nuj(j=1,2,…,m)；

(5)得到最近鄰居集后，預(yù)測求得想要推薦給u的項目的評分，由高到低排序后，把前N個項目推薦給u。

2 基于Slope One的協(xié)同過濾推薦優(yōu)化算法

為有效緩解數(shù)據(jù)稀疏性，本節(jié)中我們選取MovieLens 100k數(shù)據(jù)集，數(shù)據(jù)集詳情如表1。

表1 MovieLens100k數(shù)據(jù)集基本信息

(實驗環(huán)境為Windows 8系統(tǒng)；硬件條件為CPU2.3GHZ，4G內(nèi)存，100G；使用軟件Python 3.7版本)我們選取9種不同方法進(jìn)行稀疏矩陣的填充，并選用均方根誤差(RMSE)來判定有效性。

參照文獻(xiàn)[18]，我們用全局均值法、用戶平均法、物品平均法、用戶活躍度&物品不平均、用戶活躍度&物品平均、用戶不平均&物品流行度、用戶平均&物品流行度、用戶活躍度&物品流行度、Slope One這9種不同方法進(jìn)行填充，其均方根誤差見表2。

從表2的結(jié)果可以看出，當(dāng)使用Slope One方法進(jìn)行填充時，其RMSE是最小的，說明使用該方法填充時誤差較小。下面我們將采用Slope One方法對MovieLens 100k版本數(shù)據(jù)集進(jìn)行填充，結(jié)果見表3。

表2 MovieLens數(shù)據(jù)集上不同填充方法的均方根誤差

由表3可知，進(jìn)行了矩陣填充后，數(shù)據(jù)集的稀疏度變?yōu)?.37%，說明運用Slope One填充的效果明顯。我們使用填充后數(shù)據(jù)設(shè)計了兩組對比實驗，以驗證有效性：

實驗1確定最佳聚類個數(shù)。在這一階段的實驗中，分別利用由Slope One填充前和填充后的數(shù)據(jù)，得到兩個最佳K-means聚類個數(shù)。在確定過程中，我們選取平均絕對誤差(MAE)作為測量標(biāo)準(zhǔn)，當(dāng)聚類個數(shù)以2為間隔，由2增加到20時，根據(jù)MAE的大小來確定出最佳聚類個數(shù)，為了保證推薦時選取的近鄰數(shù)相同，將其固定為25，以此增強MAE值的可靠性。圖1中縱坐標(biāo)代表MAE值，橫坐標(biāo)是聚類個數(shù)。

表3 用Slope One填充后MovieLens100k信息表

實驗結(jié)果表明：圖1中隨著聚類個數(shù)從2增加到20，在進(jìn)行SlopeOne填充和未填充時，K-means不同聚類個數(shù)的MAE值都呈現(xiàn)出先下降后上升的趨勢，且波動幅度較小。兩種情況的MAE最低值都出現(xiàn)在k=8，因此最佳的聚類個數(shù)都是8。

圖1 K-means算法不同聚類個數(shù)的MAE變化對比圖

實驗2推薦算法精度對比。我們采用三種算法來做對比試驗，分別是：基于SlopeOne填充后的K-means協(xié)同過濾推薦、經(jīng)典K-means協(xié)同過濾推薦和傳統(tǒng)的協(xié)同過濾推薦算法。圖2中縱軸是MAE值，橫軸是近鄰個數(shù)，以5為間隔從5增加到50，結(jié)果如圖2所示。

圖2 不同近鄰個數(shù)MAE值對比

由圖2可以看出，三種協(xié)同過濾推薦算法的MAE值都隨著最近鄰個數(shù)的增加呈現(xiàn)出緩慢下降的趨勢，且在鄰居個數(shù)變化相同時，用Slope One填充后的K-means聚類協(xié)同過濾算法的MAE值最小。因此，在推薦之前，先對評分矩陣進(jìn)行填充，這樣能增加一些用戶評分?jǐn)?shù)據(jù)，以便在推薦過程中發(fā)掘出更多的可供推薦的項目，填充完畢的矩陣再對用戶進(jìn)行K-means聚類，這樣是為了能縮小近鄰尋找范圍，類中的所有用戶相比類外的用戶與目標(biāo)用戶具有更高的相似程度，在后續(xù)的近鄰匹配選取時也就更便利。

3 基于改進(jìn)K-means的協(xié)同過濾推薦優(yōu)化算法

3.1 基于中心聚集參數(shù)的改進(jìn)K-means算法

由于第2節(jié)中用到的傳統(tǒng)K-means聚類算法的初始中心和聚類個數(shù)k均是隨機產(chǎn)生的，其合理性會影響聚類結(jié)果。因此，本節(jié)中我們參考文獻(xiàn)[19]，首先給出如下定義：

定義1任意兩個數(shù)據(jù)點間距離的平均值為:

(3)

其中，d(xi,xj)是任意兩點之間的歐式距離，n表示數(shù)據(jù)點的個數(shù)。

定義2定義鄰域半徑R為:

(4)

releR是一個用來調(diào)節(jié)的系數(shù)，releR取0.13時，聚類效果最好。

定義3點的聚集度定義:

(5)

定義4簇類平均距離定義為:

(6)

簇類平均距離Gavgd(xi)衡量的是元素密集度，數(shù)值越小，說明在目標(biāo)用戶xi所在類中，數(shù)據(jù)點之間越緊湊。

定義5聚集度距離G(xi)定義為:

(7)

G(xi)是通過比較聚集度Dp(xi)來確定的，用它來衡量不同簇之間的差異性。在所有的點中，當(dāng)xi的聚集度最大時，G(xi)是xi與剩余所有點之間的最大距離，反之則為xi與剩余所有點之間的最小距離。

定義6中心聚集參數(shù)定義為:

(8)

基于以上概念，我們給出基于中心聚集參數(shù)的改進(jìn)K-means算法流程：

輸入：所有的數(shù)據(jù)集點x1,x2,…,xn

輸出：聚類結(jié)果

(1)計算出每個點的中心聚集參數(shù)ω(xi)；

(2)選出使得ω(xi)最大的點xi，由它做為第一個初始聚類中心，計算出xi與剩余點間的距離，將得到的距離值與鄰域半徑R作比較，若距離小于R則說明可以與xi劃為一類，因此將從數(shù)據(jù)點中除去這些點，若距離大于R，則說明與xi的距離過遠(yuǎn)，不適宜與xi歸為一類，因此將這些點保留下來，進(jìn)行下一步；

(3)在第(2)步中保留下的點里再選出ω(xi)最大的點，作為第2個聚類中心，再次操作步驟(2)；

(4) 一直重復(fù)操作步驟(3)，當(dāng)數(shù)據(jù)集中的點x1，x2，…，xn全部去除為止；

(5)輸出k個最優(yōu)初始中心Mi(i=1,2,…,k);

(6)利用初始簇心Mi，對Rm×n執(zhí)行K-means算法，將數(shù)據(jù)集分成k類；循環(huán)執(zhí)行K-means算法，直至其準(zhǔn)則函數(shù)收斂，得到最終聚類結(jié)果；

為驗證上述算法的有效性，我們選取以下UCI數(shù)據(jù)集進(jìn)行驗證(見表4)，同時選取的評價標(biāo)準(zhǔn)有：調(diào)整后的蘭德指數(shù)(RI)、互信息(MI)以及Fowlkes-Mallows指標(biāo)[19]。實驗結(jié)果如圖3～圖5：

表4 UCI數(shù)據(jù)集

圖3 調(diào)整蘭德指數(shù)指標(biāo)對比

圖4 互信息指標(biāo)對比

圖5 Fowlkes-Mallows指標(biāo)對比

由圖3、圖4和圖5，我們可以看出基于中心聚集參數(shù)的改進(jìn)K-means算法得到的相關(guān)數(shù)值均比經(jīng)典K-means聚類算法值要高，并且在Wine和Soybean兩個數(shù)據(jù)集上的表現(xiàn)更為明顯。因此通過此實驗表明，基于中心聚集參數(shù)的改進(jìn)K-means算法具有較好的聚類效果。

3.2 基于中心聚集參數(shù)的改進(jìn)K-means協(xié)同過濾推薦算法

本節(jié)中，我們把3.1節(jié)中基于中心聚集參數(shù)的改進(jìn)K-means算法用于協(xié)同過濾推薦過程中，為驗證改進(jìn)后的算法在推薦上的效果，為方便起見，我們從MovieLens100k數(shù)據(jù)中隨機選取了189名用戶的評分?jǐn)?shù)據(jù)，并按2:8分為測試集和訓(xùn)練集，設(shè)計了如下兩組對比實驗：

實驗1確定最佳聚類個數(shù)。在這一階段的實驗中，需要得到兩個最佳聚類個數(shù)。首先執(zhí)行基于中心聚集參數(shù)的改進(jìn)K-means算法，得出最佳的聚類個數(shù)是19；其次需要判定經(jīng)典K-means算法的最佳聚類個數(shù)，選取的評價指標(biāo)是平均絕對誤差(MAE)，當(dāng)聚類個數(shù)以2為間隔，由2增加到20時，根據(jù)MAE的大小來確定出最佳聚類個數(shù)，為了保證推薦時選取的近鄰數(shù)相同，將其固定為25，以此增強MAE值的可靠性。

圖6 經(jīng)典K-means不同聚類個數(shù)下的MAE變化

圖6表明：隨著聚類個數(shù)的增加，MAE值呈先下降后上升趨勢，在聚類數(shù)k=16時最低。因此對經(jīng)典K-means算法而言，最佳聚類個數(shù)是16，從而保證獲取有效的分組，提高在近鄰選擇時的便利性和可靠性，取得較好的推薦效果。

實驗2推薦算法精度對比。我們采用三種算法來做對比試驗，分別是：基于中心聚集參數(shù)的改進(jìn)K-means協(xié)同過濾推薦算法、基于K-means的協(xié)同過濾算法與傳統(tǒng)的協(xié)同過濾推薦算法。下圖中縱軸是MAE值，橫軸是近鄰個數(shù)，以5為間隔從5增加到50。

由圖7可以看出，進(jìn)行對比的三種協(xié)同過濾推薦算法它們的MAE值都呈現(xiàn)先下降后上升的趨勢，整體上隨著最近鄰個數(shù)的增加而降低，且在同樣的鄰居個數(shù)變化的前提下，基于中心聚集參數(shù)改進(jìn)K-means協(xié)同過濾推薦算法的MAE值最低。MAE值越低表明推薦誤差越小，所以當(dāng)目標(biāo)用戶的近鄰數(shù)不斷增加時，推薦準(zhǔn)確度也隨之提高。因此，基于中心聚集參數(shù)的改進(jìn)K-means協(xié)同過濾推薦算法的推薦效果較好。

圖7 不同近鄰個數(shù)下MAE變化

4 結(jié)論及展望

本文主要從兩個角度對個性化推薦系統(tǒng)中的協(xié)同過濾推薦算法進(jìn)行了優(yōu)化。首先，基于Slope One算法對缺失數(shù)據(jù)進(jìn)行填充，提出了基于Slope One的協(xié)同過濾推薦優(yōu)化算法。其次，提出了一種基于中心聚集參數(shù)的改進(jìn)K-means優(yōu)化算法，并將該算法用于協(xié)同過濾推薦中。為驗證本文提出算法的有效性，結(jié)合MovieLens數(shù)據(jù)集設(shè)計了相應(yīng)的對比實驗，結(jié)果表明：本文所提方法推薦精度均得到顯著提高，數(shù)據(jù)稀疏性和擴展性問題得到了一定程度的改善。但本文仍有一定不足之處，比如第3節(jié)中因用Slope One填充后的矩陣過于龐大，未能將Slope One填充與基于中心聚集參數(shù)的協(xié)同過濾推薦算法相結(jié)合，這將是本文后續(xù)工作中需要解決的重要問題。