鄧鐘晟

(東華大學(xué)計算機科學(xué)與技術(shù)學(xué)院，上海 201600)

0 引言

近年來，隨著在線社交網(wǎng)絡(luò)服務(wù)［1］的迅速發(fā)展。許多知名網(wǎng)站如新浪微博、Facebook、豆瓣等吸引了巨大數(shù)量的用戶，對互聯(lián)網(wǎng)環(huán)境產(chǎn)生了巨大影響［2］。在線社交網(wǎng)絡(luò)通過用戶間相似的教育、地理等背景以及共同興趣，為人與人之間的信息共享和社交開辟了新的渠道［3］。其開放性促使用戶產(chǎn)生大量的輕量數(shù)據(jù)，如標(biāo)簽、評論、話題、作品。每個用戶的數(shù)據(jù)都能反映出用戶的特征，通過抽象這些數(shù)據(jù)，進行比較，可以評估用戶之間的關(guān)系強度。

熵在生態(tài)學(xué)中可用于反映生物在地區(qū)分布中的多樣性，通過熵模型，可以反映用戶間在不同地點、不同時間的出現(xiàn)的分布情況，進而判斷用戶的關(guān)系強度。文獻(xiàn)［4］通過比較用戶的簽到數(shù)據(jù)，推斷用戶在時空上的社會關(guān)系強度，在效率和效果上都有良好的表現(xiàn)。本文在此基礎(chǔ)上，將用戶數(shù)據(jù)在不同事物、不同關(guān)鍵詞上的分布情況通過熵模型進行計算，從而得到用戶在社交網(wǎng)絡(luò)中關(guān)系強度。

1 數(shù)據(jù)定義

1.1 興趣集合

當(dāng)用戶在網(wǎng)絡(luò)上發(fā)布文字時，服務(wù)器上將記錄以下信息:

其中用戶id 為數(shù)據(jù)庫標(biāo)示用戶的索引;主題編號為文本信息所表述的對象，在社交網(wǎng)絡(luò)的輕量數(shù)據(jù)中，主題編號可以是微博中的某一話題、某位熱點人物、某類商品;文本信息為用戶在目標(biāo)主題上的看法、感受等。將文本信息切分成意義明確的單詞，這些數(shù)據(jù)可以表示為一個三元組＜u(user)，i(item)，t(token)＞。其中u 表示用戶的id，i 為主題，t 為單詞。從而元組＜u，i，t ＞可以表示用戶u 在主題i 的關(guān)鍵詞為t。例如，用戶u1在世界杯主題下發(fā)表了“C 羅加油，葡萄牙加油”的評論，可以得到三元組＜u1，“世界杯”，”C羅”＞，＜u1，“世界杯”，”葡萄牙”＞，＜u1，“世界杯”，”加油”＞。顯然，這些三元組的集合可以在一定程度上描述一個用戶的特點和興趣。

假設(shè)用戶u1有以下三元組:

將用戶u1在所有的主題中的信息整合成一個向量，則用戶u1的興趣向量可以表示為:

表示用戶在主題i1上的關(guān)鍵詞為t1，t2，在主題i2上的關(guān)鍵詞為t3，在主題i3上的關(guān)鍵詞為t2，t4。最后，任意用戶ui在M(1，2，...，m)個主題上分別有k 個關(guān)鍵詞，則可以得到用戶的興趣向量為Vi=(＜t1，1，t1，2，…，t1，k1＞，＜t2，1，t2，2，…，t2，k2＞，…，＜tm，1，tm，2，…，tm，km＞)

1.2 同現(xiàn)向量

若2 個用戶在同一個主題上有相同的關(guān)鍵詞，則可以認(rèn)為2 位用戶有相同的興趣。從而可以得到用戶a 和用戶b 之間的相同關(guān)鍵詞出現(xiàn)的向量(同現(xiàn)向量):

其中Cab，i表示用戶a 和用戶b 在主題i 上出現(xiàn)的相同關(guān)鍵詞的個數(shù)。例如，假設(shè)有8 項主題，用戶u1，u2在主題上的興趣向量如下:

則用戶間同現(xiàn)向量為C12=(1，1，1，0，0，0，0，0)，通常情況下，主題的總數(shù)是巨大的，每個用戶相關(guān)的主題在主題集合之中只能占到極小的部分，因此同現(xiàn)向量與用戶興趣向量中的值多數(shù)為0。同現(xiàn)向量表示了用戶之間相同興趣在主題集合上的分布情況。

2 熵模型

熵模型通過Renyi 熵和區(qū)位熵推斷2 個用戶在社交網(wǎng)絡(luò)上的關(guān)系強度。其中Renyi 熵是香農(nóng)熵的推廣，用于計算同現(xiàn)向量的多樣性［5］。而區(qū)位熵是基于主題權(quán)重的計算，用于消除熱門主題對社會關(guān)系強度造成的誤差影響。

