基于信任模型的社區(qū)發(fā)現(xiàn)與協(xié)同過濾推薦研究與應(yīng)用

趙瑩瑩,李玉潔,蘇 萍

(南通理工學(xué)院,江蘇 南通 226000)

0 引言

網(wǎng)絡(luò)技術(shù)的發(fā)展及信息化的不斷提高,“信息過載”的現(xiàn)象越來越嚴(yán)重,為了緩解這個(gè)問題,“推薦”應(yīng)運(yùn)而生。 推薦對(duì)于人們生活來說意義重大,社交平臺(tái)上的好友推薦服務(wù)是信息過濾的重要手段。 社區(qū)檢測(cè)被定義為識(shí)別給定網(wǎng)絡(luò)中所有的社區(qū),在這些社區(qū)中,用戶彼此之間的聯(lián)系比社區(qū)之外的聯(lián)系更緊密,將相同或相似興趣的用戶劃分為一個(gè)社區(qū),在社區(qū)中進(jìn)行推薦,而不需要用戶明確的要求。 Gu W 等[1]提出網(wǎng)絡(luò)信任傳播,即信任權(quán)代替相似權(quán),但是信任會(huì)隨著傳播而減少。 本文并沒有將信任代替相似度,而是將信任與相似度結(jié)合,在社團(tuán)中進(jìn)行推薦。 推薦模型質(zhì)量越高使得用戶依賴性越強(qiáng),可建立長(zhǎng)期穩(wěn)定的關(guān)系。

1 基于改進(jìn)信任模型和社區(qū)發(fā)現(xiàn)混合研究

1.1 基于相似性的信任模型

假設(shè)有一個(gè)網(wǎng)絡(luò),其中的節(jié)點(diǎn)具有相互作用。 信任可以通過一個(gè)有向圖來建模,用頂點(diǎn)表示實(shí)體,邊表示實(shí)體之間的信任關(guān)系。

利用圖的結(jié)構(gòu),存在一個(gè)用于導(dǎo)出信任的適當(dāng)模型,將其作為底層方法。 社區(qū)中的信任通過使用信任圖來建模,即一條邊作為兩個(gè)實(shí)體之間建立的信任關(guān)系。

信任聲明定義:

在εxε,C,T,TD相似網(wǎng)絡(luò)中,信任聲明代表一個(gè)元素其包括Trustor,Trustee,c,t,Trustct,其中εxε 是實(shí)體與實(shí)體的集合,C 是特征的集合,TD 是信任域的元素,其計(jì)算函數(shù)為:

f是一個(gè)單調(diào)遞增函數(shù),這就意味著元素之間的距離越小就越相似,因此其中一個(gè)對(duì)另一個(gè)的信任值也就越高。

信任域是一個(gè)部分有序集(TD,b,0),其中TD的每個(gè)有限子集在子集中都有一個(gè)極小元素,0 表示TD最小元素的特定信任域是區(qū)間[0,1),在區(qū)間中1 表示完全信任,0 表示缺乏信任的證據(jù)。

1.2 改進(jìn)信任模型

信任關(guān)系可以分為顯性信任和隱性信任,在大多數(shù)情況下,人們出于對(duì)自己的隱私的保護(hù),并不愿意給出顯性信任聲明,所以有時(shí)候信任聲明的獲取變得費(fèi)時(shí)又費(fèi)力。 本文提出一種隱性信任聲明,即在原有的某種隱性相似情況下推斷出其信任。

假設(shè)有一組用戶U= {u1,u2,u3,…,um}和一組項(xiàng)目I={i1,i2,i3,…,in}。 用戶U 對(duì)項(xiàng)目I 的每個(gè)記錄看作是一個(gè)評(píng)級(jí)。 用矩陣R=[rui]m×n表示用戶-項(xiàng)目之間的等級(jí)矩陣,其中每個(gè)條目rui表示用戶u對(duì)項(xiàng)目i的等級(jí)。 在社交網(wǎng)絡(luò)中加入用戶的信任關(guān)系,使用加權(quán)圖g= (V,E,W)表示社會(huì)信任網(wǎng)絡(luò),其中V是m個(gè)用戶的集合,E是用戶之間的邊集,W是信任度,使用矩陣T描述信任關(guān)系。 社交網(wǎng)絡(luò)中有許多不同的社會(huì)行為。 如果用戶與他人對(duì)某一部電影評(píng)價(jià)一致,則對(duì)其推薦時(shí)效果增強(qiáng)。 如表1 所示,用戶u1和用戶u2對(duì)電影i1和電影i2的評(píng)分都是相同的,則可以推斷出u1和u2之間存在著信任關(guān)系,從用戶之間相同評(píng)分的電影個(gè)數(shù)可以計(jì)算出他們之間的信任強(qiáng)度,其信任強(qiáng)度用ηij表示。 空格代表其并沒有看這部電影,評(píng)級(jí)的范圍都是在0～5。

表1 關(guān)于社會(huì)行為的一個(gè)簡(jiǎn)單例子

