吳 錚，于洪濤，劉樹新，朱宇航

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002)

(*通信作者電子郵箱wzxuexizhuanyong@163.com)

基于信息熵的跨社交網(wǎng)絡(luò)用戶身份識別方法

吳 錚*，于洪濤，劉樹新，朱宇航

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002)

(*通信作者電子郵箱wzxuexizhuanyong@163.com)

針對主觀分配屬性項(xiàng)權(quán)重的方法忽視了各屬性項(xiàng)在身份匹配的應(yīng)用領(lǐng)域中具有的特殊含義與作用，導(dǎo)致識別準(zhǔn)確率低的問題，提出了一種基于信息熵的跨網(wǎng)絡(luò)用戶身份識別算法(IE-MSNUIA)。首先，該算法分析不同屬性項(xiàng)的數(shù)據(jù)類型及物理含義，相應(yīng)地采用不同的相似度計算方法；然后根據(jù)各屬性的信息熵值賦予權(quán)值，進(jìn)而充分挖掘各屬性的潛在信息；最后融合各個屬性進(jìn)行決策判定賬號是否匹配。理論分析和實(shí)驗(yàn)結(jié)果表明，與機(jī)器學(xué)習(xí)算法和主觀賦權(quán)算法相比，所提算法的各個性能參數(shù)值均有所提升，在不同數(shù)據(jù)集上的平均準(zhǔn)確率可以達(dá)到97.2%,平均召回率達(dá)到94.1%，平均綜合性能值達(dá)到95.6%，可以準(zhǔn)確地識別出用戶在不同社交網(wǎng)絡(luò)中的多個賬號身份。

用戶身份識別；屬性相似度；信息熵；信息融合；在線社交網(wǎng)絡(luò)

0 引言

隨著互聯(lián)網(wǎng)時代的到來，以及社交網(wǎng)絡(luò)的迅速普及與廣泛應(yīng)用，人們的生活方式發(fā)生了深刻的改變。越來越多的人習(xí)慣每天通過微信、QQ等社交工具與家人、好友、同事進(jìn)行即時通信，在微博、朋友圈發(fā)布信息，在頭條、騰訊上閱讀新聞并進(jìn)行評論。一個人往往在多個社交網(wǎng)絡(luò)中注冊賬號，進(jìn)行不同的社交活動，留下了豐富的用戶社交元數(shù)據(jù)信息。然而，目前由于“單點(diǎn)登錄”技術(shù)還不夠完善，同一個用戶在不同社交網(wǎng)絡(luò)中注冊的多個賬號之間往往是孤立開來的。如果可以跨網(wǎng)絡(luò)識別用戶，即識別出同一個用戶在不同網(wǎng)絡(luò)中的多個賬號，就可以實(shí)現(xiàn)數(shù)據(jù)的融合，最大限度地收集、整合與完善用戶的個人信息，從而能夠?qū)τ脩艉Ａ可缃辉獢?shù)據(jù)進(jìn)行充分挖掘。

跨網(wǎng)絡(luò)用戶識別技術(shù)在商業(yè)應(yīng)用、信息檢索、網(wǎng)絡(luò)空間安全等許多領(lǐng)域都具有重大的研究意義與實(shí)用價值[1]。按照用戶在社交網(wǎng)絡(luò)中擁有的三種維度的信息，目前跨網(wǎng)路用戶識別技術(shù)大多可以分為三類：基于網(wǎng)絡(luò)結(jié)構(gòu)信息[2-4]、基于屬性信息[5-10]以及基于行為信息[11-14]的用戶身份識別方法。當(dāng)用戶的屬性信息可以被利用時，該方法的準(zhǔn)確率高于其他兩類。目前基于屬性信息的用戶身份識別方法主要是判斷不同網(wǎng)絡(luò)中兩個賬號的檔案信息是否匹配，用戶檔案信息通常包括用戶名、地址、興趣等多個屬性，把賬號檔案所有屬性項(xiàng)映射到一種多維特征的分向量，向量中的每一維度的值是不同網(wǎng)絡(luò)中的兩個賬號在各個屬性信息上的相似度，通過給不同屬性設(shè)定權(quán)重融合多個屬性的相似度，最終計算得出檔案相似度，再與預(yù)定閾值相比較，判定是否屬于同一用戶。相關(guān)的研究成果有很多，如Vosecky等[5]首次提出將用戶的檔案信息表示為由多個屬性字段組成的n維向量，各個用戶的相似度用向量相似性計算方法來計算，它的缺點(diǎn)是屬性與領(lǐng)域是緊耦合的，每次個性化應(yīng)用的改變都需要權(quán)重的重新計算。Raad等[6]將用戶的配置信息轉(zhuǎn)移到FOAF(Friend-Of-A-Friend)詞匯表，利用判定算法計算兩個賬號的相似度，該方法的問題在于識別時使用電子郵件地址作為用戶唯一標(biāo)識符，而該私人信息能被其他人獲取，所以算法的應(yīng)用受限。Motoyama等[7]收集了Facebook和Myspace中用戶賬號的學(xué)歷程度、職業(yè)等檔案信息，把它們作為單詞集合，通過比較單詞的相似度來衡量賬號的相似度。Zamani等[8]綜合考慮不同社交網(wǎng)絡(luò)中用戶賬號的單位、地址、專業(yè)興趣以及過往經(jīng)歷等信息，并使用了從簡單的均等評價模型到復(fù)雜的訓(xùn)練混合模型等一系列方法來融合多個檔案信息屬性的相似度，通過實(shí)驗(yàn)驗(yàn)證了準(zhǔn)確識別用戶身份的可能性。Ye等[9]提出一種社交網(wǎng)絡(luò)中主觀導(dǎo)向的客觀賦權(quán)方法用于合成屬性信息，計算用戶檔案相似度。Esfandyari等[10]則提出了一種新的訓(xùn)練集中反面案例選擇方法，相比傳統(tǒng)的隨機(jī)選擇法，提出基于重疊屬性項(xiàng)的選擇方法使得訓(xùn)練出來的模型魯棒性更強(qiáng)。

