基于混合聚类的k-匿名数据发布算法

方 凯，史志才，2，贾媛媛

(1.上海工程技术大学 电子电气工程学院，上海 201620； 2.上海市信息安全综合管理技术研究重点实验室，上海 200240)

随着移动互联网的快速发展，各种传感器以及无线终端设备采集了海量的数据[1]。为了挖掘大数据的潜在价值，享受大数据带来的方便和快捷，需要对数据进行发布[2]。如果待发布的数据不经过隐私保护处理被直接发布，那么攻击者可能会利用各种途径窃取用户的敏感信息，造成用户的隐私泄露和财产损失[3]。因此，在保护用户数据隐私的同时减少数据发布的信息损失，提高数据发布的质量，已成为当前研究的热点问题[4]。

传统的数据发布隐私保护模型主要分为k-匿名模型[5]、l-多样性模型[6]和t-closeness[7]模型。在这些经典的隐私保护模型基础上，许多算法相继被提出[8-10]。近年来，随着机器学习在各领域的广泛应用，将聚类算法引入数据发布隐私保护技术引起了广泛关注[11-12]。文献[13]提出了一种基于k-means聚类的隐私保护方法。文献[14]提出了一种基于多属性泛化聚类实现k-匿名的算法。文献[15]提出了一种针对混合属性的聚类算法。现有的利用聚类算法实现k-匿名模型的方法未考虑到离群点噪声[16]对聚类结果的影响，且采用传统分类树[1]进行距离度量和属性泛化会造成严重的信息损失。此外，利用k-means均值聚类实现k-匿名的算法虽然复杂度低、效率较高，但是由于其初始聚类中心点的选取具有不确定性，因此易导致算法陷入局部最优，降低了算法的稳定性。

在分析了现有的数据发布隐私保护技术的基础上，本文提出了一种混合聚类k-匿名数据发布算法。该算法通过数据集的密度特征，选择初始聚类中心点，使用划分聚类算法进行迭代，从而实现最优聚类来保证算法的运行效率。此外，该算法利用密度阈值剔除部分离群点噪声，改进了传统聚类算法的距离度量方式。相对于传统的分类树泛化方法，本文引入桶泛化算法[17]，减少了数据的信息损失。在同等隐私保护级别的情况下，对比了KACA算法[18]、本文提出的混合聚类k-匿名算法、基于k-匿名的k-means聚类算法[12]的信息损失和运行时间，结果证明本文提出的混合聚类k-means算法有效改善了聚类效果，降低了数据发布的信息损失。

1 基于聚类的k-匿名算法

在数据发布领域，聚类算法可以通过数据之间的相似度对数据集进行等价类划分，降低生成的等价类信息的损失。对于待发布数据，可将其属性划分为标识符属性(Individually Identifying Attribute，IIA)、准标识符属性(Quasi-Identifier Attribute，QIA)以及敏感属性(Sensitive Attribute，SA)[5]。标识符属性用来特定区分某一个个体，例如电话号码、身份证号码等，在数据发布之前需将其进行删除。准标识符属性是一些组合起来可以识别某个个体的属性或者属性集合，例如邮政编码、年龄、性别等属性的集合。敏感属性是指包含个人敏感信息的属性，例如疾病、收入等，需要根据实际情况进行设定。

基于聚类的k-匿名问题可归结为：将一个数据集D分成n个等价类，使得每个等价类至少包含k个数据记录，则称其满足k-匿名模型。其中等价类是指在经过泛化匿名操作之后，在准标识符上具有相同属性值的一组数据集合。为了满足匿名模型的要求，一般需要对原始数据在准标识符属性值上进行泛化操作，其基本思想是通过概括的属性值去代替原有的具体的属性值，从而在一定程度上实现对隐私数据的保护。但是，泛化操作容易导致泛化过度，使得数据的精度有所下降。已有研究表明，使用聚类方法实现的匿名隐私保护可以有效减少泛化操作造成的信息损失[4]。

