基于距离贡献率的隐私保护框架下k-medoids算法研究

刘丹青，高 瑜，吴振强

(1.青海师范大学 计算机学院，青海 西宁 810016；2.陕西定边实验中学 计算机基础教学部，陕西 榆林 718600；3.陕西师范大学 计算机科学学院，陕西 西安 710062)

1 引言

现如今，无处不在的信息技术使各个领域都产生了海量的数据，如何从中“提炼”出有效的知识或信息，为人们的生产和生活提供决策，是大数据时代一项重要的工作.然而Malik[1]指出，拥有越多的数据就越能够发现其中的错误和不精准数据.为此，需要专业的数据挖掘技术使人们能够从海量数据中找到对实践具有指导作用的知识.

随着网络科学的发展，数据挖掘技术中的聚类分析应用越来越广泛，在研究者们共同努力下也有了更大的技术进展和应用市场.它的功能主要是通过观察若干个簇的特征，以洞察数据模式的分布.但Geng[2]指出，在聚类分析中用户的敏感信息有可能被第三方利用数据挖掘引发隐私安全问题，且部分用户还有可能为了保护自己隐私不被窃取，在数据提交之初就刻意隐瞒自己的真实信息.因此聚类分析中的用户隐私泄露等问题极大地限制了数据挖掘技术的深度应用.

为了处理数据隐私保护和数据挖掘分析之间的关系，Aggrawal在1999年初次提出隐私保护下的数据挖掘技术，在隐私保护前提下设计对敏感信息保护的算法，防止敏感属性遭到隐私攻击，至此学界掀起了一股这一领域的研究热潮[3].作为分析数据问题、寻找数据之间内在结构或分布模式的数据挖掘工具——聚类分析，如何保证在聚类过程中不被攻击者获取用户的隐私也逐渐成为学者们致力研究的一个学术方向[4].

2006年，Dwork等[5]提出了一种基于严格数学定义的模型——差分隐私保护模型，这种模型通过在真实数据基础上添加随机噪声，就可使攻击者无法发现原始数据的分布模式及真实值，实现对真实数据的隐私保护，这一优势引起研究者们的持续关注.基于这一隐私保护模型框架，Dwork[6]在对隐私数据进行分析时提出了DPk-means优化算法，通过修改隐私预算分配方式以提高聚类效果，但未对初始中心点的选择进行优化.国内学者李杨等[7]继而在该算法基础上提出了能对初始中心点选择优化的IDPk-means算法，以提高算法的实用性.胡闯等[8]研究了一种新的聚类算法——DPk-means-up算法，该算法以k-means++的结果作为输入值，改善了中心点的选择问题.傅彦铭等[9]则针对k-means++算法在随机选取初始化中心点和迭代求质心过程中隐私泄露的问题，提出了DPk-means++算法，确保不同隐私预算下聚类的可用性及准确性.

聚类分析中基于划分的另一种典型算法——k-medoids算法应用比较广泛，主要用来解决离群值问题，因而隐私保护下的k-medoids算法研究也更富有挑战性[10-11].Sanjit Kumar Dash[12]提出了一种在移动云架构中使用同态加密技术保护数据的方法——差分隐私下的k-medoids分析法，用在与他人共享敏感隐私信息时，保护隐私免被侵犯.国内研究中，马银方等[13]考虑到海量数据在动态聚类过程中的隐私保护问题，提出了差分隐私下的动态聚类算法KDCk-medoids.文献[14]也提出了一种差分隐私下的DPk-medoids算法，该算法在基于欧式距离测度数据相似性的迭代中对聚类中心点添加Laplace噪声后再发布，以防止聚类结果的隐私信息泄露.2016年，英国考文垂大学的研究学者提出了一种差分隐私的拓展模型——误差隐私保护模型，这两种模型都属于应用数据扰动技术中添加随机数的方法来进行隐私保护的方法[15].基于这一隐私保护模型，文献[16]提出了一种EPPk-medoids算法，通过随机化查询结果，可以使攻击者无法透过扰动值推断出聚类后用户的隐私信息[16].

