【论文】基于隐私保护的聚类挖掘的研究与实现

1、I 基于隐私保护的聚类挖掘的研究与实现基于隐私保护的聚类挖掘的研究与实现 摘要摘要：随着数据库和网络技术的发展，数据在数量和复杂性上出现了很大的增 长，随之出现了数据挖掘这一强有力的数据分析工具。其能发现数据中的规律， 为很多领域做出了巨大贡献，应用前景广泛。然而，在很多情况下，数据持有者 可能出于数据安全和敏感性等原因而不想和别人共享自身的数据，如何在私有数 据不被泄露的前提下得到精确的挖掘结果也就成了当前数据挖掘的一大研究方向， 称为基于隐私保护的数据挖掘。 本文既考虑在半诚实模型下又研究在恶意模型情况下的隐私保护的聚类问题， 在半诚实模型下,各个方之间不存在共谋作弊现象,所以使用普通的正

2、交变换来实 现数据扰乱，实验得到扰乱前后两属性间距离不变。在恶意模型下,由于恶意方 可能会中途中断协议,联合其它方作弊等,这种情况下普通的正交变换已失去了保 护性,所以考虑使用随机化的方法来实现隐私保护，其先使用层次聚类算法确定 初始聚类中心,然后用k-means聚类算法进行欧氏距离实验测试，最后得出误差在 合理精度范围之内。实验表明所提出的方法在合理的精度下实现了垂直分布数据 的隐私保护。 关键词关键词：隐私保护；数据挖掘；聚类；垂直分布；恶意模型；半诚实模型；数 据扰乱 Research and Implementation of privacy preserving clustering

3、 mining Abstract: With the development of database and network technology, the number and complexity of data grow a lot. There appears a powerful data analysis tools called data mining, which can found the law of the data. It has made tremendous contributions to many areas and it has an extensive ap

4、ply prospect. But in many cases, the data holders may do not want to share their own data with others for some reasons, such as data security and sensitivity and so on. How can get accurate mining result without leaking the private data is becoming a major research direction of data mining. It is ca

5、lled privacy preserving data mining. This paper considers the problem of the semi-honest model but study the cluster problem of the malicious model to the privacy protection. In the semi-honest model, each party does not cheat in conspiracy, therefore, we use ordinary orthogonal transformation to ca

6、rry out the data perturbation，the experiment gets that the distance between the two unchanged. In the malicious model, as malicious may interrupt the agreement in the half way, and cheat with others and so on, in this case, ordinary orthogonal transformation has lost its protective, so we consider u

7、sing random perturbation to achieve privacy protection, it first use cluster algorithm to determine the initial level of cluster center, and then use k- means cluster algorithm to carry out Euclidean distance test, finally, it gets that the error is in a reasonable accuracy. The experiments show tha

8、t this method can carry out the vertical distribution of data privacy protection with reasonable accuracy. Key words: privacy preserving; data mining; clustering; vertical distribution; malicious model; semi-honest model; data perturbation 目 录 第一章绪 论.1 1.1 研究背景及意义 .1 1.2 隐私保护数据挖掘的研究现状 .2 1.3 主要内容 .2

9、 1.4 文章组织结构 .3 第二章隐私保护数据挖掘概述.4 2.1 数据扰乱方法 .4 2.2 基于密码学的技术 .5 2.3 未来隐私技术的发展 .7 2.4 几种安全计算模型的定义 .7 2.5 两个基本协议 .8 2.5.1 求和协议 .8 2.5.2 点积协议 .8 第三章 集中分布数据隐私保护的聚类.9 3.1 聚类及聚类分析 .9 3.2 基于集中分布数据的隐私保护方法:几何数据转换 .9 第四章 垂直分布数据隐私保护的聚类.13 4.1 数据分布 .13 4.2 聚类算法 .13 4.2.1 k-means聚类算法.14 4.2.2 层次聚类算法 .15 4.3 分布式环境下隐

10、私保护的聚类 .15 4.3.1 小型数据集的隐私保护 .15 4.3.2 大型数据集的隐私保护.17 第五章实验及其结果.25 5.1 集中分布数据集隐私保护的聚类实验 .25 5.2 半诚实模型下的隐私保护实例 .26 5.3 恶意方存在下的隐私保护 .28 结 论.30 致 谢.31 参考文献.32 1 第一章第一章 绪绪 论论 1.11.1 研究背景及意义研究背景及意义 由于计算机处理能力、存储技术以及互联网络的快速发展，人类拥有的信 息呈爆炸式增长，从而激发了人们寻找“知识宝藏”的意识，进而推动了数据 挖掘的发展。数据挖掘可用来预测别人将来的行动将会怎么样，并尝试从别人 过去的行为预

