基于中心節點重疊社區發現的協同過濾推薦系統*

侯 強， 孫 瑜

(沈陽工業大學 管理學院， 沈陽 110870)

電子商務個性化推薦系統是利用電子商務網站向用戶提供產品信息和相關建議，幫助用戶決定購買什么產品，通過模擬銷售人員幫助用戶完成購物過程的系統[1]56-58。電子商務替代了傳統的商業交易行為和流程，趨于向網絡模式轉移。淘寶網發布的2011年網購數據顯示，2011年交易額達50億元人民幣，同比增速達到150%，2012年預測服務市場規模將達到125億。這種網絡消費蓬勃發展的趨勢，使電子商務系統的結構日趨復雜，海量信息的涌現也給用戶的篩選造成了極大的困擾。信息過載問題使用戶很難從中發現自己感興趣的商品，而網絡中的“暗信息”也因少人問津而無法被獲取。推薦系統的產生有效地解決了這一問題。作為信息過濾的工具，對推薦系統的研究有助于用戶更好地利用互聯網信息，有助于提高網站的用戶黏著度和推廣相關產品或服務[2]。

個性化推薦系統主要包括協同過濾系統、基于內容的推薦系統、基于二分網資源分配的推薦系統、混合推薦系統和其他推薦系統等[3]。這一領域的研究主要集中于將協同過濾與其他方法相結合，克服稀疏矩陣、冷啟動、擴展性等問題，提升運算效率。協同過濾推薦系統的算法可以分為兩類，即基于記憶的算法和基于模型的算法。基于記憶的算法關鍵是相似度的計算，根據系統中所有被打過分的產品信息進行預測。基于模型的算法本質是基于對已有數據進行應用統計和機器學習得到的模型進行預測。Breese提出了聚類模型和Bayes網絡[4]18-25，而概率相關模型[5]、極大熵模型[6]22-35和Bayes模型等也有廣泛的應用。

這些算法主要是利用個體間的相似性，對交易所形成的復雜網絡的網絡結構信息的利用相對不足。隨著社會網絡理論的研究日益成熟，許多學者試圖以網絡結構為突破口對當前的推薦算法從原理和計算方式上進行改進，其中很重要的一個方向就是進行社區劃分。從社區劃分計算方法原理的角度可以將其分為基于優化的算法和啟發式算法。基于優化的算法將社區劃分問題轉化為優化問題，典型的方法是運用截函數方法進行劃分的譜分析；啟發式算法是將問題轉化為預先定義的啟發式規則的設計問題，典型的算法有MFC算法[7]、GN算法、FEC算法和CPM算法等。從社區劃分計算方式的視角，可以將其分為凝聚算法(如貪婪算法)、分裂算法、搜索算法和其他搜索方法等。本文將從社區劃分這一視角出發進行個性化推薦系統的構建。

一、算法的基本思想與相關概念

電子商務系統可以看成用戶集合和項目集合通過邊進行連接的二分網[8]，根據二分網將用戶(或項目)之間的關系轉化為社會網關系。這種研究人或團體之間聯系或交互的理論最普遍的特性就是社區結構，即網絡的若干組中包含的節點組內連接較多、組間連接較少。基于該思想，首先依據項目信息計算出用戶的相似度，以此相似度作為用戶社會網中兩元素連接的權重即邊權；而后以邊權為基礎采用一定的規則計算出點權，以點權較大的點作為中心節點，以貢獻度來判斷是否加入新元素來進行社區劃分；利用中心節點的思想提取出社區C后，并不從網絡中刪除社區C的節點和邊，為尋找社區間的重疊節點提供了便利；社區形成后，對個體相關的各個社區進行合并，依據協同過濾思想在合并的社區內進行推薦[9]。為說明相關算法，首先界定以下概念。

(1) 邊權。有權圖中用邊的權重衡量兩個節點之間關系的緊密程度。本文改進了傳統的Pearson相關性計算方法，由于相關系數將受到樣本容量的影響，本文加入體現樣本容量的因子，計算公式為

(1)

(2) 點權。點權不僅依賴于度(節點與其他節點連接的數目)，也取決于與其相連的其他節點的權重[10-11]。假設對于網絡G，其包含節點集合V={v1，v2，…，vn}與節點i相連接的節點集合Ti={ti1，ti2，…，tik}，定義函數g(vi)為節點vi的度，函數f(vi)為vi節點的權重，則

(2)

式中：d為阻尼系數，取值在0～1之間(本文中d=0.4)；函數f(vi)可以準確度量每個節點的權重系數，節點權重的求解可以采用迭代的方式進行[7]。

(3) 貢獻度。貢獻度的計算公式為

(3)

根據文獻[9]定義ωin，用來表示社區與內部所有連邊上的權重之和；定義ωout，用來表示社區與外部所有連邊上的權值之和。

(4) 重疊度。重疊度的計算公式為

(4)

式中：Ci∩Cj為社區Ci和Cj的公共節點數目；Ci∪Cj為社區Ci和Cj的節點總數。

(5) 推薦結果。選取K個最相似用戶作為一個子集，則對于目標用戶用其評分的一個加權集合產生推薦。這個推薦值源于鄰居的平均值和加權平均偏差，公式為

(5)

式中：ωut為用戶u對項目t的可信權重，即初始評分和分組評分的轉化系數；sim(ua，u)為目標用戶ua和訓練集用戶u的相似度；K為鄰居集中的用戶數量[12]。

二、算法流程

(2) 根據式(2)計算點權，按節點權重由大至小的順序排成序列S={S1，S2，…，Sn}，初始S中任何節點均不被標識。

(3) 選擇未被社區劃分的點權最大的節點Si作為初始社區Ci，并將該節點做上標記，初始化全局貢獻度Q=0。

