一種改進的協作過濾算法

劉浩杰 金鑫

(武漢理工大學 信息工程學院，湖北 武漢 430072)

0 引言

隨著計算機和網絡技術的發展，呈現在計算機用戶面前的信息變得越來越龐大，但不同的用戶對于信息的需求是不同的，因此如何快捷地為用戶找到所需的信息成為一個難題，而協作過濾方法則是目前解決這一問題的主要手段。該方法是指信息使用者(即用戶)根據自身的需求，通過和其他用戶進行合作，形成一定的協作規則，或利用多個信息使用者的傾向性來預測單個用戶的興趣，然后根據具有相同興趣喜好的用戶對信息進行評價，從而得到推薦結果。與已有的大多數其他信息推薦方法相比，基于協作過濾對用戶進行信息推薦的優勢是巨大的，它是目前個性化推薦系統中最具有優勢的技術之一，也是目前眾多研究者的研究熱點之一。與此同時，協作過濾技術的運用范圍也正在不斷擴大，在諸如信息查詢、評價預測、產品推薦和電子商務等領域都有著較好的研究前景，本文也將針對協作過濾技術進行研究。

1 相關工作

目前，對于協作過濾技術的研究［1］有很多，在基于協作過濾技術開發的系統中，有些已經達到了使用水平，例如，基于資源的協作過濾推薦算法［2］、基于項目的協作過濾推薦算法［3］、基于用戶的協作過濾推薦算法［4］等等。盡管這些技術已經取得了較大的成功，但還有很多地方存在缺陷，需要做進一步的研究，總結起來主要有以下幾點:(1)如何更為有效地對用戶的行為和興趣進行形式化描述;(2)現有的多用戶之間相似性計算方法存在語義不一致性，如何解決該問題還沒有一種較好的方案;(3)由于目前的信息量越來越龐大，現有的方法不能很好地應對由于信息量增加造成的數據高維稀疏性和擴展性差的問題，還有待研究出更加有效的方法來進一步提高個性化服務的質量;(4)目前大多數方法對于某個資源的評分值都不是一個整數，很多方法對于得到的評價值采用＂四舍五入＂的原則來進行取舍，然而這種方式已經被證明無法得到準確的結果，與用戶的真正需求相差甚遠。鑒于以上幾點不足，本文針對現有的協作過濾方法面臨不足，提出了一種改進的協作過濾推薦算法，并進行了實驗驗證。實驗結果表明，本文提出的協作過濾算法在推薦效果方面更優，能夠更快更好地為用戶推薦所需的信息。

2 協作過濾的基本思想

協作過濾算法的主要思想是依據不同信息使用者對資源的喜好來為對方相互推薦資源，這樣可以免去對資源內容進行分析的復雜過程，然后，依據信息使用者對資源的評價來計算用戶之間的相似性，并根據計算得到的相似性來預測當前用戶對資源的需求強弱。下面先給出傳統的協作過濾算法描述，如下所示。

算法1 傳統的協作過濾算法

輸入:測試數據集

輸出:對目標用戶的推薦結果

Step1.使用皮爾遜(Pearson)相關系數進行加權處理來計算用戶之間的相似性;

Step2.從Step1中選擇相似度大于某一規定閾值的k個用戶，即為和當前用戶最相似的用戶;

Step3.利用相似鄰居的加權和來預測當前用戶ua對資源 t的打分:

其中，Sua表示用戶 ua的鄰居集，Pua，t表示用戶ua對資源t的預測值，sim'(u0，ui)表示用戶之間的相似度。

上述算法產生的預測值Pua，t通常情況下不是一個整數，但是在實際應用中，信息使用者對資源評價值需要整數，例如，在電影推薦系統中，用戶的評分級別一般為2、4、6、8、9和10分。所以，對于Pua，t，我們還需要將它進一步修正為一個整數。如果預測值為2、4、6、8、9 和 10 分，可以直接判定，但是如果預測值為 5.2分，現有處理辦法都是按照"四舍五入"的原則判定為5分，如果預測值為4.8分則判定為5分，顯然，這種處理是不夠合理的，它沒有考慮到用戶對資源使用存在的潛在需求。另外，當數據量很大時，傳統的協作過濾算法計算就會很復雜，需要耗費大量的計算資源，另外還無法避免或減少數據稀疏性所帶來的計算不準確問題，從而導致了推薦質量的低下。