现有的基于聚类实现k-匿名模型的算法主要以k-means聚类算法为主。k-means是一种基于划分的聚类算法，其流程图如图1所示。由图可知，k-means聚类算法选择初始中心点的方式是随机选择，并且没有对数据集中的噪声数据进行处理，导致聚类结果不佳，稳定性差，易陷入局部最优。

图1 k-means聚类算法流程图

2 基于混合聚类的k-匿名算法

为了解决现有基于聚类的k-匿名数据发布算法存在的问题，本文提出了基于混合聚类的k-匿名数据发布算法。如图2所示，该算法主要由4个部分组成：第1部分是初始中心点选取过程；第2部分是聚类迭代过程，生成最优聚类；第3部分是聚类调整过程，通常需要使等价类中的数据记录介于k和2k-1之间才会有更好的聚类效果[4]；第4部分是泛化生成匿名数据集过程。

图2 混合聚类k-匿名算法框架

算法基本步骤如下：

输入数据集D，k-匿名参数k。

输出匿名数据集E。

步骤1计算需要划分的等价类或聚类的个数m=n/k(m取整数部分)，其中n为数据集D中所有记录个数，k为k-匿名参数；

步骤2利用密度聚类思想，根据数据集密度特征选出m个最优初始聚类中心点{S1，S2，S3，…，Sm}，同时剔除离群点噪声干扰；

步骤3对数据集中每一条数据记录，计算其与步骤2生成的所有聚类中心点之间的欧氏距离，并把它加入到距离最近的聚类中心，生成一个簇Ci(m>i>0)。直到所有的数据记录都被分配到相应的簇中，计算新簇的中心点，并对旧的中心点进行更新；

步骤4重复步骤3，直到聚类中心不再发生变化或达到终止条件；

步骤5对每一个簇的大小进行调整，使其满足k-匿名原则。定义一个集合R，若簇Ci(m>i>0)中数据记录数大于k，则将该簇中距离聚类中心点最远的|Ci|-k条数据记录加入集合R中；若簇Ci(m>i>0)记录数小于k，则将集合R中距离簇Ci最近的k-|Ci|条数据记录加入簇Ci中，最后将集合R中剩余的记录分别分配到距离最近的簇中。其中|Ci|表示第i个簇中所有记录的个数；

步骤6将以上生成的簇进行泛化操作得到等价类E={E1，E2，E3，…，Em}。

2.1 距离度量方法

针对混合型数据集[19]，需要对数值型数据和分类型数据分别进行距离度量。数值型数据一般采用基于k-means的距离度量方式。分类型数据以往都是先建立分类树，然后根据分类树进行距离度量。由于这种方式需要提前建立分类树，并且泛化过程会造成巨大的信息损失，因此在本文中，针对分类型数据，采用基于k-modes[11]算法的分类型数据距离度量方式。下面分别介绍两种针对不同数据类型的度量方法的具体计算式。

k-means算法采用欧式距离作为距离度量方式，假设样本xi=(xi1，xi2，xi3，…，xin)与xj=(xj1，xj2，xj3，…，xjn)，其计算式如式(1)所示。

(1)

因为不同属性的属性值有不同的数量级，所以对数值属性进行距离计算之前，需要对属性进行归一化处理，使得每个属性的权重相同。假设年龄属性的区间为[0～90]，工资属性的区间为[1 000～10 000]，如果不进行归一化处理，那么在进行距离度量时工资属性占的权重会过大，导致聚类中心点的偏移。进行归一化处理后，每个属性的范围都在[0～1]之间，便于对多维属性的数据记录进行距离度量。

k-modes是一种常用的对于离散属性数据集的聚类算法。假设对于某一分类型属性的属性值a和b，若属性值相同，则距离计为0；若属性值不同，则计为1/l，其中l为该分类属性属性值的个数，具体距离计算方式如式(2)所示。

(2)

2.2 初始聚类中心点选取

本文提出的基于混合聚类的k-匿名数据发布算法依据数据集的密度特征来选择初始聚类中心点，选出的中心点分布均匀，符合数据集的分布特点，避免了随机性对聚类结果的影响。选取步骤如下：

输入数据集D，k-匿名参数k。

输出初始聚类中心点。

