CN102156755A

CN102156755A - 一种k-匿名改进方法

Info

Publication number: CN102156755A
Application number: CN2011101173038A
Authority: CN
Inventors: 张静
Original assignee: Tianjin University
Current assignee: Tianjin University
Priority date: 2011-05-06
Filing date: 2011-05-06
Publication date: 2011-08-17

Abstract

本发明公开了一种K-匿名改进方法，涉及数据挖掘领域，根据原始数据集选择准标识符，确定泛化方式，并建立与泛化方式对应的初始泛化格；判断初始泛化格是否为空，如果否，根据最优节点选择方式从初始泛化格的所有节点中选择出全局最优节点，获取第一泛化格；根据全局最优节点对待发布数据进行匿名化处理，获取匿名簇的数量；判断匿名簇的数量是否小于预设数量，如果是，对第一泛化格进行最优节点选择方式计算，获取最优节点；如果否，匿名簇为孤立簇，对第一泛化格进行二次K-匿名计算，获取最优节点；将待发布数据按照最优节点对应的泛化方式进行泛化，获取泛化后的数据，将泛化后的数据发布。本发明缩短了执行时间，提高了信息的准确性。

Description

一种K-匿名改进方法

技术领域

本发明涉及数据挖掘领域中的K-匿名(K-Anonymity)，特别涉及一种K-匿名改进方法。

背景技术

数据匿名化采用的常用处理手段源于统计数据库中的数据处理方法，主要是通过以发布数据中的属性值的信息损失为代价，换取通过这些属性值再标识某些个体的准确性，同时尽可能保证发布数据的可用性，在发布数据的准确性和隐私保护之间达到一种平衡。传统的隐私保护方法，为了保证发布数据的整体趋势，往往以牺牲单个数据记录的准确性为代价。

K-Anonymity(K-匿名算法)：K-匿名(K-Anonymity)是不同于传统的访问控制等基于目标的隐私保护技术，是一个典型的微数据发布模型(微数据定义为一条表达和描述个体信息的数据记录，为个体信息的载体。这些信息包括个体的标识信息(如姓名、身份证号等)、敏感信息(如病史等)、以及一些非敏感信息(如性别)。每个信息都是以个体属性和相应的属性值匹配的方式作为微数据(记录)的某个分量。)。它要求首先对原始数据进行预处理以满足匿名要求，然后将已处理的数据予以发布。它并不要求限制对已发布数据的访问，相反尽可能的保持数据的可统计性。因而数据泛化(泛化是对于数据的一个属性，用概括值代替原来的值，使其意义更为广阔)是常用的数据预处理手段。K匿名就是要求在一个集合中(这里是指广义集合，即允许包含相同元素，类似于包(Bag)或簇(Cluster)的概念)中只能以不大于1/k(k是一个常数)的概率确定任何一个元素，即要求任何一个元素，集合中至少存在k-1个相同的副本元素。用形式化语言表述K匿名的概念，一般是将发布数据表中的个体记录的属性分为标识符、准标识符和敏感属性三类，并提出了等价类的概念。以下是相关定义：

标识符(Identifiers)：标识符属性是指能够直接标识出个体身份的属性，如姓名、身份证号码、社会保险号码等属性，通过这些属性值能够直接确定具体的个体。

准标识符(Quasi-Indentifiers，QI)：给定实体集合U、实体表T(A₁，A₂，LA_n)，f_c：U→T以及f_g：T→U′，其中，

实体表T的准标识符QI为属性组其中，

且满足f_g(f_c(p_i[QI]))＝p_i。换言之，同时存在于发布数据表和外部数据源表中，利用此两种数据表进行连接的推演来表示个人隐私信息的一组属性称为准标识符属性。准标识符属性也叫做类标识符属性。不同的发布数据表可以根据不同的情况划分不同的准标识符属性，一般情况下准标识符由专家选择，而非用户随便选取。一般情况下可以以年龄、教育程度、性别作为准标识符。

