为了在数据共享过程中保护用户隐私, 同时尽可能地保持数据完整性, 研究人员提出了数据匿名技术^[1]. 数据匿名技术主张在不泄露用户隐私的前提下, 对数据进行尽可能少的、不可逆的匿名化操作, 降低攻击者获取用户敏感信息的概率, 同时保证数据的真实性. 匿名后的数据可以安全地共享给第三方, 甚至发布到网络中.

大部分现有数据匿名研究主要针对关系数据或者事务数据, 不能有效处理同时包含两类数据的关系-事务数据. 其中, 关系数据指包含若干关系型属性的数据, 这些属性中联合起来能够唯一标识用户身份的属性被称为准标识符;事务数据指包含若干取值的集合型数据, 其取值中通常包含用户的敏感信息. 在真实的数据应用中, 绝大部分的数据集都属于关系-事务数据, 例如诊疗数据中的年龄、性别和邮编属于关系数据, 而病人的多次诊疗记录属于包含用户敏感信息的事务数据. 在关系-事务数据匿名发布中, 由于关系数据和事务数据均有可能受到链接攻击, 需要同时匿名这两部分数据. 为此, 文献^[2]首次针对这个问题提出了(k, k^m)-匿名模型, 通过对等价类同时施加k-匿名和k^m-匿名约束来保护用户隐私. 但是, 该文献提出的匿名模型过于严格, 按照该模型匿名关系-事务数据会造成严重的数据缺损, 无法保障数据可用性.

针对关系-事务数据匿名中的数据可用性问题, 本文提出(k, l)-多样化模型, 通过等价类上的l-多样化约束和事务数据上的k-匿名约束, 保证用户隐私不被泄露. 在此基础上, 本文设计并实现了满足该模型的APA (anatomize and partition anonymization)和PAA(partition and anatomize anonymization)算法, 用真实的公开数据集对其进行测试和评估, 并与相关工作进行对比. 本文的主要贡献如下:

(1) 提出了(k, l)-多样化匿名模型, 通过等价类上的l-多样化约束和事务数据上的k-匿名约束, 保证关系-事务数据中的用户隐私不被泄露.

(2) 针对(k, l)-多样化模型, 设计并实现了两种满足该模型的匿名算法APA和PAA, 并给出了相应的数据缺损评估方法;用真实的公开数据集对APA和PAA算法进行了评估和分析, 并与相关工作进行对比.

本文第1节介绍相关工作. 第2节介绍数据匿名基本概念和定义. 第3节介绍关系-事务数据匿名技术, 提出(k, l)-多样化匿名模型, 并给出满足该模型的APA和PAA算法. 第4节分析和评估实验结果. 第5节总结全文.

1 相关工作

近年来, 能够保证数据集真实性的数据匿名技术得到了许多研究者的关注. 根据匿名对象不同, 可以将现有研究工作分为三大类:关系数据匿名、事务数据匿名和关系-事务数据匿名. 3类研究工作都包含两方面的内容:数据匿名模型和数据匿名算法^[3]. 其中, 数据匿名模型研究主要针对特定的泄露风险, 在理论上建立约束模型, 为数据匿名算法提供理论依据和指导;数据匿名算法研究主要在数据匿名模型约束下设计高效的匿名算法, 力求在不泄露用户隐私的前提下, 以尽可能低的数据缺损完成匿名. 在特定模型约束下, 以最小数据缺损代价实现的匿名被称为最优匿名. 但是在现有数据匿名模型约束下, 实现最优匿名均为NP-hard^[4], 所以常用的数据匿名算法均为近似算法.

(1) 关系数据匿名

在关系数据匿名中, 一般将数据属性分为两类:联合起来能够唯一标识用户身份的准标识符和包含用户敏感信息的敏感属性. Sweeney和Samarati首先指出准标识符上链接攻击带来的隐私泄露问题, 并提出k-匿名模型^[1]--通过保证每条记录都有至少k-1条记录与它在准标识符上无法区分, 来确保数据受到链接攻击时不会泄露隐私信息. Meyerson等人在文献^[4]中证明了当k≥2时, 通过最小的泛化实现数据k-匿名的问题是NP-hard. 文献^{[5, 6]}分别讨论了高维k-匿名问题和多约束k-匿名问题. k-匿名没有对敏感属性进行约束, 当大部分记录具有相同的敏感属性取值时, 攻击者能够以较高的概率推断出用户的敏感信息. 因此, Raymond等人^[7]在k-匿名的基础上提出了(a, k)-匿名, 保证发布数据在满足k-匿名的同时, 每个等价类中与任意敏感属性取值相关的记录不超过1/a. 文献^[8]提出了安全性更高的l-多样化, 保证等价类中任意敏感属性取值的出现频率不高于1/l, 使得攻击者获取到用户敏感属性的概率不高于1/l;文中还提出约束更强的entropy-l-多样化, 要求每个等价类中的敏感属性信息熵不低于l. 文献^[9]在l-diversity的基础上考虑敏感属性的分布问题, 并提出了t-Closeness, 保证不同等价类中的敏感属性分布尽量接近于全局分布. 文献^[10]指出在数据增量发布的过程中, 现有数据匿名模型会造成隐私泄露, 并提出了m-Invariance模型. 文献^[11]提出了个性化隐私保护(personalized privacy preservation)的匿名模型, 为用户提供不同粒度的隐私保护. 文献^[12]提出了面向匿名查询的数据匿名模型--差分隐私(differential privacy), 通过保证相差一条记录的不同集合有较大的概率具有相同的查询结果来保护匿名查询中的用户隐私. 需要注意的是, 数据匿名模型并不是越严格越好. 数据匿名模型要求越严格, 匿名后数据集的安全性越高, 但是实现匿名的代价也越大, 导致数据可用性越差.

