賀懷清，范志亮，劉浩翰

（中國民航大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，天津　300300）

基于網(wǎng)絡(luò)社區(qū)劃分的協(xié)同推薦算法

賀懷清，范志亮，劉浩翰

（中國民航大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，天津300300）

為提高協(xié)同推薦系統(tǒng)的準(zhǔn)確性及可擴(kuò)展性，提出基于網(wǎng)絡(luò)社區(qū)劃分的協(xié)同推薦算法。首先利用用戶好友數(shù)據(jù)構(gòu)建用戶關(guān)系網(wǎng)，然后利用社區(qū)劃分算法對用戶進(jìn)行社區(qū)劃分，使得劃分在同一社區(qū)的用戶有共同話題和愛好，接著利用同一社區(qū)的用戶尋找目標(biāo)用戶近鄰集，最后根據(jù)近鄰用戶對未知項目的評分預(yù)測目標(biāo)用戶的評分。通過實驗證明：在近鄰數(shù)小于27時，該推薦算法優(yōu)于基于用戶模糊聚類的協(xié)同過濾算法。

協(xié)同過濾；平均絕對誤差；均方根誤差；用戶關(guān)系網(wǎng)；社區(qū)劃分

在信息爆炸的時代，人們每天需要面對數(shù)以億計的信息數(shù)據(jù)，如何快速、便捷的從中發(fā)現(xiàn)其所關(guān)注的信息，成為人們所關(guān)注的問題。推薦系統(tǒng)可幫助人們選擇其可能喜歡的信息，有效地解決信息過載問題。

協(xié)同過濾[1]是應(yīng)用較為成熟的一種推薦技術(shù)，主要包括基于用戶的和基于項目的協(xié)同推薦。其主要是利用相似性用戶[2]的評分來預(yù)測目標(biāo)用戶的評分。協(xié)同推薦主要面臨兩個困難：

1）系統(tǒng)擴(kuò)展能力差在系統(tǒng)用戶數(shù)增多時，計算量會線性增加，使得系統(tǒng)響應(yīng)能力變差。

2）數(shù)據(jù)的稀疏性造成推薦的準(zhǔn)確度不高本文通過對協(xié)同過濾算法分析發(fā)現(xiàn)，其在相似度計算時，只單純地基于用戶評分矩陣進(jìn)行預(yù)測，忽略用戶之間的社會關(guān)系，這是導(dǎo)致其準(zhǔn)確度不高的又一原因。

針對以上困難，很多學(xué)者將聚類算法引入到協(xié)同推薦中。李華等[3]將模糊聚類算法與協(xié)同過濾算法結(jié)合從用戶角度出發(fā)提出了基于用戶模糊聚類的推薦方法。熊忠陽等[4]則從項目角度出發(fā)提出了基于項目分類的協(xié)同過濾推薦算法。但無論是用戶聚類還是項目聚類，在進(jìn)行聚類前首先需確定聚類數(shù)k，而最優(yōu)聚類數(shù)目k的確定是所有聚類算法所面臨的共同挑戰(zhàn)。還有些學(xué)者將社會網(wǎng)絡(luò)引入?yún)f(xié)同過濾算法中，通過用戶間的信任關(guān)系構(gòu)建信任網(wǎng)絡(luò)，利用信任網(wǎng)絡(luò)及用戶信息尋找近鄰用戶集。盡管這種方法提高了協(xié)同推薦的準(zhǔn)確度，但在網(wǎng)絡(luò)規(guī)模較大時，尋找近鄰用戶所需的計算量會線性增加。因此提出了基于網(wǎng)絡(luò)社區(qū)劃分的協(xié)同推薦算法，利用用戶信息構(gòu)建用戶關(guān)系網(wǎng)絡(luò)，并用Louvain社區(qū)劃分算法對用戶關(guān)系網(wǎng)[5]進(jìn)行社區(qū)劃分，然后利用目標(biāo)用戶所在社區(qū)的其他用戶構(gòu)建近鄰集，最后利用近鄰集的用戶對目標(biāo)用戶進(jìn)行預(yù)測。

