（计算机软件与理论专业论文）隐私保护聚类挖掘方法的研究.pdf

c l a s s i f i e di n d e x u d c ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g r e s e a r c ho np r i v a c yp r e s e r v i n g c l u s t e r i n gm i n i n gm e t h o d c a n d i d a t e x u y i f e n g s u p e r v i s o r p r o f l i uj i e a c a d e m i cd e g r e e a p p l i e df o r m a s t e ro fe n g i n e e r i n g s p e c i a l i t y c o m p u t e rs o f t w a r ea n dt h e o r y d a t eo fs u b m i s s i o n m a r c h 2 0l0 d a t eo f0 r a le x a m i n a t i o n m a r c h 2 01o u n i v e r s i t y h a r b i ne n g i n e e r i n gu n i v e r s i t y 咿 奴 t 哈尔滨工程大学 学位论文原创性声明 本人郑重声明 本论文的所有工作 是在导师的指导下 由 作者本人独立完成的 有关观点 方法 数据和文献的引用己在 文中指出 并与参考文献相对应 除文中已注明引用的内容外 本论文不包含任何其他个人或集体己经公开发表的作品成果 对 本文的研究做出重要贡献的个人和集体 均己在文中以明确方式 标明 本人完全意识到本声明的法律结果由本人承担 作者 签字 镰 1 沁 日期 勘10 年3 月7 6 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定 即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学 哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索 可采用影印 缩印或扫描等复制手段保存和汇编本 学位论文 可以公布论文的全部内容 同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学 涉密学位论文待解密后适用本声明 本论文 日在授予学位后即可口在授予学位1 2 个月后 口 解密后 由哈尔滨工程大学送交有关部门进行保存 汇编等 作者 签字 镣一风 日期 2 1 1 0 年3 月l6 日 z o 导l o 军蹴苫钏乐年3 月形日 h 之 哈尔滨工程大学硕士学位论文 摘要 随着数据挖掘技术的发展和数据挖掘工具的大量出现 人们对自己隐私 的保密性要求也变得越来越迫切 如何在保证个人隐私的前提下进行数据挖 掘 已经成为一个迫切需要解决的问题 目前 人们对隐私保护聚类问题研 究较少 使用的方法也较单一 而聚类挖掘是分析管理问题的重要方法之一 常应用于市场细分 客户分类 模式识别 w e b 文档分类与制造系统单元化 设计等重要领域 通过对目前已有的隐私保护聚类挖掘方法进行深入地研究分析后发现 几何数据转换方法应用最为简单且不影响挖掘结果的准确性 但是隐私保护 度较低 为了解决已有的几何数据转换方法隐私保护度低的不足 本文分别 提出了基于平面反射的几何数据转换方法和随机响应几何变换算法 基于平面反射的几何数据转换方法 即任意选择平面上的一条直线 且 将所有属性两两配对以构成平面上的点 对每个点作关于直线的对称点 所 得数据即转换后的数据 通过实验证明 这种方法简单易行且比平移 缩放 旋转等几何数据转换方法具有更高的隐私保护度 为了进一步提高隐私保护度 本文又提出了随机响应几何变换算法 该 算法将随机响应技术与几何变换方法相结合 根据随机数生成器生成的随机 数的不同 选择不同的几何变换方法 起到了双重隐私保护的效果 实验证 明这种算法确实具有较高的隐私保护度 并且是高效可行的 关键词 数据挖掘 聚类 隐私保护 几何数据转换 随机响应 瓴 t op e o p l e sp r i v a c y i nt h i se a s e h o wt om i n ed a t au n d e rt h ep r e m i s eo fp r e s e r v e p e r s o n a lp r i v a c y h a sb e c o m ea nu r g e n tp r o b l e mt oa d d r e s s a tp r e s e n t t h e p r o b l e m so fp r i v a c yp r e s e r v i n gc l u s t e r i n ga r el e s ss t u d i e d a n dt h eu s e dm e t h o d s a r ev e r ys i n g l e c l u s t e r i n gm i n i n gi sa l li m p o r t a n tm e t h o do fa n a l y z i n ga n d m a n a g i n gq u e s t i o n s i t i so f t e nu s e di nm a r k e ts e g m e n t a t i o n c u s t o m e r c l a s s i f i c a t i o n p a t t e mr e c o g n i t i o n w e bd o c u m e n tc l a s s i f i c a t i o n t h ec e l ld e s i g no f m a n u f a c t u r i n gs y s t e m sa n do t h e ri m p o r t a n ta r e a s t h r o u g ht h ei n d e p t hr e s e a r c ha n da n a l y s i so ft h ee x i s t i n gp r i v a c yp r o t e c t i o n c l u s t e rm i n i n gm e t h o d s w ef i n dt h a tg e o m e t r i cd a t at r a n s f o r m a t i o nm e t h o d sa r e m o s ts i m p l et oa p p l yw i t h o u ta f f e c t i n gt h ea c c u r a c yo fm i n i n gr e s u l t s b u th a v ea l o w e rd e g r e eo fp r i v a c yp r e s e r v i n g i no r d e rt os o l v et h el o wp r i v a c yo ft h e e x i s t i n gm e t h o d so fg e o m e t r i cd a t at r a n s f o r m a t i o n t h i sp a p e rp r e s e n t st h em e t h o d o fp l a n er e f l e c t i o nb a s e dg e o m e t r i cd a t at r a n s f o r m a t i o na n dt h er a n d o mr e s p o n s e m e t h o do fg e o m e t r i ct r a n s f o r m a t i o ns e p a r a t e l y t h em e t h o do fp l a n er e f l e c t i o nb a s e dg e o m e t r i cd a t at r a n s f o r m a t i o ni sa s f o l l o w s f i r s tw ec h o o s eas t r a i g h tl i n ei nt h ep l a n e t h e nm a t c ht h ea t t r i b u t e si n t o p a i r st of o r mp o i n t so nt h ep l a n e a n dc o m p u t et h es y m m e t r yp o i n to f e a c hp o i n t t h er e s u l ti st h et r a n s f o r m e dd a t a t h et e s tp r o v e dt h a tt h i sm e t h o di ss i m p l ea n d h a sah i g h e rd e g r e eo fp r i v a c yp r o t e c t i o nt h a nt r a n s l a t i o n s c a l i n g r o t a t i o na n d o t h e rg e o m e t r i cd a t at r a n s f o r m a t i o nm e t h o d s t of u r t h e re n h a n c et h ed e g r e eo fp r i v a c yp r e s e r v i n g t h i sp a p e rr a i s e st h e r a n d o mr e s p o n s e sm e t h o do fg e o m e t r i ct r a n s f o r m a t i o n t h er a n d o mr e s p o n s e m e t h o do fg e o m e t r i ct r a n s f o r m a t i o nc o m b i n e st h er a n d o mr e s p o n s et e c h n o l o g y 哈尔滨工程大学硕士学位论文 i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i l w i t ht h eg e o m e t r i ct r a n s f o r ma l g o r i t h m a c c o r d i n gt ot h ed i f f e r e n tr a n d o m n u m b e r g e n e r a t e db y r a n d o mn u m b e r g e n e r a t o r d i f f e r e n tg e o m e t r i c t r a n s f o r m a t i o nm e t h o di ss e l e c t e d w h i c hh a sp l a y e dad u a le f f e c to fp r i v a c y p r o t e c t i o n o u re x p e r i m e n tp r o v e st h a tt h i sm e t h o dh a sah i g h e rd e g r e eo fp r i v a c y p r e s e r v i n g a n di ti sf e a s i b l ea n de 箍c i e n t k e y w o r d s d a t am i n i n g c l u s t e r i n g p r i v a c yp r e s e r v i n g g e o m e t r i c d a t a t r a n s f o r m a t i o n r a n d o mr e s p o n s e b 纽 第2 章数据挖掘相关知识 6 2 1 数据挖掘 6 2 1 1 数据挖掘概述 6 2 1 2 数据挖掘常用方法 一7 2 1 3 数据挖掘研究前景 一9 2 2 聚类挖掘 1o 2 2 1 聚类挖掘基本概念 1 0 2 2 2 聚类处理的数据结构 1 0 2 2 3 聚类处理的数据类型 1 1 2 2 4 聚类挖掘算法的分类 15 2 2 5 经典聚类算法 k m e a n s 算法 1 6 2 3 隐私保护 18 2 3 1 隐私保护数据挖掘基本概念 1 8 2 3 2 隐私保护算法的分类 1 9 2 4 本章小结 21 第3 章基于平面反射的几何数据转换方法 2 2 3 1 算法的提出 2 2 3 2 基于平面反射的几何数据转换方法 2 3 3 2 1 相关概念 2 3 3 2 2 算法描述 2 5 3 2 3 算法评价 2 7 b 4 3 2 实验结果 4 1 4 3 3 结果分析 4 2 4 4 本章小结 4 4 结论 4 5 参考文献 4 6 攻读硕士学位期间发表的论文和取得的科研成果 5 1 致谢 5 2 h 矗 的特征 找出有效的 新颖的 有潜在用处的 易于理解的关系和模型 怎 样才能利用一定的方法从数据中挖掘出复杂的模型 发现出能够为人所理解 的知识 能够被再利用的先验知识 能够较少或完全不依赖于外部专家的主 观知识 怎样才能做到当目标数据中存在数据丢失 失真等情况时 自然恢 复正确的值 怎样才能结合领域知识来高效地发现知识 要解决上述问题就 需要数据挖掘 人们从数据挖掘中得到的回报就是将这些新发现的知识转变 为经营上的成果 比如如何增加顾客的购买欲望 怎样减少信用卡欺诈的数 量等 聚类分析作为一种重要的数据挖掘方法已有多年的研究历史 目前在许 多领域都得到了广泛的应用 其中包括 模式识别 数据分析 图像处理和 市场分析等 通过聚类 人可以辨认出空旷和拥挤的区域 进而发现整个的 分布模式 以及数据属性之间所存在有价值的相关关系 然而在聚类分析的 过程中 不可避免地涉及到隐私泄露的问题 聚类是一个将数据集划分为若 干组或类的过程 并使得同一个组内的数据对象具有较高的相似度 而不同 组中的数据对象则是不相似的 相似度的计算通常是根据对象间的相对距离 或对象的相对密度来确定的 由此可见 聚类分析的过程中完全可以不涉及 原始的隐私数据 只要不改变对象间的相对距离和相对密度 可以对原始数 据做相应的转换 然后对转换后的数据进行分析 从而达到既保护隐私数据 又能得到正确的聚类结果的目的 l 本文在前人研究的基础上 提出了两种新的隐私保护聚类挖掘方法 旨 在保证挖掘结果准确性的同时提高隐私保护度 h k 哈尔滨工程大学硕士学位论文 1 2 隐私保护数据挖掘的研究现状 数据挖掘在1 9 8 9 年8 月美国底特律市召开的第十一届国际联合人工智能 学术会议上正式形成 从1 9 9 5 年开始 每年举行一次知识发现 k n o w l e d g e d i s c o v e r yi nd a t a b a s e k d d 国际学术会议 把对数据挖掘和知识发现的研 究推入高潮 目前 几种典型的数据挖掘方法是关联规则 聚类 分类 预测 w e b 挖掘等 2 1 文献 3 中提出了一种基于关联规则的隐私保护算法m a s k m i n i n g a s s o c i a t i o n sw i t hs e c r e c yk o n s t r a i n t s 算法 一个顾客元组可以被看成一个随 机向量x x x 0 或1 扰动后的向量 d i s t o r t x 其中z x x o r r 是 的补 且随机变量r 的密度函数为 厂 厂 b e r n o u l l i p 0 p 1 也就是说r 以概率p 取1 以概率1 p 取o 该方法通过数据 干扰和分布重构实现了隐私保护的关联规则挖掘 文中还在随机化参数的设 置和支持度的计数方法等方面给出了优化方案 文献 3 15 f t l 文献 4 提出了基于主成分分析的隐私保护聚类挖掘方法 主成 分分析方法是把原来的高维且具有一定相关性的变量 通过投影的方法重新 组合成一组新的相互无关的低维变量的多元统计分析方法 该方法首先通过 一系列正交旋转变换 将总方差分解为数个不相关的新变量的方差之和 使 变量按方差大小排列 且第一个变量的方差最大 然后选取前面少数几个具 有较大方差的变量代替原来的多个变量 其中心思想是缩减一个包括很多相 互联系着的变量的数据集 并且保留尽可能多的有用变量 这种方法只适用 于高维数据的聚类 数据转换过程中需要根据一种事先定义好的兴趣标准使 映射达到最优化 但是对于给定的数据集 很难选择正确的兴趣标准 文献 6 提出了 种基于随机映射的聚类挖掘数据转换方法 随机映射是 一种线性变换 从以维到k 维的随机映射是通过乘以玎 k 维的随机矩阵尺来 实现的 通常k 远小于珂 这种方法能够有效实现数据的降维 简化原有的 数据结构 从而既能实现对隐私数据的保护又能降低聚类挖掘的时间和空间 复杂度 随机映射方法也适用于高维数据的聚类 其数据转换过程比主成分 分析方法简单 但是聚类结果具有高度不确定性 不同的随机映射方法可能 2 t k 乱 哈尔滨工程大学硕士学位论文 导致完全不一样的聚类结果 文献 7 和文献 8 提出了一种基于几何集的聚类挖掘数据转换方法 这种 方法基于图像的成像原理 通过平移 t r a n s l a t i o nd a t ap e r t u r b a t i o nm e t h o d 比例缩放 s c a l i n gd a t ap e r t u r b a t i o nm e t h o d 矛1 2 旋转 r o t a t i o nd a t ap e r t u r b a t i o n m e t h o d 等方式对初始敏感性数据实施扰动 但保持聚类的特征不变 即保 持对象间距离和密度不变 这种方法既适用于低维数据又适用于高维数据 而且聚类挖掘结果的准确性高 算法复杂度低 可扩展性强 该方法的缺点 是隐私保护度太低 为了提高隐私保护度 文献 7 中引入了随机扰动的方法 随机参数p 决定对数据的扰动程度 但是很明显这会降低挖掘结果的准确性 p 越大隐私保护度越高 挖掘结果的准确性越低 相反p 越小隐私保护度越 低 而挖掘结果的准确性越高 这种情况下隐私保护度和挖掘结果的准确性 成为一对不可调和的矛盾 文献 9 提出了一种基于二次反射的隐私保护聚类挖掘数据转换方法 t h ed o u b l e r e f l e c t i n gd a t ap e r t u r b a t i o nm e t h o d d r d p 这种方法取每个 属性的最大值和最小值的均值作为这个属性的对称轴 将所有的属性值作映 射 文中提到的属性配对仅仅是为了作图的需要 并没有体现到数据转换过 程中 经过d r d p 转换后的数据虽然与原始数据有较大差异 但是属性的最 大值和最小值依然存在 只是交换了彼此的位置 因此很容易还原出原始数 据 文献 1 0 提出了一种运用决策树分析解决推导问题的隐私保护分类挖掘 方法 它将谨慎降级思想与决策树分析相结合 谨慎降级是一个模型 其目 的是在要进行降级的数据集中形式化信息的处理形式 信息处理方向为从安 全环境到数据公开的环境 换句话说 降级就是对要公开发布的信息进行隐 私保护处理的过程 在这种降级方法中 用秒来代替要阻塞的数据 而其它 的阻塞方法往往采用 等代替要阻塞的数据 目的取值在o 和1 之间 它代 表被阻塞的属性取某个值的概率 数据管理者对分类标签进行阻塞 这使得 数据的接收者不能在没有降级的数据集上进行信息建模 决策树用来对可能 存在的信息推导渠道进行分析 以决定对哪些数据进行降级 文献 1 1 在w e b 页面的链接结构之上提出了相应的网页主题内容提取算 法 h i t s 算法 h i t s 是一种有效的基于链接分析的主题提取方法 它所依 1 哈尔滨1 程大学硕士学位论文 赖的是对超链接环境下链接结构的分析 在h i t s 算法模型中 认为互联网上 的一个主题含有很多权威页面 这些权威页面都应该被其他超链接所指向 也就是说这个主题所对应的权威页面能够被大多数的网站开发人员认同其价 值 文献 1 2 提出了基于分布式环境的四种安全多方计算的隐私保护方法 安全多方计算协议应用在不同的数据分布形式下 又形成了不同的隐私保护 算法 安全多方计算是通过密码学的技术构建安全多方计算协议 s m c 进 行计算 参与者拥有自身的数据 各方通过合作进行挖掘 但是在这个过程 中不允许任何一方获得别人的数据 隐私保护算法众多 怎么衡量它们的优劣呢 文献 1 3 和文献 1 4 1 中提出 隐私保护算法的评价标准主要有以下几点 1 算法的效率 即在应用算法进行隐私保护时所需时间的长短 2 算法的可扩展性 指增大处理的数据量后该算法解决问题的能力 3 隐私保护度 防止原始数据或其隐含的知识被推导出的程度 4 算法的精度 与非隐私保护的同类算法相比 其判断精度 丢失比 率和误生成比率 5 通用程度 适应各种数据挖掘技术的程度 1 3 论文的研究内容与组织结构 1 3 1 论文的研究内容 本文致力于隐私保护聚类挖掘方法的研究 提出了两种隐私保护方法 基于平面反射的几何数据转换方法和随机响应几何变换方法 基于平面反射的几何数据转换方法 任意选择平面上的一条直线 将所 有属性两两配对以构成平面上的点 对每个点作关于直线的对称点 所得数 据即转换后的数据 随机响应几何变换方法 一种将随机响应技术与几何变换方法相结合的 方法 首先给定四个参数 对应选取四种不同的几何变换的概率 根据随机 数生成器生成的随机数的不同 选择不同的几何变换方法 4 了基于平面反射的几何数据转换方法的隐私保护度和挖掘结果准确性 第4 章随机响应几何变换方法 针对几何数据转换方法隐私保护度低的 不足 本章将随机响应技术与几何数据转换方法相结合 提出了一种随机响 应几何变换方法 并举例介绍了该算法 然后分析了算法的效率和可扩展性 最后 本章通过实验结果分析了随机响应几何变换方法的隐私保护度和挖掘 结果准确性 用数据中 提取隐含在其中的 人们事先不知道的 但又是潜在有用的信息 和知识的过程 提取的信息和知识一般可表示为概念 c o n c e p t 规则 r u l e 规律 r e g u l a r i t y 模式 p a t t e r n 等形式i i l 数据挖掘技术是一门综合性的技术 涉及到诸如机器学习 模式识别 人工智能 统计学 智能数据库 专家系统等多个领域 数据挖掘的成果可 以应用于信息管理 决策支持等许多方面 数据挖掘的基本流程如图2 1 所示 在数据预处理中的数据规范化主要是去掉不相干数据 进行二义性分析 和消除不一致性 数据集成主要是将不同的数据源集成到单个系统中 数据 转化就是将数据转化为统一的形式能方便地进行数据挖掘 模式评价是识别数据挖掘中有价值的模式 知识的表示是将有价值的模式或知识以用户可以接受或理解的方式表达 出来 实际的分析过程既可以包括上述全部步骤 也可以只完成一部分步骤 但在得到满意的结果之前则有可能需要将这些步骤反复进行多次 6 哈尔滨工程大学硕士学位论文 用户界面 善 读入数据i i 挖掘的主题与任务 一r i 盔 1r 数据源卜 叫数据规范化r l 数据集成卜 叫数据转化 数据预处理梗块 j r 挖掘综合器 上 关联势析聚娄分析分娄分析进化分析非结构数据分析 数据挖掘篁法库 i 梗式评价卜 知识的表示 上 事先无法预测的有价值的知识 图2 1 数据挖掘的基本流程 2 1 2 数据挖掘常用方法 数据挖掘的常用方法包括关联规则挖掘 分类规则挖掘 聚类挖掘 预 测分析与趋势分析 统计分析等 下面简要介绍各种方法 1 关联规则挖掘 关联规则挖掘就是从给定的数据集中发现数据项之 间的有趣的关联或相关关系 关联规则揭示了数据项间的未知的依赖关系 根据所挖掘出的关联关系 可以从一个数据对象的信息来推断另一个数据对 象的信息 关联规则挖掘广泛用于市场营销 事务分析等应用领域 哈尔滨工程大学硕士学位论文 例如 一家超市利用数据挖掘方法对原始交易数据进行挖掘和分析 一 个意外的发现是 跟尿布一起购买最多的商品竟是啤酒 经过大量实际调查 和分析 揭示了一个隐藏在 尿布与啤酒 背后的一种行为模式 一些年轻 的父亲下班后经常要到超市去买婴儿尿布 而他们中有3 0 4 0 的人同时 也会为自己买一些啤酒 于是这家超市将尿布和啤酒摆在一起出售 这个举 措使尿布和啤酒的销量双双增加了 按常规思维 尿布与啤酒风马牛不相及 若不是借助数据挖掘技术对大量交易数据进行挖掘分析 沃尔玛是不可能发 现数据内在的这一有价值的规律的 2 分类规则挖掘 所谓分类 就是为了理解事物特征并做出预测而使 用历史数据建立一个分类模型 即分类器 的过程 首先从数据中选出已经 分好类的训练集 然后在该训练集上运用数据挖掘分类的技术 建立分类模 型 最后对没有分类的数据进行分类 例如 通过训练集获得了下列规则 i f 年龄 3 1 4 0 a n d 收入 较高 t h e n 信用程度 优 秀 这个规则的含义就是 年龄在3 1 到4 0 之间 收入较高的情况下 这类 顾客群体的信用程度被认为是 优秀 3 聚类挖掘 将数据集划分为若干组或类 使得同一个组内的数据对 象具有较高的相似度 而不同组中的数据对象差别较大 聚类与分类不同 聚类是在没有给定划分类的情况下 如没有预定的分 类表 没有预定的类目 根据信息相似度进行信息聚集的一种方法 所以 聚类分析的输入数据集是一组未标记的对象 在机器学习中 聚类是无指导 学习的一个例子 分类是有指导学习的一个例子 两者所采用的方法相差甚 远 并且聚类的时间复杂度要比分类大得多 4 预测分析与趋势分析 数据挖掘活动就是揭示事物发展的趋势 预 测分析与趋势分析可以在完成了其他数据挖掘过程之后进行 例如 在考虑如何保持客户时 可以在八月份和九月份分别建立一个模 型 然后通过这两个模型的对比就有可能发现从八月份到九月份有哪些变化 最为显著 这一方法将有助于分析变化是季节性的变化还是由于业务环境改 变而引起的意外变化 r 哈尔滨工程大学硕七学位论文 5 统计分析 统计分析长期以来一直用于数据建模 线性回归是一个 利用概率 数据分析及统计知识推理的过程 统计方法的优点是精确 易理 解且已广泛使用 缺点是很难有效使用 数据挖掘是从数据中抽取有价值信 息的过程 而统计学是一个完整的研究领域 包括从数据中抽取有价值的信 息 2 1 3 数据挖掘研究前景 当前 数据挖掘技术的研究正方兴未艾 预计未来的研究焦点可能会集 中到以下几个方面 1 形式化描述语言 即研究专门用于知识发现的数据挖掘语言 它 也许会像s q l 语言一样走向形式化和标准化 2 可视化的数据挖掘过程 寻求数据挖掘过程中的可视化方法 使知 识发现的过程易于被用户理解和操纵 可使数据挖掘过程成为用户业务流程 的一部分 也便于在知识发现的过程中进行人机交互 包括数据可视化呈现 与交互操纵两部分 3 研究在网络环境下的数据挖掘的应用 特别是在i n t e m e t 上建立数 据挖掘服务器 与数据库服务器配合 实现数据挖掘 从而建立强大的数据 挖掘引擎与数掘挖掘服务市场 4 融合各种异构数据的挖掘技术 加强对各种非结构化数据的挖掘 d a t am i n i n gf o r a u d i o v i d e o 如对文本数据 图形数据 视频图像数据 声音数据乃至综合多媒体数据的挖掘 5 处理的数据将会涉及到更多的数据类型 这些数据类型或者比较复 杂 或者是结构比较独特 为了处理这些复杂的数据 就需要一些新的和更 好的分析和建立模型的方法 同时还会涉及到为处理这些复杂或独特数据所 做的费时和为复杂数据准备的一些工具和软件 6 私有数据的保护与数据安全性 数据挖掘中 有可能面对的是敏感 数据或者私有数据 什么情况下数据挖掘将会导致对私有数据造成侵犯和采 用什么手段来防止敏感信息的泄漏的研究也非常重要 7 交互式发现 9 聚类是一个将数据集划分为若干组或类的过程 使得同一个组内的数据 对象具有较高的相似度 而不同组中的数据对象差别较大 聚类分析的基本 指导思想就是最大程度地实现类中对象相似度最大 类间对象相似度最小 相似或不相似的度量是基于数据对象描述属性的取值来确定的 通常就是利 用 各对象间 距离来进行描述的 坫 聚类的用途是很广泛的 它是一种重要的人类行为 聚类分析已经广泛 地用于许多应用中 包括模式识别 数据分析 图像处理 空间数据库技术 生物学以及市场研究 在商业上 聚类可以帮助市场分析人员从他们的消费者数据库中区分出 不同的消费群体来 并且概括出每一类消费者的消费模式或习惯 例如 租 用v c d 的类型不相似的客户群体 可能暗示成员属于不同的亚文化群 零 售商想知道在他们的客户群中是否存在着某种相似性 以便以此为依据划分 消费群体 并掌握各自特点 更好地销售商品和拓展市场 聚类还可以用来 从地理数据库中识别出具有相似土地用途的区域 可以从一个城市的房地产 信息数据库中 根据房型 房价及地理位置分成不同的类 还可以用来从万 维网上分类不同类型的文档等 2 2 2 聚类处理的数据结构 聚类算法通常采用两种具有代表性的数据结构 一个是数据矩阵 一个 是相异程度矩阵 数据矩阵是一个对象 属性结构 它是由n 个对象组成 这些对象是利用 p 个属性来进行描述的 如 年龄 高度 重量等 数据矩阵采用nxp 矩 阵来表示 如图2 2 所示 1 0 一般采用 刀矩阵来表示 如图2 3 所示 0 d 1 2 d 1 3 d 1 胛 d 2 1 0d 2 3 d 2 玎 d 3 1 a 3 2 0 d 3 g d n 1 a n 2 d n 3 0 图2 3 差异矩阵 其中 d i 表示对象f 和对象j 2 f b q 的差异 或不相似程度 通常为 非负数 当对象洱口对象 非常相似或彼此 接近 时 该数值接近o 该数 值越大 就表示对象f 和对象 差异越大 2 2 3 聚类处理的数据类型 文献 1 6 付旨出 聚类分析中处理的数据包括区间标度变量 二元变量 标称型变量 序数型变量 比例型变量和混合类型变量等类型 对不同类型 的数据 其相异程度的估算方法是不一样的 1 区间标度变量 区间标度变量是一个粗略线性标度的连续度量 如重量 长度 温度等 选用的度量单位对聚类分析的效果影响很大 一般而言 度量单位越小 变 量的取值范围就越大 对聚类效果的影响也就越大 为了减小度量单位的选 择对聚类效果的影响 需要对数据进行标准化 使原来的度量值变成无度量 明考斯基距离公式为 d i 卜门 x j l r i x j 一x 1 9 i x 护一x 印1 9 其中i x l x i 2 和j x j lx 2 x 咖 是两个p 维的数据对象 q 是一个正整数 当g 1 时 d i 成为曼哈坦距离 当q 2 时 d f 就成 为欧几里德距离 在实际使用距离公式度量相异程度时可以根据每个变量的重要性赋予一 个权重 例如 加权的明考斯基距离公式为 d i w 胁 卜w 2k x j 2 卜 w p b b 1 9 2 二元变量 一个二元变量仅取0 或1 值 其中0 代表 变量所表示的 状态不存在 而1 则代表相应的状态存在 表2 1 给出了二元变量的可能性表 其中每个对象有p 个变量 且p a b c d a 表示对象f 和对象 的值都为1 的变量的数目 d 表示对象f 和 对象 的值都为0 的变量的数目 b 表示对象f 为1 对象 为0 的变量的数 目 c 表示对象f 为o 对象 为l 的变量的数目 对于对称的二元变量 采用简单匹配系数来评价两个对象之间的相异程 1 2 3 标称型变量 标称型变量是二元变量的推广 标称型变量可以对两个以上的状态进行 描述 例如 地图颜色 变量就是一个符号变量 它可以表示五种状态 即 红 绿 蓝 紫和黄色 有两种计算标称变量相异程度的方法 1 简单匹配方法 d 尘竺 p 其中 m 是匹配的数目 p 是全部变量的数目 2 使用二元变量为每一个状态创建一个新的二元变量 可以用非对称 的二元变量来编码标称变量 将标称变量的相异程度的计算转化为二元变量 的相异程度的计算 4 序数型变量 一个序数型变量可以是离散的 也可以是连续的 一个离散顺序变量与 一个标称变量相似 不同的是对应m 个状态的的m 个顺序值是具有按照一定 顺序含义的 序数型变量在描述无法用客观方法表示的主观质量评估时是非 常有用的 例如 专业等级 描述 就是一个序数型变量 它是按照助教 讲师 副教授和教授的顺序进行排列的 一个连续顺序变量看上去就象一组 未知范围的连续数据 但它的相对位置要比它的实际数值有意义的多 例如 哈尔滨t 程大学硕七学位论文 在足球比赛中 一个球队排列名次常常要比它的实际得分更为重要 在计算对象间差异程度时 序数型变量的处理方法与区间标度变量的处 理方法类似 假设变量厂为一组描述n 个对象顺序变量中的一个 涉及变量厂 的差异程度计算方法描述如下 将第f 个对象的 变量值标记为x 矿 变量厂有m 个有序状态 可以利 用等级1 2 mr 分别替换相应的x 矿 得到相应的勺 勺 1 2 m 由于每个顺序变量的状态个数可能不同 因此有必要将每个顺序变量的 取值范围映射ne o 1 1 区间 以便使每个变量的权值相同 可以通过将第f 个 对象中的第厂个变量的 用以下所计算得到的值来替换 矿筹 采用z 矿作为第f 个对象的厂值 就可以用前面介绍的区间标度变量的任 一种距离计算方法来计算相异程度 5 比例型变量 一个比例型变量就是在非线性尺度上所获得的证测量值 如 指数比例 可以用以下公式近似描述 a e 厨或彳p 一 其中彳和b 为正的常数 典型例子包括 细菌繁殖增长的数目描述 或 放射元素的衰减 在计算比例型变量所描述的对象间的距离时 有三种处理方法 方法一 将比例数值变量当作区间标度变量来进行计算处理 但这不是 一个好方法 因为比例尺度是非线性的 方法二 利用对数转换方法 y 矿 l o g x 来处理第i 个对象中取x 矿变 量厂 然后将y 当作区间标度变量并根据前面所介绍有关区间标度变量的任 一个距离计算公式来进行计算处理 方法三 将x 矿当作连续序数型数据 即将其顺序值作为间隔数值来进行 相应的计算处理 6 混合类型变量 在许多实际应用的数据库中 对象往往是用多个不同类型的变量描述的 一个数据库中可能包含了上述所有类型的变量 对混合类型变量的处理相对复杂一些 一种可行的方法是将不同类型的 哈尔滨t 程大学硕士学位论文 变量组合在同一个相异程度矩阵中 对所有有意义的变量 将它们的值域映 射n o 1 区间内 对象i 之间的相异程度定义为 缈d d i 竺f 一 彰厂 其中 p 为对象中变量的个数 如果两或z 缺失 即对象f 或对象 没 有变量厂的值 或者h x o 且变量厂是不对称的二元变量 那么 指 示项露 o 否则 露 l 变量厂对对象i j 之间的相异程度的计算方法与变量厂的具体类型有 关 1 f 是二元变量或标称变量 如果b x 那么 彤 o 否则 d 厂j 1 2 是区间变量 彤厂 上蔓二虹 这里的乃取遍变量的所 m a x hx i l f m l n hx h f 有非空缺对象 3 厂是序数型或者比例标度型变量 计算秩膏和z 矿 之j 刍 并将z f 作为区间标度变量束处理 2 2 4 聚类挖掘算法的分类 目前存在大量的聚类算法 算法的选择取决于数据的类型 聚类的目的 和应用 大体上 主要的聚类算法可以划分为如下几类 1 分裂 划分 法 给定一个有n 个元组或者记录的数据集 分裂 法将构造k 个分组 每一个分组就代表一个聚类 k n 而且这k 个分组满 足下列条件 每一个分组至少包含一个数据记录 每一个数据记录属于且仅属于一个分组 这个要求在某些模糊聚类算 法中可以放宽 哈尔滨工程大学硕七学位论文 对于给定的k 算法首先给出一个初始的分组方法 以后通过反复迭代 的方法改变分组 使得每一次改进之后的分组方案都较前一次好 所谓好的 标准就是 同一分组中的记录越近越好 而不同分组中的记录越远越好 代表算法有 k m e a n s 算法 k m e d o i d s 算法 c l a r a n s 算法 2 层次法 这种方法对给定的数据集进行层次分解 直到某种条件满 足为止 具体又可分为 自底向上 和 自顶向下 两种方案 例如在 自底向 上 方案中 初始时每一个数据记录都组成一个单独的组 在接下来的迭代 中 它把那些相互邻近的组合并成一个组 直到所有的记录组成一个分组或 者某个条件满足为止 代表算法有 b i r c h 算法 c u r e 算法 c h a m e l e o n 算法等 3 基于密度的方法 基于密度的方法与其他方法的一个根本区别是 它不是基于各种各样的距离 而是基于密度的 这样就能克服基于距离的算 法只能发现 类圆形 的聚类的缺点 这个方法的思想就是 只要一个区域 中的点的密度大过某个阈值 就把它加到与之相近的聚类中去0 代表算法有 d b s c a n 算法 o p t i c s 算法 d e n c l u e 算法等 4 基于网格的方法 这种方法首先将数据空间划分成有限个单元的网 格结构 所有的处理都是以单个的单元为对象的 这样处理的一个突出的优 点就是处理速度很快 通常这是与目标数据库中记录的个数无关的 它只与 数据空间分成的单元数有关 代表算法有 s t i n g 算法 c l i q u e 算法 w a v e c l u s t e r 算法等 5 基于模型的方法 给每一个聚类假定一个模型 然后去寻找能够很 好地满足这个模型的数据集 这样一个模型可能是数据点在空间中的密度分 布函数或者其他函数 它的一个潜在的假定就是 目标数据集是由一系列的 概率分布所决定的 通常有两种方案 统计的方案和神经网络的方案 2 2 5 经典聚类算法一k m e a n s 算法 k m e a n s 算法是最著名与最常用的划分方法 算法以k 为参数 把n 个 对象划分为k 个簇 以使簇内具有较高的相似度 而簇间的相似度较低 相 1 6 哈尔溟工程大 学硕七学1 f 7 论文 似度的计算根据一个簇中对象的平均值 被看作簇的重心 来进行 k m e a n s 算法的处理流程如下 首先 随机地选择k 个对象 每个对 象初始地代表了一个簇的平均值或中心 然后对剩余的每个对象 根据其与 各个簇中心的距离 将它赋予最近的簇 接下来重新计算每个簇的平均值 这一过程不断重复 直到准则函数收敛 通常 采用平方误差准则 其定义 如下 k e i p 一所 1 2 一 一l i i 1 j f c 这里的e 是数据库中所有对象的平方误差的总和 p 是空间中的点 表 示给定的数据对象 m 是簇e 中的平均值 p 和m 都是多维的 这个准 则试图使生成的结果簇尽可能地紧凑和独立 下面给出了k m e a n s 算法的 实现过程 k m e a n s 算法 输入 簇的数目k 和包含 z 个对象的数据库 输出 k 个簇 使平方误差准则最小 流程 1 任意选择k 个对象作为初始的簇中心 2 循环开始 3 根据簇中对象的平均值 将每个对象 重新 赋给最类似的簇 4 更新簇的平均值 即计算每个簇中对象的平均值 5 直到所有对象选择完 这个算法尝试找出使平方误差函数值最小的k 个划分 当结果簇是密集 的 而簇与簇之间的区别明显时 它的效果较好 对处理大数据集 该算法 是相对可伸缩的和高效率的 因为它的复杂度是o n k t 其中 z 是所有 对象的数目 k 是簇的数目 t 是迭代的次数 通常地 k 珂且t f 这 个算法经常以局部最优结束 k m e a n s 算法的缺点 1 只有在簇的平均值被定义的情况下才能使用 这可能不适用于某些 应用 例如涉及有分类属性的数据 2 要求用户必须事先给出k 的取值 要生成的簇的数目 1 7 哈尔滨工程大学硕士学伊论文 3 k m e a n s 算法不适合于发现非凸面形状的簇 或者大小差别很大 的簇 4 它对于噪声和离群数据是敏感的 少量的该类数据就能够对均值产 生极大的影响 k m e a n s 算法有很多变种 它们可能在初始k 个平均值的选择 相异 度的计算和计算聚类平均值的策略上有所不同 其中一个经常会产生较好的 聚类结果的策略是 首先采用层次的聚类算法决定结果簇的数目 并找到一 个初始的聚类 然后通过迭代重定位来改进聚类结果 2 3 隐私保护 2 3 1 隐私保护数据挖掘基本概念 近年来 硬件技术的进步使计算机存储和记录有关消费者和个人资料的 能力大大增强 这导致人们担心个人数据可能由于各种目的而被滥用 为了 减轻人们的担心 大量在隐私保护的前提下进行数据挖掘的技术被提了出来 2 0 0 2 年 g a r t n e r 在一份隐私调查中表示 随着信息化的进一步深入 监控技术使得摄取隐私信息变得很容易 其主要途径如下 1 监视器 该类监控技术已广泛应用于城市街道 楼字 办公场所以 及其他公共场所 主要问题是 什么人有多少机会能够访问到该类数据 2 数字追踪 数字化的工作和生活方式使得追踪历史信息变得更加容 易 包括e m a i l 短信 浏览器访问 金融交易 信用卡和在线买卖的记录 信息等都可能在当事人不知情的情况下被其他人获取 新兴电子标签和移动 电话定位更提供了追踪持有者信息的有效途径 3 信息分析 以数据挖掘为代表的数据分析技术 如聚类和关联规则 等 已用于预测客户群体行为的商业应用中 例如保险公司根据用户的住址 分析其被盗的风险概率 甚至用于医疗保险和人事雇用上 4 信息聚合与访问 从不同处收集用户信息并聚合在一起时 往往能 发现更多隐私信息 从上述的技术中不难发现 对于涉及隐私问题的信息技术 其出发点均 1 r 哈尔滨t 程大学硕士学位论文 是为人们带来有益的信息服务 并且已经得到了人们的认可和普及 那么主 要的问题是如何实现技术应用过程的可约束性 解决方法可以从法律法规以 及技术层面进行 技术层面上 隐私保护数据挖掘是一种非常重要的解决途 径 早在1 9 9 5 年召开的第一届k d d 上 隐私保护数据挖掘就成为了一个专门 的研究主题 1 9 9 8 年 a n nc a v o u k i a n 发表了一篇题