与数据匿名模型不同, 数据匿名算法的研究主要侧重于针对特定的数据匿名模型设计高效的数据匿名算法, 在满足匿名模型的基础上保证匿名后数据的可用性. 文献^[13]给出了基于全局泛化空间完全搜索的k-匿名算法MinGen. 文献^[14]给出了近似比为O(logk)和O(blogk)的近似算法(b≥1), 其中, 近似比为O(blogk)的算法通过牺牲一定的近似比实现了更高的匿名效率. 文献^[15]给出了基于全局泛化空间剪枝的k-匿名算法Incognito, 该算法通过动态规划的方式可以有效减少搜索空间. 虽然全局泛化方法的搜索空间较小, 生成的匿名化数据格式统一、便于分析, 但是会造成较高的数据缺损. 为此, 文献^[16]提出了局部泛化技术, 通过进一步细化泛化粒度, 降低数据缺损. 文献^[17]在之前泛化算法的基础上提出了多维度泛化技术Mondrian, 通过多维度划分, 将泛化粒度再次缩小. 随着数据维度的增加, 泛化技术造成的数据缺损会迅速增加^[5], 为此, 文献^[18]提出了基于有损分解的数据匿名方法Anatomy, 通过有损分解弱化准标识符和敏感属性的关系, 降低攻击者获取到敏感信息的概率. 文献^[19]提出了基于泛化和有损分解的匿名方法ANGEL, 通过结合泛化和有损分解, 大幅度降低数据缺损.

在匿名查询方面, 差分隐私技术得到了广泛的关注^{[20, 21]}. 针对现有差分隐私方法中数据可用性差的问题, 文献^[22]提出了基于Wavelet的Privelet方法, 提高了匿名数据集的范围查询精度. 针对差分隐私无法有效保护数据关系的问题, 文献^[23]提出了面向非交互式网络数据的差分隐私方法.

(2) 事务数据匿名

与关系型数据不同, 事务数据由于其维度不固定, 匿名方式有很大的不同. Ghinita等人^[24]将事务数据划分为公开的事务数据和敏感的事务数据, 并提出利用带状矩阵来压缩高维稀疏事务数据;在此基础上, 他们设计了一种基于泛化和置换的数据匿名算法. 文献^[25]针对发布敏感事务数据导致隐私泄露的问题提出了(h, k, p)- coherent模型, 通过同时约束敏感和非敏感事务数据保证用户隐私不被泄露. 在攻击者获取的背景知识维度不超过m的前提假设下, 文献^[26]提出了k^m-匿名, 保证攻击者背景知识维度不超过m时, 获取到的组合数大于k;在此基础上, 他们给出了Apriori Anonymization算法, 并通过count tree结构降低了算法复杂度. 文献^[27]发现, k^m-匿名无法保护长度大于m的组合;同时, 基于全局泛化的Apriori Anonymization算法会造成严重的数据缺损. 为了解决这个问题, 文中提出了满足k-匿名的局部泛化的算法Partition, 通过自顶向下划分和回溯来保证数据被近似最优的分组, 从而降低数据缺损. 文献^[28]在Apriori Anonymization算法的基础上设计并实现了基于格雷码的局部泛化算法, 降低了数据缺损.

(3) 关系-事务数据匿名

关系-事务数据同时包含关系数据和事务数据, 并普遍存在于关系数据库中. 发布该类型数据能够为更复杂的数据应用(如并发症分析、购物偏好分析等)提供支持. 但是, 上述研究工作主要针对单一型数据匿名, 无法直接应用到关系-事务数据中, 否则会造成隐私泄露^[2]. 为此, Poulis等人在文献^[2]中首次针对关系-事务数据的匿名问题展开研究, 提出了(k, k^m)-匿名模型, 通过保证每个等价类在关系数据上满足k-匿名, 同时在事务数据上满足k^m-匿名的方式来保护用户隐私, 并给出了满足该模型的RMR等算法. 但是, 该文献提出的(k, k^m)-匿名模型和算法存在3个方面的问题:

1) 仅能保护事务数据中长度不超过m的组合, 对于长度超过m的组合不施加任何保护;

2) 该模型没有多样性约束, 无法防御同质攻击^[8];

3) 对于等价类要求过严格, 导致严重的数据缺损.