目前基于賬號屬性信息的跨網(wǎng)絡(luò)用戶身份識別方法主要將不同屬性的值都看作字符串，通過計算字符串相似度刻畫屬性相似度。該類處理方法具有計算簡單、適用于大規(guī)模數(shù)據(jù)集的特點(diǎn)。此外該方法在融合多個屬性信息時，多采用主觀導(dǎo)向的客觀修正法，即專家根據(jù)各屬性的重要程度主觀確定權(quán)重系數(shù)，然后根據(jù)結(jié)果反饋進(jìn)行權(quán)重修正，提高識別準(zhǔn)確率。上述方法雖然取得了一定的效果，但是仍然存在以下問題：1)將屬性信息統(tǒng)一按照字符串進(jìn)行處理，忽略了某些屬性的特殊性，在相似度刻畫中存在缺陷，造成匹配結(jié)果精度受限；2)主觀賦權(quán)導(dǎo)向的客觀修正法是基于特定網(wǎng)絡(luò)訓(xùn)練出來的，推廣到其他網(wǎng)絡(luò)中時模型的合理性受到質(zhì)疑，面對新的網(wǎng)絡(luò)時需要訓(xùn)練新的模型，會增加復(fù)雜度。

針對上述問題，本文基于用戶檔案中多個屬性信息的身份識別問題進(jìn)行建模與分析，對不同類型的屬性制定了適用于賬號匹配領(lǐng)域的科學(xué)合理的相似度計算方法，并綜合考慮了各屬性項(xiàng)所含信息量與對賬號匹配的貢獻(xiàn)程度，提出了一種可以適應(yīng)不同網(wǎng)絡(luò)環(huán)境、魯棒性強(qiáng)的基于信息熵的權(quán)重賦予方法，通過判定算法計算兩個檔案的相似度，識別出同一用戶在多個網(wǎng)絡(luò)中的賬號身份，從而進(jìn)一步融合多個社交網(wǎng)絡(luò)中的用戶身份信息，為社交網(wǎng)絡(luò)的數(shù)據(jù)挖掘與分析打下堅(jiān)實(shí)基礎(chǔ)。本文通過在爬取到的社交網(wǎng)絡(luò)用戶信息真實(shí)數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)，驗(yàn)證了所提算法的有效性。

1 相關(guān)工作

1.1 用戶屬性建模

本文利用賬號檔案中的多個屬性信息構(gòu)成一個多維特征向量，用來表征用戶在特定網(wǎng)絡(luò)中的身份。

可以被識別的用戶是指在目標(biāo)網(wǎng)絡(luò)中可以找到一個賬號Fd與源網(wǎng)絡(luò)中的賬號Fs相匹配。選取不同網(wǎng)絡(luò)中賬號的用戶身份向量，通過計算兩個向量中各個屬性項(xiàng)的相似度，構(gòu)建賬號相似度向量。

SimFunc()函數(shù)用來計算各個屬性項(xiàng)的相似度，如果兩個屬性項(xiàng)完全一致，則SimFunc()函數(shù)返回值為1；如果兩個屬性信息完全不同，則SimFunc()函數(shù)返回值為0。不同的屬性信息，用來計算相似度的SimFunc()函數(shù)形式也會不同。

1.2 字符串相似度計算方法

大多數(shù)的屬性項(xiàng)都存儲為字符串類型，因此利用計算字符串序列之間相似程度就可以獲取該屬性項(xiàng)的相似度。字符串相似度的計算已經(jīng)建立了成熟的理論和模型，并且已經(jīng)被廣泛應(yīng)用，其中來自統(tǒng)計學(xué)、數(shù)據(jù)庫、人工智能領(lǐng)域的學(xué)者都從自身的研究領(lǐng)域出發(fā)，提出了不同的相似度計算方法。常見的字符串距離公式有：

1)Levenshtein距離。Levenshtein距離dlev又叫作編輯距離，它是通過計算使兩個字符串相等所需的單個字符編輯(增加、刪除、替換)步數(shù)，以此作為操作代價衡量兩個字符串的差異性。字符串li和lj的Levenshtein相似度計算方法如式(1)：

(1)

其中|li|和|lj|表示字符串中字符的個數(shù)。

2)Jaro距離。Jaro距離是基于公共字符的個數(shù)與順序的方法，最初是用在人口普查中判定健康記錄中兩個名字是否相同，因此非常適用于用戶名的匹配。字符串li和lj的Jaro距離計算方法如式(2)：

(2)

其中：|li|和|lj|是每個字符串的長度，m是公共字符的個數(shù)，t是換位的個數(shù)。字符串li和lj的Jaro相似度計算方法如式(3)：

(3)

3)Dice系數(shù)。對于多值屬性字符串，Dice系數(shù)的計算方式是兩個字符串ni和nj的交集信息的2倍除以ni和nj的元素總和，如式(4)：

(4)

例如對于兩個多值屬性字符串“sports music movie”和“music reading traveling”，交集信息為{“music”},所以相似度為2/6≈0.33。

對于單值屬性字符串，Dice系數(shù)的計算方式是兩個字符串li和lj的交集信息的2倍除以li和lj的長度總和，如式(5)：

(5)

