基于聚类的差分隐私民航旅客数据发布算法

丁建立，杜天天

(中国民航大学 计算机科学与技术学院，天津 300300)

0 引 言

隐私安全问题通常会阻碍用户数据分享，甚至阻碍分析从数据挖掘的价值信息[1]。数据挖掘在生活中有许多应用，聚类是一种广泛使用的数据挖掘方法之一，应用数据挖掘通常都假定可以自由访问数据集，但这是不现实的。因此需要做好隐私保护，解决由于数据发布导致的个人隐私泄露这一问题。隐私保护的数据发布已有多种方法。其中差分隐私技术可以保证在两个仅相差一条记录的数据集上运行算法能够产生相似的输出。本文目标是实现发布民航旅客数据的同时最大程度地保护隐私。差分隐私提供强大的隐私保证。大数据时代，数据无处不在，大量有价值的信息隐藏在数据中等待着研究者挖掘。数据分析者可通过对数据整理分析[2]提取有价值信息，使人们生活更加便利美好。然而在增加人民幸福感的同时，其中的问题也相应暴露出，在搜集数据的同时会携带大量隐私信息，比如，在分析不文明旅客时，会收集其身份信息、联系方式等等。如果向公众直接发布这些信息，有可能对用户构成相当大的威胁。因此，数据发布隐私保护[3]的重难点为保证发布的数据可用的同时不会泄露隐私信息。

1 研究现状

1.1 聚类的研究现状

聚类是数据挖掘中的重要工具，在数据分析、信息检索和文本挖掘等领域具有许多应用。它旨在将有限的、未标记的数据集划分为几个自然子集，同一簇内的数据相近，而来自不同簇的数据互不相同。为了实现该目的，现在已经提出了许多聚类算法，例如：基于划分、基于网络以及基于模型的聚类等等。这些聚类算法中的大多数都需要事先指定集群的数量或隐式集群的数量控制参数。对于某些应用，可以根据用户的专业知识来估计集群的数量。但是，在许多情况下，不能确定数据集的簇数。然而，聚类数量会大大影响聚类结果的好坏。因此，确定数据集中的簇数(通常标记为k)是聚类分析中的一个基本问题。现有很多估计k值的研究[4]。基于数据类型的差异，这些方法通常可以归类为用于数值数据、分类数据和混合数据的聚类算法。在数值领域，文献[5]提出了针对海量数据的k-means问题的有效近似方法。将整个数据集递归地划分为少量子集，每个子集均以其代表(质心)和权重(基数)为特征，然后将k-means算法的加权版本应用于此类局部表示，这样可以大大减少计算出的距离数。对于分类数据，文献[6]提出k-modes聚类的性能对初始聚类中心的选择特别敏感。从离群值检测的角度考虑了k-modes聚类的初始化。通过使用基于传统的基于距离的离群值检测技术和基于分区熵的离群值检测技术来计算每个对象的离群度。在初始化过程中，采用了新的距离度量标准-加权匹配距离度量标准。

文献[7]中有几种算法可以对混合数据进行聚类。但是，所有这些算法都需要预先直接或间接指定聚类数。本文提出确定混合数据集中簇数的有效方法。该方法由经过改进的k-prototype组成。

1.2 隐私保护的研究现状

隐私数据保护自隐私出现一直被人们所研究，并提出了很多保护方法，k-anonymity及其改进的算法[8]是其中较早且经典的研究成果。k-anonymity保护数据中的隐私是通过保证每个记录与至少k-1个其它记录无法区分。但是在攻击者可能获得背景知识的前提下，很容易受到攻击，之后提出的l-diversity和t-closeness，可以预防多样性攻击，但仍会受到其它攻击。差分隐私模型通过向数据中添加一定量的噪声，保证发布的数据不会泄露隐私信息，无需考虑攻击者的背景知识，因此差分隐私有更加强大的隐私保证。

