基于模塊度和標(biāo)簽傳遞的推薦算法

盛 俊，李 斌，陳 崚

（1.揚(yáng)州大學(xué)信息工程學(xué)院，江蘇揚(yáng)州 225000；2.揚(yáng)州市職業(yè)大學(xué)信息工程學(xué)院，江蘇揚(yáng)州 225000）

0 引言

隨著網(wǎng)民數(shù)量的增加，近年來(lái)各種推薦系統(tǒng)得到了廣泛的應(yīng)用，可以向用戶推薦書(shū)籍［1］、產(chǎn)品［2］、視頻［3］和云計(jì)算服務(wù)［4］等。此外，還能向客戶推介其滿意的領(lǐng)域?qū)＜摇⒑献髡?、娛?lè)節(jié)目、餐廳、服裝、金融服務(wù)、人壽保險(xiǎn)、交友約會(huì)等。推薦系統(tǒng)的核心是推薦算法的設(shè)計(jì)［5］。推薦算法要能夠快速地從大量的信息中及時(shí)發(fā)現(xiàn)用戶的喜好與消費(fèi)習(xí)慣，發(fā)現(xiàn)與商品有關(guān)的有價(jià)值的內(nèi)容，并動(dòng)態(tài)、及時(shí)地向用戶推介。根據(jù)所基于的數(shù)據(jù)分析方法的不同，主要有3 類推薦方法：協(xié)同過(guò)濾方法、基于規(guī)則的和基于內(nèi)容的推薦方法。

協(xié)同過(guò)濾［6］是最常用的推薦方法。協(xié)同過(guò)濾方法的基本思想是：如果兩個(gè)人所喜好的項(xiàng)目很相似，其中一個(gè)人采用過(guò)的項(xiàng)目，另一個(gè)人很可能也會(huì)采用，并且他們會(huì)喜歡過(guò)去喜歡的類似的東西。雖然協(xié)同過(guò)濾方法已經(jīng)被廣泛使用，但它還存在3 個(gè)問(wèn)題需要解決：冷啟動(dòng)問(wèn)題、可伸縮性問(wèn)題和數(shù)據(jù)稀疏性問(wèn)題。如何解決這幾個(gè)問(wèn)題，是協(xié)同過(guò)濾方法性能提高的關(guān)鍵。

基于關(guān)聯(lián)規(guī)則的推薦［7-8］是利用關(guān)聯(lián)規(guī)則所提供的信息，通過(guò)關(guān)聯(lián)規(guī)則來(lái)計(jì)算各種商品被用戶所偏好程度的相關(guān)性。該方法的缺點(diǎn)是對(duì)關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)需要大量的計(jì)算時(shí)間，對(duì)于大型的推薦系統(tǒng)，很難滿足實(shí)時(shí)應(yīng)用的需要。

推薦系統(tǒng)的另一種常見(jiàn)方法是基于內(nèi)容的推薦［9-11］，這種方法將不同的候選項(xiàng)與用戶先前評(píng)價(jià)的項(xiàng)目進(jìn)行比較，推薦最佳匹配項(xiàng)。該類方法比較簡(jiǎn)單，而且推薦結(jié)果具有可解釋性，易于被理解。

二部網(wǎng)絡(luò)是一種重要的復(fù)雜網(wǎng)絡(luò)形式，通常用于兩種不同類型的對(duì)象之間的關(guān)系建模。二部網(wǎng)絡(luò)可以用圖論中的二部圖來(lái)表示，它的頂點(diǎn)可以分成兩個(gè)不相交的兩種類型的集合，在同一類型的頂點(diǎn)間不存在連接，只有在不同類型的頂點(diǎn)間才可能有條邊連接?，F(xiàn)實(shí)中的許多兩種不同類型的對(duì)象之間的關(guān)系度可以用二部網(wǎng)絡(luò)來(lái)描述。例如，一個(gè)足球運(yùn)動(dòng)員和俱樂(lè)部的關(guān)系可以用二分網(wǎng)絡(luò)來(lái)描述，如果球員為某俱樂(lè)部效力，在該球員和俱樂(lè)部之間就會(huì)有一個(gè)連接。二部網(wǎng)絡(luò)的其他的例子包括：用戶與項(xiàng)目的網(wǎng)絡(luò)［12］、公司投資者之間形成的股份網(wǎng)絡(luò)［13］、論文-作者網(wǎng)［14-15］、蛋白質(zhì)交互作用網(wǎng)絡(luò)［16］、基因-疾病網(wǎng)絡(luò)［17-19］等。推薦問(wèn)題主要是針對(duì)二部網(wǎng)絡(luò)而言的，二部網(wǎng)絡(luò)的加權(quán)的鄰接矩陣就是推薦問(wèn)題中的用戶-項(xiàng)目評(píng)分表。已經(jīng)有一些基于二部網(wǎng)絡(luò)的推薦方法，如基于二部網(wǎng)絡(luò)的鏈接預(yù)測(cè)的方法［20］、基于相似度網(wǎng)絡(luò)的個(gè)性化推薦方法［21］等。