11、测他们未来的需要。这种行为能够准确的定位市场，提供高效的 商业流程，为客户提供满意和个性化的服务。然而，有些人可能非常不愿意让 别人知道有关自己的信息，同时，战略性规则的公开，可能导致商业上竞争优 势的丧失。所以，伴随着网络技术的发展，数据挖掘中的隐私保护成为了一个 热门的话题。 一般认为，隐私是指用户隐藏个人信息和可以决定是否发布个人信息给其 他人的权利和控制能力。而在数据挖掘中，除了一些可能被误用的个人信息属 于隐私外，数据挖掘的结果也可能包含隐私信息。随着数据挖掘在公私部门使 用的逐渐增加，存在于被挖掘的数据中的潜在的敏感特征越来越引起人们的关 注。 数据挖掘本身并没有侵犯隐私，但挖掘过

12、程中可能会涉及到一些敏感信息， 如何在保护隐私的前提下得到精确的挖掘结果越来越引起人们的关注，而隐私 保护的数据挖掘在数据挖掘和隐私保护之间找到平衡。顾名思义,隐私保护的数 据挖掘方法研究的出发点和最终目标,就是要在合理保护隐私数据的前提下进行 数据挖掘和知识发现,寻找其中潜在的有用的模式与规则。 隐私保护主要考虑两个方面： 第一，为了不侵犯隐私，对于敏感的数据例如身份证号、姓名、地址等等 必须在原始数据库中进行修正和整理。举例：某个医院想分析某种药品对某类 疾病的治疗效果,需要对病人的资料进行分析,由于病历涉及到病人的隐私，显 然，很多病人不愿公开自己的一些敏感信息。这就涉及到如何在保护各方

13、隐私 的条件下如何进行科学准确的临床调查的问题。 第二，随着信息化和网络技术的发展，数据并不是集中分布在一个数据库 2 上的，而是分布在若干个不同的数据库上，通常数据分布在几个想共同合作提 取全局知识的组织上，而隐私的担心又阻止它们直接地共享这些数据，举例： 商业领域:有多家旅游机构希望合作进行旅游市场预测从而共同获利，他们需要 对以往的客户资料进行统计分析。显然，任何一家旅游公司都不愿意向其他公 司公开自己的业务记录数据，以防止泄露商业机密，因此，他们需要有一个安 全的方法来解决联合统计分析问题，同时能保护各自的隐私信息。这就是一个 典型的分布式隐私保护的数据挖掘的例子。 1.21.2 隐私

14、保护数据挖掘的研究现状隐私保护数据挖掘的研究现状 隐私保护的数据挖掘提供了一种方法能够计算出一个数据挖掘算法的结果 而不揭露隐私信息(至少是一些敏感性信息)。根据考虑对象或数据分布的不同， 隐私保护的方法也可以分为两类: 一类是集中式数据隐私保护(Centralized Data Privacy Preserving)，即对集中 提供的数据进行扭曲、扰乱、随机化和匿名化。这是因为数据中可能含有不能 公开的个人隐私信息，如姓名、身份证号码、年龄、工资等。 另一类是分布式数据隐私保护(Distributed Data Privacy Preserving)，即在双 方或多方合作进行数据挖掘时，由于

15、某种原因，参与者往往不愿意将数据与他 人共享而只愿共享数据挖掘的结果。这种情况在科学研究、医学研究及经济和 市场动态研究等方面屡见不鲜。这就要求人们提出保持隐私性的数据挖掘算法， 对于参与者而言，只能获得最终的挖掘结果，除此以外，不能获得他人的任何 其他信息。 隐私保护的数据挖掘涉及到的领域主要是关联规则、分类和聚类。目前， 在所有的隐私保护的数据挖掘中，使用扰乱方法的达到45%，而其余的使用基于 密码学的方法（主要是安全多方计算） 。 1.31.3 主要内容主要内容 本文主要考虑在半诚实模型下和研究在恶意模型情况下的隐私保护的聚类 问题。在半诚实模型下使用普通的正交变换来实现数据扰乱。在恶意

16、模型下,使 3 用随机化的方法来实现隐私保护。最终实验表明所提出的方法在合理的精度下 了实现垂直分布数据的隐私保护。 1.41.4 文章组织结构文章组织结构 第一章 绪 论 主要介绍下隐私保护的基本原理及其现状，总括全篇的研究目标及各个章 节的内容。 第二章 隐私保护数据挖掘概述 主要介绍下其研究的方法及未来的发展，还有就是介绍几个关于安全计算 定义。 第三章 集中分布数据隐私保护的聚类 介绍几种几何数据转换方法，通过对原数据集中一些数据的属性值进行改 变，从而达到隐私保护的目的。该方法的思想主要来源于图形学中图像处理的 一些做法，特别是数字图像中的基本几何变换方法，如平移、缩放、旋转等。 它

