王扶東++楊宏一++薛冰

[摘要]結(jié)合社會網(wǎng)絡(luò)分析的推薦方法研究已成為熱點。電子商務(wù)中用戶的動態(tài)行為異常豐富，隱含了用戶的關(guān)聯(lián)關(guān)系，利用這些信息進行商品推薦是個新研究思路。分析電子商務(wù)系統(tǒng)中用戶動態(tài)行為關(guān)聯(lián)關(guān)系及用戶間明確好友關(guān)系形成復(fù)雜隱性社會網(wǎng)絡(luò)，將社團劃分算法應(yīng)用到該網(wǎng)絡(luò)中，則社團內(nèi)部用戶聯(lián)系緊密且具有更相似的消費偏好，據(jù)此設(shè)計了電子商務(wù)中社團內(nèi)部的推薦方法，應(yīng)用R語言進行了算法的驗證并與傳統(tǒng)的協(xié)同過濾算法進行比較。實驗表明，該推薦算法提高了推薦的質(zhì)量，緩解了傳統(tǒng)推薦算法中數(shù)據(jù)稀疏性及冷啟動問題等。

[關(guān)鍵詞]隱性社會網(wǎng)絡(luò)；社團劃分；個性化推薦

[中圖分類號]TP39 [文獻標識碼]A [文章編號]1008-0821（2015）05-0049-05

社會網(wǎng)絡(luò)為電商的推薦提供了一個協(xié)作的社會環(huán)境…，目前社會網(wǎng)絡(luò)分析與推薦方法結(jié)合的研究成為研究熱點。Fengkun Liu等通過實驗表明融合社會網(wǎng)絡(luò)信息與推薦算法，能有效提高推薦的準確度。喬秀全等將社會學(xué)與心理學(xué)中人們之間信任的產(chǎn)生過程結(jié)合到社會網(wǎng)絡(luò)服務(wù)中，提高了信任度計算的合理性以及有效性。有學(xué)者從多維社會網(wǎng)絡(luò)出發(fā)以提高相似性的計算準確度。Pasquale De Meo等提出了基于SIS的社會網(wǎng)絡(luò)來收集用戶信息。張華青等提出了一種多維加權(quán)社會網(wǎng)絡(luò)的個性化推薦算法。Jianming He等利用社會網(wǎng)絡(luò)中的信息提出了一種推薦系統(tǒng)的新范式。Yu Shian Chiu等提出了一個Social Network -based Serendipity推薦系統(tǒng)，這個系統(tǒng)利用社會網(wǎng)絡(luò)中用戶和朋友之間的交互信息，找出用戶感興趣但自己卻不容易發(fā)現(xiàn)的項目推薦給用戶。由于數(shù)據(jù)的龐大，對于推薦速度問題，趙學(xué)臣和楊長春等學(xué)者通過研究社會網(wǎng)絡(luò)中社團發(fā)現(xiàn)，提出高效的推薦模型。

結(jié)合社會網(wǎng)絡(luò)中社團劃分的朋友推薦已有很多研究，這為在電商推薦中結(jié)合社團劃分思想提供了新的思路。網(wǎng)絡(luò)社團也被稱為網(wǎng)絡(luò)模塊、內(nèi)聚組等，它被廣泛應(yīng)用于社會學(xué)、計算機圖形學(xué)等領(lǐng)域，根據(jù)人們的興趣特點而形成的社團在網(wǎng)絡(luò)中呈現(xiàn)出多樣性。復(fù)雜網(wǎng)絡(luò)中的社團發(fā)現(xiàn)算法很多，目前有代表性的由WH算法和CN算法等，其中CN算法是一種層次分裂算法，應(yīng)用最廣泛，該算法的基本思路是為網(wǎng)絡(luò)中的每一條邊計算邊介數(shù)，通過不斷地從網(wǎng)絡(luò)中移除邊介數(shù)最大的邊，將整個網(wǎng)絡(luò)分解為不同的社團。之后Newman陸續(xù)提出了Newman快速算法和利用矩陣的特征向量來發(fā)現(xiàn)網(wǎng)絡(luò)社團結(jié)構(gòu)。

隨著社會網(wǎng)絡(luò)的發(fā)展，電子商務(wù)中不斷集成社交網(wǎng)絡(luò)服務(wù)平臺，使得電子商務(wù)中的用戶行為除了簡單的對項目評分外，還有很多復(fù)雜的用戶動態(tài)行為，本文通過對電子商務(wù)系統(tǒng)中豐富的用戶動態(tài)行為信息挖掘分析，構(gòu)建電子商務(wù)系統(tǒng)中的隱性社會網(wǎng)絡(luò)并進行網(wǎng)絡(luò)社團的劃分，得到聯(lián)系更加緊密且用戶之間具有更高相似消費偏好的網(wǎng)絡(luò)社團。根據(jù)網(wǎng)絡(luò)社團的特性進行個性化商品推薦，將有助于提高推薦的質(zhì)量。