1　Louvain社區(qū)劃分算法

社區(qū)劃分就是發(fā)現(xiàn)社會網(wǎng)絡(luò)中所固有的社區(qū)結(jié)構(gòu)[6]，將具有共同話題和興趣的用戶劃分到同一社區(qū)，使得網(wǎng)絡(luò)中社區(qū)內(nèi)用戶點的聯(lián)系較緊密，社區(qū)與社區(qū)間的聯(lián)系較稀疏。

目前社區(qū)劃分算法主要分為2種：①分離法，找出社區(qū)之間的邊把它們從網(wǎng)絡(luò)中移除；②聚合法，將聯(lián)系緊密的點聚合為一個社區(qū)，并通過變量函數(shù)實現(xiàn)聚合。一般而言，聚合算法比分離算法劃分的準(zhǔn)確，且效率也相對比較高。Louvain算法[7]是一種聚合社區(qū)[8]劃分算法，是基于模塊度[9-10]進(jìn)行社區(qū)劃分的一種方法。在一個有權(quán)的網(wǎng)絡(luò)中，模塊度的定義為

其中：Aij為連接節(jié)點i與j邊的權(quán)值；m為網(wǎng)絡(luò)中邊的數(shù)量；ki為節(jié)點i的度；kj為節(jié)點j的度；ci為i所屬的社區(qū)。?（ci，c）j為節(jié)點i與節(jié)點j是否為同一個社區(qū)，如在同一個社區(qū)?（ci，c）j=1，否則?（ci，c）j=0。

Louvain算法的基本思想是遍歷網(wǎng)絡(luò)中的所有點，將其從所屬的社區(qū)中取出，然后計算該點加入到別的社區(qū)所產(chǎn)生的模塊度增量，將該節(jié)點加入模塊度增量最大的社區(qū)，最后將各個社區(qū)再合并為一個點。重復(fù)上述步驟，直到模塊度不再增加。

2　基于網(wǎng)絡(luò)社區(qū)劃分的協(xié)同推薦算法

該算法將社會網(wǎng)絡(luò)中社區(qū)劃分算法與協(xié)同推薦算法相結(jié)合，利用社區(qū)劃分算法將原始用戶關(guān)系網(wǎng)分成一個個社區(qū)，使社區(qū)中的用戶聯(lián)系比較緊密，即使未建立好友關(guān)系的用戶間也存在共同的特性。社區(qū)劃分后，有利于協(xié)同過濾算法中目標(biāo)用戶近鄰集的構(gòu)建，彌補(bǔ)了協(xié)同推薦算法不可擴(kuò)展的缺陷。同時用戶關(guān)系網(wǎng)的引入更全面地考慮了用戶間的關(guān)系，彌補(bǔ)了協(xié)同推薦算法中僅依靠用戶評分尋找相似用戶的不足。

2.1創(chuàng)新點

本文采用的基于網(wǎng)絡(luò)社區(qū)劃分的協(xié)同過濾算法，與以往的協(xié)同推薦算法相比主要有2個創(chuàng)新點：

1）將Louvain社區(qū)劃分算法與協(xié)同推薦算法相結(jié)合利用用戶好友數(shù)據(jù)構(gòu)建的關(guān)系網(wǎng)絡(luò)通過Louvain算法進(jìn)行社區(qū)劃分，實現(xiàn)了用戶的聚類過程，縮小了在協(xié)同過濾算法中相似用戶的尋找范圍，有利于協(xié)同過濾算法中目標(biāo)用戶最近鄰集的構(gòu)建。

2）提出用戶關(guān)系相似度傳統(tǒng)相似度計算僅依據(jù)用戶的評分向量，忽略了用戶間的社會關(guān)系。本文提出的用戶關(guān)系相似度中，不但考慮用戶的購買行為而且考慮用戶間關(guān)系。將用戶間關(guān)系分為直接朋友關(guān)系和隱式朋友關(guān)系，并提出了隱式朋友關(guān)系的計算方法。

