侯 強(qiáng)， 孫 瑜

(沈陽工業(yè)大學(xué) 管理學(xué)院， 沈陽 110870)

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

個(gè)性化推薦系統(tǒng)主要包括協(xié)同過濾系統(tǒng)、基于內(nèi)容的推薦系統(tǒng)、基于二分網(wǎng)資源分配的推薦系統(tǒng)、混合推薦系統(tǒng)和其他推薦系統(tǒng)等[3]。這一領(lǐng)域的研究主要集中于將協(xié)同過濾與其他方法相結(jié)合，克服稀疏矩陣、冷啟動(dòng)、擴(kuò)展性等問題，提升運(yùn)算效率。協(xié)同過濾推薦系統(tǒng)的算法可以分為兩類，即基于記憶的算法和基于模型的算法?；谟洃浀乃惴P(guān)鍵是相似度的計(jì)算，根據(jù)系統(tǒng)中所有被打過分的產(chǎn)品信息進(jìn)行預(yù)測?；谀Ｐ偷乃惴ū举|(zhì)是基于對已有數(shù)據(jù)進(jìn)行應(yīng)用統(tǒng)計(jì)和機(jī)器學(xué)習(xí)得到的模型進(jìn)行預(yù)測。Breese提出了聚類模型和Bayes網(wǎng)絡(luò)[4]18-25，而概率相關(guān)模型[5]、極大熵模型[6]22-35和Bayes模型等也有廣泛的應(yīng)用。

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

一、算法的基本思想與相關(guān)概念

電子商務(wù)系統(tǒng)可以看成用戶集合和項(xiàng)目集合通過邊進(jìn)行連接的二分網(wǎng)[8]，根據(jù)二分網(wǎng)將用戶(或項(xiàng)目)之間的關(guān)系轉(zhuǎn)化為社會(huì)網(wǎng)關(guān)系。這種研究人或團(tuán)體之間聯(lián)系或交互的理論最普遍的特性就是社區(qū)結(jié)構(gòu)，即網(wǎng)絡(luò)的若干組中包含的節(jié)點(diǎn)組內(nèi)連接較多、組間連接較少?；谠撍枷?，首先依據(jù)項(xiàng)目信息計(jì)算出用戶的相似度，以此相似度作為用戶社會(huì)網(wǎng)中兩元素連接的權(quán)重即邊權(quán)；而后以邊權(quán)為基礎(chǔ)采用一定的規(guī)則計(jì)算出點(diǎn)權(quán)，以點(diǎn)權(quán)較大的點(diǎn)作為中心節(jié)點(diǎn)，以貢獻(xiàn)度來判斷是否加入新元素來進(jìn)行社區(qū)劃分；利用中心節(jié)點(diǎn)的思想提取出社區(qū)C后，并不從網(wǎng)絡(luò)中刪除社區(qū)C的節(jié)點(diǎn)和邊，為尋找社區(qū)間的重疊節(jié)點(diǎn)提供了便利；社區(qū)形成后，對個(gè)體相關(guān)的各個(gè)社區(qū)進(jìn)行合并，依據(jù)協(xié)同過濾思想在合并的社區(qū)內(nèi)進(jìn)行推薦[9]。為說明相關(guān)算法，首先界定以下概念。

(1) 邊權(quán)。有權(quán)圖中用邊的權(quán)重衡量兩個(gè)節(jié)點(diǎn)之間關(guān)系的緊密程度。本文改進(jìn)了傳統(tǒng)的Pearson相關(guān)性計(jì)算方法，由于相關(guān)系數(shù)將受到樣本容量的影響，本文加入體現(xiàn)樣本容量的因子，計(jì)算公式為

(1)

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

(2)

式中：d為阻尼系數(shù)，取值在0～1之間(本文中d=0.4)；函數(shù)f(vi)可以準(zhǔn)確度量每個(gè)節(jié)點(diǎn)的權(quán)重系數(shù)，節(jié)點(diǎn)權(quán)重的求解可以采用迭代的方式進(jìn)行[7]。