1 隱性社會網(wǎng)絡(luò)定義

近年來，隨著電子商務(wù)的發(fā)展，在電子商務(wù)系統(tǒng)中，不同的用戶會對同一件商品進行瀏覽、購買等行為，這些行為將原來獨立的用戶聯(lián)系起來，形成了電子商務(wù)中隱性社會網(wǎng)絡(luò)的一部分，即用戶之間的弱關(guān)系，如圖1。同時社會學(xué)和心理學(xué)研究表明，人們更愿意信任自己的好友，采納自己好友的意見。社會網(wǎng)絡(luò)服務(wù)電子商務(wù)系統(tǒng)中的集成，給我們挖掘并利用真實的人際關(guān)系提供了有利的條件，故本文將電子商務(wù)系統(tǒng)中用戶之間明確的好友關(guān)系形成隱性社會網(wǎng)絡(luò)的另一部分，即用戶之間的強關(guān)系，如圖2。 其中，a，b，c"'表示電子商務(wù)系統(tǒng)中用戶之間存在的弱關(guān)聯(lián)關(guān)系類型：a搜索、b瀏覽、c收藏、d購買、e評價、f參加過同一活動，等等。

最后，由電子商務(wù)系統(tǒng)中用戶間的這些強弱關(guān)系構(gòu)成了電子商務(wù)中的隱性社會網(wǎng)絡(luò)（The recessive social network）。隱性社會網(wǎng)絡(luò)中的點和邊分別由電子商務(wù)中的用戶和用戶間強弱關(guān)聯(lián)關(guān)系構(gòu)成。隨著用戶在電子商務(wù)系統(tǒng)中用戶行為數(shù)據(jù)的增多，隱性社會網(wǎng)絡(luò)規(guī)模越來越大，網(wǎng)絡(luò)密度也逐漸變大。由于本文構(gòu)建的隱性社會網(wǎng)絡(luò)與一般社會網(wǎng)絡(luò)本質(zhì)上具有類似的性質(zhì)，因此同樣可以進行網(wǎng)絡(luò)社團的劃分，進而對社團內(nèi)部進行個性化商品推薦。

2 算法思想與設(shè)計

2.1 算法的基本思想

由于通過網(wǎng)絡(luò)社團劃分得到的各個社團中的用戶之間存在更強的相似性，因此社團內(nèi)部成員之間的推薦更容易被采納。對電子商務(wù)系統(tǒng)中存在的稀疏而龐大的隱性社會網(wǎng)絡(luò)通過傳統(tǒng)的Newman快速算法進行網(wǎng)絡(luò)社團的劃分，找到具有相似興趣愛好的團體，當有新項目加入進來時，若有用戶對其產(chǎn)生行為，則搜索網(wǎng)絡(luò)找到該用戶所在社團，再將該項目推薦給社團內(nèi)其他成員，可以緩解傳統(tǒng)推薦算法中存在的基本問題。

2.2 算法的設(shè)計

（1）對隱性社會網(wǎng)絡(luò)利用Newman快速算法思想進行網(wǎng)絡(luò)社團劃分，并通過模塊度Q來度量社團劃分的合理性。 Newman定義模塊度為社區(qū)內(nèi)部的總邊數(shù)和網(wǎng)絡(luò)中總邊數(shù)的比例減去1個期望值，模塊度Q的計算如公式（1）：

其中， 表示點v的度； 表示點v所在的社區(qū)；a函數(shù) 的取值定義為：如果v和w在一個社區(qū)，及 則為1，否則為0。m為網(wǎng)絡(luò)中邊的總數(shù)。

本文采用一個向上聚集的方法，設(shè)定網(wǎng)絡(luò)Ⅳ個獨立的社團，即初始化網(wǎng)絡(luò)社團為一個用戶為一個社區(qū)。用Ⅳ維單位矩陣表示網(wǎng)絡(luò)社團結(jié)構(gòu)，定義兩個變量，如公式（2）和（3）：

其中，公式（2）表示社區(qū)i和社區(qū)J內(nèi)部邊數(shù)目的和與總邊數(shù)的比例；公式（3）表示社區(qū)i內(nèi)部的點所關(guān)聯(lián)的所有的邊數(shù)目與總邊數(shù)的比例。則模塊度Q的計算簡化為公式（4）：

按照Newman的定義，當Q近似于O時，表示該網(wǎng)絡(luò)社團劃分效果不佳，相反，若Q接近于l，則表示該網(wǎng)絡(luò)社團劃分最優(yōu)。

