陳白楊，陳曉亮

（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，四川 成都 610039）

近年來(lái)，在線社交網(wǎng)絡(luò)(online social network,OSN)在世界范圍內(nèi)迅速普及，各種各樣的社交網(wǎng)絡(luò)服務(wù)平臺(tái)紛紛建立，如國(guó)內(nèi)的微博、豆瓣、貼吧，國(guó)外的Facebook、Twitter、Instagram。這些平臺(tái)為用戶提供了豐富多彩的個(gè)性化服務(wù)，如：Twitter、微博主要提供社交服務(wù)和微博客服務(wù)；Facebook、Instagram 主要提供社交服務(wù)和照片分享服務(wù)；豆瓣、貼吧主要提供影視、書(shū)籍、興趣活動(dòng)等分享服務(wù)。用戶為滿足不同的需求，往往不會(huì)局限于單個(gè)社交網(wǎng)絡(luò)，而會(huì)在多個(gè)網(wǎng)絡(luò)平臺(tái)上注冊(cè)賬號(hào)。這些用戶可以充當(dāng)連接不同網(wǎng)絡(luò)的橋梁，從而將多個(gè)社交網(wǎng)絡(luò)進(jìn)行連接、融合。

用戶對(duì)齊（user alignment,UA），旨在將不同社交網(wǎng)絡(luò)上的同一自然人聯(lián)系起來(lái)。開(kāi)發(fā)一個(gè)高質(zhì)量的用戶對(duì)齊模型有助于構(gòu)建一個(gè)全面的用戶特征表示。大量社交網(wǎng)絡(luò)應(yīng)用，如跨網(wǎng)絡(luò)朋友推薦[1]、信息擴(kuò)散[2?3]、鏈路預(yù)測(cè)[4]和網(wǎng)絡(luò)動(dòng)力學(xué)分析[5]等都表明了研究用戶對(duì)齊問(wèn)題的必要性和益處。

跨社交網(wǎng)絡(luò)用戶對(duì)齊的研究工作大致興起于2009 年，目前仍處于高速發(fā)展時(shí)期，各類(lèi)方法絡(luò)繹不絕。大數(shù)據(jù)條件下的跨網(wǎng)絡(luò)用戶對(duì)齊的算法研究和系統(tǒng)構(gòu)建成為了當(dāng)下研究的熱點(diǎn)。本文對(duì)近年來(lái)跨社交網(wǎng)絡(luò)用戶對(duì)齊的研究進(jìn)行了綜述：首先對(duì)研究的問(wèn)題進(jìn)行了形式化定義；然后從數(shù)據(jù)預(yù)處理、候選集生成、訓(xùn)練數(shù)據(jù)獲取、特征抽取、對(duì)齊算法5 方面概述了各種可用方法和研究進(jìn)展，重點(diǎn)從基于規(guī)則和基于統(tǒng)計(jì)2 個(gè)角度對(duì)主流的用戶對(duì)齊方法進(jìn)行了詳細(xì)闡述，并簡(jiǎn)要介紹了一些可用的數(shù)據(jù)集和算法評(píng)估方法；最后對(duì)目前面臨的問(wèn)題和挑戰(zhàn)進(jìn)行了探討，對(duì)未來(lái)的研究方向做出了展望。

1 問(wèn)題描述

跨社交網(wǎng)絡(luò)平臺(tái)的用戶對(duì)齊最初被定義為在不同社區(qū)之間鏈接具有相同身份的用戶[6]。用戶對(duì)齊也稱為用戶識(shí)別[7]（user identification）、錨定鏈接預(yù)測(cè)[8]（anchor link prediction）、個(gè)人資料鏈接[9]（profile linkage）、用 戶 身 份 鏈 接[10]（user identity linkage,UIL）等，其目的是在不同社交網(wǎng)絡(luò)平臺(tái)上對(duì)屬于同一自然人的用戶進(jìn)行鏈接。一般而言，具有唯一性的用戶屬性，如電子郵件地址、手機(jī)號(hào)碼和身份號(hào)碼等，可以直接用于確定在線社交網(wǎng)絡(luò)用戶的真實(shí)身份。然而，由于隱私保護(hù)和安全問(wèn)題，這些信息常難以獲取。研究者往往通過(guò)用戶在社交網(wǎng)絡(luò)平臺(tái)上公開(kāi)的信息，如用戶名、興趣愛(ài)好、職業(yè)、發(fā)表的帖子、好友關(guān)系等進(jìn)行跨社交網(wǎng)絡(luò)平臺(tái)的用戶對(duì)齊。下面對(duì)本文研究的問(wèn)題進(jìn)行定義。

定義1社交網(wǎng)絡(luò)。一個(gè)社交網(wǎng)絡(luò)是一個(gè)三元組G=(U,R,A)，其中U=表示該網(wǎng)絡(luò)中全體用戶的集合，R=表示網(wǎng)絡(luò)中用戶之間關(guān)系(如朋友、粉絲、關(guān)注等)的集合，A=表示全體用戶屬性的集合。

定義2用戶屬性。用戶屬性是用戶性質(zhì)或特征的集合，包括用戶的基本信息（如用戶名、工作單位等）和用戶生成的內(nèi)容（如用戶發(fā)布的微博、帖子等）。用戶屬性用一個(gè)由鍵值對(duì)組成的集合來(lái)表示，每個(gè)屬性鍵值對(duì)代表用戶某一方面的屬性，如＜姓名：邁克爾＞，其中“姓名”是屬性的類(lèi)型（或鍵）,“邁克爾”是該屬性的值。在社交網(wǎng)絡(luò)中，用戶通常具有許多不同類(lèi)型的屬性，例如姓名、年齡、隸屬關(guān)系等。用戶ui的 屬性表示為aui=，其中代 表 用 戶ui第j個(gè)屬性鍵值對(duì)。

定義3用戶對(duì)齊。給定2 個(gè)任意的社交網(wǎng)絡(luò)GX=(UX,RX,AX)和GY=(UY,RY,AY)，以及一些預(yù)先匹配的用戶對(duì)，用戶對(duì)齊(UA)的目標(biāo)是找到其他隱藏的匹配用戶對(duì)M=，其 中ui和uj屬于同一自然人。

2 用戶對(duì)齊技術(shù)概述

現(xiàn)有的用戶對(duì)齊技術(shù)大多可以歸納為一個(gè)統(tǒng)一的框架，如圖1 所示。該框架由5 個(gè)部分組成：1）數(shù)據(jù)預(yù)處理；2）候選集生成；3）標(biāo)注數(shù)據(jù)獲?。?）特征提??；5）用戶對(duì)齊算法。

圖1 跨社交網(wǎng)絡(luò)用戶對(duì)齊總體框架

對(duì)于待匹配的任意2 個(gè)或多個(gè)社交網(wǎng)絡(luò)平臺(tái)，首先應(yīng)對(duì)用戶數(shù)據(jù)進(jìn)行預(yù)處理，挑選出待匹配的候選用戶，并根據(jù)算法需要獲取必要的標(biāo)記數(shù)據(jù)；然后進(jìn)入到特征抽取和對(duì)齊算法模塊，先從用戶數(shù)據(jù)中提取到有用的特征作為對(duì)齊算法的輸入，再通過(guò)算法優(yōu)化、求解來(lái)預(yù)測(cè)候選用戶對(duì)是否匹配。

2.1 數(shù)據(jù)預(yù)處理

對(duì)于跨社交網(wǎng)絡(luò)平臺(tái)用戶對(duì)齊問(wèn)題，給定待匹配用戶的屬性集合中某些屬性可能很關(guān)鍵、很有用，另一些屬性則可能沒(méi)什么用。對(duì)當(dāng)前任務(wù)有用的屬性稱為“相關(guān)特征”，沒(méi)什么用的屬性稱為“無(wú)關(guān)特征”。數(shù)據(jù)預(yù)處理首先要做的就是從給定特征集合中選出和當(dāng)前任務(wù)有關(guān)的特征子集；然后，通過(guò)歸一化、標(biāo)準(zhǔn)化、正則化等方式改進(jìn)不完整、不一致、無(wú)法直接使用的數(shù)據(jù)。然而，在線社交網(wǎng)絡(luò)的數(shù)據(jù)龐大、零亂且高度非結(jié)構(gòu)化[11]，不同網(wǎng)絡(luò)平臺(tái)之間的用戶數(shù)據(jù)可能存在極大差異，這為數(shù)據(jù)的預(yù)處理帶來(lái)了巨大挑戰(zhàn)。值得慶幸的是，隨著數(shù)據(jù)清洗與整合技術(shù)的發(fā)展，數(shù)據(jù)預(yù)處理領(lǐng)域的大量研究成果可供借鑒，具體內(nèi)容可以參見(jiàn)文獻(xiàn)[12?14]，本文不再贅述。

