基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型的物質(zhì)擴(kuò)散推薦算法

周 雙，賓 晟，邵峰晶，孫更新

(青島大學(xué)數(shù)據(jù)科學(xué)與軟件工程學(xué)院,山東 青島 266071)

0 引言

目前，個(gè)性化推薦技術(shù)主要分為基于圖的推薦[9]、協(xié)同過(guò)濾推薦[10]、混合推薦[11]、基于內(nèi)容的推薦[12]。其中，協(xié)同過(guò)濾推薦算法又分為兩種，一種是基于用戶的協(xié)同過(guò)濾推薦算法，另一種是基于項(xiàng)目的協(xié)同過(guò)濾推薦算法,如物質(zhì)擴(kuò)散算法[13]和熱傳導(dǎo)算法[14]等。物質(zhì)擴(kuò)散算法在推薦時(shí)執(zhí)行速度快且準(zhǔn)確率高，因此成為目前應(yīng)用最為廣泛的推薦算法之一。傳統(tǒng)的物質(zhì)擴(kuò)散算法，將物理動(dòng)力學(xué)中的物質(zhì)擴(kuò)散能量分配原理引入到二部圖中，通過(guò)能量擴(kuò)散計(jì)算不同商品間的相似度，進(jìn)而為用戶進(jìn)行推薦。

郭強(qiáng)等人[15]通過(guò)引入產(chǎn)品流行度的可調(diào)參數(shù)，提出了一種考慮產(chǎn)品流行度對(duì)用戶興趣偏好影響的物質(zhì)擴(kuò)散算法。胡吉明等人[16]將詞匯引入關(guān)聯(lián)圖中，探討了基于用戶、資源、詞匯三部圖的推薦實(shí)現(xiàn)機(jī)理，并提出了二部圖和能量分配雙重加權(quán)的三部圖推薦實(shí)現(xiàn)策略。周濤等人[17]利用用戶-產(chǎn)品的二部分圖建立關(guān)聯(lián)網(wǎng)絡(luò)，并運(yùn)用關(guān)聯(lián)矩陣提出基于網(wǎng)絡(luò)結(jié)構(gòu)的物質(zhì)擴(kuò)散算法。以上研究只是利用用戶-商品評(píng)分矩陣對(duì)用戶進(jìn)行推薦，并沒(méi)有充分考慮用戶之間存在的多種關(guān)系對(duì)推薦結(jié)果的影響，所以推薦結(jié)果并不十分準(zhǔn)確。因此，本文通過(guò)構(gòu)建多關(guān)系復(fù)合復(fù)雜網(wǎng)絡(luò)，將用戶間的多種社交關(guān)系引入到推薦系統(tǒng)中，從而提高了推薦算法的準(zhǔn)確率。

1 多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型

復(fù)合網(wǎng)模型可以使用一個(gè)四元組G=(V,E,R,F)表示：

1)V={v1,v2,…vm}表示節(jié)點(diǎn)的集合，m=|V|是集合中元素的個(gè)數(shù)；

2)E={〈vh,vl〉|vh,vl∈V,1≤h,l≤m}?V×V，表示節(jié)點(diǎn)間連邊的集合；

3)R=R1×…×Ri×…×Rn={(r1,…,ri,…,rn)|ri∈Ri,1≤i≤n},Ri表示節(jié)點(diǎn)間一種相互作用關(guān)系集合，ri表示節(jié)點(diǎn)間的一種相互作用關(guān)系,n是節(jié)點(diǎn)間相互作用關(guān)系的總數(shù)，當(dāng)n>1時(shí)，表示節(jié)點(diǎn)間有多種相互關(guān)系；

圖1 復(fù)合網(wǎng)G=(V,E,R,F)示例圖

圖1為復(fù)合網(wǎng)G=(V,E,R,F)的示例圖，節(jié)點(diǎn)可以表示不同類型的個(gè)體，連邊表示節(jié)點(diǎn)之間的關(guān)系，其中R=R1×R2,R1={r1},R2={r2}。從圖1中可以看出，邊〈v1,v2〉、〈v1,v3〉、〈v2,v3〉只具有R1關(guān)系，邊〈v2,v5〉、〈v3,v5〉、〈v4,v5〉只具有R2關(guān)系，邊〈v3,v4〉既具有R1關(guān)系又具有R2關(guān)系。

2 基于復(fù)合網(wǎng)的物質(zhì)擴(kuò)散算法

2.1 物質(zhì)擴(kuò)散算法