其中當(dāng)定義好字符組包含的字符個數(shù)為N時，交集信息|li∩lj|是指兩個字符串相同的字符組個數(shù)。例如當(dāng)定義N=2時，對于兩個字符串“Jon”和“Jone”，“Jon”的字符組是{“Jo”，“on”},“Jone”的字符組是{“Jo”，“on”,“ne”},交集信息為{“Jo”，“on”}，所以相似度為2×2/5=0.8。

4)MN(Matching Name)距離。MN用戶名匹配算法[5]包括兩個步驟：先是預(yù)處理，將用戶名中含有的特殊字符或表情刪除；然后將精確匹配與部分匹配結(jié)合，得到最終的匹配結(jié)果值。

1.3 圖像數(shù)據(jù)相似度計算方法

圖像類數(shù)據(jù)相似性的計算方法較為復(fù)雜，主要是因?yàn)椴煌W(wǎng)絡(luò)中頭像圖片的格式、類型可能不同，而且拍攝時角度的不同也會帶來圖像的差異。

針對各種圖像變形的問題，采用兩種技術(shù)聯(lián)合計算圖像相似度，因?yàn)楦兄Ｋ惴?Perceptual Hash Algorithm，PHA)[15]不擅長處理圖像角度變換的情況，而尺度不變特征變換(Scale-Invariant Feature Transform, SIFT)算法[16]不擅長處理計算機(jī)生成的圖片，兩者結(jié)合互補(bǔ)可以使相似度算法具有更好的魯棒性。

1.4 地理位置之間距離計算方法

li和lj分別表示賬號i和賬號j的地理位置，地點(diǎn)li的經(jīng)緯度坐標(biāo)為(lati,loni)，地點(diǎn)lj的經(jīng)緯度坐標(biāo)為(latj,lonj)，兩個全球定位系統(tǒng)(Global Positioning System, GPS)坐標(biāo)之間的距離采用大圓距離的計算方法計算[17]，大圓距離指的是從地球的一點(diǎn)出發(fā)到達(dá)球面上另外一點(diǎn)所經(jīng)過的最短路徑長度，計算方法如式(6)所示，

(6)

其中：R為地球半徑(6 371 km),d(li,lj)的單位為km。

2 基于信息熵的用戶身份識別算法

2.1 身份識別問題建模

用戶是現(xiàn)實(shí)生活中的真實(shí)個體，賬號表示該人在虛擬網(wǎng)絡(luò)中的身份。每個用戶在社交網(wǎng)絡(luò)中存在兩種身份標(biāo)識：一種是特定社交網(wǎng)絡(luò)中唯一辨識用戶身份的ID號；另一種是可以跨網(wǎng)絡(luò)識別用戶的身份標(biāo)識。前者由社交網(wǎng)站進(jìn)行管理，而后者實(shí)際上并不存在，通過某種技術(shù)手段將同一人在不同社交網(wǎng)絡(luò)中的多個ID號連接起來，可以識別出用戶的多個賬號身份，從而全面融合用戶信息，實(shí)現(xiàn)相關(guān)的數(shù)據(jù)挖掘與應(yīng)用。

2.2 屬性相似度計算

目前屬性信息相似度的測量方法很多，只有針對不同的類型和領(lǐng)域信息選擇不同的比較方法，才最能真實(shí)地反映相似程度，取得最佳的匹配準(zhǔn)確率與效率。本文選擇用戶的用戶名、自我描述、興趣愛好、網(wǎng)頁鏈接、地理位置、頭像共6類屬性信息作為賬號相似度的衡量基準(zhǔn)。按照屬性項(xiàng)的數(shù)值所屬的不同數(shù)據(jù)類別，可以分為三類：字符串類型、圖像類型以及數(shù)字類型。其中屬于字符串類型的有用戶名、自我描述、興趣愛好和網(wǎng)頁鏈接，屬于圖像類型的是用戶頭像，屬于數(shù)字類型的是地理位置，各自的相似度計算方法如下。

1)用戶名。用戶名是最容易獲得的屬性信息，通常也包含在用戶檔案主頁統(tǒng)一資源定位符(Uniform Resoure Locator, URL)中。相關(guān)研究表明，用戶在不同網(wǎng)絡(luò)中注冊賬號時，傾向于在一個用戶名的基礎(chǔ)上做一些微小的變化，例如在原有用戶名中插入特殊符號、簡寫部分字符串、改寫部分字符、交換部分字符串、添加具有特殊含義的字符串等,從而衍生出多個相似的用戶名。如原有用戶名為“Alfred Gin”,則用戶可能會在其他網(wǎng)站中注冊賬號為“**Alfred Gin**”“A Gin”“Alfr@d Gin”“Twitter Alfred”“Alfred Gin Twitter”等。根據(jù)文獻(xiàn)[5]的研究表明，與其他算法相比，MN算法計算的用戶名相似度更加客觀真實(shí)、合乎邏輯，所以本文采用MN算法計算用戶名相似度。

2)自我描述。自我描述是一段類似于自我介紹的話，告訴他人自己的興趣、特長、觀點(diǎn)、理念等，向他人“推銷”自己，從而吸引志同道合的人添加好友關(guān)系。自我描述通常是一段字符串，利用詞頻-逆文檔頻率(Term Frequency-Inverse Document Frequency, TF-IDF)構(gòu)建關(guān)鍵詞向量，通過計算向量的余弦相似度作為不同網(wǎng)絡(luò)中自我描述的相似度。

3)興趣愛好。用戶在社交網(wǎng)站中會關(guān)注自己所感興趣的話題，加入特定主題的群組，以及經(jīng)常閱讀、分享自己喜歡的文章等，從這些行為中都可以抽取出用戶的興趣愛好。以所有描述用戶興趣主題的詞構(gòu)建“興趣標(biāo)簽詞袋”，每個賬號依據(jù)各自的興趣從“興趣標(biāo)簽詞袋”中抽取出部分詞標(biāo)簽集，利用Dice算法計算多詞屬性相似度，作為不同網(wǎng)絡(luò)中興趣愛好相似度。