還有一些推薦方法是基于復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘技術(shù)的，萬(wàn)慧等［22］針對(duì)電影推薦問(wèn)題，提出了一種融合電影類別、用戶評(píng)分和用戶標(biāo)簽的電影推薦模型。該方法基于電影類別使用凝聚式層次聚類算法進(jìn)行社區(qū)劃分，在社區(qū)中進(jìn)行推薦。黃泳航等［23］提出了基于社區(qū)劃分的學(xué)術(shù)論文推薦方法。該方法在社區(qū)好友關(guān)系網(wǎng)絡(luò)圖中進(jìn)行社區(qū)劃分，根據(jù)社區(qū)劃分結(jié)果在社區(qū)內(nèi)部的用戶之間推薦學(xué)術(shù)論文。賀懷清等［24］提出基于網(wǎng)絡(luò)社區(qū)劃分的協(xié)同推薦算法。該方法首先利用社區(qū)劃分算法對(duì)用戶進(jìn)行社區(qū)劃分，使得劃分在同一社區(qū)的用戶有共同話題和愛(ài)好，接著利用同一社區(qū)的用戶尋找目標(biāo)用戶近鄰集，最后根據(jù)近鄰用戶對(duì)未知項(xiàng)目的評(píng)分來(lái)預(yù)測(cè)目標(biāo)用戶的評(píng)分。

上述的各種基于復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘技術(shù)的推薦方法在對(duì)用戶-項(xiàng)目網(wǎng)絡(luò)進(jìn)行社區(qū)劃分以后，僅僅在社區(qū)內(nèi)通過(guò)用戶或項(xiàng)目相似度對(duì)項(xiàng)目進(jìn)行推薦，這就限制了推薦結(jié)果只能在同一社區(qū)內(nèi)進(jìn)行，使得推薦結(jié)果的質(zhì)量與社區(qū)劃分密切相關(guān)。對(duì)于不同的粒度、不同的社區(qū)個(gè)數(shù)，其社區(qū)劃分結(jié)果是不一樣的。這樣就很難找到一個(gè)能取得最優(yōu)推薦結(jié)果的社區(qū)劃分。為此，本文提出了基于社區(qū)挖掘的推薦算法，在考慮項(xiàng)目之間、用戶之間的相似性的同時(shí)，還考慮社區(qū)之間的相似性對(duì)項(xiàng)目進(jìn)行推薦。這樣可以提高推薦結(jié)果的質(zhì)量。

本文用帶權(quán)的二部圖來(lái)表達(dá)用戶-項(xiàng)目的評(píng)分矩陣，利用二部網(wǎng)絡(luò)的社區(qū)挖掘的技術(shù)，提出了在二部網(wǎng)絡(luò)上進(jìn)行社區(qū)挖掘的標(biāo)簽傳遞的算法，基于社區(qū)之間的相似性和用戶間的相似性對(duì)項(xiàng)目進(jìn)行推薦。該方法基于二部網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)信息，充分利用了用戶所在的社區(qū)之間的相似性，以及項(xiàng)目之間、用戶之間的相似性來(lái)挖掘用戶可能感興趣的項(xiàng)目。由于二部網(wǎng)絡(luò)的社區(qū)信息在一定程度上反映了用戶和項(xiàng)目的相似程度，算法可以取準(zhǔn)確率較高的推薦結(jié)果。

1 二部網(wǎng)絡(luò)及其社區(qū)挖掘

二部網(wǎng)絡(luò)可用一個(gè)無(wú)向簡(jiǎn)單二部圖G=(U，V，E)來(lái)表示，其中，E為G的邊的集合，U和V分別是G的兩部分頂點(diǎn)的集合。U和V兩部分頂點(diǎn)內(nèi)部不存在連接的邊，對(duì)于所有邊(u，v) ∈E必有u∈U、v∈V。二部網(wǎng)絡(luò)可以用來(lái)描述推薦問(wèn)題，例如圖1 所示為一個(gè)二部網(wǎng)絡(luò)，其中上面部分的節(jié)點(diǎn)表示用戶，下面部分的節(jié)點(diǎn)表示商品，在兩個(gè)部分的一些節(jié)點(diǎn)之間的連線上具有權(quán)重，表示上面部分的節(jié)點(diǎn)所代表的用戶對(duì)相應(yīng)的商品的評(píng)分值，其值的范圍為1～5。這樣就描述了7個(gè)用戶對(duì)8個(gè)商品進(jìn)行評(píng)分的推薦問(wèn)題。在圖1中，有些商品和用戶的節(jié)點(diǎn)之間沒(méi)有連線，說(shuō)明該用戶尚未對(duì)該商品評(píng)分，也可能是該項(xiàng)評(píng)分丟失了。在這種情況下，帶權(quán)鄰接矩陣中的相應(yīng)的元素aij的值為0。圖1 中的二部網(wǎng)絡(luò)的帶權(quán)鄰接矩陣如圖2 所示，其中每行代表用戶類型的一個(gè)頂點(diǎn)，每列代表項(xiàng)目類型的一個(gè)頂點(diǎn)。這實(shí)際上是推薦問(wèn)題中的評(píng)分矩陣。因此每個(gè)推薦問(wèn)題對(duì)應(yīng)了這樣一個(gè)加權(quán)二部圖。