（2）根據(jù)網(wǎng)絡(luò)社團劃分算法，對電子商務(wù)系統(tǒng)中用戶間存在的整個隱性社會網(wǎng)絡(luò)進行劃分，取模塊度Q值最大時得到的網(wǎng)絡(luò)社團。網(wǎng)絡(luò)社團結(jié)構(gòu)用二維矩陣來表示，如圖3。endprint

其中矩陣中的行代表網(wǎng)絡(luò)社團，列代表用戶，其中數(shù)值l表示用戶在相應(yīng)的社區(qū)內(nèi)，相反O表示不在社區(qū)內(nèi)。

（3）當系統(tǒng)中某個用戶j對某個項目i進行了某種行為，根據(jù)社團內(nèi)部成員之間具有較高相似性的特點，通過遍歷找到該用戶所在的社團，向該社團內(nèi)部其他成員推薦該項目。

3 實驗設(shè)計及驗證

3.1 實驗數(shù)據(jù)集說明

本文的研究對象是電商中的隱性社會網(wǎng)絡(luò)，對該網(wǎng)絡(luò)的分析需要用戶對項目的行為信息及用戶間關(guān)系信息等進行收集，而真實數(shù)據(jù)涉及商業(yè)機密，故難以獲取。而由明尼蘇達大學(xué)的G roupLens研究小組收集的MovieLens網(wǎng)站的電影評分數(shù)據(jù)集是用于驗證推薦算法的經(jīng)典數(shù)據(jù)，包括了用戶對電影作品的評分信息，評分值為1-5分，分值越高表示用戶越喜歡該電影，反之，表示用戶不喜歡該電影。該數(shù)據(jù)集本質(zhì)上和電商中用戶對商品的評分相似，故本文實驗驗證數(shù)據(jù)集中的用戶對項目行為信息中的評分信息由MovieLens數(shù)據(jù)集中的用戶對項目評分信息獲得具有一定的合理性。又因為真實電子商系統(tǒng)中用戶的行為符合隨機分布的特點，因此用戶其他行為，如瀏覽、搜索等數(shù)據(jù)以及用戶間關(guān)系信息由隨機模擬產(chǎn)生。

3.2 實驗評價標準 本文采用推薦的準確率和全面性去衡量推薦算法的效用。 用查全率（Recall Ratio，RR）衡量推薦的全面性，即針對某項目v，推薦算法得到的推薦用戶集中實際購買了該項目的用戶數(shù)量qr與測試數(shù)據(jù)集中購買該項目v的用戶總數(shù)量Q^t的比值。計算公式（5）：

用查準率（Precision Ratio，PR）衡量推薦準確度，即針對某項目v，推薦算法得到的最終推薦用戶集中實際購買了該項目的用戶數(shù)量q^r與推薦算法得到的最終推薦用戶集中用戶總數(shù)量Q^r的比值。計算公式如（6）：

其中查全率和查準率值越大，表示本文的推薦算法具有越好的推薦效果。

3.3 實驗方案

本文將實驗數(shù)據(jù)集分為訓(xùn)練集和測試集兩部分，訓(xùn)練集用來訓(xùn)練模型，測試集用來評估模型。為了驗證算法的推薦效果，本文在原始實驗數(shù)據(jù)集中隨機選取5組訓(xùn)練集和測試集，并在每組數(shù)據(jù)集上進行5次實驗，最后取平均值作為實驗的最終結(jié)果。

在訓(xùn)練集中，以隱性社會網(wǎng)路中某用戶Uⁱ的行為為觸發(fā)點，若用戶Uⁱ對某項目，I^j有瀏覽、收藏等行為信息，通過對網(wǎng)絡(luò)社團劃分后的隱性社會網(wǎng)絡(luò)中進行寬度優(yōu)先遍歷發(fā)現(xiàn)用戶Uⁱ所在的網(wǎng)絡(luò)社團，再將項目Ij推薦給該社團內(nèi)的其他所有用戶。最后通過與測試數(shù)據(jù)集中的數(shù)據(jù)進行查全率與查準率的計算，來評估本文算法的效果。

3.4 實驗結(jié)果及分析

使用R語言對算法進行編程實驗，首先對隱性社會網(wǎng)絡(luò)進行網(wǎng)絡(luò)社團劃分，結(jié)果如表l，再對模塊度Q值變化趨勢進行分析，得到變化曲線圖4：

從表1可知，當社團個數(shù)為8時，模塊度Q取得最大值，表明網(wǎng)絡(luò)社團劃分效果達到最優(yōu)。劃分的社團如下：

社團[1]：1，2，3，4，5，6，7；

社團[2]：8，9，10，11，12，13，14，15；

社團[3]：16，17，18，19；

社團[4]：

20， 21， 22， 23， 24， 25， 26， 27，28， 29， 30；

社團[5]：3l，32，33，34，35，36；

