基于差分隐私保护的二分k均值聚类算法研究

马文博, 巫朝霞

(新疆财经大学 统计与数据科学学院， 乌鲁木齐 830011)

0 引 言

当下数据科学的发展一日千里，所产生的数据也呈爆炸式增长，结合传统统计学的理论基础与现代计算机科学的计算优势所产生的衍生学科在处理复杂问题的能力上也有了质的飞跃。机器学习、数据挖掘、人工智能等新的理论和技术也应运而生，为大数据的信息挖掘与应用带来了新的路径和视野，新理论、新技术的应用极大提升了社会服务的效率、增强了商业运营的能力、促进了相关科学研究的发展，但对大数据的滥用及相关的隐私泄漏问题也日渐显现。用户举手投足间产生的海量信息中往往包含着大量的敏感信息，如；金融信息、医疗信息、行为特点信息等，而对这些敏感信息的滥用将会切实危害到信息提供者的隐私安全，不利于大数据行业的健康发展，大数据的利用与隐私保护已经成为了一对尖锐的问题，保护数据隐私的情况下高效的利用数据是当下研究的重要关注点[1-2]。

隐私保护的发展也决定了数据科学的应用范围与发展方向。目前隐私保护方法可以分为密码学方法、信息隐藏方法以及数据处理方法。密码学方法主要是研究数据的加解密方案，以及不同的密钥分配管理机制，包括同态加密、对称加密等[3-4]；信息隐藏方法则通过对原始数据的形态变换，将隐私信息隐写与公开信息再进行传输进而保护原始信息，如数字水印等[5]；数据处理方法是减少隐私数据之间存在的关联性，通过添加数据扰动、数据匿名化等方法实现隐私保护。防止复杂网络分析、深度学习等大数据计算的过程中泄露敏感信息。Dwork在数据扰动的思想下于2006年提出了差分隐私保护技术，是可由严密数学逻辑证明的数据扰动隐私保护技术[6]。通过对所要处理的数据添加符合隐私预算ε的噪声，从而实现在假定攻击者拥有最大知识背景的情况下依然能对数据进行有效保护，使数据在保证其可用性的同时不会泄露敏感信息。

在大数据处理分析中，聚类分析是数据挖掘的核心问题之一[7]。k-means作为基于划分聚类的经典算法，有着原理直观、可解释性强、算法复杂度低、收敛速度快、对于处理大数据具有良好的伸缩性等诸多优势。但传统k-means算法对初始点的选取非常敏感，聚类性能易受初始节点的影响，在算法迭代过程中存在隐私泄露的安全隐患[8]。傅彦铭等[9]人提出了一种基于拉普拉斯机制的差分隐私保护k-means++算法，保证了在不同安全级别下算法的可用性；李洪成[10]等人针对传统隐私保护方法无法应对任意背景知识下恶意分析的问题，提出了分布式环境下满足差分隐私的k-means算法；马银方[11]等人提出了基于差分隐私保护的KDCK-medoids动态聚类算法，解决k-medoids算法不能对动态数据进行聚类的问题；Dwork[12]等人提出了差分隐私保护k-menas算法中隐私预算的分配方法。

本文针对k-means算法可能存在的隐私泄露以及易受初始点选取影响的缺陷，提出了一种基于拉普拉斯噪声机制的差分隐私保护二分k-means算法(DP Bi-k-means)，在聚类的过程中实现了差分隐私保护机制。实验结果表明，该算法与传统差分隐私保护k-means算法相比，可以避免聚类结果受初始点的影响陷入局部最优解，从而优化聚类效果，并为聚类分析提供了严格的隐私保护。

1 差分隐私相关理论

1.1 差分隐私定义

差分隐私是基于不同机制对不同类型的数据进行失真的隐私保护方法。通过对原始数据、算法参数、以及输出结果等关键信息添加服从特定分布的噪音，使在全体数据集中任意添加或删除一条数据并不显著改变该数据集的信息熵，使攻击者在拥有最大背景知识时也无法准确判断某条数据是否在该数据集中，从而保证了所有隐私信息的安全[6]。满足差分隐私的数据集能够抵抗对隐私数据的分析，具有信息论意义上的安全性。

定义1ε-差分隐私

假设D和D′是两个具有相同数据结构且差别为一条数据记录的相邻数据集，函数M为随机函数，其取值范围表示为Range(M)，存在集合S，且S∈Range(M)，E为查询函数，Pr(E)表示隐私泄露的风险。

