融合隱性社交網(wǎng)絡(luò)社團(tuán)劃分和協(xié)同過(guò)濾的推薦算法

孫海崗，李玲娟

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210023)

推薦系統(tǒng)作為一種能夠根據(jù)用戶習(xí)慣及興趣進(jìn)行信息過(guò)濾和推送的系統(tǒng)，可以在很大程度上彌補(bǔ)搜索引擎的不足，解決信息過(guò)載問(wèn)題［1］。

協(xié)同過(guò)濾是個(gè)性化推薦系統(tǒng)中應(yīng)用最為廣泛的技術(shù)之一［2］。 基于用戶的協(xié)同過(guò)濾算法UserCF 是推薦系統(tǒng)的經(jīng)典算法之一，該算法依據(jù)與目標(biāo)用戶有相似行為的“近鄰”對(duì)項(xiàng)目的興趣來(lái)預(yù)測(cè)目標(biāo)用戶的興趣［3］。 雖然傳統(tǒng)的協(xié)同過(guò)濾算法已得到廣泛應(yīng)用，但是仍存在對(duì)數(shù)據(jù)稀疏敏感、可擴(kuò)展性差等缺點(diǎn)［4］。 針對(duì)這些問(wèn)題，國(guó)內(nèi)外學(xué)者已經(jīng)對(duì)傳統(tǒng)的協(xié)同過(guò)濾算法進(jìn)行了改進(jìn)。 文獻(xiàn)［5］提出了基于SVD 模型的協(xié)同過(guò)濾算法，使用更加稠密的隱向量表示用戶和物品，雖然能在一定程度上降低協(xié)同過(guò)濾對(duì)評(píng)分矩陣稀疏的敏感性，但是容易過(guò)擬合且計(jì)算量大，可擴(kuò)展性仍有待提高。 文獻(xiàn)［6－9］通過(guò)對(duì)用戶進(jìn)行聚類提高了推薦準(zhǔn)確度，但可擴(kuò)展性仍有待提高。 文獻(xiàn)［10－11］提出了基于社交網(wǎng)絡(luò)的協(xié)同過(guò)濾算法，雖然能在一定程度上提高推薦的準(zhǔn)確性，但是需要用戶之間的顯式社交關(guān)系，然而在一些系統(tǒng)（如電影推薦系統(tǒng)）中并不具備這些信息。 總之，各種算法都一定程度上提升了推薦準(zhǔn)確性，但是如何使推薦算法的性能得到全面提升，仍是需要深入研究的問(wèn)題。

本文設(shè)計(jì)了一種融合隱性社交網(wǎng)絡(luò)社團(tuán)劃分和協(xié)同過(guò)濾的推薦算法（Recommendation Algorithm Integrating Implicit Social Network Community Division and Collaborative Filtering，ICDCF）。 該方法先對(duì)用戶做社團(tuán)劃分，再實(shí)施基于用戶的協(xié)同過(guò)濾推薦。在社團(tuán)劃分階段，將用戶對(duì)項(xiàng)目的共同興趣視為社交關(guān)系，利用改進(jìn)的Jaccard 相似系數(shù)衡量用戶間的社交關(guān)系強(qiáng)弱；再基于相似度構(gòu)建用戶隱性社交網(wǎng)絡(luò)（即基于興趣關(guān)系的社交網(wǎng)絡(luò)）；并進(jìn)一步基于譜聚類思想對(duì)隱性社交網(wǎng)絡(luò)進(jìn)行用戶社團(tuán)劃分；最后在劃分的社團(tuán)內(nèi)進(jìn)行協(xié)同過(guò)濾推薦。 在MovieLens-100K 和FilmTrust 數(shù)據(jù)集上與其他算法的對(duì)比實(shí)驗(yàn)結(jié)果驗(yàn)證了ICDCF 算法能同時(shí)提高準(zhǔn)確性和可擴(kuò)展性。

1 相關(guān)知識(shí)

1．1 基于用戶的協(xié)同過(guò)濾推薦算法UserCF

UserCF 算法的框架如圖1 所示。

