模糊t-closeness隐私保护方法研究

陈晓宇 韩 斌 黄树成 朱文正

(江苏科技大学计算机学院 江苏 镇江 212000)

0 引 言

随着互联网技术的飞速发展，以数据发布和数据挖掘为主的数据共享模式正逐步成为信息化时代的发展潮流。但是，数据共享带来便捷的同时也伴随着个人隐私数据泄露[1]的风险。以数据发布过程中的隐私泄露为例，发布群体用户统计信息的过程往往伴随着某个特定用户的隐私数据的泄露。如何确保隐私数据的安全性同时又不降低数据的可利用价值，成为了当前隐私保护领域研究工作的重点。

目前使用最广泛的隐私保护方法以匿名化隐私保护[2]为主。现有的匿名隐私保护方法采用隐匿标识符属性[3](Identity Attribute，身份证号码、姓名等可以标识个体信息的属性)和泛化准标识符属性(Quasi-identifier Attribute，年龄、性别、生日、邮编等可以推演出标识个体信息的属性)的方式达到保护敏感属性(Sensitive Attribute，疾病、薪资等用户不愿透露的属性)不被泄露的目的。k-匿名和l-多样性[4]是其中最具代表性的方法。k-匿名通过控制泛化后数据集中等价类的数目，有效地防止了链接攻击。l-多样性在此基础上，对等价类中敏感属性的多样性做出约束，克服了k-匿名无法有效防止同质攻击的缺点。但是l-多样性还是存在不能有效防止偏斜攻击和相似性攻击[5]的缺陷，直到近些年t-closeness[6]被提出，这一问题才得到了解决。之后，针对t-closeness的进一步完善成为了隐私保护方法研究的热点之一，如何优化t-closeness方法使其在达到隐私目的的同时，数据仍具有较高的质量成为了关键。

t-closeness中实现匿名化的主要方式是泛化[7]准标识符属性。泛化分为值泛化和域泛化。然而无论是值泛化中将数值中部分数字隐藏，还是域泛化中将属性值映射到更大区间的过程，都伴随着信息量的丢失。为满足t-closeness的约束条件，泛化程度往往很高，随之而来的是信息损失总量的增加。针对现有t-closeness方法里泛化准标识符属性过程中信息丢失量过大的缺点，本文在模糊理论的基础上给出了隐私保护方法中数据模糊化的具体定义。并设计和实现了一套符合t-closeness隐私保护方法的模糊化过程。与泛化机制不同，本文提出的模糊化方法有效地控制了数据的信息丢失量。最后通过实验证明，模糊t-closeness隐私保护方法在提高数据可用性的同时，也增强了数据的隐私保护强度。

1 t-closeness隐私保护

t-closeness隐私保护方法在l-多样性的基础上要求数据集中敏感属性值在等价类中的分布与其在整个数据表中的分布的差异不超过阈值t。这样使得等价类中敏感值的分布与整个数据集中的敏感值的分布相似，以此防止偏斜攻击。

定义1t-closeness：如果敏感属性在一个等价类中的分布和该敏感属性在整个表中的分布之间的差异不超过某个阈值t，则称该等价类满足t-closeness。如果表中的所有等价类都满足t-closeness，则称该表满足t-closeness。

上述定义中提到的敏感属性值分布之间存在的差异指的是概率分布距离[8]上的度量差异。目前，在t-closeness隐私保护方法中最常使用的概率分布距离度量公式有EMD(earth move’s distance)、Hellinger距离和KL-散度等[9]。

给定两个分布，P=(p1，p2，…,pm)，Q=(q1，q2，…,qm)，P表示敏感属性在整个数据表中的分布，Q表示敏感属性在等价类中的分布。P与Q的差异距离表示为D[P，Q]。如果D[P，Q]

(1)

定义独立于P、Q的基准距离为F，F表示分布Q向分布P移动时做的最小工作量。记dij是P中元素i和Q中元素j的基准距离，fij表示i到j的最小工作量，那么整个转移的工作量可以表示为：