若随机算法M对数据集D和数据集D′进行计算，得到的输出结果M(D)和M(D′)使M(D)∈range(M)，M(D′)∈range(M)成立，且满足式(1)：

Pr[M(D)∈S]≤eε×Pr[M(D′)∈S]

(1)

则称算法M满足隐私参数为ε的差分隐私[6]。在ε确定的情况下，差分隐私的严格数学定义保证了算法M在计算时其输出结果的概率分布是随机相似的。即使遭到最大背景知识的差分攻击，也能对数据集中任意一条的数据进行保护。由公式(1)可知隐私参数ε的值越小，M(D)与M(D′)的概率分布越相似，随机算法M的隐私保护能力越强。

风险泄露曲线如图1所示，可知在位置参数相同的情况下两曲线的差为|eε|。即满足任意随机算法在相邻数据集上输出同一个结果的概率的比值Z∈[e-ε,eε]。

图1 隐私泄露风险曲线

定义2全局敏感度

敏感度是差分隐私保护中的一个重要参数，全局敏感度是指对数据集中任意一个数据进行修改时对查询结果造成的最大影响。全局敏感度与查询函数性质相关，与数据集无关。

设f是将d维数据集D映射为实数空间内一个d维向量的查询函数，对于任意只相差一条数据的邻近数据集D和D′，函数f的全局敏感度，式(2)：

(2)

对于全局灵敏度较小的函数，只需要添加少量的噪声，就可以使在更改一条数据时对查询结果的影响具有不可分辨性。然而，当全局灵敏度较大时，需要向输出添加大量的噪声，以满足ε差分隐私。为了避免因添加过量噪音导致数据可用性变差，针对不同的问题常常引入不同的噪声机制。

定义3拉普拉斯机制

差分隐私技术通常通过拉普拉斯机制(Laplace Mechanism)实现对数值型数据的隐私保护。在此机制下可以对原数据或随机函数的查询结果添加服从拉普拉斯分布的随机噪声，来保证满足ε的差分隐私。当噪声函数的概率密度为公式(3)时，则此噪声函数服从拉普拉斯分布记为x∽Lap(Δf/ε)

(3)

其中，位置参数为u，尺度参数为b(b>0)，式(4)：

(4)

给定数据集D时，设有查询函数F，全局敏感度为Δf，根据差分隐私定义可得经ε的差分隐私保护的查询函数M，式(5)：

(5)

由公式(5)可知在敏感度已知的情况下，在ε的差分隐私保护的查询函数M中，隐私参数ε越小，添加的噪声越多，隐私保护程度越高。

1.2 差分隐私的特性

隐私保护问题往往是复杂的系统工程。对于多层次的数据结构，多样的查询需求，需要多次使用差分隐私保护算法才能保证数据的隐私安全。为了平衡算法的可用性与算法隐私保护能力，需要借助差分隐私保护算法的两个组合性质合理的设置隐私参数ε。

性质1序列组合性

如果给定一个组合函数S(s1(c),s2(c),s3(c)…sn(c))，对于给定的数据集C进行差分隐私保护，每一个独立的函数s1,s2,s3…sn都满足差分隐私，且差分隐私预算分别为ε1,ε2,ε3…εn则对于整体的组合函数都满足ε差分隐私，式(6)：

(6)

性质2并行组合性

如果给定一个组合函数S(s1(C1),s2(C2),s3(C3)…sn(Cn))，对给定的不相交的数据集C1,C2,C3…Cn进行差分隐私保护，每一个独立的函数s1,s2,s3…sn都满足差分隐私，且差分隐私预算分别为ε1,ε2,ε3…εn，则对于整体的组合函数都满足ε差分隐私，式(7)：

(7)

2 基于拉普拉斯机制保护的二分k-均值聚类算法

二分k均值聚类算法(Bisecting k-means)是传统k-means聚类算法结合层次聚类算法思想中分裂策略的改进算法。首先使所有对象初始化为一个簇，自上而下递归地进行分裂，将原始簇一分为二；再选择其中一个新的簇进行以上操作。因为聚类的误差平方和(SSE)能够衡量聚类性能，该值越小表示数据点越接近于其质心，聚类效果就越好；选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值；重复该过程直到分出了指定的k个簇。相对于k-means聚类算法，该算法最后优化时采用的质心是多次二分产生的，避免了因随机产生质心而得到局部最优化结果。