近年来，差分隐私保护技术已经成为了一个备受关注的研究热点。差分隐私[9]被越来越多地用作数据分析选择的隐私保护技术，使数据既能被挖掘有价值信息的同时又保护了用户个人隐私。差分隐私数据发布有交互式框架和非交互式框架两种方式，在差分隐私初期，被应用于研究者在数据库上查询数据时，返回的查询数据满足差分隐私，然而这种形式的差分隐私应用对数据有严格的限制，交互式场景下，随着查询次数增多，所得的数据偏差会越来越大，最后所查询数据甚至完全没有参考价值，这导致它只能接受有限数量的查询。在此弊端的影响下人们研究出了非交互式场景下的差分隐私数据发布，这里的数据可对整个数据集进行差分隐私处理，使得可以发布满足差分隐私的数据集，这些数据集保证了基本的数据统计特征，研究者可以利用这些统计结果进行分析和处理，然而如果想要进一步分析，可能使用这些数据集不能够得出精确的分析结果，这是由于差分隐私需要在数据集中加入大量噪声所造成的，这些噪声既保护了数据，相应的又破坏了数据，使得数据的可用性降低，其分析价值降低。而后研究表明，合理分配隐私预算，在实现保护隐私的前提下，适当降低查询敏感度可以大大提高差分隐私数据的可用性。目前对于混合型数据发布的研究相对较少，而在实际生活中大部分数据集为混合型数据集。因此，研究针对混合型(数据类型和分类类型)数据集的差分隐私数据发布方法更加具有现实意义，可实现人们对于隐私保护的需求。文献[10]研究了两种方法在差分隐私k-means聚类中的有效性。提出了一种非交互式方法EUGkM，该方法发布了k-means聚类的差分隐私模型，验证了EUGkM算法的有效性。文献[11]中介绍了最广泛使用的聚类k-means容易陷入局部最优。并提出传统的聚类方法直接在隐私数据上执行，但是无法应对针对攻击者任意背景知识的大规模数据挖掘任务中的恶意攻击。这将导致侵犯个人隐私，以及通过系统资源和聚类输出造成泄漏。

现阶段，在非交互式场景下，针对差分隐私数据发布基本方法是基于直方图发布。这种方法可以很直观地看出数据的分布并可以近似计算数据和、差、方差以及平均数等统计信息。然而，当数据中的属性数量增加时，这种方法则会表现出严重的局限性，现在我们可以得到的数据量增大，其数据类型也在不断的增加，我们如果想要更加全方位的收集信息，信息中的属性相应的也会增加。这使得计算效率大大降低。除此之外，直方图发布方法仅仅提供了分区数据的计数，比如年龄为20～30的旅客有2000个，却无法提供具体数据，这使得我们仅仅可以看到经过统计处理的数据，数据的可用性降低。本文提出满足差分隐私的数据集发布，这将克服数据属性数量及无具体数据值的限制。为进一步提高数据集的可用性，本文提出利用聚类算法先对数据进行聚类，将一个大数据集聚类为几个子集，查询敏感度由一分化为多，使整个数据集的查询敏感度降低，进而减少噪声添加量。

针对于此，本文提出了一种基于聚类满足差分隐私的数据发布算法，可以对民航旅客信息数据集进行差分隐私保护。分析民航旅客数据，从中发现数据包括数值属性和分类属性，k-prototype可对混合数据集聚类，因此使用k-prototype聚类算法，该算法是处理混合数据类型的典型聚类算法。根据民航旅客数据集特有的性质改进了k-prototype算法中分类属性的距离计算，能够更好的对混合属性数据进行聚类，最后通过聚类算法的分组，由单一数据集分成多组数据集，降低差分隐私的敏感度，从而减少需要添加的噪声量，因此大大提高数据的可用性。

2 差分隐私定义及噪音机制

2.1 差分隐私定义

差分隐私要求数据的输出应该大致相同，即使在输入数据库中任意添加或删除任何一个元组也是如此。

定义1ε-差分隐私：设有随机算法R满足ε-差分隐私，以及任意两个相邻数据集D1和D2(在一条记录中有所不同)输出S∈Range(R)。 有

(1)

式中：参数ε是隐私预算，由公式可得出ε越小，随机算法R隐私保护程度越高。

