摘要：協(xié)同過(guò)濾技術(shù)在面臨評(píng)分?jǐn)?shù)據(jù)稀疏性問(wèn)題時(shí)，推薦效果較差。為了提高推薦系統(tǒng)的推薦精度，可以將用戶在社會(huì)網(wǎng)絡(luò)中的交互信息加入到推薦系統(tǒng)中來(lái)，彌補(bǔ)評(píng)分?jǐn)?shù)據(jù)不足的問(wèn)題。在本文中，提出一種基于混合信任模型的協(xié)同過(guò)濾推薦算法，該算法將用戶在社會(huì)網(wǎng)絡(luò)中的歷史評(píng)級(jí)信息和交互頻率合并計(jì)算用戶之間的直接信任度，并通過(guò)一定的信任傳遞規(guī)則將沒(méi)有直接關(guān)聯(lián)的用戶間的間接信任度也計(jì)算出來(lái)，組成稠密的用戶信任矩陣。最后基于用戶信任矩陣和用戶評(píng)分矩陣共同來(lái)計(jì)算用戶之間的相似度并預(yù)測(cè)目標(biāo)用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分，得到推薦集。實(shí)驗(yàn)結(jié)果表明本文提出算法可以提高數(shù)據(jù)密度，改善協(xié)同過(guò)濾推薦技術(shù)的稀疏性問(wèn)題，有效提高推薦精度。

關(guān)鍵詞：協(xié)同過(guò)濾；信任模型；基于信任的推薦算法；相似度；社會(huì)網(wǎng)路

中圖分類號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）20-0257-04

Abstract： In the face of rating data's sparsity problem， the recommendation effect of collaborative filtering technology is not so good. In order to improve the accuracy of recommendation system， we can add the interaction with the user information in social networks into the recommended system， in order to make up for the shortage of data rates. In this paper， we set up a hybrid trust model based on collaborative filtering algorithm， which combine the user rating information and interaction frequency in a social network， and calculate direct-trust-relationship between users. Following， the indirect-trust-relationship is also calculated by using some certain trust rules， and at last it forms a dense matrix of user trust. Finally， we calculate the similarity between users and predict the target ratings based on user-trust-matrix and user-scoring-matrix and get recommended set. Experimental results show that the proposed algorithm can increase data density， improve the sparsity problem of collaborative filtering technology and effectively improve the recommendation accuracy.

Key words：Collaborative filtering； Trust model； Trust-based recommender algorithm； Similarity；Social networks

1 引言

一個(gè)社交網(wǎng)站，比如臉譜網(wǎng)、微博，已經(jīng)成為互聯(lián)網(wǎng)用戶不可或缺的一部分。信息技術(shù)和互聯(lián)網(wǎng)技術(shù)的普及和迅猛的發(fā)展，加劇了信息過(guò)載問(wèn)題，增加了用戶獲得有用信息的成本。推薦系統(tǒng)作為一種過(guò)濾技術(shù)，可以有效緩解信息過(guò)載問(wèn)題，為用戶提供優(yōu)質(zhì)的個(gè)性化服務(wù)[1]。在傳統(tǒng)的個(gè)性化推薦算法中，協(xié)同過(guò)濾算法無(wú)疑是最成功的一種算法。協(xié)同過(guò)濾推薦算法是基于某些特定項(xiàng)目的用戶之間的相似性偏好來(lái)預(yù)測(cè)推薦結(jié)果的。更一般而言，如果他們?cè)谀承╉?xiàng)目上有類似的利益，他們最有可能對(duì)一些其他項(xiàng)目感興趣?；趨f(xié)同過(guò)濾的方法首先基于項(xiàng)目或基于用戶的相似性度量計(jì)算發(fā)現(xiàn)鄰居項(xiàng)目或鄰居用戶，然后通過(guò)相似性的鄰居的歷史偏好來(lái)預(yù)測(cè)目標(biāo)用戶的偏好。雖然協(xié)同過(guò)濾是有效的，但當(dāng)評(píng)分?jǐn)?shù)據(jù)稀疏，用戶沒(méi)有足夠的歷史評(píng)級(jí)數(shù)據(jù)來(lái)支撐相似性計(jì)算時(shí)，推薦效果表現(xiàn)不佳。此外，基于協(xié)同過(guò)濾的推薦系統(tǒng)忽略了用戶之間的社會(huì)關(guān)系或信任關(guān)系，很多研究者也考慮利用社會(huì)網(wǎng)絡(luò)關(guān)系信息來(lái)提高協(xié)同過(guò)濾推薦系統(tǒng)性能。

