韓亞全+曹春萍

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

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

DOIDOI：10.11907/rjdk.162322

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

0引言

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

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

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

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

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

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

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

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

1.1多賬戶識別模型

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

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

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

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

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

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

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

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

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

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

M=（1）

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

定義2：網(wǎng)站模型G： 網(wǎng)站的拓撲結構可以看作是一個有向圖，如公式（2）所示：

G=（2）

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

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

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

定義5：相似性sim（pi，pj）：假設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：語義相似度：當兩個元素（文字或者符號）具有某種特征時，則定義它們是相似的，可以用sim（x，y）（0≤sim（x，y）≤1）表示兩個元素x、y的相似度。

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

圖2語義分析流程

采用基于GVSM 的語義相似度算法計算多個賬戶的語義相似度，通過構建語義網(wǎng)計算兩個詞的關聯(lián)度，從而計算兩個詞的相似性。語義相關度 SR（Semantic Relatedness）表示兩個詞的相似性，采用語義網(wǎng)絡建設模式，將每種類型的邊賦予權值，權值越高說明兩個詞的關聯(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）表示語義相關度，O是詞庫，本文定義文本向量，增加了ci、cj在文本W(wǎng)k中的權值，定義如下：

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

·R（ci，cj）（6）

由文本向量構造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行為-語義加權無向圖模型構建

定義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ù)表示兩個賬戶的鄰接賬戶權重和越大，兩個賬戶越相似。

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）表示鄰接兩頂點的路徑權重。

為了避免噪聲的影響，本文舍棄了部分相似賬戶，但并不說明它們兩個不相似，如果它們的鄰接頂點相似度很高，證明兩個賬戶很近，也就是說，它們之間的距離是接近的（語義和行為達到平衡）。定義賬戶距離（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)繞分數(shù)（USS）：給出一個用戶v∈V，那么v的環(huán)繞分數(shù)USS的計算公式如下：

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

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

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

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

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：用戶匹配分數(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分值最高的用戶更可能是匹配的，應該被選中?；谏鲜鲆?guī)則生成候選賬戶。

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

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

算法2：當?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內存、500G硬盤，操作系統(tǒng)是Windows XP。

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

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

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

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

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

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

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

圖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)絡數(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)應用，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].計算機學報，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]孫琛琛，申德榮，寇月，等. 面向關聯(lián)數(shù)據(jù)的聯(lián)合式實體識別方法[J].計算機學報，2015，38（9）：17391754.