基于差分隱私保護和近鄰優化的微博僵尸用戶檢測

李明娟 朱 焱 李春平

1(西南交通大學信息科學與技術學院 四川 成都 611756)2(清華大學軟件學院 北京 100084)

0 引 言

微博僵尸用戶由軟件自動生成和維護，其行為特征不同于正常用戶，是用于批量關注和熱捧其他用戶或話題的“非正常用戶”，這類用戶導致的數據造假現象嚴重影響了微博公信力。僵尸用戶在微博用戶群體中數量少但危害大，且以離群點的形式存在于微博數據中，所以應用離群點檢測技術識別僵尸用戶，對凈化微博環境具有重要意義。

近年出現了各種基于密度的離群點檢測方法。2014年文獻[1]提出一種密度峰值聚類算法DPC(Density peaks clustering)，該算法具有待調節參數少、聚類速度快、能對非球形分布的數據進行聚類等優點。雖然DPC算法是目前較理想的檢測算法，但采用該算法進行僵尸用戶檢測時存在以下不足：

(1) DPC算法根據截斷距離dc定義局部密度，由于輸入的參數dc是全局統一設置的，其具有主觀性且未考慮到數據內部的結構差異。若對類簇間密度相差較大的數據進行聚類，則容易將密度較小的類簇中的正常點錯判為離群點。如圖1所示，采用DPC算法處理密度分布不均勻的微博數據時，由于用戶q在dc范圍內的樣本數少于用戶p，即q的局部密度比p小，所以用戶q更可能被判定為僵尸用戶。但實際上類簇C2中的點分布較稀疏，q更可能是屬于C2的正常用戶，而類簇C1中的點分布較緊密，p更可能是偏離C1的僵尸用戶。因此，這種設置全局參數的方式并不適用于密度分布不均勻的數據集，導致算法在處理這類數據時準確率低。

圖1 非均勻分布的微博數據下用戶的錯判

針對以上問題，本文通過引入反向k近鄰RKNN(Reverse k-nearest neighbor)的概念重新定義DPC算法中樣本的局部密度。RKNN最早由Korn等[2]提出，某樣本的反向k個近鄰樣本離它距離越遠，表明該樣本的偏離程度越大，則它為離群點的可能性也越大。因此，該算法不僅對于發現離群點具有重要作用，而且結合反向k近鄰定義的密度是局部范圍內的相對密度，即使在多密度層次的微博數據中，也能準確地反映微博用戶的局部信息，從而減少僵尸用戶的錯判。

表1 微博數據部分特征

差分隱私DP(Differential privacy)是Dwork等[3]在2006年提出的一種隱私保護機制。相較于傳統的隱私保護技術如k-匿名[4]、l-多樣性[5]等，差分隱私定義了一個極其嚴格的攻擊模型，且對隱私泄露風險給出了嚴謹的數學證明和量化表示。Blum等[6]提出了基于差分隱私保護的DP K-means算法。隨后李楊等[7]提出了IDP K-means算法，通過改進初始中心點的選取方式，解決了DP K-means算法聚類結果較差的問題。吳偉民等[8]提出了基于差分隱私保護的DP DBSCAN算法，該算法在實現隱私信息保護的同時，保持了聚類的有效性。

為了在挖掘過程中保護用戶隱私，可以通過在DPC算法的距離計算中添加滿足差分隱私的隨機噪聲，致使攻擊者難以根據受噪聲干擾的距離值推算出正常用戶的隱私屬性，以實現隱私保護下的僵尸用戶檢測。

綜上，本文研究了一種基于差分隱私保護和近鄰優化的密度峰值聚類算法DPNN-DPC(Density peaks clustering based on differential privacy protection and nearest neighbor)，以實現微博僵尸用戶的檢測。

1 相關技術

1.1 DPC算法

DPC算法基于如下假設：類簇中心的局部密度大于周圍鄰居點的局部密度；不同類簇中心之間的距離相對較遠[9]。該算法有兩個重要概念，分別是樣本的局部密度和相對距離。

定義1(局部密度)[10]。樣本點i的局部密度定義公式如下：

(1) 當數據規模較大時，ρi被定義為：

(1)

(2)

(2) 當數據規模較小時，式(1)會導致某些樣本點具有相同的ρi，進而影響結果的準確性，所以采用高斯核函數來定義ρi，定義如下：

(3)

式中：D是整個數據集，dij為點i和j間的歐氏距離，dc為截斷距離。

定義2(相對距離)[10]。樣本點i的相對距離δi定義如下：

(4)

(5)

對于局部密度最大的樣本點按式(4)計算其相對距離；其他樣本點的相對距離按式(5)計算，式(5)表示點i與局部密度比它大且距離它最近點的距離。

1.2 差分隱私保護

