一種有效緩解數據稀疏問題的協同過濾推薦算法

程 芳 沈紅巖 趙 艷

(河北農業大學信息科學與技術學院，河北 保定 071000)

?

·技術視角·

一種有效緩解數據稀疏問題的協同過濾推薦算法

程 芳 沈紅巖 趙 艷

(河北農業大學信息科學與技術學院，河北 保定 071000)

傳統協同過濾推薦算法依據共同評分項目計算用戶相似度，進而產生推薦項目。然而，隨著用戶和商品數量的不斷增加，用戶共同評分的項目會越來越少，甚至沒有，因此傳統協同過濾推薦算法對用戶之間相似度的衡量將會越來越不準確，從而影響推薦系統的性能。針對這一問題，本文對用戶相似度的計算方法進行了改進，提出直接相似度和間接相似度的概念，同時引入關鍵人物權重，進一步提高推薦系統的準確性。

電子商務；推薦系統；協同過濾；直接相似度；間接相似度；關鍵人物

隨著電子商務的迅速發展，電子商務網站平臺的商品越來越多，同時相當多的用戶面臨著海量的商品往往不知如何下手，必須花費大量的時間和精力來尋找所需的信息，因此智能推薦系統在電子商務網站中尤為重要。協同過濾推薦是目前最好的一種推薦技術[1]，其根據用戶的評分數據進行項目推薦。傳統的協同過濾推薦技術雖然一段時間內發揮了很大的作用，然而隨著電子商務網站規模的不斷擴大，協同過濾推薦技術面臨著眾所周知的嚴重問題[2]：(1)“稀疏性”問題：用戶-項目評價矩陣非常稀疏；(2)“冷啟動”問題：一個新的商品出現時，用戶對其評分會特別少，甚至沒有，那么這個商品就不容易被推薦出去。另外，一個新用戶加入時，由于沒有對任何項目進行過評價，系統就無法對其進行推薦。(3)“可擴展性”問題：面對用戶和商品數量的日益增多，系統的性能會越來越低。

為了解決數據稀疏而導致的推薦結果不準確問題，許多學者提出了各自不同的方法。目前常用的方法有以下幾種：(1)數據填充：在計算用戶相似性之前，首先對原始的用戶-項目評分矩陣進行填充，從而降低其稀疏性，提高推薦準確度。郝立燕等[3]根據原始矩陣中評分數據的特征，采用SOFT-IMPUTE算法對評分矩陣進行填充，然后利用填充后的矩陣計算用戶相似性，進而做出推薦預測。張玉芳等[4]采用分兩步對原始評分矩陣進行填充的方法。首先在利用傳統協同過濾推薦算法尋找目標用戶鄰居集時，只考慮相似度比較高的用戶作為目標用戶鄰居，進而對評分矩陣進行第一次填充，然后將第一步填充后的矩陣作為新的用戶-項目矩陣，在此基礎上進行第二次填充，此方法可以很好的解決數據稀疏問題。黃永鋒等[5]在原始評分矩陣基礎上，首先根據用戶訪問過的項目的特征及訪問頻率對用戶訪問過但沒有給出評價的項目進行填充，從而降低原始評分矩陣的稀疏度，提高推薦準確性。(2)聚類技術：在計算用戶相似性之前，首先對用戶或項目進行聚類，從而降低預測計算量，提高推薦質量。黃國言等[6]及崔春生等[7]提出對用戶進行聚類的方法，前者根據用戶對項目評分的相似性對用戶進行聚類，后者根據用戶的興趣度對用戶進行聚類，進而分別在各聚類內部計算用戶相似性，產生推薦項目。吳潮等[8]提出對用戶和項目兩個方面分別聚類并互相結合的方法，在已有聚類中尋找用戶最近鄰居集，實現對用戶的推薦。(3)矩陣分解：對原始評分矩陣進行分解，從而降低評分矩陣維數，提高推薦精確度。李改等[9]分析了傳統的矩陣分解模型(SVD)的弊端，并對其進行了改進，提出了帶正則化的基于迭代最小二乘法的矩陣分解方法，此方法提高了傳統推薦算法的抗稀疏性。楊陽等[10]提出增量奇異值矩陣分解的方法，對評分矩陣進行梯度分解，從而有效的解決矩陣稀疏的問題。

