彭　歡　張能福

(作者單位：五邑大學(xué)經(jīng)濟(jì)管理學(xué)院)

?

基于情感緊密度的社交網(wǎng)絡(luò)推薦算法

彭歡張能福

當(dāng)前的社交網(wǎng)絡(luò)推薦算法主要是基于內(nèi)容相似度或者好友相似度進(jìn)行推薦，忽略了社交網(wǎng)絡(luò)中情感值計(jì)算；而基于NAS算法的緊密度計(jì)算屬性邊權(quán)值靈活度不高，因而緊密度計(jì)算不夠準(zhǔn)確，不能產(chǎn)生較為理想的推薦效果。針對(duì)上述兩個(gè)問(wèn)題，提出了基于情感緊密度的社交網(wǎng)絡(luò)推薦算法，以達(dá)到社交網(wǎng)絡(luò)推薦準(zhǔn)確率的提高。實(shí)驗(yàn)證明，該方法在提高短號(hào)集團(tuán)網(wǎng)絡(luò)的推薦準(zhǔn)確率方面較為理想。

緊密度；推薦準(zhǔn)確率；情感值計(jì)算；NAS算法

一、引言

短號(hào)集團(tuán)社交網(wǎng)絡(luò)上的推薦問(wèn)題，不同于傳統(tǒng)的推薦系統(tǒng)，傳統(tǒng)社交網(wǎng)絡(luò)推薦系統(tǒng)主要基于以下幾類來(lái)進(jìn)行推薦：第一、基于用戶節(jié)點(diǎn)愛好之間的相似度來(lái)進(jìn)行推薦；第二、基于共同好友之間的相似度來(lái)進(jìn)行推薦；第三、基于以上兩類之間的相似度來(lái)進(jìn)行推薦。然而，對(duì)于用戶節(jié)點(diǎn)之間的通話除了固有的工作需求，還存在生活好友之間的聯(lián)系需求，以上推薦系統(tǒng)對(duì)于情感緊密度的計(jì)算都鮮有涉及，因此也難以提供較為理想的推薦效果[4][5][6]。

集團(tuán)社交網(wǎng)絡(luò)中的推薦系統(tǒng)所服務(wù)對(duì)象是單個(gè)自然人用戶節(jié)點(diǎn)，其推薦的內(nèi)容主要為向用戶推薦最為有利的短號(hào)集團(tuán)網(wǎng)絡(luò)。對(duì)于單向交流的推薦，通過(guò)計(jì)算用戶節(jié)點(diǎn)與集團(tuán)網(wǎng)絡(luò)內(nèi)的部分用戶節(jié)點(diǎn)間的交流頻率、情感強(qiáng)度，進(jìn)而得出用戶與集團(tuán)之間的緊密度，根據(jù)緊密度最高值進(jìn)行推薦的方法通常能達(dá)到很理想的推薦效果。

針對(duì)以上問(wèn)題，本文主要解決的是用戶節(jié)點(diǎn)與集團(tuán)社交網(wǎng)絡(luò)通話記錄的情感緊密度計(jì)算，具體分為兩大類：工作關(guān)系需求分析對(duì)于推薦集團(tuán)社交網(wǎng)絡(luò)的影響，通過(guò)緊密度分析計(jì)算用戶節(jié)點(diǎn)間的緊密度權(quán)值；生活關(guān)系對(duì)于推薦集團(tuán)網(wǎng)絡(luò)的影響，通過(guò)緊密度分析計(jì)算用戶節(jié)點(diǎn)間的緊密度權(quán)值。通過(guò)以上分析計(jì)算，再進(jìn)行歸類，統(tǒng)計(jì)用戶節(jié)點(diǎn)與各個(gè)集團(tuán)社交網(wǎng)絡(luò)的權(quán)值大小，利用改進(jìn)的NAS算法計(jì)算自然人與集團(tuán)之間的緊密度，根據(jù)緊密度向自然人推薦集團(tuán)社交網(wǎng)絡(luò)，進(jìn)而提高推薦的準(zhǔn)確度[1]。

二、改進(jìn)的NAS算法

基于節(jié)點(diǎn)屬性相似性的NAS算法計(jì)算方法是：對(duì)任意兩節(jié)點(diǎn)計(jì)算屬性相似度，每增加一個(gè)共同屬性，其邊權(quán)值就加1，由此來(lái)判斷兩節(jié)點(diǎn)之間的緊密度。然而自然人與集團(tuán)社交網(wǎng)絡(luò)各用戶之間的緊密程度各有不同，邊權(quán)值大小不一[2]。改進(jìn)的NAS算法基于邊權(quán)值不同的思想，對(duì)原有的算法進(jìn)行改進(jìn)，計(jì)算方法如下：

