基于自组织聚类的多敏感属性数据发布算法

， ,

(1.北京电子科技学院 研究生部， 北京 100070； 2.西安电子科技大学 计算机学院， 陕西 西安 710071)

随着数据挖掘技术的飞速发展以及数据拥有者对隐私数据泄露问题的高度关注，隐私数据发布技术不断进步。如何保证隐私数据在发布后敏感信息不易被攻击，同时数据可挖掘性能够得到极大保证，针对这一问题，国内外学者给出了多种可行方案。

l-匿名模型[1]、l-多样性模型[2]和l-closeness模型[3]是比较经典的3种隐私保护模型。基于这些模型，许多算法被相继提出[4-10]。这些算法在处理单敏感数据发布时虽然有可观的抗攻击性，但是不适用于多敏感数据发布。针对多敏感属性数据发布隐私保护，杨晓春等[11]提出了基于有损链接的多维分桶技术，其将每一敏感值映射到对应分桶，按照策略分组，实现组内满足l-多样性。其他基于有损链接很多算法被提出[10-12]，但有损链接会破坏非敏感属性与敏感属性间的关联关系，影响到发布后数据的信息可挖掘性。与有损链接的方法对比，无损链接的方法较好地保存了敏感数据与非敏感数据关联性。基于无损链接的算法较少，文献[13]中提出了基于l-多样性模型的无损链接发布算法,但不适用于敏感属性值多样性差异过大的情况。为了解决该问题，本文中提出了(l,x,w)多样性模型，该模型通过约束等价组内敏感属性多样性及均匀性来实现匿名保护，并基于该模型提出了多敏感属性数据发布的基于信息熵的l-多样性聚类(entropy basedl-diversity clustering, EBLC)匿名算法。该算法按照非敏感属性对数据进行聚类后，在同簇中按照策略生成满足多样性的等价组，对等价组内元组泛化后进行发布。对该算法进行仿真实验，通过运行效率、信息损失等实验结果验证算法的匿名效果。

1 基本概念

对于一般待发布数据，针对其属性可划分为个人标识属性(individually identifying attribute, IIA)、准标识符属性(quasi-identifier attribute, QIA)以及敏感属性(sensitive attribute, SA)。IIA用于直接识别个人身份信息，QIA可结合外部数据识别个人信息，SA包含个体隐私信息。

设T={Q1,Q2, …,Qp,S1,S2, …,Sd}(p为分类性属性个数，d为数值性属性个数)为待发布数据集，其中Qi(1≤i≤p)表示准标识符属性，|Qi|表示敏感属性Qi在T中不同值的个数。Sj(1≤j≤d)表示敏感属性， |Sj|表示敏感属性Sj在T中不同值的个数。T中有n个元组ti(1≤i≤n)，T的元组数目用|T|=n表示，对任意元组ti∈T，用ti、X表示元组ti在属性X上的取值。

文献[10]中提出了基于有损链接的(l1,l2, …,lm)模型，文献[13]中提出了(l,m)多样性模型。在文献[10]中，(l1,l2, …,lm)模型与噪声添加配合使用才能抵抗概率攻击，但是引入的噪声污染了数据，而文献[13]中(l,m)模型不适用于敏感属性值个数差异过大情况，特别是，当某一个敏感属性取值为2时，此时l的选取受到该敏感属性候选值个数限制。本文中提出(l,x)多样性模型用以解决此类问题。

定义2((l,x)多样性)gi为T的一个等价组，对于任意敏感属性Sj，多样性变量x为

x=min{l, |Sj|}

。

(1)

若等价组gi在敏感属性Sj上的不同取值数不小于x， 则称等价组gi满足(l,x)多样性； 若对任意gi∈T，gi均满足(l,x)多样性， 则称T满足(l,x)多样性。

敏感属性信息如表1所示。当l=3时，显然年收入的属性个数已经无法满足l-多样性。

表1 敏感属性信息