以上幾種方法均在一定程度上緩解了評分矩陣的稀疏性問題，并取得了一定的成果，但在計算用戶形似度進而尋找最近鄰居集時，仍局限于用戶共同評分項目，而大多數用戶共同評分項目極少，此時用戶相似度的計算只受幾個項目評分的影響，計算結果很容易出現偏差。尤其當用戶興趣愛好一致但不存在共同評分項目時，系統則無法計算其相似性。針對這一問題，本文對傳統協同過濾推薦技術中計算用戶相似度及產生推薦項目的方法進行改進，使用戶相似度的計算不再僅僅依據用戶共同評分項目，同時兼顧用戶未評分項目，并引入關鍵人物權重，進而進一步提高推薦質量。

1 傳統協同過濾推薦算法

協同過濾推薦算法的主要思想是，利用現有用戶群過去的評價數據來預測當前用戶的購買意向[3]。這種方法的潛在假設是，如果某些用戶對一些項目的評價相似，那么他們對其他項目的評分也是相似的。通過相似性計算發現和當前用戶相似的N個近鄰，根據興趣相似的用戶群的評價，計算產生對某些項目的預測評分，最后根據預測值將排名最前的k個項目推薦給當前用戶。算法一般分為3步：建立用戶-物品評分矩陣，計算用戶相似度并尋找近鄰集，產生推薦項目[11]。

1.1 建立用戶-物品評分矩陣

推薦系統經常利用用戶對已購買物品的評分作為推薦系統的數據源，一般定義用戶集U={U1，U2，…，Um}，物品集定義為I={I1，I2，…，In}，通常用戶-物品評分矩陣用矩陣Rm×n來表示，其中的每一項Rij表示第i個顧客對第j個商品項的評價值[12]，通過獲得的評價值來反映顧客的購買興趣。通常以1～5表示用戶對物品的偏好程度，沒有評分的項目用0代替。

1.2 計算用戶相似度并尋找近鄰集

在這一步先計算用戶之間的相似度，然后根據相似度尋找到用戶的最近鄰居集。在協同過濾推薦系統中，確定相似用戶集，一般采用的方法是Pearson相關系數[3]。給定評分矩陣R，用戶a和用戶b的相似度sim(a，b)可以用公式(1)來表示。

(1)

1.3 產生推薦項目

對于用戶a未作評價的項目，可以通過用戶a的最近鄰居集N的評分來預測，具體方法如下：

(2)

最終推薦項目的獲取可以通過選擇預測分數最高的N個項目作為推薦結果。

2 本文算法

在大型電子商務網站中，用戶評分的項目極為稀疏，一般不足1%，傳統的協同過濾推薦算法無疑會導致算法準確率下降，使得系統難以找到真正的相似用戶。為了彌補傳統相似度計算方法的缺陷，本文提出了一種改進的協同過濾推薦算法。

2.1 用戶相似度計算方法的改進

本文用戶相似度的計算方法與傳統的推薦系統不同之處在于，在計算用戶a與用戶b的相似度時，不僅僅根據兩個用戶共同評價過的項目集合進行計算，同時考慮用戶a評價過，而用戶b未評價過的項目集合。即計算用戶a與用戶b的相似度Sab時，需綜合考慮直接相似度和間接相似度兩個因素，計算公式如下：

Sab=α*Ri+(1-α)*Rj

(3)

其中，Ri表示用戶a與用戶b的直接相似度，Rj表示用戶a與用戶b的間接相似度，α為小于1的權重系數。下面分別給出Ri和Rj的計算公式。

2.1.1 計算直接相似度

在用戶-物品評分矩陣中，如果用戶a與用戶b共同評價過同一個項目，則認為用戶a與用戶b進行了一次交易，那么用戶a與用戶b之間的相似度可以直接利用Pearson系數計算方法，公式如下：

(4)

2.1.2 計算間接相似度

在用戶-物品評分矩陣中，定義用戶a評價過的項目集為Ia，用戶b評價過的項目集為Ib，用戶a評價過但用戶b沒有評價的項目集合Id=Ia-(Ia∩Ib)。這里首先采用傳統的協同過濾推薦技術尋找用戶b的最近鄰居集，進而得到用戶b對項目集Id的預測評價值，進而在項目集Id上，通過用戶a的評價值與用戶b的預測評價值得到的相似度即為用戶a與用戶b的間接相似度。因此，計算用戶a與用戶b的間接相似度公式如下：

