第２ｌ卷第１０期 长春大学学报 Ｖ０１．２１ Ｎｏ．１Ｏ ０ｃｔ．２０１ｌ ２０１１年ｌ０月 ＪＯＵＲＮＡＬ ＯＦ ＣＨＡＮＧＣＨＵＮ ＵＮＩＶＥＲＳＩＴＹ 一种新的Ｋ均值挖掘的隐私保护算法 王思勃，白素平 （长春理工大学光电工程学院，长春１３００１２） 摘要：对隐私保护数据挖掘算法进行了深入研究和分析。总结出目前研究的缺点，提出了一种新的Ｋ均值数据 挖掘的隐私保护算法，通过与已有隐私保护算法的比较，在保证不减少隐私强度的情况下，提高了挖掘的精度。 关键词：Ｋ均值；数据挖掘；隐私保护；ＷＥＫＡ 中图分类号：ＴＰ３０９．７ 文献标志码：Ａ 文章编号：１００９—３９０７（２０１１）１０—００２７－０３ Ｏ 引 言 近年来，人们对隐私问题以及数据挖掘应用越来越关注，于是很多研究人员开始研究隐私保护的数据挖 掘技术，简称ＰＰＤＭ。ＰＰＤＭ技术被广泛应用于医疗、商业、社会学等多种领域。前期的工作主要有两类：数 据修改和数据加密…。数据加密技术没有数据修改技术应用的广泛，因为它的计算和通信代价太高。隐私 保护的数据挖掘有两个目标：隐私和精度 ］。这两个目标往往是一种平衡关系：隐私要求方面，在挖掘者挖 掘数据之前，要对隐私数据进行足够的干扰；精度要求方面，尽管隐私数据被干扰，蕴藏在隐私数据中的数据 模式仍然可以被挖掘者挖掘出来。本文提出了一个新的噪音添加算法来干扰原始数据，实验表明，这个算法 在同等条件下比其它的算法挖掘精度更高。 １ 背景介绍 对于数据加密的隐私保护方法，主要实现分布式数据挖掘隐私保护方法。由于公钥密码机制保证了第 三方对原始数据的不可见性以及数据的无损失性，能够实现与原始挖掘相同精度的挖掘结果。但是与数据 干扰方法相比，其计算和通信代价很昂贵。 数据修改技术主要有：加法噪音，乘法噪音，矩阵乘法，数据交换和Ｋ匿名 ，本文着眼于加法噪音技 术。对于加法噪音技术，２０００年，Ａｇｒａｗａｌ ａｎｄ Ｓｒｉｋａｎｔ公布了他们关于隐私保护数据挖掘的早期工作，他们提 出了一个在客户／服务器场景下，构建决策树的加法干扰技术，通过重构原数据的数据分布得到与原数据相 似的数据，然后再挖掘重构数据，缺点是重构比较麻烦。为了能够直接通过挖掘干扰数据，而不需要修改挖 掘算法，就能得到很好的挖掘效果，刘丽Ｈ 提出了一个门限法，计算每条数据记录的概率值，通过门限将数 据记录进行分类，这样就跳过了重构过程，减少了程序的计算。刘丽方法的缺点是合适的门限的选取比较困 难，没有规律，要依靠经验，不同的数据集也不同。 ２ ＲＤ算法 以前的加法噪音算法都是要对干扰后的数据进行处理，然后再进行挖掘。本文提出的ＲＤ（ｒａｎｄｏｍ ｄｉｓ— ｔａｎｃｅ）算法是在数据干扰之前，对原始数据进行一次 均值的预挖掘，根据挖掘后的结果再进行干扰，而数 据分析者只需要直接对于扰后的数据进行挖掘，就能够得到与挖掘原数据相似的结果．ＲＤ算法中，数据提 供者使用下面公式替代原始数据Ｘ： Ｙ＝Ｘ＋Ｒ （１） 其中，尺是独立同分布的噪音数据。 我们假设Ｄ是原始数据集，ｃ（ｃ ，ｃ …ｃ ）是使用 均值聚类算法挖掘原始数据的聚类结果。我们的 目的就是要把Ｄ修改成Ｄ ，当数据分析者挖掘Ｄ 时，得到一个新的聚类结果ｃ （Ｇ ，ｃ …ｃ ），这个聚类 收稿日期：２０１１－０５．１０ 作者简介：王思勃（１９８８一），男，吉林长春人，硕士研究生，主要从事数据挖掘方面研究。 白素平（１９７０一），女，吉林长春人，副教授，硕士，主要从事数据挖掘、隐私保护，精密仪器总体设计方面的研究。 长春大学学报 第２１卷 结果与ｃ具有较高的相似度，从而保证了挖掘精度。如图１所示。 图１ ＲＤ算法示意图 在ＲＤ算法中，首先遍历数据集中的所有记录，在使用 均值聚类之后，每一条记录都将会被归类，此 时，数据提供者对记录添加噪音数据。为了保证干扰后的数据模式保持不变，ＲＤ算法尽可能得去保证每条 记录在于扰前后类别不变，方法是在添加噪音数据后，调整聚类中心和干扰后记录点之问的距离，使得数据 干扰前后始终在此类别域内，如图１所示，Ｃ 是聚类中心，Ｒ ｉｓ记录点．噪音数据Ｒ ａｎｄＲ 被添加到属性 和ｙ中，然后回得到点Ｐ（Ｘ＋尺 ，ｌ，＋Ｒ ）．此时，有三种情况需要考虑，｜Ｐ分别在Ｄ （ ），Ｄ（ｉ）和 （ ）域内： ，ｄｉｓ（Ｃ ，Ｐ），Ｐ∈Ｄ（ ），１ ｉ ｄｉｓ（Ｃ ，Ｐ ）＝２２Ｄ（ ），ｚ 一ｄｉｓ（Ｃ ，Ｐ），Ｐ∈Ｄ （ ），１ ［２Ｄ（ ），ｒｉｇｈｔ—ｄｉｓ（Ｃ ，Ｐ），Ｐ∈Ｄ （ ），ｌ 后 （２） 在计算ｃ 和Ｐ 之间的距离之后，就能计算出将要发布给数据分析者的数据点Ｐ 的坐标。 ＲＤ算法伪代码 Ｂｅｇｉｎ （１）使用ｋ－ｍｅａｎ算法将数据集划分为ｋ类 （２）ｆｏｒ每一个实例 ｄｏ （３）找到 所属类别ｋ （４）计算ｋ 的半径范围 （５）给 添加高斯噪音 （６）计算ｄ （ｃ ，Ｐ） （７）ｉｆ（ｄｉｓ（Ｃ ，Ｐ）＜Ｄ（ ）． ｔｈｅｎ （８）ｄｉｓ（Ｃ ，Ｐ）＝２Ｄ（ｉ）．１ｅｆｔ—ｄｉｓ（Ｃ ，Ｐ） （９）ｅｌｓｅ ｉｆ（ｄｉｓ（Ｃ ，Ｐ）＞Ｄ（ｉ）．ｒｉｇｈｔ）ｔｈｅｎ （１０）ｄｉｓ（Ｃ ，Ｐ）：２Ｄ（ ）．ｒｉｔｈｔ—ｄｉｓ（Ｃ ，Ｐ） （１１）ｅｌｓｅ （１２）ｄｉｓ（Ｃ ，Ｐ）＝ｄｉｓ（Ｃ ，Ｐ） （１３）ｅｎｄ ｉｆ （１４）ｅｎｄ ｉｆ （１５）根据ｄ （Ｃ ，Ｐ ）和ｃ 的坐标，计算Ｐ 的坐标 （１６）ｅｎｄ ｆｏｒ Ｅｎｄ． ３ 实验结果 本文实验中，数据挖掘工具使用的是ＷＥＫＡ工具，噪音数据的生成使用的是Ｍａｔｌａｂ ７．０实现的，使用的 数据集来源于真实的数据集Ｉｒｉｓ，Ｙｅａｓｔ和Ｇｌａｓｓ，，实例数分别为１５０、１４８４、２１４，从加利福尼亚大学的ＵＣＩ机 器学习库中下载得到。 实验中，通过与Ｋｅｋｅ Ｃｈｅｎ的数据干扰进行比较来衡量算法的性能。对每一个数据集，实验测试条件 第１０期 王思勃，等：一种新的Ｋ均值挖掘的隐私保护算法 为：分类数目选取２和３，加法噪音为均值为０，方差为０．２的高斯分布。我们的结果与Ｋｅｋｅ Ｃｈｅｎ的数据干 扰进行比较，每一项测试选取ｌ０组噪音数据，计算平均精度作为最终精度。图２和３显示了分别挖掘Ｉｒｉｓ 数据集干扰前后的结果。由此可见，干扰后隐私所属类别更明显了，从而保证了很高的挖掘精度。 ４．５ ５ ５．５ ６ ６．５ ７ ７．５ 图２隐私数据分布 图３干扰后数据分布 表１显示了测试的结果，实验表明，在大多数情况下，我们的算法的挖掘精度要高于Ｋｅｋｅ Ｃｈｅｎ的算法。 表１挖掘精度 ４ 结语 本文提出了一个新的噪音添加方法，保护了数据挖掘中的隐私数据。我们的方法根据对原数据的预挖 掘结果来调整干扰后数据，从而不再需要计算代价很高的重构步骤，也不需要修改数据挖掘方法，并且能够 得到较高的挖掘精度，是一个有效可靠的隐私保护的数据挖掘方法。 参考文献： ［１］Ｊｉａｗｅｉ Ｈａｎ，Ｍｉｃｈｅｌｉｎｅ Ｋａｍｂｅｒ．范明，盂小峰等译．数据挖掘：概念与技术［Ｍ］．北京：机械工业出版社，２００１． ［２］王泳．基于隐私保护的数据挖掘［Ｄ］．赣州：江西理工大学，２００８． ［３］ 李锋，马进，李建华．分布式数据挖掘中的匿名隐私保护方法［Ｊ］．浙江大学学报（工学版），２０１０（２）：２７６—２８３ ［４］Ｌｉ Ｌｉｕ，Ｍｕｒａｔ Ｋａｎｔａｒｃｉｏｇｌｕ，ＢｈａｖａｎｉＴｈｕｒａｉｓｉｎｇｈａｍ．Ｐｒｉｖａｃｙ ＰｒｅｓｅｒｖｉｎｇＤｅｃｉｓｉｏｎＴｒｅｅｍｉｎｉｎｇｆｒｏｍ ＰｅｔｒｕｒｂｅｄＤａｔａ［Ｊ］．Ｉｎ ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ４２ｔｈＨａ— ｗａｉｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ．２００９． ［５］Ｋ．Ｃｈｅｎ，Ｇ．Ｓｕｎ，ａｎｄ Ｌ．Ｌｉｕ．Ｔｏｗａｒｄｓ ａｔｔａｃｋ—ｒｅｓｉｌｉｅｎｔ ｇｅｏｍｅｔｒｉｃ ｄａｔａ ｐｅｒｔｕｒｂａｔｉｏｎ［Ｊ］．Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆｔｈｅ ２００７ ＳＩＡＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｍｉｎｉｎｇ（ＳＤＭ’０７），Ｍｉｎｎｅａｐｏｌｉｓ，ＭＮ，Ａｐｒｉｌ ２００７：５８９—５９２． 责任编辑：吴旭云 Ａ Ｎｅｗ Ｋ－ｍｅａｎ Ｍｉｎｉｎｇ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｐｒｉｖａｃｙ Ｐｒｏｔｅｃｔｉｏｎ ＷＡＮＧ Ｓｉ－ｂｏ，ＢＡＩ Ｓｕ—ｐｉｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｏｐｔｉｃａｌ Ｅｌｅｃｔｒｏｎｉｃ Ｅｎ￣ｎｅｅｆｉｎｇ，Ｃｈａｎｇｃｈｕｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｃｈｕｎ １３００２２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｄｅｓｃｒｉｂｅｓ ｔｈｅ ｔｅｃｈｎｏｌｏｇｉｅｓ ａｂｏｕｔ ｄａｔａ ｍｉｎｉｎｇ ｆｏｒ ｐｒｉｖａｃｙ ｐｒｏｔｅｃｔｉｏｎ ａｎｄ ｐｒｏｐｏｓｅｓ ａ Ｈｅｗ Ｋ・－ｍｅａｎ ｄａｔａ ｍｉｎｉｎｇ ａｌｇｏ・・ ｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｓｕｍｍａｒｉｚｉｎｇ ｔｈｅ ｄｉｓａｄｖａｎｔａｇｅｓ．Ｃｏｍｐａｒｉｎｇ ｔｏ ｔｈｅ ｅｘｉｓｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ，ｉｔ ｉｎｃｒｅａｓｅｓ ｍｉｎｉｎｇ ａｃｃｕｒａｃｙ ｉｎ ｔｈｅ ｃｏｎｄｉｔｉｏｎ ｏｆ ｅｌｌ－ ｓｕｒｉｎｇ ｐｒｉｖａｃｙ ｐｒｏｔｅｃｔｉｏｎ ｓｔｒｅｎｇｔｈ． Ｋｅｙｗｏｒｄｓ：Ｋ—ｍｅａｎ；ｄａｔａ ｍｉｎｉｎｇ；ｐｒｉｖａｃｙ・ｐｒｅｓｅｒｖｉｎｇ；ＷＥＫＡ