基于抽样的隐私保护聚类挖掘算法研究

河北工业大学硕士学位论文基于抽样的隐私保护聚类挖掘算法研究姓名：刘风丽申请学位级别：硕士专业：管理科学与工程指导教师：吴晓丹20071101河北工业大学硕士学位论文i基于抽样的隐私保护聚类挖掘算法研究摘要数据分析与处理技术迅速发展，在公布或共享数据以挖掘有效决策信息和知识的同时，不免暴露出个人和公司隐私泄露问题，进而催生了隐私保护数据挖掘这一研究领域并在近三年成为国内外研究者关注的焦点。数据挖掘中的聚类挖掘是分析管理问题的重要方法之一，常应用于市场细分、客户分类与制造系统单元化设计等重要领域，而要得到这些结果则需要涉及大量详细具体的敏感性数据和信息，与此同时数据中潜在的模式和规律也很有可能对隐私和信息安全构成威胁。因此随着客户个性化需求时代的急速发展，聚类隐私保护算法也成为亟待解决的关键隐私保护数据挖掘问题。目前关于隐私保护聚类挖掘算法才刚刚起步，采用的隐私保护算法也相对简单，且现有的隐私保护聚类算法在效率效果上均存在着难以调和的矛盾。基于这种现状，本文提出了抽样隐私保护聚类算法，在保证数据隐私性和聚类结果准确性的同时，还可以处理大规模数据。论文主要贡献在于依据基于密度和基于模型聚类算法可构建聚类分布函数的原理，构造了均匀抽样、一元正态和多元正态抽样等三种聚类分布函数。并指出加和模糊系统与高斯混合函数的等价性，确立了基于模糊C均值聚类统计结果的分布函数参数的昀优估计，进而应用随机抽样技术，产生了既具原始数据聚类特征又能保护隐私的新数据，并给出了算法流程的详细描述。昀后通过仿真实验，验证了本文算法的有效性，并给出了各种隐私保护聚类方法的优势和适用条件。关键词：数据挖掘，隐私保护，聚类分析，抽样河北工业大学硕士学位论文iiRESEARCHONPRIVACYPRESERVINGCLUSTERINGMININGALGORITHMBASEDONSAMPLINGTECHNIQUEABSTRACTWiththedevelopmentofdataanalysisandprocessingtechnique,theprivacyleakproblemaboutindividualorcompanyisinevitablyexposedwhenreleasingorsharingdatatomineusefuldecisioninformationandknowledge,thengivethebirthtotheresearchfieldonprivacypreservingdataminingandbecomethefocusoftheresearcherhomeandabroadinrecentthreeyears.Clusteringindataminingisoneoftheimportantmethodstoanalyzemanagementproblem,suchasmarketsegmentation,customerclassificationandmanufacturingsystemmoduledesignandsoon.Inordertoobtaintheseresults,itinvolvesalargenumberofdetailedsensitiveinformation.Atthesametime,thepotentialmodelsandpatternsindatabasemaybringthreattoprivacyandinformationsecurity.Therefore,withtherapiddevelopmentofpersonalizeddemandofcustomers,privacypreservingclusteringalgorithmbecomesthekeyissueofprivacypreservingdataminingproblemwhichneedstobesolvedurgently.Atpresent,privacypreservingclusteringalgorithmhasjustbegun,andprivacypreservingtechniqueadoptedisverysimple.Furthermoretheefficiencyandtheeffectivenessoftheprivacypreservingclusteringalgorithmshavecontradictions.Basedonsuchscenario,thispaperpresentsasampling-basedprivacypreservingclusteringalgorithm,inthepremiseofensuringthedataprivacyandtheaccuracyofclusterresults,italsocanprocessdatabasewithaquantitydata.Thecontributionsofthisdissertationareasfollows:accordingtothetheoryofdensity-basedclusteringalgorithmandthemodel-basedclusteringalgorithmwhichcanconstructclusteringdistributionfunction;threedistributionfunctionshavebeenconstructed.Theyaretheuniformsamplingmodel,theGaussiansamplingmodelandthemixtureGaussiansamplingmodel.ThispaperalsoprovestheequivalencebetweenadditivefuzzysystemandGaussianmixturemodelanddeterminestheoptimalparametersoftheclusteringdistributionfunctioncanbeestimatedbyfuzzycmeansclusteringresults.Thenitcanproducenewdatawhichhavetheclusteringcharacteristicoftheoriginaldataandalsocanprotecttheprivacybytheapplicationofrandomsamplingtechnique.Andthengivethedetaileddescriptionofthisalgorithmprocess.Atlast,itteststhevalidityofthenewalgorithmbyexperimentsimulationandgivestheadvantagesandthesuitablesettingtoapplyeachalgorithm.KEYWORDS:DataMining,PrivacyPreserving,ClusteringAnalysis,Sampling河北工业大学硕士学位论文第一章引言§1-1问题提出随着计算机处理能力、存储技术以及互联网络的发展，信息的数字化处理程度极大提高。据估计每隔二十个月，信息量就会增加一倍。人们希望通过对积累的数据进行更高层次的分析，找出数据内部一些潜在的关系和规则，通过将“未知”变为“可知”，将数据变为真正的财富。如银行的信用卡中心期望能够从大量的交易数据中找出优质客户的行为特征和消费模式，以帮助寻找潜在客户、刺激客户消费并创造更多的交叉销售的机会。再如银行的信贷管理部门，如何通过分析信贷历史纪录，来帮助设计贷款产品、指导市场营销和贷款的发放，以降低不良贷款率和降低银行风险是他们面临的一个重大难题。这样的需求数不胜数，涵盖了社会的方方面面。任何事情都有其两面性，数据挖掘领域也不例外，在挖掘数据产生财富的同时，随之产生的就是隐私泄露的问题。在数据挖掘领域，隐私被划分为两类：一类隐私是原始数据本身具有的。由于传统的数据挖掘技术是基于未加密过的原始数据来进行的，也就是说必须将包含个人/企业隐私的原始数据交给数据挖掘者才能挖掘出有用的知识，如个人的家庭电话、银行帐号、财产状况、信用等级等信息，这些信息一旦泄露，极有可能对个人的生活产生不良影响。另一类隐私是原始数据所隐含的知识，如某公司优质客户的行为特征规则，这些知识如果被别有用心的人非法获得，将会严重影响企业的核心竞争力。一方面，这样的数据对商业组织和政府进行决策和提供社会福利等方面是一个重要的资产。另一方面分析这样的数据，如果做得不当，会产生新的危险，隐私和个人的自主权将受到威胁。于是，考虑隐私保护的数据挖掘便成为人们关注的焦点，迅速成为数据挖掘领域研究的热点之一，如何在不暴露客户敏感信息的前提下进行数据挖掘，一直是人们感兴趣的课题。问题的解决对实现安全、公平的新型数据挖掘和数据共享有着重要的理论意义和实用价值。因此，建立隐私保护体系、开发隐私保护方法，使客户的权益与企业利益达到平衡，成为企业发展至关重要的任务。不仅如此，隐私保护在政府文件共享、医疗机构的合作研究、电子商务等领域中也有着广阔的应用前景。2003年以来隐私保护越来越得到人们的重视，并迅速成为数据挖掘领域研究的热点之一。在不揭露个体和公司的隐私信息下，为了满足研究者和决策者对初始数据的需求，尽可能的实现数据的传播，研究者设计并实施了一些隐藏方法。Vaidya&Cliftion（2004）和Clifton,Kantarcioğlu&Vaidya（2005）对隐私保护算法进行了描述总结。并把隐私保护算法主要分为两大类：数据扰动（dataperturbation）和多方安全计算（SecureMultipartyComputation，SMC）。数据扰动是通过对数据的扰动变形使数据变的模糊来隐藏敏感的数据或规则，即将数据库D变形为一个新的数据库以供研究者或企业查询使用，这样诸如个人信息等敏感的信息就不会被泄露。通常，'会和D很相似，从中可以挖掘出和D相同的信息这些方法修改原始数据。即使得敏感性信息不能与初始的对象联系起来或使得敏感性信息不复存在。但数据对分析依然有效。'DD'D该技术适用于集中式数据和分布式数据。其主要的数据隐藏技术有：（1）一般化与删除（generation&suppression）：将数据概括，合并或抽象详细数据为更高层次的数据，不体现出数据的细节，对不能一般化的数据强行删除。这种方法也可称为K匿名法。粗略的说，一个数据库是K匿名的是指：对于一些属性如果对于这些属性的不同值，每个组合至少存在K个事物与之一样。（Samarati&Sweeney1998；Iyengar2002；Domingo-Ferrer&Mateo-Sanz2002；Torra2004）；（2）随机化（randomization）：向数据中加入噪声，或随机的改变数据的值（Evfimievski2002；Dutta，Kargupta&Datta2003；Kargupta&Datta2005）；（3）数据重构（datareconstruction）：将改变后的数据还原出原有的数据分布，而不还原原有的1基于抽样的隐私保护聚类算法研究数据，通常是根据噪声数据的分布函数和改变后的数据值用统计学的方法如贝叶斯后验概率或期望昀大值法等还原出原始数据的分布情况（Agrawal&Aggarwal2001；Parthasarathy&Aggarwal2003）；（4）数据净化（datasanitization）：仅移去事物集中的信息，在统计揭露控制中可称为非扰动算法（Johnsten&Raghava2002；Lee&Chang2004；Oliveira&Zaïane&Saygin2003）。（5）阻碍（blocking）：用“？”来替代存在的值，以保护敏感数据和规则（Saygin,Verykios&Clifton,2001）。（6）抽样（sa