4)網(wǎng)頁鏈接。網(wǎng)頁鏈接是該用戶其他網(wǎng)絡(luò)中賬號主頁的URL，它可以唯一標(biāo)識用戶的身份，本文選取的策略為當(dāng)兩個賬號的網(wǎng)頁鏈接相同則網(wǎng)頁鏈接相似度為1，否則為0。

5)地理位置。地址信息是社交網(wǎng)站中常見的屬性信息，由于不同網(wǎng)絡(luò)中地址信息書寫格式不同，若采用字符串匹配則會帶來誤判，而且依據(jù)字符串比較不同地理名稱的相似性沒有實(shí)際意義，所以通過百度地圖應(yīng)用程序編程接口(Application Programming Interface, API)將地理名稱轉(zhuǎn)化為相應(yīng)的經(jīng)緯度坐標(biāo)，利用式(6)計算兩地之間的距離，從而判斷地理位置是否相同。

6)頭像。本文選取的屬性中，用戶頭像屬于圖像類數(shù)據(jù)。主要采用兩種方法計算頭像圖片的相似度：一是PHA技術(shù)，該技術(shù)通過比較圖片的“指紋”來判斷兩幅圖片是否相似；另一個是SIFT技術(shù)，該技術(shù)通過匹配檢測出的局部特征來比較兩幅圖片的相似度。

上述的屬性信息中，利用網(wǎng)頁鏈接、地理位置和頭像進(jìn)行身份識別時，由于其現(xiàn)實(shí)意義的特殊性，衡量這些屬性的相似度應(yīng)當(dāng)具有“斷層”性質(zhì)，即大于“斷層式”閾值則認(rèn)定為相同，相似度為1，否則不相同，相似度為0，其余的相似度值對于身份匹配應(yīng)用而言沒有意義。所以本文對于這些屬性的利用，在傳統(tǒng)的相似度計算基礎(chǔ)上，設(shè)置了二值判定，從而使得匹配結(jié)果更加科學(xué)合理。

2.3 信息熵確定屬性權(quán)重

在確定檔案信息中各項(xiàng)屬性對于相似度決策判定的權(quán)重系數(shù)時，傳統(tǒng)的專家主觀賦權(quán)法是與屬性領(lǐng)域緊耦合的，算法魯棒性較差，而客觀賦權(quán)法依賴于足夠的樣本數(shù)據(jù)，通用性和參與性差。

為解決以上問題，本文提出了基于信息熵的賦權(quán)方法。熵權(quán)法的基本思想是認(rèn)為指標(biāo)的差異程度越大越重要,則權(quán)重相應(yīng)也越大。計算時,如何實(shí)現(xiàn)各指標(biāo)間熵值與熵權(quán)的轉(zhuǎn)換是關(guān)鍵環(huán)節(jié),其直接影響著各指標(biāo)客觀權(quán)重的正確性,進(jìn)而關(guān)系著方案評價的合理性、可靠性。在信息論中,熵值反映了信息無序化程度：其值越小,系統(tǒng)越有序,攜帶的信息越多；其值越大，系統(tǒng)越混亂，攜帶的信息越少。故可用信息熵評價所獲系統(tǒng)信息的有序度及其效用,即由評價指標(biāo)值構(gòu)成的判斷矩陣來確定指標(biāo)權(quán)重,消除各指標(biāo)權(quán)重計算的人為干擾,使評價結(jié)果更符合實(shí)際。

依據(jù)信息熵的定義，當(dāng)系統(tǒng)可能處于多種不同的狀態(tài)，每種狀態(tài)j出現(xiàn)的概率為pij(j=1,2,…,n)時，系統(tǒng)的熵為：

(7)

其中Ei表示第i個事件。

本文根據(jù)用戶各屬性的相似度確定其權(quán)重，匹配賬號的相似度與不匹配賬號的相似度差別越大，信息越有序，熵值越小，該屬性攜帶的信息越多，該屬性越有價值，對用戶識別的判斷就越準(zhǔn)確，所以熵權(quán)應(yīng)該越大；匹配賬號的相似度與不匹配賬號的相似度差別越小，信息越無序，熵值越大，該屬性攜帶的信息越少，該屬性價值越低，對用戶識別的判斷就越模糊，所以熵權(quán)應(yīng)該越小?；谝陨戏治?，對式(7)中的pij定義為屬性相似度出現(xiàn)的概率，如式(8)：

(8)

(9)

(10)

(11)

2.4 用戶賬號匹配

根據(jù)相似度向量的定義，則衡量兩個賬號相似度的計算方法如式(12)所示：

(12)

算法1 檔案相似度計算方法。

輸出Fs和Fd兩個賬號的相似度Similarity(Fs,Fd)。

2) fori=1 ton

4) end

構(gòu)建賬號相似度向量

6) end

7) fori=1 ton

8) 利用式(8)計算屬性i相似度出現(xiàn)的概率pij

12) end

13) 利用式(12)計算Fs和Fd兩個賬號的相似度Similarity(Fs,Fd)

14) returnSimilarity(Fs,Fd)

通過比較不同賬號對之間的相似度值的大小，確定最佳匹配賬號對。

2.5 身份識別過程

基于屬性信息的跨網(wǎng)絡(luò)用戶身份識別過程包括三個步驟：賬號選擇、賬號匹配、剪枝過濾。

1)賬號選擇。

