融合隱性社交網絡社團劃分和協同過濾的推薦算法

孫海崗，李玲娟

(南京郵電大學 計算機學院，江蘇 南京 210023)

推薦系統作為一種能夠根據用戶習慣及興趣進行信息過濾和推送的系統，可以在很大程度上彌補搜索引擎的不足，解決信息過載問題［1］。

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

本文設計了一種融合隱性社交網絡社團劃分和協同過濾的推薦算法（Recommendation Algorithm Integrating Implicit Social Network Community Division and Collaborative Filtering，ICDCF）。 該方法先對用戶做社團劃分，再實施基于用戶的協同過濾推薦。在社團劃分階段，將用戶對項目的共同興趣視為社交關系，利用改進的Jaccard 相似系數衡量用戶間的社交關系強弱；再基于相似度構建用戶隱性社交網絡（即基于興趣關系的社交網絡）；并進一步基于譜聚類思想對隱性社交網絡進行用戶社團劃分；最后在劃分的社團內進行協同過濾推薦。 在MovieLens-100K 和FilmTrust 數據集上與其他算法的對比實驗結果驗證了ICDCF 算法能同時提高準確性和可擴展性。

1 相關知識

1．1 基于用戶的協同過濾推薦算法UserCF

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

圖1 UserCF 框架

算法的輸入是記錄了用戶對項目歷史評分的評分矩陣，其中｛U1，U2，…，Un｝表示用戶集，｛I1，I2，…，Im｝表示項目集。 首先，根據用戶的歷史評分記錄，使用相似度計算方法，為目標用戶找到具有相似興趣的最近鄰居集；然后通過最近鄰居對項目的評分，預測目標用戶對未評分項目的評分；最后根據預測結果，選出評分高的前N個項目進行推薦［12］。隨著用戶數、項目數的增長，用戶對項目的評分矩陣變得稀疏，會產生用戶相似度計算不準確、計算開銷大等問題。

1．2 相似度計算方法

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

（1） 皮爾遜相關系數

皮爾遜相關系數的計算如下

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

（2） Jaccard 相似系數

Jaccard 相似系數的計算如下

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

皮爾遜相關系數的計算依賴于用戶共同評分的項目集，如果用戶共同評分的項目集較小，則存在一定的偶然性，不能為目標用戶提供準確的預測。Jacccard 相似度系數通過用戶整體評分信息進行相似度計算，可以有效避免此類問題。

1．3 譜聚類與社團劃分

譜聚類［13］算法以數據集中的樣本為頂點，以樣本間的相似度為頂點間連邊的權值，構建出無向加權圖，將聚類問題轉化為圖的最優劃分問題，劃分出的子圖內的邊權和盡可能大，子圖間的邊權和盡可能小。 它能對任意形狀的樣本空間聚類并能收斂于全局最優解。 其總體步驟如下：

（1） 計算被聚類樣本的相似度矩陣W，該矩陣映射了無向加權圖；

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

（3） 利用經典的聚類算法對特征向量空間中的特征向量進行聚類。

社團劃分旨在從社會網絡中發現模塊化的社團結構，社團內節點連接緊密，社團間節點連接疏遠［14］。 社會網絡可以用由節點和邊構成的網絡圖表示，因此社團劃分也被稱為圖聚類［15］。 不難看出，譜聚類與社團劃分的目標是一致的，因此適用于社團劃分。

2 ICDCF 算法設計與分析

2．1 設計思路

本文設計融合隱性社交網絡社團劃分和協同過濾的推薦算法ICDCF 的出發點是：減少因稀疏的評分矩陣中用戶共同評分項目少使相似度計算不準確而給推薦準確性帶來的負面影響，以及搜索近鄰計算量大對協同過濾推薦時間效率的負面影響，使推薦準確性和可擴展性都得到提升。

針對UserCF 算法搜索近鄰時相似度計算開銷大的問題，考慮采用先對用戶做社團劃分，再在社團內進行協同過濾推薦的策略。 將用戶對項目的共同興趣（共同評價項目的情況）視為社交關系，用相似度表示關系的強弱，以用戶為節點，以用戶相似度為連邊的權值，構建無向加權的隱性社交網絡。 由于譜聚類算法適用于社團劃分，并且能體現節點間關系的強弱，因此考慮基于譜聚類思想進行社團劃分。

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

2．2 ICDCF 算法的總體流程

融合隱性社交網絡社團劃分和協同過濾的推薦方法ICDCF 的總體流程如圖2 所示。

圖2 ICDCF 總體流程