2.2 候選集生成

一般對(duì)2 個(gè)或多個(gè)用戶進(jìn)行匹配的時(shí)候,需要將一個(gè)社交網(wǎng)絡(luò)平臺(tái)中所有用戶與其他待匹配的社交網(wǎng)絡(luò)平臺(tái)中所有用戶進(jìn)行比較，這將導(dǎo)致算法復(fù)雜度隨著網(wǎng)絡(luò)規(guī)模呈指數(shù)增長(zhǎng)。在大數(shù)據(jù)條件下，其計(jì)算量是難以接受的，而實(shí)際上可能的匹配用戶數(shù)量不會(huì)超過(guò)規(guī)模較小社交網(wǎng)絡(luò)的用戶數(shù)量。為了解決這個(gè)問(wèn)題，需要設(shè)計(jì)高效的算法在保證準(zhǔn)確率的前提下盡可能減少待匹配用戶的數(shù)量，使復(fù)雜的匹配計(jì)算只在最有可能的用戶中進(jìn)行。單個(gè)待匹配用戶一般稱為“候選用戶”，成對(duì)的待匹配用戶則稱為“候選用戶對(duì)”。所有候選用戶及候選用戶對(duì)統(tǒng)稱為“候選集”，候選集的生成一般可以采取3 種策略。

1）從所有待匹配用戶中選擇具有辨識(shí)度的用戶特征來(lái)進(jìn)行判斷。例如：Zafarani 等[6]首先通過(guò)尋找一組用戶名的關(guān)鍵詞來(lái)生成候選集，然后通過(guò)添加/刪除一系列前/后綴來(lái)進(jìn)行擴(kuò)展；MEgo2Vec直接將具有較高用戶名相似性的用戶對(duì)作為候選集[15]。

2）從已經(jīng)發(fā)現(xiàn)的匹配用戶出發(fā)，沿著其相鄰用戶進(jìn)行擴(kuò)展。例如：Bennacer 等[16]將已匹配用戶的直接鄰居作為候選集；Zhang 等[17]將已匹配用戶的d跳鄰居作為候選用戶集，d從1 開(kāi)始逐步增大。

3）將以上2 種策略相結(jié)合。例如COSNET 首先將具有較高用戶名相似度的用戶對(duì)作為初始候選集，然后沿著初始用戶的鄰居進(jìn)行擴(kuò)展[18]。

2.3 標(biāo)記數(shù)據(jù)獲取

在用戶對(duì)齊任務(wù)中，預(yù)先匹配的用戶對(duì)又稱為標(biāo)記數(shù)據(jù)。大部分基于統(tǒng)計(jì)學(xué)習(xí)的用戶對(duì)齊方法需要充足的標(biāo)記數(shù)據(jù)來(lái)進(jìn)行模型的訓(xùn)練。標(biāo)記數(shù)據(jù)無(wú)論是對(duì)匹配的準(zhǔn)確度還是算法的收斂速度都會(huì)產(chǎn)生重要影響。然而，大規(guī)模獲取這種標(biāo)記數(shù)據(jù)的成本較高。目前主要有2 種獲取標(biāo)記數(shù)據(jù)的手段。

1）一些社交網(wǎng)絡(luò)平臺(tái)允許用戶公開(kāi)自己在其他網(wǎng)絡(luò)平臺(tái)上的賬號(hào)。這些賬號(hào)即可作為獲取預(yù)先匹配用戶對(duì)的線索。這種數(shù)據(jù)獲取方式速度快、準(zhǔn)確度高，因此，大部分研究[15,19?20]采用這種方法。

2）部分用戶屬性具有很強(qiáng)的辨識(shí)度，通過(guò)人工設(shè)置一組規(guī)則可以自動(dòng)進(jìn)行數(shù)據(jù)標(biāo)注。例如Narayanan 等[21]通過(guò)搜索具有相同度數(shù)和鄰居數(shù)的k團(tuán)(k-clique)來(lái)獲取初始對(duì)齊用戶；Liu 等[22]通過(guò)分析用戶名的稀有性和通用性來(lái)自動(dòng)標(biāo)注訓(xùn)練數(shù)據(jù)；CoLink 預(yù)定義了一組基于用戶名稀有性、屬性一致性和用戶關(guān)系的規(guī)則來(lái)生成標(biāo)記數(shù)據(jù)[23]。這類(lèi)方法適用性廣，可以大規(guī)模獲取標(biāo)記數(shù)據(jù)，但準(zhǔn)確度相對(duì)較低。

2.4 特征抽取

由于用戶對(duì)齊問(wèn)題討論的是2 個(gè)或多個(gè)網(wǎng)絡(luò)之間用戶的關(guān)聯(lián)，其特征抽取可以分為2 種方式。

1）針對(duì)候選用戶對(duì)的特征抽取，即先從待匹配網(wǎng)絡(luò)中挑選成對(duì)的候選用戶，再對(duì)候選用戶對(duì)提取特征。這種類(lèi)型主要采取人工特征抽取技術(shù)（即特征工程）。傳統(tǒng)的人工特征提取是用戶對(duì)齊任務(wù)中特征抽取的重要方法，大量研究[20,24?25]采取這類(lèi)方法。

2）針對(duì)單個(gè)用戶的特征抽取，即先分別從待匹配網(wǎng)絡(luò)中挑選候選用戶，再對(duì)單一候選用戶提取特征。這種類(lèi)型主要采取基于表示學(xué)習(xí)（representation learning,RL)的方法。表示學(xué)習(xí)旨在將原始數(shù)據(jù)轉(zhuǎn)換成為能夠被計(jì)算機(jī)有效利用的表示形式，從而在構(gòu)建分類(lèi)器或其他預(yù)測(cè)模型時(shí)更容易提取有用的信息[26]。表示學(xué)習(xí)的重要特性在于允許計(jì)算機(jī)學(xué)習(xí)使用特征的同時(shí)，也學(xué)習(xí)如何提取特征。

社交網(wǎng)絡(luò)中的用戶數(shù)據(jù)[27]主要包括用戶的基本信息（如用戶名、職業(yè)、地理位置），用戶生成內(nèi)容（如用戶發(fā)布的帖子、博客、出版物）以及用戶之間的關(guān)系（如朋友、關(guān)注、被關(guān)注）等。這些數(shù)據(jù)按照表現(xiàn)形式不同又可以分為文本數(shù)據(jù)、圖像數(shù)據(jù)、音頻/視頻數(shù)據(jù)、地理位置數(shù)據(jù)、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)等。學(xué)者們利用用戶文本屬性和用戶網(wǎng)絡(luò)關(guān)系來(lái)進(jìn)行用戶對(duì)齊研究。下面主要介紹基于文本和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的特征抽取方法。

2.4.1 文本特征抽取

對(duì)于成對(duì)的文本類(lèi)型用戶屬性（如用戶名）主要采用字符串相似性算法來(lái)進(jìn)行特征提取，如Jaccard 相似度[28]、Jaro和Jaro-Winkler距離[29]、Levenshtein 距離[30]等。此外，一些研究[7，31?32]先將文本字符串向量化，再通過(guò)向量之間的距離度量，如余弦相似度、歐氏距離等來(lái)提取特征。

1）Jaccard 相似度。將待匹配的2 個(gè)字符串看作2 個(gè)由單一字符構(gòu)成的集合，再計(jì)算2 個(gè)集合的交集與并集的比值，即

其中a,b為 待匹配的2 個(gè)字符串。token(·)函數(shù)將字符串轉(zhuǎn)換為由單個(gè)字符組成的集合。Jaccard 相似度算法的優(yōu)點(diǎn)在于對(duì)文本順序無(wú)關(guān),但對(duì)錯(cuò)誤比較敏感,人工錄入錯(cuò)誤或字符缺失等情況會(huì)對(duì)結(jié)果產(chǎn)生較大影響。

2）Levenshtein 距離。即將一個(gè)字符串轉(zhuǎn)換另一個(gè)所需要的插入、刪除和替換操作的最小次數(shù)。Levenshtein 距離又稱為“編輯距離”，用ai/bj表示字符串a(chǎn)/b的第i/j個(gè) 字符，當(dāng)ai≠bj時(shí)，指示函數(shù)Iai≠bj的值 為1，否 則為0。函數(shù) Leva,b(i,j)表示a的前i個(gè)字符構(gòu)成的子串與b的前j個(gè)字符構(gòu)成的子串之間的Levenshtein 距離，則a和b之間的Levenshtein 距離 Leva,b(|a|,|b|)可以通過(guò)式（2）遞歸計(jì)算得出。

