摘 要

随着互联网技术的发展，我们在享受到数据共享所带来的便利的同时也需要注意数据对我们带来的隐私安全威胁，正是由于互联网的互通，互连的特性，我们的各种行为数据可以轻松的在网上获取。如何保证数据可用性的同时保证数据的隐私性变得愈发重要起来。本文就是在当前环境下提出一种基于聚类的隐私保护算法。

k-means算法和MDAV算法分别是聚类算法和k-划分算法中比较著名的算法，本文在这两个算法的基础上做出些许改进，将以往k-匿名算法不能解决的非连续型数据巧妙的转变为树型结构中节点间距来完成计算点间距的目的。本文提出了一种高效的，高保真的k-匿名算法。经实验证明，本算法能在保证k-匿名的前提下缩短算法所需的执行时间并能保护更多的语义性。

关键词：k-匿名，k-means，聚类，链接攻击。

Abstract

With the development of Internet technology, we also need to bring attention to our data privacy security threats to enjoy the convenience of data sharing the same time, precisely because of the Internet exchange, interconnection characteristics, our various acts data can easily found on web. How to ensure data availability while ensuring the privacy of data becomes increasingly important. This article is proposed in the current environment protection algorithm based on clustering privacy.

k-means and MDAV are two of the most famous algorithm in clustering and k-divide area.In this paper,we make some improvement on the basis of the two algorithm.The Continuous data is translated into a leaf in a tree structure to deal with calculating the distance which can not be done by formor k-anonymity algorithm between two data.This paper propose an algorithm which is efficient.As is proved by experiment ,this algorithm which is under the premise of guaranteeing k-anonymity mode can not only shorting the costing time but also can protect more semantic.

Keywords:k-anonymity,k-means,Link-Attack

目录

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究背景以及研究目的与意义 1

1.1.1 研究背景 1

1.1.2 国内外研究现状 1

1.1.3 研究目的和意义 2

1.2 本文研究内容 2

1.3 行文结构 2

第2章 相关技术 4

2.1 基本概念 4

2.2 评估标准 5

第3章 高还原度的微聚类K-匿名算法 7

3.1 基本思想 7

3.2 聚类算法 7

3.2.1 k-means聚类算法 7

3.2.2 高保真的k-means聚类算法 9

3.3 k-匿名算法 12

第4章 实验仿真 17

第5章 总结和展望 23

参考文献 25

致谢 26

绪论

研究背景以及研究目的与意义

研究背景

随着互联网技术的迅猛发展，各种互联网应用如雨后春笋般喷涌而出。不可否认，这些互联网应用很大程度的方便了我们的生活。但是在使用这些应用的同时，我们各项行为数据也被各大应用厂商所储存。由于研究需要，各数据持有者需要将这些数据发布出来，因此在数据发布过程中隐私泄漏问题也就日益突出，故对数据发布中的敏感数据进行加密和隐藏就变得更加重要。所谓在隐私数据发布中隐私保护即指消除用户敏感数据和用户身份信息之间的对应关系。通过隐藏唯一标识符和概化准标识符是现在主流的隐私保护方法。但是仅仅如此并不能抵挡链接攻击，链接攻击即非法研究者通过对发布的数据和其他地方获取的数据进行比较和综合达到唯一标识用户的目的。故P.Samarati和L.Sweeney提出了k-匿名模型来抵御链接攻击^[1]。

国内外研究现状

自k-匿名模型被提出以来，关于k-匿名的研究越发火热。K-匿名只是一个模型，针对k-匿名模型的实现由很多种算法。文献[2]提出了DATAFLY算法，该算法在实现k-匿名化的时候以表中的属性为一组对于数据表中的所有元组进行K-匿名化，这样会导致即使有些元组已经满足匿名化的条件了但是仍要参加匿名化的过程降低了精度。文献[3]提出一种基于取整划分函数的k-匿名算法，并从理论上证明了此算法可以在非平凡数据集中取得更低的上界。文献[4]则在特征类的精度上做文章提出了classfly算法,该作者在一年后提出支持多约束的k-匿名化方法classfly 来降低多约束k-匿名化的信息损失^[5]。文献[6]在datafly算法的基础上提出一种自底向上的支持多属性归纳的k-匿名算法。近些年来也有部分学者提出传统的方法计算复杂度较高，故提出将聚类算法引入到k-匿名模型中来。通过将微聚集方法和其他技术相结合用来保护隐私数据^[7]。针对此思想文献[7]提出了(m,k,l)算法，即对数据线进行聚类处理，将处理后的数据再使用MDAV算法进行匿名化处理，并在选取数据的时候选取最优数据以达成l多样性。文献[8]在研究k-匿名化模型后提出k-匿名化虽然能抵御链接攻击，但是并不能抵御背景知识等攻击，故提出了L-diversity模型，要求各匿名组中的敏感数据重复性不得高于1/l。L-多样性是基于K-匿名的，比k-匿名更能保护隐私数据安全的模型，故文献[9]研究了基于L多样性的MDAV算法。文献[10]就用基于l-diversity的隐私保护方法对社交网络数据进行保护。文献[11-12]都研究了基于地理位置LBS的隐私数据保护方法，并使用了实例来进行了论证，不同的是文献[11]是基于k-匿名化的，而文献[12]是基于L-diversity的。

研究目的和意义

虽然各学者都对如何进行k-匿名化提出了自己的算法，但是大部分算法在选取点构成k-匿名组的时候都是通过计算两点之间的相似性来判断的，然而却没有考虑到当属性值为混合型数据时并没有做过多探讨或是单纯的相同则差距为0，不同则差距为1的方式来计算。这么做务必会导致两点之间的相似性计算不准确，进而导致k-匿名组分配不合理的情况。此外，对于k-匿名组的输出以上算法也没有做详尽的讨论，大多只是将k-匿名组分出来后就没有向下展开。故本文提出一种高保真度的k-匿名聚类算法，让k-匿名化能对混合型属性值有更好的表现，以期进一步提高匿名后数据的可用性。

本文研究内容

为实现高保真的k-匿名算法，必须对非数值型数据有更好的数据差值计算。故提出一种基于树形结构的k-means聚类算来对数据进行初步聚类处理。本文主要研究了

1. 如何进行树形结构的文本输入。
2. 如何计算两个叶子节点之间的距离。
3. 如何将k-means算法和处理过后的点阵数据结合起来。
4. 如何将分好组的各数据匿名输出，即完成k-匿名的过程。

行文结构

本文一共分为5章，每章的主要内容如下：

第1章，绪论。主要介绍了研究背景和国内外的研究现状。概括了本文的主要研究内容并对各章内容进行介绍。