動態k近鄰輔助多權值Slope One算法

馬 浩，黃 俊，孔 麟，鄭小楠，郭小煥

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

隨著互聯網和信息技術的快速發展，信息過載[1]問題也愈來愈突出。如何在信息海洋中快速發掘用戶的興趣，并向其推薦感興趣的信息，已成為當前的研究熱點。

Daniel Lemire提出了Slope One算法(SO)。該算法簡單、高效，在協同過濾算法中得到廣泛的應用和發展。但隨著數據量的增加，其數據稀疏性、準確性等問題[2]也凸現出來。Slope One算法在進行平均評分偏差計算時，考慮所有共同評分用戶的歷史評分數據，其中包含大量與目標用戶相似度極低的用戶群體，難免會引入干擾數據，導致評分預測結果不夠精確[3]。因此，部分學者[4]采用k近鄰的方法給目標用戶選擇近鄰用戶集合。但k值不具有特殊性，無法適應不同的預測場景、人群及物品，使得推薦誤差很大。所以，有學者[5,6]提出使用不確定鄰居來優化Slope One算法。在傳統的Slope One算法當中運用最為廣泛的是Daniel Lenmire提出的Weighted Slope One算法(WSO)[7]，考慮到共同評分用戶數量的影響，將其作為權重，使得推薦的準確性在一定程度上得到改善。在此基礎上，部分學者[8,9]將用戶相似度和項目相似度添加為原始公式的權重因子進行改進，一定程度上提高了推薦精度。倪建成等[10]通過引入時間權重，來改善傳統Slope One算法數據的稀疏性和實時性差等問題。以上改進大多是針對單一方面進行考慮，往往取得的效果不是很理想。針對以上問題，本文綜合多方面考慮，提出一種動態k近鄰輔助多權值Slope One算法(dynamick-nearest neighbor-assisted multi-weight Slope One，KTWSO)。

1 相關研究

1.1 傳統Slope One算法

傳統Slope One算法是一種基于項目的協同過濾算法，其核心思想是利用一元線性模型f(x)=x+b對評分進行線性回歸預測。詳細定義請參見文獻[11]。

Slope One算法基本原理如圖1所示。要對用戶B的項目J進行評分預測，首先找出用戶B的其它評分項目，如項目I。然后找出對項目I和項目J都做出評分的用戶集合，如用戶A，并計算項目I與項目J之間的平均評分偏差。最后，將用戶B對項目I的評分與項目I和項目J之間的平均評分偏差進行計算，得出預測評分。

圖1 Slope One算法基本原理

綜上，Slope One算法評分預測推薦分為3步：

(1)利用式(1)計算項目之間的評分差的均值，記為平均評分偏差devij

(1)

其中，rui為用戶u對項目i的評分，ruj為用戶u對項目j的評分，Uij為對項目i與j都產生了評分的用戶集合，|Uij| 為集合Uij中用戶個數。

(2)利用式(2)，根據目標用戶的歷史評分和項目間的平均評分偏差，產生目標用戶未評分項目的預測評分

(2)

其中，用preui為用戶u對項目i的預測評分，I(u)為用戶u產生過項目評分，且滿足 (i≠j,|Uij|>0) 的項目集合，|I(u)| 為集合I(u) 中的項目個數。

(3)將預測評分進行Top-N排序，對目標用戶產生推薦。

1.2 Weighted Slope One算法

傳統Slope One算法簡單、高效且可擴展。但是在計算項目i與項目j間的平均評分偏差時，沒有將不同用戶和項目區別對待，導致推薦結果不夠理想。如果對項目i和項目j都產生評分的用戶數為200，對項目i和項目k都產生評分的用戶數為20，顯然，產生共同評分的用戶數差異會影響平均評分偏差的可靠性。本例中得到的平均評分偏差devij要比devik更精確，所以在進行評分預測時應該賦予devij更高的權重。因此，文獻[2]提出了將用戶數量作為項目間平均評分偏差的權重的Weighted Slope One算法，如式(3)所示

(3)

1.3 相似度計算方法