17、对于聚类挖掘中隐私保护高效简单，同时独立于数据聚类的各种方法，保持 了类的基本特征，并具有可靠的数学基础。 第四章 垂直分布数据隐私保护的聚类 介绍垂直分布数据结构，两种经典的聚类算法：层次聚类和k-means聚类算 法，最后系统的介绍恶意方的情况下的垂直分布数据隐私保护方法。 第五章 实验及其结果 通过实验验证第三章和第四章的方法的正确可行性。 4 第二章第二章 隐私保护数据挖掘概述隐私保护数据挖掘概述 2.12.1 数据扰乱方法数据扰乱方法 数据扰乱方法（也称数据随机化方法或随机扰动方法）,首先由Agrawal和 Srikant等1首先在2000年提出,目的是保证在挖掘过程中单个记录的值不

18、会露， 即对原始数据加上服从某种分布(均匀分布或正态分布)的“噪声”数据，从而 得到了可以认为是不会泄露原始数据信息的扭曲数据，然后利用扭曲数据的值 以及噪声数据的分布，通过Bayes法则构建原始数据的近似分布。固定数据扰乱 方法是一种最简单的形式，这种方法通过添加一些噪音条件e 而达到使一个秘 密属性X成为Y的目的，当这种方法被用在多属性的数据库中时，数据库中的每 个属性都是独立于其它属性而被扰乱的，这种方法可以描述为Y=X+e或Y=Xe， 后来S.J.Rizvi等人继续沿用，提出布尔属性隐私保持的关联规则挖掘方法，对 初始数据进行异或操作来保证隐私度和正确度，该方法主要应用于事务数据库。

19、还有 很 多基于扰乱技术和分布重构的方法被提出来。Agrawal和Aggarwal提出 了一种基于期望最大化(EM)的方法，它更有效地实现了分布重构，最大可能的 使重构分布接近于原始数据的分布，降低了信息丢失的水平。同时也提出了一 个很好的隐私定义和测量隐私的方法。Evfimievski等人也提出了类似的挖掘关 联规则的方法。Polat等人则提出了应用在协同过滤(CF)技术的随机扰乱方法， 也能够很好的保护用户的隐私，满足隐私政策的要求。实验已经证明，在应用 分类和关联规则等数据挖掘技术时，通过挖掘应用了随机化扰乱技术后的数据 集得到的结果和挖掘原始数据集一样精确。当然，随机扰乱技术也有一些限

20、制， 这是因为当我们对扭曲后的数据进行分布重构时，扭曲数据也给出了关于原始 数据值的信息。Kargupta等人正式分析了随机化技术的安全性，并证明了在很 多情况下，随机化对隐私的保护是有限的。而Evfimievski等人则提出一种隐私 裂口的定义，并提出一种称为防止隐私裂口的方法，使得在使用随机化技术保 护数据挖掘中的隐私时能够限制隐私的破裂。 对于聚类分析中的隐私保护方法，StanleyR .M.Oliveira2等人提出的通过 几何数据转换达到聚类隐私保护的方法。主要通过几何转换如平移，缩放和简 5 单的旋转等转化初始数据，但是，这个方法容易改变数据的相似性，从而造成 聚类的误差，同时，这

21、个方法对于空间的维数也是有限制的。后来 StanleyR.M.Oliveira等人再次提出保持空间距离不变的基于旋转的转换(RBT) 方法，实现了多维空间中点的等距变换，达到了很好的隐私保护效果。但是， 该方法在用户提出过高隐私要求时可能无法取得合适的旋转角度，同时，该方 法没有讨论所有等距变换。无论利用哪种随机扰动方法实现隐私保护的数据挖 掘，基本步骤是相似的：(1)提出具体扰动方法；(2)重构方法；(3)与现有挖掘 算法的整合；(4)提出衡量隐私泄露以及算法优化标准。优点:简单,代价低。缺 点:精度不高。其基本思想是修改敏感数据使其失去它敏感意义，但要保留其统 计学的特性。这类方法的一个主