總體上，ICDCF 算法包括3 大部分：（1） 隱性社交網絡構建；（2） 社團劃分；（3） 協同過濾推薦。 各部分具體設計如下。

2．3 隱性社交網絡構建

（1） 相似度計算方法設計

構建隱性社交網絡是進行基于譜聚類社團劃分的基礎，而相似度計算又是構建無向加權隱性社交網絡的關鍵，必須采用合適的相似度計算方法。

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

定義1好友：具有共同評分項目的用戶互為“好友”。

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

定義2間接好友：沒有共同評分項目但有共同好友的用戶互為“間接好友”。

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

定義3不相關用戶：既沒有共同評分項目，也沒有共同好友的用戶為“不相關用戶”。

為了全面衡量上述的用戶間的關系，本文對Jaccard 相似系數做了改進，改進的Jaccard 相似系數如式（3）所示。

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

（2） 構建隱性社交網絡

基于評分矩陣，用式（3）計算用戶相似度，構建用戶相似度矩陣，該相似度矩陣可視為社交網絡的鄰接矩陣W，如式（4）所示，其中，wij表示節點i和節點j之間連邊的權值（即邊權），wij＝S（i，j）。

矩陣W映射著一個無向加權的隱性社交網絡，該網絡的每個節點對應一個用戶，相似度不為零的用戶i和j（i≠j） 所對應的節點之間都有連邊，即好友和間接好友之間都有連邊，邊權取值為相似度。

2．4 社團劃分

按照2.1 節所述思路，ICDCF 用譜聚類思想對隱性社交網絡進行社團劃分，具體流程如下。

輸入：無向加權隱性社交網絡的鄰接矩陣W和社團劃分數目k。

輸出：k個社團。

步驟：

Step1 計算矩陣W的度矩陣D

其中，di為節點的度，

Step2 用式（6）計算拉普拉斯矩陣L。

Step3 計算L的特征值，取前q個最小特征值｛λ1，λ2，…，λq｝，并計算特征值所對應的特征向量｛f1，f2，…，fq｝。

Step4 將q個最小特征值對應的特征向量作為列，組成n×q階矩陣Fn×q ＝｛f1，f2，…，fq｝。

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

Step6 用K-means 算法對新樣本集Y＝｛y1，y2，…，yn｝聚類，產生k個簇C1，C2，…，Ck。

Setp7 分別以簇C1，C2，…，Ck中指示向量所對應的網絡節點集合構成k個社團S1，S2，…，Sk。

2．5 協同過濾推薦

按照2.1 節所述思路，ICDCF 在社團內實施基于用戶的協同過濾推薦，推薦流程如下。

輸入：評分矩陣、社團集｛S1，S2，…，Sk｝、推薦數N。

輸出：Top-N個項目。

步驟：

Step1 在目標用戶u所屬的社團內，用式（1）計算u與其他用戶的相似度。

Step2 基于相似度找到與目標用戶u最相似的lu個近鄰用戶。

Step3 用式（7）基于最近鄰的預測方法預測用戶u對項目i?I（I為近鄰用戶已評分而用戶u未評分的項目集）的評分

Step4 按預測評分的降序對項目進行排列，選取Top-N個（即前N個）項目推薦給目標用戶。

2．6 ICDCF 算法時間復雜度分析

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

3 實驗與結果分析

為了檢驗ICDCF 的性能， 在經典數據集MovieLens-100K 和FilmTrust 上做測試實驗，并與UserCF、基于用戶聚類的二分圖網絡協同推薦算法［9］（在以下圖表中簡稱為“基于用戶聚類”）和基于K-means 的協同過濾算法（在以下圖表中簡稱為“基于K-means”）進行對比。

3．1 實驗數據

MovieLens-100K 數據集［16］由Minnesota 大學的Grouplens 項目組提供。 該數據集由943 個用戶、1 682部電影以及100 000 次評分組成，數據稀疏程度為93.695%。 每條記錄包含user＿id、item＿id、rating、timestamp 四個字段，分別對應用戶標識、電影標識、評分值和評分時間。

FilmTrust 數據集［17］是在2001 年從FilmTrust 網站爬取的。 該數據集由1 508 個用戶、2 071 部電影以及35 497 個評分組成，數據稀疏度為98.863%。 每條記錄包含userId、moviId 和movieRating 三個字段，分別對應用戶標識、電影標識和評分值。

3．2 評價指標

實驗中以平均絕對誤差MAE 和推薦速率F為性能指標，分別評價ICDCF 的準確性和實時性。 此外，通過測試數據集規模增大時推薦速率F的變化情況，評價其可擴展性。

