基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法*

鄭懷宇

(福建中醫(yī)藥大學(xué) 現(xiàn)代教育技術(shù)中心， 福州 350122)

隨著互聯(lián)網(wǎng)與無線通信技術(shù)的飛速發(fā)展，海量數(shù)據(jù)信息被提供給網(wǎng)絡(luò)用戶.在海量數(shù)據(jù)和信息面前，用戶往往陷入數(shù)據(jù)信息的汪洋大海，難以精確選取符合定制化需求和個性偏好的項目資源.針對該問題，推薦系統(tǒng)從兩方面來為用戶推薦個性化的信息、商品和服務(wù)：基于內(nèi)容推薦與協(xié)同過濾推薦.在眾多推薦方法中，協(xié)同過濾應(yīng)用最為廣泛.協(xié)同推薦[1-2]首先在用戶群體中找到與用戶節(jié)點偏好相近的鄰居用戶，綜合鄰居用戶的評價信息，為用戶節(jié)點推薦其可能喜歡的服務(wù).

協(xié)同過濾推薦系統(tǒng)不需要考慮項目的內(nèi)容，且易于實現(xiàn)，是當(dāng)前應(yīng)用最為廣泛的推薦技術(shù)之一.許多大型的電子商務(wù)網(wǎng)站都應(yīng)用了協(xié)同過濾推薦系統(tǒng)，如Amazon、淘寶、當(dāng)當(dāng)網(wǎng)等.但協(xié)同過濾也面臨兩大難題[3]，即數(shù)據(jù)稀疏性與鄰居用戶推薦.

針對上述問題，本文提出了基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法.相比傳統(tǒng)的協(xié)同推薦算法，該算法將協(xié)同推薦分為兩個階段：

2) 協(xié)同推薦階段.圍繞聚類中心及其所在群組為未評分項目完成預(yù)測評分，為用戶推薦綜合評分最高的Top-n項目.

1 研究背景

除了同一類型節(jié)點構(gòu)成的同質(zhì)網(wǎng)絡(luò)，現(xiàn)實世界中還廣泛存在著大量具有二分結(jié)構(gòu)(2-mode)的網(wǎng)絡(luò)[4-5]，例如電影與電影評價、上網(wǎng)者與點擊網(wǎng)頁、論文合著者與其合著論文、在線用戶與其加入的興趣群組等等.二分圖網(wǎng)絡(luò)由兩類節(jié)點群體及兩類節(jié)點間的連接組成，同類節(jié)點之間不存在連邊，前一類節(jié)點表示某活動、事件的參與者(用戶節(jié)點)，后一類節(jié)點表示所參與的活動或事件.當(dāng)用戶節(jié)點與項目節(jié)點建立邊連接后，擁有共同連接節(jié)點的用戶節(jié)點之間也具有了連通性.

假設(shè)推薦系統(tǒng)中有m個用戶和n個項目，令G(U，I，E)表示一個二分圖網(wǎng)絡(luò)推薦系統(tǒng)，為m×n階項目評分權(quán)重矩陣，U為用戶節(jié)點集，I為項目節(jié)點集，E為邊集.假設(shè)用戶節(jié)點數(shù)U=m，項目節(jié)點數(shù)I=n，則二分圖網(wǎng)絡(luò)節(jié)點總數(shù)為r=m+n.若用戶up對項目iq的評分不為空，則Gpq=1；否則，Gpq=0.

二分圖網(wǎng)絡(luò)除了刻畫傳統(tǒng)意義上的網(wǎng)絡(luò)結(jié)構(gòu)特征，還有助于為用戶實現(xiàn)精確的協(xié)同推薦[6-7].二分圖網(wǎng)絡(luò)示意圖如圖1所示，二分圖網(wǎng)絡(luò)的特殊結(jié)構(gòu)可以從兩方面進(jìn)行理解：

1) 網(wǎng)絡(luò)由用戶域和項目域共同組成，用戶域與項目域間的連接狀況反映了用戶節(jié)點與項目節(jié)點間建立連接的傾向與選擇性，可認(rèn)為是用戶節(jié)點的偏好、傾向在項目節(jié)點上的映射；

