關 菲, 周 藝, 張 晗

(河北經貿大學 數學與統計學學院,河北 石家莊 050061)

0 引言

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

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

1 預備知識

1.1 Slope One算法

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

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

(1)

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

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

(2)

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

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

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

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

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

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

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

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

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

表1 MovieLens100k數據集基本信息

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

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

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

表2 MovieLens數據集上不同填充方法的均方根誤差

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

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

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

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

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

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

圖2 不同近鄰個數MAE值對比

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

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

3.1 基于中心聚集參數的改進K-means算法

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

定義1任意兩個數據點間距離的平均值為:

(3)

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

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

(4)

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

定義3點的聚集度定義:

(5)

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

(6)

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

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

(7)

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

定義6中心聚集參數定義為:

(8)

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

輸入：所有的數據集點x1,x2,…,xn

輸出：聚類結果

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

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

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

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

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

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

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

表4 UCI數據集

圖3 調整蘭德指數指標對比

圖4 互信息指標對比

圖5 Fowlkes-Mallows指標對比

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

3.2 基于中心聚集參數的改進K-means協同過濾推薦算法

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

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

圖6 經典K-means不同聚類個數下的MAE變化

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

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

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

圖7 不同近鄰個數下MAE變化

4 結論及展望

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