相似度計算作為協同過濾算法中關鍵步驟，在近鄰用戶的選擇中顯得尤為重要。常用的幾種(用戶)相似度計算方法如下所示：

(1)余弦相似度

(4)

其中，rui和rvi分別表示用戶u和v對項目i的評分，Iuv為u和用戶v共同評分的項目集。

(2)修正余弦相似度

(5)

(3)Pearson相關系數

(6)

2 本文算法

針對傳統Slope One算法和Weighted Slope One算法在計算項目平均評分偏差時，忽略了用戶之間的內在關系，無差別地使用所有用戶的數據可能會引入大量不相關的評分數據，從而導致得到的平均評分偏差誤差大并影響推薦質量，以及采用單一加權方式來提高推薦精度上存在的不足等問題，本文先采用一種改進的k近鄰方法，去除部分不相關的干擾用戶，以過濾掉干擾的評分數據。然后在評分預測時，從用戶相似度、用戶綜合信任度和項目相似度三方面綜合考慮，提出一種動態k近鄰輔助多權值Slope One算法，以提高推薦的準確率。

2.1 改進的動態k近鄰方法

2.1.1 改進的相似度計算

k近鄰的選擇取決于相似度計算，本文選擇Pearson相關系數，如式(6)所示，其定義請參見文獻[9]。

假設用戶共同評分項目集合很小，且它們的評分也很接近，就會得到較高的相似度。但這是不可靠的，因為集合基數太小，不具普遍性。因此，可以考慮將用戶間共同評分的項目數作為一個平衡因子Nuv，來改善用戶評分數據稀疏的問題，如式(7)所示

(7)

其中，|Iuv| 為用戶u和v共同評價的項目數，|Iu| 為用戶u評分項目數，|Iv| 為用戶v評分的項目數。

傳統的Pearson相關系數無差別對待所有項目，忽略了熱門項目對相似度帶來的影響。熱門項目往往反映的是大眾的喜好，并不能完全代表個人的偏好，反之，若兩個用戶都對某個冷門項目產生評分，則更能反映用戶間的相似性。因此本文引入熱門項目懲罰因子wi，如式(8)所示

(8)

其中，Ni為所有用戶中喜歡用戶u和用戶v共同評價的項目i的用戶數。

而在實際生活中，用戶的興趣不會保持一成不變，用戶近期的評分記錄相對于比較久遠的評分記錄對預測應該有著更重的權值。因此，本文采用非線性指數遺忘函數來刻畫用戶興趣隨時間的變化，其值保持在(0,1]之間。并定義興趣穩定期概念為用戶興趣保持不變的時間周期，用于解決用戶興趣在較小的時間窗內保持不變的問題，使得用戶興趣的衰減呈現梯度指數衰減，更加符合實際情況，如式(9)所示

(9)

其中，t=tnow-tui，tnow為當前時間，tui為用戶u對項目i的產生評分時間，Ts為興趣穩定期。

綜上，結合平衡因子、熱門項目懲罰因子和時間權重，改進的Pearson相關系數如式(10)所示

(10)

2.1.2 閾值過濾

傳統的k近鄰算法固定k值不具有特殊性，無法適應不同的預測場景、人群等。為了提高預測精度，本文在采用改進的Pearson相關系數度量用戶相似度的情況下，設置一個評分相似度閾值λ，針對不同的目標用戶篩選出動態k近鄰用戶集。即在與目標用戶產生共同評分項目的用戶集中，只有大于相似度閾值λ的用戶，才會被選入目標用戶的動態k近鄰用戶集合參與評分預測，并將該集合定義為rknn(u)，如式(11)所示

rknn(u)={v|simr(u,v)≥λ}

(11)

2.2 加權因子

2.2.1 改進的用戶相似度

采用上章節改進的Pearson相關系數，如式(10)所示，將它作為權重加權到Slope One算法中，以考慮用戶間相似性的影響。

2.2.2 用戶綜合信任度