2.1 多樣性

多樣性的概念被廣泛地用在物理學(xué)、經(jīng)濟學(xué)、生物學(xué)等領(lǐng)域，用于評估目標(biāo)系統(tǒng)的豐富程度。對于本文的同現(xiàn)向量，可以認(rèn)為相同興趣更具有多樣性(更廣泛)的人之間擁有更強的社會聯(lián)系，對于以下3 個同現(xiàn)向量:

可以注意到用戶1 和用戶2 之間有5 個相同興趣，用戶2 和用戶3 為4 個，用戶1 和用戶3 為1 個，雖然擁有同樣多的相同關(guān)鍵詞，但是不難理解C12比C23更具有多樣性，C23比C13更具有多樣性，因此用戶1 和用戶2 之間具有更強的社會關(guān)系。

熵模型正是使用同現(xiàn)向量的多樣性這一指標(biāo)，度量2 個用戶間同現(xiàn)向量所代表的有效主題的數(shù)量，得到用戶同現(xiàn)向量多樣性豐富程度的比例中項，進而評估用戶間的關(guān)系強度。

2.2 香農(nóng)熵

香農(nóng)熵是一種評估樣本多樣性的模型，定義了用于描述樣本不確定性程度大小的度量熵(簡稱為香農(nóng)熵)。當(dāng)概率分布P 的不確定性程度越大時，其對應(yīng)的熵值越大;反之，其熵值越小。在主題文本的應(yīng)用環(huán)境下表示用戶a 和b 在主題i存在相同關(guān)鍵詞表示用戶a 和b 在主題i 上的相同關(guān)鍵詞的合集，是用戶a 和b所有相同興趣關(guān)鍵詞的合集，則用戶在主題i 上相同關(guān)鍵詞的概率為。用戶a 和b 的同現(xiàn)向量的香農(nóng)熵為:

香農(nóng)熵的多樣性指數(shù)［6］為:

以上文中的3 個同現(xiàn)向量為例，香農(nóng)熵的多樣性指數(shù)如下:C12=5.0，C23=3.789，C13=1.0。正確地反映了3 個同現(xiàn)向量的多樣性。

2.3 Renyi 熵

對于香農(nóng)熵的多樣性而言，興趣向量在一個主題上的高頻次會使計算結(jié)果產(chǎn)生和實際情況不相符的誤差［7］。將香農(nóng)熵推廣到Renyi 熵［8］后，可以通過q的取值控制多次重復(fù)對計算結(jié)果的影響。Renyi 熵的定義如下:

Renyi 熵的多樣性:

其中fab=∑iCab，i表示用戶a 和b 的相同興趣關(guān)鍵詞的總數(shù)。Cab，i表示用戶a 和b 在主題i 上的相同興趣關(guān)鍵詞個數(shù)。

公式(4)表示了由Renyi 熵給出的相同興趣向量的多樣性，其中q 為多樣性級數(shù)，文獻(xiàn)［9］闡述了多樣性級數(shù)對Renyi 熵計算結(jié)果的影響，證明過程本文不再贅述，其q 值的變化反映了局部頻率的權(quán)重:

1)q ＞1，局部頻率Cab，i越大，其權(quán)重越大，對多樣性的影響力越大。

2)q ＜1，局部頻率Cab，i越小，其權(quán)重越大。

3)q=0，多樣性與Cab，i無關(guān)，為相同興趣的個數(shù)。

4)q=1，Renyi 熵及其多樣性分別轉(zhuǎn)化為香農(nóng)熵及其多樣性。

例如對于相同興趣向量Cab=(10，1，0，0，9)與Ccd=(2，3，2，2，3)，香農(nóng)熵多樣性為Dab=2.35，Dcd=4.90。而Renyi 熵的多樣性(q=0.5)分別為Dab=24.60，Dcd=279.67?？梢钥闯鲇脩鬰 和d 之間同現(xiàn)向量的多樣性評分顯著高于用戶a 和b，且Renyi 熵提高了均勻分布樣本的多樣性指數(shù)。

3 權(quán)重頻率

對于熱門主題，參與的用戶數(shù)量與冷門主題的用戶數(shù)量相差較大。因此，在熱門主題中更有可能出現(xiàn)相同的關(guān)鍵詞。顯然，這些相同關(guān)鍵詞與冷門主題中的相同關(guān)鍵詞相比更有可能是巧合，或是較為普遍的關(guān)鍵詞。因而這些關(guān)鍵詞在社會關(guān)系強度的評分上應(yīng)當(dāng)進行適當(dāng)?shù)臋?quán)重修正。本文將區(qū)位熵引入模型，從而對熱門主題中的關(guān)鍵詞評分進行修正。