Levenshtein 距離可以降低相似性匹配的錯(cuò)誤敏感性，但是它為每一個(gè)字符的每一次編輯操作都賦予相同的權(quán)重（次數(shù)），沒(méi)有考慮不同字符或子串的重要程度；然而實(shí)際上不同位置的子串編輯操作對(duì)相似性匹配的重要性可能不同，比如一些前后綴和縮寫(xiě)詞的處理。

3）Jaro 和Jaro-Winkler 距離。Jaro 距離的主要思想是通過(guò)比較2 個(gè)字符串的公共部分來(lái)計(jì)算相似程度，所謂“公共”這里特指2 個(gè)字符相等并且它們?cè)谧址械奈恢镁嚯x之差Δ不大于較小字符串長(zhǎng)度的一半，即 ?≤0.5×min(|a|,|b|)，設(shè)t為公共部分發(fā)生位置交換的次數(shù),δ為公共字符的集合，則Jaro 距離可以定義為

Jaro 距離可以容忍少量的拼寫(xiě)錯(cuò)誤，但對(duì)于2 個(gè)主體部分相同但前綴或者后綴不同的字符串的度量效果并不好。Jaro-Winkler 距離對(duì)此進(jìn)行了改進(jìn)。對(duì)于字符串a(chǎn)和b以及共同前綴τ，Jaro-Winkler 距離表示為

其中，λ 為前綴τ 對(duì)整體相似度影響的一個(gè)系數(shù)。

4）基于向量距離的方法。先將文本字符串向量化，再通過(guò)計(jì)算2 個(gè)向量之間的距離來(lái)評(píng)估字符串相似程度。將文本字符串表示為向量的常用方法有詞袋模型（bag-of-words,BOW）、詞頻–逆文檔頻 率（term frequency-inverse document frequency,TF-IDF）等。

詞袋模型忽略文本的語(yǔ)序、語(yǔ)法或句法關(guān)系，將其僅僅看作是一個(gè)詞的集合，文本中每個(gè)詞的出現(xiàn)都是獨(dú)立的，不依賴于其他詞是否出現(xiàn)。對(duì)字符串a(chǎn)，其詞袋向量化表示定義為

其中 tfc表 示字符表 V 中第c個(gè)字符在a中 出現(xiàn)的次數(shù)。

TF-IDF 在詞袋模型的基礎(chǔ)上進(jìn)行了改進(jìn)。其核心思想在于：一個(gè)詞的重要程度跟它在單個(gè)文檔中的計(jì)數(shù)成正比，而跟它在語(yǔ)料庫(kù)中出現(xiàn)的次數(shù)成反比。對(duì)字符串a(chǎn)，其TF-IDF 向量化表示為

式中：D表示語(yǔ)料庫(kù)中文檔的總數(shù)(即用戶總數(shù))；dfc表 示語(yǔ)料庫(kù)中包含詞匯表 V中第c個(gè)單詞的文檔的數(shù)量。

在將字符串a(chǎn)和b分 別進(jìn)行向量化表示后，其余弦相似度可表示為

其歐式距離表示為

基于向量距離的文本特征抽取方法具有適用性廣的優(yōu)點(diǎn)，能夠有效提取長(zhǎng)文本的語(yǔ)義特征，但仍然忽略了詞的順序以及語(yǔ)法、句法關(guān)系。此外，少量研究也在成對(duì)用戶文本特征提取中采用了表示學(xué)習(xí)方法，如MEgo2Vec 先將候選用戶對(duì)的文本屬性用卷積神經(jīng)網(wǎng)絡(luò)（convolution neural network,CNN）從字符和詞2 個(gè)視角分別進(jìn)行嵌入，再進(jìn)行拼接，通過(guò)訓(xùn)練使得匹配用戶之間的文本屬性向量距離最小[15]。

對(duì)于單一用戶的文本類(lèi)型屬性，大部分研究采用基于表示學(xué)習(xí)的方法來(lái)提取特征?；诒硎緦W(xué)習(xí)的特征抽取方法往往能夠從大規(guī)模訓(xùn)練數(shù)據(jù)中獲得對(duì)下游任務(wù)有用的特征表示，性能通常較高，但也需要構(gòu)建較復(fù)雜的優(yōu)化模型，運(yùn)算量較大。自然語(yǔ)言處理技術(shù)中有大量相關(guān)研究，本文不再敘述。

2.4.2 網(wǎng)絡(luò)結(jié)構(gòu)特征抽取

對(duì)于候選用戶對(duì)之間的網(wǎng)絡(luò)結(jié)構(gòu)特征一般用一些結(jié)構(gòu)相似性函數(shù)進(jìn)行度量，如共同鄰居計(jì)數(shù)[33]、Jaccard 系數(shù)[28]、Adamic/Adar 系數(shù)[34]等。

1）共同鄰居計(jì)數(shù)（common neighbors）。即2 個(gè)用戶在不同網(wǎng)絡(luò)中的屬于同一自然人的相鄰用戶個(gè)數(shù)。用戶ui和uj的相鄰用戶分別用N B(ui)和 NB表示，其共同鄰居計(jì)數(shù)s imNB表示為

其中，K為一個(gè)足夠大的常數(shù)，使得所有用戶對(duì)的共同鄰居計(jì)數(shù)值都在0 到1 之間。

2）Jaccard 系數(shù)。即2 個(gè)用戶的共同鄰居計(jì)數(shù)與他們所有鄰居計(jì)數(shù)的比值，定義為

Jaccard 系數(shù)和共同鄰居計(jì)數(shù)都比較簡(jiǎn)單直觀，但Jaccard 系數(shù)考慮了節(jié)點(diǎn)本身的度數(shù)，從而能夠區(qū)分不同節(jié)點(diǎn)的重要程度。此外，兩者都為每個(gè)匹配的鄰居賦予相同的權(quán)重，但實(shí)際中某些鄰居可能具有不同的影響力或作用。為此，Adamic/Adar系數(shù)進(jìn)行了改善。

3）Adamic/Adar 系數(shù)。其核心思想是存在關(guān)聯(lián)關(guān)系越多的用戶作為鄰居在計(jì)算中所分配權(quán)重越低，其定義為

Adamic/Adar 系數(shù)提升了算法的準(zhǔn)確率，但相應(yīng)地增加了運(yùn)算復(fù)雜度。此外，一些研究將待匹配的2 個(gè)（或多個(gè)）網(wǎng)絡(luò)通過(guò)預(yù)先匹配用戶整合為一個(gè)統(tǒng)一網(wǎng)絡(luò)，然后在這個(gè)統(tǒng)一網(wǎng)絡(luò)上進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)，進(jìn)而獲得候選用戶對(duì)的有效特征表示，例如MGGE 先將2 個(gè)網(wǎng)絡(luò)進(jìn)行合并，然后利用社交網(wǎng)絡(luò)在結(jié)構(gòu)上的高階鄰近性和面向?qū)R任務(wù)的特性來(lái)構(gòu)造網(wǎng)絡(luò)表示學(xué)習(xí)模型[35]。

對(duì)于單個(gè)用戶的網(wǎng)絡(luò)結(jié)構(gòu)特征，研究者大多采取諸如DeepWalk[36]、LINE[37]、TADW[38]、Node2vec[39]、Struc2vec[40]、GAT[41]等的網(wǎng)絡(luò)表示學(xué)習(xí)的方法進(jìn)行特征學(xué)習(xí)。此外，一些異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)方法，如TransE[42]及其擴(kuò)展等也可以直接運(yùn)用于社交網(wǎng)絡(luò)結(jié)構(gòu)的特征提取。表1 示出本文闡述的各種特征抽取方法。

表1 特征抽取方法對(duì)比

2.5 用戶對(duì)齊方法概述