用戶信任度可以作為評分預測的一個重要依據。在生活中，一個值得信任的人提供的信息就具有更高的可靠性，同理，在Slope One算法中，也可以運用這種思維。具有高信任度的用戶對某些項目產生的歷史評分將具有更高的可信性和參考價值，反之亦然。因此，本文提出一種用戶綜合信任度，包含用戶活躍度和評分公正度兩方面。事實上，并非所有的用戶都積極參與項目的評分，這就會出現部分用戶的評分數量較多，而另外一部分用戶評分數量較少的情況，顯然我們更愿意去信任那些評分比較積極的用戶。因此，我們可以采用用戶的項目評分數去衡量用戶活躍度。當用戶的項目評價數越多，其活躍度越高，反之越低。但是僅通過用戶活躍度去衡量某個用戶的信任度是不夠的，因為某些用戶可能存在隨意或者惡意評分的情況。因此，需要考慮用戶對項目的評分客觀公正程度。本文采用用戶對項目的評分與其平均評分差值作為衡量用戶評分公正度的標準，當這差值越大，其評分公正度越小，反之越大。

用戶的活躍度Au如式(12)所示，其值保持在(0,1]之間

(12)

用戶的公正度Fu如式(13)所示，其值保持在(0,1]之間

(13)

結合上述兩個因子，用戶綜合信任度T(u) 如式(14)所示

T(u)=Au*Fu

(14)

對于某個用戶來說，他的評分數量越多而且評分具有越高可靠性，就越具有參考價值，賦予越高的權重。

2.2.3 改進項目相似度

Weighted Slope One算法在衡量項目間內在聯系的時候，考慮了兩個項目共同產生評分的用戶數量的影響。因此，在評分數據稀疏情況下，針對Pearson相關系數準確度不高的問題，可以結合Weighted Slope One算法的思想，加權項目間共同評分的用戶數來進行改進，如式(15)所示

(15)

其中，Uij表示對項目i和項目j共同評分的用戶集合，|Uij| 表示該集合中用戶的個數，|Ui| 表示對項目i評分的用戶數，|Uj| 表示對項目j評分的用戶數。

綜合多個方面進行考慮，可以有效解決單因素加權改進的不足。

2.3 動態k近鄰輔助多權值Slope One算法描述

(16)

(17)

最后，將生成的預測評分，進行Top-N推薦。具體過程如下：

輸入：用戶-項目評分矩陣Rm×n，目標用戶u，目標項目j，用戶相似度閾值λ，興趣穩定期Ts，推薦長度N。

輸出：N個推薦項目。

步驟1 根據評分矩陣Rm×n，使用改進的相似度計算式(10)計算用戶間相似度矩陣Sm×m。

步驟2 將其他用戶與目標用戶u進行相似度比較，篩選出相似度值大于λ的用戶作為u的動態k近鄰用戶集合rknn(u)。

步驟3 在集合rknn(u) 中，采用式(16)計算目標項目j與其它項目間的平均評分偏差。

步驟4 通過式(17)為目標項目j生成預測評分。若用戶u的rknn(u) 集合為空，則以u對其它項目的評分均值作為預測評分，若u未產生過任何評分，則以項目j的評分均值作為預測評分。

步驟5 將產生的預測評分進行排序，并取評分較高的N個項目生成推薦列表。

3 實驗結果與分析

3.1 實驗數據集

本文實驗采用Grouplens提供的MovieLens數據集[12]。MovieLens數據集包含大量用戶的電影的評分數據，以及電影元數據信息和用戶屬性信息等。其中，數據集MovieLens 100k記錄了943個用戶在1682部電影上產生的 100 000 條評分記錄，評分范圍由1到5，評分的高低反映了對電影的喜愛程度。本實驗隨機選取100 k總數據集的80%作為訓練集，余下的20%用作測試集。

3.2 度量標準

本文采用實際評分和預測評分的平均絕對誤差(mean absolute error，MAE)來衡量算法預測評分的準確性。MAE的值越高，預測評分的準確性越低，反之亦然。MAE如式(18)所示

(18)

其中，pi和qi分別表示項目i的預測評分和實際評分，N為測試集中預測項目的數量。

3.3 實驗結果與分析