區(qū)位熵可以用于衡量一個區(qū)域的熱門程度［10］。計算結(jié)果區(qū)位熵越大，表示該地方越受歡迎。在本文中，將區(qū)位熵用于衡量一個主題的熱門程度。通過訪問主題的用戶數(shù)量計算主題的熱門程度。其表達(dá)式如下:

其中Pu，i=|Vi，u|/|Vi|表示用戶u 訪問主題i 的概率，Vi，u={＜u，i，t ＞:?t}表示用戶u 訪問主題i 的集合，Vi={＜u，i，t ＞:?t，?u}表示所有用戶訪問主題i 的集合。

則加權(quán)頻率為:

同樣以相同興趣向量Cab=(10，1，0，0，9)、Ccd=(2，3，2，2，3)為例，假設(shè)主題1 與主題5 為熱門主題，另有其他20 名用戶訪問，且每人訪問10 次，可以得到加權(quán)頻率Fab=1.10，F(xiàn)cd=3.07?？梢园l(fā)現(xiàn)使用加權(quán)頻率提高了在冷門主題中的關(guān)鍵詞的權(quán)重。

4 社會關(guān)系強度

上文闡述了用相同興趣向量評估用戶關(guān)系強度的2 種相互獨立的方法，多樣性分析的是用戶在主題維度上的分布，加權(quán)頻率則關(guān)注的是主題本身的熱門程度。因此用戶間在社交網(wǎng)絡(luò)上的關(guān)系強度與這2個獨立變量線性相關(guān)，從而得到用戶a 和b 間社會關(guān)系強度的表達(dá)式:

其中參數(shù)α，β，γ 需通過對已知好友關(guān)系的數(shù)據(jù)集學(xué)習(xí)獲得。文獻(xiàn)［4］比較了3 種評估關(guān)系強度的技術(shù)，分別為杰卡德距離、亞當(dāng)/亞達(dá)相似性［11］、卡茨評分。其中卡茨評分在熵模型的召回率與準(zhǔn)確率上變化較為平滑，訓(xùn)練效果較好。

卡茨評分通過計算用戶與用戶在社交網(wǎng)絡(luò)上的關(guān)系距離，從而評估用戶間的關(guān)系強度，用戶a 與用戶b 之間的卡茨評分定義如下:

其中Pab，l表示從用戶a 到用戶b 好友路徑長度為l 的集合，ε 是一個正常數(shù)，隨著l 的增長，ε 能減少其對卡茨評分的影響，最優(yōu)值應(yīng)在10-3數(shù)量級上［12］。在實際應(yīng)用中，考慮六度分割理論［13］，長度大于4 的路徑對卡茨評分的影響較小，可以忽略不計。

5 實 驗

5.1 實驗數(shù)據(jù)

實驗使用了last.fm 網(wǎng)站提供的用戶數(shù)據(jù)，last.fm 網(wǎng)站提供了用戶各類音樂專輯、曲目的數(shù)據(jù)，允許用戶對這些音樂條目打上自定義的標(biāo)簽，并且提供了好友關(guān)注的社交功能［14］。數(shù)據(jù)分為3 部分:1)用戶數(shù)據(jù)，用戶的數(shù)字編號標(biāo)示的用戶數(shù)據(jù)，總計99 405條。2)好友關(guān)系信息，以2 個用戶編號為一組的好友關(guān)系對，總計3 151 283 對。3)標(biāo)簽信息，以用戶編號、條目編號、標(biāo)簽編號組成的三元組，條目編號1 393 559條，標(biāo)簽編號281 818 條。用戶的相關(guān)參數(shù)統(tǒng)計如表1 所示。

表1 數(shù)據(jù)集中用戶相關(guān)參數(shù)的統(tǒng)計信息

5.2 實驗方法

本實驗使用數(shù)據(jù)集中一半的數(shù)據(jù)進行訓(xùn)練，用剩下的數(shù)據(jù)對實驗結(jié)果進行評估。

實驗分為4 個部分:1)計算同現(xiàn)向量;2)計算向量的Renyi 熵多樣性及區(qū)位熵;3)通過卡茨評分學(xué)習(xí)模型參數(shù);4)將模型參數(shù)代入剩余數(shù)據(jù)集檢驗。

首先，為了提高數(shù)據(jù)的處理效率，采用Hadoop［15］分布式平臺下MapReduce 框架［16］計算同現(xiàn)向量。

