·应用研究·
基于数据扰动的隐私保持的分类挖掘方法
陶卫平
（钦州学院物理与材料科学学院
广西钦州
535000)
数字技术与应用
要，在局前已有的基于数据扰动的随私保持的分类挖据方法中，分美算法必预经过改遗方可应用于抗动后数据，而且扰动方法不同，
使用的分要算法不同，对分类算法进行改造的方法电就不，这使样该类方法难以在实际中推广应用。本文针对这一间题，提出了一种新的基于数据扰动的障私保持的分奏范摄方法，通过生成并公开一级与原始数据独立同分事的新数据的方法来实现数据扰动。由于新数据与原始数据独，图此从新数据得不到关于原始数据的详细信息，由于新数据与原始数据同分市，图此鲁通的分要花摄算法可以直接应用于新数括，从面解决了现有方法使用不方使的间题。
关键词：数据抢据中图分类号：S126
障私保护
数据抗动
文献标识码：A
1引言
数据挖据旨在从海景数据中发现人们难以察党却又感兴递的知识，一般的数据挖播技术都假定数据是可以直接得到的，这在实际中并不一定成立。实际中出于隐私保护的需要，有可能需要在得不到精确数抵的前提下进行挖据，即需要进行隐私保持的数据挖据"，
隐私保持的数据挖揽目前已经成为数据挖掘研究的热点之一。它的首要任务是开发在得不到精确数据的前提下进行挖据的方法。分类是数据挖的重要研充内容之一，目前已有的隐私保持的分类挖据方法主要有两类。一类是基于安全多方计算的方法，另一类是基于数据扰动的方法，本文针对基于数据扰动的方法进行研究。
2算法过程
本文方法的基本思想是：生成一组与原始数据独立同分布的数据作为扰动后数。由于扰动后数据与原始数据独立，因此从扰动后数据得不到关于原始数据详细内容的信息，仅能得到原始数据的统计特性，这样就保护了隐私数据。另一方面，由于扰动后数据与原始数据同分布，因此数据挖遥算法可以直接应用于扰动后数据，不需要对算法进行改造。
本文方法用于集中式数据库时，用扰动后数微来代替原始数据，将其提供给数据挖据人员便可以了。本文方法也适用于水平型分布式数据序，这时，数据分布式存储在多个节点上，每个节点仅存储有一部份样本，但每个样本都是完整的。每个数节点独立的生成新数据并公开，数帮挖漏人员只需将各节点数据配总便可进行挖。
生成与原始数据独立同分布数据的围难之处在于，原始数据往往是高维的，而且各维之间并不独立。在本文方法中，首先不考虑各维间的联系，分别对各维进行统计并生成新数据，随后利用数值的大小顺序关系重构各维之间的联系，通过这一方法解决了高维数据雍以生成独立同分布数据的间题。
3算法分析
3.1隐私性和有效性
隐私性要求对隐私数据提供足够的保万方数据
文章编号：1007-9416（2010）09-0053-01
护，要求无法从扰动后数据得到原始数据。在本文方法中，扰动后数据是独文于原始数猪的，因此它仅仅保留了原始数据的统计信息，在某个具体样本的取值上与原始数据没有任何联系、因此无法从某个扰动后样本得到其对应的原始样本的值。本文方法对隐私数据提供了很好的保护，满足隐私性要求。
有效性是指算法运行要有小的时间复杂度和通信开销。本文方法中，设一共有n个m维样本，生成一个随机数需要的时间复杂度为O(G)，则完成--维的分布函数的统计并生成新数据所需时间复杂度为O(nG)，完成全部m维需要O(mnG) 的时间复杂度，完成各维数据之间关系的重构需要分别对原始数据以及新数据进行排序，并重新排列新数据，达需要 0(mnlog(n))的时间复杂度，因此总的时间复杂度为O(mn(log(n)+G)。
本文方法中，挖掘过程在本地完成，仅在得到样本数据时需要通信。设一共有n 个m维样本，在最坏情况下，数据全部没有存储在本地，全部需要下载，这时的通信开
销为O(mn)。 3.2准确性
准确性要求最终可以得到准确的挖指结果，要求使用隐私保持的挖掘方法所得结果与不考惠隐私保持，直接在原始数据上使用替通的挖据方法所得结果相近。
采用实验方法来证明本文方法的准确性，使用参考文献中的数据进行实验，该数据包含9个属性，共有5个不同的分类函数(F1~F5)。5个分类函数都将样本分成两类。训练样本一共1000000个，测试样本一共 5000个。
实验：假设数据存储在水平型分布式数据库中，考察样本在各节点上分布不均衡，即各节点拥有的样本数不同时，本文方法生成的决策树的分类精度。当样本分布不均衡时，使用扰动后数诺生成决策树的精度。在该实验中，各节点上的样本数目满足给定方差的正态分布。从图中可以看出，当方差增大时，即样本分布越来越不均衡时，本文方法所得决策树的精度没有明显的变化趋势，即本文方法不受样本分布不均衡程度的影响。
综上，实验证明，本文方法并不局限于某种特定的分类算法，各种常用的分类算
法都可以真接应用于本文方法扰动后的数据并得到高精度结果，当本文方法应用于水平型分布式数据库时，所得结果精度随着告点个数的增加面下降，但该方法对于节点个数的增加并不敏感，在节点个数很多的情况下依然会有相当好的效果，当本文方法应用于水平型分布式数据库时，所得结果精度不受样本分布不均衡程度的影响，
4结语
在现有的基于数据扰动的隐私保持的分类挖方法中，分类算法必须经过改造方可应用于扰动后数据，而且不同的分类算法，不同的扰动方法都有不同的改造方法，这使得日前此类方法使用很不方便，难以在实际中推广应用。本文针对这一间题，提出了一种新的基于数据扰动的隐私保持的分类花据方法。在该方法中，普通的分类算法可以不加修改直接应用于扰动后数据，从而解决了现有方法使用不方便，不便于推广应用的间题。
本文方法通过生成并公开一组与原始数据独立同分布的新数据的手段来达到对原始数据进行扰动的目的。由于新数据是独立于原始数据生成的，因此它仪仪保窗了原始数据的统计信息，在某个具体样本的取值上与原始数据没有任何联系，从某个新数据上得不到其对应的原始数措的取值，从而很好的保护了隐私数据。另一方面，新数据与原始数据同分布，保持了原始数据的统计特性，因此，替通的分类算法可以不加修改使直接应用于新数据。实验表明，使用本文方法生成的分类器，与不考虑隐私保持，直接在原始数据上生成的分类
器具有相近的精度。参考文献
[1]Elisa Bertino, Igor Nai Fovino, Loredana
Parasiliti Provenza.A Framework for Evaluating Privacy Preserving Data Mining Algorithms. Data Mining and Knowledge Discovery,2005,11(2):121 154.
[2]陈红亚.基于文本挖拥的主动信息服务
[J].情报杂志，2004(10。
[3]鹿小明，文本挖据及其在信息检索中的
作用[J].情报资料工作，2004(6),
数技术与应用
59