王 菲，黃 剛，朱崢宇

(南京郵電大學 計算機學院，江蘇 南京 210000)

0 引 言

隨著互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡信息呈爆炸式增長，導致用戶無法在龐大的數(shù)據(jù)信息中篩選有價值的信息，信息過載問題亟待解決。在此背景下，個性化推薦系統(tǒng)應運而生。具體而言，推薦系統(tǒng)是基于用戶的歷史行為數(shù)據(jù)或物品數(shù)據(jù)，通過有效的算法，為用戶推薦符合需求的物品。目前在電子商務和社交網(wǎng)絡等領域中，都不同程度地使用了推薦系統(tǒng)技術。

協(xié)同過濾(collaborative filtering,CF)算法是應用最廣泛的推薦算法之一，該算法利用用戶對項目評分的高低來衡量用戶的興趣偏好，根據(jù)評分進行推薦。協(xié)同過濾推薦算法主要分為基于模型和基于鄰域兩類?；谀Ｐ偷膮f(xié)同過濾主要通過用戶對產(chǎn)品的評分信息訓練出相應的模型，利用模型再進行未知數(shù)據(jù)的預測。雖然憑借良好的擴展性和可實踐性而應用廣泛，但是隨著用戶和項目數(shù)量的急劇增加，面臨著用戶-評分矩陣稀疏性的問題，導致推薦質(zhì)量不高[1]?；卩徲虻膮f(xié)同過濾算法是通過計算用戶間或者項目間的相似度建立近鄰關系，在進行預測推薦時，推薦系統(tǒng)可以根據(jù)目標的近鄰的評分進行預測。但是在計算相似度時，用戶和條目的數(shù)量越大，耗費的時間就越長，并且仍然存在冷啟動的問題[2]。

針對這些問題，國內(nèi)外研究者提出了多種解決方案。文獻[3]提出了基于信任的推薦方法，利用用戶明確表達的信任來幫助新用戶的預測，緩解了協(xié)同過濾中的數(shù)據(jù)稀疏和冷啟動問題。文獻[4]通過實驗獲得最佳的平衡因子，用來計算用戶的評分信息，并且融合傳統(tǒng)的余弦相似度算法，一定程度上提高了推薦質(zhì)量。文獻[5]提出基于聚類平滑聯(lián)合來減少數(shù)據(jù)稀疏的不良影響，但是該方法丟失了部分用戶評價的數(shù)據(jù)。文獻[6]將奇異值矩陣分解方法和基于項目的方法進行混合，有效緩解了數(shù)據(jù)稀疏的問題。

最近，一些研究將社交網(wǎng)絡作為附加信息與用戶進行聚類。例如，社會信任關系，首先從信任網(wǎng)絡拓撲中提取信任簇，然后在每個信任簇中找到相似鄰居進行聚類，這樣改善了傳統(tǒng)聚類協(xié)同過濾的性能[7]。但是這類研究沒有考慮不信任的信息，文獻[8]證明了不信任信息對于推薦系統(tǒng)中的預測精度起著重要的作用。另一方面，由于只考慮信任關系的聚類方法，不能處理數(shù)據(jù)稀疏性和冷啟動的問題，使得預測精度和覆蓋率相對較低。

針對上述問題，文中提出了一種基于信任聚類的協(xié)同過濾推薦算法(trust clustering based collaborative filtering recommendation algorithm,TCCF)。該算法加入了不信任信息的處理，使用SVD聚類算法處理信任和不信任關系矩陣，然后對信任度進行建立和度量，并提出了一種稀疏評分補碼算法來生成密集用戶的評分模型，一定程度上緩解了稀疏性問題。

1 相關工作

本節(jié)將介紹傳統(tǒng)的基于信任的推薦系統(tǒng)和基于聚類的推薦系統(tǒng)相關的方法。

1.1 基于信任的推薦系統(tǒng)

基于信任的推薦系統(tǒng)利用用戶明確表達的信任信息來進行預測推薦。基于信任的推薦系統(tǒng)可以分為基于模型和基于內(nèi)存的方法?；谀Ｐ偷男湃瓮扑]系統(tǒng)采用基于模型的協(xié)同過濾方法作為其基本模型，并且廣泛使用矩陣分解技術。文獻[9]將基本矩陣分解方法和基于信任的方法結(jié)合起來，融合了用戶的喜好和他們信任的朋友們的喜好。文獻[10]提出了一種將用戶評級和社會信任評級結(jié)合起來的方法，實驗結(jié)果表明該方法可以有效地提高推薦性能。