22、要问题是需要在挖掘结果的正确性和隐私之间 做出折衷，不容易得到精确的挖掘结果。 2.22.2 基于密码学的技术基于密码学的技术 基于密码学的技术，最主要的是安全多方计算(SMC） 。安全多方计算问题 主要解决如何在相互不信任的各方之间合作计算的问题。一种简单的形式是安 全两方计算,起源于YAO的百万富翁问题。基本问题是两个百万富翁想知道谁 更富有一些，但是谁都不想揭露净资产值。理论上说，这个问题是简单地比较 两个数字的大小，每一方拥有一个数字，任何一方都不想把它的数字揭露给另 一方。YAO提出了一种解决方案。以后被扩展到安全多方计算(SMC)。 安全多 方计算( Secure Multi-pa

23、rty Computation , SMC)是指在一个互不信任的多用户 网络中,各用户能够在不泄漏各自私有输入信息的情况下协同合作执行某项可靠 的计算任务。理论上，安全多方计算可以通过电路计算协议获得解决，解决思 路很简单，首先将要计算的函数F表示成布尔电路，然后参与方利用一个小的协 议安全计算电路中的门电路，最终各方获得结果的一个分量。这个协议理论上 说非常完美，但由于协议的效率由输入和电路的大小来决定，对于具有大量输 入的算法，协议效率非常低。因此构造高效的隐私挖掘算法依然是需要解决的 问题。利用 安 全 多方计算进行隐私保护的方法首先由Lindell等人提出，针对 两个私有数据库情形，他

24、们利用密码工具构建了ID3决策树，并且在协议中保证 6 了零知识泄露。Lindell等人的方法主要针对水平型分布的数据库。依照这个方 法，刘毅辉等针对数据分类算法中应用非常普遍的朴素贝叶斯分类算法，利用 安全两方计算协议，给出一个保持隐私的朴素贝叶斯分类协议。在保持计算隐 私性的同时，协议在计算复杂度和传输复杂度上与一般的贝叶斯分类非常接近， 协议高效可行。 从垂直型分布的数据库中，挖掘隐私关联规则的关键步骤是项集支持度的 计算，如果可以通过异地双方的中间数据安全计算全局项集支持度，然后将该 全局项集支持度同阀值进行比较，即可判定该项集是否频繁集。而项集支持度 的计算可以认为是矩阵的计算，Va

25、idya3等人提出了一种利用K个方程求解K+N 个未知数的不确定性来解决项集支持度计算安全性的方法，但是该方法的主要 缺点在于如果对方知道了所有的方程式，就可以计算出本方的所有隐私的数据。 同时该方法的传输速率比较低，在双方计算项集支持的同时，需要传送K个矩阵， 计算任一个项集支持度时，都需要产生新的N个随机值，重新传送K个矩阵，因 此该方法在使用中存在很大程度的效率问题。针对上述的情况，沈旭昌等人提 出了一种新的分布式的关联规则挖掘算法，该算法可以大大增加计算过程的安 全性，在多次使用的过程中，可以复用原有数据，不需要多次传送所需数据， 因此在效率上有很大程度的提高。对于聚类分析中的隐私保护

26、问题，也有一些 很好的解决方法。Vaidya等人提出了应用于垂直分布类型的聚类分析的方法， 主要是使得每个站点在得到聚类结果时，不会泄露自己站点内部的事务属性值。 而Merugu等人也提出了一种解决分布式聚类分析的隐私保护方法，在这个方法 中，每个站点共享部分原始的数据或扰乱的数据，在每一个本地站点生成合适 的参数，然后把参数传送给中心站点，通过合理的抽样完成了高质量的分布式 聚类，实验证明这个方法具有合理的隐私丢失和低的交流成本。Vaidya等人提 出了应用于垂直分布类型的聚类分析的方法, 主要是使得每个站点在得到聚类 结果时, 不会泄露自己站点内部的事务属性值。Merugu等人也提出了一种

27、解决 分布式聚类分析的隐私保护方法,在这个方法中, 每个站点共享部分原始的数据 或扰乱的数据,在每一个本地站点生成合适的参数, 然后把参数传送给中心站点, 通过合理的抽样完成了高质量的分布式聚类, 实验证明这个方法具有合理的隐 私丢失和低的交流成本。S.Jha等人针对水平分布类型的聚类分析方法, 使用安 7 全计算的方法, 提出了一种解决k-平均聚类分析的隐私保护方法, 在聚类挖掘 的过程中, 使用了基于健忘多项式计算和同态加密的协议, 从而达到在计算聚 类中心时, 私有信息没有泄露出来的目的，但是这种算法使用k-means算法作为 初始候选算法，也带有k-means算法的缺陷。 2.32.3

28、 未来隐私技术的发展未来隐私技术的发展 对于未来隐私保护技术的发展，一些关键的要求可以成为发展的指南:(1) 独立性，一个理想的数据挖掘隐私保护技术方案应该是独立于各种各样的数据 挖掘算法。(2)准确性，一个有效的解决方案应该能够在隐私和挖掘结果的准确 性之间找到平衡。(3)隐私水平，这是隐私保护的基本原则，隐私保护方案必须 确保在数据挖掘的过程和结果中不违反隐私规定。(4)不同的属性类型，一个好 的隐私保护技术应该能够处理各种不同的属性类型。(5)多功能性，一个多功能 的隐私保护技术应该能够应用在不同的数据源分布，它不但可以用在集中式的 数据上，也可以用在分布式的数据上。(6)交流代价，当数

29、据是分布在不同的站 点时，隐私保护技术应该考虑各个站点之间交流的代价。 数据挖掘可能对人们的隐私和数据安全构成威胁。然而，就象我们所看到 的一样，为了防止收集的数据被误用，己经有很多解决方案被提出来。而且， 数据库系统中的数据安全增强技术也可以用在数据挖掘中，来保证收集到的数 据或挖掘结果的安全。随着公司和消费者的不断努力，更多保护数据隐私和安 全解决方案的提出，数据挖掘一定能在符合隐私保护要求的情况下给我们带来 更多的有趣的知识。 2.42.4 几种安全计算模型的定义几种安全计算模型的定义 （1）honest adversaries:两方或多方把需要计算的数据送给这个方进行安全 的处理,这一

30、方处理后公布结果。一般情况下这种完全可靠的方是不现实的,这 只是一种理想的模型。 （2）semi-honest adversaries: （或诚实的且好奇的）对手会严格按照协议 的规定执行，但在协议运行期间设法从他们所观察到的数据中推导出其它方的 8 秘密信息。 （3）malicious adversaries: 恶意对手可能会做任何它想做的设法去推导出 秘密信息（在多项式计算范围内） 。它们可能在任何时间中途中断协议，发送伪 造的信息，哄骗信息，同其它（恶意）方联合作弊等。这种情况比较复杂，目 前很少有文献提出解决恶意对手问题的方法。 2.52.5 两个基本协议两个基本协议 2.5.1 求和

31、协议 假设存在 r(r2)方，P1,Pr, Pi方拥有数值 Vi,各方之间没有共谋现象。 各方都想得到和 V=, 但又不愿泄露本方的数值,则由一个半可信第三方 1 r i i V SP 产生一个随机数 R 并送往 P1方, P1方计算 R+V1将其传送给 P2, P2 计算 R+ ，并将其传送给 P3，依此类推，Pr最终得到 R+，并将其传送给 2 1 i i V 1 r i i V SP，SP 计算 R+-R= 并公布这个和。 1 r i i V 1 r i i V 2.5.2 点积协议 向量的点积协议其实是矩阵点积协议的一种特殊形式,设有两个向量 Xx 1 x x 和 Yy y y ,分别

32、属于两个方 PA和 PB,要求在各方不透露本方 2n T 12n T 的任何属性信息的情况下,安全地计算 X Y,步骤为:1)方 PA产生一个与 X 为互 T 为正交的向量 Z=z z z ,使得 Z X=0；2) PA计算 U=(I-ZZ ),且对 U 进 12n TTT 行 QR 分解,得到两个矩阵 Q 和 R,并将 R 发送给 PB, PA计算 X Q, PB计算 RY, T PA和 PB将计算结果发送给半可信第三方 SP；3)SP 计算X QRY= X (I- ZZ ) TTT Y=X Y，因为 X Z=0。 TT PA虽然知道U及它的分解矩阵 R 和 Q，但是它对于 PB的向量一无所

