基于隱性社會網絡社團劃分的推薦方法研究

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

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

[關鍵詞]隱性社會網絡；社團劃分；個性化推薦

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

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

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

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

1 隱性社會網絡定義

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

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

2 算法思想與設計

2.1 算法的基本思想

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

2.2 算法的設計

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

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

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

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

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

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

其中矩陣中的行代表網絡社團，列代表用戶，其中數值l表示用戶在相應的社區(qū)內，相反O表示不在社區(qū)內。

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

3 實驗設計及驗證

3.1 實驗數據集說明

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

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

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

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

3.3 實驗方案

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

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

3.4 實驗結果及分析

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

從表1可知，當社團個數為8時，模塊度Q取得最大值，表明網絡社團劃分效果達到最優(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)網絡社團后，對社團內成員進行推薦，并通過查全率RR和查準率PR對推薦效果進行驗證。通過測試數據集對推薦效果進行驗證，得到查全率和查準率數據如表2所示。

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

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

3.5 與傳統協同過濾算法比較

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

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

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

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

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

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

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

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

4 結束語

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

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