鄭 鵬, 王應(yīng)明

(福州大學(xué) 經(jīng)濟(jì)與管理學(xué)院,福州 350108)

引言

互聯(lián)網(wǎng)的高速發(fā)展以及電子商務(wù)的迅速崛起,有力地促進(jìn)了推薦系統(tǒng)的研究發(fā)展. 其中,協(xié)同過(guò)濾(Collaborative Filtering,CF)推薦算法是推薦系統(tǒng)中應(yīng)用最廣泛、最成功的推薦技術(shù)之一[1]. 雖然協(xié)同過(guò)濾推薦算法取得了一些成果,但是它同時(shí)也存在數(shù)據(jù)稀疏性、冷啟動(dòng)和擴(kuò)展性等一系列問(wèn)題[2].

現(xiàn)實(shí)生活中,人們更愿意相信好友推薦的物品,因此推薦系統(tǒng)如果結(jié)合用戶的信任關(guān)系信息,則能夠進(jìn)一步提高推薦精度. 隨著在線社會(huì)網(wǎng)絡(luò)的普及,利用社會(huì)網(wǎng)絡(luò)中用戶之間的信任關(guān)系來(lái)緩解傳統(tǒng)協(xié)同推薦存在問(wèn)題的信任感知推薦系統(tǒng)(TARS)成為推薦領(lǐng)域新的研究熱點(diǎn)[3-5]. Massa等[6]提出使用信任度取代相似度的TARS系統(tǒng),根據(jù)信任網(wǎng)絡(luò)傳播來(lái)估計(jì)一個(gè)信任度的權(quán)值,該方法增加了覆蓋范圍(可預(yù)測(cè)的評(píng)分總數(shù)),并未降低精確度(預(yù)測(cè)誤差),但需要用戶的顯式信任聲明. Yuan等[7]根據(jù)隱含信任網(wǎng)絡(luò)的小世界特性,提出一種基于用戶相似度的隱含信任感知推薦系統(tǒng)(ITARS),該方法雖然不需要用戶提前對(duì)自己在整個(gè)信任網(wǎng)絡(luò)中的信任關(guān)系做出聲明,但是該方法需要根據(jù)用戶之間的相似度構(gòu)建隱含的信任網(wǎng)絡(luò),并估算信任網(wǎng)絡(luò)的平均路徑長(zhǎng)度. 郭艷紅等[8]提出以用戶的評(píng)價(jià)個(gè)數(shù)和為他人提供推薦的次數(shù)為要素的可計(jì)算的信任模型推薦算法. 該算法改變傳統(tǒng)推薦過(guò)程中,用戶之間的相似度唯一決定預(yù)測(cè)結(jié)果的現(xiàn)狀,提高了推薦的精度,但該算法無(wú)法對(duì)沒有鄰居的用戶做出推薦. 杜永萍等[9]在傳統(tǒng)基于用戶的協(xié)同過(guò)濾推薦算法的基礎(chǔ)上,引入信任關(guān)系計(jì)算,設(shè)計(jì)并構(gòu)建一個(gè)集用戶聲望信任和用戶局部信任的混和信任網(wǎng)絡(luò),實(shí)現(xiàn)了對(duì)協(xié)同過(guò)濾推薦算法稀疏性問(wèn)題的優(yōu)化,但該方法未考慮用戶的全局信任值. 張俊等[10]提出一種融合用戶興趣相似性和評(píng)分相似性的協(xié)同過(guò)濾推薦算法,該算法引入興趣度進(jìn)行相似度計(jì)算,并通過(guò)引入專家信任度的概念對(duì)用戶未評(píng)分項(xiàng)目進(jìn)行評(píng)分預(yù)測(cè)填充,但該算法需要進(jìn)行惡意用戶檢測(cè),算法復(fù)雜度較大. 楊秀梅等[11]提出融合用戶信任模型的協(xié)同過(guò)濾推薦算法,該算法考慮用戶評(píng)分相似性和用戶之間信任關(guān)系對(duì)推薦結(jié)果的影響,利用層次分析法實(shí)現(xiàn)用戶信任模型的構(gòu)建. 但該算法在計(jì)算用戶信任度過(guò)程中引入信息過(guò)少,導(dǎo)致用戶信任模型過(guò)于簡(jiǎn)單. 陳婷等[12]提出一種可信推薦模型(Trust-PMF),該算法首先結(jié)合全局信任和局部信任,利用信任的傳播性質(zhì)對(duì)信任關(guān)系進(jìn)行建模. 然后,設(shè)置推薦權(quán)重,綜合考慮相似度和信任度來(lái)構(gòu)建用戶間的偏好關(guān)系,篩選出鄰居. 最后,將基于記憶的協(xié)同過(guò)濾思想和社交網(wǎng)絡(luò)的信任關(guān)系融入概率矩陣分解模型,但該算法同樣需要用戶提供信任聲明. 王瑞琴等[13]提出一種基于多元社交信任的協(xié)同過(guò)濾推薦算法,該算法借鑒社會(huì)心理學(xué)中的信任產(chǎn)生原理,提出基于多個(gè)信任要素的信任度計(jì)算方法,基于用戶間的綜合信任度選取可信鄰居,完成對(duì)目標(biāo)用戶的個(gè)性化推薦,但該算法的時(shí)間復(fù)雜度較高. 針對(duì)上述問(wèn)題,本文提出一種基于增強(qiáng)相似度和隱含信任的協(xié)同過(guò)濾算法(ETCF),在考慮用戶興趣度的同時(shí),不需要用戶提供顯式聲明,該算法不僅提高了推薦準(zhǔn)確度和覆蓋率,而且彌補(bǔ)了傳統(tǒng)算法的不足,有效緩解了數(shù)據(jù)稀疏性問(wèn)題.