圖1 UserCF 框架

算法的輸入是記錄了用戶對(duì)項(xiàng)目歷史評(píng)分的評(píng)分矩陣，其中｛U1，U2，…，Un｝表示用戶集，｛I1，I2，…，Im｝表示項(xiàng)目集。 首先，根據(jù)用戶的歷史評(píng)分記錄，使用相似度計(jì)算方法，為目標(biāo)用戶找到具有相似興趣的最近鄰居集；然后通過(guò)最近鄰居對(duì)項(xiàng)目的評(píng)分，預(yù)測(cè)目標(biāo)用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分；最后根據(jù)預(yù)測(cè)結(jié)果，選出評(píng)分高的前N個(gè)項(xiàng)目進(jìn)行推薦［12］。隨著用戶數(shù)、項(xiàng)目數(shù)的增長(zhǎng)，用戶對(duì)項(xiàng)目的評(píng)分矩陣變得稀疏，會(huì)產(chǎn)生用戶相似度計(jì)算不準(zhǔn)確、計(jì)算開銷大等問(wèn)題。

1．2 相似度計(jì)算方法

UserCF 算法的核心是用戶間相似度計(jì)算。 常用的計(jì)算方法有歐幾里德距離、Jaccard 相似系數(shù)、余弦相似度和皮爾遜相關(guān)系數(shù)等。 本文涉及到其中的皮爾遜相關(guān)系數(shù)和Jaccard 相似系數(shù)。

（1） 皮爾遜相關(guān)系數(shù)

皮爾遜相關(guān)系數(shù)的計(jì)算如下

其中，sim（i，j）表示用戶i和用戶j之間的相似度，Iij表示用戶i和用戶j共同評(píng)分的項(xiàng)目集合，Ri，c和Rj，c分別表示用戶i和j對(duì)項(xiàng)目c的評(píng)分，分別表示用戶i和j對(duì)項(xiàng)目評(píng)分的均值。

（2） Jaccard 相似系數(shù)

Jaccard 相似系數(shù)的計(jì)算如下

其中，sim（i，j）表示用戶i和用戶j之間的相似度，Ii和Ij分別表示用戶i和用戶j已評(píng)分的項(xiàng)目集。

皮爾遜相關(guān)系數(shù)的計(jì)算依賴于用戶共同評(píng)分的項(xiàng)目集，如果用戶共同評(píng)分的項(xiàng)目集較小，則存在一定的偶然性，不能為目標(biāo)用戶提供準(zhǔn)確的預(yù)測(cè)。Jacccard 相似度系數(shù)通過(guò)用戶整體評(píng)分信息進(jìn)行相似度計(jì)算，可以有效避免此類問(wèn)題。

1．3 譜聚類與社團(tuán)劃分

譜聚類［13］算法以數(shù)據(jù)集中的樣本為頂點(diǎn)，以樣本間的相似度為頂點(diǎn)間連邊的權(quán)值，構(gòu)建出無(wú)向加權(quán)圖，將聚類問(wèn)題轉(zhuǎn)化為圖的最優(yōu)劃分問(wèn)題，劃分出的子圖內(nèi)的邊權(quán)和盡可能大，子圖間的邊權(quán)和盡可能小。 它能對(duì)任意形狀的樣本空間聚類并能收斂于全局最優(yōu)解。 其總體步驟如下：

（1） 計(jì)算被聚類樣本的相似度矩陣W，該矩陣映射了無(wú)向加權(quán)圖；

（2） 計(jì)算拉普拉斯矩陣并求解其前k個(gè)最小的特征值與特征向量，構(gòu)建特征向量空間，將高維空間的數(shù)據(jù)映射到低維空間；

（3） 利用經(jīng)典的聚類算法對(duì)特征向量空間中的特征向量進(jìn)行聚類。