2) 圍繞同一聚類中心的群組節(jié)點具有近似的行為模式或連接模式，可以推薦共同關(guān)注的項目.

圖1 二分圖網(wǎng)絡(luò)示意圖Fig.1 Schematic bipartite networks

基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法充分考慮了用戶之間的鄰域關(guān)系、用戶與項目之間基于鄰域和項目的關(guān)聯(lián)，根據(jù)協(xié)同過濾和用戶聚類推薦的思想進(jìn)行協(xié)同推薦.該算法有兩個特點：

1) 結(jié)合鄰域用戶的評分行為構(gòu)建用戶相似度，將用戶之間的鄰域關(guān)系與項目關(guān)聯(lián)，離線建模到鄰域用戶相似度矩陣中，以保證推薦準(zhǔn)確性；

2) 使得目標(biāo)用戶的推薦計算量只與用戶聚類中心、核心用戶的關(guān)聯(lián)項目相關(guān)，從而降低方法的復(fù)雜度.

2 基于用戶聚類的網(wǎng)絡(luò)協(xié)同推薦算法

本文提出了一種基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法，在二分圖網(wǎng)絡(luò)中，根據(jù)用戶對不同項目的興趣程度進(jìn)行用戶聚類，為目標(biāo)用戶推薦其可能喜歡的項目.通過分析二分圖矩陣中用戶與項目的評分信息將用戶聚類，獲取目標(biāo)用戶所在類的評分信息，并基于同類用戶實現(xiàn)二分圖的協(xié)同推薦，提升在稀疏數(shù)據(jù)集上的推薦效果.本文算法主要包括估算節(jié)點中心度、用戶聚類、協(xié)同推薦等階段，主要流程如圖2所示.

圖2 基于用戶聚類的協(xié)同推薦算法流程Fig.2 Flow chart of collaborative recommendationalgorithm based on user clustering

2.1 基本定義

定義2用戶中心度.G={U，O，E}表示某二分圖網(wǎng)絡(luò)，借鑒PageRank算法的中心度定義，將網(wǎng)絡(luò)G中任意節(jié)點i的中心度P表示為

(1)

式中：ωik為連接節(jié)點i和k的邊eik的權(quán)重；a(i)為與節(jié)點i有直接連接的所有鄰接節(jié)點的集合.在原始的PageRank定義中，通常設(shè)置α為0.85，α∈(0，1).(1-α)/(m+n)項是為孤立節(jié)點設(shè)定一個附加值，避免其中心度計算無法收斂.用戶中心度刻畫了二分圖網(wǎng)絡(luò)中任意用戶節(jié)點的全局中心度，基于用戶中心度可以獲取用戶的聚類中心，并基于此確定目標(biāo)用戶所在的用戶聚類，獲取同類用戶選擇項目節(jié)點連接的選擇性與傾向，并為一個或多個目標(biāo)用戶推薦可能喜歡的項目.

定義3用戶相似度矩陣.二分圖網(wǎng)絡(luò)中用戶選定的評分項目往往有重合節(jié)點，這些重合節(jié)點構(gòu)成了不同用戶間的評分相似性.本文采用Pearson系數(shù)來衡量用戶間的評分相似度，即

(2)

評分相似度可以衡量任意兩用戶節(jié)點u，t關(guān)于項目節(jié)點的喜好和選擇方面的相似度，sim(u，t)值越大，相似度越高，推薦的項目節(jié)點越有可能被喜歡；sim(u，t)值越小，相似度越低，推薦的項目節(jié)點被喜歡的可能性越低.

2.2 用戶聚類

為了提高協(xié)同推薦的有效性和準(zhǔn)確性，需要對二分圖網(wǎng)絡(luò)進(jìn)行用戶聚類，從中提取關(guān)于目標(biāo)用戶的聚類信息，為下一步的協(xié)同推薦奠定基礎(chǔ).常用的聚類算法Kmeans和Kmedodis通過隨機選取數(shù)據(jù)節(jié)點作為聚類核心，這類算法對初始節(jié)點的選取較為敏感，聚類準(zhǔn)確性難以保證.針對該問題，本文采用基于節(jié)點中心度的聚類算法對二分圖網(wǎng)絡(luò)進(jìn)行用戶聚類，以克服隨機選取初始節(jié)點對用戶聚類的不利影響.

