基于隱性社會(huì)網(wǎng)絡(luò)社團(tuán)劃分的推薦方法研究

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

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

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

[中圖分類號(hào)]TP39 [文獻(xiàn)標(biāo)識(shí)碼]A [文章編號(hào)]1008-0821（2015）05-0049-05

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

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

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

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

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

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

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

2.1 算法的基本思想

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

2.2 算法的設(shè)計(jì)

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)及驗(yàn)證

3.1 實(shí)驗(yàn)數(shù)據(jù)集說(shuō)明

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

3.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn) 本文采用推薦的準(zhǔn)確率和全面性去衡量推薦算法的效用。 用查全率（Recall Ratio，RR）衡量推薦的全面性，即針對(duì)某項(xiàng)目v，推薦算法得到的推薦用戶集中實(shí)際購(gòu)買了該項(xiàng)目的用戶數(shù)量qr與測(cè)試數(shù)據(jù)集中購(gòu)買該項(xiàng)目v的用戶總數(shù)量Q^t的比值。計(jì)算公式（5）：

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

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

3.3 實(shí)驗(yàn)方案

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

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

3.4 實(shí)驗(yàn)結(jié)果及分析

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

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

社團(tuán)[1]：1，2，3，4，5，6，7；

社團(tuán)[2]：8，9，10，11，12，13，14，15；

社團(tuán)[3]：16，17，18，19；

社團(tuán)[4]：

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

社團(tuán)[5]：3l，32，33，34，35，36；

社團(tuán)[6]：37，38，39，40，41，42，43；

社團(tuán)[7]：44，45，46，47，48，49，50，51；

社團(tuán)[8]： 52， 53， 54， 55.56， 57， 58，59。

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

如表2所示，5次實(shí)驗(yàn)的查全率RR和查準(zhǔn)率PR的平均值分別為：0.74和0.54，評(píng)價(jià)指標(biāo)的值均大于0.5，表明本文的推薦算法有較好的推薦效果。

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

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

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

對(duì)于推薦準(zhǔn)確度的評(píng)價(jià)采用平均絕對(duì)偏差（ Mean Abso-lute Error，MAE），通過(guò)計(jì)算目標(biāo)用戶的預(yù)測(cè)評(píng)分與實(shí)際評(píng)分間的偏差來(lái)衡量預(yù)測(cè)的準(zhǔn)確性，MAE的值越小，預(yù)測(cè)評(píng)分與實(shí)際評(píng)分的偏差越小，推薦的準(zhǔn)確度也就越高。MAE定義如下：

其中， 是用戶u對(duì)項(xiàng)目i的真實(shí)評(píng)分； 是用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分； 為實(shí)驗(yàn)數(shù)據(jù)中的測(cè)試集。

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

其中，Sim（u，v）代表用戶u和用戶v之間的相似性；i^u，v代表用戶u和用戶v共同評(píng)過(guò)分的項(xiàng)目集合；R^u.i代表用戶u對(duì)項(xiàng)目i的評(píng)分； 表示用戶u的平均評(píng)分。

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

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

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

4 結(jié)束語(yǔ)

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

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