社團(tuán)劃分旨在從社會(huì)網(wǎng)絡(luò)中發(fā)現(xiàn)模塊化的社團(tuán)結(jié)構(gòu)，社團(tuán)內(nèi)節(jié)點(diǎn)連接緊密，社團(tuán)間節(jié)點(diǎn)連接疏遠(yuǎn)［14］。 社會(huì)網(wǎng)絡(luò)可以用由節(jié)點(diǎn)和邊構(gòu)成的網(wǎng)絡(luò)圖表示，因此社團(tuán)劃分也被稱為圖聚類［15］。 不難看出，譜聚類與社團(tuán)劃分的目標(biāo)是一致的，因此適用于社團(tuán)劃分。

2 ICDCF 算法設(shè)計(jì)與分析

2．1 設(shè)計(jì)思路

本文設(shè)計(jì)融合隱性社交網(wǎng)絡(luò)社團(tuán)劃分和協(xié)同過(guò)濾的推薦算法ICDCF 的出發(fā)點(diǎn)是：減少因稀疏的評(píng)分矩陣中用戶共同評(píng)分項(xiàng)目少使相似度計(jì)算不準(zhǔn)確而給推薦準(zhǔn)確性帶來(lái)的負(fù)面影響，以及搜索近鄰計(jì)算量大對(duì)協(xié)同過(guò)濾推薦時(shí)間效率的負(fù)面影響，使推薦準(zhǔn)確性和可擴(kuò)展性都得到提升。

針對(duì)UserCF 算法搜索近鄰時(shí)相似度計(jì)算開銷大的問(wèn)題，考慮采用先對(duì)用戶做社團(tuán)劃分，再在社團(tuán)內(nèi)進(jìn)行協(xié)同過(guò)濾推薦的策略。 將用戶對(duì)項(xiàng)目的共同興趣（共同評(píng)價(jià)項(xiàng)目的情況）視為社交關(guān)系，用相似度表示關(guān)系的強(qiáng)弱，以用戶為節(jié)點(diǎn)，以用戶相似度為連邊的權(quán)值，構(gòu)建無(wú)向加權(quán)的隱性社交網(wǎng)絡(luò)。 由于譜聚類算法適用于社團(tuán)劃分，并且能體現(xiàn)節(jié)點(diǎn)間關(guān)系的強(qiáng)弱，因此考慮基于譜聚類思想進(jìn)行社團(tuán)劃分。

針對(duì)稀疏的評(píng)分矩陣中共同評(píng)分項(xiàng)目少，使得所計(jì)算的相似度不夠準(zhǔn)確而影響最終推薦準(zhǔn)確性的問(wèn)題，做了兩方面考慮：（1） 構(gòu)建隱性社交網(wǎng)絡(luò)時(shí)，用Jaccard 相似系數(shù)計(jì)算用戶相似度，而在后續(xù)協(xié)同過(guò)濾的近鄰搜索階段，采用皮爾遜相關(guān)系數(shù)計(jì)算相似度，通過(guò)兩者互補(bǔ)使相似度更準(zhǔn)確；（2） 對(duì)Jaccard 相似系數(shù)加以改進(jìn)，不僅考慮用戶間是否有共同評(píng)分的項(xiàng)目，還考慮當(dāng)用戶間無(wú)共同評(píng)分項(xiàng)目時(shí)，在分別與其有共同評(píng)分項(xiàng)目的用戶之間是否存在交集，以便更全面準(zhǔn)確地反映用戶間可能存在的興趣關(guān)系，進(jìn)一步提高用戶相似度的準(zhǔn)確性。

2．2 ICDCF 算法的總體流程

融合隱性社交網(wǎng)絡(luò)社團(tuán)劃分和協(xié)同過(guò)濾的推薦方法ICDCF 的總體流程如圖2 所示。

圖2 ICDCF 總體流程

總體上，ICDCF 算法包括3 大部分：（1） 隱性社交網(wǎng)絡(luò)構(gòu)建；（2） 社團(tuán)劃分；（3） 協(xié)同過(guò)濾推薦。 各部分具體設(shè)計(jì)如下。

2．3 隱性社交網(wǎng)絡(luò)構(gòu)建

（1） 相似度計(jì)算方法設(shè)計(jì)