針對以上的問題，本文提出了一種改進的協作過濾算法，算法通過對預測值進行修正、過濾數據預處理、聚類等一系列操作來保證最終推薦結果的準確性。

3 改進的協作過濾算法

3.1 對協作過濾算法中預測值的修正

為了方便論文的后續描述，先給出以下幾個相關的定義。定義1趨勢度(Trend Degree):指用戶根據自身的需求，將某一信息評為某一級別的概率。設某個評分級別k趨勢度標記為Tre(k)，則有:

L表示評分級別(Level)的個數，Count(k)表示用戶評分中被評為級別k的個數。

定義2差異度(Difference Degree):按照用戶根據自身的需求，指通過算法對某一信息進行評價的值偏離某個評分級別的程度大小。設預測值p相對于級別k的差異度標記為Dif(p，k)，計算公式為:

定義3 可信度(Credible Degree):指通過某個算法預測用戶對一個資源評分的預測值應該被判定為某個評分級別的可能性程度。設預測值p相對于級別k的可信度標記為Cre(p，k)，計算公式為:

其中α為可調節因子，在實驗中來設定。

結合上述三個定義，預測值的修正算法如下所示。

算法2 預測值的修正算法

輸入:通過某算法計算用戶對一個資源的預測值P，該用戶的評分集合 R={r1，r2，r3，…，rn}，評分級別 L={l1，l2，l3，…ln}

輸出:預測值P的修正值;

Step 1.根據公式(1)計算每個評分級別li的趨勢度T(li);

Step 2.根據公式(2)計算預測P與最接近的兩個評分級別的差異度 Dif(p，lia)和 Dif(p，lib);

Step 3.根據公式(3)計算與預測值P最接近的兩個評分級別的可信度Cre(p，lia)和Cre(p，lib)，選擇較大的作為最后的修正值。

3.2 改進后的協作過濾算法

目前的信息資源數量越來越龐大，但是我們可以根據資源的種類、屬性和領域等對其進行分類，劃分為不同的類別，這樣就可以大大降低數據的維度和稀疏程度。那么，如果先對多個用戶進行聚類，然后在簇內部計算目標用戶和其他用戶的相似性，并選取相似度值大于某個閾值的K個用戶作為其最近鄰居。這樣，不僅可以縮小目標用戶查找最近鄰的搜索范圍，而且由于簇內部的用戶的興趣也較為相似，因此，他們共同進行評分的參考數據往往也較多，這樣可以增加選擇相似鄰居的準確性，從而能夠提高為用戶進行資源推薦的質量。

基于以上的考慮，得出本文改進的協作過濾算法的主要思想是:首先對資源進行分類，然后通過加權過濾數據預處理，再利用K-平均聚類算法對用戶進行聚類，最后，通過計算用戶間的相似性，產生最近鄰居集，并對預測值進行修正，從而得到用戶的推薦集。算法描述如下所示。

算法3 改進的協作過濾推薦算法

輸入:測試數據集

輸出:對目標用戶的推薦集

Step1.對資源項目依內容進行分類;

Step2.將用戶-項目矩陣R(M×N)轉化為用戶-資源項目類別矩陣C(M×X);

Step3.對矩陣C(M×X)進行加權過濾數據預處理，得到CW(M×X);

Step4.運用K-平均聚類算法對用戶進行聚類;

Step5.在各簇中，計算目標用戶與其他用戶的相似性;

Step6.選取目標用戶的若干最相似用戶，建立最近鄰居集。

算法各個步驟的具體說明如下:

Step1，在對資源進行分類時，主要基于啟發式規則和基于貝葉斯分類的方法進行資源分類，以確保分類的正確性;

Step2，將Step1中的分類結果進行轉換，得到用戶-資源項目類別矩陣C(M×X)，矩陣的值Cm，x表示用戶M對某一資源類別X的評分。由于資源可以依據其內容或者屬性劃分為多個不同的類別，用戶對資源的最終評分通常取其不同類別評分和的平均值;

