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

JIANGSUUNIVERSITY本科毕业论文基于隐私保护的聚类挖掘的研究与实现ResearchandImplementationofPrivacyPreservingClusteringMining学院名称：计算机科学与通信工程学院专业班级：学生姓名：指导教师姓名：指导教师职称：年月I基于隐私保护的聚类挖掘的研究与实现专业班级：学生姓名：指导老师：职称：摘要：随着数据库和网络技术的发展，数据在数量和复杂性上出现了很大的增长，随之出现了数据挖掘这一强有力的数据分析工具。其能发现数据中的规律，为很多领域做出了巨大贡献，应用前景广泛。然而，在很多情况下，数据持有者可能出于数据安全和敏感性等原因而不想和别人共享自身的数据，如何在私有数据不被泄露的前提下得到精确的挖掘结果也就成了当前数据挖掘的一大研究方向，称为基于隐私保护的数据挖掘。本文既考虑在半诚实模型下又研究在恶意模型情况下的隐私保护的聚类问题，在半诚实模型下,各个方之间不存在共谋作弊现象,所以使用普通的正交变换来实现数据扰乱，实验得到扰乱前后两属性间距离不变。在恶意模型下,由于恶意方可能会中途中断协议,联合其它方作弊等,这种情况下普通的正交变换已失去了保护性,所以考虑使用随机化的方法来实现隐私保护，其先使用层次聚类算法确定初始聚类中心,然后用k-means聚类算法进行欧氏距离实验测试，最后得出误差在合理精度范围之内。实验表明所提出的方法在合理的精度下实现了垂直分布数据的隐私保护。关键词：隐私保护；数据挖掘；聚类；垂直分布；恶意模型；半诚实模型；数据扰乱IIResearchandImplementationofprivacypreservingclusteringminingAbstract:Withthedevelopmentofdatabaseandnetworktechnology,thenumberandcomplexityofdatagrowalot.Thereappearsapowerfuldataanalysistoolscalleddatamining,whichcanfoundthelawofthedata.Ithasmadetremendouscontributionstomanyareasandithasanextensiveapplyprospect.Butinmanycases,thedataholdersmaydonotwanttosharetheirowndatawithothersforsomereasons,suchasdatasecurityandsensitivityandsoon.Howcangetaccurateminingresultwithoutleakingtheprivatedataisbecomingamajorresearchdirectionofdatamining.Itiscalledprivacypreservingdatamining.Thispaperconsiderstheproblemofthesemi-honestmodelbutstudytheclusterproblemofthemaliciousmodeltotheprivacyprotection.Inthesemi-honestmodel,eachpartydoesnotcheatinconspiracy,therefore,weuseordinaryorthogonaltransformationtocarryoutthedataperturbation，theexperimentgetsthatthedistancebetweenthetwounchanged.Inthemaliciousmodel,asmaliciousmayinterrupttheagreementinthehalfway,andcheatwithothersandsoon,inthiscase,ordinaryorthogonaltransformationhaslostitsprotective,soweconsiderusingrandomperturbationtoachieveprivacyprotection,itfirstuseclusteralgorithmtodeterminetheinitiallevelofclustercenter,andthenusek-meansclusteralgorithmtocarryoutEuclideandistancetest,finally,itgetsthattheerrorisinareasonableaccuracy.Theexperimentsshowthatthismethodcancarryouttheverticaldistributionofdataprivacyprotectionwithreasonableaccuracy.Keywords:privacypreserving;datamining;clustering;verticaldistribution;maliciousmodel;semi-honestmodel;dataperturbationIII目录第一章绪论..........................................11.1研究背景及意义................................................11.2隐私保护数据挖掘的研究现状....................................21.3主要内容......................................................21.4文章组织结构..................................................3第二章隐私保护数据挖掘概述............................42.1数据扰乱方法..................................................42.2基于密码学的技术..............................................52.3未来隐私技术的发展............................................72.4几种安全计算模型的定义........................................72.5两个基本协议..................................................82.5.1求和协议..................................................82.5.2点积协议..................................................8第三章集中分布数据隐私保护的聚类.......................93.1聚类及聚类分析................................................93.2基于集中分布数据的隐私保护方法:几何数据转换...................9第四章垂直分布数据隐私保护的聚类......................134.1数据分布.....................................................134.2聚类算法.....................................................134.2.1k-means聚类算法..........................................144.2.2层次聚类算法.............................................154.3分布式环境下隐私保护的聚类...................................154.3.1小型数据集的隐私保护.....................................154.3.2大型数据集的隐私保护......................................17第五章实验及其结果...................................255.1集中分布数据集隐私保护的聚类实验.............................255.2半诚实模型下的隐私保护实例...................................265.3恶意方存在下的隐私保护.......................................28结论..................................................30致谢..................................................31IV参考文献................................................321第一章绪论1.1研究背景及意义由于计算机处理能力、存储技术以及互联网络的快速发展，人类拥有的信息呈爆炸式增长，从而激发了人们寻找“知识宝藏”的意识，进而推动了数据挖掘的发展。数据挖掘可用来预测别人将来的行动将会怎么样，并尝试从别人过去的行为预测他们未来的需要。这种行为能够准确的定位市场，提供高效的商业流程，为客户提供满意和个性化的服务。然而，有些人可能非常不愿意让别人知道有关自己的信息，同时，战略性规则的公开，可能导致商业上竞争优势的丧失。所以，伴随着网络技术的发展，数据挖掘中的隐私保护成为了一个热门的话题。一般认为，隐私是指用户隐藏个人信息和可以决定是否发布个人信息给其他人的权利和控制能力。而在数据挖掘中，除了一些可能被误用的个人信息属于隐私外，数据挖掘的结果也可能包含隐私信息。随着数据挖掘在公私部门使用的逐渐增加，存在于被挖掘的数据中的潜在的敏感特征越来越引起人们的关注。数据挖掘本身并没有侵犯隐私，但挖掘过程中可能会涉及到一些敏感信息，如何在保护隐私的前提下得到精确的挖掘结果越来越引起人们的关注，而隐私保护的数据挖掘在数据挖掘和隐私保护之间找到平衡。顾名思义,隐私保护的数据挖掘方法研究的出发点和最终目标,就是要在合理保护隐私数据的前提下进行数据挖掘和知识发现,寻找其中潜在的有用的模式与规则。隐私保护主要考虑两个方面：第一，为了不侵犯隐私，对于敏感的数据例如身份证号、姓名、地址等等必须在原始数据库中进行修正和整理。举例：某个医院想分析某种药品对某类疾病的治疗效果,需要对病人的资料进行分析,由于病历涉及到病人的隐私，显然，很多病人不愿公开自己的一些敏感信息。这就涉及到如何在保护各方隐私的条件下如何进行科学准确的临床调查的问题。第二，随着信息化和网络技术的发展，数据并不是集中分布在一个数据库上的，而是分布在若干个不同的数据库上，通常数据分布在几个想共同合作提取全局知识的组织上，而隐私的担心又阻止它们直接地共享这些数据，举例：商业领2域:有多家旅游机构希望合作进行旅游市场预测从而共同获利，他们需要对以往的客户资料进行统计分析。显然，任何一家旅游公司都不愿意向其他公司公开自己的业务记录数据，以防止泄露商业机密，因此，他们需要有一个安全的方法来解决联合统计分析问题，同时能保护各自的隐私信息。这就是一个典型的分布式隐私保护的数据挖掘的例子。1.2隐私保护数据挖掘的研究现状隐私保护的数据挖掘提供了一种方法能够计算出一个数据挖掘算法的结果而不揭露隐私信息(至少是一些敏感性信息)。根据考虑对象或数据分布的不同，隐私保护的方法也可以分为两类:一类是集中式数据隐私保护(CentralizedDataPrivacyPreserv