33、知， PB对 PA向量也是一无所知，半可信第三方并不知道 R 和 Q，所以它根据两个 乘积 X Q 和 RY 根本无法推断出 X 或 Y 的值，因为所有参与方都不共谋，所以 T 这个协议是安全的。在执行这个协议过程中,每个方与 SP 只需通信一次,两个 9 方之间也只需通信一次,执行一次协议,共需通信三次。 10 第三章第三章 集中分布数据隐私保护的聚类集中分布数据隐私保护的聚类 3.13.1 聚类及聚类分析聚类及聚类分析 聚类是一个将数据集划分为若干组或类的过程，使得同一个组内的数据对 象具有较高的相似度，而不同组中的数据对象则是不相似的。聚类分析的基本 指导思想就是最大程度地实现类中对象相

34、似度最大，类间对象相似度最小。相 似或不相似的度量是基于数据对象描述属性的取值来确定的。通常就是利用 （各对象间）距离来进行描述的。聚类分析是一个正在蓬勃发展的领域，其应 用也变得越来越广泛，如顾客的购买行为分析、模式识别、市场分析等4。 在商业合作中，经常需要进行聚类分析。不同的公司，各自都拥有自己的 客户购买行为的数据集。为了共同的利益，决定利用聚集数据进行挖掘。假设 聚类的目标是对商场购买力较大的客户居住地进行分析，以帮助商场主管针对 相应客户群采取针对性的营销策略。那么各个公司必须确信能够在本公司客户 的隐私不受侵害的情况下获取最终的聚类挖掘结果。 3.23.2 基于集中分布数据的隐私

35、保护方法基于集中分布数据的隐私保护方法: :几何数据转换几何数据转换 所谓几何数据转换方法，就是通过对原数据集中一些数据的属性值进行改 变，从而达到隐私保护的目的。该方法的思想主要来源于图形学中图像处理的 一些做法5，特别是数字图像中的基本几何变换方法，如平移、缩放、旋转等。 它对于聚类挖掘中隐私保护高效简单，同时独立于数据聚类的各种方法，保持 了类的基本特征，并具有可靠的数学基础。 假设所要进行聚类分析的数据集可用数据矩阵Dmn表示，行表示数据集有m 个对象，列表示每个对象都有n 个属性Ai（i = 1，n），Ai可以为数值属性 或其他类型。如果有d（d n）个属性被认为是敏感的，是需要隐藏

