戴 軍，馬 強

西南科技大學 信息工程學院，四川 綿陽621010

在信息化的時代背景下，現(xiàn)代社交網絡的用戶規(guī)模已經達到幾十億水平，同一個用戶會在多個社交平臺分享信息并留下個人獨特的“數字印記”[1-2]。從不同社交平臺中識別出相同用戶具有重要意義，這將對許多應用產生重要的實際影響，例如由用戶識別衍生的服務：好友推薦、社區(qū)檢測、惡意用戶識別和在線精確營銷以及為研究人員提供更完整的用戶數據等。

現(xiàn)有研究技術主要分為兩類，這一類方案通常是在時空維度上統(tǒng)計簽到數據，分析用戶簽到位置[3-5]和簽到時間的共現(xiàn)頻率，計算簽到記錄在KL（Kullback-Leibler）散度或者其他分布下的相似性，例如利用核密度估計方法，或者分析關鍵簽到節(jié)點計算相似度。文獻[6]采用卷積神經網絡標記簽到軌跡匹配節(jié)點，基于坐標的最短距離，分別采用隨機選擇、排列程度和PageRank算法來計算軌跡相似度。類似的還有文獻[7]提出ULMP（user account linkage across multiple platforms）算法，將簽到表示成網格單元序列和間隔的概率分布，并提出GTkNN（the top-knearest neighborsof a given user account based on G and T）算法計算概率分布的重合度，基于KL散度定義網格散度GKL和間隔散度IKL計算用戶相似度。文獻[8]提出了UIDwST（user identification method with spatio-temporal awareness）算法，基于TF-IDF分配簽到記錄權重，并提取出沖突簽到，綜合正向相似評分和負向懲罰評分計算用戶相似度。文獻[9]構建用戶軌跡分布頻率Top-N區(qū)域，將問題轉換成角余弦、偏差概率和加權Jaccard三種方法下的區(qū)域集相似性計算。文獻[10]考慮簽到的時空信息，用三部圖表示用戶軌跡，通過圖的最優(yōu)劃分得到最優(yōu)的匹配方案。

另一類方法對用戶簽到向量化或文本化，通過向量相似度或文本的主題分布計算簽到相似度。向量化方法首先對用戶簽到序列化，利用Doc2vec[11]模型對序列進行向量轉換，最后采用余弦相似度等方法計算相似度。文本化方法通過位置的語義詞文本化用戶軌跡，利用LDA[12]（latent Dirichlet allocation）等模型獲取用戶的主題分布，最后計算主題的相似度表示用戶相似度。文獻[13-14]將用戶簽到軌跡轉化成網格序列，從時間、空間和時空三個維度劃分用戶軌跡，構建三種不同的訓練樣本，利用Doc2vec模型得到不同的軌跡向量，拼接構成完整的軌跡向量，用戶相似度由軌跡向量之間加權的余弦相似度表示。文獻[15]構建了主題模型，將位置轉成語義詞，以此將用戶軌跡文本化。該方案利用LDA模型獲取用戶的主題分布，最后采用KL散度計算用戶相似性。隨著深度學習技術的發(fā)展，諸如卷積神經網絡CNN[16]、圖卷積網絡GCN[17]和圖神經網絡GNN[18]等模型逐漸應用到跨社交網絡用戶匹配中。文獻[19]利用異構圖表示用戶信息，使用多個注意力層匯總這些信息并用多層感知器預測鏈接用戶身份。文獻[20]利用簽到點構建簽到圖，在簽到圖的基礎上使用圖神經網絡學習簽到圖中的節(jié)點嵌入，利用循環(huán)神經網絡構建軌跡序列的向量對軌跡進行用戶分類。