差分隐私提供了正式且可量化的隐私保证，而不受对手的背景知识和可用的计算能力的影响。如果对于整个输出空间，对于任何一对相邻输入，生成相同输出的概率彼此之间的较小倍数内，则认为随机算法是差分隐私的。这意味着对于彼此接近的任何两个数据集，差分隐私算法在两个数据集上的表现大致相同。无论对手是否拥有先验知识，该概念都为用户提供了足够的隐私保护。在本文中，当且仅当数据集D1和D2仅相差一条记录时，我们才将两个数据集D1和D2视为邻居，D1+t表示将元组t与数据集D1相加而得的数据集，我们用D1≃D2来表示。这可以保护任何单个元组的隐私。

定义2 敏感度：对于输入数据集上的任何查询f，对于任何两个相邻的数据集D1和D2，f的敏感度为

(2)

敏感度较低的查询所需的噪声较小。差分隐私保护技术即向查询结果的数据添加噪声，对数据扰动，最终达到隐私保护的目的。

对于满足差分隐私的数据发布来说，需要多次应用差分隐私算法，差分隐私的两个组合性质可以将隐私预算合理的分配到整个差分隐私中。

性质1 序列组合性：设存在n个随机算法K，数据集D， {ki(D)|1≤i≤n} 满足εi-差分隐私，则K在D上整体满足∑εi-差分隐私。

性质2 并行组合性：设存在n个随机算法K，作用在互不相交的一组数据集 {Di|1≤i≤n}， {ki(Di)|1≤i≤n} 满足εi-差分隐私，则K在D上整体满足max(εi)-差分隐私。

2.2 噪音机制

噪声量会影响数据安全性和可用性，Laplace机制与指数机制为现有常用的噪音机制。拉普拉斯机制对数值型数据进行处理，是实现差分隐私最常用的机制。本文使用拉普拉斯机制和指数机制满足差分隐私。

定理1Laplace机制:对于任意数据集D和函数f，若满足

(3)

则算法K满足ε-差分隐私保护。其中，Δf为全局敏感度，lap(Δf/ε) 代表添加的噪声量，根据以上公式可知，查询函数f的全局敏感度越大，所需添加的噪声量越大。

定理2 指数机制:给定一个可用性函数u(D,r)， Δu为u(D,r) 的全局敏感度，O表示输出域，r表示从O中所选取一个元素，若算法K满足

(4)

则K满足ε-差分隐私。

指数机制的关键是可用性函数u(D,r)，u评估输出值r，指数机制是用指数级更高的概率选择评分更高的元素，u(D,r) 越大，r被输出的概率越大。

3 基于k-prototype聚类的差分隐私民航旅客数据发布算法

3.1 改进k-prototype算法

k-prototype是聚类中常用的模型，该算法从代表k个组的k个随机选择的点开始，计算每个记录到初始点的距离，然后将样本迭代地聚类到最近的簇，并通过聚类到这些点的样本的众值来更新这些点。直至所有的记录全部分到最近的簇。本文根据民航旅客数据的特点，改进k-prototype聚类算法。首先确定最小k值和最大k值，依次对每个k值进行实验，随机选择k个初始类中心点，根据元组间距离计算方法得到一条记录到每个中心点距离，迭代对数据集进行计算，选取距离最小的簇，得到初步聚类结果。进而选取每个簇中出现最多的元组作类中心，进行距离计算，再次选取距离最小的簇，迭代至每个元组跟上一次的簇数一样，然后计算聚类有效值，选择具有最小有效值评价的k值，输出最佳聚类结果。

(5)

分类型属性通过汉明距离计算属性差异度

(6)

针对分类型数据距离计算结果对聚类结果的影响程度，设置其在算法中的权重，以达到提高聚类精度的目的。综上所述，最终元组至中心点的距离计算公式为上述两个公式(式(5)、式(6))相加。k-prototype聚类中的损失函数计算数值型和分类性到每簇聚类中心点的距离，因此选择一个合适的损失函数y。假定设定数据集的簇为k个，使用0和1表示第m(1≤m≤k) 个聚类中是否存在元组i，0则表示存在，反之，1表示不存在。综上损失函数可以定义为

(7)

(8)

3.2 算法及差分隐私证明

将训练集随机分为多个子集，对每个子集运行聚类算法以获取输出，然后使用差分隐私对每个元组加噪，具体做法为遍历每一个元组并确定其所在簇，形成不同簇之后，总结每个簇的分类属性中的属性值集合，利用属性值集合使用指数机制对分类型属性干扰，数值型采用拉普拉斯机制方法加噪，生成满足差分隐私的数据集。此方法将查询函数的灵敏度由一整个数据集的所有记录分散至多个子集的k个记录中，一定程度上减少了数据中的噪音量，更接近于原始数据，加噪后的数据可用性大大提高。具体算法见表1。