36、的，则需 要对m d 矩阵进行转换操作。该矩阵可作为欧氏空间的一个矢量子空间V 看待，其中有viV，vi =（a1，a2，ad），1id，ai为Ai的一个实例。几何 数据转换方法（Geometric Data Transformation Method，GDTM）就是通过采取 11 图形学中图形转换的类似操作，对每一个vi实施一个统一噪音矢量N，使V 变成 V，从而使一些真实数据被改变。其中，所用的几何转换函数f 包括平移、缩放 及旋转，具体操作相应为加法（Add），乘法（Mult）和旋转（Rotate）变化。 若用有序对来表示该过程，即有GDTM =（V，f）。几何数据转换方法包括以下 几种

37、： (一)平移数据转换方法（TDTM） 平移是指将物体沿直线路径从一个坐标位置移到另一个坐标位置的重定位。 即通过给原始坐标位置（x，y）加上一个距离 tx和 ty来平移二维点以实现移到 新位置（ x，y）的移动。 一对平移距离（tx，ty）称为平移向量（Translation Vector）或移动向量。 x=x+ tx，y =y+ty。 输入：初始矩阵V，噪音矢量集合N 输出：转换结果矩阵V 算法执行步骤： （1）对于V 中的任一敏感属性Aj执行下列操作：为Aj选取一噪音矢量 ej，ejN；所选转换操作为加法操作。 （2）对于每个vi，viV，对其中的每个属性对象aj （ajvi）根据噪音矢

38、 量ej实施数据转换，使ajaj。 算法示例：假设有某保险公司个人参保客户样本数据，如表3.1 所示。现 需对表中年龄和参保年限两个属性进行隐藏，采用平移数据转换方法，定义统 一噪音矢量N=（ ，），则表3.2为经过转换后的数据表。 表3.1 初始样本数据表 表3.2 平移转换后的结果数据表 编号性别年龄文化年限 001男30本科3 002女25本科1 003女35本科8 004男40本科10 编号性别年龄文化年限 12 (二)旋转数据转换方法（RDTM） 二维旋转是将物体沿xy 平面内的圆弧路 径重定位。为了实现旋转，需要指定旋转角 和物体旋转的旋转点的位置。旋转角的正值 定义绕基准点逆时针

39、旋转，负值则以顺时针 方向旋转物体。相对于原点将在位置（x，y）处的点旋转角 的变换方程为x = xcos - ysin，y = xsin + ycos。 输入：初始矩阵V，噪音矢量集合N 输出：转换结果矩阵V 算法执行步骤： （1）对于V 中的任一敏感属性Aj和Ak所组成的属性对执行下列操作:为 (Aj,Ak)选取一角度矢量；所选转换操均为旋转操作。 （2）对于每个vi，(viV)，对其中的每个属性值对（,）(,vi),根 j a k a j a k a 据角度矢量实施数据旋转，使(,)(,)。 j a k a j a k a 算法示例：样本数据如表3.1 所示，同样对表中年龄和参保年限两个

40、属性进行 隐藏。采用旋转数据转换方法，定义统一噪音矢量N=（）。表3.3 为经过转换后的数据表。 表3.3 旋转换后的结果数据表 表3.4 缩放转换后的结果数据表 编号性别年龄文化年限 001男24本科3.6 002女20本科1.2 003女28本科9.6 004男32本科12 (三)缩放数据转换方法(SDTM) 缩放变换用于改变物体的尺寸。对多边 形缩放则可通过将每个顶点的坐标值乘以缩放系数sx和sy以产生变换的坐标来实 现x = x sx，y = y sy。采用缩放数据转换方法，定义统一噪音矢量N = ，）。 001男25本科8 002女20本科6 003女30本科13 004男35本科1

41、5 编号性别年龄文化年限 001男29本科8.2 002女24本科5.3 003女33本科13.9 004男37本科16.8 13 输入:初始矩阵V,噪音矢量集合N 输出:转换结果矩阵V 算法执行步骤:(1)对于V叶的任一敏感属性Aj执行以下操作: 为Aj选取一 噪音矢量ej，ejN；所选转换操作为乘法操作。(2)对于每个vi，viV，对其 中的每个属性对象aj （ajvi）根据噪音矢量ej实施数据转换，使ajaj算法示 例：样本数据如表1 所示，同样对表中年龄和参保年限两个属性进行隐藏。采 用缩放数据转换方法，定义统一噪音矢量N =（ ， ）。表3.4为经过转换后的数据表。 (四)混合数据转

42、换方法（HDTM） 所谓混合数据转换方法就是针对多个敏感属性任意采取平移，缩放和旋转 等不同的变换。 输入：初始矩阵V，噪音矢量集合N输出：转换结果矩阵V算法执行步骤： （1）对于V 中的任意一个(或对)敏感属性A执行下列操作，为A 选取一 噪音矢量e（eN）；所选转换操作为加法，乘法或旋转变化。 （2）对于每个vi （ viV），对其中的每个(或对)属性值a（ avi）根据 相关属性上的噪音矢量e 实施数据转换，使aa。 算法示例：样本数据如表1 所示，同样对表中年龄和参保年限两个属性进 行隐藏。采用混合数据转换方法，定义统一噪音矢量N =（ ， ）。表3.5为经过转换后的数据表。 表3.5