構(gòu)建隱性社交網(wǎng)絡(luò)是進(jìn)行基于譜聚類社團(tuán)劃分的基礎(chǔ)，而相似度計(jì)算又是構(gòu)建無(wú)向加權(quán)隱性社交網(wǎng)絡(luò)的關(guān)鍵，必須采用合適的相似度計(jì)算方法。

按照2.1 節(jié)所述思路，本文將用戶關(guān)系分為“好友”、“間接好友”、“不相關(guān)用戶”3 種。

定義1好友：具有共同評(píng)分項(xiàng)目的用戶互為“好友”。

由于用戶對(duì)項(xiàng)目的反饋信息可以在一定程度上表示用戶的興趣，如果用戶i和用戶j對(duì)相同項(xiàng)目進(jìn)行了評(píng)分，可以認(rèn)為兩者的興趣存在相似性，因此本文將他們視為“好友”。

定義2間接好友：沒(méi)有共同評(píng)分項(xiàng)目但有共同好友的用戶互為“間接好友”。

如果用戶i和用戶j沒(méi)有共同評(píng)分的項(xiàng)目，即不是“好友”，但與他們有共同評(píng)分項(xiàng)目的用戶存在交集，即兩者有共同的好友，基于好友的好友可能成為好友的思想，將用戶i和用戶j視為“間接好友”。

定義3不相關(guān)用戶：既沒(méi)有共同評(píng)分項(xiàng)目，也沒(méi)有共同好友的用戶為“不相關(guān)用戶”。

為了全面衡量上述的用戶間的關(guān)系，本文對(duì)Jaccard 相似系數(shù)做了改進(jìn)，改進(jìn)的Jaccard 相似系數(shù)如式（3）所示。

其中，Ii和Ij分別表示用戶i和用戶j已評(píng)分的項(xiàng)目集合，Ni和Nj分別表示用戶i和用戶j的好友集合。對(duì)照定義1 至定義3，可以看出：自上而下依次為好友的、間接好友的和不相關(guān)用戶的相似度；好友之間的相似度高于間接好友，不相關(guān)用戶的相似度為零。

（2） 構(gòu)建隱性社交網(wǎng)絡(luò)

基于評(píng)分矩陣，用式（3）計(jì)算用戶相似度，構(gòu)建用戶相似度矩陣，該相似度矩陣可視為社交網(wǎng)絡(luò)的鄰接矩陣W，如式（4）所示，其中，wij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間連邊的權(quán)值（即邊權(quán)），wij＝S（i，j）。

矩陣W映射著一個(gè)無(wú)向加權(quán)的隱性社交網(wǎng)絡(luò)，該網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)用戶，相似度不為零的用戶i和j（i≠j） 所對(duì)應(yīng)的節(jié)點(diǎn)之間都有連邊，即好友和間接好友之間都有連邊，邊權(quán)取值為相似度。

2．4 社團(tuán)劃分

按照2.1 節(jié)所述思路，ICDCF 用譜聚類思想對(duì)隱性社交網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，具體流程如下。

輸入：無(wú)向加權(quán)隱性社交網(wǎng)絡(luò)的鄰接矩陣W和社團(tuán)劃分?jǐn)?shù)目k。

輸出：k個(gè)社團(tuán)。

步驟：

Step1 計(jì)算矩陣W的度矩陣D

其中，di為節(jié)點(diǎn)的度，

Step2 用式（6）計(jì)算拉普拉斯矩陣L。

Step3 計(jì)算L的特征值，取前q個(gè)最小特征值｛λ1，λ2，…，λq｝，并計(jì)算特征值所對(duì)應(yīng)的特征向量｛f1，f2，…，fq｝。

Step4 將q個(gè)最小特征值對(duì)應(yīng)的特征向量作為列，組成n×q階矩陣Fn×q ＝｛f1，f2，…，fq｝。

Step5 令yi為Fn×q第i行向量，yi作為節(jié)點(diǎn)i的指示向量，其中i ＝1，2，…，n。