尽管也可以使用(l1,l2, …,lm)模型进行数据匿名发布，但是该模型需要引入噪声，这会污染数据。若使用(l,m)模型则需要调整使l=2，这样使得发布后数据的安全性降低，无论使用以上哪种模型都不合适；而当使用(l,x)多样性模型在生成等价组时，只需要使敏感值多样性小于l的敏感属性满足x多样性即可。表2所示为一个l=3时的满足(l,x)多样性的等价组。

2 算法介绍

2.1 聚类生成

近些年来，基于聚类的敏感数据发布算法不断发展[7,9-10,14-17]，但大多是基于有损链接或者单敏感属性。其中文献[18]中提出的(t, sim, dif)算法在抗概率攻击以及同质攻击方面均有良好表现；但是，由于该算法是从敏感属性部分生成聚类构造等价组，同时，该算法为单敏感属性数据发布算法，因此无法解决多敏感数据发布问题。基于文献[18]中通过聚类寻找等价组思路，本文中提出了针对多敏感属性数据发布的EBLC算法，由非敏感属性生成聚类构造等价组，通过对原数据进行去噪点以及聚类划分，在聚类基础上生成满足目标约束的等价组，保证生成等价组有全局最优信息损失与抗攻击性。

表2 多样性为3时满足(l, x)多样性的等价组

2.1.1 距离定义

本文中主要针对分类型数据及数值型数据进行研究， 根据不同类型数据， 定义不同的距离度量公式。

定义3(非数值型属性距离) 设属性X为分类型属性，按照不同取值构建属性值分层树，设xi表示该属性的某一取值，则距离函数为

Dclassi(xi,xj)=|1/flevel(xi,xj)-1/flevel(xi)|+

|1/flevel(xi,xj)-1/flevel(xj)| ，

(2)

式中：flevel(xi)表示分类值xi在分层树中的层级；flevel(xi,xj)表示值xi、xj在分层树中最小祖先节点的层级；Dclassi(xi,xj)表示属性值xi与xj的分类距离。

定义4(数值型属性距离) 设属性X为数值型属性，xi为该属性的某一取值，则距离函数为

Ddigit(xi,xj)=|xi-xj|/(max{X}-min{X})，

(3)

式中：Ddigit(xi,xj)表示数值属性值xi与xj的距离；max{X}表示属性X最大值；min{X}表示属性X的最小值。

定义5(元组距离) 元组ti、tj(i≠j)为表T的2个元组，则元组间距离函数为

(4)

2.1.2 聚类的生成算法

使用k均值的方法进行聚类，考虑到传统k均值方法的k值以及初始点的设定对聚类结果的影响，本文中使用自组织k均值算法(self-organizingk-means algorithm, SOKM) 。

算法1：自组织k均值算法。

输入：元数据集表T、 停止条件δ。

输出：数据集聚类信息表T′。

1) 令聚类数目Cnum=1，T′记录T的簇划分以及簇中心距离信息，令可移动元组数目Cmove=|T|，对原数据集T使用二分k均值算法进行二分;

2) 遍历当前所有分簇，对每一个分簇进行二分聚类，对比其他簇中元组与其原簇质心距离与新生簇质心的距离，将该元组划入距离近的一簇，统计每一次二分后移动的元组数目，选择移动数目多的簇进行二分；

3) 令Cmove等于元组最大移动数目，令Cnum+1，并更新T′；

4) 检查Cmove与δ，当Cmove小于δ时停止分裂，输出T′，否则重复步骤2)和3)直到满足停止条件。

考虑到离群点对匿名算法的影响，在聚类部分对离群点进行处理，计算所有簇的半径，依据半径设定离群点判定阈值，当超出该阈值则判定为离群点，划入簇0中。

2.2 算法核心介绍

2.2.1 (l,x,w)多样性

信息熵常被用来描述信源的不确定度。为了提升发布数据抗同质攻击以及概率攻击的能力，在生成等价组时使用信息熵作为策略之一。

(5)

定义7(敏感标准熵) 设gi为一满足(l,x)多样性的等价组， 对于任意敏感属性Sj， 其标准熵函数为