差分隱私保護通過添加滿足特定分布的隨機噪聲使數據失真，從而達到隱私保護的目的。噪聲量的大小受隱私預算和敏感度的直接約束，要使加入的噪聲既能保護用戶隱私，又不能因加入的噪聲過多而導致數據不可用。

定義3(ε-差分隱私)[11]。假設D1和D2是至多相差一條數據記錄的相鄰數據集。給定一個隨機函數K，Range(K)表示K的取值范圍，Pr[X]表示事件X被披露的概率，若K在D1和D2上的輸出結果S(S∈Range(K))能夠滿足：

Pr[K(D1)∈S]≤exp(ε)×Pr[K(D2)∈S]

(6)

則稱算法K滿足ε-差分隱私保護，式中隱私預算ε表示隱私保護程度。ε值越小，則隱私保護程度越高。

定義4(敏感度)[12]。敏感度Δf是指刪除數據集中任一數據對查詢結果造成的最大改變。對于任意函數f:D→Rd，其Δf為：

(7)

式中：D1和D2至多相差一條數據記錄；R表示所映射的實數空間；d表示函數f的查詢維度。Δf只是函數f的性質之一，與數據集無關。

定義5(差分隱私的實現機制)[13]。差分隱私保護的主要實現機制有Laplace機制和指數機制，兩者的本質均是噪聲機制。Laplace機制主要針對數值型數據進行隱私保護，對于函數f:D→Rd，如果算法K滿足差分隱私保護，則向查詢結果f(D)中添加滿足Laplace分布的隨機噪聲，得到查詢結果的近似值：

(8)

式中：K(D)表示真實查詢結果f(D)經差分隱私加噪后的結果。

1.3 反向k近鄰

樣本點i的反向k近鄰(記作RKNNk(i))是那些k近鄰中包含它的點集合[14]。定義如下：

RKNNk(i)={|oo∈D∩i∈KNNk(o)}

(9)

式中：D是待檢測數據集；KNNk(o)是樣本點o的k個近鄰點集合。

2 集成隱私保護和僵尸用戶檢測技術的DPNN-DPC方法

2.1 檢測所涉及的微博特征

微博特征主要分為四類，分別是用戶個人屬性特征、用戶行為屬性特征、微博內容屬性特征和用戶關系屬性特征。

(1) 用戶個人屬性特征。該類特征主要反映微博用戶的基本信息，如是否有個人描述。正常用戶通常會描述自己的身份信息、興趣愛好和生活態度，以達到吸引其他用戶關注的目的，但僵尸用戶這類“非正常用戶”的個人描述大多為空。

(2) 用戶行為屬性特征。該類特征主要反映微博用戶的行為軌跡和作息規律，如平均每日發博量。為了保持一定的活躍度，僵尸用戶通常由第三方軟件每天定時更新微博，所以僵尸用戶較正常用戶發博更頻繁，使得其每日發博量一般遠多于正常用戶。

(3) 微博內容屬性特征。該類特征主要反映微博用戶發布內容的特點，如微博被評論、被轉發率。因為正常用戶有真實的社交關系如朋友、家人等做支撐，所以其被關注度高，發布的微博被評論、轉發的概率通常比僵尸用戶高。

(4) 用戶關系屬性特征。該類特征主要反映微博用戶的社交關系，如用戶關注數與粉絲數的比例(關注粉絲比)。僵尸用戶的關注粉絲比大多集中在10～50之間，而正常用戶的關注粉絲比主要集中在0～8之間，兩者的明顯差異更加說明僵尸用戶以關注其他用戶為目的而存在[15]。

2.2 基于反向k近鄰的密度度量優化

通過引言中的分析可知，在多密度層次的微博數據中設置全局參數dc，容易將稀疏類簇中的正常點錯判為離群點，而將靠近密集類簇的離群點錯判為正常點。因此，為了在密度分布不均勻的數據中準確地表示樣本局部密度，本節提出新的局部密度定義。對于每個樣本點i，其局部密度ρi定義如下：

ρi=SN(i),SN(i)=size(RKNNk(i))

(10)

式中：size(RKNNk(i))代表樣本點i的反向k近鄰數，該值越小，點i的局部密度越小。這樣計算局部密度的優勢在于它不受數據內部結構差異的影響，因為樣本密度只與它周圍樣本的分布有關，進而更準確地反映樣本所在區域的密度特征。結合引言中圖1進行分析，局部離群點p靠近密集類簇C1，p周圍樣本彼此分布緊密但距它相對較遠，使得無任何樣本的k近鄰中包含p，即p的局部密度為0。而稀疏類簇C2中的q，其周圍樣本分布較稀疏，我們發現q周圍樣本的k近鄰中大多都包含q。與圖1中dc度量的局部密度結果相反，根據式(10)度量出q的局部密度明顯大于p，符合數據真實分布情況。所以該定義方式能準確地識別局部離群點和稀疏類簇中的正常點，進而減少DPC算法中由于dc設置不合理導致的微博用戶錯判。