其中, 第3个问题尤为严重. 例如, 表 1为诊疗数据, 表 2为按照(2, 2²)-匿名要求发布的表 1数据. 虽然攻击者无法通过关系数据和事务数据唯一标识Bob并获取他的疾病信息, 但是, 为了形成满足(2, 2²)-匿名的等价类, 匿名算法泛化了大量的数据, 导致事务数据全部缺损. 此外, 由于采用了基于聚类的匿名算法和Apriori Anonymization算法, RMR算法运行效率非常低.

针对上述问题, 本文拟从两方面展开研究:

1) 更合理的数据匿名模型:通过保护任意长度的事务数据组合, 并增加多样性约束来增强匿名模型安全性;通过放宽对等价类的约束来提高数据可用性.

2) 更高效的数据匿名算法:采用更高效的匿名子算法, 并采用有损分解的方式匿名关系-事务数据, 提高匿名效率.

2 基本定义

本文针对关系-事务数据展开研究, 该类型数据普遍存在于关系数据库系统中. 为了简化问题, 我们将关系-事务数据(RT-data)中的所有关系属性作为准标识符(quasi-identifier, 简称QI), 将事务数据均作为敏感属性(sensitive attribute, 简称SA). 同时, 我们按照文献^[2]的方式, 假设每个用户对应一条关系-事务数据记录, 且在该记录中, 事务数据中的取值不重复^[26-28]. 本文用T表示需要匿名的数据集, n表示T中的记录数, T^*代表匿名化之后的数据, t表示T中某一条数据记录, t_r表示t的关系数据取值. 由于用户在事务数据上的取值没有先后顺序且不会重复, 可以用集合表示, 我们称其为事务数据组合, 记为c, 并用t_c表示t中的事务数据组合. 我们用A表示属性, d代表关系数据属性数目, 则T中共有d+1个属性, 记为A₁, A₂, …, A_d, A_d+1;其中, A₁, A₂, …, A_d表示关系数据属性, A_d+1表示事务数据属性. 本文所用符号见表 3.

定义 1(等价类(equivalence class))^[17]. 数据表T中, 在关系数据上具有相同取值的所有记录形成等价类, 记为EC.

定义 2(事务数据桶(transaction data bucket)). 数据表T中, 在事务数据上具有相同取值组合的所有记录构成事务数据桶, 记为TBucket.

EC和TBucket是分别根据关系数据(准标识符)取值和事务数据组合是否相同对数据集T进行的划分. 假设T中有x个EC和y个TBucket, 则$\bigcup\limits_{i=1}^{x}{E{{C}_{i}}}=\bigcup\limits_{j=1}^{y}{TBucke{{t}_{j}}}=T, $且∀i≠j, EC_i∩EC_j=∅, TBucket_i∩TBucket_j=∅.

定义 3(泄露风险(disclosure risk)). 攻击者通过关系数据或者事务数据取值, 唯一标识用户身份并获取到敏感信息的概率.

根据Zhou等人^[3]的研究, 数据的隐秘性由其泄露风险决定:泄露风险越高, 隐秘性越差. 本文将泄露风险分为关系数据泄露风险和事务数据泄露风险, 并取较大值作为泄露风险. 由于EC内的记录在关系数据上无法区分, 故关系数据泄露风险与|EC|成反比. 另一方面, 由于TBucket内的记录在事务数据上无法区分, 故事务数据泄露风险与|TBucket|成反比. 根据这个性质, 我们定义T中任意记录t的关系数据泄露风险Risk(t_r)为

$Risk({{t}_{r}})=\frac{1}{|E{{C}_{i}}|}$

(1)

定义t的事务数据泄露风险Risk(t_c)为

$Risk({{t}_{c}})=\frac{1}{|TBucke{{t}_{j}}|}$

(2)

定义t的泄露风险Risk(t)为

$Risk\left( t \right)=max\left( Risk\left( {{t}_{r}} \right), Risk\left( {{t}_{c}} \right) \right)$

(3)

其中, t_r∈EC_i, t_c∈TBucket_j. 以表 1为例, 根据公式(1)~公式(3), 由于Bob的事务数据组合$\langle $a₁, b₂$\rangle $只出现一次, TBucket大小为1, 故事务数据泄露风险为100%, 即攻击者通过事务数据唯一标识Bob的概率是100%. 同时, 由于Bob在关系数据上的取值$\langle $18, M, 12000$\rangle $只出现一次, 故其在关系数据上的泄露风险为100%, 即攻击者通过关系数据上的背景知识唯一标识Bob的概率为100%. 最终, Bob在表 1中的泄露风险为100%. 为了保护用户隐私, 需要保证数据集的泄露风险低于某个阈值.

目前, 实现数据匿名的方法主要有两类:数据泛化和有损分解. 前者通过一定的方式模糊数据取值, 使得原有等价类不断合并, 最终满足匿名要求;后者则通过分组和表切分的方式, 将原有的一一对应关系破坏为一对多关系, 使得每个等价类至少对应多个不同的SA取值.