周濤等[17]首次提出了物質(zhì)擴(kuò)散(Mass Diffusion,MD)算法。MD算法基于用戶-商品二部圖網(wǎng)絡(luò)，它首先給用戶選擇過(guò)的商品賦予一個(gè)單位的能量，沒(méi)有被選擇過(guò)的商品初始能量為0，這作為初始狀態(tài)。從初始狀態(tài)出發(fā)，帶有能量的節(jié)點(diǎn)將能量平均分配給選擇過(guò)它的用戶，這樣能量就從商品擴(kuò)散到了所有用戶。經(jīng)過(guò)商品到用戶的第一步傳播后，用戶ui獲得的能量hi為

(1)

其中，kβ為商品oβ的度，n為商品的個(gè)數(shù)，fβ為商品oβ的能量，若商品oβ被用戶ui選擇過(guò)，則aiβ=1，否則aiβ=0。

(2)

其中，di為用戶ui的度，m為用戶的個(gè)數(shù)。

(3)

由式(1)、(2)、(3)可得整個(gè)物質(zhì)擴(kuò)散的過(guò)程為

(4)

圖2 用戶-商品二部圖物質(zhì)擴(kuò)散過(guò)程

2.2 基于復(fù)合網(wǎng)的物質(zhì)擴(kuò)散算法

傳統(tǒng)的物質(zhì)擴(kuò)散算法只是根據(jù)用戶對(duì)商品的評(píng)分進(jìn)行推薦，并沒(méi)有考慮用戶間社交關(guān)系對(duì)推薦的影響。通過(guò)構(gòu)建多關(guān)系復(fù)合網(wǎng)，商品節(jié)點(diǎn)的初始能量通過(guò)連邊在復(fù)合網(wǎng)中擴(kuò)散，從而達(dá)到了引入社交網(wǎng)絡(luò)信息進(jìn)行推薦的目的。

設(shè)復(fù)合網(wǎng)中用戶和商品的選擇關(guān)系為r1，若引入了用戶之間的某一種社交關(guān)系，則此關(guān)系為r2。假設(shè)r1和r2的關(guān)系強(qiáng)度均為1，r1關(guān)系強(qiáng)度比例系數(shù)為sf1,r2關(guān)系強(qiáng)度比例系數(shù)為sf2，且sf1+sf2=1。設(shè)sf1為p,則sf2為1-p，p∈(0,1)。當(dāng)引入用戶之間的一種社交關(guān)系時(shí)，基于復(fù)合網(wǎng)的物質(zhì)擴(kuò)散算法(簡(jiǎn)稱SMD)流程為

1)為目標(biāo)用戶選擇過(guò)的商品賦1個(gè)單位的能量，為該商品的初始能量。

2)商品中的能量通過(guò)連邊向用戶傳播，用戶節(jié)點(diǎn)ui獲得的能量hi為

(5)

(6)

(7)

4)在復(fù)合網(wǎng)絡(luò)中傳播后的用戶的能量又進(jìn)一步傳給了商品：

(8)

所以，商品oα獲得的能量gα為

(9)

(10)

對(duì)用戶沒(méi)有選擇過(guò)的商品按照最終能量的大小進(jìn)行排序，進(jìn)而形成推薦列表。當(dāng)p=1時(shí)，即關(guān)系r2的強(qiáng)度系數(shù)為0，SMD算法退化為傳統(tǒng)的MD算法。圖3為一個(gè)簡(jiǎn)單示例來(lái)描述引入一種用戶間社交關(guān)系的基于復(fù)合網(wǎng)的物質(zhì)擴(kuò)散算法(簡(jiǎn)稱SMD1)過(guò)程，其中假設(shè)p=0.5。

圖3 引入一種用戶間社交關(guān)系的基于復(fù)合網(wǎng)的物質(zhì)擴(kuò)散過(guò)程

(11)

圖4為引入兩種用戶間社交關(guān)系的基于復(fù)合網(wǎng)的物質(zhì)擴(kuò)散算法(簡(jiǎn)稱SMD2)過(guò)程，其中假設(shè)p=0.5,q=0.5。

當(dāng)q=0或q=1時(shí)，即關(guān)系r3的強(qiáng)度系數(shù)或者關(guān)系r2的強(qiáng)度系數(shù)為0，引入兩種用戶間關(guān)系的基于復(fù)合網(wǎng)的物質(zhì)擴(kuò)散算法SMD2就退化為引入一種用戶間關(guān)系的基于復(fù)合網(wǎng)的物質(zhì)擴(kuò)散算法SMD1。

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

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