聚類中心與項目節(jié)點集的關(guān)系模型如圖3所示，在實際二分圖網(wǎng)絡(luò)中，中心度較高的用戶節(jié)點更有可能成為網(wǎng)絡(luò)中的聚類中心.但若從全網(wǎng)絡(luò)范圍內(nèi)計算所有用戶節(jié)點的中心度，計算復(fù)雜度較高，很多節(jié)點的計算甚至并不必要.本文設(shè)計如下策略：選取大于或等于網(wǎng)絡(luò)平均節(jié)點度的節(jié)點作為候選的種子節(jié)點.借鑒了圖摘要算法的思想，提出了一種簡化的中心度聚類算法，該算法首先構(gòu)建基于用戶節(jié)點的相似度矩陣，從用戶相似度矩陣中選取節(jié)點度較高的節(jié)點作為聚類核心，然后計算高度數(shù)節(jié)點在網(wǎng)絡(luò)中的中心度并排序，以搜索二分圖網(wǎng)絡(luò)中所有的聚類中心，最后圍繞聚類核心完成用戶聚類.算法的具體步驟如下：

1) 初始化聚類中心節(jié)點集為空.

2) 基于用戶關(guān)聯(lián)的項目構(gòu)建并計算用戶的相似性，獲得用戶相似性矩陣Bm×m，bij=sim(i，j)表示用戶i與用戶j在關(guān)聯(lián)項目評分上的相似度.

3) 選取矩陣B中節(jié)點度大于均值的節(jié)點作為聚類核心，并圍繞其鄰居節(jié)點聚類.在其跳轉(zhuǎn)范圍內(nèi)，計算所有周圍鄰近節(jié)點的中心度P值.

4) 節(jié)點聚類后，計算擴展子團(tuán)中心度，若中心度增量為正，則將該節(jié)點加入對應(yīng)的用戶聚類核心.

5) 重復(fù)步驟3)和4)，選取中心度為Top-p的節(jié)點作為二分圖網(wǎng)絡(luò)的聚類中心.

圖3 二分圖網(wǎng)絡(luò)中聚類中心與項目節(jié)點集的關(guān)系模型Fig.3 Relation model between clustering centers andproject node set in bipartite networks

當(dāng)滿足以下條件，算法終止：1)超過最大的迭代次數(shù)；2)所有聚類中心節(jié)點的中心度高于某門限閾值.通過中心度聚類算法，最終能夠獲取二分圖網(wǎng)絡(luò)中所有用戶節(jié)點的聚類中心.聚類中心選擇算法從用戶節(jié)點集U中獲得p個聚類中心，按照各用戶節(jié)點到聚類中心的距離大小將用戶節(jié)點劃分為p類，分類用戶集合表示為C={c1，c2，…，cp}.

2.3 基于二分圖網(wǎng)絡(luò)的協(xié)同推薦算法

假設(shè)通過聚類中心選擇算法從用戶節(jié)點集U中獲得p個聚類中心cp，并進(jìn)一步得到用戶u所隸屬的聚類中心及所屬類的用戶聚類中心cu.基于二分圖網(wǎng)絡(luò)的評分矩陣及協(xié)同推薦算法圍繞用戶u同類的鄰居用戶進(jìn)行未評分項目的評分預(yù)測，綜合比較最終的評分矩陣，并選取其中評分較高的項目推薦給用戶集U.算法流程如下：

1) 獲取用戶聚類中心及每類中心里所有用戶推薦的項目集合{o1，o2，…，op}，oi表示對應(yīng)聚類中心ui的所有推薦項目；

2) 采用Pearson相關(guān)系數(shù)計算目標(biāo)用戶ut與C={c1，c2，…，cp}中每一聚類中心的相似性，選取具有最大相似性的聚類中心類cmax作為ut所在的類；

3) 根據(jù)式(2)計算目標(biāo)用戶ut與cmax類中每位用戶的相似性，取相似性從大到小排列的前k個用戶作為用戶ut的最近鄰集合U0=(u1，u2，…，uk)；