敏感属性(Sensitive-Attributes，SA)，个人隐私属性。发布数据中，个体不希望其他用户知道的信息属性。比如说个人的工资水平以及患者的就诊记录中的所患疾病。发布数据时，为了防止个人敏感信息的泄露，标识符必须被删除，发布的数据记录只保留准标识符属性和敏感属性，称为匿名化处理。

等价组：在准标识符上的投影完全相同的记录组成的等价组，即：等价组中所有的记录在准标识符上的属性值完全相同，其他的属性值可以不同。

K-匿名：给定数据表T(A₁，A₂…A_n)，QI是与T相关联的准标识符，当且仅当在T[QI]中出现的每个值序列至少在T[QI]中出现K次，则T满足K-匿名。T[QI]表示T表中的元组在QI上的投影。

现实生活中，将医疗、投票和求职等信息公开的同时又要保证隐藏相关患者、投票人和求职人等的个体标识信息并确保这些公布的数据不能用来推导出这些标识信息，K-匿名就是非常好的可选模型。当数据发布到公共数据库，数据的拥有者不再继续控制数据的使用方式和范围时，在这种情况下为了不暴露数据主体的身份移出所有涉及到个体标识的数据项信息De-Identification(去标识)就是一种常用的方法。

发明人在实现本发明的过程中发现现有技术中至少存在以下的缺点：

现有技术中的K-匿名方法在判断和比较的时候，都需要比较泛化格中的所有节点，当泛化格的规模比较大时，执行时间将会很长，这对于数据处理是很不利的；这种方法多半是全局最优的，由于数据分布的不均匀性，即存在着孤立簇(即数量很小的集合)，为了达到匿名要求，不得不采用更高的泛化层次，这显然会降低信息的准确性。

发明内容

为了缩短执行时间，提高信息的准确性，本发明提供了一种K-匿名改进方法，详见下文描述：

一种K-匿名改进方法，所述方法包括以下步骤：

(1)根据原始数据集选择准标识符，由所述准标识符确定泛化方式，并建立与所述泛化方式对应的初始泛化格；

(2)判断所述初始泛化格是否为空，如果是，流程结束；如果否，执行步骤(3)；

(3)根据最优节点选择方式从所述初始泛化格的所有节点中选择出全局最优节点，获取第一泛化格；

(4)根据所述全局最优节点对待发布数据进行匿名化处理，获取和所述全局最优节点相应的匿名簇的数量；

(5)判断所述匿名簇的数量是否小于预设数量，如果是，执行步骤(6)；如果否，执行步骤(7)；

(6)对所述第一泛化格进行所述最优节点选择方式计算，获取最优节点；

(7)匿名簇为非孤立簇，对所述第一泛化格进行二次K-匿名计算，获取所述最优节点；

(8)将所述待发布数据按照所述最优节点对应的泛化方式进行泛化，获取泛化后的数据，将所述泛化后的数据发布，流程结束。

步骤(3)中的所述根据最优节点选择方式从所述初始泛化格的所有节点中选择出全局最优节点，获取第一泛化格，具体为：

①计算所述初始泛化格中所有节点的度；

②对所述初始泛化格中所有节点按照度进行排序，获取度最大节点；

③判断所述度最大节点是否满足K-匿名，如果是，执行步骤④；如果否，执行步骤⑤；

④所述度最大节点的所有父节点都为K-匿名节点，删除所述度最大节点的所有祖先节点，查找所述原始数据集中保存的K-min集合，判断所述K-min集合中是否有所述度最大节点的祖先，如果是，从所述K-min集合中删除所述度最大节点的祖先；如果否，执行步骤⑥；

⑤所述度最大节点的所有子孙节点都不是K-匿名节点，删除所述度最大节点以及所述度最大节点的所有子孙节点；

⑥计算所述K-min集合中所有节点的信息损失量，获取最小信息损失量，将所述最小信息损失量对应的节点作为全局最优节点，获取所述第一泛化格；

其中，计算所述K-min集合中所有节点的信息损失量具体为：