目前的研究方案雖然已經取得不少的成果，但仍然面臨一定挑戰(zhàn)：（1）用戶多源數據的獲取和整合困難，由于隱私問題，難以獲取用戶的多源數據，其次不同社交平臺的用戶數據字段不齊，整合困難。（2）難以維持在真實社交網絡簽到數據稀疏性和偏差性下的有效性，用戶在不同社交平臺的簽到很難對稱，簽到數量和簽到時間具有較大的偏差，這種偏差性使目前方案很難達到良好的效果。（3）對數據質量依賴程度高，軌跡的語義提取需要良好的數據支撐，在數據稀疏或者失衡的情況下難以提取有效的信息。為了解決對用戶多源數據的依賴問題，鑒于用戶簽到具有高真實性和難模仿性，本文采用用戶簽到數據，提出一種基于用戶簽到的跨社交網絡用戶匹配算法UMbUC（user matcing cross-social network based on user check-in）。利用網格映射將用戶簽到轉換成網格表示，通過聚類策略獲得用于提取特征的網格數據。本算法從簽到數據中提取時空多屬性特征來克服單一特征的局限性，綜合多屬性相似度構建匹配模型并采用梯度下降算法優(yōu)化多屬性相似度的權重，綜合計算最終用戶匹配評分，確保算法在面對簽到數據偏差的情況下，能夠有效地度量相似性。

本文的主要貢獻：（1）本文通過網格映射和聚類策略，在減少計算復雜度的同時過濾掉內在關聯(lián)性弱的用戶簽到數據，以便于特征提取；（2）本文從時空維度抽取多種用戶特征，設計多屬性相似度以克服單一特征的局限性；（3）本文構建一種多屬性相似度匹配模型，并在多組實驗數據集和真實數據集上對所提算法進行測試，驗證了所提算法的有效性。

1 相關定義及數據預處理

1.1 相關定義

定義1（用戶簽到集）用戶在社交平臺中的時空數據稱為用戶簽到s(lon,lat,t),lon和lat為簽到的經緯度，t為簽到時間。用戶在社交平臺的所有簽到構成簽到集S={s1,s2,…,sm},m為簽到數。

定義2（用戶匹配）用戶u1和u2分別來自不同社交平臺，他們的簽到集分別為S1和S2。如果u1和u2來自同一個現(xiàn)實用戶，那么S1和S2相互匹配。

本文的目的是準確識別出待匹配用戶集中的匹配用戶，挖掘來自同一現(xiàn)實用戶的社交用戶。

1.2 簽到數據預處理

用戶簽到集是多個空間坐標按時序構成的集合，這些坐標反映用戶在地理位置的活動信息。由于用戶對不同社交平臺的訪問頻率不同，用戶在不同社交平臺的簽到數量差異巨大，這種偏差對用戶匹配造成負面影響。另外，直接計算坐標數據會出現(xiàn)計算開銷大和噪聲坐標影響匹配精準度的問題，需要對簽到進行預處理。首先從用戶簽到集中獲取經度的最小值lonmin、最大值lonmax以及緯度的最小值latmin、最大值latmax，然后將四個參數所圍住的空間對經緯度進行k等距劃分，形成k2個網格，網格表示為c(x,y,ρ),x和y分別為網格的經度和緯度序號，ρ為網格密度，大小等于落在該網格內的簽到數量。網格序號的計算如下：

其中，f為向下取整函數，k為網格劃分密度系數，lon和lat分別為簽到位置的經緯度。通過將簽到映射到網格，得到用戶u1和u2簽到集的網格集合表示C1={c1,c2,…,ck}和C2={c1,c2,…,cp}。其中k和p分別表示用戶u1和u2進行坐標映射之后的網格數量。

2 簽到匹配算法

簽到匹配算法首先利用網格映射將簽到轉為網格表示，然后通過網格聚類算法聚類關聯(lián)性強的網格形成網格簇并利用網格簇篩選算法進一步過濾聚類的結果，獲取潛在關聯(lián)性強的網格簇，刪除掉關聯(lián)性弱的噪聲數據。接下來從用戶的網格數據和原始簽到數據中提取時空特征，構建多屬性相似度，通過權重優(yōu)化方法對不同相似度賦權，最后綜合計算出用戶匹配評分。算法的整體流程如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flowchart

2.1 網格聚類和篩選

2.1.1 網格聚類定義3(c1?c2)對于c1(x1,y1,ρ1)和c2(x2,y2,ρ2)，若滿足| |x1-x2≤1且| |y1-y2≤1，則c1?c2=1，否 則c1?c2=0。

