李明娟 朱 焱 李春平

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

0 引 言

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

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

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

圖1 非均勻分布的微博數(shù)據(jù)下用戶的錯(cuò)判

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

表1 微博數(shù)據(jù)部分特征

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

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

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

1 相關(guān)技術(shù)

1.1 DPC算法

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

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

(1) 當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，ρi被定義為：

(1)

(2)

(2) 當(dāng)數(shù)據(jù)規(guī)模較小時(shí)，式(1)會(huì)導(dǎo)致某些樣本點(diǎn)具有相同的ρi，進(jìn)而影響結(jié)果的準(zhǔn)確性，所以采用高斯核函數(shù)來定義ρi，定義如下：

(3)

式中：D是整個(gè)數(shù)據(jù)集，dij為點(diǎn)i和j間的歐氏距離，dc為截?cái)嗑嚯x。

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

(4)

(5)

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

1.2 差分隱私保護(hù)

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

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

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

(6)

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

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

(7)

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

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

(8)

式中：K(D)表示真實(shí)查詢結(jié)果f(D)經(jīng)差分隱私加噪后的結(jié)果。

1.3 反向k近鄰

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

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

(9)

式中：D是待檢測數(shù)據(jù)集；KNNk(o)是樣本點(diǎn)o的k個(gè)近鄰點(diǎn)集合。

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

2.1 檢測所涉及的微博特征

微博特征主要分為四類，分別是用戶個(gè)人屬性特征、用戶行為屬性特征、微博內(nèi)容屬性特征和用戶關(guān)系屬性特征。

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

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

(3) 微博內(nèi)容屬性特征。該類特征主要反映微博用戶發(fā)布內(nèi)容的特點(diǎn)，如微博被評論、被轉(zhuǎn)發(fā)率。因?yàn)檎Ｓ脩粲姓鎸?shí)的社交關(guān)系如朋友、家人等做支撐，所以其被關(guān)注度高，發(fā)布的微博被評論、轉(zhuǎn)發(fā)的概率通常比僵尸用戶高。

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

2.2 基于反向k近鄰的密度度量優(yōu)化

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

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

(10)

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

2.3 基于差分隱私保護(hù)的距離計(jì)算

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

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

(11)

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

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

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

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

輸入：微博數(shù)據(jù)集D。

輸出：僵尸用戶檢測結(jié)果集合result。

Begin

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

2.distance=disturb_distance(D);

//調(diào)用算法2

3.density=get_density(distance);

//調(diào)用算法3

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

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

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

7.else

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

9.end if

10.relativeDist.append(δi);

11.end for

12.//設(shè)置僵尸用戶的判定閾值

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

14.for每個(gè)用戶的ρ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行調(diào)用算法2，該方法是對任意兩用戶間距離值進(jìn)行滿足差分隱私的加噪處理。第3行調(diào)用算法3，該方法結(jié)合反向k近鄰重新獲取用戶的局部密度。此外，通過大量實(shí)驗(yàn)尋找了近鄰個(gè)數(shù)k和僵尸用戶判定閾值m的最佳設(shè)置，k的取值范圍在5～15之間最佳，m的取值范圍在10～15之間最佳。

算法2disturb_distance(D)

輸入：數(shù)據(jù)集D，隱私預(yù)算ε。

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

Begin

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

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

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

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

5.end for

6.returndistance;

End

算法3get_density(distance)

輸入：距離矩陣distance，近鄰個(gè)數(shù)k。

輸出：局部密度集合density。

Begin

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

2.fordistance中每個(gè)用戶與其他用戶的距離：

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

4.end for

5.fork_matrix中每個(gè)用戶的反向k近鄰數(shù)：

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

7.density.append(ρi);

8.end for

9.returndensity;

End

3 實(shí)驗(yàn)設(shè)置

3.1 數(shù)據(jù)集與預(yù)處理

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

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

圖2 Dataset1的數(shù)據(jù)分布

各實(shí)驗(yàn)數(shù)據(jù)集具體信息如表2所示。

表2 實(shí)驗(yàn)數(shù)據(jù)集

3.2 評價(jià)指標(biāo)與實(shí)驗(yàn)設(shè)置

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

實(shí)驗(yàn)環(huán)境為：Intel(R) Core(TM) i5- 6200U CPU @2.30 GHz 2.40 GHz，4.00 GB(RAM)內(nèi)存，Windows 10 64位操作系統(tǒng)，實(shí)驗(yàn)使用Python語言實(shí)現(xiàn)。

4 實(shí)驗(yàn)結(jié)果分析

隱私保護(hù)數(shù)據(jù)挖掘的效果取決于隱私信息保護(hù)程度和挖掘結(jié)果的準(zhǔn)確度。為了驗(yàn)證本文提出的DPNN-DPC算法的有效性，在新浪微博數(shù)據(jù)集上對DPNN-DPC算法與DPC算法進(jìn)行了對比實(shí)驗(yàn)，結(jié)果如圖3所示。

圖3 微博數(shù)據(jù)集在不同隱私預(yù)算下的AUC值

對圖3實(shí)驗(yàn)結(jié)果進(jìn)行分析：

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

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

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

圖4 Dataset1數(shù)據(jù)集在不同隱私預(yù)算下的AUC值

圖5 Ionosphere數(shù)據(jù)集在不同隱私預(yù)算下的AUC值

5 結(jié) 語

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

本文算法中的近鄰個(gè)數(shù)k需要人為設(shè)定，所以參數(shù)k的自適應(yīng)是下一步需要深入研究的課題。