基于內(nèi)存的信任推薦系統(tǒng)使用基于內(nèi)存的協(xié)同過濾方法作為它們的基本模型。首先搜索信任網(wǎng)絡，以獲得給定用戶的信任鄰居。其鄰居可以是信任鄰居、相似的鄰居或者是信任鄰居和相似鄰居的組合。例如，在文獻[11]中提出的基于信任的推薦系統(tǒng)體系結(jié)構中，存在一個信任度量模塊和一個相似度度量模塊，可以通過信任度量或相似度度量來生成識別鄰居的權重，以緩解傳統(tǒng)的協(xié)同過濾冷啟動的問題。文獻[12]提出了一種基于信任和基于項目的協(xié)同過濾方法的信任漫步模型，在推薦精度方面優(yōu)于傳統(tǒng)的協(xié)同過濾方法。

1.2 基于聚類的推薦系統(tǒng)

基于聚類的推薦方法根據(jù)用戶-項目評分矩陣將用戶或者項目劃分為不同組。即先計算基于評分的相似度，然后使用特定的聚類算法生成用戶或者物品組。

文獻[8]提出了一種利用聚類算法來減少產(chǎn)品維度的方法。類似的產(chǎn)品被分組在同一個集群中，不同的產(chǎn)品被分派到不同的集群中。實驗結(jié)果表明，在保持一定推薦質(zhì)量的情況下，推薦效率明顯提高。Guo等[13]開發(fā)了一種多視圖聚類方法，主要集中使用評級和新人信息的集群用戶，并使用支持向量回歸模型根據(jù)用戶、項目和預測相關特性來給定項目的預測。在這些方法的啟發(fā)下，文中開發(fā)一種更好的方法來改進基于集群的推薦算法的性能。

2 TCCF推薦算法

2.1 信任社區(qū)挖掘

在網(wǎng)絡社會中，可以將信任分成兩類關系。一類是正相關關系，例如信任和喜歡。一類是負相關關系，例如不信任和討厭。相關網(wǎng)絡挖掘的研究認為，信任網(wǎng)絡通常是由社區(qū)組成。用戶在同一個社區(qū)中有著積極的關系，不同社區(qū)之間存在著消極的關系[14]。在這項研究的啟發(fā)下，文中提出一種基于奇異值分解(SVD)的聚類方法，以進行信任社區(qū)挖掘，根據(jù)用戶對他人的信任和不信任，將其劃分為不同的社區(qū)。

SVD聚類方法是一種源自光譜圖中應用的劃分方法，一般需要聚類特征進行提取和標記，然后對聚類內(nèi)容進行挖掘，最后使用SVD計算最終的聚類信息。初始的SVD方法的輸入是鄰接矩陣A=(aij)x1×x2,它是一個無定向并且為加權的圖G，鄰接矩陣A的元素可以表示為：

(1)

其中,E表示圖G中的邊。

這里使用截斷奇異值分解(truncated singular value decomposition，TSVD)對矩陣進行分解降維。TSVD是一種矩陣因式分解技術，經(jīng)常用在特征提取和病態(tài)問題的解決上，實質(zhì)是一種正則化方法，犧牲部分精度來保證解的穩(wěn)定性，使得結(jié)果具有更高的泛化能力。使用TSVD進行矩陣分解，可以通過它們的信任關系將進行聚類分組。分解后的信任關系矩陣可以表示為：

其中，P、Q和S分別為左奇異矩陣、右奇異矩陣和奇異值矩陣。

信任關系網(wǎng)絡中包含的信任關系和不信任關系可以被認為是一個加權有向圖，僅用式1的鄰接矩陣來發(fā)現(xiàn)信任社區(qū)是不合理的。因此，信任關系矩陣T=(tuv)|U|×|U|定義如下：

(3)

其中,|U|表示信任網(wǎng)絡中的頂點數(shù)，euv是用戶u到v的有向邊。seuv=1表示用戶u信任v，seuv=-1表示用戶u不信任v，否則，他們之間沒有關系，記作0。

文獻[15]將奇異值以降序的方式繪制在線形圖上，而這些值的大小下降最明顯的點總是被視為k的最佳值。因此，P和Q的行可以看作是k維空間中參與者的坐標，并且SVD聚類方法只作用于無向圖，并且使用奇異向量的模式將節(jié)點集中在圖中。文中也使用這種方處理直接信任矩陣T，在k維度上具有相同符號的P行被劃分進同一聚類，也就是說信任網(wǎng)絡中的用戶是通過信任和不信任他人進行聚類的，以此來劃分信任社區(qū)。

2.2 信任度度量