2.2用戶關(guān)系網(wǎng)

用戶關(guān)系網(wǎng)反映了網(wǎng)絡(luò)中用戶間的緊密程度。在網(wǎng)絡(luò)中直接相連的兩個用戶表明是好友關(guān)系，即用戶是通過添加并取得對方同意后形成的好友關(guān)系。網(wǎng)絡(luò)中未相連的用戶不一定就是陌生關(guān)系，他們之間可能存在隱式的朋友關(guān)系。用戶關(guān)系網(wǎng)可以用一個無向圖G表示，G中的每個點表示一個用戶，用戶相連表示是用戶間是朋友關(guān)系，連線上的權(quán)值反映了用戶間關(guān)系的強(qiáng)弱。無向圖G中的信息可以存儲在其對應(yīng)的鄰接矩陣V中。V可表示為

其中：m表示網(wǎng)絡(luò)中用戶的數(shù)目，V中任意一點vij為無向圖G中用戶i與j連接的權(quán)值。

如圖1所示，A、B、C、D 4個用戶構(gòu)建了一個用戶關(guān)系網(wǎng)，可看出A與B、C是朋友關(guān)系，C與A、B、D是朋友關(guān)系，B與A、C是朋友關(guān)系，D只與C是朋友關(guān)系。同時還可看出A與B朋友關(guān)系最強(qiáng)，C與D朋友關(guān)系最強(qiáng)。圖1關(guān)系網(wǎng)對應(yīng)的鄰接矩陣V可表示為

圖1　用戶關(guān)系網(wǎng)Fig.1　User relationship network

關(guān)系網(wǎng)中權(quán)值的設(shè)定在用戶關(guān)系網(wǎng)中，權(quán)值反映了用戶間好友關(guān)系的強(qiáng)弱，權(quán)值越大表明用戶間的好友關(guān)系越緊密。本文使用的是Last.fm音樂數(shù)據(jù)集，因此用戶關(guān)系網(wǎng)中權(quán)值設(shè)定規(guī)則如下：

1）如果用戶間僅是朋友關(guān)系，則權(quán)值為1；

2）如果用戶間是朋友關(guān)系且收聽了同一藝術(shù)家的音樂，則權(quán)值為2；

3）如果用戶間是朋友關(guān)系且有過聊天行為，則權(quán)值為3；

4）如果用戶間是朋友關(guān)系，收聽同一藝術(shù)家的音樂且有過聊天行為，則權(quán)值為4；

5）如果用戶間是非朋友關(guān)系，無論其是否與其他用戶收聽同一藝術(shù)家的音樂或有過聊天行為，權(quán)值都為0。

2.3用戶關(guān)系相似度

文獻(xiàn)[11]通過實驗證明了人們更加傾向于相信自己的朋友，而非是與自己相似度最高的相似用戶。因此在用戶關(guān)系網(wǎng)中，本文將相似度的計算公式進(jìn)行了改進(jìn)，考慮了用戶關(guān)系對相似度的影響，其定義如下

其中：S（un，um）代表用戶n與m的用戶關(guān)系相似度；w（un，um）為用戶n與m之間用戶關(guān)系函數(shù)；α為調(diào)節(jié)因子，調(diào)節(jié)在用戶關(guān)系相似度計算中用戶關(guān)系與用戶評分所占的比重。sim（un，um）表示用戶n與m之間的Pearson相關(guān)相似性，其計算式為

用戶關(guān)系函數(shù)w（un，um）的公式為

其中：numn、numm分別表示用戶n與用戶m各自的好友數(shù)；numnm表示用戶n與m共同的好友數(shù)。

式（4）不但考慮了用戶間直接的朋友關(guān)系，還考慮了陌生用戶間可能存在的隱式朋友關(guān)系。在現(xiàn)實生活中，如果兩個人共同的朋友越多，則這兩個人成為朋友的幾率越大。該公式充分考慮了這一點。而在傳統(tǒng)的用戶關(guān)系函數(shù)中，并未考慮用戶間隱式的朋友關(guān)系，一般當(dāng)兩個用戶不相識時，設(shè)定w（un，um）=0。