(2)

以含有|T|条记录的数据表T为例，记T={Q1，Q2，…,Qd，S1，S2，…,Sm}，其中Qi(1≤i≤d)为准标识符属性；Sj(1≤j≤m)为敏感属性，则T中含有d个准标识符和m个敏感属性。将敏感属性分为类，给出不同敏感属性类别的阈值t。本文中将敏感属性分为两类，给定第一类敏感属性阈值t1和第二类敏感属性阈值t2。同时，用Tn表示数据表T中的第n行记录。下面给出现有的t-closeness隐私保护的一种实现方法。

设第一个等价类为C1并且置为空，将表T中前k条记录放入C1中，计算C1中每一条记录的第一类敏感属性分布差异是否小于t1，接着计算第二类敏感属性分布差异是否小于t2，若不满足条件，则将这些记录移出C1。重新向C1中填入记录，直至C1中k条记录中的敏感属性分布差异均小于阈值。同理，建立新的等价类，直至剩余记录无法划分或剩余记录数量小于k，则将剩余记录逐条依次添入已建立的各等价类中计算敏感属性差异。当所有剩余记录被添入已有的等价类中且满足敏感属性差异小于阈值t时，对不同的等价类对应的准标识符属性进行泛化，最终得到满足t-closeness隐私保护的数据表T。

将泛化后的数据表T′中准标识符属性记为QI={M1，M2，…,Mm，N1，N2，…,Nn}，其中Mi(i=1,2,…,m)是分类属性，Nj(j=1,2,…,n)是数值属性。则等价类C中分类属性的信息损失为：

(3)

式中：card(Mi)是分类属性Mi泛化等级树[10]中，以泛化结果为根的子树所包含的叶子节点数，|Mi|则表示整个泛化等级树所包含的叶子节点数。

等价类C中数值属性的信息损失为：

(4)

式中：vmax和vmin分别是C中Nj的最大和最小值，|Nj|是Nj的值域。

在式(3)和式(4)的基础上可得等价类C的信息损失IL(C)，再由各等价类信息损失求和计算可得数据表T到T′的泛化过程中的信息损失：

(5)

2 模糊t-closeness隐私保护方法

2.1 方法概述

与采用泛化和隐匿技术实现隐私保护目的的传统t-closeness方法不同，本文在模糊理论的基础上设计和实现了符合t-closeness的模糊化过程，有效地克服了传统方法中信息丢失量过大的缺点。同时，给出隐私保护过程中数据模糊化和模糊等价类的定义，定义如下：

定义2数据模糊化：在对数据集里原始记录进行模糊聚类[11]的基础上，根据记录到各个类中心的隶属度选取替代点代替原始记录的过程。

定义3模糊等价类：在模糊聚类的基础上，将数据表分为若干簇，若簇中任一记录的敏感属性在该簇的分布与在整个数据表中的分布差异小于阈值t，则称该簇为符合t-closeness的模糊等价类。

基于上述给出的定义，本文设计和实现了符合t-closeness的模糊化过程。整个模糊化过程的输入是原始数据集，输出是模糊数据集。模糊t-closeness隐私保护方法的具体步骤如下：

步骤1：根据准标识符属性值，对输入数据集进行模糊聚类，获取聚类的簇。

步骤2：计算敏感属性在簇和整个数据集中的分布，根据定义1中关于敏感属性分布的约束条件调整簇中的记录点的划分得到新的簇，即模糊等价类。

步骤3：计算各个模糊等价类的隶属度矩阵，采用隶属度限幅元素平均值法[12]获取模糊聚类的后各个元素的替代点集合。

步骤4：利用替代点的集合模糊准标识符属性值，输出模糊化后的数据集。

2.2 方法的实现

2.2.1 获取簇中心及其对应隶属度矩阵

本文使用模糊C-均值(FCM)算法[13]，通过优化目标函数得到每个记录点对所有类中心的隶属度，不断修正簇中心点，最终获取最优的簇中心点及其对应的隶属度矩阵。