2.1 k-means聚类算法收敛性证明

给定观测点集D={x1,x2,…,xn}，k-means算法针对聚类所得到的簇划分C={C1,C2,…,Cn}最小化平方误差，式(8)：

(8)

假设簇数k已确定，使用误差平方和(SSE)作为目标函数，可以变形获得畸变函数，式(9)：

(9)

其中，x(i)为观测集中第i个观测，c是观测对象属于的类。

基于最短距离判断可知，c=argmin‖x-μj‖2,μc为聚类簇的中心点，对畸变函数求偏导∂μj(j=1,2,…,k)，式(10)：

(10)

令畸变函数偏导为0，可以求得极值点，式(11)：

(11)

证得收敛。

从k-means的算法可以发现，误差平方和函数(SSE)是一个严格的坐标下降过程。每一次朝一个变量Ci寻找最优解，式(12):

(12)

其中，m是Ci所在簇的元素的个数。

即当前聚类的均值就是当前方向的最优解，这与k-means的每一次迭代过程一样，保证误差平方和函数(SSE)每一次迭代时，都会减小，最终收敛。

由于误差平方和函数(SSE)是一个非凸函数，所以不能保证收敛于全局最优解。

2.2 二分k均值算法隐私泄露风险

二分k-means聚类算法是基于距离的聚类方法，其更新迭代聚类中心点的过程与传统k-means相同，其中迭代参数sum为分类过程中簇内的点到簇中心点的距离之和，num为分类过程中簇内点的个数，Ck为聚类过程中的簇中心，式(13)：

(13)

由公式(13)可知，二分k均值算法在基于背景知识对聚类中心点的攻击下会泄露整体数据集从而发生隐私泄露[8]。

2.3 差分隐私保护的二分k均值(DP Bi-k-means)算法设计

针对二分k均值聚类算法在聚类过程中存在数据泄露的问题，ε-差分隐私保护二分k均值聚类算法通过在算法迭代中心点添加噪音，达到对中心点数据的保护，算法的步骤如下：

步骤1预设聚类个数k；

步骤2将整体数据划分为一个簇，计算质心及总误差平方和；

步骤3使用k-means算法将这个簇二分为两个簇；

步骤4计算该簇一分为二之后的总误差平方和；

步骤5选择满足条件的可以分解的簇进行划分；

步骤6重复步骤3-步骤5操作，直到达到指定的簇数k为止。

迭代过程中分别计算各簇迭代参数sum与num并分别添加拉普拉斯噪音，从而得到新的聚类中心，式(14)：

(14)

通常在步骤5时会选择可以使总误差平方和最小的簇进行划分，本文选用划分后簇内误差平方和最大的簇进行划分。实验证明：在保证其聚类效果优于传统k-means算法的情况下，相较于通常的二分k-means算法提高了算法运行效率。

2.4 差分隐私保护的二分k均值(DP Bi-k-means)算法安全性证明

DP Bi-k-means算法通过向迭代过程添加服从拉普拉斯的噪音实现对算法敏感参数的保护，进而保护整体数据集，其中隐私保护强度由全局敏感度Δf、隐私参数ε决定。由定义2可知：在算法迭代中心点时，敏感度参数Δf=1。同一簇内计算距离之和的敏感度Δf≤M，M为数据集的特征个数，所以DP Bi-k-means算法的全局敏感度为M+1。

根据定义1，对随机算法M更新的迭代中心点进行计算可得式(15)；

Pr[M(D)∈S]≤eε×Pr[M(D′)∈S]

(15)

根据性质1，差分隐私的序列组可得式(16)：

(16)

即DP Bi-k-means算法满足ε-差分隐私。

3 实验结果及分析

通过3个方面对差分隐私保护的二分k均值算法(DP Bi-k-means)进行实验评价：

(1)DP Bi-k-means与DP k-means在隐私参数动态变化的情况下对比聚类效果，分析新算法的算法特征；

(2)分析在相同隐私参数条件下新算法相比传统算法的抗局部最优解的能力；

(3)通过使用不同的分类策略提高新算法的运行效率。

实验平台为windows10操作系统，cpu3.2 GHZ，8 GB内存，采用python语言及相关库进行模拟实验。数据集来自UCI机器学习实验室的IRIS数据集和Wine数据集，见表1。