2.4算法思想

算法主要思想是：首先利用用戶間的好友關(guān)系建立一個用戶關(guān)系無向圖，然后利用Louvain算法將由用戶好友關(guān)系構(gòu)成的社會網(wǎng)絡(luò)劃分成很多社區(qū)，使社區(qū)內(nèi)用戶間的聯(lián)系比較緊密，社區(qū)間的聯(lián)系較為稀疏。接著查詢目標(biāo)用戶所在的社區(qū)，利用目標(biāo)用戶所在社區(qū)的社會關(guān)系，結(jié)合本文提出的用戶關(guān)系相似度得到目標(biāo)用戶的最近鄰集合，最后根據(jù)最近鄰用戶的評分預(yù)測目標(biāo)用戶的評分。

2.5算法步驟

基于Louvain社區(qū)劃分的協(xié)同過濾算法框架示意圖，如圖2所示，具體實現(xiàn)步驟如下：

圖2　算法框架示意圖Fig.2　Algorithm schematic framework

1）首先根據(jù)原始數(shù)據(jù)用戶間的關(guān)系構(gòu)建用戶關(guān)系網(wǎng)G（M，E），并將網(wǎng)絡(luò)中的信息存儲于其對應(yīng)的鄰接矩陣V。其中M為關(guān)系網(wǎng)中用戶節(jié)點的集合，E為網(wǎng)絡(luò)中邊集，邊上的權(quán)值表示用戶之間的關(guān)系。

2）利用Louvain社區(qū)劃分算法對用戶關(guān)系網(wǎng)進(jìn)行劃分，使得劃分后每個社區(qū)內(nèi)用戶有著相同興趣愛好。

3）構(gòu)建近鄰用戶集。查找目標(biāo)用戶所在社區(qū)，利用式（2）計算與目標(biāo)用戶最相似的前n個用戶。

4）評分預(yù)測。根據(jù)近鄰用戶集中用戶對目標(biāo)項目的評分，利用修正的預(yù)測式（5）計算目標(biāo)用戶對目標(biāo)項目的評分

其中：Nu為用戶u的最近鄰集合分別為用戶i和用戶j已評分項的平均值；S（ui，u）j為用戶i與j的用戶關(guān)系相似度；Rj，k為鄰居j對項目k的評分。

2.6算法描述

輸入：用戶關(guān)系網(wǎng)絡(luò)G（V，E），目標(biāo)用戶user，項目items

輸出：預(yù)測評分向量pre

//利用Louvain算法對用戶關(guān)系網(wǎng)絡(luò)G進(jìn)行社區(qū)劃分

1）將G中各個點初始化為一個獨立的社區(qū)，計算模塊性度值Q1

2）for i∈V do

3）for j∈V do

4）利用式（1）計算當(dāng)用戶i屬于用戶j所屬社區(qū)時，模塊增益ΔQ

5）end for

6）將用戶i移入j所屬的社區(qū)，此時對應(yīng)的模塊增益ΔQ最大

7）end for

8）用模塊度計算公式（1）來計算此時模塊度值Q2

9）if Q2＞Q1，轉(zhuǎn)到步驟2），考慮另一個用戶

10）end if

11）將劃分好的各個社區(qū)的點存入community_ table

12）fd_id（user，community_table）→communityid//查找用戶user所屬社區(qū)id

13）prediction（user，items，communityid）→pre//根據(jù)式（5）計算user對items的評分

14）return pre

2.7算法復(fù)雜度分析

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

3.1數(shù)據(jù)集與度量標(biāo)準(zhǔn)

采用Last.fm音樂數(shù)據(jù)集，該數(shù)據(jù)集來源于Last. fm社交音樂網(wǎng)站，該網(wǎng)站同時也是一個社交網(wǎng)站，用戶間可以交流。Last.fm數(shù)據(jù)集中包含1 823個用戶，18 342個音樂家，92 745條用戶聽歌記錄以及12 148條用戶關(guān)系數(shù)據(jù)（記錄了用戶之間是否為朋友）。在實驗中，本文隨機(jī)選取了20%的用戶數(shù)據(jù)作為測試數(shù)據(jù)集，余下的80%作為訓(xùn)練集的數(shù)據(jù)。

