基于交叉配血的多賬戶識別模型研究

韓亞全+曹春萍

摘要摘要：對用戶多賬戶檢測識別是信息整合研究目標(biāo)之一。針對目前用戶識別技術(shù)普遍存在的準(zhǔn)確率低和局域性問題，提出了基于交叉配血的多賬戶識別模型。該模型要求根據(jù)用戶行為相似度和語義相似度繪制出多個賬戶的關(guān)系圖，然后利用交叉配血原則來平衡語義和行為，在配置信息的協(xié)同下，對語義行為模型進行一致性識別。要求用戶多個賬戶互相匹配以提高識別率，通過交叉匹配降低假種子賬戶對結(jié)果的影響。實驗證明該算法大大提高了識別準(zhǔn)確率。

關(guān)鍵詞關(guān)鍵詞：交叉配血；賬戶識別；語義分析；用戶相似度

DOIDOI：10.11907/rjdk.162322

中圖分類號：TP302文獻標(biāo)識碼：A文章編號文章編號：16727800（2017）001000105

0引言

互聯(lián)網(wǎng)中存在大量重復(fù)的用戶身份信息[1]，以國外知名網(wǎng)站Twitter、Facebook為例，約有47%的用戶擁有超過一個應(yīng)用賬戶，整合這些重復(fù)用戶信息很有意義，對網(wǎng)絡(luò)應(yīng)用中的多賬戶進行判定[2]并整合，能夠幫助網(wǎng)絡(luò)服務(wù)提供商全面了解用戶，從而提供更好的個性化服務(wù)。從網(wǎng)絡(luò)安全角度鑒別用戶多賬戶，能夠協(xié)助網(wǎng)絡(luò)安全管理者發(fā)現(xiàn)虛假或不法身份[3]，保護用戶權(quán)益。

為了整合用戶信息，首先需要對用戶進行身份識別、判定。影響網(wǎng)絡(luò)用戶身份識別的特征值主要有：配置信息、好友圈、行為和語義[4]信息等。目前識別方法主要有兩種：①基于用戶檔案判定[5]的用戶識別。該方法針對賬戶公有屬性進行判定，然而賬戶公有屬性相似度很大，導(dǎo)致準(zhǔn)確率極其低下；②基于好友關(guān)系的多賬戶識別。該方案依據(jù)賬戶公共好友進行識別，但是多個賬戶并不擁有共同的好友圈，這嚴(yán)重影響識別準(zhǔn)確度。

目前用戶識別檢測處于快速發(fā)展階段，許多學(xué)者對傳統(tǒng)用戶識別進行了改進，例如周松松等[6]提出了基于URL的相似度會話識別方法，通過對URL的處理進行用戶檢測；業(yè)寧等提出一種Web用戶行為聚類算法，通過對Web日志的處理，提取用戶的訪問行為。這些基于用戶日志和URL的方法，在一定程度上改善了識別的準(zhǔn)確率，但同時也引入噪聲，沒有充分利用用戶行為，忽視了用戶的語義。

為了提高用戶多賬戶識別準(zhǔn)確率，本文提出了基于交叉配血原則的用戶身份同一性[7]判定方法。通過對行為和語義進行交叉匹配，生成準(zhǔn)確的種子用戶，進而進行綜合判定識別。

交叉配血最初來源于生物學(xué)，其原理是將獻血人的紅細(xì)胞和血清分別與受血人的血清和紅細(xì)胞混合，若無凝集反應(yīng)說明兩血型相合，反之不相匹配。依據(jù)上述方法可以解決臟血問題，從而保證安全輸血。

交叉配血識別模型設(shè)計：①將各個賬戶的行為看作紅細(xì)胞、語義看作血清，分別與其它賬戶進行交叉匹配；②把匹配度最高的賬戶作為種子用戶進行下一輪測試，從而識別出用戶所有賬戶。

在交叉匹配前需要對賬戶的行為、語義進行處理，識別處理過程如下：①采用矩陣聚類算法對用戶行為相似度進行度量；②采用GVSM 的語義相似度算法對用戶語義進行分析；③構(gòu)造行為-語義加權(quán)無向圖；④結(jié)合用戶的配置相似度并按照交叉配血原則對用戶行為-語義進行識別，從而得到準(zhǔn)確的用戶組。

1基于交叉配血算法的行為-語義識別

1.1多賬戶識別模型