(6)

当等价组gi中敏感属性Sj的多样性数目为x时，可知其敏感标准熵为其信息熵的最大值，此时该属性的不确定度最大。

定义8((l,x,w)多样性) 设gi为一满足(l,x)多样性的等价组， 对于任意敏感属性Sj，若等价组中该敏感属性敏感信息熵与敏感标准熵之比不小于w，则称等价组gi满足(l,x,w)多样性，若T中所有等价组均满足(l,x,w)多样性，则称T满足(l,x,w)多样性。

EBLC算法即对原始数据集T在聚类划分得到T′后， 分簇寻找满足(l,x,w)多样性的等价组， 最后对同一等价组按分组中心泛化， 最终得到发布数据集T*。 对于泛化后产生的信息损失， 给出以下定义。

定义9(等价组信息损失) 设gi为一满足(l,x,w)多样性的等价组，t为等价组中的元组，t′为等价组组中心，定义等价组泛化信息损失函数为

(7)

定义10(全局信息损失) 设T*为数据集处理后得到的满足(l,x,w)多样性的待发布数据集，其等价组集合G={g1,g2, …,gs}，全局信息损失函数为

(8)

定义11(平均信息损失)T*为数据集T处理后得到的满足(l,x,w)多样性的待发布数据集，Iinfoloss(T*)为全局信息损失，则平均信息损失函数为

ηinfoloss(T*)=Iinfoloss(T*)/|T*|

，

(9)

式中|T*|为数据集T*的元组数目。

2.2.2 基于信息熵的多样性聚类匿名算法

算法2：EBLC算法。

输入：元数据集T、 聚类信息T′、 多样性l、 敏感熵比值w。

输出：可发布数据表T*。

1) 获取表T所有敏感属性的多样性集L={l1,l2, …,ld}；

2) 由T′得到所有的簇集合信息C={c1,c2, …,ck}，按照簇半径进行升序排序得到半径信息矩阵R；

3) 分别计算所有簇中心距离，并按照升序排序，得到簇间距离信息矩阵N，令T*为空，并依据T′得到所有簇的半径升序矩阵Cradius；

4) 选择当前簇集中半径最小的簇作为等价组生成簇ci，令等价组gtmp为空;

5) 当ci中元组数目大于l时，按照第1次添加l条元组，第1次之后每次添加1条元组的原则向空的gtmp中添加记录，每次添加后检查gtmp是否满足(l,x,w)并删除ci中对应元组；

6) 当gtmp满足(l,x,w)多样性时将gtmp中元组添加到T*，并清空gtmp；

7) 重复步骤5)和6)直到ci为空并从C中删除当前ci；

8) 此时若gtmp非空则选择剩余簇中质心与当前ci质心最近的簇作为新的ci，若gtmp为空则对照Cradius与C选择C中半径最小的簇最为新的ci；

9) 重复步骤5)到8)直到C为空，得到T*，对T*中元组按照不同等价组质心对其进行泛化后发布T*。

2.3 基于信息熵的多样性聚类匿名算法复杂度分析

本算法对数据匿名处理分为2个部分即聚类及等价组的生成。

聚类部分的每一次二分可分为记录重划分以及簇二分2个部分， 这2个部分每一次的时间复杂度分别为O(n-ni)和O(nit),其中ni为当前遍历簇大小，t为二分聚类的平均迭代次数； 遍历所有簇的时间复杂度为O[nt+n(ktmp-1)]， 其中ktmp为每一次遍历时的分簇总数； 聚类部分的时间复杂度为O(nkt+nk2)， 其中k为最终的分簇数目。

等价组生成部分复杂度最坏情况为O(n2)，最优情况为O(n)，因此，EBLC算法复杂度最坏情况为O[n(kt+k2+n)]，最优情况为O[n(kt+k2+1)]。

2.4 基于信息熵的多样性聚类匿名算法抗攻击分析

由于等价组满足(l,x,w)多样性， 因此任意等价组内元组t， 对任意敏感属性Si， 可以保证至少存在x-1条元组与t在属性Si上的取值不同，保证了发布后数据的抗同质攻击能力。