(3) 貢獻(xiàn)度。貢獻(xiàn)度的計(jì)算公式為

(3)

根據(jù)文獻(xiàn)[9]定義ωin，用來表示社區(qū)與內(nèi)部所有連邊上的權(quán)重之和；定義ωout，用來表示社區(qū)與外部所有連邊上的權(quán)值之和。

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

(4)

式中：Ci∩Cj為社區(qū)Ci和Cj的公共節(jié)點(diǎn)數(shù)目；Ci∪Cj為社區(qū)Ci和Cj的節(jié)點(diǎn)總數(shù)。

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

(5)

式中：ωut為用戶u對項(xiàng)目t的可信權(quán)重，即初始評分和分組評分的轉(zhuǎn)化系數(shù)；sim(ua，u)為目標(biāo)用戶ua和訓(xùn)練集用戶u的相似度；K為鄰居集中的用戶數(shù)量[12]。

二、算法流程

(2) 根據(jù)式(2)計(jì)算點(diǎn)權(quán)，按節(jié)點(diǎn)權(quán)重由大至小的順序排成序列S={S1，S2，…，Sn}，初始S中任何節(jié)點(diǎn)均不被標(biāo)識(shí)。

(3) 選擇未被社區(qū)劃分的點(diǎn)權(quán)最大的節(jié)點(diǎn)Si作為初始社區(qū)Ci，并將該節(jié)點(diǎn)做上標(biāo)記，初始化全局貢獻(xiàn)度Q=0。

(4) 依據(jù)邊權(quán)矩陣找出與Ci相連且權(quán)重大于臨界值L1的節(jié)點(diǎn)，置于鄰接點(diǎn)集合U中。

(5) 遍歷U中的所有節(jié)點(diǎn)j，依據(jù)式(3)計(jì)算j對社區(qū)的貢獻(xiàn)度qj。若存在qL=qmax=max{qj}≥Q，則將節(jié)點(diǎn)L加入社區(qū)Ci中，同時(shí)對節(jié)點(diǎn)L做標(biāo)識(shí)，更新Q=qmax并重復(fù)執(zhí)行，否則得到社區(qū)Ci。

(6) 遍歷未被標(biāo)識(shí)的節(jié)點(diǎn)，重復(fù)第4、5步，直至所有節(jié)點(diǎn)均被標(biāo)識(shí)。

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

(9) 在社區(qū)Cl內(nèi)，根據(jù)采用文獻(xiàn)[12]的方法解決稀疏問題。

(10) 在解決了稀疏性之后的候選用戶集中，根據(jù)文獻(xiàn)[12]中的加權(quán)相似度計(jì)算目標(biāo)用戶和所有候選用戶集中每個(gè)用戶的相似度。

(11) 選取K個(gè)最相似用戶作為一個(gè)子集，則對于目標(biāo)用戶，根據(jù)式(5)利用其評分的一個(gè)加權(quán)集合產(chǎn)生推薦。

(12) 根據(jù)實(shí)際評分情況定期更新邊權(quán)和點(diǎn)權(quán)，重新進(jìn)行社區(qū)劃分。

三、算例分析

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

圖1 本文算法與傳統(tǒng)協(xié)同過濾的MAE比較

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

圖2 本文算法與傳統(tǒng)協(xié)同過濾的RT比較

四、結(jié) 論

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

參考文獻(xiàn)：

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

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

[3]吳恒亮，張巍巍.電子商務(wù)推薦系統(tǒng)中推薦技術(shù)的比較研究 [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]萬雪飛.基于社會(huì)網(wǎng)絡(luò)的協(xié)同過濾推薦技術(shù)研究 [D].北京：電子科技大學(xué)，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]段曉東，王存睿，劉向東，等.基于網(wǎng)絡(luò)權(quán)重的多社團(tuán)網(wǎng)絡(luò)結(jié)構(gòu)劃分算法 [J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，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]劉建國，周濤，郭強(qiáng)，等.個(gè)性化推薦系統(tǒng)評價(jià)方法綜述 [J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2009，6(3)：1-10.