本文實驗分為兩個部分：一是參數的選擇，包括用戶相似度閾值λ，興趣穩定期Ts；二是進行算法對比性實驗，驗證改進的有效性。

3.3.1 參數分析實驗結果

(1)首先進行興趣穩定期Ts的選擇實驗。由于改進的k近鄰方法中涉及到用戶相似度閾值λ和興趣穩定期Ts那個參數的選擇，我們先去掉相似度閾值這一參數，然后采用傳統的k近鄰算法中選擇式(10)來進行用戶相似度的計算，最后將產生的k近鄰用戶集拿去進行平均評分偏差的計算，定義為改進k近鄰Slope One算法(improved k-nearest neighbor Slope One，KSO)。

分別取近鄰k值為10、20、30與不同取值的興趣穩定期來進行實驗。由圖2可知，在用戶興趣穩定期Ts為30的情況下，MAE總能取到最優值，因此我們選擇Ts=30作為最佳的興趣穩定期。

圖2 興趣穩定期對MAE的影響

(2)進行用戶相似度閾值的選擇實驗。如果將相似度閾值設置得太低，就會引入過多的干擾數據參與到評分預測當中，勢必會影響推薦的準確性，同理，如果將相似度閾值設置的太高，得到的用戶近鄰集合就會太小，推薦的精度也不會太理想。因此，從這兩方面考慮，選取0.1到0.8作為用戶相似度閾值分別進行實驗。由圖3可知，在相似度閾值為0.3時，可以取得最優的MAE值。

圖3 λ對MAE的影響

綜上，分別取λ=0.3和Ts=30作為本實驗的用戶相似度閾值和興趣穩定期。

3.3.2 算法對比實驗結果

(1)首先，比較本文第二章中的兩個改進部分，以驗證改進的有效性。

將數據集MovieLens 100k通過5折線交叉法，隨機分成5等份，輪流取其中4份作為訓練集，取剩下的1份作為測試集。然后將2.1節改進的動態k近鄰方法與Slope One算法結合，定義為動態k近鄰Slope One算法(dynamic k-nearest neighbor Slope One，KTSO)，并與結合2.1節和2.2節提出的動態k近鄰輔助多權值Slope One算法進行對比，采用上面分好的數據集，分別執行5次。

實驗結果如圖4所示，在采用動態k近鄰的情況下，結合多權值改進的KTWSO算法的MAE值明顯低于僅采用動態k近鄰改進的KTSO算法，從而驗證了2.2節算法改進的合理性。

圖4 KTSO和KTWSO的MAE比較

(2)然后將本文提出的KTWSO算法與SO算法、WSO算法以及文獻[5]提出的The K-nearest neighbor Slope One algorithm based on weighted user similarity and user tag算法(KHSO)進行比較，分別進行5組實驗，實驗結果見表1。

表1 不同算法下的MAE

分別取表中各算法MAE均值作比較，由圖5中可知，本文提出的KTWSO算法的MAE值相對于前3種算法分別降低了3%、2%和1%。相對于KHSO算法來說，本文提出的KTWSO算法采用動態k近鄰，過濾掉了部分干擾數據，并一定程度上改進了傳統K近鄰算法無法適應不同的預測場景、人群的問題，同時從用戶相似度、用戶綜合信任度以及項目相似度多方面考慮，進一步提高了評分預測的準確性，達到了更好的推薦效果。

圖5 SO、WSO、KHSO和KTWSO的MAE比較

4 結束語

針對傳統Slope One算法無差別地使用所有用戶評分數據導致評分預測不準確的問題，本文引入動態k近鄰的思想來篩選用戶的近鄰用戶集，并從用戶興趣偏移和熱門項目方面對相似度計算方法進行改進，一定程度上提高了近鄰用戶的質量。然后將近鄰用戶集運用到計算項目平均評分偏差中，從而剔除了干擾用戶數據并提高了推薦精度。同時，本文優化的算法將用戶相似度、用戶綜合信任度和項目相似度作為權重因子加權到Slope One算法的評分預測當中，使得推薦的精度進一步提高。未來，我們可以從用戶和項目的標簽信息考慮，將更多信息納入算法，以獲得更多的改進。