上述研究工作中，研究者均视研究所基于的数据集中数据点的每个维度对于数据的重要性或者影响程度都相同，但事实上，从数据分析的角度而言，数据点的属性集中有的属性重要、占主导地位，有的属性次要、仅起辅助说明作用，这使得对数据点的聚类和加噪应根据数据点每一维属性对于该数据的重要性或者影响程度而论，不应统一而论.基于此，论文提出了基于距离贡献率聚类(即加权聚类)的Wk-medoids算法，并在该聚类算法基础上提出了基于距离贡献率加噪(即加权加噪)的面向差分隐私保护框架的WDPk-medoids算法及面向误差隐私保护框架的WEPPk-medoids算法，研究了相应算法的特性，并与前人未加权的工作做了对比分析，以验证算法在聚类和加噪过程中引入数据属性权重的必要性及重要性；同时还应用聚类效用评价指标对这三种基于距离贡献率的隐私保护聚类算法的性能进行了对比分析，为隐私保护框架下聚类挖掘算法如何权衡数据聚类有效性以及隐私保护安全性之间的相互关系提供了参照建议.

2 基于距离贡献率的Wk-medoids算法

2.1 闵氏距离

聚类分析中基于划分的k-medoids算法是一种常用的聚类算法，其基本问题描述如下：设数据集D={x1，x2，…，xn}，且xi∈Rd，k表示将数据集合D划分为类簇的个数，Cj表示第j个类簇，nj表示第j个类簇的大小.

k-medoids算法一般采用欧氏距离作为目标函数来划分数据集，为了研究隐私保护框架下聚类算法的普适性特征，论文基于闵氏距离开展研究，如定义1所示.闵氏距离(亦称闵可夫斯基距离)，是欧氏空间的一种测度，当幂指数p分别取1，2及∞时，该距离公式分别相当于曼哈顿距离、欧氏距离及切比雪夫距离.

定义1[17]闵氏距离

(1)

其中：xij表示第i个数据的第j个属性值，xkj表示第k个数据的第j个属性值，d(xi，xk)表示数据点xi(i=1，2，…，n)到中心点xk(i=1，2，…，n)的距离值.

通常在计算数据点相似性的算法中，默认为数据点每一维的属性对于点与点之间距离的贡献率是一样的.为了更准确地度量数据之间的相似性，应依据属性集中属性的重要程度，或对其他属性的影响程度、或对计算样本点距离中心点远近的贡献率，通过对各属性之间进行横向比较而确定其相应的权值.于是，数据集所有样本点第k个属性的权重均相同，相当于整个数据集只有一个1×m维的权重向量，该权重标准强化了重要属性对距离中心点的贡献率、减弱了次要属性对计算距离中心点远近的影响[17].基于此，论文采用基于距离贡献率的闵氏距离来开展隐私保护框架下k-medoids算法的研究，如定义2所示.我们将这个加权聚类算法称为Wk-medoids算法.

定义2[18]基于距离贡献率的闵氏距离为：

(2)

需要说明的是，论文关于权值ω的计算方法没有做统一的定义，根据实际决策问题可采用主观赋权法，即决策者(专家)依据对各属性的重视程度和自身的知识经验来确定各属性的权重，也可采用客观赋权法或组合赋权法来确定各属性的权重，只要满足各属性的权重之和为1即可.在本文的仿真实验中，权值ω是通过随机数赋值的.

Wk-medoids算法中，中心点的更新可以采用数据点距代表对象的聚类误差平方和最小为迭代策略，该平方和定义如下所示：

定义3[19]聚类误差平方和

(3)

其中：xj b表示第j类的第b个对象，oj是簇Cj的代表对象.

2.2 聚类效用评价指标

为了分析聚类结果的有效性及可用性，在聚类分析过程中需要采用一些客观的评价方法，本小节主要介绍论文所采用的几个聚类效用评价指标[20].

定义4[21]戴维森堡丁指数DB.戴维森堡丁指数DB是通过数据集中任意两个簇的簇内平均距离之和Si+Sj与两个簇簇中心距离Sij的比值中最大值之和的平均值，来计算簇之间的相似度：

(4)

根据公式可知，DB值与聚类结果相似性的程度呈反比，即DB值越小，簇内越同质、簇间越异质.

设有数据集D={x1，x2，…，xn}.假设数据集D可划分成m个组，表示为E={E1，E2，…，Em}，且D中存在一个包含k个簇的聚类结构，表示为C={C1，C2，…，Ck}，则可通过比较分组E和聚类结构C来对聚类质量进行评价.

定义5[22]标准化互信息NMI(Normalized Mutual Information)可通过下面一组公式进行计算：

(1)数据E和C之间的互信息

(5)

(2)数据E与C之间的信息熵

H(E)=-∑Ep(Ei)p(Cj),

(6)

(3)数据E与C之间的归一化互信息

(7)

由式(7)可知，NMI的值越大，则划分结果越相似、聚类效果越好.