4) 獲取與目標(biāo)用戶ut沒有直接聯(lián)系的未評分項目集合，并估算ut對未評分項目i的評分，即

(3)

5) 將目標(biāo)用戶ut所有的評分項目按降序排列，獲取前n個項目組成Top-n推薦集{o1，o2，…，on}，并輸出.

2.4 計算復(fù)雜度分析

傳統(tǒng)搜尋最近鄰的方式是基于整個用戶空間搜尋用戶節(jié)點的最近鄰計算，復(fù)雜度為O(m×n)，因為m和n是同一數(shù)量級，所以O(shè)(m×n)≈O(n2).而在本文算法的用戶聚類階段，根據(jù)關(guān)聯(lián)項目評分的相似性對用戶進(jìn)行聚類，計算復(fù)雜度為O(m×t)；在協(xié)同推薦階段，比較目標(biāo)用戶與各個用戶聚類核心的相似度，計算復(fù)雜度為O(p×n).在整個協(xié)同推薦過程中，避免了在整個二分圖網(wǎng)絡(luò)范圍內(nèi)進(jìn)行搜索和計算，整體計算復(fù)雜度為O(m×t)+O(p×n).由于t，p都遠(yuǎn)小于m或n，所以本文算法通過用戶聚類二分網(wǎng)絡(luò)協(xié)同推薦，能夠大大降低算法的復(fù)雜度和計算量.

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

為了分析基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法的性能，實驗將其與當(dāng)前2個經(jīng)典的協(xié)同推薦算法進(jìn)行比較，即CF(collaborative filtering)[8-9]和Content-based算法[10-11].其中，CF算法采用類似Top-k思想的協(xié)同過濾推薦算法；Content-based算法則采用了基于主題內(nèi)容相似度的k近鄰?fù)扑]算法.

本文使用MovieLens數(shù)據(jù)集7和Netflix數(shù)據(jù)集13對算法進(jìn)行評估.MovieLens數(shù)據(jù)集包含943位用戶對1 682部電影的100 000條評分記錄，評分值為1～5的正整數(shù).Netflix數(shù)據(jù)集包含480 189位用戶對17 770部電影的100 480 507條評分記錄，評分值為1～5的正整數(shù).由于Netflix數(shù)據(jù)集規(guī)模過大，從中隨機抽取25 413條評分記錄作為實驗數(shù)據(jù)集.表1給出了實驗用數(shù)據(jù)集的基本特征，本文將每一數(shù)據(jù)集劃分為50%的訓(xùn)練集用戶和50%的測試集用戶.

表1 實驗數(shù)據(jù)集基本特征Tab.1 Basic characteristics of experimental data sets

3.1 稀疏數(shù)據(jù)條件下推薦性能對比

在社交、購物等網(wǎng)絡(luò)應(yīng)用場景下，往往存在著數(shù)據(jù)稀疏性的問題，數(shù)據(jù)稀疏度常常低于10%，因此，稀疏數(shù)據(jù)條件下各種算法的推薦性能很重要.為對比稀疏條件下各種算法的協(xié)同推薦性能，將數(shù)據(jù)稀疏度設(shè)置為5%，6.5%，8.5%，12.5%4種情況，對比實際推薦數(shù)量與需要推薦數(shù)量的比值.實驗中設(shè)置最大需推薦數(shù)量不超過測試集的非零值數(shù)量.一般情況下，比值越大，則說明協(xié)同推薦算法對數(shù)據(jù)稀疏性的適應(yīng)能力越強，推薦效果越好.

表2表示在不同數(shù)據(jù)稀疏度條件下，4種算法實際推薦數(shù)量與需推薦數(shù)量的比值.當(dāng)數(shù)據(jù)極端稀疏時(稀疏度≤6.5%)，4種算法都不能獲取足夠的推薦數(shù)量，CF和Content-based算法推薦數(shù)量比值較低，而本文算法的推薦能力受數(shù)據(jù)稀疏性的影響相對較小，推薦數(shù)量比值接近于1；當(dāng)數(shù)據(jù)稀疏度≥8.5%時，CF和Content-based算法推薦數(shù)量比值有一定的提升，但仍然都小于50%，而本文算法的推薦數(shù)量比值為100%，完全能夠達(dá)到需要的推薦數(shù)量.這說明在稀疏條件下，本文算法的推薦效果更好.