一般來(lái)說(shuō)，用戶對(duì)齊方法總體上可以劃分為2 大類(lèi)：基于規(guī)則的方法和基于統(tǒng)計(jì)學(xué)習(xí)的方法?；谝?guī)則的方法首先從社交網(wǎng)絡(luò)平臺(tái)用戶數(shù)據(jù)中人工挑選一組適合的用戶屬性，再針對(duì)每個(gè)屬性設(shè)計(jì)評(píng)分規(guī)則，最后通過(guò)匹配算法來(lái)實(shí)現(xiàn)跨社交網(wǎng)絡(luò)的用戶對(duì)齊，這部分內(nèi)容將在3.1 節(jié)進(jìn)行詳細(xì)闡述?；诮y(tǒng)計(jì)學(xué)習(xí)的方法，也稱為基于統(tǒng)計(jì)機(jī)器學(xué)習(xí)的方法[43]，通過(guò)特征工程或表示學(xué)習(xí)來(lái)抽取用戶特征，并訓(xùn)練預(yù)測(cè)模型來(lái)進(jìn)行用戶對(duì)齊，這類(lèi)方法是當(dāng)前跨社交網(wǎng)絡(luò)用戶對(duì)齊研究的主流方法，將在3.2 節(jié)進(jìn)行詳細(xì)介紹。

此外，由于用戶對(duì)齊問(wèn)題與傳統(tǒng)的網(wǎng)絡(luò)對(duì)齊[44]（network alignment）和知識(shí)庫(kù)實(shí)體對(duì)齊[45](knowledge base entity alignment）在問(wèn)題設(shè)置、研究方法、評(píng)估方法等方面比較相似，因此，網(wǎng)絡(luò)對(duì)齊和實(shí)體對(duì)齊的一些方法也可以適用于用戶對(duì)齊問(wèn)題，這部分內(nèi)容將在第3 章相關(guān)部分進(jìn)行概述。

3 用戶對(duì)齊方法

3.1 基于規(guī)則的用戶對(duì)齊方法

基于規(guī)則的方法是用戶對(duì)齊問(wèn)題的重要方法，早期的大量研究建立在這種方法之上。一個(gè)典型的基于規(guī)則的用戶對(duì)齊方法有4 個(gè)步驟。

步驟1，通過(guò)數(shù)據(jù)預(yù)處理從社交網(wǎng)絡(luò)中挑選出對(duì)當(dāng)前任務(wù)有用的屬性，如用戶名、出生日期、工作單位、朋友關(guān)系等。

步驟2，對(duì)每個(gè)屬性設(shè)計(jì)相應(yīng)的評(píng)分規(guī)則，并計(jì)算候選集中待匹配用戶對(duì)的各項(xiàng)評(píng)分。

步驟3，將候選用戶對(duì)的各項(xiàng)評(píng)分進(jìn)行加權(quán)求和，得到該候選用戶對(duì)的匹配度。

步驟4，通過(guò)一個(gè)特定匹配算法進(jìn)行用戶對(duì)齊。

給定一個(gè)候選用戶對(duì) (ui,uj)及其對(duì)應(yīng)的屬性集合 K，通過(guò)特征抽取方法，用sk(ui,uj)表示該候選用戶對(duì)的第k個(gè)特征的評(píng)分，則該用戶對(duì)的匹配度Sij可以表示為

其中 αk∈[0,1]表 示第k個(gè)特征的權(quán)重系數(shù)。下面介紹一些常見(jiàn)的用戶匹配算法。

3.1.1 匹配度最大化用戶對(duì)齊算法

在獲得候選用戶對(duì)的匹配度以后，一種最直觀的用戶對(duì)齊方法是將候選集中具有與目標(biāo)用戶最大匹配度的候選用戶作為對(duì)齊用戶。早期研究大多利用用戶公開(kāi)的屬性信息來(lái)進(jìn)行用戶對(duì)齊。例如：Zafarani 等[6]直接利用待匹配用戶的用戶名進(jìn)行字符串模式匹配；Iofciu 等[46]結(jié)合用戶名的字符串相似性和標(biāo)簽（Tag）模式相似性來(lái)搜索對(duì)齊用戶。用戶屬性信息通常比較容易獲得，但不同的社交網(wǎng)絡(luò)之間的用戶屬性可能差異極大，僅僅依靠用戶屬性可能難以取得比較好的對(duì)齊效果。用戶之間的關(guān)系反映了用戶在網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)特征，為跨網(wǎng)絡(luò)的用戶識(shí)別提供了重要線索。因此，一些研究者通過(guò)用戶在網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)來(lái)識(shí)別匹配用戶。例如：CPCC 設(shè)計(jì)了3 個(gè)基于網(wǎng)絡(luò)結(jié)構(gòu)的相似性指標(biāo)，并通過(guò)綜合比較候選用戶對(duì)的結(jié)構(gòu)相似度來(lái)發(fā)現(xiàn)匹配用戶[24]；馮朔等[47]借鑒圖論中最大公共子圖的思想來(lái)定義用戶之間匹配度，匹配度越高代表2 個(gè)用戶有越高的概率是同一自然人。社交網(wǎng)絡(luò)中用戶之間關(guān)系可能非常嘈雜，而大規(guī)模社交網(wǎng)絡(luò)的完整結(jié)構(gòu)信息通常難以獲取，單純依靠網(wǎng)絡(luò)結(jié)構(gòu)特征的用戶對(duì)齊方法也有其局限性；因此，研究者往往把用戶的屬性特征和網(wǎng)絡(luò)結(jié)構(gòu)特征相結(jié)合，以提高預(yù)測(cè)準(zhǔn)確率。例如：Labitzke 等[48]提出通過(guò)比較用戶朋友的用戶名來(lái)發(fā)現(xiàn)匹配用戶；DCIM 基于用戶發(fā)布的文章和好友關(guān)系定義了動(dòng)態(tài)核心興趣度的概念，然后采用余弦相似度來(lái)計(jì)算目標(biāo)用戶對(duì)之間匹配度[49]。

為了進(jìn)一步提高預(yù)測(cè)準(zhǔn)確性，一些算法在最大匹配度規(guī)則上設(shè)置了約束。約束主要包括2 種類(lèi)型。

1）只有當(dāng)最大匹配度達(dá)到某個(gè)閾值的候選者才被識(shí)別為匹配用戶對(duì)。例如：Vosecky 等[7]提出了一個(gè)字符串相似度算法，將用戶之間的多個(gè)文本屬性（包括用戶名、E-mail、生日等）的相似度進(jìn)行加權(quán)求和，再通過(guò)一個(gè)閾值來(lái)過(guò)濾相似度較低的候選用戶對(duì)；Perito 等[32]討論了用戶名的獨(dú)特性，通過(guò)用戶名相似性來(lái)識(shí)別匹配用戶，并用一個(gè)閾值來(lái)調(diào)節(jié)算法的查準(zhǔn)率和查全率。

2）一對(duì)一匹配約束?；谧畲笃ヅ涠鹊姆椒ê?jiǎn)單、直觀，但沒(méi)有考慮匹配結(jié)果的唯一性，輸出的結(jié)果可能存在一對(duì)多（即一個(gè)網(wǎng)絡(luò)中的某用戶和另外一個(gè)網(wǎng)絡(luò)中的多個(gè)用戶相匹配）、多對(duì)多的情況；因此，研究者提出了一對(duì)一匹配約束。例如：Narayanan 等[21]要求候選用戶對(duì)在2 個(gè)網(wǎng)絡(luò)中彼此都具有最大匹配度（又稱為“雙向最大匹配度”），且匹配度達(dá)到一個(gè)閾值方可進(jìn)行對(duì)齊；Buccafurri等[50]考慮了用戶名的文本相似度和基于共同鄰居計(jì)數(shù)的網(wǎng)絡(luò)結(jié)構(gòu)相似度，通過(guò)一個(gè)閾值過(guò)濾相似度較低的候選用戶對(duì)，再設(shè)置另一個(gè)閾值識(shí)別對(duì)齊用戶；User-Matching 計(jì)算了候選用戶對(duì)的基于網(wǎng)絡(luò)結(jié)構(gòu)特征的匹配度，然后通過(guò)一個(gè)帶閾值的雙向最大匹配度算法來(lái)搜索匹配用戶對(duì)[51]；POIS 先通過(guò)地理位置軌跡特征來(lái)計(jì)算候選用戶對(duì)匹配度，然后在二部圖上進(jìn)行一對(duì)一用戶匹配[52]。

3.1.2 基于傳播的用戶對(duì)齊方法

基于傳播的用戶對(duì)齊方法可以利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及已經(jīng)獲取到的匹配用戶信息來(lái)迭代地發(fā)現(xiàn)新的匹配用戶。設(shè) N(ui)和分別表示用戶ui及uj的相鄰用戶的集合，傳播算法通過(guò)一個(gè)基于鄰居特征的匹配函數(shù)來(lái)計(jì)算新的候選用戶對(duì)的匹配度，并進(jìn)行多次迭代，直到?jīng)]有發(fā)現(xiàn)新的匹配用戶對(duì)為止。依據(jù)候選集的生成方式，傳播方法可采取2 種傳播規(guī)則。