1 基于增強(qiáng)相似度和隱含信任的協(xié)同過(guò)濾推薦算法

協(xié)同過(guò)濾算法的關(guān)鍵在于用戶之間的相似度測(cè)量,但是由于數(shù)據(jù)稀疏性問(wèn)題的存在,使得傳統(tǒng)的相似度測(cè)量方法都存在著缺陷. 本文的基本思路是將傳統(tǒng)的相似度度量方法和信任結(jié)合,采用增強(qiáng)的用戶相似度和隱含信任來(lái)計(jì)算用戶之間的相似度.

1.1 增強(qiáng)的用戶相似度

計(jì)算用戶相似度的方法有很多,比較傳統(tǒng)的方法有皮爾遜相關(guān)(PCC)、受約束的皮爾遜相關(guān)(CPC)、均方偏差(MSD)和Jaccard相似度. 本文使用均方偏差和Jaccard相似度進(jìn)行用戶相似度的度量.

均方偏差(MSD)的公式如下：

JMSD相比傳統(tǒng)的皮爾遜相關(guān)系數(shù)(PCC)、余弦相似(Cosine)、調(diào)整的余弦相似度(Adjusted Cosine)具有明顯的優(yōu)勢(shì),但是還是存在著一個(gè)問(wèn)題,那就是沒有考慮用戶的評(píng)分偏好. 假如現(xiàn)在有三個(gè)用戶,他們對(duì)四項(xiàng)物品的評(píng)分值分別為U1(4,3,3,4),U2(2,1,-,-),U3(4,2,-,-),這時(shí)候使用JSMD計(jì)算出的相似度,用戶U1和U3的相似度小于U2和U3的相似度,這顯然不符合實(shí)際情況,主要的原因就是沒有考慮用戶的評(píng)分偏好問(wèn)題. 有的用戶喜歡打高分,有的用戶喜歡打低分. 考慮到這個(gè)問(wèn)題,本文引入了一種偏好相似度,其公式為：

基于以上的情況,本文提出一種新的基于用戶的相似性度量方法,公式如下：

1.2 隱含信任

在實(shí)際的數(shù)據(jù)集中兩個(gè)用戶之間可能不存在共同評(píng)分的項(xiàng)目,這種情況下使用傳統(tǒng)的相似性度量方法顯然不可行,本文引入信任機(jī)制來(lái)解決用戶之間沒有共同評(píng)分項(xiàng)的問(wèn)題.

1.2.1 信任機(jī)制