3.2 協(xié)同推薦的準(zhǔn)確性對比

本文引入了Fmeasure和MAP(mean average precision)兩項指標(biāo)來衡量算法協(xié)同推薦的準(zhǔn)確 性.Fmeasure表示準(zhǔn)確率和召回率的調(diào)和平均值，該值越高則表明推薦算法的綜合性能越好；MAP表示對每個用戶推薦結(jié)果的平均值，該值越高，表明推薦算法的總體推薦質(zhì)量越好.

表2 稀疏數(shù)據(jù)條件下的協(xié)同推薦數(shù)量對比Tab.2 Quantitative comparison in collaborative recommendation under sparse data condition

(4)

(5)

式中：Fi為標(biāo)準(zhǔn)數(shù)據(jù)集，將局部社區(qū)發(fā)現(xiàn)的結(jié)果X映射到該標(biāo)準(zhǔn)數(shù)據(jù)集；r為數(shù)據(jù)集中被正確劃分的節(jié)點數(shù)在標(biāo)準(zhǔn)數(shù)據(jù)集所占的比例.

圖4和圖5分別表示不同數(shù)據(jù)稀疏度條件下，3種算法協(xié)同推薦Fmeasure指標(biāo)與MAP指標(biāo)的性能對比.綜合圖4、5可知，Content-based算法數(shù)據(jù)的稀疏性并不敏感，但推薦準(zhǔn)確率一直保持在較低水平；而本文算法在數(shù)據(jù)極端稀疏時，仍能保證較高的推薦準(zhǔn)確率，并隨著數(shù)據(jù)密集度增大而不斷上升.在3種算法中，本文算法在Fmeasure和MAP兩項推薦準(zhǔn)確率指標(biāo)上都能獲得最優(yōu)的性能，且相比傳統(tǒng)方法具有較為顯著的提升.

圖4 3種算法協(xié)同推薦Fmeasure指標(biāo)性能對比

Fig.4PerformancecomparisonincollaborativerecommendationofFmeasureindexfor3algorithms

3.3 協(xié)同推薦的多樣性對比

為對比協(xié)同推薦算法推薦結(jié)果的多樣性，實驗通過人工標(biāo)注，將測試數(shù)據(jù)集按照項目內(nèi)容和主題分為16個不同的類別.在冷啟動場景下，新加入的用戶由于關(guān)注的項目較少，推薦結(jié)果往往 就被限制在其關(guān)注的主題范圍內(nèi)，可推薦的項目也就較少.為避免推薦算法過快收斂，要求推薦算法能夠產(chǎn)生更具多樣性的推薦結(jié)果，并提高跨類別推薦的比例.

圖5 3種算法協(xié)同推薦MAP指標(biāo)性能對比

Fig.5PerformancecomparisonincollaborativerecommendationofMAPindexfor3algorithms

實驗中，通過選擇性地刪除在訓(xùn)練數(shù)據(jù)集中每個用戶對于某類或多類項目的關(guān)聯(lián)信息，來模擬冷啟動場景下的數(shù)據(jù)特點，以此來檢驗算法跨類別的推薦能力.推薦結(jié)果在測試集中被印證，才能稱為有效推薦；跨類別的推薦結(jié)果在測試集中的被印證，則稱為跨類別有效推薦.

表3顯示了3種算法協(xié)同推薦的多樣性推薦數(shù)量對比.隨著刪除類別數(shù)量的增多，3種算法的可推薦數(shù)量和跨類別的推薦數(shù)量都呈下降趨勢，推薦的有效數(shù)量和跨類別的有效數(shù)量也都逐步下降.相比其他2種算法，在相同條件下，本文算法推薦數(shù)量更多，跨類別推薦數(shù)量也更多，與實際結(jié)果相符的有效數(shù)量、跨類別的有效數(shù)量也更多.這說明相比傳統(tǒng)基于內(nèi)容的推薦方法，本文算法能夠產(chǎn)生更高質(zhì)量的跨類別推薦結(jié)果，協(xié)同推薦的多樣性更高；在冷啟動的場景下，跨類推薦的數(shù)量和多樣性都更優(yōu).而基于內(nèi)容的方法在主題類別缺失較多的情況下，具有極低的推薦多樣性，導(dǎo)致推薦結(jié)果過快收斂，推薦的范圍往往受限.