m位用戶之間的信任關(guān)系如公式2 所示,可以看出是一個(gè)對(duì)稱矩陣,即ηij=ηji,則通過隱性信任信息構(gòu)造用戶與用戶之間的信任關(guān)系。

1.3 融合聚類

通過相似度與信任關(guān)系迭代聚類,支持向量回歸模型進(jìn)行預(yù)測(cè),該模型基于用戶、項(xiàng)和預(yù)測(cè)相關(guān)的特性。

聚類過程如圖1 所示。

圖1 融合聚類過程

本文選擇k-medoids 進(jìn)行兩者之間的聚類。 kmedoids 算法選擇一個(gè)真實(shí)用戶作為質(zhì)心,從而最小化集群內(nèi)兩兩距離的總和。 其目標(biāo)函數(shù)如下:

C為用戶的整個(gè)集群,u和v表示集群中的用戶,c屬于C集群,d(u,v)定義用戶之間的距離。

表2 相似度與信任分區(qū)聚類

表3 融合聚類算法

算法復(fù)雜度分析:對(duì)于算法1,迭代最耗時(shí)的部分是迭代搜索以前生成的集群(第8～9 行和第16～17 行)和更新相似度和信任度。 其計(jì)算時(shí)間大概是O(n2s+n2t)≈O(n2)。 對(duì)于算法2,主要的計(jì)算是識(shí)別將要合并和修剪的集群(第7～16 行),時(shí)間復(fù)雜度是O(ninj)。 由于該算法消除第19 行中的簇,所以整個(gè)計(jì)算時(shí)間為O(krninj) ≈O(n2) 。 綜上所述,融合聚類方法的總體時(shí)間復(fù)雜度為O(m(n2+n2)) ≈O(n2) 。 本算法使用并行方式計(jì)算(第8 ～9 行),提高了計(jì)算的速度,最終的時(shí)間復(fù)雜度為O(n)。

1.4 添加信任模型發(fā)現(xiàn)社團(tuán)

本論文在相似度的基礎(chǔ)上添加信任信息矩陣,有效地緩解數(shù)據(jù)稀疏性問題,X表示相似與信任融合矩陣。 改進(jìn)的社團(tuán)發(fā)現(xiàn)過程如下:

輸入:相似與信任融合矩陣X,迭代次數(shù)maxiter,K個(gè)社區(qū),屬性信息相似度矩陣L。

輸出:社區(qū)的劃分矩陣

步驟1 對(duì)相似與信任融合矩陣X以K進(jìn)行非負(fù)矩陣分解算法,得到分解矩陣U和V,然后對(duì)U和V進(jìn)行規(guī)范化操作。

步驟2 利用目標(biāo)函數(shù)O= ‖X-UVT‖2+λTr(VTLV) 進(jìn)行計(jì)算,最小化其目標(biāo)函數(shù)。

步驟3 重復(fù)下列操作,直至目標(biāo)函數(shù)不發(fā)生變化為止。

對(duì)V 進(jìn)行如下更新操作(迭代次數(shù)maxiter):

計(jì)算目標(biāo)函數(shù):

步驟4 輸出結(jié)果U(U中的每個(gè)列元素看作頂點(diǎn)到K 群的隸屬度)。

2 基于社區(qū)發(fā)現(xiàn)和協(xié)同過濾推薦研究

2.1 協(xié)同過濾算法概念

在推薦系統(tǒng)中,協(xié)同過濾算法應(yīng)用非常廣泛。 首先確定目標(biāo)用戶,找出與其興趣相同或相似的鄰居社區(qū)。 在社區(qū)中,預(yù)測(cè)目標(biāo)用戶可能喜歡的項(xiàng)目,并向其進(jìn)行推薦,可知推薦效果更強(qiáng)。 用戶對(duì)項(xiàng)目的興趣越大,得分越高。 Ghaleb 等[2-3]提出推薦是偶然發(fā)生的。算法允許用戶參與推薦的過程,并且用戶自己決定好壞。

2.2 協(xié)同過濾算法內(nèi)容及步驟

協(xié)同過濾算法主要步驟:

(1)首先建立一個(gè)評(píng)級(jí)表或者是矩陣。 評(píng)級(jí)的內(nèi)容可以是顯性的,也可以是隱性的。

(2)對(duì)評(píng)級(jí)表或矩陣進(jìn)行處理。

(3)在對(duì)上一步處理之后,在此基礎(chǔ)上生成對(duì)項(xiàng)目預(yù)測(cè)的矩陣。

在處理評(píng)價(jià)表期間,算法進(jìn)一步分為兩類。 鄰域(基于內(nèi)存)和潛在因素(基于模型的算法)[4]。

2.3 基于社區(qū)TOP-N 協(xié)同過濾研究

2.3.1 TOP-N 排序原理

將傳統(tǒng)的協(xié)同過濾算法近鄰與社會(huì)近鄰結(jié)合,在社區(qū)中利用近鄰用戶對(duì)目標(biāo)用戶進(jìn)行推薦,某個(gè)社區(qū)簡(jiǎn)圖如圖2 所示。