社團[6]：37，38，39，40，41，42，43；

社團[7]：44，45，46，47，48，49，50，51；

社團[8]： 52， 53， 54， 55.56， 57， 58，59。

得到最優(yōu)網(wǎng)絡(luò)社團后，對社團內(nèi)成員進行推薦，并通過查全率RR和查準率PR對推薦效果進行驗證。通過測試數(shù)據(jù)集對推薦效果進行驗證，得到查全率和查準率數(shù)據(jù)如表2所示。

如表2所示，5次實驗的查全率RR和查準率PR的平均值分別為：0.74和0.54，評價指標的值均大于0.5，表明本文的推薦算法有較好的推薦效果。

另外，當有一個新的項目進入系統(tǒng)時，由于缺乏歷史評價信息，傳統(tǒng)的協(xié)同過濾推薦算法無法對其進行推薦。本文提出的基于隱性社會網(wǎng)絡(luò)社團劃分的推薦方法，利用社會網(wǎng)絡(luò)社團劃分算法得到用戶間具有更緊密關(guān)系的網(wǎng)絡(luò)社團。并通過社團內(nèi)部用戶行為觸發(fā)產(chǎn)生推薦，大太縮小的推薦的范圍，使得推薦具有針對性，從而緩解了冷啟動問題并提高了推薦的準確度。

3.5 與傳統(tǒng)協(xié)同過濾算法比較

推薦系統(tǒng)的主要目的就是對用戶未來的喜好進行預(yù)測，從而進行精準的推薦。因此推薦的準確度是衡量一個推薦算法性能好壞的重要方面。

對于推薦準確度的評價采用平均絕對偏差（ Mean Abso-lute Error，MAE），通過計算目標用戶的預(yù)測評分與實際評分間的偏差來衡量預(yù)測的準確性，MAE的值越小，預(yù)測評分與實際評分的偏差越小，推薦的準確度也就越高。MAE定義如下：

其中， 是用戶u對項目i的真實評分； 是用戶u對項目i的預(yù)測評分； 為實驗數(shù)據(jù)中的測試集。

虛用相關(guān)相似性計算方法計算出用戶之間的相似度，記為Sim（u，v）。

其中，Sim（u，v）代表用戶u和用戶v之間的相似性；i^u，v代表用戶u和用戶v共同評過分的項目集合；R^u.i代表用戶u對項目i的評分； 表示用戶u的平均評分。

根據(jù)用戶間相似度對目標用戶未評分的項目進行評分預(yù)測，預(yù)測評分的計算公式如下，得到用戶——項目預(yù)測評分矩陣，采用上述的數(shù)據(jù)集產(chǎn)生推薦并與本文中的算法，運用R語言進行5次實驗對比比較，結(jié)果如圖5：

其中，這里的 分別代表用戶u和用戶v在自己所有評分項目上的平均評分；N（u）代表用戶u的最近鄰居集。

通過將本文推薦算法與傳統(tǒng)的協(xié)同過濾推薦算法比較，驗證本文推薦算法的準確性。實驗結(jié)果表明，本文提出推薦算法比傳統(tǒng)的協(xié)同過濾算法具有更高的推薦準確度，并在一定程度上緩解了傳統(tǒng)協(xié)同過濾推薦算法中的數(shù)據(jù)稀疏性問題。

4 結(jié)束語

基于“通過網(wǎng)絡(luò)社團劃分得到的各個社團中的用戶之間存在更強的相似性，因此社團內(nèi)部成員之間的推薦更容易被采納”的思想，本文利用網(wǎng)絡(luò)社團劃分的方法對電子商務(wù)系統(tǒng)中隱性社會網(wǎng)絡(luò)進行劃分，并提出了基于隱性社會網(wǎng)絡(luò)社團劃分的個性化商品推薦方法。在模型驗證時使用MovieLens數(shù)據(jù)集借助R語言對算法進行了有效性驗證。實驗結(jié)果表明，本文提出的基于隱性社會網(wǎng)絡(luò)社團劃分的個性化商品推薦方法，對推薦的質(zhì)量的提高有一定的輔助作用。

通過一定的社會網(wǎng)絡(luò)分析方法，對隱性社會網(wǎng)絡(luò)進行網(wǎng)絡(luò)社團劃分，可以得到聯(lián)系更加緊密的網(wǎng)絡(luò)社團，而劃分后的網(wǎng)絡(luò)社團內(nèi)部的用戶之間具有更加相似的消費偏好，以及更強的信任度。在今后的工作中，可以通過一定的方法對網(wǎng)絡(luò)中用戶的消費偏好進行分析，構(gòu)建消費偏好模型，根據(jù)該模型結(jié)合傳統(tǒng)的推薦算法進行商品推薦，將更加符合用戶的需求，達到更加高效的個性化商品推薦。endprint