假定兩節(jié)點(diǎn)i和j共有N個(gè)聯(lián)系人，對(duì)于第k條通話ak(1kN)，先計(jì)算節(jié)點(diǎn)聯(lián)系人k的情感緊密值xk，每增加一個(gè)聯(lián)系人，其邊權(quán)值就加xk，即：

ifi.ak=j.ak，Wnas(i,j)=Wnas(i,j)+xk

公式表示為：

Wnas(i,j)+=(xk-|i.ak-j.ak|)

由上式計(jì)算方法可知，自然人與集團(tuán)社交網(wǎng)絡(luò)之間的值越高，就越緊密，反之，則緊密度越低。選取緊密度最高的集團(tuán)社交網(wǎng)絡(luò)給予推薦能達(dá)到較為理想的效果。

三、情感緊密值分析

下面結(jié)合默認(rèn)日常工作時(shí)間，給出影響情感傾向性的兩種時(shí)間段的情感緊密值計(jì)算規(guī)則。

對(duì)于一個(gè)自然人，有工作時(shí)段情感系數(shù)、生活時(shí)間情感系數(shù)、通話頻率和情感值4個(gè)概念，分別記為Work(value)、Life(value)、Frequency(value)和Socre。影響用戶之間通話情感值的關(guān)系分為兩種，分別為：工作關(guān)系和生活關(guān)系。工作關(guān)系本身的情感強(qiáng)度低于生活關(guān)系的情感強(qiáng)度，情感程度直接影響情感系數(shù)的取值。工作時(shí)段情感系數(shù)表示處于工作時(shí)間段通話所包含的情感值，設(shè)為0.5；生活時(shí)間情感系數(shù)表示處于生活時(shí)間段通話所包含的情感值，設(shè)為1；通話頻率表示工作時(shí)間段和生活時(shí)間段分別所含的次數(shù)。自然人與集團(tuán)內(nèi)客戶通話情感程度計(jì)算規(guī)則如式(1)所示：

Socre=Work(value)Frequency(value)+Life(value)Frequency(value)(1)

說(shuō)明：當(dāng)自然人與集團(tuán)內(nèi)某些客戶僅存在工作關(guān)系時(shí)，生活時(shí)間情感系數(shù)與通話頻率的組合情感值默認(rèn)為0，同理當(dāng)自然人與集團(tuán)內(nèi)某些客戶僅存在生活關(guān)系時(shí)，工作時(shí)間情感系數(shù)與通話頻率的組合情感值默認(rèn)為0。

四、基于情感緊密度的用戶圖

首先建立邊無(wú)權(quán)值的初步用戶圖(如圖1樣式)。用戶圖表示為G=。其中，V表示用戶節(jié)點(diǎn)；E表示用戶節(jié)點(diǎn)間的聯(lián)系。如果自然人與甲存在聯(lián)系，且甲屬于某個(gè)集團(tuán)網(wǎng)絡(luò)，那么此集團(tuán)網(wǎng)絡(luò)節(jié)點(diǎn)V則包含了甲，會(huì)有一條邊到達(dá)此集團(tuán)網(wǎng)絡(luò)節(jié)點(diǎn)，若自然人與此集團(tuán)用戶乙同樣存在聯(lián)系，也會(huì)只有一條邊連接到此集團(tuán)網(wǎng)絡(luò)節(jié)點(diǎn)[7]。如果甲不屬于某個(gè)集團(tuán)網(wǎng)絡(luò)，則會(huì)有一條邊直接連接到甲。

圖1　初步用戶圖

通過(guò)以上步驟得到一個(gè)無(wú)權(quán)的初步用戶圖，下面將為其加上基于用戶情感緊密度的邊權(quán)值。具體步驟為：由情感緊密值分析計(jì)算源節(jié)點(diǎn)與各聯(lián)系人之間的情感緊密值，將屬于同一集團(tuán)網(wǎng)絡(luò)的情感值進(jìn)行加成，再由改進(jìn)的NAS算法遍歷圖中的每一個(gè)節(jié)點(diǎn)，逐一計(jì)算該自然人節(jié)點(diǎn)集團(tuán)網(wǎng)絡(luò)之間的情感緊密度，并將其作為邊權(quán)值保存于圖中。從而創(chuàng)建帶邊權(quán)值的完整用戶圖。

算法 Improved NAS