(5)

其中，ra，p是用戶a對項目p的評價值，rb，p是用戶b對項目p的預測評價值。

2.2 關鍵人物的引入

在所有的用戶中，總會有一些關鍵人物的存在。在推薦系統中，關鍵人物即為對推薦有特別幫助的用戶。關鍵人物具有如下特征，如內行：定義為寫了很多評論的用戶；頻繁評分者：評價了很多的物品；連接者：信任很多人，也被很多人信任。在推薦系統中引入關鍵人物能夠提高最終結果的準確度。

由于關鍵人物的評價對提高推薦系統的準確度起著重要的作用，因此，本文提高了關鍵人物的信任值權重，以此提高推薦系統準確度。在用戶-物品評價矩陣中，如果用戶a的近鄰集N中包含用戶b，即Ub∈N，且用戶b為關鍵人物。那么，引入關鍵人物權重后，計算用戶a與用戶b的相似度Sab的公式可以修改如下：

Sab=β*(α*Ri+(1-α)*Rj)

(6)

其中，β為大于1的權重系數。

2.3 產生推薦項目

改進用戶相似度計算及引入關鍵人物后，產生推薦項目可以由公式(2)修改如下：

(7)

最終推薦項目的獲取可以通過選擇預測分數最高的N個項目作為推薦結果。

3 推薦方法測試

3.1 實驗環境

實驗環境使用的服務器為IBM System x3850 X6，CPU為2枚Xeon E7-4820，最高主頻為2.5G，內存是4*16GB DDR3，共計64GB，操作系統采用Microsoft Windows Server 2012，推薦算法采用JAVA語言編寫。

3.2 實驗集

本文采用了MovieLens提供的數據集(http:∥www.grouplens.org)作為測試數據，MovieLens數據集包含了1997年9月至1998年5月的943個用戶對1 682部電影的100 000條評價記錄，每個用戶評價了至少20部電影，評分范圍1～5。針對這一數據集，出現了很多劃分訓練集和測試集的方法，本文采用的是站點提供的一種方法，將測試數據分為了訓練集(占80%)和測試集(占20%)，因此可以計算得出稀疏度為：(943*1682-100000)/(943*1682)=93.695%。

3.3 評價標準

評價推薦系統推薦質量的標準主要有統計精度度量方法和決策支持精度度量方法[13]。本文采用統計精度度量方法中廣泛使用的平均絕對偏差(Mean Absolute Error，MAE)作為度量標準，即通過計算預測的用戶評分與實際用戶評分之間的偏差來衡量預測的準確性。MAE的計算公式如下[14]：

(8)

其中，N表示預測分數的數量，pi代表項目i的預測評分，而qi代表項目i的實際評分。MAE值越小，準確度越高。

3.4 實驗結果分析

為驗證本文推薦算法的有效性，在實驗過程中，分別采用兩種推薦算法，即本文所改進的協同過濾推薦算法和傳統協同過濾推薦算法，并對兩種情況下的推薦結果進行對比分析。推薦算法中目標用戶的最近鄰居數以4為間隔從4個增加到32個。經過實驗驗證，取得最優的權值參數α值為0.8，β值為1.3，觀察不同條件下的推薦效果。實驗結果如表1。

表1 兩種推薦算法的MAE值比較

傳統的協同過濾推薦算法與本文改進的協同過濾推薦算法的推薦試驗MAE值比較結果直觀表示如圖1所示。

圖1 兩種推薦技術的MAE值比較

由以上實驗結果可以看出，本文所改進的推薦算法，對推薦結果有明顯的改善。隨著目標用戶最近鄰居數目的增加，雖然兩種推薦算法的MAE值都呈下降趨勢，但當鄰居數較多時，本文推薦算法的優勢越來越明顯，推薦結果更加準確。由此可見，本文所提出的協同過濾推薦算法可以增強推薦系統的抗稀疏性，提高推薦系統的推薦質量。

4 結 論