2.3 基于差分隱私保護的距離計算

引言中分析了僵尸用戶檢測時存在的隱私泄露問題，攻擊者可以通過將已獲取的背景知識和兩點間的距離值代入距離計算公式中，從而推算出正常用戶的隱私屬性。因此需要在檢測算法泄露隱私的關鍵位置，即用戶間距離計算中添加滿足差分隱私的隨機噪聲，使得攻擊者難以根據已失真的距離值推算出正常用戶實際的隱私屬性值。加噪方法表示為：

dist(i,j)′=dist(i,j)+Noise

(11)

式中：dist(i,j)為真實距離值；dist(i,j)′為加噪后的距離值；Noise為加入滿足特定分布的隨機噪聲。為了在檢測過程中保護隱私信息的同時盡量減少對檢測結果的影響，引入滿足差分隱私的Laplace噪聲實現。即式(11)中Noise賦值為Laplace(b)，其中b=Δf/ε，可知要加入的噪聲與敏感度Δf成正比，與隱私預算ε成反比。根據Δf的定義，相鄰數據集D1和D2在d維空間[0,1]d中添加或刪除一個樣本時，對每一維的敏感度都為1，所以對于d維數據集，在距離計算中Δf設置為特征維數d(例如10維特征Δf賦值為10)。因此，Laplace機制主要通過ε控制噪聲的大小。ε越小表示加入的噪聲越大，則隱私保護程度越高。

2.4 基于DPNN-DPC的微博僵尸用戶挖掘策略

本文策略包含兩個關鍵技術：(1) 在DPC算法的用戶距離計算中集成差分隱私方法，達到在挖掘僵尸用戶的同時保護隱私數據的目的；(2) 采用反向k近鄰策略更新DPC算法中局部密度的度量方式，從而減少在非均勻分布的數據中微博用戶的錯判，提高檢測準確率。根據計算出的距離和局部密度，得到每個用戶的相對距離。最后將局部密度較小但相對距離較大的微博用戶判定為僵尸用戶。具體如算法1所示。

算法1基于DPNN-DPC的僵尸用戶檢測算法

輸入：微博數據集D。

輸出：僵尸用戶檢測結果集合result。

Begin

1.初始化距離矩陣distance={}、局部密度集合density={}、相對距離集合relativeDist={}、結果集合result={};

2.distance=disturb_distance(D);

//調用算法2

3.density=get_density(distance);

//調用算法3

4.fordensity中每個用戶的局部密度ρi:

5.if用戶i的ρi最大:

6.根據式(4)計算用戶i的相對距離δi;

7.else

8.根據式(5)計算用戶i的相對距離δi;

9.end if

10.relativeDist.append(δi);

11.end for

12.//設置僵尸用戶的判定閾值

13.設置閾值ρ_threhold為density升序后前m%的值，δ_threhold為relativeDist降序后前m%的值;

14.for每個用戶的ρi和δi:

15.ifρi<ρ_threholdandδi>δ_threhold:

16.outlieri=1;

//不符合判斷條件則賦為0

17.end if

18.result.append(outlieri);

19.end for

20.returnresult;

End

其中，算法1第2行調用算法2，該方法是對任意兩用戶間距離值進行滿足差分隱私的加噪處理。第3行調用算法3，該方法結合反向k近鄰重新獲取用戶的局部密度。此外，通過大量實驗尋找了近鄰個數k和僵尸用戶判定閾值m的最佳設置，k的取值范圍在5～15之間最佳，m的取值范圍在10～15之間最佳。

算法2disturb_distance(D)

輸入：數據集D，隱私預算ε。

輸出：加噪聲干擾的距離矩陣distance

Begin

1.forD中任意兩用戶i,j:

2.計算用戶i,j間的距離值dist(i,j);

3.根據式(11)計算加入Laplace噪聲的距離dist(i,j)′;

4.distance.append(dist(i,j)′);

5.end for

6.returndistance;

End

算法3get_density(distance)

輸入：距離矩陣distance，近鄰個數k。

輸出：局部密度集合density。

Begin

1.初始化k近鄰矩陣k_matrix={};

2.fordistance中每個用戶與其他用戶的距離：

3.k_matrix.append(KNNk(i));

4.end for

5.fork_matrix中每個用戶的反向k近鄰數：

6.根據式(10)計算用戶i的局部密度ρi;

7.density.append(ρi);

8.end for

9.returndensity;

End

3 實驗設置

3.1 數據集與預處理