(8)

2.3 Wk-medoids算法流程图

聚类算法中的k-medoids算法主要解决离群值问题，应用比较广泛.Wk-medoids算法以目标函数最小化为目的，通过迭代策略把数据集合划分成若干个块或分组，每个块或分组称为一个簇.

算法流程图如图1所示.

图1 Wk-medoids算法流程图

3 基于距离贡献率的WDPk-medoids算法

3.1 差分隐私保护模型

差分隐私保护采用添加诸如适用于数值数据的Laplace随机数，以对数据进行加噪处理.噪声值的大小受敏感度影响，噪声过大，数据可用性降低；噪声过小，数据隐私泄露风险增高.

定义7[23]假设随机函数A所有可能的输出构成集合Range(A)，且Range(A)的任意子集为S(S⊆Range(A))，对于最多相差一条记录的两个数据集D1，D2，(|D1ΔD2|≤1))，若满足下式：

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

(9)

则称A提供ε-差分隐私，数据隐私保护的效果随着隐私保护预算ε的增大而降低.

定义8[23]设有函数f：D→Rd.对于任意相邻的数据集D1和D2，其敏感度定义为：

Δf=maxD1D2‖f(D1)-f(D2)‖.

(10)

定义9[23]基于定义8，如果算法A的输出结果满足：

A(D)=f(D)+〈Lap1(Δf/ε)，…，Lapd(Δf/ε)〉

(11)

则称算法A可提供满足Laplace机制的差分隐私保护.

考虑到数据集D中数据点每一维的属性对于数据的重要程度不同，且在聚类过程中对于距离中心点的贡献率也有所不同，因此对数据点的加噪也应按照属性相应的贡献率有轻重缓急之分，以减少数据整体的失真程度.基于此，我们提出基于距离贡献率的Laplace加噪机制，即依据数据每一维属性的权重来为相应维度添加噪声，此时算法A的输出结果满足：

A(D)=f(D)+〈ω1*Lap1(Δf/ε)，…，ωd*Lapd(Δf/ε)〉

(12)

3.2 WDPk-medoids算法流程图

WDPk-medoids算法是在差分隐私保护框架下基于DPk-medoids的算法，应用基于距离贡献率的理念对中心点加噪、对剩余结点聚类，循环往复直至发布最新噪音中心点和聚类分布，以实现隐私信息不被泄露的目的.

算法流程图如图2所示.

图2 WDPk-medoids算法流程图

4 基于距离贡献率的WEPPk-medoids算法

4.1 误差隐私保护模型

误差隐私保护模型是对查询结果随机化，使得第三方估算数据点在与不在数据集中的误差方差值总相等，从而无法挖掘用户的隐私信息.

(13)

这里，参数ε为xe的隐私泄露程度.式(12)表明，第三方使用函数f(Dn)预测xe的未知信息比用函数f(Dne)预测xe的未知信息仅仅多ε部分，当ε很小时，xe几乎没有隐私披露的风险；如果ε为0，数据的隐私保护最强，即用户的信息不会因为在Dn中就会被第三方使用查询函数查询得到个人隐私，而是和xe不在Dn中的情况有几乎相同的查询结果；而随着ε值的增加，xe隐私披露的风险也逐步增加.

为了实现对数据点的隐私保护，需要在满足上式条件下，对查询结果随机化.该过程可采用自助抽样法加噪机制来进行，其过程如图3所示[16]：对于数据集的每一个簇，用均匀随机抽样法生成样本簇，样本簇大小与原始簇大小相同，并按下式计算样本簇的质心(中心点):

图3 自助抽样法的过程示意图

(14)

再独立地将前面的随机抽样事件重复执行B次，并取这些质心的均值.则每个聚类簇的中心点可按下式进行估计，其中αe为xe在有放回抽样的结果中出现的次数：

(15)

与差分隐私保护框架中对聚类中心的加噪一样，在误差隐私保护框架下我们同样提出基于距离贡献率的自助抽样加噪机制，在对样本簇质心的每个分量进行估算时参考了相应属性的权重，此时每个样本簇的中心点可按下式进行估计：

(16)

4.2 WEPPk-medoids算法流程图

WEPPk-medoids算法是在误差隐私保护框架下基于EPPk-medoids算法，在Wk-medoids聚类分析所得中心点上，应用基于距离贡献率的自助抽样法估算近似中心点(噪音结点)，再以噪音结点为聚类中心基于距离贡献率重新分配剩余结点，直接发布加噪后的中心点及聚类分布，由此防止第三方得到真实聚类分布情况.