（1） 平均絕對誤差MAE

MAE 是評價推薦準確性的常用指標之一，反映預測評分與用戶實際評分的差異，計算公式如下

其中，pi表示算法所產生的目標用戶對項目i的預測評分，qi表示目標用戶對項目i的實際評分，N表示已為目標用戶預測評分的項目數量。 MAE 值越小，則預測準確性越高，推薦效果越好。

（2） 推薦速率F

推薦速率F是指單位時間內的推薦次數，具體計算公式如下

其中，R為推薦次數，T為推薦所用的時間，F值越大，則實時性越好。

3．3 實驗結果分析

實驗時將數據隨機分成5 份，依次選取其中的1 份作為測試集，其余4 份作為訓練集，共進行5 次測試，以5 次測試結果的均值作為最終結果。

3.3.1 準確性測試與評價

（1） 最近鄰居數增加時MAE 的變化情況

實驗中設定社團個數為5，最近鄰居數以10 為單位逐漸增加。 測試結果如圖3 所示。

圖3 最近鄰居數增加時MAE 的變化

可以看出：①在兩種數據集上，隨著最近鄰居個數的增加，4 種算法的MAE 值都是先呈現下降趨勢，然后趨于穩定，而在鄰居數增加到一定量后又略有回升（如鄰居數為100 時，回升已比較明顯）。 這是因為隨著最近鄰居數量的增加，在預測評分值時可以有更多的參考項，預測出來的值也更接近真實值；但鄰居數過多也會因有些鄰居參考價值不高而形成干擾。 ②ICDCF 算法的MAE 值始終最小，并且從最近鄰個數為30 時開始趨于穩定。

（2） 不同社團個數下MAE 的變化情況

實驗中最近鄰居數設為圖3 中效果較好時的30，社團個數以1 為單位逐漸增加。 測試結果如圖4 所示。

圖4 不同社團個數下MAE 的變化

可以看出：①沒有社團劃分環節的傳統UserCF的MAE 值保持穩定且最高。 隨著所劃分的社團個數的增加，基于用戶聚類的二分圖網絡協同推薦算法、基于K-means 的協同過濾算法和ICDCF 算法的MAE 值略有波動，在社團數增加到一定量（如MovieLens-100K 數據集上劃分為6 個社團）后呈現略微回升的趨勢。 ②在兩種數據集上，ICDCF 算法的MAE 值始終最小，并且當社團為某個數量（如在FilmTrust 數據集上劃分為5 個社團）時，ICDCF 算法的MAE 值最低，推薦準確性達到最高點。 這說明社團個數不是越多越好，因為協同過濾推薦在社團內進行，社團劃分過細，可能會使有價值的參考項流失于社團外。

（3） 不同數據集規模下MAE 的變化情況

實驗中最近鄰居數設為30，社團個數設為5，數據量分別為MovieLens-100K 和FilmTrust 數據集的20%、40%、60%、80%和100%。 測試結果如表1所示。

表1 不同數據規模下MAE 的變化情況

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

綜合各種情況，4 種算法中ICDCF 算法的準確性最高，并且合理設置最近鄰個數和社團個數將能更充分地發揮其優勢。

3.3.2 實時性與可擴展性測試與評價

（1） 不同社團個數下推薦速率F的對比

實驗中最近鄰居數設定為30，在基于K-means的協同過濾算法中，社團個數就是其聚類個數。 測試結果如表2 所示。

表2 不同社團個數下推薦速率F 的對比 千次／s

可以看出：沒有社團劃分環節的傳統UserCF 的推薦速率最低，并且與社團劃分數量沒有關系；ICDCF 算法的推薦速率最高，而且隨著社團個數的增加，ICDCF 速度提升更明顯。 這是因為隨著社團劃分數目的增加，單個社團所包含的用戶數量更少，搜索目標用戶最近鄰居集的迭代次數更少。 需要說明的是，根據以上對準確性測試結果的分析，在實際使用中，社團個數的選擇需兼顧準確性，并不是越多越好。

（2） 不同數據集規模下推薦速率F的對比

實驗中最近鄰居數設為30，社團個數設為5，數據量分別為MovieLens-100K 和FilmTrust 數據集的20%、40%、60%、80%和100%。 測試結果如表3所示。

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

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

綜合表2 和表3，ICDCF 算法具有更好的實時性和可擴展性。 此外，在準確性測試表1 中，ICDCF方法的MAE 值隨著數據量的增大持續變?。蚀_性增高），也從另一個角度說明了ICDCF 方法有更好的可擴展性。

4 結束語

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