為了分析驗證DPNN-DPC算法的有效性和普適性，本文實驗采用了新浪微博數據集、人工數據集Dataset1以及UCI(http://archive.ics.uci.edu/)的Ionosphere數據集。

為了構建一個真實和有效的微博數據集，挑選出約3 500個資料完整度較高的微博用戶，爬取并小組投票標注出正常用戶和僵尸用戶。在經過數據清洗、特征提取等操作后，構建了本文實驗所用的微博數據集。該數據集包括12個特征，3 060個用戶樣本，其中正常用戶與僵尸用戶的比例約為50 ∶1；數據集Dataset1由4個密集程度不同的類簇和少量離群點構成，數據分布如圖2所示。其中，空心點視為待檢測的離群點；對于UCI數據集，從較小類中隨機抽取少量樣本作為待挖掘的離群點，數據集中較大類樣本為正常點，以此構建滿足離群點檢測特點的實驗數據。

圖2 Dataset1的數據分布

各實驗數據集具體信息如表2所示。

表2 實驗數據集

3.2 評價指標與實驗設置

僵尸用戶的檢測效果采用ROC曲線下的面積AUC值來評估。AUC值在[0,1]之間，值越接近1表示檢測效果越好。隱私保護程度采用隱私預算ε來評估，ε與隱私保護程度呈負相關關系，即ε取值越小，隱私保護程度越高。為減小由添加的隨機噪聲而產生的誤差，在各個實驗數據集上運行30次DPNN-DPC算法后取AUC的平均值作為最終的實驗結果。

實驗環境為：Intel(R) Core(TM) i5- 6200U CPU @2.30 GHz 2.40 GHz，4.00 GB(RAM)內存，Windows 10 64位操作系統，實驗使用Python語言實現。

4 實驗結果分析

隱私保護數據挖掘的效果取決于隱私信息保護程度和挖掘結果的準確度。為了驗證本文提出的DPNN-DPC算法的有效性，在新浪微博數據集上對DPNN-DPC算法與DPC算法進行了對比實驗，結果如圖3所示。

圖3 微博數據集在不同隱私預算下的AUC值

對圖3實驗結果進行分析：

(1) 本文提出的DPNN-DPC算法的AUC值與隱私預算的取值呈正相關關系，即ε值越小，AUC值越小。由2.3節可知，ε值越小，則添加的Laplace噪聲越大，即隱私保護程度越高，加噪后距離值的可用性就越低，導致根據距離計算的局部密度和相對距離受影響，所以AUC值也越小。但隨著ε的不斷增加，AUC值先是急劇上升，然后上升幅度逐漸減少并趨于穩定。因而可以取趨于穩定后并且較小的ε值作為隱私預算，這樣既可以有效檢測出僵尸用戶，也能最大限度地降低正常用戶隱私信息被泄露的風險。

(2) 本文提出的DPNN-DPC算法的AUC值比DPC算法高約4%。當ε較小時，將導致計算的距離值因加入的噪聲過大從而隨機化，將已失效的距離值代入式(10)無任何意義，進而未能使優化效果得到提升。但隨著ε值增大，加入的噪聲量可以在起到一定隱私保護效果的同時，較好地保持用戶間的距離關系，進而代入式(10)中能達到優化局部密度的目的。由2.2節可知，DPNN-DPC算法結合了反向k近鄰以重新獲取用戶局部密度，使其能更準確地表示用戶所在區域的密度特征，減少了將稀疏類簇中的正常用戶檢測為僵尸用戶及將靠近密集類簇中的僵尸用戶檢測為正常用戶的錯判，從而提高了算法的AUC值。

為了驗證DPNN-DPC算法也適用于其他密度不均衡的離群點檢測領域，本文將DPNN-DPC算法在Dataset1和Ionosphere數據集上進行驗證。實驗結果如圖4和圖5所示，可以得出與微博僵尸用戶檢測(圖3)相似的結論，說明DPNN-DPC算法具有普適性。

圖4 Dataset1數據集在不同隱私預算下的AUC值

圖5 Ionosphere數據集在不同隱私預算下的AUC值

5 結 語

本文提出了基于差分隱私保護和近鄰優化的DPNN-DPC算法，主要貢獻為：(1) 集成差分隱私技術，最大限度地降低正常用戶隱私信息被泄露的風險；(2) 結合反向k近鄰重新定義局部密度，減少在非均勻分布的數據下微博用戶的錯判。通過在新浪微博數據集上驗證，表明本文算法既能有效識別微博僵尸用戶，又能一定程度保障數據隱私。本文方法本質上是離群點檢測技術，針對各類數據異常檢測方面，不受數據不平衡的影響，且具有一定的普適性。

本文算法中的近鄰個數k需要人為設定，所以參數k的自適應是下一步需要深入研究的課題。