43、 混合转换后的结果数据表 编号性别年龄文化年限 001男28本科2.7 002女23本科0.9 003女33本科7.2 004男38本科9 14 第四章第四章 垂直分布数据隐私保护的聚类垂直分布数据隐私保护的聚类 4.14.1 数据分布数据分布 数据分布：大多数据传统的数据挖掘方法主要基于集中分布式的数据，而 出于数据的机密性和隐私保护的考虑，隐私保护的数据挖掘(PPDM)研究的环境 大都都为分布式环境，分布式数据分为水平分布的数据和垂直分布的数据两种 情况。 水平分布的数据：不同实体的相同的信息集被分布在不同的站点上（不同 的实体对不同的对象收集相同的信息） ，每一方收集关于 m 个属性 A

44、1，A2Am 的信息。方 Pi收集到关于 ni个对象的信息，n0+n1+nk-1=n(不同的方收集关于 不同实体的信息)，例：几个银行对于不同的客户收集有关信誉卡交易的相似信 息；不同的超市收集同类食品的购买数据。 垂直分布的数据是指同样实体集的信息被分布在不同的站点上， （不同的方 对于同一个实体集收集到不同的特征信息） ，如对于同样的 n 个客户银行收集到 金融交易信息而国税务局收集税务信息。形式化说明即：假设有 r 个不同的方， P1，P2，Pr，m 个属性，方 Pi收集到有关 mi个属性的信息，Ai,1,Ai,mi。属 性总数为 m0+m1+mn-1=m。所有的方都拥有关于 n 个同样

45、的对象的信息。 4.24.2 聚类算法聚类算法 聚类是将对象集合按照相似性归为若干类别,与分类和预测不同,属于无指 导分类,即分析数据对象而不考虑已知的类标记。属于同一类的对象具有较高的 某种相似性,而不同类的对象之间的差别较大。对象根据最大化类内相似性、最 小化类间相似性的原则进行聚类或分组，这样形成的一个簇（聚类）都可以看 作一个对象类。聚类算法主要分为以下几种:基于划分的聚类方法，层次聚类方 法，基于密度的聚类方法。 类间距离的度量:相似度是定义一个聚类的基础，两个类的相似度的度量标 准对聚类算法来讲是不可缺少的，一个聚类分析过程的质量取决于度量标准的 15 选择。相似度测量:在聚类分析

46、中,需要计算对象间的相似度(或相异度),常用对 象间的距离来表示。最常用的距离度量方法有欧氏距离、曼哈坦距离和明考斯 基距离等，本文采用的是欧氏距离，两个 m 维属性 X(x1,x2,xm)和 Y（y1,y2,ym）之间的欧氏距离表示为: 20.5 1 (, )() ) m iii dist X Yxy 一个n*m的数据矩阵表示n对象m个属性，数据矩阵中所有对象间的距离形成 的矩阵称为相异矩阵。 图 4.1 数据矩阵D和相异矩阵d 欧氏距离满足以下几个属性： (1)dist(X,Y)0:距离是一个非负数 (2)dist(X,Y)=0:对象到它自身的距离 (3)dist(X,Y)= Distan

47、ce(Y,X):距离是对称的函数 (4)dist(X,Y)Distance(X,K)+ Distance(K,Y):距离满足三角不等式 4.2.1 k-means 聚类算法 k-means 聚类算法是一种简单的基于划分的聚类算法,k-means 算法最大的 特点是处理大量的高维的数据集时很高效,算法简单、计算复杂度低,只有 O(nkt)， 其中 n 是对象的总数，k 是簇的个数，t 是迭代的次数，通常 kn，tn，则复 杂度为 O(n)。该方法的局限性：依赖k值的指定，聚类结果依赖初始聚类中心 的选择，会出现因初始聚类中心选择的随机性，导致聚类结果的不确定性现象， 且算法存在对离群点敏感、易陷

48、入局部最优解、仅适合发现球状簇，难以发现 复杂形状簇等缺陷，k-means 算法可以这样描术： (1)初始化k个中心12，,k为0。 16 (2)随机选取k个初始点，, 作为初始聚类中心。 1 2 k Repeat (3)for(i=1;i=n,i+) if(dist(i,j)对于所有的j最小) 将点i分配给聚类j End for (4)计算新的中心，, 1 2 k (5)重复(3)-(4),直到(12，,k)=( ，, ) 1 2 k 4.2.2 层次聚类算法 层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚 类,它又可以分为两类,即自底向上的聚合层次聚类和自顶向下的分解层次