信任在人們的日常生活中占據(jù)著舉足輕重的地位,但它是一個(gè)相對(duì)模糊的概念,涉及到的方面很多,以至于至今都未能給出一個(gè)令人信服的定義. 雖然信任的定義難以確定,但目前信任有一些公認(rèn)的特性,包括主觀性、不對(duì)稱性、傳遞性、動(dòng)態(tài)性等,這些屬性彼此之間是相互關(guān)聯(lián)的,所以它們之間出現(xiàn)交叉或沖突等情況是正?，F(xiàn)象

下文將給出本文對(duì)信任的定義.

定義1. 信任是指接受推薦者對(duì)提供推薦者特定行為的主觀可能性預(yù)測(cè),它是一種單向、相對(duì)、局限在一定范圍內(nèi)的主觀反映.

定義2. 直接信任是指兩個(gè)用戶根據(jù)曾經(jīng)直接交往的經(jīng)驗(yàn)建立的信任關(guān)系.

定義3. 間接信任是指兩個(gè)用戶通過(guò)第三方的推薦建立的信任關(guān)系.

定義4. 信任度是根據(jù)用戶所處的情境以及信任的屬性,量化用戶間信任程度后的信任值.

1.2.2 用戶之間的直接信任

直接信任度來(lái)源于兩個(gè)用戶曾經(jīng)交互的經(jīng)驗(yàn)積累,本文的直接信任度通過(guò)活動(dòng)用戶相似度來(lái)度量,例如,如果用戶a和用戶b的相似度比較大,那么我們可以認(rèn)為二者屬于同一類,是可以相互信任的. 對(duì)用戶的信任推導(dǎo),我們使用JMSD,也就是說(shuō)用戶之間的直接信任度：

從中可以很容易的看出如果兩個(gè)用戶之間的共同評(píng)分項(xiàng)非空,二者之間的直接信任度非零,否則二者之間的信任度為零. 在現(xiàn)實(shí)生活中,人們之間的信任程度受到交互經(jīng)驗(yàn)的影響,推薦系統(tǒng)中用戶間的信任度也會(huì)隨著項(xiàng)目交互結(jié)果的變化而逐漸變化. 本文根據(jù)用戶評(píng)分的均值將用戶評(píng)分分成兩類,即積極評(píng)分和消極評(píng)分. 如果評(píng)分值不小于用戶的評(píng)分均值就被認(rèn)為是積極評(píng)分,相反則被認(rèn)為是消極評(píng)分. 當(dāng)用戶u和v對(duì)項(xiàng)目i的評(píng)分同為消極評(píng)分或積極評(píng)分時(shí),交互是成功的,反之是失敗的：

公式中1表示交互成功,0表示交互失敗. 交互成功和失敗分別用sus和fal表示若交互成功則sus+1,否則fal+1. 結(jié)合了用戶交互經(jīng)驗(yàn)的直接信任度計(jì)算公式如下：

1.2.3 間接信任的計(jì)算

在社會(huì)信任網(wǎng)絡(luò)中,當(dāng)2個(gè)用戶之間沒有直接的信任關(guān)系時(shí),就需要通過(guò)信任傳播從信任網(wǎng)絡(luò)中推斷出用戶之間的間接信任關(guān)系. 例如,假定用戶a信任用戶b,并且用戶b信任用戶c,通過(guò)使用信任傳播矩陣,可以推導(dǎo)出用戶a在某種程度上信任用戶c,在中間用戶多于一個(gè)的情況下,就需要使用信任聚合方法來(lái)合并不同的信任. 一般的信任聚合方法有： 最大值、最小值、均值. 其中加權(quán)平均聚合方法相比其他方法被認(rèn)為具有更好的性能[15],加權(quán)平均聚合的基本思想是確保距離源用戶比較近的信任路徑上的信任值獲得比較大的權(quán)值. 對(duì)任意的用戶u,v,w,間接信任計(jì)算公式如下：

綜合公式(8)和公式(9),可以得到兩個(gè)用戶之間的信任值,該信任值是通過(guò)評(píng)分矩陣計(jì)算得出來(lái)的,不同于TARS中用戶的顯式聲明,被稱為隱含信任. 表示為,公式如下：