1）窮舉法，即從剩余的未匹配用戶對(duì)中選擇候選用戶對(duì)。例如：Narayanan 等[21]通過(guò)搜索具有相同度數(shù)和鄰居數(shù)的k團(tuán)(k-clique)來(lái)獲取初始對(duì)齊用戶，然后重復(fù)從所有未匹配用戶中隨機(jī)選取候選用戶對(duì)進(jìn)行匹配；User-Matching 首先通過(guò)基于共同鄰居計(jì)數(shù)的規(guī)則來(lái)識(shí)別匹配用戶，然后用一個(gè)預(yù)設(shè)條件來(lái)挑選新的候選用戶對(duì)，逐步發(fā)現(xiàn)更多的對(duì)齊用戶[51]。

2）相鄰搜索，即從現(xiàn)有匹配用戶對(duì)的鄰居中選擇候選用戶對(duì)。例如：Buccafurri 等[50]和Shen 等[53]綜合利用了用戶屬性相似度和網(wǎng)絡(luò)結(jié)構(gòu)相似度來(lái)識(shí)別對(duì)齊用戶，然后沿著相鄰用戶進(jìn)行傳播；Bennacer等[16]則通過(guò)基于用戶名、姓名、Email 等屬性相似度的規(guī)則來(lái)迭代搜索匹配用戶對(duì)；FRUI 僅依靠朋友關(guān)系特征來(lái)計(jì)算用戶匹配度，然后沿著匹配用戶的鄰居關(guān)系進(jìn)行傳播[54]；CLA 基于用戶鏈接信息定義了朋友匹配度，并結(jié)合用戶名、URL、E-mail 等屬性相似度來(lái)迭代發(fā)現(xiàn)對(duì)齊用戶[25]。

此外，知識(shí)庫(kù)實(shí)體對(duì)齊方法中也有基于傳播的算法可供借鑒，例如SiGMa 利用實(shí)體屬性和鄰居結(jié)構(gòu)特征計(jì)算候選實(shí)體對(duì)的相似度評(píng)分，并一對(duì)一進(jìn)行實(shí)體對(duì)齊，然后沿著相鄰實(shí)體迭代搜索新的匹配實(shí)體對(duì)[55]。表2 匯總了本文闡述的基于規(guī)則的用戶對(duì)齊方法。

表2 基于規(guī)則的用戶對(duì)齊方法

3.2 基于統(tǒng)計(jì)學(xué)習(xí)的用戶對(duì)齊方法

隨著機(jī)器學(xué)習(xí)和深度學(xué)習(xí)技術(shù)的快速發(fā)展，大量基于統(tǒng)計(jì)學(xué)習(xí)的方法也被應(yīng)用到用戶對(duì)齊領(lǐng)域，并取得了豐碩的研究成果?；诮y(tǒng)計(jì)學(xué)習(xí)的用戶對(duì)齊方法主要有2 種工作模式：一是通過(guò)特征工程人工提取用戶特征，然后在標(biāo)記數(shù)據(jù)的基礎(chǔ)上訓(xùn)練分類(lèi)模型；二是通過(guò)表示學(xué)習(xí)的方法學(xué)得適應(yīng)于用戶對(duì)齊任務(wù)的最佳用戶表示，然后再進(jìn)行跨網(wǎng)絡(luò)用戶匹配。依據(jù)使用標(biāo)注數(shù)據(jù)數(shù)量的不同，基于統(tǒng)計(jì)學(xué)習(xí)的用戶對(duì)齊方法又可以分為基于監(jiān)督學(xué)習(xí)（supervised learning）、基于半監(jiān)督學(xué)習(xí)（semi-supervised learning）和基于無(wú)監(jiān)督學(xué)習(xí)（unsupervised learning）的用戶對(duì)齊方法。

3.2.1 基于監(jiān)督學(xué)習(xí)的用戶對(duì)齊方法

基于監(jiān)督學(xué)習(xí)的用戶對(duì)齊方法需要將預(yù)先匹配的用戶對(duì)作為標(biāo)記數(shù)據(jù)，然后使用訓(xùn)練好的模型對(duì)待匹配的候選用戶對(duì)進(jìn)行預(yù)測(cè)。一個(gè)典型的監(jiān)督學(xué)習(xí)模型[56]有以下3 個(gè)步驟。

步驟1，選擇合適模型，使用訓(xùn)練數(shù)據(jù)對(duì)模型進(jìn)行訓(xùn)練，并進(jìn)行參數(shù)調(diào)節(jié)。

步驟2，對(duì)以上訓(xùn)練出來(lái)的模型進(jìn)行測(cè)試和評(píng)估，并進(jìn)一步調(diào)節(jié)參數(shù)或改進(jìn)模型。

步驟3，將測(cè)試好的模型應(yīng)用于實(shí)際數(shù)據(jù)進(jìn)行預(yù)測(cè)。

基于監(jiān)督學(xué)習(xí)的方法一般將用戶對(duì)齊任務(wù)設(shè)置為分類(lèi)問(wèn)題，其訓(xùn)練數(shù)據(jù)包括2 類(lèi)實(shí)例：一是真實(shí)的匹配用戶對(duì)，稱為“正例（positive instances）”；二是非匹配用戶對(duì)，稱為“負(fù)例（negative instances）”。集合表示所有候選用戶對(duì)，M=屬于同一自然人?Q表 示正例集合，N=Q?M表示負(fù)例集合。候選用戶對(duì)集合 Q又 可以劃分為訓(xùn)練集 Q′和測(cè)試集 Q′′。基于監(jiān)督學(xué)習(xí)的用戶對(duì)齊模型目標(biāo)在于在訓(xùn)練集 Q′上學(xué)得一個(gè)映射函數(shù) F :UX×UY→{0,1}。早期的基于監(jiān)督學(xué)習(xí)的用戶對(duì)齊方法通常在人工提取特征的基礎(chǔ)上訓(xùn)練分類(lèi)器模型。給定一個(gè)候選用戶對(duì)(ui,uj)及 其對(duì)應(yīng)的屬性集合 K，通過(guò)特征抽取，用sk(ui,uj)表 示該候選用戶對(duì)的第k個(gè)特征的評(píng)分，則可以用一個(gè) |K|維 向量fij來(lái)表示該用戶對(duì)，即

在此基礎(chǔ)上，一些常見(jiàn)的分類(lèi)器，如支持向量機(jī)[57](support vector machine,SVM)、決 策 樹(shù)[58](decision tree)、樸素貝葉斯[59](na?ve bayes)等可以用來(lái)構(gòu)建有監(jiān)督的用戶對(duì)齊模型。例如：Motoyama 等[31]提取了候選用戶對(duì)的文本屬性特征（包括生日、地址、教育背景等），然后通過(guò)提升技術(shù)[60]（Boosting）將多個(gè)弱分類(lèi)器進(jìn)行整合；Malhotra 等[61]和Zhang 等[9]則全面考察了包括圖像特征（如頭像、臉部照片等）在內(nèi)的多種用戶特征來(lái)構(gòu)建分類(lèi)器模型，并進(jìn)行有監(jiān)督的用戶對(duì)齊；Bartunov 等[62]、Peled 等[63]以及Li 等[20]結(jié)合用戶文本屬性和網(wǎng)絡(luò)結(jié)構(gòu)特征來(lái)構(gòu)建分類(lèi)模型；MOBIUS 從用戶行為模式中提取特征，并在決策樹(shù)、樸素貝葉斯、隨機(jī)森林、支持向量機(jī)、邏輯斯蒂回歸等多個(gè)分類(lèi)器上取得了近似的用戶對(duì)齊效果[64]；朱俊星[65]對(duì)中文用戶名的特性進(jìn)了研究，然后在用戶名相似度評(píng)分的基礎(chǔ)上訓(xùn)練多個(gè)分類(lèi)器。

與此同時(shí)，一些研究者在分類(lèi)器模型基礎(chǔ)上結(jié)合了基于規(guī)則的匹配算法，例如：MNA 通過(guò)擴(kuò)展的共同鄰居計(jì)數(shù)、Jaccard 系數(shù)、Adamic/Adar 系數(shù)提取了用戶文本屬性特征、用戶關(guān)系特征和用戶時(shí)空分布特征，然后在訓(xùn)練分類(lèi)器模型的基礎(chǔ)上提出了一個(gè)一對(duì)一的穩(wěn)定匹配算法[8]；Zhang 等[17]利用了用戶昵稱、地址、朋友關(guān)系等特征來(lái)構(gòu)建分類(lèi)器模型搜索對(duì)齊用戶，并沿著匹配用戶的鄰居進(jìn)行迭代傳播。

