（计算机软件与理论专业论文）数据挖掘中聚类和孤立点检测算法的研究.pdf

山东大学硕士学位论文 摘要 随着计算机应用的普及，信息系统产生的数据量日益增大，如何有效地利用 巨量的原始数据分析现状和预测未来，己经成为人类面临的一大挑战。数据挖掘 技术应运而生并得以迅猛发展，这是快速增长的数据量和日益贫乏的信息量之间 矛盾运动的必然结果。 数据挖掘，又称为数据库中的知识发现，是从大量数据中提取可信的、新颖 的、有效的并能被人们理解的模式的处理过程。数据挖掘是一门新兴的技术，它 以数据库技术作为基础，把逻辑学、统计学、机器学习、模糊学、可视化计算等 多门学科的成果综合在一起，进行如何从数据库中得到有用信息的研究。数据挖 掘技术得到了人们的普遍关注，广泛应用于银行金融、保险、公共设施、政府、 教育、远程通讯、软件开发、运输等各个企事业单位及国防科研上。 聚类分析是数据挖掘中的一个重要研究领域。所谓聚类，就是把没有类别标 记的样本集按某种准则划分成若干类，使类内样本的相似性尽可能大，类问样本 的相似性尽可能小，是一种无监督的学习方法。聚类分析通常是在没有先验知识 支持的前提下进行的，它所要解决的就是在这种前提下，实现满足要求的类的聚 合。聚类分析的研究主要集中在聚类算法上，产生性能好而且实用的聚类算法是 其终极目的。迄今为止，人们提出了很多不同的适用于数据挖掘的聚类算法，但 这些算法仅适用于特定的问题及用户，而且它们在理论和方法上仍不完善，甚至 还有严重的不足之处。对聚类算法的进步优化研究将不仅有助于算法理论的完 善，更有助于算法的推广和应用。 本文在分析了当前各种聚类算法的思想和方法的同时，针对目前基于划分的 聚类算法存在的一些缺陷和不足，提出了基于粗糙集理论的聚类改进算法。解决 了划分问题中不能准确设定聚类个数和只能用于挖掘球形聚类的问题，使得划分 方法也可以用于发现任意形状的聚类。 绝大多数现实世界中的数据库都包含了“噪声 和孤立点数据。一些聚类算 法对于这样的数据敏感，可能导致低质量的聚类结果。因此，本文在分析研究现 有基于距离的孤立点检测算法的基础上，针对其性能和精度上的不足，定义了一 个新的相异度函数来度量孤立点的强弱，从而使孤立点的“孤立”程度有了一个 量化的尺度，然后将该相异度函数作为遗传算法的适应度函数，提出了基于遗传 山东大学硕士学位论文 算法的孤立点检测改进算法。在本算法中，用户只需指定要找的孤立点的个数， 其他的一切均由该算法自动完成，这不仅减轻了用户的负担，也使得外界的影响 达到最小。在综合数据集和真实数据集上的大量对比实验结果验证了该算法的正 确性，同时在性能和质量上也比其它的孤立点检测算法更加合理有效。 关键词：数据挖掘；聚类分析；孤立点检测；粗糙集；遗传算法 i i 山东大学硕士学位论文 a b s t r a c t w i t ht h ew i d eu s a g eo fi n f o r m a t i o nt e c h n o l o g y , d a t ag e n e r a t e df r o md i f f e r e n t i n f o r m a t i o ns y s t e m sb e c o m em o r ea n dm o r e h o wt ou t i l i z et h eh u g eo r i g i n a ld a t at o a n a l y z ec u r r e n t s i t u a t i o na n dp r e d i c tf u t u r eo fq u a n t i t i e se f f e c t i v e l y , h a v ea l r e a d y b e c o m eag r e a tc h a l l e n g et h a tt h em a n k i n dh a sf a c e d t h e r e f o r et h ed a t am i n i n g t e c h n o l o g ya r i s e s a tt h eh i s t o r i cm o m e n ta n dc a nb ed e v e l o p e dr a p i d l y , w h i c hi s a t t r i b u t e dt ot h en e c e s s a r yc o n s e q u e n c eo ft h ec o n f l i c t i n gm o v e m e n tb e t w e e nt h er a p i d i n c r e a s i n gd a t aa n dt h ep o o ri n f o r m a t i o nd a yb yd a y d a t am i n i n g ，a l s oc a l l e da sk n o w l e d g ed i s c o v e r yo fd a t a b a s e s ( k d d ) ，i sa p r o c e s s i n gp r o c e d u r eo fe x t r a c t i n gc r e d i b l e ，n o v e l ，e f f e c t i v ea n du n d e r s t a n d a b l e p a t t e m sf r o md a t a b a s e s d a t am i n i n gi sar e l a t i v e l yy o u n gr e s e a r c ha n da p p l i c a t i o na r e a b a s e do nd a t a b a s et e c h n i q u e s ，w h i c hs y n t h e s i z e sm u l t i d i s c i p l i n a r yp r o d u c t i o n s ，s u c ha s l o g i cs t a t i s t i c s ，m a c h i n el e a m i n g ，f u z z yt h e o r ya n dv i s u a lc o m p u t i n g ，i no r d e rt oa c q u i r e u s a b l ei n f o r m a t i o nf r o md a t a b a s e i th a sa c h i e v e di n c r e a s i n ga t t e n t i o ni nt h ep a s ty e a r s ， a n dh a sb e e na p p l i e dt of i n a n c e ，i n s u r a n c e ，c o m m u n a lf a c i l i t i e s ，g o v e r n m e n t ，e d u c a t i o n ， t e l e c o m m u n i c a t i o n ，s o f t w a r ed e v e l o p m e n to ft h eb a n k ，t r a n s p o r t i n g ，e t c c l u s t e r i n ga n a l y s i si sa ni m p o r t a n tt e c h n o l o g yi n d a t am i n i n g c l u s t e r i n g ，a n u n s u p e r v i s e dc l a s s i f y i n g m e t h o di st h e p r o c e s s o fg r o u p i n g t o g e t h e rs i m i l a r m u l t i d i m e n s i o n a ld a t av e c t o r si n t oan u m b e ro fc l u s t e r so rb i n s c l u s t e r i n gp r o c e s s e s a r ea l w a y sc a r r i e do u ti nt h ec o n d i t i o n 、析t hn op r e - k n o w nk n o w l e d g e ，s ot h em o s t r e s e a r c ht a s ki st os o l v et h a th o wt og e tt h ec l u s t e r i n gr e s u l ti nt h i sp r e m i s e s m o s t r e s e a r c h e sa b o u tc l u s t e r i n ga r ef o c u s e do nc l u s t e r i n ga l g o r i t h m s ；t h em a i np u r p o s ei st o p r o d u c ep r a c t i c a la l g o r i t h m sw i t hb e t t e rp e r f o r m a n c e u pt on o w , m a n yc l u s t e r i n g a l g o r i t h m sh a v eb e e np r e s e n t e d ，b u tt h e s ea l g o r i t h m sa r eo n l ys u i t e ds p e c i a lp r o b l e m s a n du s e r s f u r t h e r m o r e ，t h e ya r ei m p e r f e c tb o t ht h e o r e t i c a l l ya n dm e t h o d o l o g i c a l l y ， e v e ns e v e r ef a u l t o p t i m i z i n gd e e p l yc l u s t e r i n ga l g o r i t h m sw i l ln o to n l yh e l pt op e r f e c t i t st h e o r y , b u ta l s oi t sp o p u l a r i z a t i o na n da p p l i c a t i o n t h i sd i s s e r t a t i o ns y s t e m a t i c a l l y , d e e p l y , r o u n d l ya n dd e t a i l e d l ys t u d i e sa n d a n a l y s e st h et e c h n i q u ea n dm e t h o d so fc l u s t e r i n ga n a l y s i s ，p u t sf o r w a r da ni m p r o v e d c l u s t e r i n ga l g o r i t h mb a s e do nr o u g hs e tt h e o r y , c o n s i d e r i n gt h ef a u l to fp a r t i t i o n b a s e d c l u s t e r i n ga l g o r i t h m t h ei m p r o v e dc l u s t e r i n ga l g o r i t h mr e s o l v e st h ep r o b l e m st h a tt h e n u m b e ro fc l u s t e r sc a n n o tb es e te x a c t l ya n dc a no n l yf i n dc l u s t e r s 谢ls p h e r i c a ls h a p e ， i i i 山东大学硕士学位论文 m a k i n gp a r t i t i o n i n gm e t h o db ea b l et od i s c o v e rc l u s t e r s 、j v i t l la r b i t r a r ys h a p e m o s tr e a l - w o r l dd a t a b a s e sc o n t a i nn o i s yo ro u t l i e rd a t a s o m ec l u s t e r i n g a l g o r i t h m sa r es e n s i t i v et os u c hd a t aa n dm a yl e a dt oc l u s t e r so fp o o rq u a l i t y s o ，t h i s d i s s e r t a t i o ns y s t e m a t i c a l l y , d e e p l y , r o u n d l ya n dd e t a i l e d l ys t u d i e sa n da n a l y s e st h e t e c h n i q u eo fd i s t a n c e - b a s e do u t l i e rd e t e c t i o n c o n s i d e r i n gt h ef a u l to ft h ea l g o r i t h mi n p e r f o r m a n c ea n dp r e c i s i o n ，d e f i n e dan e wd i s s i m i l a r i t yf u n c t i o nt om e a s u r et h ed e g r e e o ft h eo u t l i e r s ，w h i c hc o n s i d e r e da st h ef i t n e s sf u n c t i o no fg e n e t i ca l g o r i t h m , a n dt h e n ， p r o p o s e da ni m p r o v e do u t l i e rd e t e c t i o na l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m i nt h e a p p r o a c h ，w h a tt h eu s e rs h o u l dd oi sn o t h i n gb u ts p e c i f y i n gt h en u m b e ro fo u t l i e r s ， w h i c hr e d u c e st h et a s ko fu s e r sa n dm i n i m i z e st h ei m p a c to ft h eo u t s i d ew o r l d e x t e n s i v ee x p e r i m e n t so ns y n t h e t i ca n dr e a ld a t as h o w e dt h a tt h ea l g o r i t h mi sc o r r e c t a n dv a l i d ，a n dp e r f o r m sb e t t e r a n yt h a n o t h e ro u t l i e rd e t e c t i o na l g o r i t h m si n p e r f o r m a n c e 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 ga n a l y s i s ；o u t l i e rd e t e c t i o n ；r o u g hs e t t h e o r y ；g e n e t i ca l g o r i t h m i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责 任由本人承担。 论文作者签名：兰堕兰之2 日 期：甚塑：! ： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存 论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：嘞兰生导师签名： 山东大学硕士学位论文 第一章绪论 本章对论文涉及的研究领域进行了较为详细的综述。简要介绍了数据挖 掘中聚类分析和孤立点挖掘的研究背景和意义。在对研究现状进行简要综述 的基础上，分析了该领域存在的主要问题，进而引出了论文的主要研究内容， 最后对论文的章节安排作了介绍。 1 1 研究背景及意义 随着信息技术的迅猛发展，近年来数据挖掘引起了信息产业界的极大关注， 其主要原因是随着数据库技术的成熟和数据应用的普及，各个领域积累的数据量 正在以指数速度增长。人们正面临着“数据丰富而知识贫乏”的问题，所以迫切 需要一种新的技术从海量数据中自动、高效地提取所需的有用知识。数据挖掘技 术就是适应这一要求迅速发展起来的一种处理数据的新技术，它可以从大型数据 库中的大量原始数据中提取人们感兴趣的、隐含的、尚未被发现的有用的信息和 知识。数据挖掘是一个融合数据库、机器学习、数理统计、可视化和信息科学技 术为一体的新兴的交叉学科领域。它的发展不仅可以为商务管理、科学研究、查 询优化、过程控制等领域提供决策支持，而且为相关的计算机学科注入新的活力， 从而推进计算机科学向纵深方向发展。毫无疑问，对数据挖掘的深入研究在计算 机理论和应用两个方面都具有十分重大的意义。在数据挖掘所能发现的众多知识 种类中，例如，关联规则的挖掘、分类和预测、聚类分析、趋势分析、偏差分析、 模式分析等，聚类分析是目前数据挖掘领域中研究最为广泛的课题之一。 在数据挖掘领域中，聚类分析是一项重要的研究课题，它主要是从数据库的 记录集中寻找数据间的相似性，并以此对数据进行分类，使得不同类别中的数据 尽可能相异，而同一类数据之间尽可能相似，即“物以类聚”，从而发现数据库中 隐含的有用的信息，同时它也可以作为其他算法的预处理步骤。 聚类技术中对待个体的另一种角度就是孤立点检测。孤立点检测的研究对象 是数据集中偏离绝大多数对象的很小一部分数据。在许多k d d 应用中，研究孤立 点比研究聚类更有用、更重要。因为在某些应用领域中研究孤立点的异常行为能 够发现隐藏在数据集中的更有价值的知识。因此，孤立点检测是一个重要的数据 挖掘任务，称为孤立点挖掘或异常挖掘。 山东大学硕士学位论文 聚类和孤立点检测是两个相辅相成的方面，在聚类的过程中要决定如何处理 孤立点的问题，寻找孤立点的过程有时也可以使用一些聚类的方法缩小数据集的 范围。人们通过聚类或孤立点的分析，识别密集的或稀疏的区域，从而发现全局 的分布模式，以及数据属性之间有趣的相互关系。目前的聚类技术和孤立点检测 技术己经广泛应用在如数据挖掘1 ，2 1 、统计学p 一、机器学习【5 1 、空间数据库技术、 生物学以及入侵检测6 。卅和天气预报1 0 1 等等相关领域中，取得了很大的成功和实 用价值。 综上所述，对于聚类算法和孤立点检测算法的研究一直有着广阔的发展空间， 今后将会在更多的领域中发挥作用。 1 2 国内外研究现状 k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 一词首次出现在1 9 8 9 年8 月举行的 第1 l 届国际联合人工智能学术会议上。迄今为止，由美国人工智能协会主办的 k d d 国际研讨会的规模已经由原来的专题讨论会发展到国际学术大会，人数由二 三十人扩大到七八百人，研究重点也逐渐从发现方法转向系统应用，并且注重多 种发现策略和技术的集成，以及多种学科之间的相互渗透。其他相关专题会议也 把数据挖掘和知识发现列为议题之一，数据库、人工智能、信息处理、知识工程 等领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。其中，i e e e 的k n o w l e d g e a n dd a t ae n g i n e e r i n g 汇刊领先在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论 文代表了当时k d d 研究的最新成果和动态。数据挖掘已经成为当前计算机科学界 的一大研究热点。 目前，国外数据挖掘的研究和应用得到迅速发展。在研究方面，对知识发现 方法的研究取得新的进展，如近年来注重对b a y e s ( 贝叶斯) 1 1 1 - 1 3 1 方法以及 b o o s t i n g i 4 - 1 6 方法的研究和提高：k d d 与数据库的紧密结合。在应用方面，k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤立的过 程。国外很多计算机公司非常重视数据挖掘的开发应用，m m 和微软都成立了相 应的研究中心，一些公司的相关软件也开始在国内销售，如p l a t i n u m 以及m m 。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量，从事数据挖 掘研究的人员主要集中在大学，也有部分在研究所或公司。所涉及的研究领域很 2 山东大学硕士学位论文 多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据挖掘理论方 面的研究。许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究， 如清华大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。 其中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究； 北京大学开展对数据立方体代数的研究；华中科技大学、复旦大学、浙江大学、 中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则挖掘算法 的优化和改造。此外，国内也有关于蚁群算法【1 7 。2 0 1 的公开报道和研究成果，但严 格理论基础尚未奠定，有关研究仍停留在实验探索阶段，大多是对算法的研究和 改进等。 作为统计学的一个分支，聚类分析已有多年的研究历史，这些研究主要集中 在基于距离的聚类分析 2 1 - 2 3 】方面。许多统计软件包，诸如：s - p l u s 、s p s s s r l s a s 都包含基于缸均值，缸中心等诸多聚类分析方法。 由于应用数据库所包含的数据量越来越大。聚类分析已成为数据挖掘研究中 一个非常活跃的研究课题。在数据挖掘中，大多数工作都集中在设计能够有效、 高效的对大数据库进行聚类分析的方法上。相关的研究课题包括：聚类方法的可 扩展性、复杂形状和复杂数据类型的聚类分析及其有效高效性、高维聚类技术、 以及混合数值属性与符号属性数据库中的聚类分析方法等。 1 3 当前研究中存在的问题 1 3 1 聚类分析研究中存在的问题 聚类是一个具有挑战性的研究领域，它的潜在应用提出了各自特殊的要 求。尽管目前提出了许多算法，但没有一种聚类方法能在各个方面都达到理 想要求。在数据挖掘领域，研究工作主要集中在为大型数据库的有效和实际的聚 类分析寻找适当的方法。基于划分方法中的c l a ra n s 方法将采样技术和p a m 结合 起来，尤其适合大型数据库的划分。但是该方法中对象之间的距离是基于欧几里 得距离进行计算的，所以只能发现凸状或球状的聚类，对于任意形状的聚类却无 能为力。另外，在划分方法中，聚类个数通常根据用户视觉和使用方便性假定。 聚类个数一旦确定在整个聚类过程中都不能更改，最终得到的簇的数目就是初始 的聚类个数。但用户往往不能准确设定聚类个数，从而得到的划分也是不准确的。 山东大学硕士学位论文 1 3 2 孤立点检测研究中存在的问题 绝大多数现实世界中的数据库都包含了“噪声 和孤立点数据。一些聚类算 法对于这样的数据敏感，可能导致低质量的聚类结果。因此，聚类和孤立点的研 究并不是孤立的，通常在聚类的过程中要决定如何处理孤立点的问题。 常用的孤立点检测算法包括：基于统计的方法、基于偏离的方法和基于距离 的方法。基于统计的方法主要应用于科研计算。基于偏离的方法中的序列异常的 概念并没有得到普遍的认同。基于距离的方法与基于统计的方法相比，不需要用 户拥有任何领域知识。与“序列异常 相比，在概念上更加直观。 但是基于距离的方法存在如下缺陷。第一，算法需要用户提供最小的可接受 距离，根据这个距离才能说明这个对象是不是孤立点。因此为了挖掘出合适的孤 立点，指定正确的最小距离非常重要，然而这个距离往往很难准确设定。如果距 离选择太小，几乎所有对象都是孤立点；如果距离选择太大，没有一个数据对象 是孤立点。第二，基于距离的孤立点挖掘方法对挖掘出的孤立点不区分强孤立点 和弱孤立点，即不排列大小。要区分孤立点之间的强弱很困难。 1 4 论文的主要内容 本文在系统归纳数据挖掘的一般原理、一般方法以及相关技术的基础上，针 对当前研究中存在的主要问题，对数据挖掘中关键技术之一的聚类分析及孤立点 检测进行了探索性的研究，主要研究内容如下： ( 1 ) 在认真研究当前各种聚类算法的基础上，针对基于划分的聚类算法中存 在的只能发现凸状或球状的聚类以及不能准确设定聚类个数的问题，将粗糙集中 多属性的等价类求解方法引入到划分方法中，提出了基于粗糙集理论的聚类算法。 通过理论分析和实验验证表明改进算法克服了原算法的缺点，消除了同一密集区 域内因选取了多个中心点产生多个聚类的情况，增强了自动探索聚类及有限度还 原自然聚类形状的能力，解决了不能准确设定聚类个数的问题，对于发现任意形 状的聚类也是非常有效的。 ( 2 ) 在认真研究当前各种孤立点检测算法的基础上，针对基于距离的孤立点 检测算法中存在的需要用户提供最小可接受距离和难以区分孤立点强弱的缺陷， 定义了一个新的相异度函数来度量孤立点的强弱，从而使孤立点的“孤立”程度 4 山东大学硕士学位论文 有了一个量化的尺度，然后将该相异度函数作为遗传算法的适应度函数，提出了 基于遗传算法的孤立点检测改进算法。本算法中，用户只需指定要找的孤立点个 数，其他的一切均由该算法自动完成，这不仅减轻了用户的负担，也使得外界的 影响达到最小。理论分析和实验验证均表明新的算法克服了原算法的缺点，提高 了孤立点检测的质量和效率，具有很强的实用性。 1 5 论文的组织结构 本文共分六章，各章的主要内容如下： 第一章绪论，简要介绍了课题的研究背景、当前国内外的研究现状以及研究 中存在的问题；概括介绍了论文的主要内容和组织结构。 第二章数据挖掘概论，介绍数据挖掘的概念、功能、过程以及数据挖掘的常 用技术等。 第三章聚类分析，聚类分析是数据挖掘的一个重要组成部分，本章主要介绍 聚类分析的基本原理、步骤、应用、常用的聚类算法，并分析了各自的优缺点及 适用条件。同时介绍了孤立点检测的基本原理、常见应用以及当前流行的孤立点 检测算法。 第四章基于粗糙集理论的聚类算法研究，简单介绍了常见的聚类算法和粗糙 集理论的基本知识，主要阐述了基于粗糙集理论的改进算法，并对算法进行了分 析和验证。 第五章基于遗传算法的孤立点检测研究，简单介绍了本算法用到的相关概 念，然后定义了一种相异度函数，详细阐述了基于遗传算法的孤立点检测算法， 并对本文采用的改进方法进行仿真实验和结果分析。 第六章总结与展望，对本文的研究工作和成果进行概括总结，并指明今后的 研究方向。 山东大学硕士学位论文 第二章数据挖掘概论 2 1 数据挖掘概念 随着数据库技术的不断发展和数据库管理系统的广泛应用，数据库中存储的 数据量急剧增大，在大量的数据背后隐藏着许多重要的信息，如果能把这些信息 从数据库中抽取出来，将创造很多潜在的利润，而这种从海量数据库中挖掘信息 的技术，就称之为数据挖掘( d a t am i n i n g ，d m ) 1 1 。1 9 9 5 年以来，国外在知识发现 和数据挖掘方面的论文非常多，已经形成了一个热门研究方向。 从技术角度讲，数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和 知识的过程。 从商业应用角度看，数据挖掘是一种崭新的商业信息处理技术。其主要特点 是对商业数据库中的大量业务数据进行抽取、转化、分析和模式化处理，从中提 取辅助商业决策的关键知识，即从一个数据库中自动发现相关商业模式1 2 4 1 。 2 2 数据挖掘功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般 可以分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般特性。预 测性挖掘任务在当前数据上进行推断，以进行预测。 数据挖掘功能以及它们可以发现的模式类型介绍如下： 1 1 概念类描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概 念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述 不同类对象之间的区别。 2 ) 关联分析 数据关联2 5 ，2 6 1 是数据库中存在的一类重要的可被发现的知识。若两个或多个 变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、 因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库 中数据的关联函数，即使知道也是不确定，因此关联分析生成的规则带有可信度。 6 山东大学硕士学位论文 3 ) 分类和预测 分类【2 刀和预测是数据分析的两种形式，可以用于提取描述重要数据类的模型 或预测未来的数据趋势。分类预测分类标号，而预测建立连续值函数模型。 数据分类是根据一个分类模型在数据库中的对象集合中找到一些共同的属 性，并把它分成不同的类型的过程。其目的在于根据历史数据自动创建能预测未 来行为的分类规则。分类规则反映的是属性数据对象和类别标识之间的因果关系。 在分类问题中，待产生类别的数目是事先知道的，而且，训练数据中同时包含有 属性数据和类别表示数据。 分类可以用来预测数据对象的类标记。然而在某些应用中，人们可能希望预 测某些空缺的或不知道的数据值，而不是类标记。当被预测的值是数值数据时， 通常称之为预测。 4 1 聚类分析 数据的聚类分析2 2 ，2 8 ，2 9 1 是根据“类内相似性最大，类间相似性最小”的原则 将一组数据分组( 没有预先定义的类属性) 。这种将实际的或抽象的对象分成相似 对象的类的分组过程叫做聚类。聚类分析有利于在大量对象集合上建立有意义的 划分，而这种划分是一种分而治之的方法，即将大规模的系统分解成较小的组成 部分以简化设计和实现。聚类也便于分类编制，将观察到的内容组织成类分层结 构，把类似的事件组织在一起。 5 ) 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这 些数据对象是孤立点。大部分数据挖掘方法将孤立点视为噪声或异常而丢弃。然 而在一些应用中，如欺骗检测等，罕见的事件比正常出现的那些更有趣。孤立点 数据分析称作孤立点挖掘 3 0 , 3 1 】或孤立点检测。 6 1 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。尽管 这可能包括时间相关数据的特征化、区分、关联、分类或聚类，这类分析的不同 特点包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 7 山东大学硕士学位论文 2 3 数据挖掘过程 数据挖掘是一个完整的过程，该过程从大型数据库或数据仓库中挖掘先前未 知的、有效的、可实用的信息，并使用这些信息做出决策或丰富知识。在实施数 据挖掘之前，先决定采取什么样的步骤，每一步都做什么，达到什么样的目标是 必要的，有了好的计划才能保证数据挖掘有条不紊的实施并取得成功。一般地， 数据挖掘在任何一个问题上的应用，都可以大致分为三个阶段3 2 3 3 】： 第一阶段，即数据准备阶段：得到待分析的问题，以及与该问题相关的数据 库。包括： ( 1 ) 数据清理：主要试图填充空缺的值，识别孤立点、消除噪音，并纠正数 据中的不一致。 ( 2 ) 数据集成：将多个数据源中的数据集合起来存放在一个一致的数据存储 中。这些数据源可能包含多个数据库，数据立方体或一般文件。 ( 3 ) 数据变换：将某一个数据进行某种转换操作，然后将转换后的值作为新 的变量存放在样本数据中，而转换的目的是为了把数据和将来要建立的模型拟和 的更好。 ( 4 ) 数据规约：如果选择用于数据分析的数据集太大，就会降低挖掘的速度 和影响挖掘的结果，于是就用数据规约得到数据集的压缩表示，它小得多，但能 产生同样或几乎同样的分析结果。 第二阶段，即数据挖掘阶段：借助各种数据挖掘工具，从数据库中找出有可 能解决问题的知识。包括： ( 1 ) 确定挖掘的任务是属于数据总结、分类、聚类、关联规则发现或序列模 式发现中的哪一种。 ( 2 ) 选择合适的挖掘技术。在确定挖掘任务的基础上，选择适当的数据挖掘 技术。如分类模型常由有指导的神经元网络或归纳技术来实现：聚类常用聚类分 析技术；关联分析使用关联发现和序列发现技术等。 ( 3 ) 选择挖掘算法。挖掘算法的选择是一个核心的步骤，一般不会存在一个 普遍适用的数据挖掘算法。一个算法在一个领域非常有效，但在另一个领域却可 能不太适合。所以，在面对一个实际的领域时，如何从众多的数据挖掘算法中精 选有效的算法就自然成为研究与开发任务首先要解决的一个核心问题。选择挖掘 8 山东大学硕士学位论文 算法主要考虑两个因素：一是不同的数据有不同的特点，因此需要用与之相关的 算法来挖掘；二是用户或实际运行系统的要求。 ( 4 ) 挖掘数据。用选定的算法或算法组合在模式空间中进行反复迭代的搜索， 从数据集合中抽取出隐藏的、新颖的模式。 第三阶段，即结果表现与解释阶段：将发现的知识用于解释当前或历史现象， 预测未来可能发生的情况，使决策者参照从过去发生的事实中抽取的信息进行决 策制定。包括： ( 1 ) 模式评估：消除无关的、多余的模式，过滤出要呈现给用户的信息。 ( 2 ) 知识表示：利用可视化技术将有意义的模式以图形或逻辑可视化的形式 表示，转化为用户可理解的语言。 以上三个阶段的工作，在实际运作中，一般都存在反复。也有人把上述整个 过程称为数据库知识发现，而仅把第二阶段称为数据挖掘，认为它是知识发现过 程的一个步骤。图2 1 给出了数据挖掘的三个主要阶段及各阶段的相关步骤。 图2 - 1 数据挖掘的过程 2 4 数据挖掘的常用技术 常用的数据挖掘技术可以分为统计分析类、知识发现类和其他类型的数据挖 掘技术三大类【2 4 】。 1 ) 统计分析类 山东大学硕士学位论文 统计分析技术中使用的数据挖掘模型有线性分析和非线性分析、回归分析、 逻辑回归分析、单变量分析、多变量分析、时间序列分析、最近邻算法和聚类分 析等技术。利用这些技术可以检查那些异常形式的数据，然后利用各种统计模型 和数学模型解释这些数据，解释隐藏在这些数据背后的市场规律和商业机会。 2 1 知识发现类 知识发现类数据挖掘技术是与统计类数据挖掘技术完全不同的一种挖掘技 术。它可以从数据仓库的大量数据中筛选信息，寻找市场可能出现的运营模式， 发掘人们所不知道的事实。 知识发现类数据挖掘技术包含人工神经网络、决策树、遗传算法、粗糙集、 规则发现和关联顺序等。 3 ) 其他数据挖掘技术 其他数据挖掘技术包含文本数据挖掘、w e b 数据挖掘、分类系统、可视化系 统、空间数据挖掘和分布式数据挖掘等。 2 5 本章小结 本章对数据挖掘技术进行了系统的阐述。 首先介绍了数据挖掘的概念，分别从技术角度和商业角度给出了数据挖掘的 定义。然后介绍了数据挖掘的功能，数据挖掘功能以及它们可以发现的模式类型 包括：概念类描述、关联分析、聚类分析、孤立点分析、演变分析等。最后介绍 了数据挖掘过程和数据挖掘的常用技术。 山东大学硕士学位论文 第三章聚类分析 “物以类聚，人以群分”，聚类是人类最基本的一项认识活动。聚类的用途非 常广泛。在生物学中，聚类可以辅助动、植物分类方面的研究，以及通过对基因 数据的聚类，找出功能相似的基因；在地理信息系统中，聚类可以找出具有相似 用途的区域，辅助石油开采；在商业上，聚类可以帮助市场分析人员对消费者的 消费记录进行分析，从而概括出每一类消费者的消费模式，实现消费群体的区分。 3 1 聚类分析概述 聚类分卡斤【1 1 源于许多研究领域，包括数据挖掘、统计学、机器学习、模式识 别等。它是数据挖掘中的一个功能，也能作为一个独立的工具来获得数据分布的 情况，概括出每个簇的特点，或者对特定的某些簇作进一步的分析。此外，聚类 分析也可以作为其他分析算法的预处理步骤，这些算法在生成的簇上进行处理【3 4 】。 3 1 1 聚类分析的概念 聚类就是将数据对象分组成为多个类或簇，划分的原则是“类内相似性最大， 类间相似性最小 。与分类不同的是，聚类操作中要划分的类是事先未知的，类的 形成完全是数据驱动的，属于一种无指导的学习方法。 3 1 2 距离与相似性的度量 由于聚类算法是给予数据自然上的相似划法，要求每个聚类内部数据尽可能 的相似而聚类之间差异要尽可能的大。所以定义一种尺度来衡量相似度就显得非 常重要。一般来说，有两种定义相似度的方法。第一种方法是定义数据之间的距 离，描述的是数据的差异。定义距离的方法一般有： ( 1 ) 欧几里得距离：采用传统的距离的概念。 d ( i ，加肛一_ 。1 2 + k ，：1 2 + + k b 1 2 ( 3 - 1 ) 此处，f _ ， , x i 2 ，却) 和产锄拗，坼) 是两个p 维的数据对象。 ( 2 ) 曼哈坦距离： d ( i ，歹) = i x n x ，。i + x ，：- x j ：l + + i - - x 归i ( 3 2 ) ( 3 ) 明考斯基距离：是欧几里得距离和曼哈坦距离的概化，其定义如下： 山东大学硕士学位论文 d ( i ，歹) = x i 。一如1 2 + k x ，：1 2 + + i 一1 2 卢( 3 - 3 ) 此处g 为正整数。当q = l 时表示曼哈坦距离，当q - = 2 时表示欧几里得距离。 ( 4 ) 相互邻接距离：是一种非测度的距离，距离的值取决于数据的上下文。 m n d ( x , ，而) = 朋v f ，砌+ n n ( x i y c j )( 3 4 ) 其中n n ( x i ，劫指而相对于x j 的邻接次序。 ( 5 ) 另外还有特殊领域的距离表示，如字符串处理领域的基于最小数目原子 操作的编辑距离和基于词根的全纯距离【3 5 1 等。 第二种方法是直接定义数据之间的相似度。定义相似度的主要方法有： ( 1 ) 基于距离的方法：距离d 描述的是数据的差异性，而相似度s 描述的是数 据的相似程度。相似度和距离的关系可以看为：d = l s 1 ，即s = l ( d + 1 ) 。可以使用 基于测度的三种距离来计算d 。如使用明考斯基距离，则有： s m 嘛m 瓿b t ，x j 、) = ( 3 5 ) ( 2 ) 余弦；! ! j 1 9 量的方法：用两个数据矢量之间的角度或角度的余弦定义相似度。 x ：x ix ：x ； k 一毛一卜晌2 赢素 。6 ( 3 ) j a c c a r d 相似度：给出了两个数据公共特征与总特征的比值。这种方法可 以应用在超市购物数据3 6 1 。 y r r s j a c 。以( 一，x ，) = j _ j l 了一 ( 3 - 7 ) x ：x i 七x jx 一x ：x 3 1 3 数据挖掘算法对聚类的典型要求 聚类是一个富有挑战性的研究领域聚类的潜在应用对聚类算法提出了各种 特殊的要求。数据挖掘对聚类的典型要求如下： 可伸缩性许多聚类算法在小于2 0 0 个数据对象的小数据集合上工作很好；但 是，一个大规模数据库可能包含几百万个对象，在这样的大数据样本上进行聚类 可能会导致有偏差的结果。 处理不同类型属性的能力许多算法被设计用来聚类数值类型的数据。但是， 应用可能要求聚类其他类型的数据，如二元类型，分类标称类型，序数型数据， 1 2 山东大学硕士学位论文 或者这些数据类型的混和。 发现任意形状的聚类许多聚类算法基于欧几里得距离或曼哈坦距离度量来 决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。 但是，一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。 用于决定输入参数的领域知识最小化许多聚类算法在聚类分析中要求用户 输入一定的参数，例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。 参数通常很难确定，特别是对于包含高维对象的数据集来说更是如此。要求用户 输入参数不仅加重了用户的负担，也使聚类的质量难以控制。 处理噪声数据的能力绝大多数现实世界中的数据库都包含了孤立点、未知数 据或错误数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。 对于输入记录的顺序不敏感一些聚类算法对于输入数据的顺序是敏感的。例 如，同一个数据集合，当以不同的顺序提交给同一算法时，可能生成差别很大的 聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。 高维性一个数据库或者数据仓库可能包含若干维或属性。许多聚类算法擅长 处理低维的数据，可能只涉及两到三维。人类最多在三维的情况下能够很好的判 断聚类质量。在高维空间中聚类数据对象是非常有挑战性的，特别是考虑到这样 的数据可能非常稀疏，而且高度偏斜。 基于约束的聚类现实世界的应用可能需要在各种约束条件下进行聚类。假设 需要在一个城市中为给定数目的自动提款机( a t m ) 选择安放位置。为了做出决定， 可以对住宅区进行聚类，同时考虑如城市的河流和公路网，每个地区的客户要求 等情况。要找到既满足特定的