圖1 二部網(wǎng)絡(luò)示例Fig.1 Bipartite network example

圖2 二部網(wǎng)絡(luò)鄰接矩陣示例Fig.2 Example of bipartite network adjacency matrix

復(fù)雜網(wǎng)絡(luò)往往具有社區(qū)特性，社區(qū)是由拓?fù)湫再|(zhì)相似、聯(lián)系密切的頂點(diǎn)所組成的。設(shè)二部網(wǎng)絡(luò)的兩部分頂點(diǎn)分別稱為X部分和Y部分，二部網(wǎng)絡(luò)的社區(qū)挖掘的目的就是要分別把二部網(wǎng)絡(luò)的X部分頂點(diǎn)和Y部分頂點(diǎn)各自劃分為若干個(gè)社區(qū)，而且定義兩個(gè)部分的社區(qū)之間的對(duì)應(yīng)關(guān)系，使得社區(qū)間頂點(diǎn)連接比較稀疏，而社區(qū)內(nèi)頂點(diǎn)之間連接比較稠密。

自2001 年Newman［25］提出社區(qū)挖掘的概念至今，已有很多學(xué)者提出關(guān)于復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘的方法。網(wǎng)絡(luò)社區(qū)挖掘的代表性方法有基于優(yōu)化模塊度、基于頂點(diǎn)劃分、基于標(biāo)簽傳播、基于仿生計(jì)算的方法以及利用Markov 隨機(jī)游走理論的方法等。

基于標(biāo)簽傳播的社區(qū)挖掘方法的基本思想是任一頂點(diǎn)都必須和它的大部分鄰居被劃分在同一個(gè)社區(qū)里.該方法開(kāi)始時(shí)將每一個(gè)頂點(diǎn)看作是一個(gè)社區(qū)，并給每個(gè)社區(qū)設(shè)定一個(gè)標(biāo)簽，然后通過(guò)迭代將標(biāo)簽傳遞，實(shí)現(xiàn)社區(qū)的合并。標(biāo)簽傳遞的規(guī)則是：每個(gè)節(jié)點(diǎn)取其鄰居節(jié)點(diǎn)中出現(xiàn)最多的標(biāo)簽為自己的新標(biāo)簽。若鄰居節(jié)點(diǎn)中出現(xiàn)最多的標(biāo)簽有多個(gè)，則根據(jù)一定的規(guī)則選取其中某一個(gè)作為自己的新標(biāo)簽。經(jīng)過(guò)若干次這樣的迭代后，緊密相連的節(jié)點(diǎn)的標(biāo)簽會(huì)趨于相同，即表示它們被劃分在同一個(gè)社區(qū)。

2 興趣密度值和稠密用戶

本文首先用一個(gè)矩陣P=[pij]n*n來(lái)表示由n個(gè)用戶對(duì)M個(gè)項(xiàng)目的評(píng)分，將這個(gè)評(píng)分矩陣看成帶權(quán)的鄰接矩陣，可構(gòu)建一個(gè)帶權(quán)二部圖G={(ui，vj)|ui∈U，vj∈V，pij＞0}。這里，U為代表用戶的頂點(diǎn)集合，V為代表項(xiàng)目的頂點(diǎn)集合，E為邊的集合，邊(i，j)上有權(quán)重值pij＞0，為用戶i對(duì)于項(xiàng)目j的評(píng)分。推薦問(wèn)題的目標(biāo)就是要對(duì)給定的用戶，計(jì)算那些沒(méi)有評(píng)分的項(xiàng)目的評(píng)分估計(jì)值，并將具有較高的評(píng)分估計(jì)值的一些項(xiàng)目向該用戶進(jìn)行推薦。

在用戶和項(xiàng)目數(shù)增多時(shí)，社交網(wǎng)絡(luò)規(guī)模迅速擴(kuò)大。此時(shí)，每個(gè)用戶所參與評(píng)價(jià)的項(xiàng)目數(shù)占總項(xiàng)目數(shù)的比例會(huì)迅速變小，使得評(píng)分矩陣變得稀疏，這就導(dǎo)致了網(wǎng)絡(luò)數(shù)據(jù)出現(xiàn)稀疏性。此外，由于用戶對(duì)某一類商品的偏好性，他的評(píng)分會(huì)集中在某一類商品上。還有由于一些商品的用戶的數(shù)量相對(duì)較少，如房屋、汽車等，用戶對(duì)商品評(píng)分也就較少，導(dǎo)致了在用戶-商品評(píng)分?jǐn)?shù)據(jù)庫(kù)的稀疏性。此外，新增的用戶往往評(píng)分的商品較少，也會(huì)增加數(shù)據(jù)的稀疏性，從而降低推薦結(jié)果的質(zhì)量。