3 实验结果与分析

3.1 实验方案

为了验证EBLC算法有效性，通过仿真实验，对EBLC算法进行实现，从执行时间、信息泄露、信息损失等方面评估EBLC算法的性能，实验结果为30次实验的平均值。硬件环境为Intel(R) Core(TM)i3-3240CPU@3.40GHz 4.00GB RAM。实验软件环境为Windows10平台、 MATLAB2016a软件。

3.2 实验数据

使用匿名算法研究领域通用的标准测试数据集，即UCI Machine Learning Repository中的Adult标准数据集。

实验选取的属性集合如表3、 4所示

表3 实验数据集信息

表4 敏感属性候选信息

3.3 实验结果

3.3.1 运行效率

图1所示为敏感属性m=3、多样性l=4、信息熵比率w=0.75时，数据量级改变条件下算法的运行时间。观察发现：随着数据量的增加，算法的运行时间随之增加；同时，等价组生成部分的运行时间较短，聚类部分的运行时间长，但运行时间仍然在可以接受范围内。

图1还给出了平均信息损失随数据量增长时的变化情况。从图中发现，数据量级的改变对平均信息损失没有明显的影响。

3.3.2 敏感属性数目改变时算法信息损失

图2所示为数据量为4 000、多样性l=4时，EBLC算法在不同敏感属性以及信息熵比下信息损失的变化情况。从图中可以发现，在不同敏感属性下，当信息熵比率控制在0.65时其平均信息损失不超过0.45，表明算法在抗攻击性以及信息损失方面均有良好表现。同时可以看出：在相同信息熵比下， 平均信息损失与敏感属性数目呈现正相关关系； 在敏感属性数目相同时， 平均信息损失也与信息熵比呈正相关关系。

图1 基于信息熵的l多样性聚类算法的运行时间

图2 敏感属性数目变化时的信息损失

为了使新增加的敏感属性满足多样性要求，在同等条件下，当敏感属性数目增多时，原等价组元组可能需要添加新的元组，这会造成组内非敏感属性的泛化程度提高，带来了更多的信息损失。同时，当信息熵比率上升时，等价组中同一属性的多样性分布均匀度需要提升，也会导致原等价组元组数目的增加，造成非敏感属性泛化程度提高，导致平均信息损失的增加。

3.3.3 多样性数目改变时算法信息损失

图3所示为数据量为4 000、敏感属性个数m=3时，EBLC算法在不同多样性以及信息熵比下信息损失的变化情况。从图中可以发现，在不同多样性条件下，当信息熵比率控制在0.65时，数据的平均信息损失不超过0.5，表明算法在抗攻击性以及信息损失方面均表现良好。同时可以看出：在相同信息熵比下， 平均信息损失与多样性数目呈现正相关关系；在多样性数目相同时，平均信息损失也与信息熵比呈正相关关系。

图3 多样性数目变化时的信息损失

在信息熵相同、多样性数目增长时，原等价组需要添加新的多样性元组，会造成泛化程度提高，引起平均信息损失的增加。当多样性数目不变而信息熵比提高时，为了提高等价组内敏感属性多样性的均匀性，也需要向等价组添加新的元组，造成平均信息损失的增加。

4 结语

本文中基于对原数据集进行聚类分簇后从同簇内元组生成满足(l,x,w)等价组的思路，提出了一种针对多敏感属性数据隐私发布的ELBC匿名算法，并对其进行仿真实验。实验结果表明：该算法有效降低了发布后数据敏感信息易受到同质攻击以及概率攻击的风险，提升了数据发布的安全性；算法在不同敏感属性数目以及不同多样性数目条件下对数据进行匿名发布后，数据的信息损失仍然能保证在可靠范围内，较大程度保证了发布数据的可挖掘价值。不足之处是本文中等价组内属性的l-多样性为语法的多样性，在下一步工作中，将会更多地进行基于语义多样性的算法研究。