将原始数据集作为待聚类的输入对象，记每一行记录的特征个数为p。它的输出是一个c行n列的矩阵U，其中c表示聚类的数目，n表示数据集中元素的个数。矩阵中任一列表示该元素到各个类的隶属程度。还有一个输出各个类的聚类中心向量集合V，即各个簇中心的集合。V一共有c个元素，每个元素是p维的。具体步骤如下：

步骤1：初始化聚类中心Ci，i=1,2, …,c。

步骤2：根据初始化的类中心点计算隶属度矩阵U。

步骤3：计算目标函数。如果目标函数小于某个确定的阈值，或者相对上次目标函数结果的改变量小于某个阈值，则算法停止，输出当前隶属度矩阵。

步骤4：修正聚类中心点，计算当前隶属度矩阵。返回步骤2。

其中步骤1里聚类中心点的个数c与泛化机制中泛化属性值到指定j个区间中的j的作用类似，决定着数据匿名化的程度。c越大，即簇中心点越多，最终模糊化程度越小，信息丢失量越小。可以通过优化目标函数得到c的取值，也可由隐私保护的执行者根据模糊化数据程度的期望来选定。

FCM的目标函数为：

(6)

式中：隶属度值uij表示元素j对类别i的隶属程度，dij是元素i到中心点j的欧式距离。m是模糊化参数，通常取2。整个目标函数Jm(U，V)表示的就是各个点到各个类的加权距离之和。

(7)

(8)

根据上述推导结果，选定参数c。接着在此基础上获取原始数据集的聚类输出，即最终的簇中心点及其对应的隶属度矩阵。与传统的泛化和隐匿方法不同，步骤1中根据模糊聚类划分簇的过程并没有改变初始数据集中的数值。

2.2.2 划分模糊等价类

在步骤1划分的簇的基础上，计算敏感属性在整个数据表和簇中的分布，分别用P=(p1，p2，…,pm)，Q=(q1，q2，…,qm)表示。接着在EMD度量方法的基础上，验证各敏感属性分布P和Q差异距离D[P，Q]是否小于设定阈值t。若差异距离大于阈值t，则将该记录根据最小工作量进行再划分，直至簇中任一记录的敏感属性在该簇的分布与在整个数据表中的分布差异小于阈值t。

再划分的具体过程：从中心点为Ci的簇开始，若该簇不符合模糊等价类的定义，则将簇中敏感属性分布大于阈值的记录划分到最邻近的簇，保证最邻近的簇的差异距离也小于阈值。否则将记录重新划分到次邻近的簇再计算差异距离，直至中心点为Ci的簇和添入记录的簇都符合模糊等价类的定义。选取下一个不符合模糊等价类定义的簇，重复上述过程，直至所有簇满足定义3。

2.2.3 选取替代点

经由获取簇中心及其对应隶属度矩阵和划分模糊等价类的两个步骤，可以得到敏感属性符合t-closeness隐私保护要求的数据表。计算该数据表的隶属度矩阵U。为了最大可能地利用元素与各个类之间的隶属度信息，本文在选取替代点时采用了隶属度限幅元素平均值法。用给定的隶属度参数值a对隶属度函数曲线进行切割，再对切割线上部的隶属度对应的所有记录点中的属性值进行平均，得到的平均值作为替代点的值。替代点用作该元素的模糊化结果在表中替代初始元素值。

图1 元素i的隶属度函数切割图(a=0.23)

数值属性的平均值指的就是算术平均值。分类属性的平均值则是指在语义不变的基础上模糊描述[14]的内容。与泛化机制中扩大分类属性概括范围的方式不同，模糊化过程中对分类属性的操作是：在模糊聚类后对Mi属性隶属度限幅取值，得到Mi临近的取值集合，在语义上给出该集合的模糊语言描述。例如，地点属性值为“苏州”的数据，在泛化机制中通常被泛化为“苏南”、“江苏”或者更大的范围，而在本文给出的模糊化方法中，该记录点聚类的结果在该属性值上临近集合{“苏州”、“无锡”、“常州”}，则根据集合内容的分析，给出语义上的描述“无锡附近”。该语义上的模糊描述内容即为替代点在该属性上的替代值。