為了解決評(píng)分矩陣的稀疏性問(wèn)題，本文提出了興趣密度值來(lái)挑出用戶頂點(diǎn)中對(duì)項(xiàng)目評(píng)分較多的頂點(diǎn)構(gòu)成稠密子集。然后在稠密子集中使用標(biāo)號(hào)傳遞的算法進(jìn)行社區(qū)挖掘，最終在得到的社區(qū)的基礎(chǔ)上進(jìn)行推薦。由于將評(píng)分矩陣所提供的用戶偏好信息和網(wǎng)絡(luò)的拓?fù)涮卣饔袡C(jī)地結(jié)合，使得推薦的準(zhǔn)確度得到提高。這也是一種基于社區(qū)挖掘的推薦算法。

針對(duì)數(shù)據(jù)的稀疏性問(wèn)題，為了提高推薦結(jié)果的質(zhì)量，本文挑選出用戶頂點(diǎn)中對(duì)項(xiàng)目評(píng)分較多的頂點(diǎn)，從而從稀疏網(wǎng)絡(luò)中構(gòu)造一個(gè)連接密集的子網(wǎng)絡(luò)，然后對(duì)該子網(wǎng)絡(luò)中的頂點(diǎn)進(jìn)行社區(qū)挖掘。為此定義每個(gè)用戶ui的興趣密度值des(ui)：

其中sign（）是符號(hào)函數(shù)，定義為：

由于用戶ui的興趣密度值des(ui)反映了用戶ui評(píng)價(jià)的項(xiàng)目數(shù)，為此，本文設(shè)定一個(gè)閾值ε＞0，定義稠密用戶集合為：

如此使得評(píng)價(jià)的項(xiàng)目數(shù)高于閾值的用戶定義為稠密用戶。興趣密度閾值ε的確定取決于網(wǎng)絡(luò)用戶側(cè)頂點(diǎn)連接的稠密程度。該稠密程度定義為，即為所有用戶的評(píng)論總數(shù)。在用戶側(cè)頂點(diǎn)連接的稠密程度較低時(shí)，用戶的評(píng)論較少，可取較低的值（如ε=0.5）；在網(wǎng)絡(luò)連接較稠密時(shí)，可取較高的值（如ε=1.5），對(duì)于一般的網(wǎng)絡(luò)可取ε=1。

由于一些商品對(duì)于大部分用戶僅僅是一次性需求，如房屋、汽車等，對(duì)它們總的評(píng)價(jià)數(shù)量相對(duì)較少。此外，新增的商品往往很少被用戶所知，導(dǎo)致評(píng)分較少，使得這些商品在用戶-商品評(píng)分?jǐn)?shù)據(jù)庫(kù)中的稀疏性。為了提高推薦結(jié)果的質(zhì)量，本文挑選出項(xiàng)目頂點(diǎn)中被評(píng)分較多的頂點(diǎn)，從而從稀疏網(wǎng)絡(luò)中構(gòu)造一個(gè)連接密集的子網(wǎng)絡(luò)。為了合理地挑選被評(píng)分較多的項(xiàng)目頂點(diǎn)，對(duì)項(xiàng)目頂點(diǎn)也定義其興趣密度值des(vj)：

設(shè)定一個(gè)λ＞0，定義稠密項(xiàng)目集合為：

類似于興趣密度閾值ε的確定，稠密項(xiàng)目的閾值λ的確定取決于網(wǎng)絡(luò)項(xiàng)目側(cè)頂點(diǎn)的稠密程度：在鏈接較稀疏時(shí)，可取較低的值（如λ=0.5）；在網(wǎng)絡(luò)鏈接較稠密時(shí)，可取較高的值（如λ=1.5）；對(duì)于一般的網(wǎng)絡(luò)可取λ=1。

用連接密集的子網(wǎng)絡(luò)中的用戶及其相關(guān)項(xiàng)目構(gòu)建新的評(píng)分矩陣P'，同時(shí)由P'構(gòu)建原二部圖的子圖G'=(U′，V′，E′)。然后在新的二部圖G'中利用標(biāo)簽傳遞進(jìn)行社區(qū)挖掘，這樣可以把用戶和項(xiàng)目一起聚類為若干社區(qū)，從而利用社區(qū)信息來(lái)計(jì)算相似度，再進(jìn)行推薦。本文根據(jù)興趣密度值選取稠密的用戶頂點(diǎn)和項(xiàng)目頂點(diǎn)構(gòu)成新的二部網(wǎng)絡(luò)，其優(yōu)點(diǎn)是使得對(duì)項(xiàng)目的推薦的信息集中在用戶最感興趣的項(xiàng)目上，其參考信息也來(lái)源于參與評(píng)分最活躍的用戶中，這就使得推薦結(jié)果的準(zhǔn)確率得到提高。此外，由于減少了二部網(wǎng)絡(luò)中的頂點(diǎn)的個(gè)數(shù)，可以提高算法的執(zhí)行速度。

3 標(biāo)簽傳遞算法

在對(duì)二部網(wǎng)絡(luò)劃分社區(qū)時(shí)，本文用模塊度作為度量社區(qū)劃分結(jié)果質(zhì)量的標(biāo)準(zhǔn)。設(shè)U、V兩部分各有p、q個(gè)頂點(diǎn)，社區(qū)劃分結(jié)果的模塊度定義如下：