定義1：多賬戶識別模型： 通過用戶行為和語義相似度構(gòu)建交叉配血的多賬戶識別模型G=，其中V表示賬戶，E表示兩個賬戶相連，Weight表示兩個賬戶語義、行為的相似度。

根據(jù)行為、語義相似度構(gòu)建無向圖，行為、語義都存在噪聲干擾，為防止噪聲影響實驗結(jié)果，經(jīng)過大量實驗分析，本文采取9%為行為噪聲，14%為語義噪聲。根據(jù)選定噪聲閾值構(gòu)建加權(quán)無向圖，大于閾值的為有效信息，通過計算多個頂點相似距離從而得到賬戶相似度。

其中，Wij表示用戶i和用戶j的相似度，作為權(quán)值參與相似計算。

1.2用戶行為相似度識別分析

用戶的行為特征主要表現(xiàn)在時間和空間上，時間特征包含每次瀏覽頁面的時間及有向路徑[8]的瀏覽時間，空間特征包含頁面的瀏覽順序和點擊信息等瀏覽行為。本文主要根據(jù)賬戶的訪問日志和登錄日志提取時間和空間特征值，通過對兩個特征值進行聚類分析，得出各賬戶之間的行為相似度，如表1所示。

行為識別步驟：①通過用戶訪問模式分析得到賬戶時間特征值；②基于用戶瀏覽相似度矩陣的聚類算法得出用戶行為相似度。

用戶訪問模式[9]的訪問路徑包含超鏈接，用戶點擊鏈接訪問網(wǎng)站。如果不同賬戶有相同的訪問順序，就意味著用戶訪問行為有一定的相似性。這是一個抽象的用戶訪問，可以被視為知識一致性頁面，通過路徑聚類[10]找到用戶的訪問行為，每個集合代表一類用戶訪問模式的相似路徑。通過處理Web用戶找到訪問模式和用戶行為偏好，用戶訪問行為偏好不僅反映在瀏覽網(wǎng)頁的路徑上，而且反映在用戶訪問Web頁面的時間上。因此，通過挖掘用戶的訪問時間，可以分析多個賬戶的行為時間特征，得到各賬戶的時間特征值。

1.2.2基于用戶瀏覽相似度矩陣的聚類算法

基于用戶瀏覽相似度矩陣的聚類算法中，L=用來表達(dá)Web服務(wù)器的日志，uid代表網(wǎng)絡(luò)用戶ID，ip代表用戶IP，url表示用戶請求的url地址，time是相應(yīng)地址的瀏覽時間。通過對日志的處理，可以分析出用戶在一段時間內(nèi)的瀏覽行為。該算法降低了對日志文件、會話識別和事務(wù)標(biāo)識的要求。

定義1：用戶瀏覽行為：用于記錄用戶瀏覽頁面留下的信息，如公式（1）所示：

M=（1）

其中，lm_userid=UserIDm，lm∈L，lm_ip=IPm，n≥1，hits代表了用戶瀏覽lm_userid頁面的次數(shù)。

定義2：網(wǎng)站模型G： 網(wǎng)站的拓?fù)浣Y(jié)構(gòu)可以看作是一個有向圖，如公式（2）所示：

G=（2）

定義3：urlID-UserID關(guān)聯(lián)矩陣Mm×n：根據(jù)有向圖G的節(jié)點集N可以得到所有網(wǎng)站的url，從相應(yīng)的節(jié)點屬性設(shè)置Np可以獲得每個節(jié)點的標(biāo)識和相應(yīng)值的訪問，可以創(chuàng)建urlID-UserID的相關(guān)矩陣Mm×n，如式（3）所示。

Sij是用戶訪問頁面的數(shù)量，i是用戶j訪問頁面的時間，每一列向量M[ ，j]表示用戶j訪問該網(wǎng)站的所有頁面；每一行向量M[i，]意味著訪問頁面i的所有用戶。行向量反映了用戶的類型，描述了用戶個性化的訪問子圖，列向量代表網(wǎng)站結(jié)構(gòu)，包含用戶常見的訪問模式[11]。通過測量每一個行向量和列向量的相似性可以直接得到相似度。

Hij=0，表示用戶沒有訪問的頁面，Hij =1，表示用戶j訪問了i頁面，Hij =2，用戶j對i頁面非常感興趣，i是閾值（根據(jù)聚類情況而定）。

定義5：相似性sim（pi，pj）：假設(shè)pi和pj是兩個m維空間向量，pi=（ai1，…，aik …，aim），pj=（aj1，…，ajk …，ajm）， 1

