第一章 引言

随着计算机软件、硬件技术及互联网技术的迅速发展，各个领域已经积累了海量数据库，并且数据库的规模正以惊人的速率增长。随着知识发现与机器学习在诸多领域的深度应用和广度拓展，隐私保护数据挖掘（privacy-preserving data mining）已经成为知识发现领域的一个核心问题，特别是在国防、反恐、情报、社会网络分析、普适计算、语义Web、病毒营销、医学、社会学等领域，隐私保护数据挖掘已经成为涉及每个国家、每个公司、每个部门、每位公民的首要问题。

数据挖掘是知识发现的核心步骤。数据挖掘就是从海量数据库中分析并发现未知的、潜在的、有价值的知识，它融合了人工智能、数据库、模式识别、统计学和数据可视化等多个领域的理论和技术。[1]随着数据挖掘技术在人类生活和社会生产中的广泛应用，带来了巨大的经济效益和社会效益。但是伴随着数据挖掘技术的逐步提高，功能越来越强大的数据挖掘工具的开发和使用，人们越来越关注数据挖掘可能导致的隐私泄露问题。传统数据挖掘技术是针对原始数据库进行数据挖掘，对数据挖掘者而言，原始数据库是完全裸露的，真实的数据完整地放在数据挖掘者面前。如银行客户数据挖掘者可以从原始数据库中获得客户的身份证号码，医疗病患数据挖掘者可以从原始数据库中得知患者的病情。使用传统数据挖掘技术可以通过一个或多个原始数据库挖掘出数据拥有者不希望他人得知的知识，如银行客户数据挖掘者可以挖掘出客户定期的消费习惯，数据挖掘者通过医疗病患数据库和上市公司数据库可以挖掘出某上市公司的重要人物患有不可治愈的疾病，若此信息被披露有可能对上市公司造成不必要的损失。随着传统数据挖掘技术的广泛使用，越来越多的传统数据挖掘技术在为某些客户提供未知的、潜在的、有价值的知识的同时，也造成了越来越多的隐私泄露。

数据发布是数据挖掘的基础和前提。数据发布是数据的拥有者将数据展示给用户（当然也包括数据挖掘者），随着信息化技术的快速发展，各种信息被不同的政府部门、研究团体、商业机构等广泛地获取、发布和分析，丰富的数据资源中难免会涉及隐私数据信息。如果数据的拥有者在发布数据时，不对数据采取任何保护措施，数据挖掘者可以获取完整的原始数据库后对其进行数据挖掘，则很有可能造成隐私泄露。如某上市公司将财务年报完整地、直接地展示给用户，数据挖掘者很可能挖掘出此上市公司的竞争对手感兴趣的知识。文献 [2-4] 研究表明，通过邮编、性别、出生日期三个属性对未采取任何保护措施直接发布的选民登记表和医疗信息表进行数据挖掘，可造成87%的美国公民身份被唯一标识。

隐私保护数据挖掘PPDM（privacy-preserving data mining）就是在保证数据挖掘的同时尽可能地保护隐私数据，在不能完整或精确地访问原始数据的条件下，得到准确或基本准确的模型和分析结果。隐私保护数据挖掘作为数据挖掘领域中一个崭新、极其重要又富有挑战性的课题，其最终目标是实现隐私数据及敏感规则的保护又能得到准确的知识挖掘。

自1995年加拿大蒙特利尔市召开了第一次KDD国际学术会议并将“隐私保护数据挖掘”作为一个专门的研究主题开始，隐私保护数据挖掘就成为数据挖掘领域的研究重点之一。经过二十年的发展，隐私保护数据挖掘逐步得到各个国家各行各业的重视，并成为数据挖掘领域的研究热点。其主要的研究方向是：

1）数据发布中的隐私保护。针对发布的具体数据，采用不同的技术发布部分失真的数据、发布加密后的数据或阻止部分数据的发布，以达到隐私保护的效果。

a）数据扰动技术。数据扰动是采用数据交换、添加噪声等方法扰动原始数据，使敏感数据失真但能保证通过数据挖掘工具挖掘出的知识真实有效，如随机扰动、随机回答、阻塞和凝聚等算法。