基于信任的推薦系統(tǒng)試圖通過(guò)引入信任度量解決數(shù)據(jù)稀疏性問(wèn)題，采用用戶項(xiàng)目評(píng)分信息和用戶社會(huì)信任網(wǎng)絡(luò)信息來(lái)共同計(jì)算相似度[2]。如果兩個(gè)用戶有非常少的共同評(píng)分項(xiàng)目，只從他們的共同額定項(xiàng)目的評(píng)級(jí)信息計(jì)算的信任值可能會(huì)產(chǎn)生誤導(dǎo)性的信任。雖然傳統(tǒng)的基于信任的比照系統(tǒng)已經(jīng)提出了基于評(píng)級(jí)的信任模型，或明確指定的信任指標(biāo)，以獲得用戶的可信性，由于用戶間共同評(píng)分?jǐn)?shù)據(jù)的極度稀疏性，造成信任值度量的誤差很大，對(duì)推薦系統(tǒng)精度的改良意義不大。所以本文提出一個(gè)新的混合信任度量模型，利用用戶的歷史評(píng)分?jǐn)?shù)據(jù)和用戶在社會(huì)網(wǎng)絡(luò)中的互動(dòng)交互頻率來(lái)共同計(jì)算直接信任值，再通過(guò)一定的信任傳遞規(guī)則來(lái)計(jì)算沒(méi)有直接聯(lián)系和沒(méi)有共同評(píng)分項(xiàng)目的用戶之間的間接信任值，合并得到用戶信任矩陣。最后基于信任矩陣和用戶評(píng)分矩陣來(lái)共同預(yù)測(cè)評(píng)分，得到推薦結(jié)果。

2 傳統(tǒng)協(xié)同過(guò)濾方法

2.1 傳統(tǒng)相似性計(jì)算方法

協(xié)同過(guò)濾推薦的關(guān)鍵點(diǎn)是不同用戶之間的相似性度量。廣泛采用的方法是基于用戶的共同歷史評(píng)分?jǐn)?shù)據(jù)項(xiàng)量來(lái)進(jìn)行相似度的計(jì)算。在相似性計(jì)算方法中，雖然各有其優(yōu)缺點(diǎn)，但最常用的相似性度量方法是余弦相似性、修正的余弦相似性和皮爾森相似性[3]。

2.2 基于信任的協(xié)同過(guò)濾算法

信任被定義為一個(gè)用戶對(duì)另一個(gè)用戶可靠性的主觀信念。信任可以分為直接信任和間接信任，直接信任是用戶間直接交互作用而建立的信任，而間接信任是一個(gè)用戶通過(guò)信任傳播的方式和別的沒(méi)有直接聯(lián)系的用戶間的信任關(guān)系。假設(shè)信任度量的目的是量化用戶之間的信任程度，如果信任關(guān)系沒(méi)有明確表示，可以從評(píng)級(jí)數(shù)據(jù)或其他間接信息中推斷出來(lái)。此外，許多研究人員將信任引入到基于用戶的協(xié)同過(guò)濾的推薦中，并提出了許多信任模型。例如，從邏輯的角度研究用戶之間的信任關(guān)系，Pitsilis提出了一種基于不確定概率理論的信任模型[6]。然而，由于不確定性是由用戶的平均評(píng)分計(jì)算得到，而評(píng)分矩陣的稀疏性導(dǎo)致信任模型的準(zhǔn)確性是有限的。Kwon等人研究了一種多維信任模型來(lái)測(cè)量用戶間相似度，然后計(jì)算一個(gè)加權(quán)匯總選擇鄰居[7]。然而，盡管該模型在選擇鄰居的過(guò)程中有更多的多樣性，但它仍然缺乏抵抗攻擊的能力。為此，本文針對(duì)上述問(wèn)題，在前人的研究基礎(chǔ)上提出了一種改進(jìn)的基于信任的協(xié)同過(guò)濾推薦算法，探討了一種計(jì)算用戶間信任度的新思路，然后將信任度和相似度按照一定原則組合，根據(jù)組合的相似度來(lái)搜索最佳鄰居得到推薦。