InputG為無(wú)權(quán)值的初步用戶圖，A[H][N]為節(jié)點(diǎn)屬性矩陣，X[N]為各條通話所得情感值，H為集團(tuán)網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)，N為通話總數(shù)。

Output G’為擁有自然人情感緊密度的用戶圖

1：for each attribute akin all attributes do

2：Wnas(i,j)=Wnas(i,j)+(X[N]-|A[i][N]-A[j][N]|)

3：end for

五、實(shí)驗(yàn)分析

實(shí)驗(yàn)數(shù)據(jù)采用江門移動(dòng)2014年11月至12月的集團(tuán)通訊錄中的加密數(shù)據(jù)，對(duì)其進(jìn)行歸納整理，隨機(jī)選取其中183個(gè)集團(tuán)網(wǎng)絡(luò)用戶，從中剔除異地記錄數(shù)據(jù)4522條，得出13587條有效數(shù)據(jù)。將屬于同一集團(tuán)的數(shù)據(jù)打包，通過(guò)情感緊密度分析規(guī)則計(jì)算其中每條數(shù)據(jù)情感值，分別采用NAS算法和改進(jìn)的NAS算法進(jìn)行緊密度的計(jì)算賦予邊權(quán)值，從中挑選邊權(quán)值最大的集團(tuán)社交網(wǎng)絡(luò)進(jìn)行推薦，對(duì)比該用戶所在真實(shí)集團(tuán)網(wǎng)絡(luò)驗(yàn)證正確率。將兩種方法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，如表1所示：

表1　兩種計(jì)算方法的實(shí)驗(yàn)結(jié)果對(duì)比

從表1中可得出如下結(jié)論：

基于情感緊密度的計(jì)算方法的整體準(zhǔn)確率為92.35%，相對(duì)于基于NAS算法的計(jì)算方法的整體準(zhǔn)確率為83.06%，提高了9.29個(gè)百分點(diǎn)。進(jìn)而基于情感緊密度的集團(tuán)社交網(wǎng)絡(luò)推薦效果更加理想。

六、結(jié)論

本文通過(guò)對(duì)自然人通話信息數(shù)據(jù)進(jìn)行預(yù)處理的基礎(chǔ)上，分別利用NAS算法和基于情感緊密度的改進(jìn)NAS算法對(duì)自然人與集團(tuán)網(wǎng)絡(luò)之間的緊密度進(jìn)行計(jì)算。得出如下結(jié)論：NAS算法僅僅利用兩節(jié)點(diǎn)間共有屬性進(jìn)行緊密度計(jì)算，忽略了自然人基于情感層面的計(jì)算，產(chǎn)生的推薦結(jié)果準(zhǔn)確率不高。

針對(duì)這種情況，本文提出的基于情感緊密度的社交網(wǎng)絡(luò)推薦方法是基于情感緊密值分析和基于改進(jìn)NAS算法緊密度計(jì)算，對(duì)屬性的邊權(quán)值進(jìn)行有效的計(jì)算。實(shí)驗(yàn)結(jié)果表明：本文所提出的基于情感緊密度的社交網(wǎng)絡(luò)推薦方法準(zhǔn)確度更高，更加符合現(xiàn)實(shí)。

(作者單位：五邑大學(xué)經(jīng)濟(jì)管理學(xué)院)

[1]Liu H，Salerno J J，Young M J.Social Computing，Behavioral Modeling，and Predicition[M].Karsten Steinhaeuser，USA:Springer，2008:168-175.

[2]陳克寒，韓盼盼，吳健.基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法[J].計(jì)算機(jī)學(xué)報(bào),2013,(2):349-359

[3]熊正理，姜文君，王國(guó)軍.基于用戶緊密度的在線社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)工程,2013,(8):50-54

[4]羅森林，潘麗敏.情感計(jì)算理論與技術(shù)[J].系統(tǒng)工程與電子技術(shù),2003,(7):905-909

[5]Yasuda Y.，Kawarnoto S.，Ebata A.，Okitsu J.，2003.Concept and evaluation of X-NAS:a highly scalable NAS system.Mass Storage Systems and Technologies，2003，(6):219 - 227.

[6]萬(wàn)常選，江騰蛟，鐘敏娟，邊海榮.基于詞性標(biāo)注和依存句法的Web金融信息情感計(jì)算[J].計(jì)算機(jī)研究與發(fā)展,2013,50(12):2554-2569

[7]Chen J，Geuer W，Dugan C，Muller M，Guy I．Make new friends，but keep the old：Recommending people on social networking sites//Proceedings of the 27th International Conference on Human Factors in Computing Systems ．New York，NY，USA，2009：201-210