在對一個網(wǎng)絡(luò)中的源賬號Fs進(jìn)行用戶識別時，如果每次都是從另一個網(wǎng)絡(luò)中選取所有的目標(biāo)賬號Fd進(jìn)行關(guān)于檔案信息中所有屬性的相似度計算，則計算量會非常大，尤其是當(dāng)網(wǎng)絡(luò)中注冊賬號的規(guī)模十分龐大時，逐一比較更是不現(xiàn)實(shí)、不可行的。因此在選取目標(biāo)賬號Fd與源賬號Fs進(jìn)行相似度計算時，有必要根據(jù)條件C對另一網(wǎng)絡(luò)中的目標(biāo)賬號進(jìn)行篩選，采用單個較為簡單的屬性作為篩選器，從全集中過濾出與源賬號Fs有較高匹配概率的候選賬號集合，從而降低計算量。

通過對人們生活習(xí)慣的觀察與分析，用戶在不同網(wǎng)絡(luò)中傾向于使用相似的用戶名，又因?yàn)橛脩裘南嗨贫扔嬎阍谒袑傩灾惺亲詈唵蔚?，所以本文使用用戶名作為篩選器，選擇一個合適的閾值來平衡候選集規(guī)模與覆蓋率之間的關(guān)系，求得一個折中值。

2)賬號匹配。

通過賬號選擇步驟，選出了滿足條件C的與源賬號Fs有可能匹配的候選賬號集合，然后依次對集合中的候選賬號與源賬號Fs進(jìn)行基于屬性信息的相似度計算，選出其中與源賬號Fs相似度最高的候選賬號Fd作為待匹配賬號，然后與預(yù)先設(shè)定閾值(通常情況下選取閾值為0.5)，如果大于閾值則判定為匹配，反之不匹配。

3)剪枝過濾。

得到最終匹配結(jié)果后，為了確保精確度，有時需要剪枝過濾的過程去除一些錯誤的匹配。本文對兩個網(wǎng)絡(luò)G1和G2中的賬號進(jìn)行識別時，以網(wǎng)絡(luò)G1中的賬號Fs作為源賬號在網(wǎng)絡(luò)G2中尋找匹配的目標(biāo)賬號Fd后，再以網(wǎng)絡(luò)G2中的Fd作為源賬號在網(wǎng)絡(luò)G1中尋找匹配的目標(biāo)賬號，如果匹配的是Fs，則保留該對匹配賬號，否則舍棄該對賬號。

算法2 基于信息熵的跨網(wǎng)絡(luò)用戶身份識別算法(Information Entropy based Multiple Social Networks User Identification Algorithm, IE-MSNUIA)。

輸出 與Fs匹配的賬號Fd。

4)c++

6) end

7)max=0

9) 利用算法1計算檔案相似度Similarity(Fs,CFj)

10) ifSimilarity(Fs,CFj)>max

11)max=Similarity(Fs,CFj)，d=j

12) end

13) ifmax≥Tp

14) returnFd

15) else return null

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

3.1 數(shù)據(jù)集的獲取與設(shè)置

在一些社交網(wǎng)絡(luò)中，用戶在填寫自己的檔案信息時，往往喜歡添加進(jìn)自己在其他網(wǎng)絡(luò)中的個人主頁鏈接，意在邀請他人與自己在其他網(wǎng)絡(luò)中也建立起好友關(guān)系，這一行為給驗(yàn)證個人多個賬號身份提供了可行性。Google+就是此類型的社交網(wǎng)站，該網(wǎng)站上的用戶檔案中有一項(xiàng)屬性是“鏈接”，用戶可以在此張貼自己在其他社交網(wǎng)站上的個人主頁鏈接。為了驗(yàn)證所提算法的有效性，本文選取從Google+、Facebook和Twitter這三個社交網(wǎng)絡(luò)中收集的賬號屬性信息進(jìn)行用戶身份識別的相關(guān)實(shí)驗(yàn)。文獻(xiàn)[18]提供了一份包含5個社交網(wǎng)絡(luò)賬號主頁鏈接的公開數(shù)據(jù)集，本文以Google+作為收集用戶屬性信息的源網(wǎng)站，過濾選取其中給出Facebook和Twitter主頁鏈接非空、網(wǎng)頁未失效且公開檔案信息訪問權(quán)限的Google+賬號，最終得到Google+賬號5 916個，F(xiàn)acebook賬號4 377個，Twitter賬號5 829個。用戶屬性信息獲取流程如下：首先從中抽取出用戶主頁鏈接地址URL，然后借助第三方網(wǎng)站查詢出對應(yīng)的用戶賬號ID，再通過官方提供的API接口爬取檔案信息數(shù)據(jù)，最后將數(shù)據(jù)存入數(shù)據(jù)庫以供實(shí)驗(yàn)使用。

不同的社交網(wǎng)絡(luò)中用戶檔案信息的屬性項(xiàng)個數(shù)與內(nèi)容并非完全相同，而且同一個用戶在不同網(wǎng)絡(luò)中填寫的情況也有差異。網(wǎng)絡(luò)中經(jīng)常出現(xiàn)用戶屬性項(xiàng)缺失的情況，屬性項(xiàng)缺失通常是用戶漏填或者設(shè)定隱私保護(hù)造成的，所以爬取到的檔案數(shù)據(jù)并不能直接使用，需要對待匹配的兩個網(wǎng)絡(luò)中的公共屬性項(xiàng)進(jìn)行篩選與語意匹配。通過綜合分析，本文最終確定在匹配Google+、Facebook和Twitter網(wǎng)絡(luò)中賬號時，選取三個網(wǎng)絡(luò)中都具備的、通過API可以獲取到且用戶填寫較為齊全的6種屬性項(xiàng)：用戶名(username)、自我描述(biography)、興趣愛好(interests)、網(wǎng)頁鏈接(URL)、地理位置(location)、頭像(avatar)。對于這6項(xiàng)屬性信息中依然存在的缺失數(shù)據(jù)以及明顯不符屬性內(nèi)容的噪聲數(shù)據(jù)，采用該項(xiàng)屬性所有用戶的平均值進(jìn)行補(bǔ)充或者替換。

