盛 俊，李 斌，陳 崚

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

0 引言

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

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

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

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

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

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

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

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

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

二部網(wǎng)絡(luò)可用一個無向簡單二部圖G=(U，V，E)來表示，其中，E為G的邊的集合，U和V分別是G的兩部分頂點的集合。U和V兩部分頂點內(nèi)部不存在連接的邊，對于所有邊(u，v) ∈E必有u∈U、v∈V。二部網(wǎng)絡(luò)可以用來描述推薦問題，例如圖1 所示為一個二部網(wǎng)絡(luò)，其中上面部分的節(jié)點表示用戶，下面部分的節(jié)點表示商品，在兩個部分的一些節(jié)點之間的連線上具有權(quán)重，表示上面部分的節(jié)點所代表的用戶對相應(yīng)的商品的評分值，其值的范圍為1～5。這樣就描述了7個用戶對8個商品進行評分的推薦問題。在圖1中，有些商品和用戶的節(jié)點之間沒有連線，說明該用戶尚未對該商品評分，也可能是該項評分丟失了。在這種情況下，帶權(quán)鄰接矩陣中的相應(yīng)的元素aij的值為0。圖1 中的二部網(wǎng)絡(luò)的帶權(quán)鄰接矩陣如圖2 所示，其中每行代表用戶類型的一個頂點，每列代表項目類型的一個頂點。這實際上是推薦問題中的評分矩陣。因此每個推薦問題對應(yīng)了這樣一個加權(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)系密切的頂點所組成的。設(shè)二部網(wǎng)絡(luò)的兩部分頂點分別稱為X部分和Y部分，二部網(wǎng)絡(luò)的社區(qū)挖掘的目的就是要分別把二部網(wǎng)絡(luò)的X部分頂點和Y部分頂點各自劃分為若干個社區(qū)，而且定義兩個部分的社區(qū)之間的對應(yīng)關(guān)系，使得社區(qū)間頂點連接比較稀疏，而社區(qū)內(nèi)頂點之間連接比較稠密。

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

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

2 興趣密度值和稠密用戶

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟2 計算每一個用戶u的相對于項目j的評分均值

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

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

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

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

圖3 評分puj的計算過程Fig.3 Computation of the score puj

從式（13）可見，對于某個用戶來說，與他所在的社區(qū)相似度較高的社區(qū)里的用戶的評分對他的推薦結(jié)果會產(chǎn)生較大的影響。

步驟4 對所得到的對項目的預(yù)測評分進行排序，將其中得分最高的N個項目向用戶進行推薦。

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

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

5 實驗結(jié)果與分析

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

5.1 實驗數(shù)據(jù)集

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

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

5.1.2 Yelp消費評論數(shù)據(jù)集

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

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

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

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

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

5.2.1 平均絕對差

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

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

5.2.2 準(zhǔn)確率

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)語

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