近年來(lái)，基于有監(jiān)督表示學(xué)習(xí)的用戶對(duì)齊方法越來(lái)越受到研究者的重視。這類(lèi)方法有2 種工作模式。

1）將待匹配的2 個(gè)網(wǎng)絡(luò)通過(guò)表示學(xué)習(xí)映射到同一低維向量空間中，使得真實(shí)匹配用戶對(duì)在向量空間中的距離最小。例如PALE 利用網(wǎng)絡(luò)結(jié)構(gòu)信息，通過(guò)一個(gè)映射函數(shù)將源網(wǎng)絡(luò)投影到目標(biāo)網(wǎng)絡(luò)，從而使匹配用戶之間的距離最小化[66]。與之類(lèi)似，ULink 通過(guò)學(xué)習(xí)一個(gè)投影矩陣將來(lái)自多個(gè)社交網(wǎng)絡(luò)的用戶映射到同一個(gè)潛在用戶空間中[10]。ABNE 利用社交網(wǎng)絡(luò)中用戶的關(guān)注和粉絲關(guān)系并結(jié)合圖注意力機(jī)制[41](graph attention network,GAT)來(lái)進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)[67]。KGEUA 采用TransE[42]模型將2 個(gè)網(wǎng)絡(luò)嵌入到同一個(gè)向量空間，再結(jié)合共同朋友計(jì)數(shù)來(lái)識(shí)別匹配用戶[68]。DPlink 獲取了用戶活動(dòng)的時(shí)空位置信息，構(gòu)造了基于深度神經(jīng)網(wǎng)絡(luò)的位置編碼器、軌跡編碼器以及分類(lèi)器模型來(lái)實(shí)現(xiàn)用戶對(duì)齊[69]。MGGE 利用社交網(wǎng)絡(luò)在結(jié)構(gòu)上的高階鄰近性和面向?qū)R任務(wù)的特性來(lái)進(jìn)行表示學(xué)習(xí)，最后通過(guò)比較向量相似度來(lái)識(shí)別匹配用戶[35]。

2）通過(guò)表示學(xué)習(xí)自動(dòng)抽取候選用戶對(duì)的特征，然后通過(guò)構(gòu)建分類(lèi)器進(jìn)行用戶對(duì)齊。例如IAUE[70]在進(jìn)行網(wǎng)絡(luò)粗?；幕A(chǔ)上采用node2vec[39]模型進(jìn)行圖表示學(xué)習(xí)，訓(xùn)練分類(lèi)器來(lái)搜索對(duì)齊用戶，最后通過(guò)穩(wěn)定婚姻匹配算法[71]篩選出一對(duì)一的匹配用戶；MEgo2Vec[15]采用卷積神經(jīng)網(wǎng)絡(luò)將待匹配用戶對(duì)的自我中心網(wǎng)絡(luò)進(jìn)行嵌入，然后通過(guò)一個(gè)二元分類(lèi)器輸出預(yù)測(cè)結(jié)果；SAUIL[72]挖掘了社交網(wǎng)絡(luò)中用戶的網(wǎng)絡(luò)瀏覽行為，并通過(guò)一個(gè)孿生神經(jīng)網(wǎng)絡(luò)[73]（siamese neural network）模型和分類(lèi)器來(lái)識(shí)別對(duì)齊用戶。

3.2.2 基于無(wú)監(jiān)督學(xué)習(xí)的用戶對(duì)齊方法

在缺乏標(biāo)記數(shù)據(jù)的情況下，研究者通過(guò)無(wú)監(jiān)督的機(jī)器學(xué)習(xí)來(lái)解決用戶對(duì)齊問(wèn)題。目前，基于無(wú)監(jiān)督機(jī)器學(xué)習(xí)的用戶對(duì)齊方法主要有2 種模式。

1）首先在具有較強(qiáng)辨識(shí)度的屬性特征上設(shè)置一組規(guī)則來(lái)自動(dòng)獲取標(biāo)記數(shù)據(jù)，然后進(jìn)行有監(jiān)督的用戶對(duì)齊。例如：Liu 等[22]首先通過(guò)評(píng)估用戶名的稀有性來(lái)自動(dòng)標(biāo)記匹配用戶對(duì)，然后利用一系列相似性評(píng)估算法來(lái)提取候選用戶特征，最后采用二元分類(lèi)器模型來(lái)識(shí)別對(duì)齊用戶；CoLink[19]定義了一組規(guī)則用于自動(dòng)生成標(biāo)記數(shù)據(jù)，然后在協(xié)同訓(xùn)練框架下，構(gòu)建一個(gè)基于用戶屬性的序列到序列[74](sequence to sequence)神經(jīng)網(wǎng)絡(luò)模型和一個(gè)基于共同鄰居計(jì)數(shù)的相似度模型，使它們迭代相互增強(qiáng)。

2）首先通過(guò)無(wú)監(jiān)督的表示學(xué)習(xí)抽取候選用戶特征，然后利用對(duì)齊算法識(shí)別匹配用戶。例如UMA[75]和FRUI-P[76]僅利用網(wǎng)絡(luò)結(jié)構(gòu)特征進(jìn)行對(duì)齊模型構(gòu)建。UMA 討論了多個(gè)待匹配網(wǎng)絡(luò)之間對(duì)齊用戶的傳遞性，并考慮了一對(duì)一匹配約束。FRUI-P 通過(guò)隨機(jī)游走和CBOW[77]模型進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)，使得對(duì)齊用戶之間在潛在向量空間中的距離最小。UUIL[78]則采用了一個(gè)全新的研究路徑，它將社交網(wǎng)絡(luò)中的全體用戶看作一個(gè)離散概率分布，構(gòu)建了一個(gè)瓦瑟斯坦對(duì)抗生成網(wǎng)絡(luò)[79]（wasserstein GAN）模型和一個(gè)正交矩陣變換模型，通過(guò)最小化2 個(gè)網(wǎng)絡(luò)對(duì)應(yīng)的分布來(lái)學(xué)習(xí)2 個(gè)網(wǎng)絡(luò)之間的映射，使得同一自然人之間的距離最近。

此外，網(wǎng)絡(luò)對(duì)齊方法中也有基于無(wú)監(jiān)督表示學(xué)習(xí)的模型可供參考。例如REGAL 首先提取了節(jié)點(diǎn)網(wǎng)絡(luò)鄰近性和屬性文本相似性特征，然后通過(guò)矩陣分解來(lái)進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)，最后按照相似度排名來(lái)進(jìn)行網(wǎng)絡(luò)對(duì)齊[80]。

3.2.3 基于半監(jiān)督學(xué)習(xí)的用戶對(duì)齊方法

無(wú)監(jiān)督方法不依賴于標(biāo)記數(shù)據(jù)，與有監(jiān)督方法相比，其性能相對(duì)較低。一些基于半監(jiān)督學(xué)習(xí)的方法被用來(lái)解決用戶對(duì)齊問(wèn)題。半監(jiān)督學(xué)習(xí)方法能夠充分利用少量標(biāo)記數(shù)據(jù)和大量未標(biāo)記數(shù)據(jù)來(lái)獲取數(shù)據(jù)潛在分布，從而有效提高用戶對(duì)齊模型效果。IONE[81]和DeepLink[82]僅依靠網(wǎng)絡(luò)結(jié)構(gòu)特征來(lái)進(jìn)行模型構(gòu)建。IONE 將用戶的關(guān)注/粉絲關(guān)系表示為輸入/輸出背景向量，在一個(gè)統(tǒng)一的優(yōu)化框架下同時(shí)解決了網(wǎng)絡(luò)嵌入問(wèn)題和用戶對(duì)齊問(wèn)題；DeepLink 在網(wǎng)絡(luò)表示學(xué)習(xí)的基礎(chǔ)上構(gòu)建了一個(gè)基于半監(jiān)督強(qiáng)化學(xué)習(xí)的用戶對(duì)齊模型，并結(jié)合了對(duì)偶學(xué)習(xí)(dual learning)機(jī)制，充分利用未標(biāo)記數(shù)據(jù)來(lái)提升模型效果。MAH[83]、COSNET[18]、MSUIL[19]和dNAME[84]都結(jié)合了用戶文本屬性和網(wǎng)絡(luò)結(jié)構(gòu)特征來(lái)識(shí)別匹配用戶。MAH 提出一種基于超圖的表示學(xué)習(xí)模型，并提取用戶名特征來(lái)改善模型效果；COSNET 綜合考慮了用戶屬性匹配、網(wǎng)絡(luò)鄰居結(jié)構(gòu)匹配和多個(gè)網(wǎng)絡(luò)的全局一致性，采用一個(gè)半監(jiān)督的能量模型來(lái)迭代地發(fā)現(xiàn)對(duì)齊用戶；MSUIL 首先采用TADW[38]模型做無(wú)監(jiān)督屬性網(wǎng)絡(luò)嵌入（attributed network embedding），然后在UUIL 的基礎(chǔ)上結(jié)合多個(gè)網(wǎng)絡(luò)之間的交互依賴性將每對(duì)社交網(wǎng)絡(luò)映射到一個(gè)向量空間；dNAME 關(guān)注模型的可解釋性，利用圖卷積神經(jīng)網(wǎng)絡(luò)（graph convolution network,GCN）來(lái)進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)，并通過(guò)對(duì)抗式學(xué)習(xí)范式來(lái)進(jìn)一步區(qū)分對(duì)齊用戶及其鄰居。HYDRA[85]深入挖掘包括了圖像特征在內(nèi)的用戶行為軌跡特征和結(jié)構(gòu)一致性特征，提出了一個(gè)半監(jiān)督的多目標(biāo)優(yōu)化框架來(lái)進(jìn)行跨社交網(wǎng)絡(luò)用戶對(duì)齊。表3 匯總了本文闡述的用戶對(duì)齊算法。