Step3，一般情況下，不同的用戶進行評分的數據是不同的，因此得出的評分結果也存在很大的差異，為了歸一化評分結果，本文采用文獻［5］中提出的一種加權過濾的方法，對用戶-資源項目類別矩陣C(M×X)進行數據預處理，從而得到標準化的資源;

Step4，在Step2和Step3的基礎上，采用K-平均聚類算法對用戶進行聚類;

Step5，在對用戶聚類后的基礎上，在簇內計算目標用戶和其他用戶的相似性，再選取相似度值大于某一規定閾值的用戶作為其最近鄰居。用戶的相似性本文選取余弦相似性來評價。

Step6，根據最近鄰居對項目i的評分來計算目標用戶u對資源項目i的預測評分。再依據預測評分的高低，產生資源項目的推薦。目標用戶預測評分的計算公式如下所示。

4 實驗結果與分析

4.1 測試數據集

本文利用了較為典型的MovieLens數據集［6］來進行實驗測試，它包含了900多個用戶對1600多部電影的10萬個評價值。從每個用戶的打分項中，隨機抽取30個作為測試項，其余的作為訓練項，因此訓練集的大小為90500，測試集的大小為9400，和目前大多數協作過濾方法的評價指標一樣，本文也使用正確率(Correct)、平均絕對誤差(MAE)、運行時間(Time)作為實驗的評價標準。

4.2 對比實驗及結果分析

在實驗中，考慮了鄰居數目從10到110的情況下，兩種算法(算法1和算法3)的比較(權重因子取值為0.85)。其中，算法1是傳統的協作過濾推薦算法，算法3是本文提出的改進的協作過濾推薦算法。正確率的比較如圖1所示:

平均絕對誤差的比較如圖2所示:

運行時間的比較如圖3所示:

圖3 不同鄰居數下的Time開銷

比較改進算法和傳統算法的推薦效果平均值如表1所示:

表1 推薦效果的平均值比較

由以上圖和表可知，本文改進的算法的正確率有了比較明顯的提高，其時間開銷要略高于傳統算法，但推薦結果的平均絕對誤差卻比傳統方法降低了很多，這表明本文的方法是有效的。仔細分析其原因可知，這主要是因為改進后的算法首先通過對資源進行分類、加權過濾數據預處理以及K-平均聚類算法對用戶進行聚類，然后利用余弦相似度計算用戶間的相似性，產生最近鄰居集，最后基于可信度對算法產生的預測值行了修正，因此得到了較為理想的推薦結果。

5 結束語

針對現有協作過濾算法沒有對預測值進行修正、存在高維數據稀疏性以及可擴展性不強等問題，本文提出了一種改進的協作過濾方法，該方法基于可信度對預測值進行了修正，最后采用基于資源分類、聚類的思想得到目標用戶的推薦集。經過實驗分析，改進后的算法與傳統的協作過濾算法相比，能得到更好的推薦質量。

未來的工作包括以下兩個方面:第一，根據用戶的背景知識，從多個角度進行相似度的計算，挖掘語義層次的最近鄰居;第二方面，對算法的時間復雜度做進一步的優化，并考慮將改進后的算法應用到其它的領域。

［1］曾春，邢春曉，周立柱.個性化服務技術綜述［J］.軟件學報，2002，13(10):1952-1961.

［2］紀良浩，王國胤.基于資源的協作過濾推薦算法研究［J］.計算機工程，2008，44(8):33-36.

［3］李偉，王新房，劉妮，等.基于項目的非鄰近序列模式推薦算法［J］.計算機工程，2009，35(16):65-67.

［4］鄧愛林，左子葉，朱揚勇，等.基于項目聚類的協同過濾推薦算法［J］.小型微型計算機系統，2004，25(9):46-52.

［5］Tuguldur Sumiya，Jonghoon Chun，Sang-goo Lee，et al.A weighted siringmethod to improve the effectiveness of collaborative filtering［C］//2004 IEEE Region 10 Conference，2004:266-269.

［6］Movielens［EB/OL］.［2006-10-05］.http://movielens.umn.edu/login.