定義4(c1?C)給定網格c1(x1,y1,ρ1)和網格集合C={c1,c2,…,cm},若滿足c1?ci=1,?ci∈C,那么c1?C=1,否則為0。

網格聚類算法的偽代碼如下所示。

通過聚類，進一步得到用戶u1和u2的網格簇集合GC1={gc1,gc2,…,gcu},GC2={gc1,gc2,…,gcv}。其中gc為網格簇，u和v分別表示聚類之后用戶u1和u2的網格簇集合內的簇數量。

2.1.2 網格簇篩選

給定用戶對(u1,u2)，假設它們的網格簇集合分別為GC1和GC2，從它們的網格簇集合中篩選獲得合格網格簇。對于網格簇集合GC中某個簇gc，簇密度用ρgc表示：

其中，ρi為ci的網格密度，|gc|為簇內的網格總數。對于給定用戶對中的用戶，例如u1，遍歷GC1中的簇，若滿足：

其中，gci∈GC1,ci∈gci，則保留gci，否則將其從GC中刪除，對u2的網格簇篩選同理。網格簇篩選算法的偽代碼如下所示。

網格聚類和篩選的目的在于對用戶坐標進行粗粒度化，減少計算復雜度，同時刪除潛在關聯(lián)性較弱的簽到，減少噪聲簽到的干擾。

2.2 時空特征提取

簽到記錄可以反映個人簽到習慣，不同用戶簽到平穩(wěn)程度不同，簽到平穩(wěn)度高的用戶表現(xiàn)為規(guī)律性簽到，比如每天簽到一次，平穩(wěn)度低的用戶則簽到規(guī)律性較弱。

定義5（簽到平穩(wěn)度cs）給定簽到集S,cs計算如下：

式中，m為S中簽到數，ti為第i次簽到時間。

用戶的簽到記錄也能反映出用戶偏向在某些特定的時間段或隨機簽到，通俗說即某些用戶習慣在上午更新簽到，而有些用戶則選擇在傍晚，這些習慣能夠反映用戶對簽到時間的偏好。

定義6（簽到偏好時間cpt）將每天按3小時等長劃分成8個時間段Δt1到Δt8，選出用戶簽到數最高的3個時間段，構成用戶簽到偏好時間cpt(Δti,Δtj,Δtk)。

同一現(xiàn)實用戶在不同社交平臺的簽到記錄不會完全一致，通過時間特征的約束，在用戶簽到中尋找滿足特定條件的簽到，可以有效地判斷用戶是否匹配。

定義7（簽到錨點集SA）分別來自簽到集S1和S2的簽到(si,sj)，若它們的簽到時間ti、tj滿足：則稱這樣的簽到對為簽到錨點，式中Δt為時間間隔閾值。用戶對的所有簽到錨點構成簽到錨點集SA。

2.3 多屬性相似度

定義8（網格距離函數）給定兩個網格c1(x1,y1,ρ1)、c2(x2,y2,ρ2)，定義網格距離函數衡量兩個網格在空間上的接近程度，計算如下式：

定義9（網格簇距離）給定網格c0(x0,y0,ρ0)和網格簇gc={c1,c2,…,cm}，定義網格簇距離函數衡量網格和網格簇在空間上的接近程度。計算如下：

定義10（網格相似度）令用戶u1和u2的合格網格簇集合為QGC1和QGC2。選擇有較少網格數的合格網格簇集合，假設QGC1的網格數較少且大小為m。構建m維偏差向量：其中分量di的計算如下：其中ci∈QGC1，用戶網格相似度simc：

式中，ρi為ci的網格密度，ρgc為網格ci所在網格簇的簇密度。

定義11（平穩(wěn)度相似度）令用戶u1和u2的簽到平穩(wěn)度為cs1和cs2，簽到平穩(wěn)度相似度simcs：

定義12（偏好相似度）令用戶u1和u2的熱門簽到時間為cpt1和cpt2，簽到偏好相似度simcpt：

其中，ni、nj分別表示Δti和Δtj內的簽到數，N和M為用戶u1和u2的簽到總數。| |i-j表示Δti和Δtj之間相差的間隔數。例如，Δt1和Δt8相差一個間隔，即|1-8|=1。