表3 基于統(tǒng)計(jì)學(xué)習(xí)的用戶對(duì)齊方法

4 評(píng)估方法

4.1 數(shù)據(jù)集

社交網(wǎng)絡(luò)平臺(tái)的用戶數(shù)據(jù)通常由網(wǎng)絡(luò)服務(wù)提供商進(jìn)行維護(hù)和存儲(chǔ)。研究者可以通過(guò)應(yīng)用程序接口（API）、網(wǎng)絡(luò)爬蟲(chóng)等方式進(jìn)行讀取。單個(gè)網(wǎng)絡(luò)用戶數(shù)據(jù)的獲取比較容易。然而，跨社交網(wǎng)絡(luò)平臺(tái)用戶對(duì)齊的研究需要獲取不同網(wǎng)絡(luò)之間相同用戶的資料（進(jìn)行數(shù)據(jù)標(biāo)注），加之社交網(wǎng)絡(luò)規(guī)模龐大、平臺(tái)隱私保護(hù)等問(wèn)題，因此，大規(guī)模獲取跨社交網(wǎng)絡(luò)用戶數(shù)據(jù)仍然是比較困難的。與此同時(shí)，不同研究方法往往采用了不同的用戶特征，因此，能夠提供全部用戶特征的數(shù)據(jù)集的獲取難度很大。學(xué)術(shù)界目前還沒(méi)有廣泛認(rèn)可的用戶對(duì)齊基準(zhǔn)數(shù)據(jù)集。Shu 等[27]歸納了用戶對(duì)齊數(shù)據(jù)集的合成方法，并介紹了早期研究中采用的一些數(shù)據(jù)集。下面補(bǔ)充介紹一些近年來(lái)公布的可用數(shù)據(jù)集。

1）CLF/IONE[86]。CLF[87]提供了一對(duì)包括了用戶帖子和地理位置特征的社交網(wǎng)絡(luò)數(shù)據(jù)集(Foursquare-Twitter)，其中Foursquare 由5 392 個(gè)用戶及其之間的關(guān)系構(gòu)成，Twitter 包含了5 223 個(gè)用戶及其之間的關(guān)系。IONE[81]僅包含了該數(shù)據(jù)集的網(wǎng)絡(luò)結(jié)構(gòu)特征。

2）MEgo2Vec[88]。它提供了3 個(gè)學(xué)術(shù)合作網(wǎng)絡(luò)和2 個(gè)社交網(wǎng)絡(luò)數(shù)據(jù)集。其中，學(xué)術(shù)合作網(wǎng)絡(luò)由Aminer（學(xué)術(shù)搜索和挖掘服務(wù)）、LinkedIn（求職類(lèi)社交網(wǎng)絡(luò)）以及VideoLectures（學(xué)術(shù)在線視頻資料庫(kù)）組成，包含了用戶名、工作單位、教育背景和研究方向/技能等用戶屬性信息和用戶關(guān)系信息。社交網(wǎng)絡(luò)數(shù)據(jù)由Twitter 和MySpace 組成，包含了用戶名、帳戶名稱和地理位置等用戶屬性信息。

3）DPlink[89]。它提供了一組包括了用戶位置軌跡特征的移動(dòng)網(wǎng)絡(luò)數(shù)據(jù)集，由2 844 個(gè)手機(jī)用戶和1 761 個(gè)微博用戶在一周內(nèi)的位置信息組成（已做匿名化處理）。其中手機(jī)用戶包含325 215 個(gè)位置記錄，微博用戶包含49 651 個(gè)位置記錄。

4）MAUIL[90]。它提供了一組包含用戶名、地理位置和用戶帖子信息的社交網(wǎng)絡(luò)數(shù)據(jù)集（微博–豆瓣）和一組包含用戶名、工作單位和論文名稱的學(xué)術(shù)合作網(wǎng)絡(luò)數(shù)據(jù)集[91]（DBLP17-DBLP19）。其中，社交網(wǎng)絡(luò)數(shù)據(jù)集包含9 714 個(gè)微博用戶以及9 526 個(gè)豆瓣用戶；學(xué)術(shù)合作網(wǎng)絡(luò)從DBLP 數(shù)據(jù)庫(kù)（計(jì)算機(jī)科學(xué)期刊和論文集）2017 年和2019 年的2 個(gè)時(shí)間點(diǎn)的快照中分別提取了9 086 個(gè)作者和9 325 個(gè)作者。

4.2 評(píng)價(jià)指標(biāo)

評(píng)價(jià)指標(biāo)用于度量算法的準(zhǔn)確性和全面性。按照問(wèn)題設(shè)置的不同，用戶對(duì)齊任務(wù)的評(píng)價(jià)指標(biāo)可以分為面向分類(lèi)問(wèn)題和面向排名問(wèn)題的評(píng)價(jià)指標(biāo)。對(duì)于分類(lèi)問(wèn)題，一個(gè)實(shí)例包括正例（positive instance）和負(fù)例（negative instance）2 種情況，因此算法運(yùn)行結(jié)果會(huì)出現(xiàn)4 種情況：1）真正類(lèi)（true positive,TP），一個(gè)正例被預(yù)測(cè)為正類(lèi)；2）假正類(lèi)（false positive,FP），一個(gè)負(fù)例被預(yù)測(cè)為正類(lèi)；3）真負(fù)類(lèi)（true negative,TN），一個(gè)負(fù)例被預(yù)測(cè)為負(fù)類(lèi)；4）假負(fù)類(lèi)（false negative,FN），一個(gè)正例被預(yù)測(cè)為負(fù)類(lèi)。

分類(lèi)問(wèn)題常用的評(píng)價(jià)指標(biāo)有準(zhǔn)確率（Accuracy）、精度（Precision）、召回率（Recall）、F1值。

1）準(zhǔn)確率，指被算法正確分類(lèi)的實(shí)例數(shù)與總實(shí)例數(shù)的比例，即

2）精度，也稱為查準(zhǔn)率，指被算法劃分為正類(lèi)的實(shí)例中，真正類(lèi)的占比，即

3）召回率，也稱為查全率，指所有正例中，被算法劃分為真正類(lèi)的占比，即

4）F1值，也稱為F-measure 或f1-score，是綜合考慮精度和召回率的一個(gè)評(píng)價(jià)指標(biāo)，定義為精度和召回率的調(diào)和均值，即

對(duì)于排名問(wèn)題，算法的輸出為一個(gè)候選答案的排序，并將排名的第一位候選答案作為預(yù)測(cè)結(jié)果輸出。常用的面向排名模型的評(píng)分指標(biāo)有Hits@k、Precision@k、MRR 等。這些指標(biāo)的評(píng)分越高，表明算法性能越好。

1）Hits@k，即真實(shí)樣例在預(yù)測(cè)結(jié)果中排前k(k≥1)名的平均分?jǐn)?shù)，其計(jì)算公式為

式中：T 表示候選樣例集合；pos(·)表示真實(shí)樣例在所有候選樣例評(píng)分列表中的位置；Ipos(x)≤k(·)為一個(gè)指示函數(shù)，當(dāng)p os(x)≤k時(shí)返回1，否則返回0。

