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

賀懷清，范志亮，劉浩翰

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

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

賀懷清，范志亮，劉浩翰

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1創(chuàng)新點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4算法思想

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

2.5算法步驟

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

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

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

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

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

4）評(píng)分預(yù)測(cè)。根據(jù)近鄰用戶(hù)集中用戶(hù)對(duì)目標(biāo)項(xiàng)目的評(píng)分，利用修正的預(yù)測(cè)式（5）計(jì)算目標(biāo)用戶(hù)對(duì)目標(biāo)項(xiàng)目的評(píng)分

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

2.6算法描述

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

輸出：預(yù)測(cè)評(píng)分向量pre

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

1）將G中各個(gè)點(diǎn)初始化為一個(gè)獨(dú)立的社區(qū)，計(jì)算模塊性度值Q1

2）for i∈V do

3）for j∈V do

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

5）end for

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

7）end for

8）用模塊度計(jì)算公式（1）來(lái)計(jì)算此時(shí)模塊度值Q2

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

10）end if

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

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

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

14）return pre

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

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

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

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

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

RMSE的定義為

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

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

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

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

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

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

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

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

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

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

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

4　結(jié)語(yǔ)

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

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

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

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

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

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

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

[7]吳祖峰,王鵬飛,秦志光,等.改進(jìn)的Louvain社團(tuán)劃分算法[J].電子科技大學(xué)學(xué)報(bào),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基金項(xiàng)目：民航科技項(xiàng)目（MHRDZ201207）；天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計(jì)劃重點(diǎn)項(xiàng)目（14JCZDJC32500）；中國(guó)民航大學(xué)預(yù)研重大項(xiàng)目（3122013P003）

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