算法流程如图1所示。

步骤：

步骤1 选择民航数据中敏感信息属性，数据清洗，并分析属性之间相关性。

步骤2 选择k最小值以及最大值。

步骤3 随机选择k个初始中心点，计算每个元组至初始中心点距离，元组中的数值型属性计算方法为每个点到k个中心点的欧氏距离，其中的分类型属性计算方法为每个点

表1 基于聚类的差分隐私数据发布算法

图1 算法流程

到k个中心点的汉明距离，最后将其分至最近的中心点。

步骤4 计算损失函数，若结果不为0，则重新选择中心点，迭代至损失函数结果为0。

步骤5 将聚类结果进行有效性评估，选择聚类效果最好的k值。得到聚类结果。

步骤6 对于数值型属性，采用Laplace机制加噪。

步骤7 对于分类型属性，生成每个簇的属性值集合，每个簇分别根据各自属性值使用指数机制选择输出值。

步骤8 生成满足差分隐私的数据集。

本文算法分为聚类分组阶段和数据发布阶段，簇的数量从k在一定范围，这导致了一系列连续的聚类结果。具体而言，在每个循环中，该方法的基本步骤包括：①使用改进的k-prototype算法和距离度量，将输入数据集划分为所需的聚类；②根据聚类评估聚类结果有效性指数；③最后，绘制了给定数据的聚类有效性指数与聚类数量的关系图。根据该图，可以目测为给定的混合数据集提供最佳的聚类数。民航旅客数据集都是混合数据集，它包含数值属性和分类属性。如果要以统一的方式处理混合数据，一般是将分类属性转换为数值属性，或者将数字属性转换为分类属性。但是，将分类属性转换为数值属性，很难将合适的数值分配给分类值。例如，如果color属性采用集合{red，blue，green}中的值，将该集合转换为{1、2、3}。在这种情况下，计算任何编码值之间的距离都是不合适的。将数值属性转换为分类属性，需要使用离散算法将实值变量的值域划分为几个区间，并为同一区间中的所有值分配一个符号。但是由于没有考虑这些值对离散值的隶属度，所以通常会导致信息丢失。因此，本文直接对混合数据进行聚类。完成聚类后，进行第二个阶段，数据中的数值型采用Laplace机制以一定概率添加噪声，通过指数机制对分类型数据实现差分隐私，从一个簇中获取属性值，以簇中每个属性值出现的概率选择值，根据输入数据，差分隐私参数和概率选择值，选择随出现概率呈指数增长。

定理3 DP-k-prototype算法满足ε-差分隐私。

根据差分隐私组合性质分析并证明：

(9)

(10)

4 实验结果及分析

本文选取民航数据中的PNR数据和离港数据。在其中选定了15个属性，包括身份、航班、位置、时间等信息组成实验所需要的数据集(表2)，并考虑异构属性类型，由48 842个记录组成。对数据集进行数据清洗，删除数据集中包含空属性以及有明显错误(如不合常规的年龄以及不存在的日期或者机场三字代码等等)的整条记录，对所有完整记录规范其中的数据，如上清洗后共有30 160个数据记录。本节仿真实验环境如下：Intel(R) Core(TM)i5-4590 CPU，4 GB内存，Windows8操作系统，在pycharm环境下进行仿真实验。

表2 数据集介绍

为方便实验，选取其中400条记录实现聚类，以及满足差分隐私的算法。每个属性之间的相关性越低，聚类效果越好，以票号为主属性，计算其与另外14个属性的相关性，如图2所示。

图2 属性之间的相关性

从图2中可看到只有两个属性之间的相关度达到了0.6，其余各个属性之间的相关度大都低于0.1，由此可见，属性之间的相关性差，依赖低，可以较好地聚类。

做好以上数据预处理工作后，进行聚类实验。

4.1 实验过程