2）Precision@k，即真實(shí)樣例在預(yù)測(cè)結(jié)果中排前k(k≥1)名的加權(quán)平均分?jǐn)?shù)。與Hits@k 的不同之處在于，Precision@k 對(duì)排名靠前的樣例賦予了更高的權(quán)重，其計(jì)算公式為

其中，h it(·)表示真實(shí)樣例在前k個(gè)（top-k）候選樣例評(píng)分列表中的位置，當(dāng)真實(shí)樣例不在top-k列表中時(shí)，返回k+1。

3）MRR，是一個(gè)信息檢索領(lǐng)域常用的評(píng)價(jià)指標(biāo)，預(yù)測(cè)結(jié)果中第1 個(gè)匹配則分?jǐn)?shù)為1，第2 個(gè)匹配則分?jǐn)?shù)為1/2，以此類(lèi)推，第n個(gè)匹配則分?jǐn)?shù)為1/n。最后取所有結(jié)果的平均值，計(jì)算公式為

5 挑戰(zhàn)與未來(lái)的研究方向

跨平臺(tái)社交網(wǎng)絡(luò)的用戶對(duì)齊技術(shù)結(jié)合了數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和自然語(yǔ)言處理技術(shù)的一些方法和技術(shù)，是一個(gè)綜合性的研究方向。近年來(lái)，用戶對(duì)齊問(wèn)題受到越來(lái)越多研究者的關(guān)注，并在數(shù)據(jù)預(yù)處理、特征抽取、對(duì)齊模型等方向取得了大量研究成果，但仍然存在一些亟待解決的問(wèn)題和挑戰(zhàn)。

5.1 面臨的挑戰(zhàn)

5.1.1 數(shù)據(jù)獲取的挑戰(zhàn)

當(dāng)前社交網(wǎng)絡(luò)用戶對(duì)齊研究的一個(gè)主要問(wèn)題就是缺少可供研究者測(cè)試和評(píng)價(jià)算法的統(tǒng)一數(shù)據(jù)集。許多算法仍使用自己構(gòu)建的數(shù)據(jù)集進(jìn)行測(cè)試。為了獲取算法評(píng)價(jià)所需的數(shù)據(jù)，研究人員面臨以下挑戰(zhàn)。

1)用戶隱私。大部分社交網(wǎng)絡(luò)平臺(tái)都會(huì)注重對(duì)用戶隱私進(jìn)行保護(hù)，比較敏感的用戶信息，如電話號(hào)碼、Email 地址等往往不對(duì)外公開(kāi)[20]。研究者需要在不侵犯用戶個(gè)人隱私的情況下訪問(wèn)和使用用戶數(shù)據(jù)進(jìn)行數(shù)據(jù)集的構(gòu)建。

2)訪問(wèn)受限。一些在線社交網(wǎng)站提供API 來(lái)訪問(wèn)它們的網(wǎng)絡(luò)數(shù)據(jù)，但是它們通常只面向網(wǎng)站應(yīng)用開(kāi)發(fā)人員，并設(shè)置了訪問(wèn)許可限制、訪問(wèn)速率限制等（如微博），這使得大規(guī)模用戶數(shù)據(jù)的獲取難以實(shí)現(xiàn)。

5.1.2 數(shù)據(jù)質(zhì)量的挑戰(zhàn)

當(dāng)今的在線社交網(wǎng)絡(luò)數(shù)據(jù)龐大、嘈雜、不完整且高度非結(jié)構(gòu)化[11]，為跨社交網(wǎng)絡(luò)用戶對(duì)齊研究帶來(lái)巨大挑戰(zhàn)，主要表現(xiàn)在以下幾方面。

1)用戶屬性的不一致。社交網(wǎng)絡(luò)平臺(tái)一般允許用戶選擇性地公開(kāi)展示個(gè)人資料且對(duì)用戶填寫(xiě)資料的真實(shí)性不加關(guān)注[35]，而用戶自身出于安全考慮也可能不愿意公布真實(shí)的個(gè)人信息，這就造成了不同平臺(tái)之間用戶信息的不一致。此外，文本格式、數(shù)量單位、縮寫(xiě)形式、語(yǔ)種、錄入錯(cuò)誤等也會(huì)給匹配過(guò)程帶來(lái)巨大困難。

2)網(wǎng)絡(luò)結(jié)構(gòu)的不一致。不同社交網(wǎng)絡(luò)往往提供了具有差異化的在線服務(wù)，單個(gè)網(wǎng)絡(luò)只反映了用戶真實(shí)世界社交圈的一個(gè)子集。例如，一個(gè)用戶在豆瓣上關(guān)注了某位作者，但他們?cè)谖⒉┥蟿t不一定是朋友。這就使得一些依靠網(wǎng)絡(luò)結(jié)構(gòu)特征的用戶對(duì)齊方法難以取得良好的效果。

5.2 未來(lái)的研究方向

5.2.1 多語(yǔ)言社交網(wǎng)絡(luò)用戶對(duì)齊

隨著社交網(wǎng)絡(luò)在全球的迅速普及和發(fā)展，各種語(yǔ)言的社交網(wǎng)絡(luò)平臺(tái)紛紛建立，不同語(yǔ)言社交網(wǎng)絡(luò)平臺(tái)之間的信息傳播越發(fā)頻繁?？缯Z(yǔ)言社交網(wǎng)絡(luò)平臺(tái)的用戶對(duì)齊能促進(jìn)信息傳播、網(wǎng)絡(luò)融合及網(wǎng)絡(luò)安全等領(lǐng)域問(wèn)題的研究。目前跨語(yǔ)言的社交網(wǎng)絡(luò)用戶對(duì)齊研究還很少，一些跨語(yǔ)言知識(shí)庫(kù)實(shí)體對(duì)齊的研究[92?95]則可供借鑒。

5.2.2 多源社交網(wǎng)絡(luò)用戶對(duì)齊

當(dāng)前用戶對(duì)齊的研究大多集中在2 個(gè)網(wǎng)絡(luò)平臺(tái)之間的對(duì)齊，當(dāng)涉及2 個(gè)以上社交網(wǎng)絡(luò)的用戶對(duì)齊時(shí)，需要考慮多個(gè)網(wǎng)絡(luò)之間的相互依賴關(guān)系[19]以及對(duì)齊用戶在多個(gè)網(wǎng)絡(luò)之間的傳遞性[75]，這就為多源場(chǎng)景的用戶對(duì)齊研究帶來(lái)了新的挑戰(zhàn)和機(jī)遇。

5.2.3 用戶對(duì)齊與隱私保護(hù)

近年來(lái)，隱私保護(hù)受到越來(lái)越多的關(guān)注，歐盟通用數(shù)據(jù)保護(hù)條例（GDPR[96]）的出臺(tái)更是從法律層面對(duì)用戶數(shù)據(jù)的使用做出了嚴(yán)格規(guī)定。在不采用個(gè)人身份識(shí)別信息，特別是敏感身份信息，如完整的姓名、身份證號(hào)碼、手機(jī)號(hào)碼、電子郵箱地址等前提下選取適合的用戶特征來(lái)構(gòu)建用戶對(duì)齊模型是未來(lái)研究的一個(gè)重要方向[72]。

6 總結(jié)

本文對(duì)近年來(lái)跨社交網(wǎng)絡(luò)用戶對(duì)齊技術(shù)的主要成果進(jìn)行了綜述，在對(duì)用戶對(duì)齊相關(guān)概念、技術(shù)和方法深入研究的基礎(chǔ)上，歸納了一個(gè)用戶對(duì)齊問(wèn)題研究的框架，同時(shí)從數(shù)據(jù)預(yù)處理、候選集生成、標(biāo)記數(shù)據(jù)獲取、特征抽取和對(duì)齊方法5 方面進(jìn)行了概括，并重點(diǎn)對(duì)主流的用戶對(duì)齊方法進(jìn)行了詳細(xì)闡述，最后探討了當(dāng)前用戶對(duì)齊研究工作面臨的挑戰(zhàn)和未來(lái)的研究方向?？缟缃痪W(wǎng)絡(luò)用戶對(duì)齊的研究工作目前仍處于高速發(fā)展階段，雖然取得了一定的成果，但仍有大量的問(wèn)題亟待解決。隨著社交網(wǎng)絡(luò)平臺(tái)的不斷發(fā)展以及網(wǎng)絡(luò)數(shù)據(jù)規(guī)模的不斷增大，未來(lái)將會(huì)有更多的研究方法和成果涌現(xiàn)出來(lái)，推動(dòng)社交媒體研究不斷向前發(fā)展。