定义 4(数据泛化(generalization)). 在数据处理过程中, 用模糊的、范围的取值取代精确取值的过程被称为数据泛化.

泛化实质上是对数据的粗粒度化, 会造成不可逆的数据缺损. 为了降低数据缺损, 同时保留数据的语义, 需要建立泛化层次结构(generalization hierarchy), 如图 1所示.

现有的数据泛化技术主要分为两类:关系数据泛化^[12-16]和事务数据泛化^[23-26], 分别如图 1(a)和图 1(b)所示. 关系数据泛化中, 每个属性对应不同的泛化层次, 泛化过程实质是寻找泛化层次中能够覆盖相应取值的最低公共子节点^[1], 例如, 将18和19岁泛化为[15, 20);与之相反, 事务数据泛化一般只有一个泛化层次, 泛化过程实质为寻求泛化层次中能够覆盖所有取值的最低公共切割^[26-28], 例如将$\langle $a₂, b₂$\rangle $泛化为$\langle $A, B$\rangle $, 将$\langle $a₁, a₂$\rangle $泛化为$\langle $A$\rangle $. 随着数据的维度增加, 数据泛化造成的缺损会急剧增加, 最终可能会丢失所有信息^[5]. 为此, Xiao等人^[18]提出了有损分解技术.

定义 5(有损分解^[18]). 通过将数据表T(QI, SA)划分为QIT(QI, GID)表和ST(GID, SA, Count)表, 将原有的QI与SA的一一对应关系转化为通过GID维持的一对多关系, 保证攻击者无法通过准标识符获取到用户敏感属性取值.

有损分解不会改变原有等价类, 但是通过切分数据表T, 将原有的QI与SA的一一对应关系打破, 使得每个等价类对应多个SA取值. 攻击者只能通过自然连接QIT和ST的方式来重构数据, 但是根据自然连接的性质, 重构会产生很多并不存在于T中的记录, 导致获取敏感信息的几率大为降低. Xiao等人^[18]还提出了一种基于有损分解的匿名算法Anatomize, 通过保证每个GID对应的敏感属性取值不小于l, 使得数据集满足l-多样化.

3 关系-事务数据匿名

本节中, 我们首先提出(k, l)-多样化模型, 通过等价类上的l-多样化约束和事务数据上的k-匿名约束, 保证用户隐私不被泄露. 在此基础上, 本文设计并实现了满足该模型的匿名算法.

3. 1 (k, l)-多样化匿名模型

为了在关系-事务数据匿名中保护用户隐私, 需要同时约束关系数据和事务数据. 此外, 为了防御同质攻击^[8], 需要增加多样性约束. 因此, 匿名后的关系-事务数据集T^*至少需要满足以下3个条件:

(1) 事务数据组合不能唯一标识用户, 避免事务数据上的链接攻击;

(2) 关系数据不能唯一标识用户, 避免关系数据上的链接攻击;

(3) 任意等价类中的事务数据组合满足多样化约束, 避免同质攻击.

目前, 常用的匿名模型^{[1, 8, 27]}只能满足条件(1)或者条件(2). 文献^[2]虽然提出了满足条件(1)、条件(2)的模型, 但是该模型无法保护长度超过m的事务数据组合^[27], 也无法防御同质攻击;并且, 该模型对等价类的要求过于严格, 会造成严重的数据缺损. 为了解决上述问题, 本文在前人研究的基础上, 提出满足条件(1)~条件(3)的(k, l)-多样化模型, 通过同时约束关系数据和事务数据, 保证用户隐私不被泄露;在此基础上, 适当放宽对等价类的约束, 提高数据可用性. 为了便于理解, 我们首先介绍(k, l)-多样化模型的两个子模型.

定义 6(事务数据k-匿名(k-anonymity on transaction data)) ^[27]. 如果数据表T^*中的每个TBucket中至少包含k条记录, 则称该数据表T^*满足事务数据k-匿名.

在事务数据k-匿名约束下, 每个TBucket均不小于k, 保证事务数据组合上的泄露风险不高于1/k. T^*满足条件(1), 但不满足条件(2)、条件(3), 攻击者仍然可以通过关系数据唯一标识用户.

定义 7(关系-事务数据l-多样化(l-diversity on RT-data)). 如果数据表T^*中, 攻击者通过事务数据组合关联到等价类中任意事务数据组合的概率不高于1/l, 则称该数据表T^*满足关系-事务数据l-多样化.

在关系-事务数据l-多样化约束下, 每个等价类至少包含l个不同的事务数据组合, 且任意事务数据组合在等价类中的出现频率不高于|EC|/l, 故关系数据上的泄露风险不高于1/l. T^*满足条件(2)、条件(3), 但不满足条件(1), 攻击者仍然可以通过事务数据组合唯一标识用户.

定义 8((k, l)-多样化((k, l)-diversity)). 如果T^*满足以下条件, 则称T^*满足(k, l)-多样化:

(1) T^*中任意TBucket中至少包含有k条记录;

(2) T^*中任意EC中, 攻击者通过事务数据组合关联到等价类中任意事务数据组合的概率不高于1/l.