圖2 某個(gè)社區(qū)內(nèi)部最近鄰用戶分布

在某一社區(qū)中,存在集合U(n個(gè)用戶),集合I(m個(gè)項(xiàng)目),用戶-項(xiàng)目的評(píng)價(jià)矩陣R={Rui}∈Rnxm。 在本文中,進(jìn)行隱式反饋和二進(jìn)制評(píng)分,即rui∈{0,1}。值rui=1 表示用戶u對(duì)項(xiàng)目i進(jìn)行評(píng)分,值rui=0 表示用戶u是否喜歡項(xiàng)目i資料不足。

矩陣W是固定的(W=R)。

3 應(yīng)用與分析

3.1 數(shù)據(jù)集采集

本文對(duì)電影進(jìn)行個(gè)性化推薦,在社團(tuán)中,目標(biāo)用戶通過近鄰用戶推薦電影。 所用的是真實(shí)數(shù)據(jù)集,在movielens 網(wǎng)站上,選取大小為movielens-100k 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)以及性能評(píng)估。 movielens-100k 數(shù)據(jù)集屬性信息如表4 所示。 從下述表中可以看出數(shù)據(jù)比較稀疏。

表4 movielens-100k 數(shù)據(jù)集屬性信息

3.2 測(cè)評(píng)指標(biāo)

本文使用AUC 曲線作為評(píng)估Top-N 推薦效果的評(píng)測(cè)指標(biāo)更加的適合。

在基于用戶的神經(jīng)網(wǎng)絡(luò)中,對(duì)于所需的目標(biāo)用戶,定義一對(duì)空項(xiàng)目(i,j),且i?uj,表示為ρ(i?uj) ,如下所示:

3.3 實(shí)驗(yàn)過程以及參數(shù)設(shè)置

首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,選取movielens 網(wǎng)站上的movielens-100k 數(shù)據(jù)集,刪除數(shù)據(jù)集中電影類型內(nèi)部缺失記錄。 計(jì)算用戶與用戶電影之間相似度,得到用戶-電影相似度矩陣Ds。 然后通過上述隱性信任方式計(jì)算用戶之間的信任度,得到用戶之間的信任度矩陣Dt,將Ds,Dt融合聚類,得到信任與相似融合矩陣X,再通過上述1.4 實(shí)驗(yàn)步驟得到用戶社團(tuán),在得到的社區(qū)中進(jìn)行目標(biāo)用戶TOP-N 協(xié)同過濾排序,最終通過AUC 曲線測(cè)評(píng)指標(biāo)將基于信任模型雙屬性矩陣非負(fù)矩陣分解社區(qū)發(fā)現(xiàn)與協(xié)同過濾推薦算法與NMF 融合協(xié)同過濾推薦算法進(jìn)行對(duì)比。

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

在TMDAMNMF 算法中,最終得到相似的用戶社區(qū)劃分,如圖3 所示,可以看出總共將用戶劃分成70 個(gè)相似的用戶社區(qū)。

圖3 movielens-100k 相似用戶社區(qū)

TMDAMNMF 與DAMNMF,NMF 算法模塊度Q值對(duì)比,如表5 所示。 TMDAMNMF 算法的Q更高,即得到相似的用戶社區(qū)準(zhǔn)確度更高。

表5 NMF、DAMNMF、TMDAMNMF 模塊度Q 比較

為了評(píng)價(jià)本文方法的性能,并與NMF 融合協(xié)同過濾推薦進(jìn)行比較,本章采用5 倍交叉驗(yàn)證的方法。 從表6 中可以看出,本方法在AUC 方面優(yōu)于NMF 融合協(xié)同過濾推薦方法。 在表7 中獲得的結(jié)果與不同的設(shè)置表明λp≈1,λn≈1 000 結(jié)果總是比較好。 在模型的構(gòu)建中,對(duì)于λn,較小的值可能使模糊的信息過于相關(guān),最終使得模型估計(jì)中引入錯(cuò)誤的信息,較大的值會(huì)減輕模棱兩可的信息的負(fù)面影響,所以λn值較大會(huì)更好。

表6 本方法與NMF 融合協(xié)同過濾推薦AUC 對(duì)比

表7 社區(qū)中AUC 的外部參數(shù)變化情況

4 結(jié)語

本論文將信任模型與用戶相似性相結(jié)合,通過kmedoids 算法進(jìn)行融合聚類,得到信任模型與用戶相似性之間的融合,在一定的程度上緩解了推薦當(dāng)中很難避免的稀疏性問題,將得到的相似與信任融合屬性信息矩陣X與用戶-電影類型屬性信息矩陣L用于基于雙屬性矩陣非負(fù)矩陣分解社區(qū)發(fā)現(xiàn)算法,可得到所需社團(tuán),在社團(tuán)中使用TOP-N 排序協(xié)同過濾算法,使得到的推薦列表的準(zhǔn)確度更高。