将属性值及其临近集合作为模糊化语义结构树的叶子节点，例如“苏州”：{“苏州”、“无锡”、“常州”}，给定模糊化语义结构树。与泛化机制里的层次结构相似，随着模糊化层次的增加，数据模糊化的程度随之增加，隐私保护效果提升，信息丢失量变大。

记“苏州”：{“苏州”、“无锡”、“常州”}为A1；“苏州”：{“苏州”、“昆山”、“张家港”}为A2；“苏州”：{“苏州”、“无锡”、“常州”、“昆山”、“张家港”}为B1；图2从左到右的过程即是构造模糊化语义结构树的过程。

图2 模糊化语义结构树构造过程

2.3 性能分析

2.3.1 效果分析

在泛化机制中，对分类属性的泛化是根据固定的泛化层次结构进行的。同一个属性值根据隐私保护的需求可以选择不同程度的泛化层次对数值进行泛化。而在本文的模糊化过程中，以属性值及其临近集合作为叶子节点的模糊化语义结构树里，每个叶子的父节点并不由属性值唯一确定，而是与其临近集合也相关。相同的属性值聚类后获得的临近集合不一定相同，因此语义描述的结果也不一定相同，即模糊化后的值不同。这样不仅在语义上模糊化了分类属性值，同时隐藏了属性值与模糊化语义结构的关联关系，增强了隐私保护的效果。

此外，相比泛化机制中将原始属性值映射到更大范围的做法，模糊化语义描述的过程不仅考虑了原始属性值，而且还考虑到原始记录点与周围记录点的位置关系。因此，模糊化语义描述的结果更接近原始记录，数据更具有可用性。

2.3.2 信息损失量分析

本文定义和设计的符合t-closeness隐私保护的数据模糊化过程，采用通过模糊聚类获取元素隶属度矩阵的方式选取替代点。在式(2)和式(3)的基础上给出了计算数据模糊化后信息量损失的函数L。同样以含有|T|条记录的数据表T中准标识符属性QI={M1，M2，…,Mm，N1，N2，…,Nn}为例，数据表T到T″的模糊化过程中的数值属性的信息损失为：

(9)

式中：vf是数据模糊化后得到的替代点上Nj属性的值，vr则表示该属性初始数值，|Nj|表示该属性的值域。分类属性的信息损失计算：

(10)

card(Mi)为敏感属性值临近集合的元素个数，|Mi|表示模糊化值对应的临近集合中元素的个数。由式(9)和式(10)可得数据表T到T″模糊化过程中信息损失为：

(11)

综上所述，可以知道同一数据表经由本文模糊化隐私保护后的信息损失总量较小，即L(T,T″)≤L(T,T′)，数据更具可用性。

2.3.3 安全性分析

与较传统的泛化准标识符属性不同，模糊化后的数据隐匿了等价类的分类信息。攻击者无法获取模糊等价类的分类信息，从而不能通过比对模糊等价类中的敏感属性分布来获取更多的信息，即模糊t-closeness方法能够有效地防止链接攻击。

此外，用模糊语言描述处理分类属性的方式使得同样的属性值在不同记录中可能对应的模糊化值不一样，且模糊化后的属性值的词义界限不明确，属性值对上下限的接近程度无法定量。因此，在拥有很大不确定性的情况下，攻击者无法通过已知的背景知识来缩小数据指向特定用户的范围，从而无法获取数据表中额外的记录信息，即模糊t-closeness方法能够有效地防止背景知识攻击。

3 实 验