本文采用推薦算法測(cè)試中常用的Epinions數(shù)據(jù)集和FilmTrust數(shù)據(jù)集對(duì)提出的推薦算法進(jìn)行評(píng)估。Epinions數(shù)據(jù)集包括40 163個(gè)的用戶，139 738個(gè)的商品，487 182條用戶和用戶之間的信任關(guān)系，以及664 823個(gè)用戶對(duì)商品的評(píng)分，通常用數(shù)值1～5表示。Film Trust數(shù)據(jù)集包括1 050個(gè)用戶，2 071個(gè)商品，1 853條用戶和用戶之間的信任關(guān)系，35 497個(gè)用戶對(duì)商品的評(píng)分。當(dāng)用戶對(duì)商品的評(píng)分大于2時(shí)，則代表用戶喜歡這個(gè)商品，用戶和商品之間有選擇關(guān)系，即用戶和商品之間建立連邊。此外還對(duì)數(shù)據(jù)集里的數(shù)據(jù)進(jìn)行預(yù)處理，剔除其中的孤立點(diǎn)，確保每個(gè)用戶都至少選擇過(guò)一個(gè)商品。

圖4 引入兩種用戶間社交關(guān)系的基于復(fù)合網(wǎng)的物質(zhì)擴(kuò)散過(guò)程

3.2 評(píng)價(jià)指標(biāo)

為了驗(yàn)證算法的性能，采用五折交叉驗(yàn)證的方法將數(shù)據(jù)集隨機(jī)分成了5份，在每次實(shí)驗(yàn)中，隨機(jī)選取一組作為測(cè)試集，其余四組作為訓(xùn)練集。5次實(shí)驗(yàn)保證每組數(shù)據(jù)集都被測(cè)試，實(shí)驗(yàn)最終結(jié)果是5次實(shí)驗(yàn)結(jié)果的均值。主要采用平均排序分(Ranking Score，RS)[15]來(lái)評(píng)價(jià)推薦結(jié)果的準(zhǔn)確性，漢明距離(Hamming Distance)[24]來(lái)衡量推薦列表的多樣性。

平均排序分[15]是評(píng)價(jià)推薦算法準(zhǔn)確率的一個(gè)重要指標(biāo)，該指標(biāo)數(shù)值越低，表示推薦算法的準(zhǔn)確率越高。對(duì)于一個(gè)目標(biāo)用戶ui，假設(shè)他在測(cè)試集中選擇了商品oj，計(jì)算oj在推薦的列表中的位置rij，測(cè)試集中用戶喜歡的所有商品的排序分的平均值越小，代表推薦算法把用戶喜歡的商品排在前面，說(shuō)明算法的準(zhǔn)確率越高。某一用戶ui排序分的定義為

(12)

對(duì)于用戶u和t,可以用漢明距離來(lái)評(píng)價(jià)兩個(gè)用戶推薦列表的多樣性，具體定義為

(13)

其中，Qut(L)表示用戶u和t推薦列表中相同商品的數(shù)目，L表示推薦列表的長(zhǎng)度。所有用戶的漢明距離的平均值就是整個(gè)推薦系統(tǒng)的漢明距離。漢明距離越大，表示推薦的多樣性越高。

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

在實(shí)驗(yàn)過(guò)程中首先利用仿真來(lái)確定p、q的取值。當(dāng)q=0時(shí)，p取不同值時(shí)Epinions數(shù)據(jù)集的平均排序分RS值的變化如圖5所示。

由圖5可知，在Epinions數(shù)據(jù)集中,當(dāng)p=0.4時(shí)，RS的值達(dá)到最小值，這表明，在該數(shù)據(jù)集中，SMD1算法在p=0.4時(shí)準(zhǔn)確率最高。在FilmTrust數(shù)據(jù)集中,RS在p=0.9時(shí)取得最小值，這表明，SMD1算法在p=0.9時(shí)準(zhǔn)確率最高。

用Ou、Ov分別表示用戶u和v購(gòu)買過(guò)的商品集合，u和v共同購(gòu)買的商品越多，則他們?cè)接锌赡苡泄餐呐d趣并相互影響，具體定義為

圖5 引入一種用戶間社交關(guān)系的基于復(fù)合網(wǎng)的物質(zhì)擴(kuò)散仿真結(jié)果

(14)

當(dāng)fuv>0.2，則代表用戶之間的興趣相似，設(shè)滿足這個(gè)條件的用戶之間的關(guān)系為r3。繼續(xù)加載r3關(guān)系，當(dāng)p、q取不同的值時(shí)，平均排序分RS值的變化如圖6所示。

圖6 引入兩種用戶間社交關(guān)系的基于復(fù)合網(wǎng)的物質(zhì)擴(kuò)散仿真結(jié)果

