面向差分隐私的BIRCH算法研究

2022-04-24王豪石张淑芬董燕灵李帅

软件导刊 2022年4期

王豪石，张淑芬，董燕灵，李帅

（1.华北理工大学理学院，河北唐山 063210；2.河北省数据科学与应用重点实验室，河北唐山 063210；3.唐山市数据科学重点实验室，河北唐山 063210）

0 引言

大数据时代，数据信息呈爆炸式增长，这些数据包含了生活的方方面面，例如，浏览器浏览的历史数据、用户浏览淘宝和京东等电商网站数据、手机客户端上的登录数据和使用数据、用户的社交网站数据等。这些数据直接或者间接地涉及了用户隐私信息，使得很多企业可以利用数据挖掘技术挖掘出用户的喜好和生活习惯，以获得巨大的利益。对于用户而言，这可能会造成个人隐私泄露。如果这些数据被一些不法之人恶意利用，可能会给用户带来难以预料的人身伤害和财产安全。此外，用户的一些不正规操作也可能导致用户信息泄露。因此，如何保护用户隐私成为当前亟待解决的问题。

随着数据泄露事件频发，隐私保护技术越来越受到学术界的重视。目前，已有针对敏感数据的隐私保护方法可分为：数据失真、抑制发布及数据加密。其中，数据失真是通过加入扰动实现隐私保护；抑制发布是根据真实情况对数据进行有条件的发布；数据加密是采用加密技术对数据集中的敏感数据进行加密处理。在数据挖掘中，聚类分析是根据研究对象的特征进行分类，但在其聚类分析中经常会出现隐私泄露问题，如何保护数据隐私安全逐渐成为研究的焦点。对此，彭春春等针对数据可用性与隐私保护性，利用本地化差分隐私方法在本地进入随机扰乱，之后在K-modes算法的初始中心点上将出现次数最多的数据作为初始中心点，提出支持本地化差分隐私保护的K_modes聚类方法；蔡英等使用针对混合型数据，利用Laplace机制对数值型添加噪声，用指数机制对分类型数据加噪，提出基于K-prototype聚类的差分隐私混合数据发布算法；傅彦铭等对K-means++算法在选取初始化中心点和迭代中心点中存在的隐私泄露问题，提出一种基于拉普拉斯机制的差分隐私保护K-means++聚类算法研究。

在BIRCH算法构建聚类特征树时存在聚类特征隐私泄露现象，故本文提出面向差分隐私的BIRCH算法。在BIRCH算法构造聚类特征树的聚类特征SS与LS中添加拉普拉斯噪声，以实现保护聚类特征的隐私安全。实验结果表明，本文提出的DPBIRCH算法能在保证聚类结果准确性的情况下，添加不同的随机噪声，实现不同级别的数据隐私保护效果。

1 相关技术

1.1 差分隐私

定义1

差分隐私。假设随机算法

满足

-差分隐私保护，则对任意相邻的两个集合

和

以及

的任意子集

，满足如下条件：

其中，

是使用者的指定常数，Pr(.)为概率密度函数，

和

为两个只差一条数据的相邻数据集，

是

所有的输出集合。从数学的角度看，只要参数

足够小，攻击者是很难从相差为1的数据集

和

中经过分析发现用户的一些真实信息。

定义2

全局敏感度。Δ

是查询函数

的敏感度，定义为：

其中，D和D是具有相同结构的数据集，且至多相差一个元素。

由定义3可知，差分隐私下的拉普拉斯噪声由敏感度Δ

与隐私预算参数

决定。Δ

越大，添加的噪声越大，Δ

越小，添加的噪声越小，添加噪声的值跟Δ

成正比；反观

值的情况，

越大添加的噪声越小，

越小添加的噪声越大，添加噪声的值与

的值成反比。从不同参数的拉普拉斯的噪声分布图（见图1）可以看出其与

的值成反比。

Fig.1 Laplace noise mechanism图1 拉普拉斯噪声机制

1.2 层次聚类

聚类是根据数据特征将一个数据集划分为不同的子集或者簇的过程，聚类算法包括基于划分的聚类、基于层次的聚类、基于密度的聚类。BIRCH算法（Balanced Iterative Reducingand Clustering Using Hierarchies）是常见的层次聚类算法之一，主要思想是用三元组表示一个簇点的相关信息。其算法基本流程为：①遍历数据集，根据初始化的阈值，建立起初始聚类特征树；②修改阈值，将满足新阈值条件的簇构造成一棵新树，并判断所有节点是否满足修改后的阈值，对大于阈值条件的进行分裂，并根据就近原则加入所属的特征树中。重复步骤②，直到一棵完整的树凝聚完成。

2 面向差分隐私保护的BIRCH算法

2.1 BIRCH算法

BIRCH算法利用聚类特征树（Clustering Feature Tree，简称CFTree）实现聚类，其聚类特征树类似于平衡B+树。