4 結(jié) 論

表3 3種算法協(xié)同推薦多樣性對比Tab.3 Diversity comparison in collaborative recommendation for 3 algorithms

參考文獻(xiàn)(References)：

[1] 王國霞，劉賀平.個性化推薦系統(tǒng)綜述 [J].計算機工程與應(yīng)用，2012，48(7)：66-76.

(WANG Guo-xia，LIU He-ping.Survey of personalized recommendation system [J].Computer Engineering and Applications，2012，48(7)：66-76.)

[2] Zhang P，Wang J L，Li X J，et a1.Clustering coefficient and community structure of bipartite networks [J].Physica A，2012，387：6869-6875.

[3] 譚云志，張敏，劉奕群，等.基于用戶評分和評論信息的協(xié)同推薦框架 [J].模式識別與人工智能，2016，29(4)：359-366.

(TAN Yun-zhi，ZHANG Min，LIU Yi-qun，et al.Collaborative recommendation framework based on ratings and textual reviews [J].Pattern Recognition and Artificial Intelligence，2016，29(4)：359-366.)

[4] 李霞，李守偉.面向個性化推薦系統(tǒng)的二分網(wǎng)絡(luò)協(xié)同過濾算法研究 [J].計算機應(yīng)用研究，2013，30(7)：1946-1949.

(LI Xia，LI Shou-wei.Research on collaborative filtering algorithm of bipartite network oriented to personal recommendation system [J].Application Research of Computers，2013，30(7)：1946-1949.)

[5] Everett M G，Borgatti S P.The dual-projection approach for two-mode networks [J].Social Networks，2013，35(2)：204-210.

[6] 吳湖，王永吉，王哲，等.兩階段聯(lián)合聚類協(xié)同過濾算法 [J].軟件學(xué)報，2010，21(5)：1042-1054.

(WU Hu，WANG Yong-Ji，WANG Zhe，et al.Two-phase collaborative filtering algorithm based on co-clustering [J].Journal of Software，2010，21(5)：1042-1054.)

[7] 冷亞軍，陸青，張俊嶺.使用二分圖網(wǎng)絡(luò)提高協(xié)同推薦的準(zhǔn)確性 [J].計算機科學(xué)，2015，42(3)：256-260.

(LENG Ya-jun，LU Qing，ZHANG Jun-ling.Using bipartite network for enhancement of collaborative filtering [J].Computer Science，2015，42(3)：256-260.)

[8] Kim Y，Shim K.A recommendation system for twitter using probabilistic modeling [C]//Proceedings of the 2012 IEEE 11th International Conference on Data Mining(ICDM).Vancouver，Canada，2012：340-349.

[9] Sakaguchi T，Akaho Y，Takagi T，et al.Recommendations in twitter using conceptual fuzzy sets [C]//Proceedings of the 2013 Annual Meeting of the North American Fuzzy Information Processing Society (NAFIPS).Toronto，Canada，2013：1-6.

[10]陳曉.基于雙聚類的圖書協(xié)同推薦方法 [J].蘭州交通大學(xué)學(xué)報，2016，35(3)：72-75.

(CHEN Xiao.Book collaborative recommendation method based on double cluster [J].Journal of Lanzhou Jiaotong University，2016，35(3)：72-75.)

[11]鄭修猛，陳福才，吳奇，等.一種利用多群組智慧的協(xié)同推薦算法 [J].西安交通大學(xué)學(xué)報，2016，50(10)：118-124.

(ZHENG Xiu-meng，CHEN Fu-cai，WU Qi，et al.A collaborative filtering recommendation algorithm using multiple groups intelligence [J].Journal of Xi′an Jiaotong University，2016，50(10)：118-124.)