Step6 用K-means 算法對(duì)新樣本集Y＝｛y1，y2，…，yn｝聚類，產(chǎn)生k個(gè)簇C1，C2，…，Ck。

Setp7 分別以簇C1，C2，…，Ck中指示向量所對(duì)應(yīng)的網(wǎng)絡(luò)節(jié)點(diǎn)集合構(gòu)成k個(gè)社團(tuán)S1，S2，…，Sk。

2．5 協(xié)同過(guò)濾推薦

按照2.1 節(jié)所述思路，ICDCF 在社團(tuán)內(nèi)實(shí)施基于用戶的協(xié)同過(guò)濾推薦，推薦流程如下。

輸入：評(píng)分矩陣、社團(tuán)集｛S1，S2，…，Sk｝、推薦數(shù)N。

輸出：Top-N個(gè)項(xiàng)目。

步驟：

Step1 在目標(biāo)用戶u所屬的社團(tuán)內(nèi)，用式（1）計(jì)算u與其他用戶的相似度。

Step2 基于相似度找到與目標(biāo)用戶u最相似的lu個(gè)近鄰用戶。

Step3 用式（7）基于最近鄰的預(yù)測(cè)方法預(yù)測(cè)用戶u對(duì)項(xiàng)目i?I（I為近鄰用戶已評(píng)分而用戶u未評(píng)分的項(xiàng)目集）的評(píng)分

Step4 按預(yù)測(cè)評(píng)分的降序?qū)?xiàng)目進(jìn)行排列，選取Top-N個(gè)（即前N個(gè)）項(xiàng)目推薦給目標(biāo)用戶。

2．6 ICDCF 算法時(shí)間復(fù)雜度分析

假設(shè)用戶數(shù)量為n，ICDCF 在構(gòu)建隱性社交網(wǎng)絡(luò)的過(guò)程中，需要按式（3）計(jì)算每個(gè)用戶與其他用戶的相似度，時(shí)間復(fù)雜度為O（n2）。 在社團(tuán)劃分過(guò)程中，時(shí)間復(fù)雜度主要集中在拉普拉斯矩陣的特征分解和K-means 聚類，矩陣特征分解的時(shí)間復(fù)雜度可以近似看作O（n3）；K-means 算法的時(shí)間復(fù)雜度為O（nkt），k表示聚類數(shù)目，t表示聚類中心的迭代次數(shù)，k和t通?？梢钥醋鞒Ａ?。 因此，K-means 的時(shí)間復(fù)雜度也可以近似看作O（n）。 ICDCF 在實(shí)施基于UserCF 的Top-N推薦時(shí)，需要按式（1）計(jì)算目標(biāo)用戶和其所在社團(tuán)內(nèi)各用戶的相似度，時(shí)間復(fù)雜度為O（l），l為目標(biāo)用戶所在社團(tuán)的用戶數(shù)量，l≤n。 實(shí)際上，隱性社交網(wǎng)絡(luò)的構(gòu)建和社團(tuán)劃分過(guò)程屬于系統(tǒng)模型訓(xùn)練部分，只需要在系統(tǒng)空閑時(shí)定時(shí)執(zhí)行，不影響推薦過(guò)程。 因此，ICDCF 算法實(shí)時(shí)推薦的時(shí)間復(fù)雜度可以近似看作O（l）。

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

為了檢驗(yàn)ICDCF 的性能， 在經(jīng)典數(shù)據(jù)集MovieLens-100K 和FilmTrust 上做測(cè)試實(shí)驗(yàn)，并與UserCF、基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法［9］（在以下圖表中簡(jiǎn)稱為“基于用戶聚類”）和基于K-means 的協(xié)同過(guò)濾算法（在以下圖表中簡(jiǎn)稱為“基于K-means”）進(jìn)行對(duì)比。

3．1 實(shí)驗(yàn)數(shù)據(jù)