3 基于混合信任模型的協(xié)同過(guò)濾推薦算法

本文提出的改進(jìn)的基于信任的協(xié)同過(guò)濾算法將用戶評(píng)分矩陣和用戶之間的交互信息作為輸入并計(jì)算用戶間之間信任值，再基于一種信任傳遞規(guī)則來(lái)計(jì)算用戶間接信任值。將直接信任值和間接信任值組合成為較稠密的信任矩陣。信任矩陣和評(píng)價(jià)矩陣被共同用來(lái)尋找目標(biāo)用戶的K近鄰，并計(jì)算目標(biāo)用戶對(duì)未評(píng)分項(xiàng)目的預(yù)測(cè)評(píng)分，最后選擇預(yù)測(cè)評(píng)分較高的項(xiàng)目作為推薦列表反饋給目標(biāo)用戶。

3.1 直接信任度量

信任權(quán)重是用戶對(duì)另一個(gè)用戶信賴程度的量化，信賴程度越高，其權(quán)重越大。但許多網(wǎng)站并沒(méi)有提供用戶表達(dá)的直接信任權(quán)重。因此，本文使用用戶的評(píng)級(jí)項(xiàng)目和用戶的互動(dòng)來(lái)計(jì)算用戶之間的直接信任值。用戶之間交互頻率越高，他們之間的相互作用就越強(qiáng)，用戶的行為也更容易受到他們信任的朋友的影響，所以接下來(lái)我們定義了一個(gè)直接的信任度的度量方法。

（1）基于歷史評(píng)分等級(jí)的直接信任度量

基于歷史評(píng)分等級(jí)的直接信任度量主要是通過(guò)用戶-項(xiàng)評(píng)分矩陣中用戶對(duì)項(xiàng)目的評(píng)分?jǐn)?shù)據(jù)來(lái)進(jìn)行的，比如用一個(gè)用戶對(duì)某一項(xiàng)目的評(píng)分去預(yù)測(cè)另一個(gè)用戶的對(duì)該項(xiàng)目的評(píng)分，若預(yù)測(cè)評(píng)分與該用戶實(shí)際對(duì)該項(xiàng)目的評(píng)分差異較小，我們認(rèn)為這個(gè)用戶推薦人是更可靠的，他們之間的直接信任值便相對(duì)較高。參考傳統(tǒng)的信任計(jì)算模型，我們可使用雷斯尼克的預(yù)測(cè)公式來(lái)計(jì)算出依賴于用戶得到目標(biāo)用戶的預(yù)測(cè)評(píng)分，計(jì)算方法定義如下：

3.2 間接信任度量

在現(xiàn)實(shí)生活中，人們不僅信任自己的朋友，還可以與朋友的朋友建立新的信任關(guān)系，這就是信任的傳遞規(guī)則。如果用戶A信任用戶B，用戶B的信任用戶C，雖然用戶A，C之間沒(méi)有直接信任關(guān)系，但通過(guò)用戶B，用戶A，C之間便可以找到一種可達(dá)的信任關(guān)系，也就是說(shuō)信任是可以繁殖傳播的。在本文中，我們將使用此功能擴(kuò)展本地信任網(wǎng)絡(luò)。類似地，我們可以在網(wǎng)絡(luò)中獲得這種間接信任關(guān)系。

在一段時(shí)間內(nèi)，用戶與用戶之間沒(méi)有任何交互聯(lián)系，也沒(méi)有一個(gè)共同的歷史評(píng)分項(xiàng)目，也就是說(shuō)，沒(méi)有直接的信任關(guān)系。若用戶和用戶之間存在信任連通路徑，如，其中都是該可達(dá)路徑上的中間用戶，則用戶和用戶之間可能存在間接信任關(guān)系。用戶對(duì)用戶的間接信任值定義如下：

在這里，表示用戶和用戶之間的可到達(dá)路徑的長(zhǎng)度。

根據(jù)上述方法，可以計(jì)算出所有用戶之間的信任值，并可以形成一個(gè)關(guān)于所有用戶之間的信任度矩陣，后面用到的信任相似度便是矩陣中用戶所在行向量中各元素取值。

3.3 組合信任值的相似度計(jì)算