算法流程图如图4所示：

图4 WEPPk-medoids算法流程图

5 算法分析与讨论

5.1 WDPk-medoids算法性能分析

本节我们对WDPk-medoids算法，应用DB指标考察引入数据点各维度基于距离的贡献率对算法聚类和加噪过程产生的影响，以说明在差分隐私保护框架下WDPk-medoids算法相较于DPk-medoids算法的优势，并基于DB指标和NMI指标分别对WDPk-medoids算法中的闵氏距离幂指数进行仿真分析，以了解该算法的特性.

论文研究采用UCI Knowledge Discovery Archive database中的公开数据集——大肠杆菌数据集.该数据集是一个生物领域的多分类数据集，由336个大肠杆菌蛋白质数据组成，每个数据均使用从蛋白质氨基酸序列计算出的七个输入变量，外加序列名称共八个属性进行描述.在仿真实验时我们删除第一列属性(序列名称)、只取后七列属性，再对所有数据进行预处理，将数据归一化为0到1之间的小数，基于预处理过的数据集使用MATLAB 2013对算法调用多次后取相应指标的平均值.

(1)距离贡献率对DB比率值的影响

针对在聚类和加噪过程中是否需要引入距离贡献率这一问题，我们在相同幂指数(p=2)下，着重考察了距离贡献率对算法DB比率值(加噪前算法的DB值与加噪后算法DB值的比率)的影响，如图5所示，其中橙色曲线表示DPk-medoids算法下的DB比率值(加噪前k-medoids算法的DB值与加噪后DPk-medoids算法DB值的比率变化)，而黄色曲线表示WDPk-medoids算法下的DB比率值(加噪前Wk-medoids算法的DB值与加噪后WDPk-medoids算法DB值的比率变化).显然，当数据点在聚类和加噪过程中按照属性的重要程度来测度或随机化后，加权的WDPk-medoids算法的DB比率值整体要高于未加权的DPk-medoids算法，这是由于加权后WDPk-medoids算法的DB值变小，使得相同ε下DB比率值增大.根据DB值与聚类结果相似性程度呈反比这一理论，这意味着加权划分后的聚类在差分隐私保护框架下其整体聚类效果更优.

图5 WDPk-medoids与DPk-medoids算法的DB比率比较图

(2)不同幂指数p对DB比率值的影响

当数据集的聚类数确定时，通过仿真分析如图6所示，加权下幂指数p越小，WDPk-medoids算法的DB比率值(原始k-medoids算法的DB值与添加噪声后WDPk-medoids算法DB值的比率)整体越大，当p=1时，该比率值整体性能最优，稳定在0.9～1之间，说明此时在差分隐私保护框架下，WDPk-medoids算法的聚类效果更接近于原始的k-medoids算法.

图6 WDPk-medoids算法的DB比率曲线图

(3)不同幂指数p对NMI指标的影响

聚类中的NMI指标反映了对数据集所划分簇之间的异质性以及簇内部同质性的程度，它与聚类有效性呈正比关系.通过图7可见，幂指数p越小，同等隐私保护程度下(相同ε值)聚类的有效性越好；随着ε值的增大，即隐私保护程度降低时，不同幂指数下的NMI值均有所升高.

图7 WDPk-medoids算法的NMI指标曲线图

从以上分析可以看出，差分隐私保护框架下算法的隐私保护预算ε越小，则添加的噪声越大、数据隐私泄露风险越低，但与此同时，WDPk-medoids算法在不同幂指数下的聚类效果均有所下降(不同颜色的曲线从右向左看均呈下降趋势).是否有算法能够同时兼顾k-medoids算法的聚类有效性以及聚类发布中数据的隐私保护程度呢？下面我们在误差隐私保护框架下对基于距离贡献率的WEPPk-medoids算法进行仿真研究.

5.2 WEPPk-medoids算法性能分析

本节我们对WEPPk-medoids算法，基于NMI指标及AP指标着重考察引入数据点各属性的权重对算法聚类和加噪过程产生的影响，以说明在误差隐私保护框架下WEPPk-medoids算法相较于EPPk-medoids算法的优势，其中WEPP-know及WEPP-unknow分别表示算法中第三方是否知道预测数据点属于哪个簇对应的情况.

(1)距离贡献率对NMI指标的影响

NMI指标是反映聚类有效性的重要指标，通过图8可见，当考虑数据点各属性对聚类及加噪过程的影响程度时，对于know及unknow两种情况，加权的WEPPk-medoids算法在各隐私保护预算ε下，整体聚类效果均大于未加权的EPPk-medoids算法.