MovieLens-100K 數(shù)據(jù)集［16］由Minnesota 大學(xué)的Grouplens 項(xiàng)目組提供。 該數(shù)據(jù)集由943 個(gè)用戶、1 682部電影以及100 000 次評(píng)分組成，數(shù)據(jù)稀疏程度為93.695%。 每條記錄包含user＿id、item＿id、rating、timestamp 四個(gè)字段，分別對(duì)應(yīng)用戶標(biāo)識(shí)、電影標(biāo)識(shí)、評(píng)分值和評(píng)分時(shí)間。

FilmTrust 數(shù)據(jù)集［17］是在2001 年從FilmTrust 網(wǎng)站爬取的。 該數(shù)據(jù)集由1 508 個(gè)用戶、2 071 部電影以及35 497 個(gè)評(píng)分組成，數(shù)據(jù)稀疏度為98.863%。 每條記錄包含userId、moviId 和movieRating 三個(gè)字段，分別對(duì)應(yīng)用戶標(biāo)識(shí)、電影標(biāo)識(shí)和評(píng)分值。

3．2 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)中以平均絕對(duì)誤差MAE 和推薦速率F為性能指標(biāo)，分別評(píng)價(jià)ICDCF 的準(zhǔn)確性和實(shí)時(shí)性。 此外，通過(guò)測(cè)試數(shù)據(jù)集規(guī)模增大時(shí)推薦速率F的變化情況，評(píng)價(jià)其可擴(kuò)展性。

（1） 平均絕對(duì)誤差MAE

MAE 是評(píng)價(jià)推薦準(zhǔn)確性的常用指標(biāo)之一，反映預(yù)測(cè)評(píng)分與用戶實(shí)際評(píng)分的差異，計(jì)算公式如下

其中，pi表示算法所產(chǎn)生的目標(biāo)用戶對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分，qi表示目標(biāo)用戶對(duì)項(xiàng)目i的實(shí)際評(píng)分，N表示已為目標(biāo)用戶預(yù)測(cè)評(píng)分的項(xiàng)目數(shù)量。 MAE 值越小，則預(yù)測(cè)準(zhǔn)確性越高，推薦效果越好。

（2） 推薦速率F

推薦速率F是指單位時(shí)間內(nèi)的推薦次數(shù)，具體計(jì)算公式如下

其中，R為推薦次數(shù)，T為推薦所用的時(shí)間，F(xiàn)值越大，則實(shí)時(shí)性越好。

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

實(shí)驗(yàn)時(shí)將數(shù)據(jù)隨機(jī)分成5 份，依次選取其中的1 份作為測(cè)試集，其余4 份作為訓(xùn)練集，共進(jìn)行5 次測(cè)試，以5 次測(cè)試結(jié)果的均值作為最終結(jié)果。

3.3.1 準(zhǔn)確性測(cè)試與評(píng)價(jià)

（1） 最近鄰居數(shù)增加時(shí)MAE 的變化情況

實(shí)驗(yàn)中設(shè)定社團(tuán)個(gè)數(shù)為5，最近鄰居數(shù)以10 為單位逐漸增加。 測(cè)試結(jié)果如圖3 所示。

圖3 最近鄰居數(shù)增加時(shí)MAE 的變化

可以看出：①在兩種數(shù)據(jù)集上，隨著最近鄰居個(gè)數(shù)的增加，4 種算法的MAE 值都是先呈現(xiàn)下降趨勢(shì)，然后趨于穩(wěn)定，而在鄰居數(shù)增加到一定量后又略有回升（如鄰居數(shù)為100 時(shí)，回升已比較明顯）。 這是因?yàn)殡S著最近鄰居數(shù)量的增加，在預(yù)測(cè)評(píng)分值時(shí)可以有更多的參考項(xiàng)，預(yù)測(cè)出來(lái)的值也更接近真實(shí)值；但鄰居數(shù)過(guò)多也會(huì)因有些鄰居參考價(jià)值不高而形成干擾。 ②ICDCF 算法的MAE 值始終最小，并且從最近鄰個(gè)數(shù)為30 時(shí)開始趨于穩(wěn)定。

（2） 不同社團(tuán)個(gè)數(shù)下MAE 的變化情況

