基于空间动态划分的差分隐私聚类算法

张可铧，成卫青

1.南京邮电大学 计算机学院，南京210023

2.东南大学 计算机网络和信息集成教育部重点实验室，南京211189

随着计算机信息技术的不断发展，数据库系统性能日趋强大、数据存储成本日趋降低，人们能从越来越多的途径获取各种信息。数据挖掘[1]是从大量信息中获取有用知识的关键途径，然而在挖掘有价值资料的过程中，个人隐私资料可能受到损害。数据发布是数据挖掘的重要应用方向，在现实生活中，有许多场所需要定期对外发布数据。比如，一些公司定期公布季度财务报表，医院对外发布医疗统计数据等。随着发布的数据量的增多，攻击者可以通过多个数据表锁定某个个体的隐私信息，导致隐私的泄漏，因此隐私保护已经成为一个重要的问题。

目前，传统匿名隐私保护模型已经被广泛研究。Sweeney[2]提出的k-匿名模型可以使数据表中的每一条记录不能与其他k-1 条记录区分开，从而使得攻击者无法辨别隐私信息的所属个体，保护了个人的隐私。l-多样性（l-diversity）模型可以保证攻击者识别出某一条隐私记录的概率低于1/l。然而，这类隐私保护的模型并没有一个衡量隐私水平的方法，需要不停地改进来防御新的攻击，例如背景知识攻击[3]和合成攻击[4]。为了解决上述问题，2006年Dwork等人[5]提出了差分隐私模型，引起了研究热潮。差分隐私保护技术通过添加拉普拉斯噪声的方式保护数据，使受差分隐私保护的数据集的隐私泄漏风险控制在一个可接受的范围内。

差分隐私保护作为一个新兴的研究热点，它在理论和实际应用中都有很重要的价值。自Dwork 提出差分隐私保护的模型之后，又在一系列文章中不断地完善补充差分隐私理论[6-8]。聚类算法是机器学习中的一个热门研究方向，也是数据挖掘的重要方法。 K-Means 算法是常用的聚类方法之一，算法比较简单并且能够提供高速聚类，聚类效果较好。在差分隐私模型中运用聚类算法也是当下研究较多的方向[9]。差分隐私保护聚类算法的研究动机在于保持良好的聚类效果的同时能够保护个体的隐私信息，这在现实生活中很常见。比如，医院定期发布医疗统计数据，要求对病人的生病类型进行聚类分析，同时又不能暴露具体病人所生的疾病。

针对以上需求，Blum 等人[10]提出了差分隐私k -means 算法，做到在获取聚类结果的同时保护数据隐私，但是聚类可用性受噪声影响较大，并且数据分布会对聚类效果造成很大影响，结果不稳健。李杨等人[11]提出了另一种IDPk-means 算法，改进了聚类初始中心点的选择，使聚类效果更好，但是他们忽视了聚类过程中异常值的负面影响。Yu 等人[12]提出了一种异常检测方法来选择初始聚类中心，并且使用OEPT算法消除数据集中的异常值，用来预处理数据集提高聚类的效果以及可用性。但是，OEPT 算法选择初始聚类中心的方法复杂，且在某些数据分布的情况下会使迭代收敛速度更慢，产生劣化。Su 等人[13]以k 均值聚类算法为例，研究了交互式方法以及非交互式方法的优缺点，提出了一种将交互式方法和非交互式方法相结合的混合方法并应用到差分隐私中，发表了EUGk-means方法。但是该方法在数据量较为庞大的情况下，存储桶的个数会急剧增加，导致添加的噪声量加大，影响最终结果。在文献[13]的研究中，无论数据分布如何，对数据进行均等间隔的分割，并创建存储桶表示这些数据。然而有些不存在数据的区域也被包含进去并且添加了噪声，这样做无形中增加了总噪声量，减少存储桶的数量可以减少噪声插入的数量但是却不能充分表示数据的分布。Ren等人[14]将数据集随机划分为多个子集来获取初始中心，但是结果受数据分布影响较大。胡闯等人[15]在传统的DPk-means算法基础上对初始中心点的选择进行改进，将k-means++算法应用到差分隐私上。但是该方法在数据集分布不规则的情况下产生较差的效果。

