基于差分隐私保护和近邻优化的微博僵尸用户检测

李明娟 朱 焱 李春平

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的自适应是下一步需要深入研究的课题。