這里，用i=1，2，…，p表示集合U中的頂點(diǎn)u1，u2，…，up；用j=1，2，…，q表示集合V中的頂點(diǎn)v1，v2，…，vq；ki、kj分別表示頂點(diǎn)ui、vj的度。用Lui代表頂點(diǎn)ui所歸屬的社區(qū)的標(biāo)簽，用Lvi代表頂點(diǎn)vi所歸屬的社區(qū)的標(biāo)簽，指示函數(shù)δ(Lui，Luj)的定義為：

若ui與vj歸屬于同一個(gè)社區(qū)，則δ(Lui，Luj)的值為1；否則值為0。式（6）中的M為二部網(wǎng)絡(luò)中所有邊上的評(píng)分值之和：。為了找出具有最大模塊度的社區(qū)劃分，文中對(duì)網(wǎng)絡(luò)中每一對(duì)頂點(diǎn)定義了一個(gè)模塊度增量，頂點(diǎn)ui、vj之間的模塊度增量定義為：

所有頂點(diǎn)對(duì)的模塊度增量構(gòu)成了p*q的矩陣B=[bij]，稱為模塊度增量矩陣。

對(duì)照式（6）和（7）可以發(fā)現(xiàn)，頂點(diǎn)ui、vj之間的模塊度增量bij的值的大小表示整體模塊度增加的程度。如果模塊度增量bij較大，頂點(diǎn)ui與vj就歸屬于同一個(gè)社區(qū)。所以本文的算法目的就是逐次挑選模塊度增量值較大的頂點(diǎn)對(duì)，將其劃歸同一個(gè)社區(qū)之中。根據(jù)這樣的想法，本文提出標(biāo)簽傳遞算法來(lái)劃分社區(qū)。

首先，在原有網(wǎng)絡(luò)的頂點(diǎn)集上構(gòu)造一個(gè)帶權(quán)完全圖，該圖每條邊上的權(quán)重為它所連接的節(jié)點(diǎn)對(duì)的模塊度增量。一開(kāi)始，把一個(gè)頂點(diǎn)看成一個(gè)社區(qū)，并給它定一個(gè)標(biāo)簽，然后將各個(gè)頂點(diǎn)的標(biāo)簽根據(jù)邊上的模塊度增量在完全圖中進(jìn)行傳遞：節(jié)點(diǎn)之間傳遞標(biāo)簽的概率會(huì)隨著模塊度增量的增大而增大。如此，它們就越有可能被劃歸到同一個(gè)社區(qū)。在傳遞標(biāo)簽時(shí)，通過(guò)迭代把每個(gè)節(jié)點(diǎn)的標(biāo)簽根據(jù)其鄰居節(jié)點(diǎn)的標(biāo)簽來(lái)逐次更新，將每個(gè)頂點(diǎn)的標(biāo)簽更新為其鄰居頂點(diǎn)中邊的權(quán)重值之和最大的標(biāo)簽。因?yàn)檫吷系臋?quán)重值就是模塊度增量，而邊上模塊度增量又與該頂點(diǎn)連接，其值越大，取相連接的節(jié)點(diǎn)的標(biāo)簽的可能性就越大，它們也就越可能被劃分到同一個(gè)社區(qū)。這樣可以將模塊度增量較大節(jié)點(diǎn)對(duì)劃歸到同一個(gè)社區(qū)中。重復(fù)上述標(biāo)簽傳遞過(guò)程，直到網(wǎng)絡(luò)中的頂點(diǎn)的標(biāo)簽不再變化時(shí)為止。此時(shí)得到的社區(qū)劃分會(huì)具有最大的整體模塊度。

基于模塊度增量和標(biāo)簽傳遞的社區(qū)挖掘算法的框架如下：

經(jīng)過(guò)算法1 的處理，將稠密的用戶和項(xiàng)目分別劃分為若干社區(qū)，其中用戶的每個(gè)社區(qū)與一個(gè)項(xiàng)目社區(qū)對(duì)應(yīng)。對(duì)于非稠密用戶，將其劃歸到其感興趣的項(xiàng)目最多的社區(qū)之中。設(shè)I(uj)為非稠密用戶uj的感興趣的項(xiàng)目集合，記I(Ci)為第i個(gè)社區(qū)Ci中的項(xiàng)目集合，將用戶uj劃歸到其感興趣的項(xiàng)目最多的社區(qū)Ck(j)：

社區(qū)的再劃分實(shí)際上是將用戶和項(xiàng)目的集合各自劃分成許多不重疊的社區(qū)，在用戶社區(qū)和項(xiàng)目社區(qū)之間存在一一對(duì)應(yīng)關(guān)系，相對(duì)應(yīng)的用戶社區(qū)和項(xiàng)目社區(qū)一起構(gòu)成了一個(gè)網(wǎng)絡(luò)的子圖。在該子圖中，用戶之間和項(xiàng)目之間的相似度如果較高，用戶和項(xiàng)目之間的相關(guān)性也會(huì)較高。