由于以往的算法受数据分布影响较大，本文提出一种基于空间动态划分的差分隐私聚类算法，使用四分树详细表示数据分布，在数据分布较密集的区域用较小的存储桶表示，数据分布比较少的区域用较大的存储桶表示，动态划分数据空间，以此来创建一个直方图有效表示数据分布，做到尽量减少存储桶的同时充分表示数据的分布情况，减少插入的噪声。使用处理过的存储桶的数据运行k-means聚类算法，可以有效提高聚类可用性以及准确度，实验结果表明所提算法优于现有算法。

1 相关概念

1.1 差分隐私的基本概念

差分隐私保护模型被公认为是一个严格强大的保护模型。它不依赖于对手的背景知识或者计算能力，通过添加噪声使数据失真，同时保证数据整体的某些属性在统计时保持性质不变。差分隐私的定义如下：

定义1[5]设K 是一随机算法，T1和T2为只存在一条记录不同的兄弟数据表，若K 对任意一对兄弟数据表T1和T2以及任意输出S ⊆Range(K)都满足：

则称算法K 满足ε-差分隐私，其中ε 为差分隐私预算。Pr[K(T1)∈S] 和Pr[K(T2)∈S] 分别表示输出K(T1) 和K(T2)为S 的概率。差分隐私预算ε 一般设定在[0.01，1）的范围之内，较低的ε 能够提供更强的隐私保护。

从定义1可以看出，噪声机制是实现差分隐私保护的主要方法。拉普拉斯机制和指数机制是实现差分隐私的两种常用方法。本文使用拉普拉斯机制实现差分隐私，使用拉普拉斯机制时的噪声大小取决于以下函数的敏感度。

定义2[5，8]设查询函数为f:T →Rd，输入为任意一对兄弟数据表T1和T2，函数f 的敏感度为：

‖ f(T1)-f(T2) ‖1表示f(T1) 和f(T2) 的一阶范数距离。拉普拉斯机制的定义如下：

定义3[16（]Laplace机制）拉普拉斯机制是通过向数值型数据添加Laplace噪声实现差分隐私机制的。现有一数据表T ，设函数f:T →Rd，函数敏感度为Δf ，那么：满足ε-差分隐私保护。噪声函数的概率密度为：

其中b=Δf/ε。

1.2 差分隐私k 均值聚类算法（DPk-means）

设计差分隐私聚类算法是为了在对数据表进行删除数据操作时，簇质心的变化不会导致隐私数据的泄漏。DPk-means[10]的主要思想是：

（1）首先输入数据集D 以及簇的数量k，随机选取k 个点{o1,o2,…,ok}作为初始中心点。

（2）将数据集中的每个点划分到距离它最近的中心簇处，形成新的聚类簇，对于每个聚类簇，计算簇内的数据点各位坐标之和得到，簇内数据个数为num。分别对sum 和num 添加满足差分隐私模型的Laplace 噪声，得到，以及，计 算 新 的 聚 类 中 心 为num′ 。不停重复上述步骤直到达到迭代次数或者中心簇不再变化，返回聚类结果中心C。

隐私预算的分配采用逐步增加的分配方式，第一轮迭代分配的隐私预算为ε/2，之后每次迭代分配的预算为前一次的一半。

在实验过程中发现随机选取初始点会导致算法陷入局部最优解，实验结果不稳定，并且添加噪声之后计算得到的新初始中心点往往会大大偏离原来中心点，从而导致后续聚类结果较差的问题。

2 DPQTk-means聚类算法

传统差分隐私聚类算法对初始中心选择敏感，聚类结果较差，并且盲目遍历所有数据，导致算法效率低下。本文提出一种新的差分隐私聚类算法DPQTk -means 算法（Differentially Private Quad Tree k -means algorithm）。所提算法采用四分树的结构对数据集进行处理，用直方图存储桶的方式表示数据集中分布的数据，自适应地根据数据分布情况用大小不一的存储桶，分布较为稀疏的区域用较大的存储桶，分布密集的区域用较小的存储桶，动态划分空间，更少的存储桶意味着插入的噪声量少，能够有效提高后续聚类效果。这种表示方式能够很好解决EUGk-means 算法中对没有数据的区域也无差别插入噪声的问题，同时能够适用于各种分布的数据。

由于采用构建差分隐私四分树的方式进行表示数据集，因此本文算法对二维平面位置数据有较好的效果。下面介绍四分树的基本结构。

2.1 四分树的结构

四分树（quad tree）是一种树形数据结构，每个结点有四个孩子，因其特殊结构[17-18]可以用来处理二维数据。四分树数据结构有一些共有的特性：（1）四分树把空间分为自适应的区块。（2）每个区块有一个最大容量，达到最大容量，区块会分裂出下一层结点。

图1表示四分树划分平面空间的具体方式，通过判断区块内的数据点的个数是否到达设定阈值来决定是否分裂。图1 中的分裂阈值设定为3，若当前区块内包含的数据点个数小于等于3则不分裂；若个数大于3，则分裂成大小相同的四份。

图1 四分树划分空间示意图

观察图1发现，数据分布比较密集的区域分裂出的区块比较多且小，这就是上文所说的较小的存储桶；数据分布较为稀疏的区块比较大，这就是较大的存储桶。这种分裂方式可以根据点的密集度动态划分空间。实际实验中分裂阈值的设定跟数据集的大小有关，并且存储桶的位置用该桶中心的位置进行代替。

2.2 算法设计

本文通过构造差分隐私四分树，将数据集里的数据存储在四分树上，根据设定阈值使用上述区块分裂策略构造直方图存储桶（也就是四分树的叶结点），创建一个直方图来有效表示数据的分布，接着提取四分树上叶结点的数据以及计数值，初始化数据集，再运行k -means算法进行聚类，初始中心点采用k-means算法在数据集上运行所得到的结果。为了对直方图进行聚类，用存储桶的中心点的数值来表示当前存储桶。

将差分隐私预算ε 分为两份ε1=γε 和ε2=(1-γ)ε来进行分配，ε1采用文献[18-20]中提出的统一分配方法对四分树进行隐私预算分配。统一分配方法按照四分树的高度平均分配每层隐私预算εi=ε1/max H ，这样分配满足从根结点到叶结点的路径隐私预算之和小于等于总隐私预算ε1。ε2对直方图创建完成后的计数值添加噪声。算法1为DPQTk-means算法的主要步骤。

算法1 DPQTk-means算法

输入：数据集D，初始化中心{o1,o2,…,ok}，差分隐私预算ε，四分树的高度maxH ，分裂阈值参数T ，比率γ，中心个数k。

输出：差分隐私聚类结果。

1.ε1←γε,ε2←(1-γ)ε

2.bound←calculate the range of the data

3.Tree ←buildDPQuadTree(D,ε1,bound,max H,T)

4.Leaves ←getQuadTreeLeaves()

5.Bucket ←∅ /*创建存储桶，桶的个数为叶结点的个数*/

6.for each i in[0,Bucket.size-1]：

7.bound ←Leaves[i].bound

8.Bucket.p[i][0]←(bound[0][0]+bound[1][0])/2

9.Bucket.p[i][1]←(bound[0][1]+bound[1][1])/2

10./*设置存储桶的中心位置坐标*/

11.Bucket.NoisyCount[i]←Leaves[i].count+Lap(1/ε2)

12.end for

13.{c1,c2,…,ck}←kmeans(Bucket,k)

14.return Cluster centroids{c1,c2,…,ck}

算法1中首先将差分隐私预算分为两份，第一份用来生成差分隐私四分树，第二份用来计算存储桶的噪音计数值，接着使用一个函数buildDPQuadTree(D,ε1,bound,max H,T)来构建差分隐私四分树，具体的构建方式见后文。构建完毕后数据集中的所有数据都被存储在Bucket 中，Bucket.p[][0]和Bucket.p[][1]表示每个存储桶代表的数据，计算每个Bucket代表的数据点（8和9行），如前文所说，使用存储桶的中心点的数值代表当前存储桶，接着对存储桶的计数值添加差分隐私噪声（第11 行），最后使用所有Bucket 的数据以及噪音计数值运行k-means 算法，返回差分隐私聚类结果。算法1中的bound 是一个二维数组，用于存储一个区块中数据（二维）的取值范围，第二行将数据集中所有数据的第一维的最小值和最大值赋给bound[0][0]和bound[1][0]，第二维的最小值和最大值赋给bound[0][1]和bound[1][1]。

差分隐私四分树的构建方式见算法2。

算法2 buildDPQuadTree(D,ε1,bound,maxH,T)

输入：数据集D，数据集值域bound ，差分隐私预算ε1，四分树的高度maxH ，阈值参数T 。

输出：差分隐私四分树。

2.noise ←Lap(1/budget)

3.count ←node.n /*计算当前结点的计数值*/

4.NoisyCount ←count+noise

5.if h ≥max H or NoisyCount ≤T then

6.nChildren←0

7.return；/*四分树初始高度为0*/

8.end if

9.nChildren ←4

10.splits ←∅ /*二维数组，用来存储孩子结点的序号*/

11.computePivot() /*计算中心点*/

12.for each i from 0 to count-1：

13.pid ←partid(pivot,data.points[i])

14./*把数据划分到四个结点中*/

15.add i to splits[pid]

16.end for

17.makeChildren(splits,h+1,ε1-budget)

算法2 的主要思想为：第一次运行算法2 会建立根结点，并设置当前结点参数，分配每层的隐私预算，根据预算添加拉普拉斯噪声。将数据集中的点根据与中心点的大小关系划分为4 类，分别存储在四个孩子结点上，并且计数。设置完毕之后生成孩子结点，其深度为h+1，分配剩余隐私预算。若四分树深度达到maxH 或者噪音计数值小于等于预先设置的分裂阈值参数T ，则四分树不再继续分裂（if 语句也为递归返回出口）。makeChildren函数用来生成孩子结点，在函数体内递归调用buildDPQuadTree 函数，不断生成结点。具体实现方式见算法3。

算法3 makeChildren(splits,h,budget)函数

输入：记录四个分裂存储桶中数据的数组splits，深度h，剩余隐私预算budget。

输出：孩子结点。

1.create children nodes

2.for j from 0 to nChildren-1

3.for d from 0 to 1

4.if (j ＞＞d)%2==0 then

5.nBound[0][d]←bound[0][d]

6.nBound[1][d]←(bound[0][d]+bound[1][d])/2

7.else

8.nBound[0][d]←(bound[0][d]+bound[1][d])/2

9.nBound[1][d]←bound[1][d]

10.end if

11.end for

12.children[j]←bulidDPQuadTree (splits[j],budget,nBound)

13.end for

makeChildren 函数根据孩子结点序号计算当前孩子结点存储桶（分裂后的存储桶）的数据边界，接着递归调用buildDPQuadTree函数，生成下一层孩子结点。

定义4[19]设有n 个随机算法{ A1,A2,…,An} 和数据集D，任意的Ai满足εi-差分隐私，则该序列组合在数据集D 上满足-差分隐私。

根据定义4，算法2的差分隐私预算为：

由上式可得，算法2满足ε1-差分隐私。

同理，算法1中ε1+ε2=ε，满足ε-差分隐私。

综上所述，所提算法满足ε-差分隐私。

3 实验与结果分析

3.1 实验参数设置与实验环境

本文使用C++语言进行编程仿真，实验环境为Intel®Core i5-8259U @2.3 GHz，8 GB内存，MacOS操作系统。

实验中使用的数据集见表1 所示。由于四分树的结构限制，本文算法适用于二维平面数据。Pytest 数据集为使用python 生成的随机数据集，维度为2，数值为(-2,2)，属性类型为数值型数据。Checkin 数据集[21]为社交网站Gowalla上用户登记酒店的位置信息（经度、纬度），维度为2，数值型数据，分布较稀疏。Unbalance 数据集[22]表示由6 500 个向量和8 个高级聚类合成的数据集。birch3数据集[22]由随机位置和随机大小组成的二维数据集。

表1 数据集信息

DPQTk-means算法需要用到ε（差分隐私预算）、k（聚类的中心簇个数）、maxH（四分树的高度）、T（分裂阈值参数）、γ（预算分配系数）。

通常ε 设置的范围是[0.01，1]之间，一些情况下设置为ln2 或者ln3[23]。本文设置ε 在[0.01，1]之间呈线性分布，方便观察算法聚类效果。

聚类簇的个数已由数据集给出。四分树高度由数据集大小决定，具体计算公式为：maxH=(ln N)/d，其中N 为数据集的样本数，d 为数据集的维度。阈值参数T的计算公式为样本数除以1 000。预算分配系数γ 取0.3。

3.2 评价标准

由于前两个数据集没有分类标签，因此采用规范化簇内方差（Normalized Intracluster Variance，NICV）来衡量聚类效果，NICV的计算公式为：

其中，Ci为第i 个聚类质心，N 为数据集的样本数，x为样本数据。

NICV的值越小，说明聚类簇与簇中数据越紧密，聚类效果越好；反之，说明聚类效果越差。

对于后两个带分类标签的数据集，采用F-measure[24]和NICV相结合的方式评估。F-measure是一种基于精确率和召回率衡量聚类结果准确性（可用性）的度量方法，F-measure 的值越大，表示聚类前后结果相似度越大，即差分隐私算法添加噪声对聚类结果可用性的影响越小。

设N 为数据集的样本数，i 为数据集的类标签，ni代表类i 中的点的数量，nj代表簇Cj中的点的数量，ni,j代表交集部分的点的数量。类i 数据的聚类精确率、召回率和F-measure定义如下：

其中β 设置为1。对于整个数据集来说，F-measure为：

3.3 实验结果与分析

分别在4 个数据集上运行了DPk -means 算法[10]、DPk -means++算法[15]、IDPk -means 算法[11]、EUGk -means 算法[13]以及DPQTk -means 算法。实验过程中，将差分隐私预算ε 从0.01逐步提高到1。实验结果显示的是对应每个差分隐私预算ε，运行30次5个算法之后得到的F-measure和NICV的平均值。

图2和图3分别展示了在数据集D1和D2上运行5种算法得到的NICV的结果。图4（a）和图5（a）为在数据集D3和D4上运行得到的NICV的结果。图4（b）和图5（b）为在D3和D4上运行得到的F-measure的结果。

图2 D1上运行的结果

图3 D2上运行的结果

图2 ～图5 中DPQTk -means 和EUGk -means 算法的NICV接近且难以区分，因此进一步采用相对聚类性能（Relative Clustering Performance，RCP）指标进行衡量。RCP定义为：

图4 D3上运行的结果

图5 D4上运行的结果

RCP 可以放大DPQTk -means 和EUGk -means 算法的NICV 的相对关系，RCP 大于0 说明本文所提算法优于EUGk -means 算法，否则说明EUGk -means 算法更有优势。图6展示了两种算法的聚类性能的优劣情况。

图6 DPQTk-means和EUGk-means算法的RCP

对比图2、图3、图4（a）和图5（a）可以发现，在相同的差分隐私预算ε 下，DPQTk-means算法的规范化簇内方差大幅低于DPk-means 算法、DPk-means++算法以及IDPk -means 算法的。观察图6 发现，DPQTk -means算法与EUGk-means算法的RCP值几乎都大于0，在较低差分隐私预算的情况下，DPQTk-means算法的聚类性能优势明显，RCP 值可以达到10%到25%，这说明本文算法采用构造差分隐私四分树的方式初始化数据集的方式是有效的，通过四分树自适应生成存储桶，动态划分平面空间，比EUGk-means算法插入更少的噪声，提高了聚类效果。观察到DPk-means 算法、DPkmeans++算法以及IDPk-means算法对于数据集的变化NICV值波动较大，而本文算法比较稳定，这些结果都说明本文算法优于其他四个算法。

对比图4（b）以及图5（b）发现，DPQTk-mans 算法优于另外四种算法，因此本文所提算法的聚类结果较为接近原始类标签标注的结果。并且随着差分隐私预算的逐渐增加，F-measure 的值也慢慢增加，这是因为隐私水平降低之后，添加的噪声量也会降低，聚类效果会得到提高。

表2 列出了ε 为0.1 时几种算法在4 个数据集上的运行时间。可以看出，算法运行时间与数据集的大小呈正相关。通过对比在相同数据集上的运行时间可以对比分析各算法的运行效率。

表2 各算法在各数据集下的运行时间 ms

在相同的数据集下，DPk -means、DPk -means++、IDPk-means算法运行时间较长，这是因为这3个算法需要对数据进行逐一遍历，效率低下。

EUGk -means 算法和DPQTk -means 算法运行时间较短，这是因为这两个算法对存储桶进行聚类，提高了效率。DPQTk-means算法的运行效率比EUGk-means算法略低，这是因为DPQTk-means算法需要先对点进行动态划分，消耗了一些时间，但其聚类性能更好。

4 结束语

本文提出了一种基于空间动态划分的差分隐私聚类算法，该算法通过构建差分隐私四分树的方式初始化数据集，动态划分平面空间成自适应存储桶，与传统DPk -means 算法、DPk -means++算法、IDPk -means 算法以及EUGk-means算法相比，有效提高了差分隐私聚类的可用性，并且能够在较高差分隐私保护水平的情况下，保持聚类效果，更好地保护了数据隐私。然而受四分树结构限制，本文算法只能处理二维数据，今后将研究多维数据的差分隐私保护。