3.2 評價指標(biāo)

使用 IE-MSNUIA可以判斷兩個賬號是否匹配，如果賬號的檔案信息相似度大于一定的閾值，則判定為匹配，即兩個賬號對應(yīng)于現(xiàn)實(shí)生活中的同一個用戶，反之則判定為不匹配。本文采用準(zhǔn)確率(precision)、召回率(recall)以及綜合評價指標(biāo)F1作為衡量算法性能的評價標(biāo)準(zhǔn)。具體定義如下，

precision=tp/(tp+fp)

(13)

recall=tp/(tp+fn)

(14)

F1=2×precision×recall/(precision+recall)

(15)

準(zhǔn)確率(precision)是指正確匹配的比率，其中tp表示被算法匹配上并且對應(yīng)于同一用戶的賬號對數(shù),fp表示被算法匹配上但是對應(yīng)于不同用戶的賬號對數(shù)；召回率(recall)是指正確識別的比率，其中fn表示未被算法匹配上的對應(yīng)于同一用戶的賬號對數(shù)；F1是前兩者的調(diào)和平均數(shù)，是算法性能的綜合評價指標(biāo)。

3.3 實(shí)驗(yàn)結(jié)果

3.3.1 單屬性匹配性能分析

在實(shí)驗(yàn)中，首先測試了各個單項(xiàng)屬性在賬號匹配中的性能，實(shí)驗(yàn)結(jié)果如圖1所示。其中本文設(shè)置二值屬性網(wǎng)頁鏈接和頭像各自的“斷層式”閾值為1和0.9；對于地理位置屬性，本文將范圍控制在市級單位，即兩地相距在80 km以內(nèi)則認(rèn)為地理位置相似度為1，否則為0。利用屬性項(xiàng)用戶名、網(wǎng)頁鏈接和頭像在匹配時，同一用戶與不同用戶的相似度分布集中且差別較大，該項(xiàng)屬性在匹配時具有較強(qiáng)的區(qū)分性，所以權(quán)重應(yīng)當(dāng)較大。屬性項(xiàng)自我描述和興趣愛好在匹配時，同一用戶與不同用戶的相似度分布離散且差別較小；屬性項(xiàng)地理位置在匹配時，同一用戶與不同用戶的相似度有交錯現(xiàn)象，這些屬性項(xiàng)匹配時的分辨力較弱，所以權(quán)重應(yīng)當(dāng)較小。

圖1 賬號各屬性的相似度分布Fig. 1 Similarity distributions of account attributes

用信息熵確定權(quán)重時，對于確定了目標(biāo)網(wǎng)絡(luò)以后，每個源網(wǎng)絡(luò)中待匹配賬號Fs都有屬于自己的一個權(quán)重分配方案。實(shí)驗(yàn)選擇在Google+和Facebook、Google+和Twitter以及Facebook和Twitter這3組網(wǎng)絡(luò)中進(jìn)行賬號匹配，圖2是在這3組網(wǎng)絡(luò)中賬號權(quán)重分配的分布圖，從分布來看，用戶名和網(wǎng)頁鏈接的權(quán)重都較大，而另外四項(xiàng)屬性的權(quán)重都較小，這與上面的分析結(jié)果是一致的，驗(yàn)證了信息熵權(quán)的客觀性與合理性。

圖2 賬號各屬性的權(quán)重分布Fig. 2 Weight distributions of account attributes

3.3.2 身份識別算法性能分析

本實(shí)驗(yàn)選擇的對比算法包括支持向量機(jī)(Support Vector Machine, SVM)算法和隨機(jī)森林(Random Forest，RF)法兩種有監(jiān)督的機(jī)器學(xué)習(xí)算法以及Vosecky等[5]、Ye等[9]和Esfandyari等[10]提出的基于主觀賦權(quán)的算法。機(jī)器學(xué)習(xí)算法相當(dāng)于把身份識別看作賬號“匹配”與“不匹配”的二分類問題，將各屬性項(xiàng)的相似度看作輸入的特征數(shù)據(jù)，把匹配與否作為輸出的判別類型，模型訓(xùn)練時正負(fù)兩類樣本比例設(shè)為1∶1，訓(xùn)練集和測試集的比例設(shè)置為3∶1。Vosecky等[5]根據(jù)不同屬性項(xiàng)的字符串特點(diǎn)，對不同的屬性項(xiàng)采取精確匹配、部分匹配和模糊匹配三種不同的方法計算字符串相似度，利用主觀經(jīng)驗(yàn)初始化各屬性項(xiàng)的權(quán)重，然后再用控制變量法，以準(zhǔn)確率為目標(biāo)對各權(quán)重進(jìn)行修正。Ye等[9]則是將屬性分為決定性屬性和非決定性屬性兩種，賦權(quán)方法采用的是主觀導(dǎo)向的客觀賦權(quán)法，即首先依據(jù)專家經(jīng)驗(yàn)賦權(quán)，然后依據(jù)相似度對其進(jìn)行反向客觀修正。Esfandyari等[10]在權(quán)重選擇上參照了Vosecky等[5]的方法，但是在訓(xùn)練集的選取上有所變化，同時選擇正確匹配和錯誤匹配的數(shù)據(jù)訓(xùn)練模型，從而使得算法魯棒性更好。實(shí)驗(yàn)在三組數(shù)據(jù)集(Google+&Facebook、Google+&Twitter、Facebook&Twitter)上進(jìn)行測試，其中機(jī)器學(xué)習(xí)算法采用10折交叉驗(yàn)證的方法求得最終結(jié)果。圖3顯示了不同算法在不同數(shù)據(jù)集上的性能參數(shù)對比情況，并且為了表述方便，橫軸的算法A～F分別代表SVM算法、RF法、Vosecky等[5]的方法、Ye等[9]的方法、Esfandyari等[10]的方法和本文的IE-MSNUIA。