InfoLoss = \frac{Σ_{i = 1}^{N} \frac{h_{i}}{{DGH}_{i}}}{N}

其中，N表示元组集中的准标识符个数、DGH_i表示N个准标识符中第i个准标识符的泛化等级、h_i表示准标识符i的泛化程度。

本发明提供的技术方案的有益效果是：

本发明提供了一种K-匿名改进方法，本发明提供的方法缩短了执行时间，提高了信息的准确性，满足了实际应用中的需要。

附图说明

图1为本发明提供的年龄Age的泛化方式；

图2为本发明提供的性别Sex的泛化方式；

图3为本发明提供的年龄Age和性别Sex的泛化格；

图4为本发明提供的一种K-匿名改进方法的流程图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明实施方式作进一步地详细描述。

为了缩短执行时间，提高信息的准确性，本发明实施例提供了一种K-匿名改进方法，本发明实施例基于K匿名算法，用于对隐私数据进行去标识，本发明实施例采用的预处理主要在得到最优节点后，对泛化格进行进一步的优化，详见下文描述：

101：根据原始数据集选择准标识符，由准标识符确定泛化方式，并建立与泛化方式对应的初始泛化格；

其中，遍历初始泛化格后保存有K-min集合。参见图1、图2和图3，例如：从原始数据集中选择准标识符年龄Age和性别Sex，由准标识符年龄Age和性别Sex确定泛化方式，泛化方式由以下泛化向量组成：L(a₁...a_i...a_k)，其中a_i表示节点每个属性的泛化等级(泛化高度)，k为表中的属性个数；泛化等级：

表示该节点的在初始泛化格中的泛化等级(泛化高度)。两个或多个准标识符进行不同等级的泛化得到的结果构成准标识符泛化序列，这些准标识符泛化序列构成基于准标识符的泛化等级序列，称为泛化格。例如：年龄Age和性别Sex可以构成图3中的初始泛化格。根据各个准标识符相应的泛化方式可以建立初始泛化格，令T_i(A₁，…，A_k)和T_j(A₁，…，A_k)是两个不同表(即两者为初始泛化格Lattice中不同的节点，(A₁，…，A_n)为数据的k个准标识符，A_k为第i个准标识符的泛化等级或泛化高度)。泛化格中的每一个节点，表示一个准标识符一次泛化后的表，即为各准标识符泛化到此时对应的发布数据。

其中，可以根据实际应用中的需要确定准标识符和泛化方式的数量，具体实现时，本发明实施例对此不做限制。

102：判断初始泛化格是否为空，如果是，流程结束；如果否，执行步骤103；

103：根据最优节点选择方式从初始泛化格的所有节点中选择出全局最优节点，获取第一泛化格；

其中，最优节点选择方式的步骤具体包括：

(1)计算初始泛化格中所有节点的度；

其中，初始泛化格中所有节点包括父节点和子节点，父节点为与该节点相连的上一层节点；子节点为与该节点相连的下一层节点；计算每个节点的度具体为：该节点的所有父节点数与所有直接子节点数的乘积。

(2)对初始泛化格中所有节点按照度进行排序，获取度最大节点；

其中，排序可以采用任何一种排序方式，例如：由高到低排序或由低到高排序，具体实现时，本发明实施例对此不做限制。

(3)判断度最大节点是否满足K-匿名，如果是，执行步骤(4)；如果否，执行步骤(5)；

(4)度最大节点的所有父节点都为K-匿名节点，删除度最大节点的所有祖先节点，查找原始数据集中保存的K-min集合，判断K-min集合中是否有度最大节点的祖先，如果是，从K-min集合中删除度最大节点的祖先；如果否，执行步骤(6)；

其中，祖先节点具体为：度最大节点的父节点以及父节点的上n层节点，n的取值为大于等于1的正整数。

(5)度最大节点的所有子孙节点都不是K-匿名节点，删除度最大节点以及度最大节点的所有子孙节点；

(6)计算K-min集合中所有节点的信息损失量，获取最小信息损失量，将最小信息损失量对应的节点作为全局最优节点，获取第一泛化格。