實(shí)驗(yàn)中最近鄰居數(shù)設(shè)為圖3 中效果較好時(shí)的30，社團(tuán)個(gè)數(shù)以1 為單位逐漸增加。 測(cè)試結(jié)果如圖4 所示。

圖4 不同社團(tuán)個(gè)數(shù)下MAE 的變化

可以看出：①?zèng)]有社團(tuán)劃分環(huán)節(jié)的傳統(tǒng)UserCF的MAE 值保持穩(wěn)定且最高。 隨著所劃分的社團(tuán)個(gè)數(shù)的增加，基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法、基于K-means 的協(xié)同過(guò)濾算法和ICDCF 算法的MAE 值略有波動(dòng)，在社團(tuán)數(shù)增加到一定量（如MovieLens-100K 數(shù)據(jù)集上劃分為6 個(gè)社團(tuán)）后呈現(xiàn)略微回升的趨勢(shì)。 ②在兩種數(shù)據(jù)集上，ICDCF 算法的MAE 值始終最小，并且當(dāng)社團(tuán)為某個(gè)數(shù)量（如在FilmTrust 數(shù)據(jù)集上劃分為5 個(gè)社團(tuán)）時(shí)，ICDCF 算法的MAE 值最低，推薦準(zhǔn)確性達(dá)到最高點(diǎn)。 這說(shuō)明社團(tuán)個(gè)數(shù)不是越多越好，因?yàn)閰f(xié)同過(guò)濾推薦在社團(tuán)內(nèi)進(jìn)行，社團(tuán)劃分過(guò)細(xì)，可能會(huì)使有價(jià)值的參考項(xiàng)流失于社團(tuán)外。

（3） 不同數(shù)據(jù)集規(guī)模下MAE 的變化情況

實(shí)驗(yàn)中最近鄰居數(shù)設(shè)為30，社團(tuán)個(gè)數(shù)設(shè)為5，數(shù)據(jù)量分別為MovieLens-100K 和FilmTrust 數(shù)據(jù)集的20%、40%、60%、80%和100%。 測(cè)試結(jié)果如表1所示。

表1 不同數(shù)據(jù)規(guī)模下MAE 的變化情況

可以看出：①隨著數(shù)據(jù)量的增大，UserCF 算法的MAE 值相對(duì)穩(wěn)定，而基于K-means 的協(xié)同過(guò)濾算法和ICDCF 算法的MAE 值呈下降趨勢(shì)，并且ICDCF 算法的MAE 值始終保持在更低水平。 ②隨著數(shù)據(jù)集的不斷增大，基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法和基于K-means 的協(xié)同過(guò)濾算法的MAE 值已經(jīng)趨于穩(wěn)定，而ICDCF 算法的MAE 值依然呈下降趨勢(shì)。

綜合各種情況，4 種算法中ICDCF 算法的準(zhǔn)確性最高，并且合理設(shè)置最近鄰個(gè)數(shù)和社團(tuán)個(gè)數(shù)將能更充分地發(fā)揮其優(yōu)勢(shì)。

3.3.2 實(shí)時(shí)性與可擴(kuò)展性測(cè)試與評(píng)價(jià)

（1） 不同社團(tuán)個(gè)數(shù)下推薦速率F的對(duì)比

實(shí)驗(yàn)中最近鄰居數(shù)設(shè)定為30，在基于K-means的協(xié)同過(guò)濾算法中，社團(tuán)個(gè)數(shù)就是其聚類個(gè)數(shù)。 測(cè)試結(jié)果如表2 所示。

表2 不同社團(tuán)個(gè)數(shù)下推薦速率F 的對(duì)比 千次／s