其中，pi 和 pj 表示Nm×n 中第i和第j行向量，pi *pj是兩個向量的向量積，|pi|×|pj|是向量模的乘積。

1.2.3算法步驟

1.3用戶語義相似度識別

定義6：語義相似度：當(dāng)兩個元素（文字或者符號）具有某種特征時，則定義它們是相似的，可以用sim（x，y）（0≤sim（x，y）≤1）表示兩個元素x、y的相似度。

每個用戶都有自己的語言表達(dá)特點，使用獨特的敘述方式、頻用詞匯、斷句方式、標(biāo)點符號等；通過分析每個賬戶發(fā)表的評論、帖子、回復(fù)信息等，從而分析賬戶的語義相似度。本文采用的賬戶語義相似度計算流程如圖2所示。

圖2語義分析流程

采用基于GVSM 的語義相似度算法計算多個賬戶的語義相似度，通過構(gòu)建語義網(wǎng)計算兩個詞的關(guān)聯(lián)度，從而計算兩個詞的相似性。語義相關(guān)度 SR（Semantic Relatedness）表示兩個詞的相似性，采用語義網(wǎng)絡(luò)建設(shè)模式，將每種類型的邊賦予權(quán)值，權(quán)值越高說明兩個詞的關(guān)聯(lián)度越高。

其中，si. m和sj . n分別是ci和cj的詞義，m是ci的詞義數(shù)，n是cj的詞義數(shù)。

基于GVSM的文本相似度[12]計算模型：

R（ci，cj）=SR（ci，cj）·（ si. m， si.n，O）

其中，SR（ci，cj）表示語義相關(guān)度，O是詞庫，本文定義文本向量，增加了ci、cj在文本W(wǎng)k中的權(quán)值，定義如下：

Wk（ci，cj）=（tf-idf（ci，Wk）+tf-idf（cj，Wk））

·R（ci，cj）（6）

由文本向量構(gòu)造GVSM模型，兩個賬戶的語義相似度可以定義為：

sim（Wk，Wp）=

∑ni=1∑nj=1wk（ci，cj）·wp（ci，cj）∑ni=1∑nj=1wk（ci，cj）2×∑ni=1∑nj=1wp（ci，cj）2（7）

1.4行為-語義加權(quán)無向圖模型構(gòu)建

定義7：配置相似度（PAS）：給出兩個用戶：v0∈V0和v1∈V1，v0和v1的配置文件，分別表示屬性向量P0={f0i}mi=0（p0∈P0）和P1={f0j}nj=0（p1∈P1），p0和p1的配置屬性相似度PAS（p0， p1）=H（Sp0，p1）∈[0，1]，其中Sp0，p1是記錄向量的相似字段，H是C4.5分類決策樹算法模型。

為了把配置文件的屬性與用戶賬戶聯(lián)系起來，本文采用賬戶親密度（UC）函數(shù)來衡量兩個賬戶之間的親密程度，采用賬戶的距離（UD）函數(shù)[13]衡量兩個賬戶之間語義和行為的差異性。如果兩個賬戶鄰接賬戶的相似度越大，那么它們的相似度就越高。

定義8：（User Closeness（UC） ）：給出兩個賬戶va ， vb∈V和一個賬戶vm，其中vm與va和vb都相似，F(xiàn)m代表va和vb鄰接頂點的集合[14]，a是a的鄰接頂點，b是b的鄰接頂點，UC函數(shù)表示兩個賬戶的鄰接賬戶權(quán)重和越大，兩個賬戶越相似。

UC（va，vb）=w（va，vb）*

1-2（∑fm∈Fmw（va，vm）*w（vb，vm））∑a′∈Faw（va′，vm）+∑b′∈Fbw（vb′，vm）（8）

w（va，vm）表示鄰接兩頂點的路徑權(quán)重。

為了避免噪聲的影響，本文舍棄了部分相似賬戶，但并不說明它們兩個不相似，如果它們的鄰接頂點相似度很高，證明兩個賬戶很近，也就是說，它們之間的距離是接近的（語義和行為達(dá)到平衡）。定義賬戶距離（UD）函數(shù)如下：

定義9：（User Distance （UD） ）：給出兩個不相鄰賬戶（va∈V，vb∈V ）和一個與va，vb都鄰接的賬戶vm，那么va 和vb的距離可以表示為：

UD（va，vb）=∑fm∈Fmw（va，vm）*w（vb，vm）deg（Fm）（9）