隨著電子商務網站的迅速發展壯大，智能推薦系統在電子商務網站中發揮著越來越重要的作用，而推薦算法決定了推薦系統的性能。計算用戶相似度是協同過濾推薦算法中最為關鍵的一步，本文在計算用戶相似度時充分考慮直接相似度、間接相似度以及關鍵人物權重三個方面因素，實驗結果證明，本文所改進的計算用戶相似度的方法比傳統的計算方法更合理更準確。尤其對于評分項目極少的用戶，可以根據間接相似度尋找其近鄰集，進而產生推薦項目。因此本推薦算法不僅可以很好的解決評分矩陣數據稀疏問題，同時還可以在一定程度上緩解系統冷啟動問題。

[1]許海玲，吳瀟，李曉東，等.互聯網推薦系統比較研究[J]．軟件學報，2009，20(2):350-362.

[2]夏建勛，吳非，謝長生．應用數據填充緩解稀疏問題實現個性化推薦[J]．計算機工程與科學，2013，35(5):15-19.

[3]郝立燕，王靖．基于填充和相似性信任因子的協同過濾推薦算法[J]．計算機應用，2013，33(3):834-837.

[4]張玉芳，代金龍，熊忠陽.分步填充緩解數據稀疏性的協同過濾算法[J]．計算機應用研究，2013，30(9):2602-2605.

[5]黃永鋒，覃羅春．一種有效緩解協同過濾推薦評價數據稀疏問題的算法[J]．東華大學學報：自然科學版，2013，39(1):83-87.

[6]黃國言，李有超，高建培，等.基于項目屬性的用戶聚類協同過濾推薦算法[J]．計算機工程與設計，2010，31(5):1038-1041.

[7]崔春生，吳祈宗，王瑩.用于推薦系統聚類分析的用戶興趣度研究[J]．計算機工程與應用，2011，47(7):226-228.

[8]吳潮，王永吉，王哲，等.兩階段聯合聚類協同過濾算法[J]．軟件學報，2010，21(5):1042-1054.

[9]李改，李磊.基于矩陣分解的協同過濾算法[J]．計算機工程與應用，2011，47(30):4-7.

[10]楊陽，向陽，熊磊.基于矩陣分解與用戶近鄰模型的協同過濾推薦算法[J]．計算機應用，2012，32(2):395-398.

[11]曾慶輝，邱玉輝．一種基于協作過濾的電子圖書推薦系統[J]．計算機科學，2005，32(6):147-150.

[12]劉東輝，彭德巍，張暉．一種基于時間加權和用戶特征的協同過濾算法[J]．武漢理工大學學報，2012，34(5):144-148.

[13]劉慶鵬，陳明銳．優化稀疏數據集提高協同過濾推薦系統質量的方法[J]．計算機應用，2012，32(4):1082-1085.

[14]郭均鵬，王啟鵬，寧靜，等.基于符號數據與非負矩陣分解法的混合推薦算法[J]．系統管理學報，2015，24(3):372-378.

(本文責任編輯：孫國雷)

Collaborative Filtering Recommendation Algorithm for Alleviating Data Sparsity

Cheng Fang Shen Hongyan Zhao Yan

(College of Information Science and Technology，Agricultural University of Hebei，Baoding 071000，China)

In traditional collaborative filtering recommendation Algorithm,similarity of users is often calculated based on common ratings,and then the recommended items are produced.However,with the increasing number of users and products,the common rated items will be less and less,and even no.So the measure of the similarity of users will be more and more inaccurate,and thus it will affect the performance of the recommendation system.In order to solve this problem,the method of calculating the similarity of users is improved,and the concepts of direct similarity and indirect similarity are put forward.At the same time,in order to further improve the accuracy of the recommendation system,the key figure is introduced into the system.

e-commerce;recommending system;collaborative filtering;direct similarity;indirect similarity;key figures

2015-12-27

保定市科學技術研究與發展指導計劃項目“基于協同過濾的農業信息推薦系統的研究與開發”(項目編號：14ZN019)、“農網中工控網絡信息安全攻擊監測方法的研究”(項目編號：14ZS005)；河北農業大學校基金“基于智能手機的三農科技信息服務體系的關鍵技術研究”(項目編號：LG201308)。

程 芳(1980-)，女，講師，碩士，研究方向：數值計算與計算機應用。

10．3969/j．issn．1008-0821．2016．03．013

TP301

A

1008-0821(2016)03-0076-04