在上節(jié)中，通過(guò)計(jì)算用戶之間的信任關(guān)系，反映了互動(dòng)效應(yīng)。因此，用戶之間的信任度越高，它們之間的相互作用越大，就越相似。信任關(guān)系在一定程度上也反映了用戶之間的相似性，因此本文提出的基于信任的協(xié)同過(guò)濾方法是用戶信任矩陣中的信任值和用戶評(píng)分相似性按照一定方式進(jìn)行組合，組合后的權(quán)重作為新的相似度參與目標(biāo)用戶對(duì)未評(píng)分項(xiàng)目的預(yù)測(cè)評(píng)分?；谌缟戏治?，我們提出了一種新的用戶評(píng)分相似度和用戶信任關(guān)系的評(píng)價(jià)方法，在最近鄰對(duì)象的選擇上，我們需要確定如何選擇推薦對(duì)象的預(yù)測(cè)目標(biāo)。通過(guò)定義兩個(gè)相似度閾值，即用戶的評(píng)分相似度閥值和用戶信任度閥值。同時(shí)我們定義評(píng)分相似度大于相似度閥值的用戶集合為評(píng)分相似鄰居集記為，信任度大于用戶信任度閥值的用戶集合為信任鄰居集記為，后續(xù)會(huì)合并評(píng)分相似度鄰居集和信任鄰居集來(lái)為目標(biāo)用戶作推薦。為評(píng)分相似度和信任度組合的權(quán)重因子，的最優(yōu)取值問(wèn)題會(huì)在后續(xù)實(shí)驗(yàn)中進(jìn)行討論。

最終的推薦相似度可以組合計(jì)算如下：

3.4 最終的預(yù)測(cè)評(píng)分值計(jì)算

在獲得直接信任值和間接信任值后，本文提出方法通過(guò)目標(biāo)用戶的評(píng)分相似度鄰居集合和信任鄰居集合的并集記為來(lái)對(duì)目標(biāo)用戶未評(píng)分的所有項(xiàng)目進(jìn)行預(yù)測(cè)評(píng)分。最后選擇預(yù)測(cè)評(píng)分值較高的項(xiàng)目作為推薦結(jié)果反饋給目標(biāo)用戶。

4 實(shí)驗(yàn)結(jié)果

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

為了驗(yàn)證本文新提出的推薦算法比傳統(tǒng)的協(xié)同過(guò)濾算法具有更好的性能，我們收集了MovieLens站點(diǎn)的相關(guān)數(shù)據(jù)集來(lái)完成相應(yīng)實(shí)驗(yàn)。MovieLens數(shù)據(jù)集是最常用來(lái)測(cè)試推薦算法性能的標(biāo)準(zhǔn)數(shù)據(jù)集。此數(shù)據(jù)集包含100000個(gè)等級(jí)從1到5的評(píng)價(jià)數(shù)值，由943名用戶對(duì)1682部電影的評(píng)價(jià)。在這個(gè)數(shù)據(jù)集中，用戶被要求至少對(duì)20部電影進(jìn)行評(píng)分，數(shù)據(jù)稀疏率是95%左右。在實(shí)驗(yàn)中數(shù)據(jù)集被分為訓(xùn)練和測(cè)試部分（80%用于訓(xùn)練測(cè)和20%用于測(cè)試集）。

4.2 結(jié)果分析

1）實(shí)驗(yàn)1：通過(guò)調(diào)節(jié)評(píng)分相似度和信任度組合的權(quán)重因子來(lái)對(duì)比推薦精度MAE的值

在本實(shí)驗(yàn)中我們將測(cè)試參數(shù)取不同值對(duì)推薦精度MAE值的影響?！蔥0，1]，的值從0開始，每次增加0.1，縱坐標(biāo)為推薦精度MAE的值，觀察縱坐標(biāo)MAE值的變化，并將本文提出算法和“基于用戶的CF” 以及“基于信任的CF”作對(duì)比，發(fā)現(xiàn)當(dāng)參數(shù)取值為0.6時(shí)推薦效果最佳。

2）實(shí)驗(yàn)2：本文算法與其他協(xié)同過(guò)濾推薦算法的比較