可以看出：沒(méi)有社團(tuán)劃分環(huán)節(jié)的傳統(tǒng)UserCF 的推薦速率最低，并且與社團(tuán)劃分?jǐn)?shù)量沒(méi)有關(guān)系；ICDCF 算法的推薦速率最高，而且隨著社團(tuán)個(gè)數(shù)的增加，ICDCF 速度提升更明顯。 這是因?yàn)殡S著社團(tuán)劃分?jǐn)?shù)目的增加，單個(gè)社團(tuán)所包含的用戶數(shù)量更少，搜索目標(biāo)用戶最近鄰居集的迭代次數(shù)更少。 需要說(shuō)明的是，根據(jù)以上對(duì)準(zhǔn)確性測(cè)試結(jié)果的分析，在實(shí)際使用中，社團(tuán)個(gè)數(shù)的選擇需兼顧準(zhǔn)確性，并不是越多越好。

（2） 不同數(shù)據(jù)集規(guī)模下推薦速率F的對(duì)比

實(shí)驗(yàn)中最近鄰居數(shù)設(shè)為30，社團(tuán)個(gè)數(shù)設(shè)為5，數(shù)據(jù)量分別為MovieLens-100K 和FilmTrust 數(shù)據(jù)集的20%、40%、60%、80%和100%。 測(cè)試結(jié)果如表3所示。

表3 不同數(shù)據(jù)量下推薦速率F 的比較 千次／s

可以看出：①數(shù)據(jù)量增大時(shí)，ICDCF 在兩種數(shù)據(jù)集上都體現(xiàn)出了速率上的優(yōu)勢(shì)。 ②隨著數(shù)據(jù)量的增大，4 種算法的推薦速率均呈下降趨勢(shì)，但是相較于UserCF、基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法和基于K-means 的協(xié)同過(guò)濾算法，ICDCF 下降的幅度更小。 在MovieLens-100K 數(shù)據(jù)集上，當(dāng)數(shù)據(jù)量從20%增加到100%時(shí)，UserCF 的推薦速率下降幅度為73.22%，基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法為61.45%，基于K-means 的協(xié)同過(guò)濾算法為54.30%，而ICDCF 算法僅為43.77%。 在FilmTrust數(shù)據(jù)集上，當(dāng)數(shù)據(jù)量從20%增加到100%時(shí)，UserCF的推薦速率下降幅度為80.18%，基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法為78.20%，基于K-means 的協(xié)同過(guò)濾算法為77.99%，而ICDCF 算法為69.87%。

綜合表2 和表3，ICDCF 算法具有更好的實(shí)時(shí)性和可擴(kuò)展性。 此外，在準(zhǔn)確性測(cè)試表1 中，ICDCF方法的MAE 值隨著數(shù)據(jù)量的增大持續(xù)變?。?zhǔn)確性增高），也從另一個(gè)角度說(shuō)明了ICDCF 方法有更好的可擴(kuò)展性。

4 結(jié)束語(yǔ)

本文綜合運(yùn)用Jaccard 相似系數(shù)、皮爾遜相關(guān)系數(shù)、隱性社交網(wǎng)絡(luò)、譜聚類和基于用戶的協(xié)同過(guò)濾思想，設(shè)計(jì)了融合隱性社交網(wǎng)絡(luò)社團(tuán)劃分和協(xié)同過(guò)濾的推薦算法ICDCF。 通過(guò)對(duì)Jaccard 相似系數(shù)加以改進(jìn)并用于衡量用戶興趣關(guān)系和構(gòu)建隱性社交網(wǎng)絡(luò)，以及基于譜聚類思想對(duì)隱性社交網(wǎng)絡(luò)進(jìn)行用戶社團(tuán)劃分，并在社團(tuán)內(nèi)進(jìn)行基于用戶的協(xié)同過(guò)濾推薦，不僅有效地避免了由于稀疏的評(píng)分矩陣中用戶間共同評(píng)分項(xiàng)少而導(dǎo)致的相似度計(jì)算不準(zhǔn)確問(wèn)題，還減少了搜索近鄰的迭代次數(shù)。 在MovieLens-100K和FilmTrust 兩個(gè)數(shù)據(jù)集上與其他算法的對(duì)比實(shí)驗(yàn)結(jié)果，驗(yàn)證了ICDCF 算法具有更高的準(zhǔn)確性、實(shí)時(shí)性和可擴(kuò)展性，實(shí)現(xiàn)了性能較為全面的提升。