如上所述, (k, l)-多样化对关系-事务数据集施加了双重约束:约束(1)保证每个事务数据组合至少对应k个用户, 使得T^*满足条件(1);约束(2)保证攻击者通过事务数据组合关联到等价类中任意事务数据组合的概率不高于1/l, 使得T^*满足条件(2)、条件(3). 从而保证T^*中的关系数据和事务数据不会泄露用户隐私. 根据以上性质, 我们还可以得到引理1和引理2.

引理 1. 如果数据集T^*满足(k, l)-多样化, 则T^*中任意事务数据组合必然满足事务数据k-匿名.

证明:为了证明引理1, 我们假设T^*满足(k, l)-多样化, 且T中存在事务数据组合c不满足事务数据k-匿名, 则c所在TBucket_c中的记录数必然小于k, TBucket_c不满足定义8(1), 与假设矛盾.

引理 2. 如果数据集T^*满足(k, l)-多样化, 则T^*中任意等价类必然满足关系-事务数据l-多样化.

证明:为了证明引理2, 我们假设T^*满足(k, l)-多样化, 且T^*中存在等价类x不满足关系-事务数据l-多样化, 则x中必然存在某个事务数据组合c, 并且c在x中的出现频率超过|x|/l, 使得攻击者能够以高于1/l的概率关联到c, 不满足8(2), 与假设矛盾.

定理 1. 如果数据集T^*满足(k, l)-多样化, 则攻击者通过事务数据唯一标识T^*中任意用户身份的概率低于1/k, 通过关系数据唯一标识用户的概率低于1/l.

证明:根据引理1, 攻击者通过事务数据组合唯一标识用户身份的概率低于1/k;根据引理2, T^*中的任意等价类满足l-多样化. 故攻击者通过关系数据唯一标识用户身份的概率低于1/l.

在定理1的保证下, 即使攻击者获取到了用户的所有事务数据取值或者关系数据取值, 也无法唯一标识用户身份, 攻击者通过事务数据或者关系数据获取用户隐私的概率低于max{1/k, 1/l}. 参数k和l没有约束关系, 故可以根据数据集的实际特性分别选取. 表 4为满足(k, l)-多样化的表 1匿名后版本(由PAA或APA匿名表 1可得), 其中, k=2, l=3. 故攻击者通过关系数据和事务数据唯一标识用户的概率不高于1/2, 用户隐私得到保护.

需要注意的是, (k, l)-多样化并不要求每个等价类均满足事务数据k-匿名. 因此, 即使T^*满足(k, l)-多样化, 其中的等价类也未必满足事务数据k-匿名. 通过适当放宽对等价类的约束, (k, l)-多样化能够更好地保障数据可用性. 与文献^[2]中的(k, k^m)-匿名相比, (k, l)-多样化不存在m的限制, 对事务数据的约束更强;其次, 通过多样化约束, 可以防御同质攻击;最后, 由于(k, l)-多样化对于等价类的约束更宽松, 能够更好地保证数据可用性.

3.2 APA 和PAA 算法

现有的大部分匿名算法都不支持关系-事务数据, 无法同时保证关系数据和事务数据不泄露用户隐私. 仅有的匿名算法RMR因为采用了基于聚类的匿名算法和Apriori Anonymization算法, 计算开销非常大. 为了高效地匿名关系-事务数据, 本文在现有研究的基础上, 基于Partition算法^[27]和Anatomize算法^[18]设计了APA和PAA算法. 通过融合关系数据和事务数据匿名技术, 实现关系-事务数据匿名. 最终发布的数据存储在RT(relational table)和TT(transaction table)中, RT中包含关系数据和GID, TT中包含事务数据和GID. 其中, Partition算法通过自顶向下的方式对数据集进行划分, 再通过局部泛化对数据进行泛化, 可以保证泛化后的数据满足事务数据k-匿名, 算法复杂度为O(n²);Anatomize算法则通过对分 桶后的敏感属性进行多样化分组, 可以确保每个等价类至少对应l个不同的敏感属性取值, 使整个数据集满足l-多样化, 算法复杂度为O(n).

为使这两种算法符合关系-事务数据匿名需求, 我们对它们进行了以下优化:为Anatomize算法增加了对事务数据的支持, 按照事务数据组合建立不同的TBucket, 并优化了剩余记录处理机制;为Partition增加了对关系-事务数据的支持, 并在原有算法的基础上优化了数据分组模块, 提高了算法效率. 限于篇幅, 本文不对改进后的Anatomize和Partition做过多的描述.

由于Anatomize和Partition在匿名过程中会互相影响, 直接调用两种算法并不能实现关系-事务数据匿名. 为此, 我们设计的协调机制如下:

· 首先, 为了避免子算法覆盖彼此的分组结果, 我们参照ANGEL^[19]的设计思路, 同时保留两种数据划分方式, 即EC和TBucket并存的方式, 使得两种子算法能够相对独立的匿名关系或者事务数据部分.