處理過程分為2 步:1)Map 將標(biāo)簽信息以條目編號分組，Reduce 得到每個條目下各個用戶的所有標(biāo)簽。2)Map 計算各個條目中出現(xiàn)局部同現(xiàn)向量，并以用戶關(guān)系對進行分組，Reduce 將局部同現(xiàn)向量合并，從而獲得完整的同現(xiàn)向量。在第一步中同時計算各個條目的區(qū)位熵，而在第二步的Reduce 過程上，可以計算同現(xiàn)向量的Renyi 熵的多樣性。在得到數(shù)據(jù)集的用戶同現(xiàn)向量之后，通過卡茨評分計算關(guān)系強度的估計值。使用最小二乘法［17］進行線性回歸，則α，β，γ 的最優(yōu)值可由公式(9)獲得:

最后，將得到的參數(shù)＜α，β，γ ＞代入公式(7)中，用剩余的數(shù)據(jù)集求得關(guān)系強度Sab。

5.3 實驗結(jié)果

在剩余的數(shù)據(jù)集中，對計算結(jié)果使用召回率與準(zhǔn)確率進行評估。召回率和準(zhǔn)確率與關(guān)系強度閾值的關(guān)系如圖1 所示。圖中橫坐標(biāo)為關(guān)系強度閾值，縱坐標(biāo)為百分比。隨著關(guān)系強度閾值的提高，召回率逐漸下降，準(zhǔn)確率逐漸提高。

圖1 模型的召回率與準(zhǔn)確率

6 結(jié)束語

本文提出了一種基于社交網(wǎng)絡(luò)主題文本推斷關(guān)系強度的熵模型。首先介紹了香農(nóng)熵和Renyi 熵用于分析在用戶間同現(xiàn)向量多樣性的計算方法，然后介紹了區(qū)位熵對熱門主題權(quán)重的修正方法，最后使用卡茨評分對用戶在社交網(wǎng)絡(luò)上的關(guān)系強度進行估計，并用于模型學(xué)習(xí)。獲得的參數(shù)結(jié)果在召回率和準(zhǔn)確率上都有良好的表現(xiàn)。

［1］王亮.SNS 社交網(wǎng)絡(luò)發(fā)展現(xiàn)狀及趨勢［J］.現(xiàn)代電信科技，2009，39(6):9-13.

［2］周鵬飛.國內(nèi)有關(guān)SNS 網(wǎng)站的研究綜述［J］.現(xiàn)代情報，2010，30(7):174-177.

［3］劉耀庭.社交網(wǎng)絡(luò)結(jié)構(gòu)研究［D］.杭州:浙江大學(xué)，2008.

［4］Pham H，Shahabi C，Liu Yan.Ebm:An entropy-based model to infer social strength from spatiotemporal data［C］// ACM SIGMOD Conference.2013:265-276.

［5］李冠國.多樣性指數(shù)的應(yīng)用［J］.海洋科學(xué)，1981(2):4-8.

［6］Jost L.Entropy and diversity［J］.Oikos，2006，113(2):363-375.

［7］Maszczyk T，Duch W.Comparison of Shannon，Renyi and Tsallis entropy used in decision trees［C］// Proceedings of the 9th Internation Conference on Artificial Intelligence and Soft Computing-ICAISC 2008.Springer Berlin Heidelberg，2008:643-651.

［8］˙Zyczkowski K.Rényi extrapolation of Shannon entropy［J］.Open Systems ＆ Information Dynamics，2003，10(3):297-310.

［9］Renyi A.On measures of entropy and information［C］//Fourth Berkeley Symposium on Mathematical Statistics and Probability.1961:547-561.

［10］Cranshaw J，Toch E，Hong J，et al.Bridging the gap between physical location and online social networks［C］//Proceedings of the 12th ACM International Conference on Ubiquitous Computing.2010:119-128.

［11］Adamic L A，Adar E.Friends and neighbors on the web［J］.Social Networks，2003，25(3):211-230.

［12］Liben Nowell D，Kleinberg J.The link-prediction problem for social networks［J］.Journal of the American Society for Information Science and Technology，2007，58(7):1019-1031.

［13］余學(xué)軍.六度分割理論成就SNS［J］.信息網(wǎng)絡(luò)，2009(11):37-37.

［14］Wu H，Sorathia V，Prasanna V K.When diversity meets speciality:Friend recommendation in online social networks［J］.Human，2013，1(1):52-60.

［15］Lam C.Hadoop in Action［M］.Manning Publications Co.，2010.

［16］Miner D，Shook A.MapReduce Design Patterns:Building Effective Algorithms and Analytics for Hadoop and Other Systems［M］.O’Reilly Media，Inc.，2012.

［17］Bishop C M.Pattern Recognition and Machine Learning［M］.New York:Springer，2006.