本實(shí)驗(yàn)的目的是將本文提出算法與傳統(tǒng)的協(xié)同過(guò)濾算法以及近期業(yè)界比較領(lǐng)先的研究方法EMDP（Effective Missing Data Prediction）進(jìn)行比較。我們使用相同的實(shí)驗(yàn)數(shù)據(jù)，比較了該算法與傳統(tǒng)的協(xié)同過(guò)濾算法，如基于項(xiàng)目的CF”，“基于用戶的CF”，“基于信任的CF”以及文獻(xiàn)[5]中提出的EMDP算法在推薦精度方面的差異。在這個(gè)實(shí)驗(yàn)中，取值為0.6，和“最近鄰數(shù)數(shù)目”取值范圍為[10，60]，每次增加5個(gè)鄰居。實(shí)驗(yàn)結(jié)果如圖2所示。實(shí)驗(yàn)結(jié)果表明，本文提出的方法可以得到較低的MAE值，因此推薦效果更好，隨著產(chǎn)品最近鄰居數(shù)目的增加，預(yù)測(cè)的質(zhì)量也在不斷提升。

5 結(jié)論

協(xié)同過(guò)濾是目前推薦系統(tǒng)所使用的主流技術(shù)，但用戶項(xiàng)評(píng)分矩陣的稀疏性問(wèn)題是協(xié)同過(guò)濾技術(shù)的主要限制之一。為了解決稀疏性問(wèn)題，本文提出了一種改進(jìn)的基于信任的協(xié)同過(guò)濾推薦算法。該算法使用用戶的評(píng)級(jí)數(shù)據(jù)和交互信息作為推斷，產(chǎn)生一個(gè)信任矩陣，代表用戶之間的信任值，然后將信任值是用來(lái)糾正傳統(tǒng)相似性計(jì)算并以此來(lái)尋找最近鄰居用戶得到未評(píng)分項(xiàng)目的預(yù)測(cè)評(píng)分。由于本文提出的改進(jìn)算法能搜索到更優(yōu)的鄰居用戶，所以使得推薦算法的推薦精度有較大提升。實(shí)驗(yàn)結(jié)果表明，該算法優(yōu)于最近鄰協(xié)同過(guò)濾的預(yù)測(cè)質(zhì)量。與傳統(tǒng)的基于項(xiàng)目的協(xié)同過(guò)濾算法、基于用戶的協(xié)同過(guò)濾算法、基于上下文的協(xié)同過(guò)濾算法、基于信任的協(xié)同過(guò)濾算法以及目前業(yè)界比較先進(jìn)的EMDP算法在推薦精度方面作了對(duì)比，推薦性能較好，能很好緩解數(shù)據(jù)稀疏性問(wèn)題對(duì)推薦精度的影響。由于要計(jì)算用戶之間的信任度，會(huì)增加推薦系統(tǒng)的時(shí)間開銷，不過(guò)可以將信任度的計(jì)算離線進(jìn)行，減少對(duì)系統(tǒng)響應(yīng)時(shí)間的影響。未來(lái)的研究，以提高該算法的時(shí)間性能以及提高算法的抗惡意攻擊能力等。

參考文獻(xiàn)：

[1] 彭玉，程小平. 基于屬性相似性的Item-based協(xié)同過(guò)濾算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（14），144-147.

[2] 李湛，吳江寧.基于用戶行為特征分析的隱形信任協(xié)同過(guò)濾推薦方法[J].情報(bào)學(xué)報(bào)，2013，28（5），490-496.

[3] 鄧愛(ài)林.電子商務(wù)推薦系統(tǒng)關(guān)鍵技術(shù)研究|D|.上海：復(fù)旦大學(xué).2003

[4] Herlocker J. Konstan J A， Riedl J. An empirical analysis of design choices in neighborhood-based collaborative filtering algorithms[J]. Information Retrieval， 2002， 5（4）： 287-310.

[5] Ma H， King 1， Lyu M R. Effective missing data prediction for collaborative filtering// Proceedings of the 30th Annual International ACM SIGIR Conference[C]. Amsterdam， The Netherlands， 2007： 39-46.

[6] Pitsilis， Georgios， and Lindsay Forsyth Marshall.A model of trust derivation from evidence for use in recommendation system[D].University of Newcastle upon Tyne， Computing Science， 2004.

[7] K. Kwon， J. Cho and Y. Park. Multidimensional credibility model for neighbor selection in collaborative recommendation[J]. Expert System with Applications， 2009，36（3）：7114-7122.