b）数据加密技术。数据加密是对原始数据加密以保护隐私，如安全多方技术（SMC, Secure Multiparty Computation）。

c）查询限制技术。查询限制是通过限制数据的查询，避免数据挖掘者获取完整原始数据的方法，实现隐私保护，如通过抑制、泛化、数据抽样、数据划分等原则匿名化数据。

2）数据挖掘中的隐私保护。针对特定挖掘任务和数据的分布方式，采用不同的技术实现在数据挖掘过程中的隐私保护。

a）针对特定挖掘任务。针对挖掘任务的不同研究相应的隐私保护数据挖掘算法。现在的数据挖掘技术可以解决关联规则挖掘、分类挖掘、聚类挖掘、数据流挖掘、序列挖掘、图挖掘、社会网络分析挖掘、多关系挖掘、对象挖掘、Web数据挖掘、多媒体挖掘、空间挖掘等。不同的挖掘任务使用的隐私保护数据挖掘技术和算法差异很大，目前还没有通用的隐私保护数据挖掘算法。

b）针对数据分布方式。数据分布方式有两种：集中式和分布式。针对集中式数据分布，主要的隐私保护技术有启发式和重建式两种；针对分布式数据分布，主要的隐私保护技术是加密技术。隐私保护数据挖掘中的关联规则主要采用Apriori方法确定频繁项集；分类方法主要有决策树归纳分类、贝叶斯分类、支持向量机分类（SVM, Support Vector Machine）、k-最近邻分类、粗糙集分类和模糊集分类等；聚类方法主要有划分方法，例如k均值、k中心点、期望最大化（EM, Expectation Maximization）等方法；层次方法，包含凝聚层次聚类和分裂层次聚类两种，例如Birch方法；基于密度的方法，如DBSCAN方法等。

c）隐私保护的度量。不存在某种隐私保护数据挖掘算法，在任何方面都胜过其他算法，优异算法是指在某些特定的方面优于其他的已有方法，如在性能或数据实用性等方面。度量一种隐私保护数据挖掘算法的优劣，主要的评测指标有：算法性能（主要是时间和空间代价）；算法效能（主要是隐私保护效果和信息遗失来衡量）；算法适用性（主要是适用不同类型的隐私、不同类型的数据、不同应用背景下隐私的保护能力）。

本课题的研究背景是北京科技大学知识工程研究所承担的国家自然科学基金面上资助项目“基于大规模复杂结构知识库的知识发现机理、模型与算法研究”（项目编号：60875029）和国家自然科学基金面上资助项目“基于多关系的模糊认知图挖掘模型、算法与评价机制研究”（项目编号：61175048）。

本书的文章组织结构如下：

第一章 引言。

第二章 引述本书研究的宏观背景。分析了KDTICM理论、隐私保护和数据挖掘，安全多方计算技术、数据匿名化技术、数据扰动技术的发展历程。

第三章 首先，总结了聚类隐私保护挖掘的研究历史沿革和现状，分析各种现存模型的特点及存在的问题，以此为基础提出了笔者解决问题的思路。其次，分析了针对数据加密技术，分布式聚类隐私保护挖掘模型。探讨了水平分布式聚类数据挖掘算法中隐私保护的可行性，在设计全新的完全同态加密算法的基础上，针对水平划分方法提出FHE-DK-MEANS模型和FHE - DBIRCH模型。最后，针对两个模型进行了实验分析、比较。

第四章 首先，总结了数据发布中隐私保护挖掘的研究历史沿革和现状，分析各种现存模型的优缺点及存在的问题，并在此基础上提出了个性化（α[s], ℓ）-多样k-匿名模型和个性化并行（alpha[s], k）-匿名模型。从理论证明和实验分析两个角度证明了这两种模型在数据发布中个性化隐私保护的优势。

第五章 首先，总结了前人的工作，发现了随着数据发布中隐私保护要求逐渐提高，现存模型无法满足要求的问题，分析了现存模型的特点，利用数据库系统中的有损分解思想，提出（α[s], ℓ）-多样k-匿名有损分解模型。从理论证明和实验分析两个角度证明了这种模型在数据发布中隐私保护的优势。

第六章 总结本书的研究成果并展望进一步的工作。