定義13（錨點相似度）令用戶u1和u2的簽到錨點集合為SA，簽到錨點相似度simsa：

其中，λ為容忍系數，由用戶u1和u2相鄰簽到距離與時間比值的最大值確定：

其中，si和si+1為用戶u1的相鄰簽到，sj和sj+1為用戶u2的相鄰簽到。

綜合上述定義的多屬性相似度，用戶匹配評分：

2.4 權重優(yōu)化

分別將正負例用戶對作為算法的輸入，計算出最終用戶對的匹配評分，該分值作為算法的預測值，基于批量梯度下降算法構建預測函數：

其中，x為輸入樣本，損失函數為均方誤差函數，對損失函數在全體樣本上求和，構建代價函數：

其中，m為樣本數，xi為第i對樣本，yi為xi的相似度標簽值。根據預測結果，通過最小化代價函數迭代更新權重值。設定好迭代初值，迭代過程分為三個步驟：

步驟1根據式（18）計算批次數據的損失值。

步驟2更新權重：

其中η為學習率。式（19）的具體計算如下：

步驟3更新批次數據并重復步驟1、2，直到達到收斂條件后結束迭代，此時完成權重優(yōu)化。

3 實驗分析

3.1 數據集、正負例數據構建

3.1.1 數據集

實驗采用的數據集來自斯坦福大學的社交網絡分析網站。數據集中同一用戶的簽到關聯(lián)相同用戶ID，借此挖掘來自同一現(xiàn)實用戶的多源簽到數據。實驗采用Facebook-Gplus、Facebook-Twitter以及Gplus-Twitter三組數據集，分別簡稱為F-G、F-T以及G-T。真實的用戶簽到數據是呈現(xiàn)多樣性，為了確保實驗的客觀性和真實性，不篩選用戶數據，保留用戶的原始數據。三組數據集的簽到記錄統(tǒng)計如表1。

表1 源數據集概況Table 1 Source dataset overview

用戶簽到失衡性表現(xiàn)在兩點上：（1）簽到數量偏差；（2）簽到時間偏差。用戶在常用的社交平臺具有多數簽到數據，不常用的社交平臺簽到數量較少。用戶簽到很難均勻歸屬不同平臺，同時，用戶在不同社交平臺的簽到時間區(qū)間，能夠相交的區(qū)間僅占小部分。不同社交平臺中的簽到時間會呈現(xiàn)不對稱的特性。定義簽到數量偏差devnum和時間偏差devtime計算如下：

式中，nA、nB分別表示用戶在不同社交平臺的簽到數量。nM表示用戶在擁有多數簽到的社交平臺的所有簽到中，簽到的時間和其他社交平臺所有簽到的時間都相差在一周以上的簽到數量。實驗將簽到數量和時間偏差分成10個區(qū)間，統(tǒng)計不同偏差區(qū)間的用戶比例分布以定性衡量總體偏差程度分布結果如圖2、3所示。

圖2 源數據集devnum分布Fig.2 devnum distribution of source dataset

圖3 源數據集devtime分布Fig.3 devtime distribution of source dataset

圖2、3中橫軸表示不同社交平臺的簽到數量和時間偏差，縱軸表示不同偏差區(qū)間用戶占全體用戶的比例。從統(tǒng)計結果來看，三組數據集整體偏差的差別較小，在多數偏差區(qū)間中F-T數據集介于F-G數據集和G-T數據集之間。通過統(tǒng)計結果可知，真實用戶在多社交網絡平臺的簽到數據的失衡性是客觀存在的，約60%以上的用戶，無論是簽到數量還是簽到時間，偏差都在50%以上，且有30%左右的用戶的簽到數據呈現(xiàn)80%以上的偏差性。

為了驗證算法對這種客觀存在的數據失衡的魯棒性，分別從三組真實數據集中隨機選擇30%的數據，將其合并，構成實驗數據集。通過隨機刪除偏差較小的簽到數據的方法，對實驗數據集執(zhí)行不同等級的擾動操作，進一步擴大偏差，擾動等級越高，隨機刪除的簽到數量越多。不同擾動等價下的結果如圖4、5所示。

