一種改進(jìn)的協(xié)作過濾算法

劉浩杰 金鑫

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

0 引言

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

1 相關(guān)工作

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

2 協(xié)作過濾的基本思想

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

算法1 傳統(tǒng)的協(xié)作過濾算法

輸入:測試數(shù)據(jù)集

輸出:對目標(biāo)用戶的推薦結(jié)果

Step1.使用皮爾遜(Pearson)相關(guān)系數(shù)進(jìn)行加權(quán)處理來計算用戶之間的相似性;

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

Step3.利用相似鄰居的加權(quán)和來預(yù)測當(dāng)前用戶ua對資源 t的打分:

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

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

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

3 改進(jìn)的協(xié)作過濾算法

3.1 對協(xié)作過濾算法中預(yù)測值的修正

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

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

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

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

其中α為可調(diào)節(jié)因子，在實驗中來設(shè)定。

結(jié)合上述三個定義，預(yù)測值的修正算法如下所示。

算法2 預(yù)測值的修正算法

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

輸出:預(yù)測值P的修正值;

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

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

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

3.2 改進(jìn)后的協(xié)作過濾算法

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

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

算法3 改進(jìn)的協(xié)作過濾推薦算法

輸入:測試數(shù)據(jù)集

輸出:對目標(biāo)用戶的推薦集

Step1.對資源項目依內(nèi)容進(jìn)行分類;

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

Step3.對矩陣C(M×X)進(jìn)行加權(quán)過濾數(shù)據(jù)預(yù)處理，得到CW(M×X);

Step4.運用K-平均聚類算法對用戶進(jìn)行聚類;

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

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

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

Step1，在對資源進(jìn)行分類時，主要基于啟發(fā)式規(guī)則和基于貝葉斯分類的方法進(jìn)行資源分類，以確保分類的正確性;

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

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

Step4，在Step2和Step3的基礎(chǔ)上，采用K-平均聚類算法對用戶進(jìn)行聚類;

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

Step6，根據(jù)最近鄰居對項目i的評分來計算目標(biāo)用戶u對資源項目i的預(yù)測評分。再依據(jù)預(yù)測評分的高低，產(chǎn)生資源項目的推薦。目標(biāo)用戶預(yù)測評分的計算公式如下所示。

4 實驗結(jié)果與分析

4.1 測試數(shù)據(jù)集

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

4.2 對比實驗及結(jié)果分析

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

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

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

圖3 不同鄰居數(shù)下的Time開銷

比較改進(jìn)算法和傳統(tǒng)算法的推薦效果平均值如表1所示:

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

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

5 結(jié)束語

針對現(xiàn)有協(xié)作過濾算法沒有對預(yù)測值進(jìn)行修正、存在高維數(shù)據(jù)稀疏性以及可擴(kuò)展性不強(qiáng)等問題，本文提出了一種改進(jìn)的協(xié)作過濾方法，該方法基于可信度對預(yù)測值進(jìn)行了修正，最后采用基于資源分類、聚類的思想得到目標(biāo)用戶的推薦集。經(jīng)過實驗分析，改進(jìn)后的算法與傳統(tǒng)的協(xié)作過濾算法相比，能得到更好的推薦質(zhì)量。

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

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

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

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

［4］鄧愛林，左子葉，朱揚勇，等.基于項目聚類的協(xié)同過濾推薦算法［J］.小型微型計算機(jī)系統(tǒng)，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.