聚类特征（

Clustering

Feature

，CF）是一个包括簇信息的三元组（N，LS，SS），其中N代表样本点的个数；LS代表所有样本点的线性和，SS代表所有样本点的平方和。

可加性定理表明，每个父节点的三元组的值是其所有子节点三元组值之和，这一性质使得在更新CF Tree时算法效率更加高效。

2.2 DPBIRCH算法

本文针对在构造CF Tree中存在的CF隐私泄露现象，提出了面向差分隐私的BIRCH算法（DPBIRC算法）。在BIRCH算法构造CF Tree的CF中的LS与SS中加入拉普拉斯噪声，最终达到保护CF的隐私信息和数据的作用。在DPBIRCH聚类算法流程中最关键的步骤是在建立聚类特征树中加入拉普拉斯噪声，其噪声添加过程如下：

步骤1：新数据添加后，检查CF所对应的球体半径阈值，当阈值小于T，则更新路径上所有CF的三元组，并且在LS与SS中添加拉普拉斯噪声，到此，插入结束，转入步骤3；

步骤2：当前叶子节点上CF的个数小于叶子节点最大CF的个数，这时创建一个新的CF，放入新数据，将新的CF节点放入这个叶子节点，更新路径上所有的CF三元组，并在LS与SS中添加拉普拉斯噪声，此时，插入结束。

DPBIRCH算法流程具体如下。

算法1：DPBIRCH算法

上述算法中，枝平衡因子B是指父节点中子节点的最大数目；叶平衡因子L是指叶子节点中CF的最大数目；阈值T是指叶子节点子聚类的最大直径。

2.3 隐私性分析

在拉普拉斯机制中，如果算法中的随机函数能够满足拉普拉斯的分布噪声，就能够实现对数据的隐私保护。DPBIRCH通过在BIRCH算法中的聚类特征SS与LS添加噪声，实现差分隐私保护。本文设定两个拉普拉斯机制函数，其隐私预算都为

，其中一个对SS添加噪声，另一个对LS添加噪声。

证明：算法1中的第8、13与9、14满足差分隐私。

假设

和

是任意相邻数据集，

是加噪算法，LS加噪后为LS，根据拉普拉斯机制：

同理可证SS的加噪过程为：

根据差分隐私的并行组合原理，在每次更新的聚类特征SS中加噪消耗隐私预算的值等于总的隐私预算

，LS中加噪消耗隐私预算的值等于总的隐私预算

；根据差分隐私的串行组合原理，DPBIRCH算法消耗总的隐私预算为2

。

2.4 DPBIRCH算法评价指标

面向差分隐私的BIRCH算法可以从两个指标进行分析，分别为差分隐私保护强度和聚类的准确性。

（1）差分隐私保护强度。差分隐私下的保护强度受隐私保护预算参数

的影响，当隐私保护预算参数

的值越小，添加的拉普拉斯噪声就越大，差分隐私保护强度越高；反之，当隐私保护的预算参数

值越大，添加的拉普拉斯噪声就越小，差分隐私保护强度越低。

（2）聚类准确性。RI指标（Rand Index），简称兰德系数，是一种用排列组合的方式对聚类进行评价，用于比较各聚类算法的准确性。本文将其用于比较添加噪声后数据聚类结果与原始数据聚类结果的相似度，如式（4）所示。

ARI指标（Adjusted Rand Index）简称调整兰德指数。ARI解决了RI不能很好地描述随机分配簇标记向量相似度的问题。ARI的定义如式（5）所示。

其中，

表示期望，max表示最大值。

ARI

的范围为［-1，1］，

ARI

的值越大表示不同簇之间的相似度越高，ARI的值接近于0表示随机分配簇，

ARI

的值为负数表示预测的簇向量非常差。本文算法通过设置不同的隐私预算参数

，比较原始的数据聚类结果与添加拉普拉斯噪声后的数据聚类结果，计算出ARI指标与RI指标的值，从而在保证聚类准确性的同时实现数据隐私保护。

3 实验结果与分析

3.1 实验设计

本文实验采用Python语言实现面向差分隐私的BIRCH算法。实验平台内存为16GB，操作系统为Win10系统，CPU为Intel core i5-9300H 2.40GHz，显卡为GTX16504G GDDR5，Python语言的版本为3.8.3，开发工具为Pycharm 2020.2.3，实验所用的数据集是从UCI数据集上下载的MAGICGamma Telescope数据集（MAGIC伽玛望远镜数据集）。其实验数据集基本信息如表1所示。

Table1 Basic information of experimental data set表1 实验数据集基本信息

为了验证DPBIRCH算法的隐私保护性，本文实验在不同隐私保护预算参数的值与簇值情况下，通过比较原始数据聚类结果与添加拉普拉斯噪声后的数据聚类结果，计算出RI指标与ARI指标的值，并观察RI指标与ARI指标值的变化情况。