表1 数据集信息

3.1 实验评价指标

为了对DP Bi-k-means算法的聚类效果进行综合评价，本文以DP k-means作为对比算法，分别从内部评估法中选取轮廓系数(Silhouette Coefficient)、DB指数(Davies-Bouldin score)、CH指数(Calinski-Harabasz Index)、外部评估方法中选取调兰德指数(Adjusted Rand Index)来对两种差分隐私聚类算法进行多方面比较。

通过对DP Bi-k-means与DP k-means的误差平方和(SSE)进行比较，来分析新算法的聚类性能与鲁棒性，并对算法改进后选用划分后簇内误差平方和最大的簇进行划分的运行效率进行实验分析。

3.2 实验结果

3.2.1 聚类效果分析

实验中通过控制隐私预算参数ε，进而在不同的隐私保护水平下对算法进行聚类效果的比较实验。

实验在指定分类个数k=3的预设下，在隐私参数ε逐步增加的情况下对试验指标进行测度。由于在k均值聚类算法中超参数只有聚类个数k，所以实验结果完全受隐私预算参数ε、算法本身以及随机误差决定。通过直接度量聚类效果的角度进行实验分析，统计算法的内部指标轮廓系数、DB指数和CH指数。经实验得到轮廓系数图如图2所示，可知在ε变动的情况下，相比DP k-means算法本文提出的DP Bi-kmeans算法轮廓系数整体更接近于1，分类目标与所划分类别更加匹配，且波动程度较小聚类效果更稳定；在相同实验条件下得到两种聚类算法的CH系数图如图3所示，可知DP Bi-k-means算法的CH系数更大，各分类内部越紧密，各分类之间越疏松，聚类能力较DP k-means算法有一定优势；实验分析DB指标得到DB指标图如图4所示，DP Bi-k-means算法的DB指数相较于与DP k-means算法的DB指数更小，各分类之间距离更大，分类结果更好。

图2 轮廓系数图

图3 CH指标图

图4 DB指标图

在将原始IRIS数据分类结果作为外部参考，将两种算法的调兰德指数(ARI)作为外部评估指标，实验得出的ARI指数图如图5所示，可以观察到在隐私参数逐步增加，隐私保护水平在逐渐减小的过程中DP Bi-k-means算法的ARI指数相比DP k-means的ARI指数始终更大，DP Bi-k-means算法的分类之间聚类的重叠程度更低。

图5 调整兰德指数图

通过对两种算法进行内部、外部评估，得知DP Bi-k-means相较于DP k-means有着更好的聚类性能。

3.2.2 鲁棒性分析

在对IRIS数据集聚类过程中进行两种算法的鲁棒性分析，在数据集聚类簇数k=3时进行实验，动态变化的隐私参数ε对DP Bi-k-means算法与DP k-means算法的总误差平方和(SSE)的影响情况如图6所示，可以观察到DP Bi-k-means算法相较于DP k-means算法，平均误差平方和降低61.15，且波动幅度更小，所以DP Bi-k-means算法有着更好的鲁棒性。

图6 误差平方和波动图

3.3.2 聚类效率分析

算法运行效率与相同条件下算法运行时间有直接联系，本文对比了两种划分方法在相同条件下的运行时间，运行时间图如图7所示 ，DP Bi-k-means 1是选用划分后簇内误差平方和最大的簇进行划分，DP Bi-k-means 2则为使用总误差平方和最小的簇进行划分，本文算法选择划分后簇内误差平方和最大的簇进行划分。由图7可知DP Bi-k-means 1比DP Bi-k-means 2运行时间更短，证明在保证其聚类效果优于传统k-means算法并且满足差分隐私保护的情况下，相较于一般二分k均值算法的划分方式提高了算法的运行效率。

图7 运行时间图

4 结束语

本文针对差分隐私保护的k均值聚类算法易受初始点影响，导致算法整体陷入局部最优解的问题，结合分层聚类的思想提出了一种差分隐私保护二分k均值聚类算法。在动态改变隐私参数的实验中与传统算法进行对比，由实验结果可知，新算法在保证其隐私保护能力的前提下，提高了聚类效果，增强了聚类算法的鲁棒性，并通过选取合适的簇划分规则提高了算法的运行效率，并证明新算法在不同隐私保护水平的情况下都有较好的性能，下一步将继续研究基于此算法的融合算法。