實(shí)驗(yàn)結(jié)果顯示，本文算法優(yōu)于對比算法，在不同的數(shù)據(jù)集上均具有最好的性能。具體分析其原因在于，機(jī)器學(xué)習(xí)算法具有較好的身份識別效果，而且在可用屬性信息充足的條件下采用不同機(jī)器學(xué)習(xí)算法進(jìn)行身份匹配時，匹配效果的變化并不大；然而由于機(jī)器學(xué)習(xí)算法本身存在的缺點(diǎn)，例如SVM算法對缺失數(shù)據(jù)敏感的問題，以及隨機(jī)森林法在處理取值劃分較多的屬性時權(quán)重不可信的問題，導(dǎo)致性能受限。此外，機(jī)器學(xué)習(xí)算法性能依賴于訓(xùn)練集數(shù)據(jù)組成的問題也限制了其應(yīng)用的廣度。

相比較而言，另外三種基于主觀賦權(quán)修正的對比算法，由于直接對屬性賦權(quán)，相比分類器算法，省去了模型訓(xùn)練的過程，所以較為簡單高效；此外還加入了對權(quán)值的修正過程，性能也較分類器算法有一定程度的提升。

本文的IE-MSNUIA綜合考慮了不同屬性項(xiàng)信息自身的數(shù)據(jù)特點(diǎn)與現(xiàn)實(shí)含義，并沒有像三種基于主觀賦權(quán)修正的對比算法那樣將屬性統(tǒng)一按照字符串進(jìn)行處理，而是制定了更科學(xué)合理的相似度計算方法，從而實(shí)驗(yàn)結(jié)果更加精確；另一方面，基于信息熵的賦權(quán)方法綜合考慮了各屬性項(xiàng)所含信息量與對賬號匹配的貢獻(xiàn)程度，所以各個屬性項(xiàng)權(quán)重的可信度更高。從實(shí)驗(yàn)結(jié)果可以看出，本文算法的平均準(zhǔn)確率可以達(dá)到97.2%，平均召回率可以達(dá)到94.1%，平均F1值可以達(dá)到95.6%，驗(yàn)證了其有效性。

圖3 各算法性能參數(shù)對比Fig. 3 Comparison of the performance parameters of different algorithms

4 結(jié)語

本文提出了一種基于屬性信息的跨網(wǎng)路身份識別算法，通過利用不同社交網(wǎng)絡(luò)開放的API接口可以爬取得到的公共用戶屬性信息，構(gòu)建待匹配賬號相似度向量，并依據(jù)信息熵的思想對不同屬性賦予不同權(quán)重，計算賬號檔案信息的整體相似度進(jìn)行賬號匹配，實(shí)現(xiàn)了在Google+、Facebook和Twitter三個網(wǎng)絡(luò)之間的跨網(wǎng)絡(luò)用戶識別?，F(xiàn)有的基于屬性信息進(jìn)行身份識別的方法在計算不同類型屬性項(xiàng)相似度時統(tǒng)一按照字符串進(jìn)行處理，而本文則通過分析屬性不同的數(shù)據(jù)類型特征采用不同的相似度衡量策略，實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的有效性與合理性。由于本文算法對每個待識別源賬號都需要計算一套屬性權(quán)值分配方案，當(dāng)社交網(wǎng)絡(luò)中待匹配的賬號規(guī)模變大時，屬性項(xiàng)權(quán)值計算量也會變大，所以下一步的工作將著眼于如何進(jìn)一步地改進(jìn)權(quán)值計算方法，降低算法的計算開銷。

References)

[1] 劉東,吳泉源,韓偉紅,等.基于用戶名特征的用戶身份同一性判定方法[J].計算機(jī)學(xué)報,2015,38(10):2028-2040. (LIU D, WU Q Y, HAN W H, et al. User identification across multiple websites based on username features[J]. Chinese Journal of Computers, 2015, 38(10): 2028-2040.)

[2] NARAYANAN A, SHMATIKOV V. De-anonymizing social networks [C]// SP ’09： Proceedings of the 2009 30th IEEE Symposium on Security and Privacy. Washington, DC: IEEE Computer Society, 2009: 173-187.

[3] KONG X, ZHANG J, YU P S. Inferring anchor links across multiple heterogeneous social networks [C]// CIKM ’13: Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. New York: ACM, 2013: 179-188.

[4] TAN S, GUAN Z, CAI D, et al. Mapping users across networks by manifold alignment on hypergraph [C]// AAAI 2014: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. Menlo Park, CA: AAAI Press, 2014: 159-165.

[5] VOSECKY J, HONG D, SHEN V Y. User identification across multiple social networks [C]// NDT ’09: Proceedings of the 2009 First International Conference on Networked Digital Technologies. Piscataway, NJ: IEEE, 2009: 360-365.

[6] RAAD E, CHBEIR R, DIPANDA A. User profile matching in social networks [C]// NBIS ’10: Proceedings of the 2010 13th International Conference on Network-Based Information Systems. Washington, DC: IEEE Computer Society, 2010: 297-304.

[7] MOTOYAMA M, VARGHESE G. I seek you: searching and matching individuals in social networks [C]// WIDM ’09: Proceedings of the Eleventh International Workshop on Web Information and Data Management. New York: ACM, 2009: 67-75.