由圖6可知，當(dāng)p=0.4、q=0.2時(shí)，RS的值最小，這表明在Epinions數(shù)據(jù)集中，SMD2算法在p=0.4、q=0.2時(shí)準(zhǔn)確率最高。同理可知，在FilmTrust數(shù)據(jù)集中SMD2算法在p=0.9、q=0.9時(shí)準(zhǔn)確率最高。在FilmTrust數(shù)據(jù)集中，由于用戶之間的r3關(guān)系比r2關(guān)系密集，所以當(dāng)q趨于1時(shí)，推薦算法的準(zhǔn)確性更高。

為了對(duì)比本文提出算法的性能，分別在Epinions數(shù)據(jù)集和FilmTrust數(shù)據(jù)集上測(cè)試了目前較為常用的推薦算法HeatS和Hybrid[25-26]。Hybrid算法在這兩個(gè)數(shù)據(jù)集上的RS最優(yōu)值分別在調(diào)節(jié)參數(shù)λ為0.67和0.5時(shí)得到。當(dāng)p、q取最佳參數(shù)值時(shí)，在Epinions數(shù)據(jù)集和FilmTrust數(shù)據(jù)集采用不同推薦算法獲得的RS值如表1所示：

表1 不同算法實(shí)驗(yàn)結(jié)果

由表1可知，在Epinions數(shù)據(jù)集和FilmTrust數(shù)據(jù)集上，SMD2算法的推薦準(zhǔn)確率比SMD1算法準(zhǔn)確率高，且這兩種算法的準(zhǔn)確率明顯高于其他推薦算法。這表明，引入用戶之間的多種社交關(guān)系，可以較為顯著地提高推薦結(jié)果的準(zhǔn)確率。

除了準(zhǔn)確性，推薦列表的多樣性也是推薦算法的重要評(píng)價(jià)指標(biāo)。由式(13)可知，推薦列表長(zhǎng)度不同，平均漢明距離的值不一樣。圖7和圖8分別為各推薦算法在Epinions數(shù)據(jù)集和FilmTrust數(shù)據(jù)集中不同推薦列表長(zhǎng)度下的推薦多樣性的變化。

圖7 Epinions上不同算法多樣性實(shí)驗(yàn)結(jié)果

圖8 FilmTrust上不同算法多樣性實(shí)驗(yàn)結(jié)果

由圖7和圖8可知，在同一個(gè)數(shù)據(jù)集和同一個(gè)算法中，當(dāng)推薦列表長(zhǎng)度L取不同值時(shí)，推薦多樣性不一樣，且L值越大，推薦多樣性越低。這表明，推薦列表越長(zhǎng)，不同用戶的推薦列表相似度越高。在Epinions數(shù)據(jù)集和FilmTrust數(shù)據(jù)集上，SMD2算法和SMD1算法的推薦多樣性比傳統(tǒng)的物質(zhì)擴(kuò)散算法的低。這說(shuō)明當(dāng)考慮了用戶之間的社交關(guān)系時(shí)，用戶的推薦列表不僅受自己歷史評(píng)分?jǐn)?shù)據(jù)的影響，還受到與該用戶有關(guān)系的其他用戶的歷史評(píng)分?jǐn)?shù)據(jù)的影響，即用戶的推薦列表會(huì)和與該用戶有社交關(guān)系的用戶的相似度偏高一些，從而導(dǎo)致推薦多樣性偏低。HeatS算法相當(dāng)于是凹透鏡一樣把用戶的歷史評(píng)分信息發(fā)散到了那些不流行的物品上，所以推薦的多樣性比傳統(tǒng)的MD算法高。從而表明本文所提基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型的物質(zhì)擴(kuò)散推薦算法能更好地在興趣相似的用戶間進(jìn)行精準(zhǔn)推薦。

4 結(jié)論

本文通過(guò)融合社交網(wǎng)絡(luò)信息，基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型構(gòu)建多關(guān)系復(fù)合網(wǎng)，通過(guò)實(shí)驗(yàn)證明了本文所提的基于復(fù)合網(wǎng)進(jìn)行物質(zhì)擴(kuò)散的算法有效地提高了推薦的準(zhǔn)確率。這說(shuō)明將社交網(wǎng)絡(luò)中存在的多種關(guān)系引入到推薦系統(tǒng)中可以更好地識(shí)別用戶的潛在感興趣的商品。實(shí)驗(yàn)結(jié)果還證明融入兩種用戶間社交關(guān)系比融入一種社交關(guān)系以及不考慮社交關(guān)系的推薦效果更好，由此可知，將越多的用戶間社交關(guān)系引入到推薦系統(tǒng)中將會(huì)使得推薦結(jié)果的準(zhǔn)確率越高。進(jìn)一步發(fā)現(xiàn)用戶間存在的隱式社交關(guān)系，以及這些社交關(guān)系對(duì)推薦結(jié)果的影響，是在今后的研究中需要進(jìn)一步探索的主要方向。