在評估推薦的準(zhǔn)確度時，本文主要使用了有平均絕對誤差MAE和平方根誤差RMSE兩個評價指標(biāo)。MAE反映預(yù)測值與真實值的絕對誤差的平均值，RMSE反映預(yù)測值與真實值間的平方差方根。RMSE與MAE值越小，表示推薦的準(zhǔn)確度越高。假設(shè)預(yù)測的用戶評分值為{k1，k2，…，kN}，實際評分值為{t1，t2，…，tN}，MAE定義為

RMSE的定義為

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

實驗1由于α的變化會影響在相似度計算中用戶評分信息與用戶關(guān)系信息所占的比重，因而α的取值可能會影響推薦的準(zhǔn)確度。在實驗中調(diào)節(jié)α的取值，變化范圍為0～1，變化間隔為0.1，觀察MAE的變化，結(jié)果如圖3所示。

圖3　權(quán)重因子對MAE的影響Fig.3　Influence of weighting factor to MAE

由圖3的實驗結(jié)果可得：當(dāng)α=0.6時，MAE值最小，即推薦效果最好。同時從α=0.6的實驗結(jié)果中可以得出在相似度的計算中，用戶關(guān)系占的比重較大，即說明用戶可能更加傾向于購買朋友推薦的商品。

實驗2在α=0.6的條件下，改變近鄰用戶數(shù)k，比較本算法與傳統(tǒng)的協(xié)同過濾算法，以及文獻(xiàn)[3]提出的算法，結(jié)果如圖4和如圖5所示。

圖4　近鄰數(shù)對MAE的影響Fig.4　Influence of neighbor number to MAE

圖5　近鄰數(shù)對RSME的影響Fig.5　Influence of neighbor number to RSME

由圖4的實驗結(jié)果可得：在近鄰數(shù)k<27時，基于社區(qū)劃分的協(xié)同推薦算法優(yōu)于其他兩種算法；在近鄰數(shù)k=27時，本文提出的算法與文獻(xiàn)[3]的算法平均絕對誤差相同，即推薦效果相當(dāng)。由圖5的實驗結(jié)果可以看出：當(dāng)用戶近鄰數(shù)為5～25時，本文提出的算法所得到的預(yù)測值與真實值之間的均方根誤差明顯小于其它兩種算法，這也同樣說明本文提出的算法推薦準(zhǔn)確度較高。在近鄰數(shù)k＞27時，從圖4和圖5中看出：文獻(xiàn)[3]的算法優(yōu)于本文提出的算法。然而在應(yīng)用模糊聚類算法時，需確定最優(yōu)的聚類數(shù)目，而最優(yōu)聚類數(shù)的確定無法通過自適應(yīng)學(xué)習(xí)過程確定，只能通過實驗人為設(shè)定。從這個角度講，本文算法具有整體優(yōu)勢。

實驗3在α=0.6，k=25時，將實驗數(shù)據(jù)分為4組，進(jìn)行了4次實驗，比較本文的算法與傳統(tǒng)協(xié)同算法以及文獻(xiàn)[3]的算法在推薦準(zhǔn)確度上的差異，實驗結(jié)果如表1所示。

從表1可以看出：在α=0.6，k=25時，本文提出的算法得到的MAE與RMSE值比其他兩種算法對應(yīng)的MAE與RMSE值要小，這說明本文提出的算法推薦預(yù)測的準(zhǔn)確度要高于文中提到的其他兩種算法。

表1　3種算法預(yù)測結(jié)果Tab.1　Forecasting results of three methods

4　結(jié)語