圖4 不同擾動的devnum分布Fig.4 devnum distribution with different disturbances

圖5 不同擾動的devtime分布Fig.5 devtime distribution with different disturbances

從圖4、5的結果可以看出，隨著擾動等級增加，最終多數用戶的偏差從10%～20%區(qū)間上升為50%～60%，總體偏差逐漸增大。需要指出的是處于60%至100%偏差區(qū)間的用戶對數量占比在不同擾動等級下幾乎保持一致，因為數據擾動只針對偏差較小的用戶對，因此它們的分布不受影響。

3.1.2 正負例數據構建

對于n對已經鏈接的用戶對，通過隨機拆分、重組形成負例。通過以上操作，構建出n/2對負例用戶對Un，剩下的n/2對用戶對則作為正例用戶對Up。Up中的用戶對來自同一現(xiàn)實用戶，Un中的用戶對來自不同現(xiàn)實用戶。對于Up和Un中的用戶對，其匹配評分的標簽值設定為1和0。三組數據集30%用作構建實驗數據集，60%用作訓練集，剩下10%用作測試集。

3.2 測試指標、參數設置

3.2.1 測試指標

實驗評估指標采用經典的分類模型評估指標，分別為準確率acc、召回率rec和F值f1，三種指標的計算如下：

其中，TP為正類判定為正類的數量，F(xiàn)P為負類判定為正類的數量，TN為負類判定為負類的數量，F(xiàn)N為正類判定為負類的數量。

3.2.2 參數設置

多屬性相似度權重參數的優(yōu)化采用梯度下降算法，迭代初值設定為ω=(0.3,0.4,0.2)，學習率η=0.02，每個訓練批次的樣本量為128，迭代過程如圖6所示。

圖6 權重迭代過程Fig.6 Weight iterative process

在訓練的初始階段，權重α、β、γ三個參數都趨于上升趨勢，在經過大約45輪訓練之后，權重β上升趨勢逐漸減小。權重α、γ上升趨勢快速趨于零，并在此后開始呈現(xiàn)下降趨勢，且下降趨勢逐漸減小，直至迭代輪數超過700之后，三個權重參數趨于收斂。此時權重參數α=0.584,β=0.362,γ=0.324。其他參數包括：網格劃分密度k、相似度評分閾值設定為st、簽到錨點檢測中預設的時間閾值Δt，針對部分用戶簽到數據稀疏的問題，例如某些用戶只有一個簽到數據，實驗中多屬性相似度缺省值設定為0.5。不同參數的實驗結果均為在三組真實數據集下測試的平均值，測試結果如圖7、8所示。

圖7 不同k下測試結果Fig.7 Test results with different k

圖8 不同st下測試結果Fig.8 Test results with different st

實驗采用三種方式計算簽到錨點相似度，方式1和2分別以Δt=1 h和24 h計算簽到錨點相似度，方式3以方式1和2的平均值作為簽到錨點相似度，測試結果如表2所示。

表2 不同計算方式下的測試結果Table 2 Test results under different calculation methods

根據測試結果，選定k=9,st=0.5，采用方式3計算簽到錨點相似度。

3.3 算法對比實驗

在算法對比實驗中，選擇了同類型中較為代表性的對比算法UIDwST[8]和CDTraj2vec[13]作為基準算法。分別在實驗數據集和真實數據集上進行對比測試。

復雜度分析：假設總簽到數據量為N，每對用戶簽到數據量平均為2n。UIDwST核心算法部分采用核密度估計，基于TF-IDF加權策略求解相似度得分和懲罰系數，計算復雜度分別為O(n2)和O(n3+nN)。CDTraj2vec利用Paragraph2vec模型生成軌跡向量，基于哈夫曼編碼的Hierarchical Softmax過濾部分詞，計算復雜度為O(Nlogn)。本文算法UMbGC在網格聚類和多屬性相似度提取的計算復雜度分別為O(n2)和O(n2+4n)。各算法在訓練樣本和三組測試樣本上測試消耗的時間如表3所示。

表3 不同算法時間消耗Table 3 Time consumption of different algorithms單位：min