1.2.4 選擇鄰居

對(duì)于鄰居的選擇過(guò)程,根據(jù)上一步計(jì)算得到的用戶相似度和間接信任度,采用Top-N方法選擇活動(dòng)用戶最信任或者與用戶相似的前N個(gè)鄰居.

1.2.5 計(jì)算加權(quán)評(píng)分

評(píng)分預(yù)測(cè)是推薦系統(tǒng)中最重要的步驟,本文的評(píng)分預(yù)測(cè)采取融合信任度與相似度的方式進(jìn)行加權(quán),計(jì)算公式如公式(11)：

2 算法流程

將上述所建立的用戶增強(qiáng)相似度以及用戶隱含信任度相結(jié)合,形成了本文新的協(xié)同過(guò)濾算法. 算法的具體步驟如下文.式(1)(2)(3)計(jì)算用戶的相似度JMSD,建立用戶相似度矩陣,根據(jù)公式(4)計(jì)算用戶的偏好相似度,最后根據(jù)公式(5)計(jì)算用戶的增強(qiáng)相似度

步驟2. 根據(jù)公式(7)計(jì)算用戶的交互成功和失敗項(xiàng)目集合,并根據(jù)公式(8)建立用戶的直接信任矩陣

步驟3. 根據(jù)用戶直接信任矩陣,利用公式(9)計(jì)算用戶的傳播信任,并根據(jù)公式(10)計(jì)算用戶的隱含信任,建立隱含信任矩陣.

步驟4. 確定用戶的鄰居數(shù)目N,根據(jù)公式(11)計(jì)算用戶的預(yù)測(cè)評(píng)分值進(jìn)行降序排列,將前N個(gè)項(xiàng)目推薦給用戶.

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本實(shí)驗(yàn)基于目前推薦系統(tǒng)研究中經(jīng)常使用的由美國(guó)Minnesota大學(xué)的GroupLens研究小組提供的MovieLens100 k(943個(gè)用戶、1682部電影、100 000條評(píng)分)和Epinions(49 290個(gè)用戶、139 738個(gè)項(xiàng)目、664 824條評(píng)分)數(shù)據(jù)集作為測(cè)試數(shù)據(jù)集. 兩個(gè)數(shù)據(jù)集的數(shù)據(jù)稀疏性(未評(píng)分過(guò)的項(xiàng)目數(shù)占整個(gè)數(shù)據(jù)集的比例)分別為93.7%和99.9%. 兩個(gè)數(shù)據(jù)集評(píng)分范圍為1-5. 實(shí)驗(yàn)中將數(shù)據(jù)集按照1：4的比例劃分成兩個(gè)部分：前者作為測(cè)試集合,測(cè)試模型的性能,后者作為訓(xùn)練集.

3.2.1 平均絕對(duì)誤差

本實(shí)驗(yàn)采用當(dāng)前被廣泛使用的平均絕對(duì)誤差(Mean Absolute Error,MAE)度量推薦算法的性能,它屬于統(tǒng)計(jì)精度方法. 它的原理是通過(guò)對(duì)比用戶對(duì)項(xiàng)目預(yù)測(cè)評(píng)分與用戶對(duì)項(xiàng)目實(shí)際評(píng)分的偏差,進(jìn)行算法預(yù)測(cè)準(zhǔn)確性的度量. 公式如下：

其中Pi為用戶對(duì)目標(biāo)的預(yù)測(cè)評(píng)分,Ri為實(shí)際評(píng)分,n代表預(yù)測(cè)評(píng)分的次數(shù). 從公式(12)可以看出,MAE值越小,算法預(yù)測(cè)的精確性越高.

3.2.2 覆蓋率

覆蓋率(Coverage)用來(lái)衡量一個(gè)算法能夠預(yù)測(cè)的項(xiàng)目占所有項(xiàng)目的百分比,在推薦系統(tǒng)中Coverage衡量的是推薦系統(tǒng)為用戶推薦的項(xiàng)目集對(duì)用戶興趣的覆蓋范圍,Coverage值越大,算法的全面性越好,Coverage的公式如下：