deg（Fm）表示鄰接頂點集合個數(shù)。

定義10：用戶環(huán)繞分?jǐn)?shù)（USS）：給出一個用戶v∈V，那么v的環(huán)繞分?jǐn)?shù)USS的計算公式如下：

USS（v）=∑s∈SseedUC（v，s）*ηvs

UD（v，s）*ηv-s（10）

其中，η是增量系數(shù)，“”表示兩個賬戶之間直接鄰接，“-”表示不直接相連。

定義11：用戶關(guān)系相似分?jǐn)?shù)（URS）：給出兩個用戶v0∈V0和v1∈V1，v0和v1的關(guān)系相似度計算公式如下：

URS（v0，v1）=∑s∈Sseed*

UC（v1，s）*ηv0sandv1s

（1-UD（v1，s））*ηv0sandv1-s

（1-UC（v1，s））*ηv0-sandv1s

UD（v1，s）*ηv0-sandv1-s（11）

定義12：用戶匹配分?jǐn)?shù)（UMS）：給出兩個用戶vselect∈V0和v∈V1，vselect和v的配置文件是pselect∈P0和pv∈P1，vselect和v的UMS定義為：

UMS（vselect，v）=PAS（pselect，pv）*|Sseed|+

URS（vselect，v）（12）

其中，|Sseed|為識別的種子賬戶。

1.5賬戶選擇及交叉匹配過程

賬戶選擇過程分為3步：

（1）每次迭代的第一步均從行為圖或語義圖中選擇一個賬戶，選擇用戶基于以下兩個規(guī)則：①如果兩個賬戶的配置文件具有很高的相似度，那么它們很可能是相同用戶；②USS分值最高的用戶更可能是匹配的，應(yīng)該被選中?；谏鲜鲆?guī)則生成候選賬戶。

（2）計算每個賬戶（行為/語義）的USS。

（3）對行為和語義選出的用戶進行排序，最高的作為下一組候選用戶匹配，過程如下：在有一個候選人用戶v后，需要匹配v用戶，首先，需要從行為圖或語義圖確定候選用戶vselect，利用交叉配血方法計算最匹配的用戶，然后返回UMS分值最高的賬戶。

算法2：當(dāng)?shù)玫狡ヅ溆脩魐matched時，將這個用戶作為一個新的候選用戶，然后通過UserMatch方法得到一個新的匹配候選人v′matched。如果v′matched恰好也是vselect ，則意味著 vselect的最佳匹配的確是vmatched，也就是說這是一個穩(wěn)定的匹配；如果Va、Vs是一組穩(wěn)定匹配，那么Va和Vs是相似的兩個賬戶，否則將用戶vselect放進不匹配的數(shù)組，重置vselect和vmatched進行下一次迭代。如果沒有新的種子用戶，也就是所有的用戶都已經(jīng)參與匹配，則終止迭代過程，從而得到相似賬戶組。

2實驗

2.1實驗環(huán)境及數(shù)據(jù)

實驗環(huán)境配置：使用Java語言，實驗機器采用2G內(nèi)存、500G硬盤，操作系統(tǒng)是Windows XP。

為了驗證本文所提出方法的有效性，實驗設(shè)計了5個對比。為了保護用戶隱私安全，本文實驗數(shù)據(jù)來自Twitter和Facebook公布的匿名數(shù)據(jù)集，由于系統(tǒng)數(shù)據(jù)龐大，實驗僅采取2013-2014年部分區(qū)域網(wǎng)絡(luò)內(nèi)用戶日志作為實驗數(shù)據(jù)，共得到1 678 156條記錄，經(jīng)過數(shù)據(jù)清洗，刪除一些gif、jpg等非文本記錄，最終

得無論是TFR算法還是基于單個行為或語義的算法，雖然可以實現(xiàn)比較高的精確度，但卻導(dǎo)致召回率和F1值比較低。所有版本的CMT比TFR擁有更高的F1值，CMTwc算法效果要比CMTbe差，事實上這些算法包含了很強的修剪過程，因為沒有交叉配血過程提供一個嚴(yán)格的條件，會有很多錯誤的種子用戶作為結(jié)果影響實驗精確度，所以必須以犧牲精確度為代價獲得較高的召回率。

根據(jù)上述比較，可以看到CMT大多數(shù)版本擁有很高的召回率，這也意味著交叉配血策略行之有效。CMT除了CMTts外都有較高的性能，CMTwc通過很強的修剪過程來平衡召回率和精確率。在所有算法中，CMT性能最佳，這表明結(jié)合配置文件和行為語義是有效的方法。