步骤1计算出每个数据点的密度，并进行从小到大排序；

步骤2选取其中密度最大的点作为第1个聚类中心点；

步骤3将附近距离最近的k-1个点聚成一个簇，把它们放到已分类的集合中；

步骤4从剩下的未分类的集合中，继续挑选密度最大的数据点作为第i(0

步骤5直到S个聚类中心点被选出。

2.3 密度计算及离群点检测

密度计算是密度聚类的核心步骤，通过数据集的密度特征选取聚类中心点并且剔除数据集中的离群点噪声。若离群点噪声不经处理就直接进行聚类泛化过程，会使得生成的等价类信息损失增大。为了减少离群点对聚类结果的影响，需要对离群点进行检测剔除[19]。假设数据集中的每一条数据记录当作一个对象，关于对象r的k距离是使r到它的最邻近的k个对象的最大距离，该距离需满足以下两个条件：

(1)对于至少k个对象o′∈D，有distance(r，o′)≤distance(r，o)。其中D为原始数据集，distance表示两个对象之间的欧式距离；

(2)最多有k-1个对象o″∈D，使得distance(r，o″)

图3中r的k距离(k=9)是r与o之间的距离，可以看出r的9个最近邻到r的距离均小于或等于r到o的距离，有8个邻居到r的距离小于o到r的距离。

图3 对象r的k距离

在数据隐私表D中，r是D中的一个记录。设 distK(i)(0

(3)

对象r的密度表示为

(4)

若r的密度denK(r，D)越大，则distKNN(r，D)越小，即r与它周围的其他记录之间距离越近。本文选择密度较大的点作为聚类的中心点进行迭代，符合数据集的分布规律，可以减少聚类过程的信息损失。离群点一般都是比较孤立的点，与周围邻近距离较大，也就是密度较小的点。因此，可以通过设定密度阈值对离群点进行剔除。

2.4 桶泛化算法

数据泛化是数据发布最常用的隐私保护方法。通过泛化操作可以将数据的信息进行概化，扩大数据的区间，或者进行语义上的概括，从而隐藏属性的真实值，来获得数据的隐私保护。传统的泛化方法是采用分类树进行的，这种方法需要提前对属性建立泛化层次。如图4所示为职业属性的泛化层次分类树。

图4 职业属性分类树

分类树是通过最小公共子树节点进行泛化的，泛化的层次越高，其信息损失越大。例如，属性值工程师和律师的最小公共子树为专业人员，那么经过泛化之后的属性值为专业人员。

采用分类树进行属性泛化容易导致过度泛化。针对分类型属性，本文采用桶算法进行泛化。桶泛化算法与传统泛化方式不同，桶泛化算法将同一等价类的每个准标识符属性的所有属性值都放在一个名为桶的抽象容器内。例如在某等价类中，对于职业属性，其属性值有工程师和律师，那么对于职业属性经过桶算法泛化后的属性值为{工程师，律师}，数据记录的属性值被完整保留，并且降低了数据的信息损失。同时，对于等价类中的每条数据记录，对应桶内的属性值的概率是相等的，例如上述例子中职业是工程师和律师的概率都是1/2，可以避免攻击者通过斜偏攻击获取背景知识。

2.5 信息损失度量方法

信息损失度量[16]是对聚类算法的聚类效果的直观评价，聚类效果越好，数据的信息损失越小。信息损失度分析是对数据发布质量的度量，这里将数据分成数值型和分类型分别进行介绍。

对于待发布的数据集中的每一条数据记录，当数据记录的准标识符属性类型为数值型时，其信息损失计算方法为

(5)

式中，Vmax为某一准标识符属性在其等价类的最大值；Vmin为该标识符属性在同一等价类的最小值；|Nj|为准标识符属性的全局区间宽度。假设在数据表中某一属性的值域范围是[20～30]，则其区间宽度是10；某一条记录经过数据匿名处理之后，该记录的属性值为[20～22]，则对于该记录的这一属性在该等价类的信息损失度为2/10=0.2。

当数据记录的准标识符属性类型为分类型时，其信息损失计算方法为

(6)

式中，|cardCi|为某一准标识符属性在其等价类的所有可能取值种类数；|Ci|为该属性的全局取值种类数。假设disease属性的取值范围为{cancer，head disease，tracheitis}，某一条记录经过匿名处理后disease的属性值为{cancer， head disease}，则该记录diease属性的信息损失度为2/3。

当数据记录既有数值型属性，又有分类型属性时，其中数值型属性的个数为n，分类型属性的个数为m，则对于整个等价类来说，其信息损失为

(7)

式中，E为等价类；|E|为等价类中数据记录的个数。整个数据集D的平均信息损失度为

(8)

式中，|D|为数据集中所有记录的条数。

3 实验与结果分析

3.1 实验环境和数据集

本算法采用Python语言实现，实验硬件配置如下：Intel(R) Core(TM) i5-3337u CPU @1.80 GHz，操作系统为Windows 7，内存8 GB。实验所用数据为UCI的Adult数据集(http://archive.ics.uci.edu/ml/)。该数据集包括部分美国人口普查数据，是隐私保护和数据挖掘研究中最常用的标准测试数据集。实验中，对比了KACA算法、基于k-means聚类的k-匿名算法和本文提出的混合聚类k-匿名算法。

首先对数据集进行归一化预处理，使得各属性的值控制在[0～1]范围内，且假设每个属性的权重都为1。实验数据集信息如表1所示。

表1 实验数据集信息

3.2 结果分析

图5所示为当k-匿名参数值不断增大时，3种不同算法的信息损失度对比情况，其中横坐标为k-匿名参数k的取值，纵坐标为平均信息损失度。当k取值从10到70变化时，随着k值增大，数据的信息损失度也不断增大。这是因为数据集的大小不变，k增大导致等价类的个数减少，每个等价类的数据记录个数变多。从图中可以发现，在不同的k值情况下，本文提出的混合聚类k-匿名数据发布算法相对于其他两种算法的信息损失度小，聚类效果更好，具有明显的优势。

图5 不同k值的信息损失度对比

图6为在准标识符属性个数不断增加时，3种算法的信息损失度的对比情况。横坐标为准标识符的个数，纵坐标为平均信息损失度。当准标识符属性QI个数不断增大时，3种不同算法的信息损失度也逐渐增加。这是因为随着准标识符数量的增加，聚类的难度越大，划分等价类的条件越高，从而导致需要泛化的程度越高。同时可以看到，在QI较小时，3种算法的信息损失度相近。当QI=7时，本文所提出的算法相对于其他两种信息损失度有明显区别，这说明数据量越大或需要划分的准标识符越多时，本文算法可以有效减少信息损失，提高数据可用性。

图6 不同准标识符个数下的信息损失度对比

图7为在不同k-匿名参数情况下，3种算法的执行时间对比，其中横坐标为k-匿名参数值，纵坐标为算法的执行时间。随着k值增大，3种算法的执行时间都呈下降趋势，这是因为当匿名参数k增大时，最终生成的等价类变少，聚类所花费的时间也就减少。当k值相同的情况下，KACA算法执行时间最短，k-means聚类算法和混合聚类的k-匿名算法的执行时间差距不大，但随着参数k的不断增大，两者逐渐逼近。虽然传统k-匿名算法的时间复杂度较小，执行时间快，但是静态数据发布一般都是线下处理然后在发布，没有严格的时间要求。当达到较好的数据发布质量时，损失较小的算法执行时间仍在可接受的范围内。

图7 不同k值对应的算法执行时间对比

4 结束语

本文将密度聚类和距离聚类相结合，提出了一种混合聚类k-匿名数据发布隐私保护算法。实验结果表明，在满足k-匿名的前提下，该算法能够有效提高数据发布质量，减少信息损失，尤其在准标识符属性越多的情况下效果越好。但是本文在k-匿名模型的基础上，只考虑了数据匿名发布的数据可用性，在安全性方面，其隐私披露风险是1/k。因此，在下一步的工作中，将尝试在减少信息损失的同时进一步提高隐私保护的安全性。