同一聚類分組中，還需要進行信任度的建立與度量。用戶會對同一聚類組中附近的用戶進行相關性檢測，當收到的信息與自己本身的信息大部分相似時，該建議被視為有效建議并且被采納，然后這兩個用戶會進行信任度的建立。這里定義直接信任函數(shù)DT(u,v)，表達式為：

(4)

其中，Iu,v為用戶的公共評價的集合；Cu,v為Iu,v中用戶v為u評分預測偏差較小的項目集合。

如果樣本數(shù)據(jù)過于稀疏，直接信任關系的樣本數(shù)會很少，所以這里還需要定義用戶之間的間接信任度函數(shù)，又稱為推薦信任度，其表達式為：

(5)

其中，Uu,v是與用戶u和v都具有信任度的用戶集合；CT(u,k)是u對k的信任關系度量函數(shù)。

結(jié)合用戶u,v的直接信任度DT(u,v)和推薦信任度IT(u,v)，可以獲得用戶間的最終信任度，表達式為：

ZT(u,v)=λ×DT(u,v)+(1-λ)×IT(u,v)

(6)

其中，λ為協(xié)調(diào)因子，取值范圍為[0,1]。不同的λ值會對最終信任度有不同的影響，需要手動進行調(diào)整，以得出最合適的協(xié)調(diào)因子。

2.3 稀疏評分填充算法

傳統(tǒng)的基于聚類的推薦方法傾向于簡單地在每個信任社區(qū)中執(zhí)行基于內(nèi)存的協(xié)同過濾方法來進行推薦。但是，在每個檢測到的信任社區(qū)中，數(shù)據(jù)稀疏問題仍然非常嚴重，可能會降低推薦的性能。為了解決這個問題，提出了稀疏評分填充算法，通過利用來自同一個信任社區(qū)的信任鄰居的評級信息為目標用戶生成密集的評級信息，這將有效緩解數(shù)據(jù)的稀疏性和冷啟動問題。具體步驟為:

(1)每個信任組選取一定數(shù)目信任度比較高的用戶建立信任鄰居集合Trustu，這也是比較重要的一步。由于大部分情況下數(shù)據(jù)矩陣是很稀疏的，這里可以認為高信任度鄰居的信任鄰居也是值得信任的，這樣做也符合信任網(wǎng)絡傳遞的原則。在理論上，這個可以無限地傳遞下去，但是信任的評級會逐級遞減，當傳遞層級較高時，雖然預填充效果即覆蓋率較為理想，但是準確率會下降很多。所以，TCCF算法將采用兩級信任傳遞原則，表達式為：

T(u,w)=T(u,v)×T(v,w)

(7)

其中，u為最終目標用戶；w為通過信任傳遞后的用戶。

(2)根據(jù)集合Trustu中用戶的評分，對目標用戶未評分的項目利用預測函數(shù)進行評分預測。通常的預測函數(shù)有權重函數(shù)、修正的權重函數(shù)和均值函數(shù)等，表達式為：

(8)

(3)重復進行步驟1和步驟2，直到用戶對所有未評分項目的評分預測完畢，并填入相應的信任組位置中，完成稀疏評分填充。

3 實 驗

3.1 數(shù)據(jù)集及預處理

為了檢驗基于信任聚類的協(xié)同過濾算法與傳統(tǒng)的協(xié)同過濾推薦質(zhì)量的差別，并且為了避免單一數(shù)據(jù)集出現(xiàn)過擬合化的問題，實驗使用在線視頻提供商Netflix提供的Netflix評分數(shù)據(jù)集和明尼蘇達大學GroupLens實驗小組提供的MoiveLens數(shù)據(jù)集。由于Netflix數(shù)據(jù)集樣本數(shù)量過于龐大，這里抽取大約為MoiveLens數(shù)據(jù)集兩倍的樣本數(shù)進行實驗。這些數(shù)據(jù)集包含用戶對所看電影的真實評分，數(shù)據(jù)集如表1所示。

表1 實驗數(shù)據(jù)集

實驗將2個數(shù)據(jù)集的用戶-項目評分數(shù)據(jù)按照80%和20%的比例分為兩部分，前者作為訓練集使用，用來構造推薦模型，后者作為測試集使用，這樣可以保證訓練數(shù)據(jù)與測試數(shù)據(jù)都是隨機的且都來自同一數(shù)據(jù)集。對于近鄰數(shù)量的設置，考慮Netflix數(shù)據(jù)集樣本數(shù)較多，這里設置MovieLens數(shù)據(jù)集近鄰數(shù)量從5取到30，間隔為5；Netflix數(shù)據(jù)集近鄰數(shù)量從10取到60，間隔為10。

