【作者】 徐聪；

【导师】 王茜；

【作者基本信息】 重庆大学 ， 计算机软件与理论， 2012， 硕士

【摘要】 在科学领域与信息技术不断地迅速进步的近些年来，信息共享与资源互利已经越来越受到人们的各种关注。与此同时，这些信息资源给人们带来各种生活中的好处，也带来了人们隐私数据信息泄露的危险。保护人们的隐私信息问题已经成为大众关注的一个焦点，也是数据发布处理研究中值得研究探讨的一个重要课题。在数据发布过程中，如果仅仅只对可以明确确定用户身份的标识符进行删除或者加密，隐私保护效果并不好，攻击者仍然可以通过利用发布数据集中的准标识符属性与外来数据集合进行联合推演，使用多个数据集的链接操作，从而推算得到个体希望被保护的隐私数据信息。K-匿名化技术是在微数据发布之中一种非常重要的隐私保护方法。可是对于在多属性集合上获取最优K-匿名化是一个NP-难问题，所以对K-匿名化的主要研究集中在：如何使发布数据集合匿名化操作控制在比较合理的时间复杂度之中，同时能够获得较高的匿名化程度。论文全面分析了目前已有的各种K-匿名化算法，并且总结出这些方法所存在的优点和缺点。针对这些问题论文的主要工作如下：①论文提出了多维映射分治的K-匿名化算法。该算法建立了新的多维到单维映射模型，并且记录其中的二种重要信息：在对每个单维进行映射得到的不同单维点的个数Pro以及每个不同单维点所对应的多维点的个数PPA。该算法采用了新的信息依赖量来度量数据信息的变化程度，降低了匿名化后的结果集中信息损失度。该算法可以在多项式的时间复杂度内获得较高匿名化程度，提高了K-匿名化算法的实际应用能力。②论文提出了K-匿名化增量更新策略。对于频繁变动的数据发布过程，该策略使用阀门值来维持数据集的相对稳定。对于增量更新时间，该策略通过对增量数据进行定位操作来实现局部更新方法，降低时间开销。对于信息损失量，该策略考虑到邻居集合中的相似集合对增量数据的信息关联度，把局部更新范围锁定在相似集合之中来来提高结果集的匿名化质量。这样保证了数据集能够在可以接受的更新时间中，重新达到K-匿名化效果。③论文分别在实验数据集合与真实数据集合上进行了多种对比实验来验证算法的可用性和高效性。实验结果表明：多维映射分治的K-匿名化算法可以得到较高的匿名化程度，且时间性能可以接受；提出的增量更新策略对于现在已经存在的技术是高效的，具有较好的数据安全性能。更多还原

【Abstract】 In recent years, with the rapid development of science technology and informationtechnology constant, sharing of resources and mutual benefit is paid close attention toby people more and more. When the kinds of information resources bring benefit in lifeto people, they also bring the risk of data privacy information disclosure to us.Protecting people’s privacy information has become a focus of the public concern. Thisis an important subject in data released treatment researching. In data release process, ifonly to delete or encryption identifier that can determine the identity of the users,privacy protection effect is not good. Attackers can still link these databases with otherreleased database on Quasi-identifiers attributes to re-identify individual’s privateinformation. K-anonymity technical in micro-data release is one of the most importantmethods in privacy protection. However, it is a NP-hard problem for optimalK-anonymity on dataset with multiple attributes. The major research of K-anonymityfocuses on how to release data of anonymity in the reasonable time complexity and atthe same time can obtain higher level by anonymity.This paper comprehensive analyzes the existing K-anonymity of algorithms andsums up the advantages and disadvantages of these methods. To solve these problemsthe major work of this paper are as follows:①This paper proposes a multi-dimensional K-anonymity algorithm based onmapping and divide-and-conquer strategy. The algorithm sets up a new mappingMulti-dimensional to single-dimensional model, and records two of importantinformation: the number of data points that each dimension is mapped tosingle-dimensional set, Pro, and number of multi-dimensional data points that eachsingle-dimensional data point is mapped to, PPA. This algorithm adopted informationdependency to measure information changes, which reduces the loss of informationafter K-anonymity. The algorithm can finish in polynomial time complexity, whichimproves the actual application ability of K-anonymity.②This paper proposes an effective k-anonymity strategy based on incrementallocal update on large dataset. For frequent change of data release process, this strategyuse threshold value to maintain relative stability. The strategy realizes local updatemethod by positioning operation to reduce the time cost. This strategy considers theneighbors set in similar set on incremental data correlation degree of information to improve the quality of the result set anonymity.③In the paper, the variety of comparative experiments are in two ways. Oneexperiment is on the experimental data, and the other is on the real data. Theexperimental results show that the multi-dimensional K-anonymity algorithm based onmapping and divide-and-conquer strategy can get a higher level by anonymity, and thetime performance can be accepted; and the effective k-anonymity strategy based onincremental local update on large dataset is efficient compared to the methods at presentand has a good data safety performance.更多还原