清 华 大 学
综 合 论 文 训 练
题目：基于概要模式的K-匿名算法
系___ 别：计算机科学与技术系
专___ 业：计算机科学与技术专业
姓___ 名：王静
指导教师：王建勇_ 副教授
2007 年 6 月 18日
I
关于学位论文使用授权的说明
本人完全了解清华大学有关保留、使用学位论文的规定，即：学校有权保留学位论文的复印件，允许该论文被查阅和借阅；学校可以公布该论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存该论文。
(涉密的学位论文在解密后应遵守此规定)
签_ 名：_____________ _____________ ____ 导师签名：_____________ _____________ _____________ ____ 日_ 期：_____________ ___ _____________ _
II
中文摘要
互联网的发展给我们获取和使用信息带来了极大的方便。但在另一方面，这种非授权的信息共享严重威胁着个人数据的隐私安全。于是，基于数据的隐私保护成为当前人们研究的热门课题。
一种比较典型的攻击方式是链接攻击，即把发布的数据和另外的数据在某些属性上链接起来而透漏敏感信息。为了防止这种攻击，提出了k-匿名的概念，它可以使得表格中的每条记录都与至少k-1条其他记录不可区分。
本文提出了一种基于概要项集的k-匿名算法。实验结果显示它可以在更短的运行时间内获得与原有算法相似的近似率。我们还把k-匿名的概念扩展到了序列数据上面，并设计了基于概要子序列的k-匿名算法。最后，我们给出了图匿名的研究现状综述。
关键词：数据安全 隐私保护 概要模式 k-匿名
II
ABSTRACT
The rapid development of network brings great convenience for people to retrieve and utilize the information. But on the other hand, this unauthorized information sharing poses a serious threat on the privacy of personal data. Therefore, data based privacy preservation has become a hot research topic in recent years.
One attack method is the linking attack which joins the published data with other data on some attributes and reveals the sensitive information. To protect privacy against this attack, the notion of k-anonymity which makes each record in the table indistinguishable with at least k-1 other records has been proposed.
In this paper, we propose a summary itemset based k-anonymity algorithm. Experimental results show that our algorithm can achieve similar approximation ratio in shorter running time. We also expand the notion of k-anonymity to sequence data and devise a summarization subsequence based k-anonymity algorithm. Furthermore, we give a brief review on the current research status of graph anonymization.
Keywords：Data security Privacy preservation Summary pattern k-anonymity