3.2 評價標準

使用平均絕對誤差(MAE)作為評價標準，MAE主要用來評估推薦算法預測的資源評分與用戶實際對資源評分的偏差程度。一般MAE值越小，推薦模型的準確率就越高，其計算公式為：

(9)

其中，測試數(shù)據(jù)集中的項目預測評分集合為{P1,P2,…,Pt}，Pi為其中一個預測評分，ri為對應的實際項目評分。

另外使用準確率(precision)和召回率(recall)作為評價標準，它們一般用來衡量推薦算法返回的推薦列表的效果，其公式計算如下：

(10)

(11)

其中，U是用戶集；R(u)是對用戶的推薦列表；T(u)是用戶在測試集中的行為列表。

雖然希望檢索結(jié)果的準確率和召回率越高越好，但事實上這兩者在某些情況下是互相矛盾的，一般隨著準確率的增加，召回率在下降，反之亦然。所以這里綜合兩者的評價指標，引入Fusion值[12]進行衡量，一般Fusion值越高，表示推薦的綜合性能越好，其公式計算如下：

(12)

3.3 實驗結(jié)果及分析

本次實驗將傳統(tǒng)的基于用戶的協(xié)同過濾(UBCF)[16]、基于K-means聚類的協(xié)同過濾(KCCF)[17]與提出的TCCF算法在不同鄰居數(shù)下進行對比實驗，以檢驗不同協(xié)同過濾推薦模型的質(zhì)量。實驗以MAE和Fusion作為評估標準，并且基于Netflix和MovieLens數(shù)據(jù)進行。

3.3.1 近鄰數(shù)對預測準確性的影響

如圖1和圖2所示，無論是MovieLens數(shù)據(jù)集還是Netflix數(shù)據(jù)集，TCCF算法的平均絕對誤差均低于傳統(tǒng)的UBCF算法和基于聚類的KCCF算法，其中傳統(tǒng)的UBCF算法表現(xiàn)略差。當近鄰數(shù)量較少時，TCCF算法明顯較UBCF算法和KCCF算法的MAE更低，這是因為在KCCF算法中對稀疏評分矩陣進行預填充，即使是近鄰數(shù)較少，也會保證一定的推薦質(zhì)量。在圖1中，隨著近鄰數(shù)量的增加，當近鄰數(shù)為15時，三種算法的MAE都趨于穩(wěn)定；在圖2中，當近鄰數(shù)量為50時，MAE趨于穩(wěn)定，即不同數(shù)據(jù)集的最適合的近鄰數(shù)量是不同的。在MovieLens數(shù)據(jù)集中，文中算法的MAE較其他算法平均降低6.2%；在Netflix數(shù)據(jù)集中，MAE平均降低5.4%，提高了預測的準確性。

圖1 MovieLens數(shù)據(jù)集的平均絕對誤差

圖2 Netflix數(shù)據(jù)集的平均絕對誤差

3.3.2 推薦數(shù)量對推薦結(jié)果的影響

如圖3和圖4所示，F(xiàn)usion值都隨著推薦個數(shù)的增加而降低，即隨著推薦個數(shù)增加時，綜合的推薦性能在下降。但無論是MovieLens數(shù)據(jù)集還是Netflix數(shù)據(jù)集，TCCF算法的Fusion值都比另外兩種算法的Fusion值要高，即準確率和召回率的平均水平都要優(yōu)于UBCF和KCCF算法，一定程度上提高了推薦質(zhì)量。另外值得注意的是，在Netflix數(shù)據(jù)集中，F(xiàn)usion值改進較大，這是由于文中稀疏評分填充算法在樣本數(shù)較多且稀疏的情況下，有更好的提升效果，傳統(tǒng)的UBCF和KCCF算法表現(xiàn)就略差一些。

圖3 MovieLens數(shù)據(jù)集的Fusion值

圖4 Netflix數(shù)據(jù)集的Fusion值

4 結(jié)束語

文中提出了一種基于信任聚類的協(xié)同過濾推薦算法。首先提出了基于SVD聚類方法來對信任與不信任關系進行處理，以發(fā)現(xiàn)信任社區(qū)。隨后提出稀疏評分填充算法，以預測缺失的評分。實驗結(jié)果表明，該算法在覆蓋率以及推薦質(zhì)量上都優(yōu)于傳統(tǒng)的協(xié)同過濾方法。今后將嘗試找到更加優(yōu)化的信任度量標準，并且應用在不同數(shù)據(jù)集上以進一步驗證該算法的有效性。