具体操作如下：首先，设置不同的簇值，通过添加相同的拉普拉斯噪声观察原始数据聚类结果与添加拉普拉斯噪声后数据聚类结果的RI指标和ARI指标值变化情况；其次，设置簇值相同时，通过添加不同的拉普拉斯噪声观察原始数据聚类结果与添加拉普拉斯噪声后数据聚类结果的RI指标与ARI指标值变化情况。其中，隐私保护预算参数

的取值分别为0.01、0.05、0.1、0.2、0.4、0.8，簇的取值分别为2、3、4、5，交替进行对比实验，并观察取10次聚类结果平均值后的RI指标与ARI指标值变化情况。由于对数据集作了归一化处理，且范围为［0，1］区间，故根据敏感度的定义可知Δ

的值为1。

3.2 实验结果与分析

针对在UCI数据集上的MAGICGamma Telescope数据集，使用本文面向差分隐私的BIRCH算法对该数据集在进行BIRCH算法时设置不同簇值以及不同隐私保护预算参数

的值进行对比实验，观察原始数据聚类结果与添加拉普拉斯噪声后数据聚类结果的RI指标与ARI指标值的情况，并统计与分析所得的RI指标和ARI指标值变化情况。取10次聚类结果平均值后的RI指标与ARI指标值的情况如表2、表3所示。

Table2 MAGIC Gamma Telescope RIindica tor values on the dataset表2 MAGIC Gamma Telescope数据集上的RI指标值情况

Table 3 MAGIC Gamma Telescope ARI index values on the dataset表3 MAGIC Gamma Telescope数据集上的ARI指标值的情况

表2、图2为在MAGICGamma Telescope数据集上隐私保护预算参数

的值和簇值对应的RI指标值变化情况；表3、图3为在MAGICGamma Telescope数据集上隐私保护预算参数

的值和簇值对应的ARI指标值变化情况。从图2、图3可以看出，整体上RI指标与ARI指标的值都随着隐私保护参数预算

值的增大而增大。其中，在比较原始的数据聚类结果与添加拉普拉斯噪声后的数据结果而计算出的RI指标与ARI指标的情况看，当簇值为2的情况下得到AI指标与ARI指标的值最大，且聚类效果最佳。其对应RI指标的值为0.864 01、0.926 10、0.937 67、0.939 64、0.959 44、0.964 08；ARI指标的值为0.639 37、0.813 22、0.844 05、0.847 63、0.901 89、0.914 38。根据实验结果分析可知，在MAGICGamma Telescope数据集中添加不同的拉普拉斯噪声，会对数据产生不同的隐私保护级别。总体上，当差分隐私的隐私保护预算参数

值越大，RI指标与ARI指标受到的影响越小，数据隐私的保护级别越小，可用性就越大，聚类所得到的RI指标与ARI指标的值越接近1；相反，当差分隐私的隐私保护预算参数

值越小，RI指标与ARI指标受到的影响就越大，数据隐私的保护级别越大，可用性就越小，聚类所得到的RI指标与ARI指标的值也越小。在确保聚类准确性的前提下，为实现对数据的隐私保护，本文在利用DPBIRCH算法时，对于

的取值有一定要求，

的取值不能太小，否则影响到数据集的可用性与聚类的准确性；同时

的取值也不能太大，否则会起不到保护数据隐私的作用。由本文实验可知，在MAGIC Gamma Telescope 数据集上，当

的值等于0.2 时，RI 与ARI 指标同

小于0.2 时相比增长明显；且大于0.2时，RI 指标与ARI 指标同

等于0.2 时增长缓慢。故

的值大于等于0.2 时，聚类结果的准确率相比

小于0.2 时提高明显，同时也保护了数据隐私安全。

Fig.2 Relationship between RI index and differential privacy budget parameter ε value on MAGIC Gamma Telescope dataset图2 MAGIC Gamma Telescope数据集上的RI指标与差分隐私预算参数ε值之间的关系

Fig.3 Relationship between ARI index and differential privacy budget parameter ε value on MAGIC Gamma Telescope dataset图3 MAGIC Gamma Telescope数据集上的ARI指标与差分隐私预算参数ε值之间的关系

4 结语

基于传统的BIRCH 算法在进行聚类构建CF Tree 时会存在CF 隐私泄露现象，为了保护BIRCH 算法中CF 的隐私安全，本文提出了面向差分隐私的BIRCH 算法，通过设置不同的隐私预算参数，对构建聚类特征树的聚类特征LS与SS 中添加噪声，以验证不同隐私预算参数下聚类结果的准确性与可用性。下一步将研究如何更加高效准确地对数据添加噪声，以及差分隐私保护在其他机器学习算法中的适用性。