算法1 的標(biāo)簽傳播規(guī)則讓模塊度增量較大的節(jié)點(diǎn)對(duì)之間的標(biāo)簽傳播概率越大，這本質(zhì)上是在使模塊度最大化，這樣使得算法的社區(qū)劃分的準(zhǔn)確率較高。由于算法1 的標(biāo)簽傳播過(guò)程簡(jiǎn)單易行，每輪迭代所需的時(shí)間為O(max{p，q})，因此算法時(shí)間復(fù)雜度較低。算法1 的另一個(gè)優(yōu)點(diǎn)是，社區(qū)的個(gè)數(shù)無(wú)需作為參數(shù)預(yù)先指定，而是由算法取得使模塊度最大化的社區(qū)的個(gè)數(shù)。

4 基于社區(qū)劃分的推薦算法

利用算法1 將用戶和項(xiàng)目劃分成社區(qū)，使得最相似的用戶以及他們最感興趣的項(xiàng)目劃歸于同一個(gè)社區(qū)，就可以基于社區(qū)的信息進(jìn)行推薦。本文在社區(qū)挖掘的基礎(chǔ)上，提出對(duì)指定用戶的項(xiàng)目評(píng)分的推薦算法。記用戶v所在的社區(qū)為U(v)，項(xiàng)目j所在的社區(qū)為I(j)，用戶u和v所在的社區(qū)U(u)和U(v)的相似度為SU(u，v)，項(xiàng)目i和j所在的社區(qū)I(i)和I(j)的相似度為SI(i，j)。算法主要有4步：

步驟1 計(jì)算項(xiàng)目社區(qū)之間、用戶社區(qū)之間的相似度。

項(xiàng)目社區(qū)I(i)和I(j)之間的相似度定義為：

這里，sim(g，h)為項(xiàng)目g和h的相似度，可以通過(guò)計(jì)算評(píng)分矩陣相應(yīng)列向量的余弦相似度或者相關(guān)系數(shù)得到。

用戶社區(qū)U(i)、U(j)之間的相似度定義為：

其中，sim(g，h)為用戶g和h的相似度，可以通過(guò)計(jì)算評(píng)分矩陣相應(yīng)行向量的余弦相似度或者相關(guān)系數(shù)得到。

步驟2 計(jì)算每一個(gè)用戶u的相對(duì)于項(xiàng)目j的評(píng)分均值

其中：I(u)為用戶所評(píng)價(jià)的項(xiàng)目的集合，SI(j，k)為項(xiàng)目j和k所在的社區(qū)I(j)和I(k)的相似度。

步驟3 根據(jù)用戶間的評(píng)分偏差和用戶的歷史評(píng)分，預(yù)測(cè)用戶對(duì)未評(píng)分物品的評(píng)分。還要計(jì)算用戶u對(duì)項(xiàng)目j的評(píng)分puj。在對(duì)用戶和項(xiàng)目進(jìn)行社區(qū)劃分后，首先判斷用戶u和項(xiàng)目j的社區(qū)U(u)和I(j)是否為相對(duì)應(yīng)社區(qū)。若是，用戶u對(duì)項(xiàng)目j的評(píng)分puj可以在U(u)和I(j)構(gòu)成的子圖中進(jìn)行，計(jì)算公式為：

若用戶u和項(xiàng)目j的社區(qū)U(u)和I(j)不是相對(duì)應(yīng)社區(qū)，則要參考其他社區(qū)的信息以及社區(qū)間的相似度來(lái)計(jì)算用戶u對(duì)項(xiàng)目j的評(píng)分puj，計(jì)算公式為：

其中，user(j)是給項(xiàng)目j評(píng)分過(guò)的用戶的集合，SU(u，v)為用戶u和v所在的社區(qū)之間的相似度。在式（13）中，(j)為用戶u對(duì)項(xiàng)目j的所在的社區(qū)的所有項(xiàng)目評(píng)分的均值，后面的一項(xiàng)為對(duì)用戶u對(duì)項(xiàng)目j的偏好值的估計(jì)。這個(gè)估計(jì)值為所有給項(xiàng)目j評(píng)分過(guò)的用戶v對(duì)項(xiàng)目j的偏好值的加權(quán)平均。權(quán)重為用戶u與v所在社區(qū)的歸一化相似度。計(jì)算過(guò)程如圖3所示。

圖3 評(píng)分puj的計(jì)算過(guò)程Fig.3 Computation of the score puj

從式（13）可見(jiàn)，對(duì)于某個(gè)用戶來(lái)說(shuō)，與他所在的社區(qū)相似度較高的社區(qū)里的用戶的評(píng)分對(duì)他的推薦結(jié)果會(huì)產(chǎn)生較大的影響。

步驟4 對(duì)所得到的對(duì)項(xiàng)目的預(yù)測(cè)評(píng)分進(jìn)行排序，將其中得分最高的N個(gè)項(xiàng)目向用戶進(jìn)行推薦。

下面給出基于社區(qū)挖掘的社交網(wǎng)絡(luò)推薦算法的框架：