图8 WEPPk-medoids与EPPk-medoids算法的NMI指标比较图

(2)距离贡献率对AP指标的影响

为了进一步说明若要达到相同的隐私保护程度，不同算法需要添加扰动量的大小，即添加的扰动量随隐私泄露程度值的变化情况，我们通过实验得到了AP(加入扰动量的平均值)随ε变化的关系图，如图9所示，对于know及unknow两种情况，加权的WEPPk-medoids算法在各隐私保护预算ε下，平均加入扰动量的程度要小于未加权的EPPk-medoids算法.这说明WEPPk-medoids这种依属性权重加噪数据的方法可降低对整个数据点添加的噪声量、减少加噪数据的失真程度，达到更好的聚类效果.

图9 WEPPk-medoids与EPPk-medoids算法的AP指标比较图

5.3 三种加权算法的比较分析

本节我们基于NMI及AP两聚类效用评价指标着重对比分析基于距离贡献率的无隐私保护的Wk-medoids算法、差分隐私框架下的WDPk-medoids算法和误差隐私框架下的WEPPk-medoids算法在聚类有效性及隐私保护安全性上的优劣.

(1)聚类有效性分析

图10展示了当ε变化时不同算法NMI指标的变化情况.根据理论可知，ε值与隐私保护程度的强弱呈反向关系，而NMI值与算法聚类结果的好坏呈正向关系.

如图10所示，Wk-medoids算法由于其不提供任何隐私保护，因而其聚类有效性最优；随着ε值的增加，WDPk-medoids算法的聚类有效性增强，直至ε=1时相当于Wk-medoids算法的聚类效果；而对于WEPPk-medoids算法，无论噪声添加的大小，其始终都能与Wk-medoids算法有相近的聚类效果.

图10也表明WDPk-medoids算法要想达到同样的聚类有效性，其隐私泄露的风险也会相应地升高.这是由于WDPk-medoids算法是基于维度来添加Laplace噪声的，对于高维数据集，ε值越小，则数据集中添加的噪声越多、给予数据的隐私保护越强，这虽避免了敏感属性隐私泄露的风险，但随着噪声扰动量的逐步添加，超过一定界限时有可能会破坏聚类的结果，因此WDPk-medoids算法更适用于低维度的数据集.

图10 不同加权算法的NMI指标比较图

(2)噪声扰动量分析

针对噪声扰动量的仿真分析如图11所示，显然当ε为0.001时，对于know及unknow两种情况，WEPPk-medoids算法添加的扰动量远小于WDPk-medoids算法，且在不同隐私保护程度下，其添加的扰动量都很小，这表明WEPPk-medoids算法在小规模数据集上的聚类效果较WDPk-medoids算法要好.

图11 不同加权算法的AP指标比较图

6 结束语

数据挖掘中聚类分析的目的就是在各种结果集中识别并提取具有价值的信息，这一过程中的规则或算法可能会导致数据的敏感信息无意中被泄露.因此，自隐私保护技术出现后，许多聚类分析工作就纷纷基于隐私保护而开展.本文主要基于距离贡献率在隐私保护框架下对k-medoids聚类算法进行相关研究，所做的仿真工作如下表所示(加粗显示的为本文所提算法)：

表1 论文仿真分析小结

通过对聚类效用评价指标的仿真分析可见，基于数据点不同维度对于距离中心点的贡献率来对数据点聚类、添加噪声或对查询结果随机化时，与原有未加权的工作相比，可降低整个数据点所添加的噪声量、减少加噪数据的失真程度、提高聚类结果的有效性.整体而言，隐私保护下的聚类算法各有优劣，其中Wk-medoids算法的聚类效果最优、隐私保护性能最差，WDPk-medoids算法更适合大规模、低维度数据集，WEPPk-medoids算法更适合小规模数据集，以在保证用户隐私安全的同时兼顾聚类结果的有效性.

综上所述，基于距离贡献率的理念不仅可以应用到数据聚类过程中，也可以应用到隐私保护的加噪过程中，以使隐私保护框架下的聚类算法适用于不同的规模和维度的数据集及应用场景.如何择优选择聚类的初始中心点、如何设计更合适的聚类目标函数及如何优化数据集各属性之间基于距离的贡献率，这关系到聚类结果的好坏，也关系到加入隐私保护后聚类算法性能的优劣，这将是聚类划分算法在隐私保护框架下进一步研究的内容之一.