49、聚类。 聚合聚类的策略是先将每个对象各自作为一个原子聚类,然后对这些原子聚类逐 层进行聚合,直至满足一定的终止条件;后者则与前者相反,它先将所有的对象都 看成一个聚类,然后将其不断分解直至满足终止条件。 对于聚合聚类算法来讲,根据度量两个子类的相似度时所依据的距离不同, 又可将其分为基于Single-Link, Complete-Link和Average-Link的聚合聚类。 Single-Link在这三者中应用最为广泛,它根据两个聚类中相隔最近的两个点之间 的距离来评价这两个类之间的相似程度,而后两者则分别依据两类中数据点之间 的最远距离和平均距离来进行相似度评价。 Single-Link层

50、次聚类算法的描述如下: (1)把每一个样本作为一个类。为所有的无序样本对的类间距离构造一个序 列，然后按升序对这个序列进行排序。 (2)按照已排序的距离序列顺序，将距离比最近的一对样本合并成一个新的 类,计算这个类的中心作为新合并的类的中心,重复这个过程,直至达到用户的要 求为止。 4.34.3 分布式环境下隐私保护的聚类分布式环境下隐私保护的聚类 17 4.3.1 小型数据集的隐私保护 对小型数据集来说，如果垂直分布的数据中各方拥有的属性数均为偶数， 则各方就可以局总地进行数据扰乱，不需要方之间的交互，但是属性在各方的 分布是随机的，包括各种可能的情况，一些方的属性个数为奇数或某一方只有 一

51、个属性等。这样就需要将两方的属性组成一个属性对来进行数据扰乱，需要 双方合作安全的完成这个过程。 设需要合作的方为 PA和 PB，PA有属性 a=a1 a2 an T, PB有属性 b=b1 b2 bnT，选择的扰乱矩阵为 T=，扰乱后的属性为：a和 b， cossin sincos 扰乱前两个属性己被规格化，则基于旋转的扰乱过程为： = b a cossin sincos n n bb aa 1 1 cossin sincos ii ii ba ba （i=1,2,n） 令 X= Y=，则 = b a b a YX n i ii n i ii ab ba n 1 1 sin)cos1 ( s

52、in)cos1 ( 1 则 var（X-Y）=- n 1 sin)cos1 ( sin)cos1 ( ii ii ab ba n i ii n i ii ab n ba n 1 1 )sin)cos1 ( 1 )sin)cos1 ( 1 2 = (4.1) n 1 n i kk ki ikk ki n i kk ki ikk ii aan n bbn n bbn n aan n 1 2 , 1 2 , ) 1( sin ) 1( )cos1 ( ) 1( sin ) 1)( )cos1 ( A = (4.2) i n 1 2 , ) 1( 1 ikk ki aan n B = - (4.3)

53、i n 1 i bn n ) 1( 1 ikk k b , 2 C = (4.4) i n 1 ikk ki aan n , ) 1( 1 ikk ki bbn n , ) 1( 1 18 令 A=A B=B C=C n i 1 i n i 1 i n i 1 i 其中的 A 和 B 可以由两方局部地求出,不需要第三方参与,而 C 需要两方和 第三方共同合作,利用隐私保护的协议来完成。 定理定理 4.1:4.1:PA虽然知道 B(方PB也知道A)的值,且两方都知道最后的 C 值,但 是 PA (相对的方 PB)从 A 和 C 的值(从 B 和 C)不能推断出具体的 PB方的属性 b (相对的

54、PA方的属性 a )。 ii 证明:因为 A=A , C=C,A是 n 个属性的算术运算,C 是包含两个 n i 1 i n i 1 iii n 维属性的算术运算,所以方 PB只根据这两个数不能推断出 a (i=1,2,n)的 i 值。同理方 PA也不能推断出 b 的值。 i 在文献6己证明两个属性组成的属性对的的最大隐私保护度为 4，其 n n1 中n为对象的数目，两方根据最大隐私保护度和每个属性的相对隐私保护度求 出最小隐私保护度，设为，两方根据 var(a-a)及 var(b-b) BA 和 A ,两方利用安全协议求出各自的角度范围,发送给第三方,第三方确定一个合 B 适的公共角度,公布

55、给两方,两方利用这个角度形成本方属性的扰乱结果,发送给 第三方,第三方对各方发送来的扰乱的数据进行聚类,公布聚类结果。试验在第 五章。 4.3.2 大型数据集的隐私保护 对于小型数据集属性间的点积和欧氏距离,可以以属性为单位进行计算,但 对于大型数据集,出于效率考虑,不能这样计算，因此这一节提出基于数据扰乱 方法对大型垂直分布的数据集进行隐私保护。所谓垂直分布数据即不同方收集 相同对象的不同的属性信息，Pi方收集了 mi个属性的信息，如属性总数为 m， 1211,.1 111212 111212112 1,.1 1,11,1,11,1 ,1,1,1,.1,.1 . . . . . . rmmmr rr mmm mmmm nn mn mn mmn mmmn mmm aa aaaa