算法2 通過(guò)對(duì)二部圖進(jìn)行社區(qū)挖掘，對(duì)用戶進(jìn)行分類，然后根據(jù)用戶對(duì)項(xiàng)目的偏好以及用戶所在的社區(qū)間的相似度，再參考相關(guān)內(nèi)容進(jìn)行推薦。具有簡(jiǎn)單易行、效率高、推薦準(zhǔn)確性較高的優(yōu)點(diǎn)，還能有助于挖掘用戶對(duì)一些項(xiàng)目潛在的偏好。

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

本文用電影網(wǎng)站數(shù)據(jù)集MovieLens 和Recsys 提供的Yelp消費(fèi)評(píng)論的數(shù)據(jù)集，對(duì)上述基于社區(qū)挖掘的推薦算法CMBR進(jìn)行實(shí)驗(yàn)，并將實(shí)驗(yàn)結(jié)果與類似的推薦算法進(jìn)行了對(duì)比分析。文中采用Matlab 編碼，在中央處理器為3.2 GHz，內(nèi)存為8 GB，Windows 7，64位操作系統(tǒng)的計(jì)算機(jī)上運(yùn)行。

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

5.1.1 MovieLens數(shù)據(jù)集

電影網(wǎng)站MovieLens數(shù)據(jù)集由GroupLens Research 實(shí)驗(yàn)室搜集整理。該數(shù)據(jù)集包含一些用戶信息、電影信息以及電影評(píng)分，是一個(gè)最常用的實(shí)驗(yàn)數(shù)據(jù)集。本文選擇數(shù)據(jù)集中100K大小的數(shù)據(jù)，包括1 682 部電影、943 個(gè)用戶、100 000 個(gè)評(píng)分，評(píng)分值為1～5。

5.1.2 Yelp消費(fèi)評(píng)論數(shù)據(jù)集

此數(shù)據(jù)集記錄了Yelp 網(wǎng)站在美國(guó)亞利桑那州的每個(gè)顧客、每個(gè)商家的信息和他們的評(píng)分。該數(shù)據(jù)集被劃分為訓(xùn)練集和測(cè)試集兩部分：訓(xùn)練集中有商家12 742 個(gè)、顧客51 296個(gè)、評(píng)分252 863 條；測(cè)試集中有商家8 341 個(gè)、顧客15 001 個(gè)、評(píng)分36 404條。顧客的評(píng)分值為1～5。

上述兩個(gè)數(shù)據(jù)集都是比較稀疏的。數(shù)據(jù)的稀疏度為未評(píng)分的數(shù)目占總體的百分比，稀疏度越大，數(shù)據(jù)集就越稀疏。

MovieLens 數(shù)據(jù)集共有943 個(gè)用戶、1682 部電影以及100 000 條電影評(píng)價(jià)，訓(xùn)練集的稀疏度約為93.695%；Yelp 消費(fèi)評(píng)論數(shù)據(jù)集中有20 萬(wàn)個(gè)顧客評(píng)分?jǐn)?shù)據(jù)，其中有22 829 個(gè)用戶僅有一個(gè)評(píng)分，Yelp訓(xùn)練集的稀疏度大約為99.961%。

5.2 推薦結(jié)果的評(píng)價(jià)指標(biāo)

對(duì)于推薦結(jié)果的質(zhì)量評(píng)估的最常用的指標(biāo)是平均絕對(duì)差（Mean Absolute Error，MAE）和準(zhǔn)確率（precision）。

5.2.1 平均絕對(duì)差

在統(tǒng)計(jì)學(xué)中，平均絕對(duì)誤差（MAE）是兩個(gè)連續(xù)變量之間的差值。在推薦問(wèn)題中，平均絕對(duì)差定義為用戶對(duì)項(xiàng)目的實(shí)際評(píng)分與推薦算法計(jì)算的評(píng)分之間的差。設(shè)用戶對(duì)k個(gè)項(xiàng)目的實(shí)際評(píng)分值為{r1，r2，…，rk}，推薦算法計(jì)算得到的相應(yīng)的評(píng)分值為{p1，p2，…，pk}，平均絕對(duì)偏差的計(jì)算公式如下：

由式（14）可以看出，較小的MAE 值表示推薦結(jié)果的精度較高。

5.2.2 準(zhǔn)確率

在推薦問(wèn)題中，設(shè)用戶對(duì)k個(gè)項(xiàng)目的實(shí)際評(píng)分值為R={r1，r2，…，rk}，而推薦算法計(jì)算得到的相應(yīng)的評(píng)分值為I={p1，p2，…，pk}，那么準(zhǔn)確率的計(jì)算公式如下：

即為所推薦的正確項(xiàng)目的個(gè)數(shù)所占的百分比，其值在0～1，推薦結(jié)果越精確，準(zhǔn)確率的值就越高。

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