在大數(shù)據(jù)時代，用戶規(guī)模的不斷擴(kuò)大使得傳統(tǒng)協(xié)同推薦系統(tǒng)的實時響應(yīng)能力變得越來越差，同時由于僅利用用戶評分?jǐn)?shù)據(jù)搜索相似用戶，使得相似用戶尋找不準(zhǔn)確，從而造成推薦準(zhǔn)確度不高。本文提出的算法引入用戶關(guān)系網(wǎng)，利用社區(qū)劃分算法將用戶關(guān)系網(wǎng)劃分，劃分后同一社區(qū)內(nèi)的用戶擁有較高的相似性。本文在相似度計算時，不僅考慮了用戶的評分信息，同時還考慮了用戶間的關(guān)系，包括直接的朋友關(guān)系和隱式朋友關(guān)系，使得相似用戶的尋找更加準(zhǔn)確，從而提高了推薦的準(zhǔn)確度。

[1]馬宏偉,張光衛(wèi),李鵬.協(xié)同過濾推薦算法綜述[J].小型微型計算機(jī)系統(tǒng),2009,30(7):1282-1288.

[2]李春,朱珍敏,高曉芳.基于鄰居決策的協(xié)同推薦算法[J].計算機(jī)工程,2010,36(13):34-36.

[3]李華,張宇,孫俊華.基于用戶模糊聚類的協(xié)同過濾推薦研究[J].計算機(jī)科學(xué),2012,39(12):83-86.

[4]熊忠陽,劉芹,張玉芳,等.基于項目分類的協(xié)同過濾改進(jìn)算法[J].計算機(jī)應(yīng)用研究,2012,29(2):493-496.

[5]薛云霞,李壽山,王中卿.基于社會關(guān)系網(wǎng)絡(luò)的半監(jiān)督情歌分類[J].北京大學(xué)學(xué)報,2014,50(1):61-66.

[6]竇炳林,李澍淞,張世永.基于結(jié)構(gòu)的社會網(wǎng)絡(luò)分析[J].計算機(jī)學(xué)報, 2012,35(4):741-753.

[7]吳祖峰,王鵬飛,秦志光,等.改進(jìn)的Louvain社團(tuán)劃分算法[J].電子科技大學(xué)學(xué)報,2013,42(1):105-108.

[8]MITRA A,SATAPATHY S R,PAUL S.Clustering Analysis in Social NetworkUsingCoveringBasedRoughSet[C]//InternationalAdvanceComputing Conference,2013:476-481.

[9]NEWMANMEJ,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):1-15.

[10]CHEN MINGMING,KONSTANTIN KUZMIN.Community detection via maximization of modularity and its variants[J].Computational Social Systems,2014,1(1):46-65.

[11]RASHMI SINHA,KIRSTEN SWEARINGEN.Comparing Recommendations Made byOnline Systems and Friends[C]//DELOS-NSF Workshop：Personalisation and Recommender Systems in Digital Libraries. 2001.

（責(zé)任編輯：楊媛媛）

Collaborative filtering recommendation algorithm based on network community partition

HE Huaiqing,FAN Zhiliang,LIU Haohan
（College of Computer Science and Technology,CAUC,Tianjin 300300,China）

In order to raise the accuracy and extensibility of collaborative filtering recommendation，a collaborative filtering recommendation based on network community is proposed.First,a network of users could be built by the metadata about friends.Then the network of users could be divided by community partition algorithm to make sure that the same community of users have similar interests.The nearest neighbour set of target users are found by users of the same community.Finally,scores of target users are forecasted according to neighbour users’scoring to unknown projects.Results show that when the number of neighbours is less than 27,the accuracy got by the proposed algorithm is better than the algorithm based on user fuzzy clustering.

collaborative filtering;MAE;RMSE;user network;community division

TP301.6

A

1674-5590（2016）05-0040-05

2015-04-08；

2015-05-15基金項目：民航科技項目（MHRDZ201207）；天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計劃重點項目（14JCZDJC32500）；中國民航大學(xué)預(yù)研重大項目（3122013P003）

賀懷清（1969—），女，吉林白山人，教授，博士，研究方向為數(shù)據(jù)挖掘、圖形圖像與可視分析.