本次实验使用Java语言编程，编程环境为MyEclipse10，实验的环境配置为2.40 GHz i5-2430M、4 GB内存、Windows7 32位操作系统。实验采用两个数据集重复试验，其中数据集“ADULT”源于美国成年人口普查。该数据集拥有30 162个实例，9个属性，属性为{sex，age，race，marital-status，education，native-country，workclass，occupation, salary}。另一个数据集“OCCUPATION”则是第五次人口普查数据中全国各行业人口的职业分布数据，该数据集包含了15个行业的7种职业大类的人口分布数据。为了验证本文提出的模糊t-closeness隐私保护方法在安全性和数据可用性方面的优势，下面将在信息损失量、直方图发布和数据安全风险评估几个实验的基础上对方法进行分析。

3.1 信息损失量

为了分析模糊t-closeness隐私保护方法中数据信息损失量随着准标识符属性维数改变而变化的规律，本文实验分析了信息损失量随着维度增加而变化的折线图。以数据集“ADULT”和“OCCUPATION”为实验对象，图3和图4分别给出了两组实验数据下采用泛化机制的t-closeness方法中信息损失量随着维度增加而变化的折线图。其中参数t取值0.15。

图3 “ADULT”信息损失量变化对比图

图4 “OCCUPATION”信息损失量变化对比图

由实验结果可知，随着属性维度的增大，数据信息损失量不断增大。同等条件下，即同一属性在t-closeness中的泛化域个数等于模糊t-closeness方法中模糊等价类个数时，模糊t-closeness方法的信息损失量要小于t-closeness方法的信息损失量。

3.2 直方图发布

快速而准确地获取数据分布的梗概是数据分析与查询的主要任务，直方图发布[15]是近似估计数据分布的主要技术之一。以数据集“ADULT”中敏感属性婚姻状况(Marital-status)为对象，发布不同年龄阶段中婚姻状态为有配偶(Spouse-present)的人数统计数据，实验分析了本文隐私保护方法模糊t-closeness的发布精度。图5展示了原始数据与输出的保护数据的直方图发布结果对比。

图5 各年龄段有配偶人数统计结果发布对比图

以数据集“OCCUPATION”中制造业的人口职业分布数据发布为例，图6展示了原始数据与输出的保护数据的直方图发布结果对比。

图6 制造业人口的职业分布数据发布对比图

由图5和图6可知，本文提出的隐私保护方法下的数据仍具有较高的可用性，直方图发布具有很高的精度。

3.3 安全风险评估

与t-closeness隐私保护下的数据一样，模糊t-closeness隐私保护下的数据也存在被同质攻击的风险。在模糊t-closeness方法中，同样的属性值存在被模糊化成多种模糊值的可能，但当这些模糊值对应的敏感属性一样时，攻击者还是能判断出原始属性值对应的敏感属性内容。这种情况下，敏感属性信息就会被泄露。本文以数据集“ADULT”中{age，education，native-country，workclass}为准标识符属性，{occupation}为敏感属性，实验分析比较了l-多样性、模糊t-closeness方法与t-closeness所受同质攻击的情况，见图7。

图7 不同匿名方法受到同质攻击的记录数

分析实验结果可知，与l-多样性的隐私保护方法相比，t-closeness和模糊t-closeness方法抵御同质攻击的能力更强。其中本文提出的模糊t-closeness隐私保护方法在同质攻击下泄露的记录数更少，具有更好的隐私保护效果。

4 结 语

目前，使用最为广泛的匿名隐私保护方法主要包括k-匿名、l-多样性和t-closeness等。其中t-closeness方法保证数据安全、阻止攻击的能力优于k-匿名、l-多样性，但存在信息损失量较大的缺点。在这些方法中，实现匿名化的主要方式是泛化和隐匿数据。本文在模糊理论的基础上，给出了t-closeness隐私保护方法中数据模糊化的相关定义，设计和实现了具体的模糊化过程。通过实验验证了本文提出的模糊t-closeness方法相比t-closeness方法，数据具有更强的安全性，且隐私保护过程中信息损失量较小。

在本文设计的模糊化过程中，模糊化语义结构树是分类属性进行模糊化的关键。如何结合自然语言处理的知识给出合理、较优的模糊化语义结构树将是本文下一步研究的重点。