本文把基于二部網(wǎng)絡(luò)劃分的標(biāo)簽傳遞社區(qū)挖掘推薦算法（CMBR）與其他4 種算法的預(yù)測(cè)結(jié)果準(zhǔn)確度和平均絕對(duì)差進(jìn)行比較。這4 個(gè)算法分別是基于雙向關(guān)聯(lián)規(guī)則項(xiàng)目評(píng)分預(yù)測(cè)的推薦算法（Collaborative Filtering recommendation algorithm based on item rating prediction using Bidirectional Association Rules，BAR-CF）［27］、基于項(xiàng)目評(píng)分預(yù)測(cè)的推薦算法（Collaborative Filtering recommendation algorithm based on Item Rating prediction，IR-CF）［28］、基于網(wǎng)絡(luò)鏈接預(yù)測(cè)的用戶偏好預(yù)測(cè)方法（user Preferences prediction method based on network Link Prediction，PLP）［29］和改進(jìn)的基于用戶的協(xié)同過(guò)濾的方法（Modified User-based Collaborative Filtering，MU-CF）［30］。從數(shù)據(jù)集中，觀察到用戶評(píng)論的條數(shù)的分布大部分集中在4～20，也就是說(shuō)用戶側(cè)頂點(diǎn)的近鄰個(gè)數(shù)集中在4～20。為了測(cè)試在各種近鄰個(gè)數(shù)下不同算法的結(jié)果的平均絕對(duì)差，本文在實(shí)驗(yàn)中對(duì)4～20、間隔為4 的不同近鄰數(shù)進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果如表1所示。

表1 兩個(gè)數(shù)據(jù)集上各種算法在不同近鄰個(gè)數(shù)下的平均絕對(duì)差Tab.1 Average absolute errors of various algorithms on two datasets under different neighbor numbers

由表1 可以看出，算法CMBR 在兩個(gè)數(shù)據(jù)集上對(duì)于各種近鄰數(shù)都可以取得最低的MAE 值。這說(shuō)明算法CMBR 能夠比其他算法取得更好的推薦效果。同時(shí)也可以看出，較大的近鄰數(shù)可以取得準(zhǔn)確率較高的推薦結(jié)果。

為了進(jìn)行更全面的性能比較，本文采用5 折交叉驗(yàn)證進(jìn)行實(shí)驗(yàn)，需要進(jìn)行5次重復(fù)實(shí)驗(yàn)。文中將數(shù)據(jù)集隨機(jī)地分成5個(gè)部分。在每次實(shí)驗(yàn)中用其中的4 個(gè)部分作為訓(xùn)練集、剩下的一個(gè)部分作為測(cè)試集。如果5次實(shí)驗(yàn)得到的MAE值的標(biāo)準(zhǔn)差小于閾值0.024，則取5 次測(cè)試結(jié)果的MAE 值的平均值作為MAE估計(jì)值。各種算法對(duì)于MovieLens和Yelp數(shù)據(jù)集上的平均MAE值如圖4所示。

由圖4可見(jiàn)，隨著近鄰數(shù)的增加，各種算法的MAE值都有所降低。但在相同的數(shù)量的最近鄰居時(shí)，本文的推薦算法CMBR 的平均絕對(duì)偏差（MAE）比其他的推薦算法更小，推薦結(jié)果的精度更高，這表明文中所提出的基于二部網(wǎng)絡(luò)劃分的標(biāo)簽傳遞社區(qū)挖掘推薦算法CMBR優(yōu)于其他的推薦算法。

圖4 兩個(gè)數(shù)據(jù)集上各種算法在不同近鄰數(shù)下的平均MAE值對(duì)比Fig.4 Average MAE value comparison of various algorithms on two datasets under different neighbor numbers

本文還測(cè)試了所提出的CMBR 算法的推薦結(jié)果與真實(shí)結(jié)果進(jìn)行比較得出的準(zhǔn)確率，并與其他四個(gè)算法在兩個(gè)數(shù)據(jù)集上進(jìn)行了比較，用得分最高的10 個(gè)項(xiàng)目作為推薦結(jié)果，其準(zhǔn)確率的比較如圖5所示。

圖5 各種算法推薦結(jié)果的準(zhǔn)確率比較Fig.5 Precision comparison of recommendation results of various algorithms

由圖5 可以看出，相較于其他的推薦算法，算法CMBR 在兩個(gè)數(shù)據(jù)集上皆具有較高的準(zhǔn)確率，取得較精確的推薦結(jié)果，說(shuō)明本文提出的基于二部網(wǎng)絡(luò)劃分的標(biāo)簽傳遞社區(qū)挖掘推薦算法CMBR 明顯優(yōu)于其他的推薦算法。本文算法之所以能有效地提高推薦結(jié)果的準(zhǔn)確率，是因?yàn)樗浞掷昧硕繄D的社區(qū)信息和用戶-項(xiàng)目的評(píng)分信息，有機(jī)結(jié)合了用戶和項(xiàng)目之間的評(píng)分信息和二部網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)［31］。

6 結(jié)語(yǔ)

本文提出了基于模塊度和標(biāo)簽傳遞的推薦算法，該方法基于二部網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)信息，充分利用了用戶所在的社區(qū)之間的相似性，以及項(xiàng)目之間、用戶之間的相似性來(lái)挖掘用戶可能感興趣的項(xiàng)目。實(shí)驗(yàn)結(jié)果也證明，該算法可以取得比其他類似方法更高準(zhǔn)確率的推薦結(jié)果。