其中P(u)代表推薦系統(tǒng)為用戶u推薦的項(xiàng)目集合,R(u)代表用戶u在測(cè)試集上的評(píng)分集合.

3.3 實(shí)驗(yàn)結(jié)果分析

3.3.1 參數(shù) λ對(duì)MAE的影響

圖1 不同的λ值下算法的精確度變化 (MovieLens100k)

3.3.2 近鄰數(shù)對(duì)算法精確度影響

為了進(jìn)一步驗(yàn)證所提出的ETCF算法的有效性,2種傳統(tǒng)的算法和兩種改進(jìn)的傳統(tǒng)算法被選作比較對(duì)象： 基于PCC的協(xié)同過(guò)濾算法,基于Cosine的協(xié)同過(guò)濾算法,基于SPCC的協(xié)同過(guò)濾算法以及基于JMSD的協(xié)同過(guò)濾算法,近鄰數(shù)K的取值為10-90. 從圖3可以看出,在MovieLens100k數(shù)據(jù)集下,隨著鄰居數(shù)K的增加,五種算法的精確度都逐漸提高,之后稍有下降,但是從整體上看本文提出的ETCF算法的精確度一直優(yōu)于其他4種算法. 從圖4可以看出在Epinions數(shù)據(jù)集下隨著K增加,JMSD、Cosine、PCC三種算法的精確度都逐漸降低,接著逐漸升高,最后趨于穩(wěn)定. SPCC的精確度隨著K的增加先下降然后逐漸上升. 本文所提出的ETCF算法隨著K的增加逐漸降低,隨后逐漸升高. 但從整體上看,本文提出的ETCF算法的精確度一直優(yōu)于其他4種算法.

圖2 不同的λ值下算法的精確度變化 (Epinions)

圖3 近鄰數(shù)對(duì)算法精確度的影響 (MovieLens100k)

3.3.2 近鄰數(shù)對(duì)算法覆蓋率的影響

圖5和圖6分別為MovieLens100k和Epinions數(shù)據(jù)集下算法的覆蓋率隨鄰居數(shù)k的變化情況,隨著鄰居數(shù)K的增加,在兩個(gè)數(shù)據(jù)集下算法的覆蓋率都逐漸提升,但本文的ETCF算法覆蓋率一直優(yōu)與其他4種算法.

圖4 近鄰數(shù)對(duì)算法精確度的影響 (Epinions)

圖5 近鄰數(shù)對(duì)算法覆蓋率的影響 (MovieLens100k)

圖6 近鄰數(shù)對(duì)算法覆蓋率的影響 (Epinions)

實(shí)驗(yàn)結(jié)果分析： 由于Movielens數(shù)據(jù)集和Epinions數(shù)據(jù)集的稀疏性比較高,用戶之間的共同評(píng)分項(xiàng)較少.Cosine和PCC都是基于用戶之間的共同評(píng)分項(xiàng)來(lái)計(jì)算相似系數(shù),所以性能比較差,SPCC和JMSD考慮了用戶之間共同評(píng)分項(xiàng)較少的問(wèn)題,公式中引入了用戶之間的共同評(píng)分作為參考項(xiàng),因此和傳統(tǒng)的算法比性能上有了一定的提升,但是這兩種算法同樣存在著缺陷,首先沒有考慮用戶評(píng)分的興趣度問(wèn)題,其次沒有考慮兩個(gè)用戶沒有共同評(píng)分項(xiàng)的問(wèn)題. 本文提出的EFCF算法在一定程度上解決了上述問(wèn)題,因此具有較好的性能.

4 結(jié)束語(yǔ)