實驗2：為了驗證種子用戶數(shù)量對不同算法F1值的影響，針對上述實驗數(shù)據(jù)集，采用不同算法分別選取1 000～4 000個種子用戶進行實驗，實驗結(jié)果如圖5所示。

由圖5可知，隨著種子數(shù)目的增加，CMT和TFR的F值都會相應(yīng)遞增，當(dāng)增加到一定數(shù)量后遞增速率會變緩從而達(dá)到穩(wěn)定。CMT算法隨著種子用戶數(shù)量的增加始終比TFR擁有較高的F值，說明CMT算法在處理大量用戶數(shù)據(jù)時更為準(zhǔn)確。

實驗3：為了更加清晰展示實驗結(jié)果，生成如圖6所示各個系統(tǒng)性能損耗對比，它展示了5個系統(tǒng)在用戶識別上的性能。采用傳統(tǒng)的方式來計算相似度，雖然不需要處理用戶的行為信息，但復(fù)雜的關(guān)系網(wǎng)使其效率很低。而交叉配血算法提高了識別率，穩(wěn)定性也是最強的。本文提出的按照交叉配血原則來計算用戶多賬戶相似度，大大提高了識別效率，降低了系統(tǒng)開銷。3結(jié)語

為了解決用戶多賬戶識別問題，本文提出了一種新穎的交叉配血策略。結(jié)合配置文件屬性、用戶行為和語義信息，在CMT中使用交叉配血策略，用于檢測種子用戶，不僅降低了計算成本，還避免了復(fù)雜的修剪過程，提高了實驗的準(zhǔn)確性。實驗證明該方案提高了識別算法性能和準(zhǔn)確率。

圖6算法實現(xiàn)效率對比

參考文獻參考文獻：

[1]ZHOU XIAOPING. Crossplatform identification of anonymous identical users in multiple social media networks [J].IEEE Transactions on Knowledge and DataEngineering，2015， 28（2）：411423.

[2]YE NA， ZHAO YINLIANG， DONG LILI，et al. User identification based on multiple attribute decision making in social networks [C]. IEEE China Communications，2013：3739.

[3]蘭麗輝，鞠時光，金華. 社會網(wǎng)絡(luò)數(shù)據(jù)發(fā)布中的隱私保護研究進展[J].小型微型計算機系統(tǒng)，2010，31（12）：23182323.

[4]L ZHIQIANG， S WERIMIN， Y ZHENHUA.Measuring semantic similarity between words using wikipedia [C].2009International Conference on Web Information Systems and Mining，2009：251255.

[5]MOHTASSEB H ，AHMED A. Twolayer lassification and distinguished representations of users and documents for grouping and authorshipidentification [C]. Intelligent Computing and Intelligent Systems， 2009：651657.

[6]周松松，馬建紅.基于URL的相似度會話識別方法[J]. 計算機系統(tǒng)應(yīng)用，2014，23（12）：191196.

[7]業(yè)寧，李威，梁作鵬，等.一種Web用戶行為聚類算法[J].小型微型計算機系統(tǒng)，2010，25（7）：13641367.

[8]MARISA GUTIERREZ，SILVIA BTONDATO.On models of directed path graphs non rooted directed path graphs[J]. Graphs and Combinatorics，2016，32（2）：663684.

[9]SMITA NIRKHI.Comparative study of authorship identification techniques for cyber forensics analysis[J].（IJACSA） International Journal of Advance Computer Science and Applications，2013，4（5）：299320.

[10]WANG WEN QI，IANGLIA FUZZY.Clustering algorithm based on weighted index and optimization of clustering number[C].the series Advances in Intelligent Systemsand Computing，2014：349359.

[11]BONCHI F， GIANNOTTI F. Web log data warehousing and mining for intelligent Web caching[J].Data and Knowledge Engineering，2001，39（2）：165189.

[12]劉東，吳泉源，韓偉紅，等.基于用戶名特征的用戶身份同一性判定方法[J].計算機學(xué)報，2015，38（10）：20282040.

[13]R ZAFARANI，H LIU.Connecting users across social media sites： a behavioralmodeling approach [C]. Proc.of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining （KDD13）， 2013：4149.

[14]孫琛琛，申德榮，寇月，等. 面向關(guān)聯(lián)數(shù)據(jù)的聯(lián)合式實體識別方法[J].計算機學(xué)報，2015，38（9）：17391754.