实验时的参数设置，其中聚类实验设置k最小值为2，最大值为9，因为如果k值太大，则会造成聚类结果的实际意义不大，由于实验数据集总共有400条记录，所以将聚类簇数控制在10以内，实验结果如图3所示。

图3 不同k值下的聚类效果(指标越低越好)

图3显示了k值与聚类指标的关系，有效性指标越小，则聚类效果越好，可以看出本文改进的聚类算法比开源包的聚类算法效果要好。观察改进的聚类算法，可以明显看出k=3时，达到最低点，聚类效果最好。所以选取k=3，将数据集聚类，并按照聚类结果对数据集中的每个簇分别进行加噪。其中数值型数值进行拉普拉斯机制加噪，分类型数值进行指数机制加噪。

选择隐私预算ε为0.1时的满足差分隐私的数据集与原数据集及进行对比，表3展示了部分记录中的4个属性之间的对比。

4.2 实验评价指标

数据可用性是通过采用差分隐私技术所产生的信息损失来测量。信息损失可以通过误差平方和(SSE)量化，计算方法为满足差分隐私数据集的记录与其相对应原始数据集中的记录之间距离的平方和，误差平方和(SSE)的计算公式如下

(11)

计算数据度量时，对于数据中的数值使用标准欧几里德距离；对于字符采用汉明距离。数据隐私受到保护的标准通过信息披露来衡量。信息披露的计算方法在本文中采用计算满足差分隐私数据集正确匹配的原数据记录的百分比，即记录关联(RL)

表3 加噪前后数据集之间对比

(12)

式中：n表示原数据集的总记录数，差分隐私干扰后的数据集记录t′的RL概率Pr(t′) 为

(13)

将本文提出的算法在民航旅客信息数据集上进行实验。确定聚类算法中的k值为3，将隐私参数ε设置为 {0.001,0.002,0.003,0.004,0.005,0.006,0.007,0.008,0.009,0.01,0.02,0.03,0.04,0.05,0.06,0.07,0.08,0.09,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1,2,3,4,5,6,7,8,9,10}， 根据以上数据进行数据信息损失与信息泄露对比实验，信息损失SSE与敏感度的关系结果如图4所示。

图4 ε不同时的信息损失

当ε为0.001到0.01时，SSE较大，即使使用聚类算法分簇后再加噪，信息损失仍较高，数据可用性低，当ε大于0.01时，SSE较小，并逐渐减小后更趋于保持稳定，信息损失较低，可用性高。信息披露RL对比分析如图5所示。

图5 ε不同时的信息披露

当ε为0.001至0.1时，RL值的变化幅度较小，且RL值趋于低水平；当ε为0.1至1时，RL值的变化幅度较大且处于上升的趋势；当ε为1至10时，RL值的变化幅度最大且近乎呈直线上升。图中的这些变化是因为当ε越大时，数据中添加的噪声就越少，当数据中添加的噪声不能对数据集进行保护时，将会出现信息披露的情况。噪声越小，风险就越高，导致隐私保护能力就越弱。图4和图5结合可以看出，当ε=0.1至10时，其数据可用性差距不大，而信息披露风险会越来越高，相应隐私保护能力越来越低；当ε小于0.1时，其数据可用性越来越低，而信息披露风险则差距不大。因此当ε=0.1获得最佳效果。

5 结束语

本文提出了一种基于聚类满足差分隐私的数据发布方法，目的是在数据发布做好隐私保护的同时最大限度提高数据的可用性，对于实验输出的数据集满足差分隐私保护模型要求已在本文做出完整的数学证明。对于此方法，我们改进了k-prototype聚类算法，在原有k-prototype聚类的基础上，针对特定的数据集特点(本文采用民航旅客信息数据集)，总结出民航数据分为数值属性(比如年龄、证件号等)和分类属性(航班号、飞机场三字代码等)，对此采用不同的计算方法得出属性差异度。将差异度较小的记录分为一组，数据集经过聚类从单一数据集变为多组数据集，且每组数据集中的数据都是相似的，对这些原始数据采用差分隐私，针对数值型使用Laplace机制，对数值进行干扰，分类型使用指数机制，利用概率对分类属性进行干扰，最后对实验结果进行分析，该方法可以在信息披露较小的情况下尽量使信息损失量最小，从而在提供隐私保护的同时提高数据可用性。