数据经过泛化后就会出现一定程度的失真，泛化程度越高，那么数据失真度就越大。发布数据常常是用来分析或者研究某些问题，因此在发布数据的时候不仅要保护隐私的泄露，还要尽量保证发布的数据有较小的损失，否则即使达到了隐私保护的目的，发布的数据也失去了价值，隐私保护也没有任何意义。

其中，计算K-min集合中所有节点的信息损失量具体为：

InfoLoss = \frac{Σ_{i = 1}^{N} \frac{h_{i}}{{DGH}_{i}}}{N}

其中，N表示元组集中的准标识符个数、DGH_i表示N个准标识符中第i个准标识符的泛化等级、h_i表示准标识符i的泛化程度。由上述公式可知泛化程度越高、信息损失量越大；泛化程度越低，信息损失量越小。

104：根据全局最优节点对待发布数据进行匿名化处理，获取和全局最优节点相应的匿名簇的数量；

其中，待发布数据由实际应用中的需要进行设定，具体实现时，本发明实施例对此不做限制。

105：判断匿名簇的数量是否小于预设的数量，如果是，执行步骤106；如果否，执行步骤107；

106：对第一泛化格进行最优节点选择方式计算，获取最优节点；

107：匿名簇为非孤立簇，对第一泛化格进行二次K-匿名计算，获取最优节点；

其中，对第一泛化格进行二次K-匿名计算具体为：取出最小K匿名节点集合中的第i个节点；计算第一泛化格节点的簇信息，包括代表每个簇的节点信息和对应的容量；取出第j簇的信息；添加簇的信息；建立新的lattice；在数据集firstdata上计算节点的信息损失量；计算二次K-匿名的抑制率；在数据集seconddata上进行抑制率为secondratio的K-匿名计算(度优先算法)；将最小K-匿名节点集合中信息损失量最小的节点找出来，获取最优节点。

其中，二次K-匿名计算的代码详见下文描述：

输入：大小簇分界值threshold

输出：最小信息损失量smallinfo

变量：firstdata用于存储孤立簇数据；seconddata用于存储进行二次匿名的数据；kmin用于存储最小K匿名节点的集合

getnode(i)：取出最小K匿名节点集合中的第i个节点

getInfoOf(latticenode)：计算latticenode节点的簇信息，包括代表每个簇的节点信息和对应的容量

getcluster(j)：取出第j簇的信息

add(ClusterInfo.get(j))：添加簇的信息

Lattice(Bnode，latticenode)：建立新的lattice

infoloss(lattticenode，firstdata)：

在数据集firstdata上计算节点latticenode的信息损失量

SecondRatio()：计算二次K-匿名的抑制率

Kmin(lattice，secondratio，seconddata)：在数据集seconddata上进行抑制率为secondratio的K-匿名计算(度优先算法)

GetsmallLatticenode(latticenode.kmin)：将最小K-匿名节点集合中信息损失量最小的节点找出来

108：将待发布数据按照最优节点对应的泛化方式进行泛化，获取泛化后的数据，将泛化后的数据发布，流程结束。

综上所述，本发明实施例提供了一种K-匿名改进方法，本发明实施例提供的方法缩短了执行时间，提高了信息的准确性，满足了实际应用中的需要。

本领域技术人员可以理解附图只是一个优选实施例的示意图，上述本发明实施例序号仅仅为了描述，不代表实施例的优劣。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims

1.一种K-匿名改进方法，其特征在于，所述方法包括以下步骤：

2.根据权利要求1所述的一种K-匿名改进方法，其特征在于，步骤(3)中的所述根据最优节点选择方式从所述初始泛化格的所有节点中选择出全局最优节点，获取第一泛化格，具体为：

①计算所述初始泛化格中所有节点的度；

其中，计算所述K-min集合中所有节点的信息损失量具体为：

InfoLoss = \frac{Σ_{i = 1}^{N} \frac{h_{i}}{{DGH}_{i}}}{N}