針對(duì)推薦系統(tǒng)中的數(shù)據(jù)稀疏性問(wèn)題,本文提出基于增強(qiáng)相似度和隱含信任的協(xié)同過(guò)濾算法,首先對(duì)傳統(tǒng)的相似性度量方法進(jìn)行改進(jìn),引入了一種基于用戶偏好和JMSD的增強(qiáng)相似度. 其次,考慮到兩個(gè)用戶之間可能沒有共同評(píng)分項(xiàng)的問(wèn)題,提出了一種基于隱含信任的信任傳播模型,在直接信任的計(jì)算過(guò)程了融入了用戶的交互經(jīng)驗(yàn),然后根據(jù)直接信任提出了一種間接信任的計(jì)算方法. 最后將用戶增強(qiáng)相似度和信任度分別進(jìn)行近鄰選擇,然后進(jìn)行融合. 實(shí)驗(yàn)表明,本文提出的ETCF算法相比傳統(tǒng)算法在推薦精度上和覆蓋率上有明顯的提升,然而該算法傳統(tǒng)相似度和用戶信任度融合的比例問(wèn)題還需要進(jìn)一步的探討.

1王立才,孟祥武,張玉潔. 上下文感知推薦系統(tǒng). 軟件學(xué)報(bào),2012,23(1)： 1-20.

2黃創(chuàng)光,印鑒,汪靜,等. 不確定近鄰的協(xié)同過(guò)濾推薦算法.計(jì)算機(jī)學(xué)報(bào),2010,33(8)： 1369-1377.

3徐守坤,孫德超,李寧,等. 一種結(jié)合語(yǔ)義Web和用戶信任網(wǎng)絡(luò)的協(xié)同過(guò)濾推薦模型. 計(jì)算機(jī)應(yīng)用研究,2014,31(6)：1714-1718.

4Eirinaki M,Louta MD,Varlamis I. A trust-aware system for personalized user recommendations in social networks. IEEE Transactions on Systems,Man,and Cybernetics： Systems,2014,44(4)： 409-421. [doi： 10.1109/TSMC.2013.2263128]

5Abbas A,Zhang LM,Khan SU. A survey on context-aware recommender systems based on computational intelligence techniques. Computing,2015,97(7)： 667-690. [doi： 10.1007/s00607-015-0448-7]

6Massa P,Avesani P. Trust-aware recommender systems.Proceedings of the 2007 ACM Conference on Recommender Systems. Minneapolis,MN,USA. 2007. 17-24.

7Yuan W,Shu L,Chao HC,et al. ITARS： Trust-aware recommender system using implicit trust networks. IET Communications,2010,4(14)： 1709-1721. [doi： 10.1049/ietcom.2009.0733]

8郭艷紅,鄧貴仕,雒春雨. 基于信任因子的協(xié)同過(guò)濾推薦算法. 計(jì) 算 機(jī) 工 程,2008,34(20)： 1-3. [doi： 10.3778/j.issn.1002-8331.2008.20.001]

9杜永萍,黃亮,何明. 融合信任計(jì)算的協(xié)同過(guò)濾推薦方法.模式識(shí)別與人工智能,2014,27(5)： 417-425.

10張俊,劉滿,彭維平,等. 融合興趣和評(píng)分的協(xié)同過(guò)濾推薦算法. 小型微型計(jì)算機(jī)系統(tǒng),2017,38(2)： 357-362.

11楊秀梅,孫詠,王丹妮,等. 融合用戶信任模型的協(xié)同過(guò)濾推薦算法. 計(jì)算機(jī)系統(tǒng)應(yīng)用,2016,25(7)： 165-170. [doi：10.15888/ j.cnki.csa.005229]

12陳婷,朱青,周夢(mèng)溪,等. 社交網(wǎng)絡(luò)環(huán)境下基于信任的推薦算法. 軟件學(xué)報(bào),2017,28(3)： 721-731. [doi： 10.13328/j.cnki.jos.005159]

13王瑞琴,蔣云良,李一嘯,等. 一種基于多元社交信任的協(xié)同過(guò)濾推薦算法. 計(jì)算機(jī)研究與發(fā)展,2016,53(6)：1389-1399. [doi： 10.7544/issn1000-1239.2016.20150307]

14Bobadilla J,Serradilla F,Bernal J. A new collaborative filtering metric that improves the behavior of recommender systems. Knowledge-Based Systems,2010,23(6)： 520-528.[doi： 10.1016/j.knosys.2010.03.009]

15Loll F,Pinkwart N. Using collaborative filtering algorithms as elearning tools. Proceedings of 42nd Hawaii International Conference on System Sciences. Big Island,HI,USA. 2009.1-10.