· 其次, 我们有效地利用了两种算法的中间结果, 提高了算法效率. 例如, Partition算法的中间结果B能够被Anatomize算法直接利用, 省去了根据事务数据组合建立桶的阶段.

· 最后, 为了避免Partition算法降低Anatomize分组的多样性, 导致匿名度降低, 我们设计了分组合并阶段, 通过分组合并, 使所有分组满足关系-事务数据l-多样化, 保证算法的匿名度.

在此基础上, 我们根据不同的匿名顺序设计了APA和PAA算法, 其伪代码如下所示:

算法 1. APA (anatomize and partition anonymization).

Input:k, l, 原始数据集T.

Output:包含关系数据和GID的RT和包含事务数据和GID的TT.

//利用改进的Anatomize对数据进行匿名化

将事务数据组合相同的记录划分到同一个TBucket中, 得到TBucket组, 记为B;

利用Anatomize从B中生成分组G;

利用Partition对事务数据组合进行k-匿名化.

//分组合并

取出G中事务数据组合小于l的组合, 放置于CG中;

While CG不为空

 从CG中Pop一个分组g;

 If CG中存在与g合并之后事务数据组合大于l的g′

  从CG中Pop g′;

   g=g∪g′;

  将g加入到G;

 Else

  将g合并到G中任意分组中;

//有损分解

按照Anatomize的方式对G内数据进行有损分解, 得到RT和TT;

Return RT和TT

算法 2. PAA (partition and anatomize anonymization).

Input:k, l, 原始数据集T.

Output:包含关系数据和GID的RT和包含事务数据和GID的TT.

//利用改进的Partition对事务数据匿名

利用Partition对事务数据组合进行k-匿名化, 使得T中的记录自然地形成TBucket组, 记为B;

利用Anatomize从B中生成分组G;

//有损分解

按照Anatomize的方式对G数据进行有损分解, 得到RT和TT;

Return RT和TT

如算法1和图 2(a)所示, APA分为3个阶段:有损分解、事务数据匿名和分组合并. 首先, 利用改进的Anatomize算法对T进行划分, 保证每个EC至少包含l个不同的事务数据组合, 复杂度为O(n);随后, 利用改进后的Partition算法对事务数据进行k-匿名化, 保证所有TBucket中的记录数大于k, 使其满足事务数据k-匿名, 复杂度为O(n²). 但是Partition会降低数据集中事务数据组合的多样化特性, 导致第1阶段划分的分组内事务数据组合减少, 部分分组的事务数据组合数目会小于l(不再满足l-多样化). 例如图 2(a)中, Partition后数据集由4-多样化变为了2-多样化. 所以, 最后一个阶段, 我们利用分组合并算法对事务数据组合数目小于l的分组进行合并, 使得所有分组均满足l-多样化, 其复杂度为O(n²). 最终APA的复杂度为O(n²), 远低于RMR的O(n⁴).

如算法2和图 2(b)所示, PAA分为两个阶段:事务数据匿名和有损分解. 首先, 利用改进的Partition算法对T中所有事务数据组合进行k-匿名化, 保证所有TBucket中的记录数大于k, 使其满足事务数据k-匿名, 复杂度为O(n²). 由于Partition算法使用了事务数据泛化, 匿名化后事务数据组合相同的记录会自动地形成TBucket. 所以, 可以直接利用改进后的Anatomize算法对Partition算法形成的TBucket进行l-多样化划分, 复杂度为O(n). 与APA不同, 按照这个顺序进行匿名化, 两种算法可以有机地结合起来, 各司其职, 互不干扰. 最终, PAA的复杂度为O(n²), 远低于RMR的O(n⁴).

与文献^[2]中的RMR相比, APA和PAA选择了线性的Anatomize算法和自上而下的Partition算法, 计算开销远远低于RMR中基于聚类的关系数据匿名算法和Apriori Anonymization算法. 因此, APA和PAA的复杂度更低, 运行效率更高. 同时, 由于APA和PAA没有采用k^m-匿名, 能够更好地保护用户隐私.

4 实验验证和分析

本节中, 我们利用真实的公开数据集来评估和分析APA和PAA的有效性及其性能, 并与文献^[2]中提出的RMR进行对比.

4. 1 实验设置