[8] ZAMANI K, PALIOURAS G, VOGIATZIS D. Similarity-based user identification across social networks [C]// Proceedings of the 2015 International Workshop on Similarity-Based Pattern Recognition, LNCS 9370. Berlin: Springer-Verlag, 2015: 171-185.

[9] YE N, ZHAO L, DONG L, et al. User identification based on multiple attribute decision making in social networks [J]. China Communications, 2013, 10(12): 37-49.

[10] ESFANDYARI A, ZIGNANI M, GAITO S, et al. User identification across online social networks in practice: pitfalls and solutions [J/OL]. Journal of Information Science (2016- 10- 01) [2016- 12- 06]. https://doi.org/10.1177/0165551516673480.

[11] ROEDLER R, KERGL D, RODOSEK G D. Profile matching across online social networks based on Geo-tags [C]// NaBIC 2015: Proceedings of the 7th World Congress on Nature and Biologically Inspired Computing, AISC 419. Berlin: Springer-Verlag, 2016: 417-428.

[12] GOGA O, LEI H, PARTHASARATHI S H K, et al. Exploiting innocuous activity for correlating users across sites [C]// WWW ’13: Proceedings of the 22nd International Conference on World Wide Web. New York: ACM, 2013: 447-458.

[13] ZAFARANI R, LIU H. Connecting corresponding identities across communities [C]// ICWSM 2009: Proceedings of the 3rd International AAAI Conference on Weblogs and Social Media. Menlo Park, CA: AAAI Press, 2009: 354-357.

[14] PERITO D, CASTELLUCCIA C, KAAFAR M A, et al. How unique and traceable are usernames? [C]// PETS 2011: Proceedings of the 2011 International Symposium on Privacy Enhancing Technologies Symposium, LNCS 6794. Berlin: Springer-Verlag, 2011: 1-17.

[15] 張慧,張海濱,李瓊,等.基于人類視覺系統(tǒng)的圖像感知哈希算法[J].電子學(xué)報,2008,36(S1):30-34. (ZHANG H, ZHANG H B, LI Q, et al. Image perceptual hashing based on human visual system [J]. Acta Electronica Sinica, 2008, 36(S1):30-34.)

[16] 陳志華,吳彩榮,趙建鋒,等.SIFT算法的介紹和應(yīng)用[J]. 企業(yè)科技與發(fā)展,2011(19):50-51. (CHEN Z H, WU C R, ZHAO J F, et al. The introduction and application of SIFT[J]. Enterprise Science and Technology & Development, 2011(19): 50-51.)

[17] 袁適之,李晶,李石君,等.一種基于位置社交網(wǎng)絡(luò)的地點(diǎn)推薦算法[J].計算機(jī)應(yīng)用研究,2016,33(7):2003-2006. (YUAN S Z, LI J, LI S J, et al. Location recommendation algorithm based on location-based social networks[J]. Application Research of Computers, 22016, 33(7): 2003-2006.)

[18] YAN M, SANG J, XU C. Unified youtube video recommendation via cross-network collaboration [C]// ICMR ’15： Proceedings of the 5th ACM on International Conference on Multimedia Retrieval. New York: ACM, 2015: 19-26.

This work is partially supported by the National Natural Science Foundation of China (61379151), the National Key Technology R&D Program (2014BAH30B01).

WUZheng, born in 1992, M. S. candidate. His research interests include big data analysis, complex network.

YUHongtao, born in 1970, Ph. D., research fellow. His research interests include big data analysis， communication and information system.

LIUShuxin, born in 1987, Ph. D., assistant research fellow. His research interests include complex network, link prediction.

ZHUYuhang, born in 1982, M. S., assistant research fellow. His research interests include graph mining.

Useridentificationacrossmultiplesocialnetworksbasedoninformationentropy

WU Zheng*, YU Hongtao, LIU Shuxin, ZHU Yuhang

(NationalDigitalSwitchingEngineering&TechnologicalResearchCenter,ZhengzhouHenan450002,China)

The precision of user identification is low since the subjective weighting algorithms ignore the special meanings and effects of attributes in applications. To solve this problem, an Information Entropy based Multiple Social Networks User Identification Algorithm (IE-MSNUIA) was proposed. Firstly, the data types and physical meanings of different attributes were analyzed, then different similarity calculation methods were correspondingly adopted. Secondly, the weights of attributes were determined according to their information entropies, thus the potential information of each attribute could be fully exploited. Finally, all chosen attributes were integrated to determine whether the account pair was the matched one. Theoretical analysis and experimental results show that, compared with machine learning based algorithms and subjective weighting algorithms, the performance of the proposed algorithm is improved, on different datasets, the average precision of it is up to 97.2%, the average recall of it is up to 94.1%, and the average comprehensive evaluation metric of it is up to 95.6%. The proposed algorithm can accurately identify user accounts across multiple social networks.

user identification; attribute similarity; information entropy; information integration; online social network

TP391.4; TP181

A

2017- 02- 08;

2017- 03- 15。

國家自然科學(xué)基金資助項(xiàng)目(61379151)；國家科技支撐計劃項(xiàng)目(2014BAH30B01)。

吳錚(1992—)，男，江蘇徐州人，碩士研究生，主要研究方向：大數(shù)據(jù)分析、復(fù)雜網(wǎng)絡(luò)； 于洪濤(1970—)，男，遼寧丹東人，研究員，博士，主要研究方向：大數(shù)據(jù)分析、通信與信息系統(tǒng)； 劉樹新(1987—)，男，山東濰坊人，助理研究員，博士，主要研究方向：復(fù)雜網(wǎng)絡(luò)、鏈路預(yù)測； 朱宇航(1982—)，男，江蘇徐州人，助理研究員，碩士，主要研究方向：圖挖掘。

1001- 9081(2017)08- 2374- 07

10.11772/j.issn.1001- 9081.2017.08.2374