由于CDTraj2vec構建三種簽到網格序列以提高模型的泛化能力，在一定程度上延長了模型的訓練時間。UIDwST雖然不需要訓練，但是該算法直接對原始簽到數據進行計算，并且采用tf-idf加權策略，進一步增加了計算成本，是該算法的預測時間最長。UmbGC通過網格映射和聚類，避免直接對簽到數據計算，有效降低了計算開銷。

對比測試及分析：算法的對比測試在分別在三組具有不同擾動等級的實驗數據集和三組真實數據集上進行實驗。各擾動等級的測試結果如圖9至11所示。

圖9 不同擾動下的準確率accFig.9 acc with different disturbances

圖10 不同擾動下召回率recFig.10 rec with different disturbances

圖11 不同擾動下F值f1Fig.11 f1 with different disturbances

在F-G、F-T以及G-T三組真實數據集下的測試結果如圖12至14所示。

圖12 不同數據集下準確率accFig.12 acc with different datasets

圖13 不同數據集下召回率recFig.13 rec with different datasets

實驗數據集測試結果表明：隨著擾動增強，CDTraj2vec和UIDwST的準確率分別下降14.9%和4.75%，召回率分別下降22.3%和3.95%，F(xiàn)值分別下降16%和3.6%，UmbGC的準確率下降約0.2%，召回率下降約0.5%，F(xiàn)值下降約0.3%。上述測試結果表明，本文算法UmbGC針對數據擾動具有較強的魯棒性，這是由于UmbGC從時空維度構建多種特征，通過多屬性相似度的耦合，克服單一特征的局限性，進而降低數據失衡性的影響。實驗結果驗證了本算法在數據失衡下的有效性。

圖14 不同數據集下F值f1Fig.14 f1 with different datasets

真實數據集的測試結果表明：UMbGC相較于對比算法CDTraj2vec和UIDwST，在三組數據集上均獲得最佳的準確率、召回率以及F值。以上指標在G-T這組數據集下差距最大。通過圖2、3統(tǒng)計的數據偏差分布結果可知，該組數據集高偏差用戶所占比例相對最高，整體用戶簽到數據偏差性更強，因此在該組數據集下UMbGC、UIDwST和CDTraj2vec差異性更能體現(xiàn)。分析原因是真實多源簽到數據客觀存在的失衡性對算法的判定產生了消極作用。該組數據集中用戶簽到的偏差性較強，UMbGC通過網格映射、聚類、篩選策略針對簽到中的關鍵節(jié)點，忽略相關性弱的噪聲節(jié)點，能夠有效提高特征提取的有效性，其次通過構建多屬性相似度，從時空多角度進行相似性度量，進一步增強算法對數據偏差的魯棒性。UIDwST和CDTraj2vec無法在失衡數據上很好地工作，部分失衡性較強的正例被誤判定為負例，導致召回率和F值降低，且用戶簽到數據偏失衡越強，下降趨勢越明顯。從多組實驗結果來看，UMbGC對于數據失衡的魯棒性和匹配性能是優(yōu)于對比算法的。

4 結束語

本文針對現(xiàn)有基于簽到的社交網絡用戶匹配算法在面對真實多源社交網絡簽到數據的不平衡性的情況下，匹配精度下降的缺點，提出一種新的基于簽到的跨社交網絡用戶匹配算法UMbGC。利用網格聚類對用戶簽到進行聚類和篩選，獲得空間關聯(lián)性強的簽到坐標。從簽到數據中提取空間、時間多方面用戶特征信息，構建多屬性相似度用戶匹配模型。采用梯度下降算法對不同屬性相似度的權重進行優(yōu)化，綜合多屬性相似度計算最終用戶匹配評分。最后分別在多組實驗數據集和真實數據集上進行了測試，實驗結果驗證了本算法在簽到數據失衡下的有效性。由于用戶簽到坐標分布是不均勻的，使用單一維度的公共區(qū)域進行用戶坐標的網格聚類可能會導致網格稀疏問題，因此本文算法后續(xù)改進可以考慮從多維度網格聚類出發(fā)，從不同層次的公共區(qū)域提取網格信息，最大化用戶特征提取，克服單一維度的網格聚類的局限性。