实验所使用的数据集为INFORMS(https://sites.google.com/site/informsdataminingcontest/)数据集. INFORMS数据集包含16个属性、102 578条用户记录(包含58 568个用户)、317 872条诊疗记录. 实验中, 我们保留其中6个属性:Month of birth, Year of birth, race, Years of education, Income, Diagnosis codes. 其中, Years of education和Income属性为有序属性, 其他属性均为无序属性. 实验中, 我们取前5个属性作为关系数据, Diagnosis codes作为事务数据. 实验数据集中, 各个属性的特性见表 5. 由于无法获取Diagnosis codes的泛化层次结构, 本文参照文献^[27]的方式将泛化空间平均划分, 以5作为单位, 每5个节点上升一层(INFORMS中事务数据取值域为1 297, 由于5⁴＜1297≤5⁵ , 故最终层次为5). 按照这种划分方式, 不需要人为地指定泛化层次即可实现匿名化. 实验中, k和l的默认取值为10和5, qd和s的默认取值为5和2. 为了公平起见, RMR算法的阈值d设定为0. 65, m设定为2.

实验的硬件环境为HP ProLiant DL 580 G5, 16G RAM, 操作系统为Ubuntu 13. 04. 实验中的所有算法均由Python实现(APA, PAA和RMR代码已上传至Github(https://github.com/qiyuangong)).

4. 2 数据缺损评估

为了对数据匿名算法进行客观评估, 我们需要量化数据缺损^[3]. 现有的信息缺损衡量技术主要分为两类: (1) 通过缺损度公式来衡量缺损, 如NCP^[16]缺损矩阵^[15];(2) 通过聚集查询和计数查询的方式来衡量数据缺损^[18]. 但是, 这两类数据缺损衡量方法不适用于关系-事务数据, 直接应用现有技术会造成事务数据部分无法衡量.

为此, 本文基于文献^[18]的计数查询技术, 提出面向关系-事务数据的计数查询, 通过匿名化前后的计数查询结果差异度来衡量数据匿名造成的数据缺损. 在实际应用中, 计数查询是很多数据应用的基本操作, 例如数据统计、关联规则挖掘和OLAP. 匿名数据集的计数查询结果与原始数据集越接近, 则其数据应用的结果与原始数据集的差异也越小.

计数查询基本的查询语句如下:

SELECT COUNT(*) FROM T

WHERE pred₁(A₁) AND pred₁(A₂) AND … AND pred₁(A_qd) AND pred₂(A_d+1)

查询子条件pred₁和pred₂如下:

pred₁: (A=x₁ OR A=x₂ OR … OR A=x_b)

pred₂: (A_n+1 contains(pred₃(c₁) OR pred₃(c₂) OR … OR pred₃(c_b))

pred₃: (v₁ AND v₂ AND … AND v_|c|)

其中, A代表属性(关系数据中的准标识符或者事务数据), x代表A中的具体取值, qd代表选择的准标识符个数, b表示该属性上需要选取的取值数目. b的计算方法如下:

$b=\left[ \left| A \right|{{s}^{1/(qd+1)}} \right]$

(4)

其中, s表示选取比例, 0≤s≤100%. 每次计数查询时, 我们先确定qd和s的取值. 随后, 随机选取qd个准标识符, 并根据公式(4)计算每个属性上b的取值. 之后, 按照b从关系数据的属性上选取一定数量的取值{x₁, . . , x_b}来形成pred₁. 再按照b从T中所有的事务数据组合中选取一定数量的事务数据组合{c₁, . . , c_b}来形成pred₂. 需要注意的是, 每个事务数据组合c中包含若干事务数据取值v, 所有取值必须都出现在记录中, 查询pred₃才为True. 最后, 利用查询语句分别查询原始数据集T和匿名后的数据集T^*.

通过查询T, 可以得到精确的计数结果act;通过查询T^*, 并按照文献^[18]的方式计算概率, 可以得到est. 利用act和est, 我们可以计算T和T在本次计数查询中的差异度, 即相对误差RE(relative error).

$RE=\frac{\left| act-est \right|}{act}$

(5)

例如, 我们随机生成了一个查询(Age=18 or 19, Sex=M, Disease=$\langle $a₁, b₂$\rangle $), 通过查询表 1, 我们得到act=1, 通过查询表 2, 我们得到est=0. 4, 查询表 4得到est=0. 66. 所以, 表 2的RE为60%, 而表 4的RE为34%. 通常情况下, 由于数据集T和T^*中的取值不满足均匀分布, RE会随着随机选取取值的不同而波动. 为了客观反映T和T^*在计数查询中的差异度, 需要计算多次RE求平均值, 即平均相对误差ARE(average r elative error).

$ARE=\frac{\sum\limits_{i=1}^{qt}{R{{E}_{i}}}}{qt}$

(6)

其中, qt表示计数查询次数. qt取值越大, ARE越稳定, 计算ARE的时间也越长. 实际实验中, 需要根据数据集选取合适qt. 在实验中, 我们将qt设置为1 000, 即进行1 000次随机的计数查询求一组ARE.

为了方便理解, 一般用百分比来表示ARE, 其取值范围为ARE≥0%;ARE可以评估匿名后数据集T和原始数据集T^*之间的计数查询差异:ARE越大, act和est的差异度越大, 数据集缺损越严重. 当est与act差异较大时, ARE有可能超过100%.

4. 3 实验分析

实验中, 我们通过ARE来衡量APA, PPA和RMR的有效性, 通过运行时间来衡量3种算法的性能. 需要注意的是, 由于关系-事务数据中的事务数据维度不固定, 且部分事务数据维度较高, 造成匿名后的ARE普遍偏高.

(1) 数据缺损分析

为了分析算法造成的数据缺损, 我们选取k, l, qd, s和数据集规模共5个属性. 每次选择其中某个属性并改变其取值, 用以分析3种算法对这些属性的敏感程度. 由于RMR算法中没有参数l, 故图 3(b)中没有RMR的曲线.

如图 3(a)所示, 我们发现, 随着k的增加, 3种算法造成的数据缺损都会缓慢增加, 这是因为k越大, 等价类中包含的记录越多, 实现匿名的代价越大;同时, 在所有的k值上, APA和PAA造成的缺损远远低于RMR, 当k值较大时, RMR算法的ARE甚至接近100%. 如图 3(b)所示, 由于子算法Anatomize对l不敏感, 所以l的增加不会对APA和PAA造成太大影响, ARE只是因为随机生成的查询出现稍许的波动.

通过分析图 4我们发现, qd和s两个计数查询的属性对于3种算法的ARE有一定的影响. 随着qd的增加, 引入的属性会增加;而随着s增加, 选取的查询空间会变大. 随着引入属性的增加和查询空间的增加, 事务数据上的查询误差被稀释, 导致3种算法的ARE均有所下降. 同时, 在任意qd和s上, APA和PAA的数据缺损都低于RMR算法.

为了分析数据集规模对两种算法的影响, 我们以5K为单位, 顺序选取12个数据集. 通过对比实验我们可以看到, 在所有测试数据集上, APA和PAA的数据缺损都低于RMR算法. 另外, 如图 5所示, 随着数据集规模的增加, APA和PAA造成的数据缺损逐步降低. 这是因为Partition算法和Anatomize算法造成的数据缺损都会随着数据集规模增加而减少. 随着数据集规模的增加, 等价类中的记录数越来越多, 满足k-匿名和l-多样化的概率也会随之增加, 从而使得缺损度大为降低. 但是, 数据集规模的增加会造成RMR的ARE增加. 这是因为随着数据集的增加, RMR算法会更趋向于合并分组, 从而造成数据缺损增加.

从图 3~图 5中我们可以看到, APA和PAA造成的数据缺损远远低于RMR;同时, PAA算法造成的数据缺损比APA算法略低. 通过分析中间结果我们发现, APA形成的分组比PAA少, 平均分组大小高于PAA, 造成一定程度的过度匿名, 导致缺损度增加.

(2) 性能分析

为了分析APA, PAA和RMR的执行效率, 我们从k, l和数据集规模这3个角度出发进行分析. 由于RMR算法中没有参数l, 故图 6(b)中没有RMR的曲线.

如图 6(a)所示, 随着k的增加, 3种算法的效率均会提高. 这是因为随着k的增加, 算法的划分次数减少, 运行时间随之减少. 但是l的取值变化对于APA和PAA的运行效率影响很小, 如6(b)所示. 因为Partition算法和Anatomize算法的执行效率本身对l不敏感, 改变l对总体的运行时间没有太大影响. 如图 6(c)所示, 随着数据集规模的增大, 3种算法的运行时间直线上升. 这是因为, 数据匿名算法的效率受数据集规模(n)影响, 数据集规模越大运行时间越长. 同时, 随着数据集规模的增加, EC和TBucket数量都会增加, 造成运行时间增加.

我们可以看到, APA和PAA的运行效率远远高于RMR. 这与我们之前的分析相符:APA和PAA的复杂度为O(n²), 远低于RMR的O(n⁴). 因此在同等条件下, APA和PAA能够比RMR更快地完成匿名任务. 在所有的实验中, APA和PAA均能在12s内完成匿名化;而RMR的运行时间则长达上千秒, 当k值较小时, RMR甚至需要上万秒的运行时间. 同时, PAA算法的效率普遍高于APA算法. 通过分析中间结果我们发现, 两种算法在前2个阶段的运算时间基本相同, 但是PAA算法比APA算法少一个分组合并阶段, 所以运行效率较高.

(3) 实验小结

在上述实验中, APA和PAA都表现出了极高的运行效率和相对较低的数据缺损度. 在所有参数组合上, APA和PAA都可以在12s内完成对INFORMS数据集的匿名化, 并保证计数查询的平均相对误差低于85%. 与文献^[2]中RMR算法相比, 我们的算法具有更高的运行效率和更低的数据缺损. 通过对比实验我们发现, PAA算法比APA算法执行效率要高, 造成的数据缺损也更少.

5 结束语

针对关系-事务数据匿名中的数据可用性问题, 本文提出了(k, l)-多样化模型以保护发布数据中的用户隐私, 并基于该模型, 以Anatomize和Partition为基础设计了APA和PAA算法. 与现有的技术相比, 两种算法能够以更低的数据缺损和更高的运行效率完成关系-事务数据匿名. 但是引入Anatomize对于属性间的关联关系具有一定的破坏作用, 原有的数据关系变为概率性的结果, 造成关联分析的难度增加. 因此, 如何将其他匿名方法应用到(k, l)-多样化中, 将是我们下一阶段的研究方向.

致谢 在此, 我们向对本文的工作给予支持和建议的同行, 尤其是东南大学的倪巍伟教授和美国马萨诸塞大学洛威尔分校的李晓白教授表示感谢.