基于用戶簽到的跨社交網(wǎng)絡(luò)用戶匹配

戴 軍，馬 強(qiáng)

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

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

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

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

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

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

1 相關(guān)定義及數(shù)據(jù)預(yù)處理

1.1 相關(guān)定義

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

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

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

1.2 簽到數(shù)據(jù)預(yù)處理

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

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

2 簽到匹配算法

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

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

2.1 網(wǎng)格聚類和篩選

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

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

網(wǎng)格聚類算法的偽代碼如下所示。

通過聚類，進(jìn)一步得到用戶u1和u2的網(wǎng)格簇集合GC1={gc1,gc2,…,gcu},GC2={gc1,gc2,…,gcv}。其中g(shù)c為網(wǎng)格簇，u和v分別表示聚類之后用戶u1和u2的網(wǎng)格簇集合內(nèi)的簇?cái)?shù)量。

2.1.2 網(wǎng)格簇篩選

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

其中，ρi為ci的網(wǎng)格密度，|gc|為簇內(nèi)的網(wǎng)格總數(shù)。對(duì)于給定用戶對(duì)中的用戶，例如u1，遍歷GC1中的簇，若滿足：

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

網(wǎng)格聚類和篩選的目的在于對(duì)用戶坐標(biāo)進(jìn)行粗粒度化，減少計(jì)算復(fù)雜度，同時(shí)刪除潛在關(guān)聯(lián)性較弱的簽到，減少噪聲簽到的干擾。

2.2 時(shí)空特征提取

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

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

式中，m為S中簽到數(shù)，ti為第i次簽到時(shí)間。

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

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

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

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

2.3 多屬性相似度

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

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

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

式中，ρi為ci的網(wǎng)格密度，ρgc為網(wǎng)格ci所在網(wǎng)格簇的簇密度。

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

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

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

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

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

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

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

2.4 權(quán)重優(yōu)化

分別將正負(fù)例用戶對(duì)作為算法的輸入，計(jì)算出最終用戶對(duì)的匹配評(píng)分，該分值作為算法的預(yù)測(cè)值，基于批量梯度下降算法構(gòu)建預(yù)測(cè)函數(shù)：

其中，x為輸入樣本，損失函數(shù)為均方誤差函數(shù)，對(duì)損失函數(shù)在全體樣本上求和，構(gòu)建代價(jià)函數(shù)：

其中，m為樣本數(shù)，xi為第i對(duì)樣本，yi為xi的相似度標(biāo)簽值。根據(jù)預(yù)測(cè)結(jié)果，通過最小化代價(jià)函數(shù)迭代更新權(quán)重值。設(shè)定好迭代初值，迭代過程分為三個(gè)步驟：

步驟1根據(jù)式（18）計(jì)算批次數(shù)據(jù)的損失值。

步驟2更新權(quán)重：

其中η為學(xué)習(xí)率。式（19）的具體計(jì)算如下：

步驟3更新批次數(shù)據(jù)并重復(fù)步驟1、2，直到達(dá)到收斂條件后結(jié)束迭代，此時(shí)完成權(quán)重優(yōu)化。

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)集、正負(fù)例數(shù)據(jù)構(gòu)建

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

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

表1 源數(shù)據(jù)集概況Table 1 Source dataset overview

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

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

圖2 源數(shù)據(jù)集devnum分布Fig.2 devnum distribution of source dataset

圖3 源數(shù)據(jù)集devtime分布Fig.3 devtime distribution of source dataset

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

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

圖4 不同擾動(dòng)的devnum分布Fig.4 devnum distribution with different disturbances

圖5 不同擾動(dòng)的devtime分布Fig.5 devtime distribution with different disturbances

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

3.1.2 正負(fù)例數(shù)據(jù)構(gòu)建

對(duì)于n對(duì)已經(jīng)鏈接的用戶對(duì)，通過隨機(jī)拆分、重組形成負(fù)例。通過以上操作，構(gòu)建出n/2對(duì)負(fù)例用戶對(duì)Un，剩下的n/2對(duì)用戶對(duì)則作為正例用戶對(duì)Up。Up中的用戶對(duì)來自同一現(xiàn)實(shí)用戶，Un中的用戶對(duì)來自不同現(xiàn)實(shí)用戶。對(duì)于Up和Un中的用戶對(duì)，其匹配評(píng)分的標(biāo)簽值設(shè)定為1和0。三組數(shù)據(jù)集30%用作構(gòu)建實(shí)驗(yàn)數(shù)據(jù)集，60%用作訓(xùn)練集，剩下10%用作測(cè)試集。

3.2 測(cè)試指標(biāo)、參數(shù)設(shè)置

3.2.1 測(cè)試指標(biāo)

實(shí)驗(yàn)評(píng)估指標(biāo)采用經(jīng)典的分類模型評(píng)估指標(biāo)，分別為準(zhǔn)確率acc、召回率rec和F值f1，三種指標(biāo)的計(jì)算如下：

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

3.2.2 參數(shù)設(shè)置

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

圖6 權(quán)重迭代過程Fig.6 Weight iterative process

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

圖7 不同k下測(cè)試結(jié)果Fig.7 Test results with different k

圖8 不同st下測(cè)試結(jié)果Fig.8 Test results with different st

實(shí)驗(yàn)采用三種方式計(jì)算簽到錨點(diǎn)相似度，方式1和2分別以Δt=1 h和24 h計(jì)算簽到錨點(diǎn)相似度，方式3以方式1和2的平均值作為簽到錨點(diǎn)相似度，測(cè)試結(jié)果如表2所示。

表2 不同計(jì)算方式下的測(cè)試結(jié)果Table 2 Test results under different calculation methods

根據(jù)測(cè)試結(jié)果，選定k=9,st=0.5，采用方式3計(jì)算簽到錨點(diǎn)相似度。

3.3 算法對(duì)比實(shí)驗(yàn)

在算法對(duì)比實(shí)驗(yàn)中，選擇了同類型中較為代表性的對(duì)比算法UIDwST[8]和CDTraj2vec[13]作為基準(zhǔn)算法。分別在實(shí)驗(yàn)數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行對(duì)比測(cè)試。

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

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

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

對(duì)比測(cè)試及分析：算法的對(duì)比測(cè)試在分別在三組具有不同擾動(dòng)等級(jí)的實(shí)驗(yàn)數(shù)據(jù)集和三組真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。各擾動(dòng)等級(jí)的測(cè)試結(jié)果如圖9至11所示。

圖9 不同擾動(dòng)下的準(zhǔn)確率accFig.9 acc with different disturbances

圖10 不同擾動(dòng)下召回率recFig.10 rec with different disturbances

圖11 不同擾動(dòng)下F值f1Fig.11 f1 with different disturbances

在F-G、F-T以及G-T三組真實(shí)數(shù)據(jù)集下的測(cè)試結(jié)果如圖12至14所示。

圖12 不同數(shù)據(jù)集下準(zhǔn)確率accFig.12 acc with different datasets

圖13 不同數(shù)據(jù)集下召回率recFig.13 rec with different datasets

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

圖14 不同數(shù)據(jù)集下F值f1Fig.14 f1 with different datasets

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

4 結(jié)束語

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