(4) 依據邊權矩陣找出與Ci相連且權重大于臨界值L1的節點，置于鄰接點集合U中。

(5) 遍歷U中的所有節點j，依據式(3)計算j對社區的貢獻度qj。若存在qL=qmax=max{qj}≥Q，則將節點L加入社區Ci中，同時對節點L做標識，更新Q=qmax并重復執行，否則得到社區Ci。

(6) 遍歷未被標識的節點，重復第4、5步，直至所有節點均被標識。

(7) 依據式(4)計算重疊度矩陣，將重疊度大于閾值L2的進行合并，遍歷計算重疊度，直至重疊度矩陣中所有元素均小于閾值T，得到社區劃分Cu。

(9) 在社區Cl內，根據采用文獻[12]的方法解決稀疏問題。

(10) 在解決了稀疏性之后的候選用戶集中，根據文獻[12]中的加權相似度計算目標用戶和所有候選用戶集中每個用戶的相似度。

(11) 選取K個最相似用戶作為一個子集，則對于目標用戶，根據式(5)利用其評分的一個加權集合產生推薦。

(12) 根據實際評分情況定期更新邊權和點權，重新進行社區劃分。

三、算例分析

驗證電子商務推薦算法的數據集有很多，例如Netflix Prize，Group Lens和Movie Lens等。它們包括了用戶集和項目集，不僅提供了不同用戶對不同項目的評分，并提供了用戶評分時間。本文以公開的Movie Lens(http：//movielens.umn.edu)經典數據集作為測試數據，選取由943個用戶、1 682部電影、100 000條評分構成的數據集。該評分介于1～5之間，評分值越大則用戶對該部電影的喜歡程度越高，且每個用戶至少有20條評分信息。選取數據集中90%的樣本數據為訓練集，10%的樣本數據為測試集。利用訓練集得到預測結果，然后用測試集對預測結果進行評價。評價時，選取預測打分與用戶實際打分的平均絕對誤差(MAE)為度量標準[13]。在MAE度量推薦精度的基礎上，用算法的運行時間(RT)度量推薦效率。圖1、2是本文算法與通過傳統協同過濾做出MAE和RT兩個參數測度的比較結果。

圖1 本文算法與傳統協同過濾的MAE比較

設ωut=0.4，K值取以5為步長的[20，50]區間。可以發現，在推薦精度相差2%的情況下，推薦效率提升了近10倍。結合圖形和其他參數的測度情況可以發現，隨著K值的增加推薦精度的差異不斷縮小，幾乎可以忽略。這表明該算法在對推薦精度產生的影響幾乎不變的前提下，推薦效率得到了大幅度的提升。

圖2 本文算法與傳統協同過濾的RT比較

四、結 論

電子商務個性化推薦算法的研究已成為一種熱門趨勢，既有的研究均是對傳統協同過濾進行算法改進，融入新思路以解決其存在的問題。本文將基于中心節點重疊社區發現算法與協同過濾算法相結合，引入了邊權和點權對基于中心節點的重疊社區劃分加以改進。由于邊權的相關系數受到樣本容量的影響，本文引入樣本容量因子對其加以控制，利用重疊度矩陣的閾值得到最終的社區結構。對目標用戶和社區的類重心建立直接的對應關系，結合top-n算法的思想產生推薦，提高了電子商務推薦系統的可靠性。由于社區的內個體的數量小于網絡中元素的個數，將大大減少系統線上計算時間。Movie Lens數據集的測試結果表明，在推薦精度基本不變的前提下，改進的基于中心節點重疊社區發現的協同過濾推薦方法比傳統的協同過濾推薦方法在推薦效率上有本質提高。

參考文獻：

[1]Resnick V.Recommender systems [M].USA：Communications of the ACM，1997.

[2]崔寶俠，任重，段勇.基于用戶興趣的電子商務推薦方法 [J].沈陽工業大學學報，2009(5)：573-576.

[3]吳恒亮，張巍巍.電子商務推薦系統中推薦技術的比較研究 [J].物流科技，2009，11(3)：57-59.

[4]John S B，David H，Carl K.Empirical analysis of predictive algorithms for collaborative filtering [M].USA：Microsoft Corporation，1998.

[5]Nir F，Lise G.Learning probabilistic relational models[R].Sweden：16th International Joint Conference on Artificial Intelligence，1999：3-18.

[6]Dmitry Y P，David M P.A maximum entropy app-roach to collaborative filtering in dynamic，sparse，high-dimensional domains [M].USA：Petersburg，2002.

[7]Flake G W，Lawrence S R，Giles C L，et al.Self-organization and identification of web communities [J].IEEE Computer，2002，35(3)：66-71.

[8]Zhou T，Ren J，Medo M，et al.Bipartite network projection and personal recommendation [J].Physical Review，2007，76(4)：1-7.

[9]萬雪飛.基于社會網絡的協同過濾推薦技術研究 [D].北京：電子科技大學，2007：1-22.

[10]Brin S，Page L.The anatomy of a large-scale hyper textual web-search engine [EB/OL].[2009-12-08].http：//www.computer.org/csdl/proceedings/iccee/2009/3925/02/3925b491-abs.html.

[11]段曉東，王存睿，劉向東，等.基于網絡權重的多社團網絡結構劃分算法 [J].復雜系統與復雜性科學，2009，6(3)：34-39.

[12]Xue G R，Lin C X，Yang Q.Scalable collaborative filtering using cluster-based smoothing[R].Brazil：2005 ACM SIGIR Conference，2005：114-121.

[13]劉建國，周濤，郭強，等.個性化推薦系統評價方法綜述 [J].復雜系統與復雜性科學，2009，6(3)：1-10.