（计算机应用技术专业论文）基于网格的带有参数参考值的聚类算法.pdf

顶十学位论文 摘要 聚类分析是数据挖掘的一个重要领域，具有广泛的应用领域。同时，聚类算 法研究也是数据挖掘领域中一个比较困难的课题。目前很多流行的聚类算法，比 如k - m e a n s 、k - m e d o i d s 、b i r c h 、c u r e 、d b s c a n 、s t i n g 等，虽然得到了广泛 的应用，但是聚类算法也面临着很多的新问题。如聚类参数设置的盲目性、海量 数据的处理、高维数据的聚类等。在聚类的过程中，大多数聚类算法需要用户自 己输入一些参数值，参数值的输入不当将对聚类结果造成重大影响。对于普通用 户来说，如何选取参数的参数值是比较麻烦的事情。所以常常导致聚类参数设置 的盲目性。 对于基于网格的聚类算法，密度闽值是一个非常关键的参数。为了减轻密度 闺值设置的盲目性，本文提出了一种新的算法即一种基于网格的带有参数参考值 的聚类算法( g r p c 算法) 。该算法在网格算法的基础之上结合了密度思想和数据分 布演化思想。根据数据分布演化思想提出了密度阈值公式。通过密度阈值公式的 计算，可以得到多个不同的密度阈值。利用这些密度阈值，该算法不但能满足一 般的聚类要求，而且还能将高密度的聚类从低密度的聚类中分离出来。算法分析 和仿真结果表明，其时问复杂度少于密度聚类算法d b s c a n ，聚类效果较好，能 有效处理任意形状和大小的聚类，很好地识别出孤立点或噪声，可以聚类不同程 度的聚类，并且有较好的精度。 然后，本文对g r p c 算法在高维性和可伸缩性两方面进行了扩展。采用二维 子空间聚类方法来聚类高维数据，将高维数据空间的聚类转化到二维子空间来进 行。利用简单随机抽样技术来抽样大规模数据集，通过对样本数据集的聚类结果 来聚类原数据集。扩展后的g r p c 算法不但能聚类小规模数据集而且能聚类大规 模数据集，不但能聚类二维数据而且能聚类高维数据。扩展后的g r p c 算法时间 复杂度除了跟数据集中数据个数和抽样率有关外跟维度的平方也有很大关系。仿 真结果表明此算法的扩展是完全切实可行的。 关键词：数据挖掘：聚类；密度阈值：网格；高维 董兰堡垒墼蹩至茎鎏薹堡塑圣耋丝鎏 a b s t r a c t c l u s t e r i n gt h a th a saw i d er a n g eo fa p p l i c a t i o n si sa ni m p o r t a n tr e s e a r c hf i e l di n d a t am i n i n g r e s e a r c ho nc l u s t e r i n ga l g o r i t h mi sad i f f i c u l tw o r k a tp r e s e n t ，m a n y p o p u l a rc l u s t e r i n ga l g o r i t h m ss u c h a sk - m e a n s 、k - m e d o i d s 、b i r c h 、c u r e 、 d b s c a n 、a n ds t i n gh a v eb e e na p p l i e ds u c c e s s f u l l yi nm a n yf i e l d s ，b u tm a n yn e w c h a l l e n g e sa r ee m e r g i n g ，s u c ha st h eb l i n d n e s so fp a r a m e t e ra s s i g n m e n t ，t h eh a n d l i n g o fl a r g e s c a l ed a t a s e t sa n dh i g h d i m e n s i o n a ld a t a s e t s ，e t c s o m ep a r a m e t e r so fm o s t c l u s t e r i n ga l g o r i t h m sm u s tb ea s s i g n e dm a n u a l l yb yu s e r si nt h ep r o c e s so fc l u s t e r i n g 1 ft h ev a l u eo ft h o s ep a r a m e t e r si sn o ta p p r o p r i a t e ，t h er e s u l t so fc l u s t e r i n gw i l lb e v e r yb a d s ot h ea s s i g n m e n to fp a r a m e t e r si sah a r dw o r k ，e s p e c i a l l yf o rg e n e r a l u s e r s i tu s u a l l yb r i n g sa b o u tt h eb l i n d n e s so fp a r a m e t e ra s s i g n m e n t f o rg r i d b a s e dc l u s t e r i n ga l g o r i t h m ，d e n s i t yt h r e s h o l di sak e yp a r a m e t e r t o r e d u c et h eb l i n d n e s so fd e n s i t yt h r e s h o l d ，an e wk i n do fc l u s t e r i n ga l g o r i t h mc a l l e d g r p cw a s p r e s e n t e di nt h i st h e s i s g r p ci sa b b r e v i a t e df r o mag r i d b a s e dc l u s t e r i n g a l g o r i t h mw i t hr e f e r e n t i a lv a l u eo fp a r a m e t e r s ，w h i c hi sb a s e do ng r i da l g o r i t h ma n d a d o p t sd e n s i t yt h i n k i n ga n dd a t ad i s t r i b u t i o ne v o l v e m e n tt h i n k i n g 。d e n s i t yt h r e s h o l d f o r m u l ai sp r o p o s e da c c o r d i n gt od a t ad i s t r i b u t i o ne v o l v e m e n t 。a n ds o m ed i f f e r e n t d e n s i t yt h r e s h o l d sa r ec o m p u t e do u tb ym e a n so fd e n s i t yt h r e s h o l df o r m u l a w i t ht h e h e l po ft h e s ed e n s i t yt h r e s h o l d s ，i tc a nn o to n l yc l u s t e rg e n e r a ld a t ab u ta l s os e g r e g a t e h i g h d e n s i t yc l u s t e r sf r o ml o w - d e n s i t yc l u s t e r s a l g o r i t h ma n a l y s i si n d i c a t e st h a tt h e t i m ec o m p l e x i t yo fg r p ci sl e s st h a nd b s c a n s s i m u l a t i o ns h o w st h a tt h i sn e w a l g o r i t h mc a nd i f f e r e n t i a t e b e t w e e no u t l i e r so rn o i s e sa n dc l u s t e r se f f e c t i v e l y ， d i s c o v e rc l u s t e r so fa r b i t r a r ys h a p e s ，w i t hg o o dc l u s t e r i n gq u a l i t ya n dc l u s t e rd i f f e r e n t c l u s t e r sw h o s el e v e lo fc l u s t e r i n gi sn o ts a m ee a c ho t h e r t h ef u r t h e rw o r ko ft h i st h e s i si st od e v e l o pg r p ca l g o r i t h mi nt h ea s p e c t so f s c a l a b i l i t ya n dh i g h d i m e n s i o n a l i t y t w o d i m e n s i o n a ls u b s p a c ec l u s t e r i n gm e t h o di s u s e dt oc l u s t e r h i g h d i m e n s i o n a ld a t a ，w h i c h t r a n s f o r m st h e c l u s t e r i n g o f h i g h d i m e n s i o n a ld a t as p a c ei n t ot h ec l u s t e r i n go ft w o - d i m e n s i o n a ld a t as u b s p a c e s s i m p l er a n d o mt e c h n o l o g yi sa p p l i e dt os a m p l el a r g e s c a l ed a t as e t a f t e rc l u s t e r i n g s a m p l ed a t as e t 。n o n - s a m p l ed a t as e ti sc l u s t e r e db ym e a n so ft h ec l u s t e r so fs a m p l e d a t as e t t h ee x t e n d e dg r p cc a nc l u s t e rn o to n l ys m a l l - s c a l ed a t as e tb u ta l s o l a r g e s c a l e d a t a s e ta n dc l u s t e rn o t o n l y t w o d i m e n s i o n a ld a t ab u ta l s o m h i g h d i m e n s i o n a ld a t a t h et i m ec o m p l e x i t yo ft h ee x t e n d e dg r p ca l g o r i t h mi sn o t o n l yr e l a t e dw i t hs a m p l i n gr a t ea n dt h en u m b e ro fd a t ap o i n t so fd a t as e tb u ta l s o r e l a t e dw i t ht h es q u a r eo fd i m e n s i o n a l i t y s i m u l a t i o n ss h o wt h a tt h ed e v e l o p m e n to f g r p ca l g o r i t h mi se n t i r e l yf e a s i b l e 。 k e yw o r d s ：d a t a m i n g ；c l u s t e r i n g ；d e n s i t yt h r e s h o l d ；g r i d ；h i g hd i m e n s i o n 碗上学位论文 插图索引 图4 1 数据点均匀分布2 7 图4 2 数据点非均匀的分布2 7 图4 3 均匀数据分布图一2 7 图4 4 实验测试数据集3 0 图4 5g r p c 算法聚类结果3 0 图4 6d b s c a n 算法聚类结果3 0 图4 7 半弧形数据聚集提取3 0 图5 1a b 平面数据分布一3 8 图5 2a c 平面数据分布。3 8 图5 3b c 平面数据分布3 8 图5 4 三维空间中的数据簇。3 8 图5 5 三维空间中的大数掇集4 1 图5 6 三维空间中的样本数据集4 l 图5 7 样本数据集的聚类结果4 2 图5 8 原数据集的聚类结果4 3 兰圭塑丝墼丝至量鍪茎堡墼童耋圣鎏 附表索引 表2 1 数据挖掘进化阶段5 表3 1 二值属性条件表1 5 i x 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：z 孓日期；。扩年j ，月z 2 ，日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：窖挈参 翩签名：融 日期：- ，年岁月22 日 日期：扣g 年f 月站日 0 汐 颂士学位论立 1 1 课题研究背景 第1 章绪论 计算机麴诞生以及其飞速的发展对人类生活的各个方面产生了匿大的影响， 极丈的促进了人类文明，使人类从工业社会迈入了信息社会! 在信息社会，人们 常常需要处理海量般的信息，所以希望能够找到种去粗取精，去伪存真的能将 海量般的数据转换成知识的技术。数据挖掘就是在这个背景下产生的。在一次高 级技术调查中，数据挖掘和人工智能被列为“未来三到五年内将对工业产生深远影 响的五大关键技术”之首。近年来，数据挖掘引起了信息产业界的极大关注，其主 要原因在于存在大量的数据，可以被广泛使用，并且迫切需要将这些数据转换成 有用的信息和知识。获取的信息和知识可以广泛用于各种应用，包括商务管理、 生产控制、市场分析、工程设计和科学探索等。 在过去的3 0 年中，计算机硬件稳定的、令人吃惊的进步导致了功能强大的计 算机、数据收集设备和存储介质的大量供应。这些技术大大推动了数据库和信息 产妊的发展，使得大量数据库和信息储存用于事务管理、信息检索和数据分析。 数据的书富带来了对强有力的数据分析工其的霈求，现代计算机技术与数据库技 术，已可以支持存储并快速检索这样规模的数据库。但是，面对“堆积如山”的数 据集合，无论在时间意义上还是空间意义上，传统的数据分析手段还是难以应付， 人们无法理解并有效的使用这些数据，由此导致越来越严重的“数据灾难”。这样， 就需要新的技术来分析这些数据，以使消耗大量奚| 力和物力所收集与整理的宝贵 资源一数据得以利用，这就是数据挖掘( d m ) 等技术产生的背景1 1 , 2 1 。数据挖掘是 从大量数据中提取和“挖掘”知识，它的研究目标是采用有效的算法，从大量现有 豹数据集合中发现并找出最初未知，僵最终可理解豹有用知识，并简明遗表示出 来【3 1 。 数据挖掘是信息技术自然演化的结果。演化过程是数据业界在如下方厩的发 展。数据收集和数据库创建，数据管理( 包括数据存储和检索，数据库事务处理) ， 以及数据分析与理解( 涉及数据仓库和数搀挖掰) 。错如，数据收集和数据库创建 机制的早期开发己成为稍后数据存储和检索、查询和事务处理有效机制开发的必 备基础。随着提供查询和事务处理的大量数据库系统广泛付诸实践，数据分析和 理解自然成为下一个目标【4 1 。数据挖掘可以解决很多的商业问题，包括：数据库 营销、客户群体划分、背景分析、交叉分析等市场分析行为，以及客户流失性分 析、客户信用记分、欺诈发现等等。另外，在生物医学方面，数据挖掘可以分柝 基于网格的带有参数考值的聚类算法 d n a 数据；在其他方瑟可以做到辅助金融、电信和市政部门进行规划，提高各项 服务质量。 聚类分析是数据挖掘的一个重要分支。所谓聚类分析，就是分析数据对象， 而不考虑已知韵类标记。对象根据最大化类内的相似性，最小化类阅的相似性的 原则避行聚类或分组。聚类算法研究是一个具有很强挑战性的研究领域，也是一 个很热门的研究课题。 1 2 课题研究目的及意义 聚类既可以作为一个单独的工具以发现数据库中数据分奄的信息，也可以作 为其他数据挖掘分析算法的一个预处理步骤。它也是一个具有挑战性的研究领域。 目前已经有不少成熟的聚类算法，大体上可分为：基于划分的聚类算法、基于密 度的聚类算法、基于层次的聚类算法、基于网格的聚类算法和基于模型的聚类算 法等。k 中心点算法1 5 】和c l a r a n s 算法f 6 1 虽然简单，容易实现，但是对于复杂 的簇类形状却无能为力。而d b s c a n l 7 1 ，c h a m e l e o n 8 1 ，c u r e 9 1 等算法具有发现任 意形状和大小簇类的优点。但是这些算法，在聚类的过程中需要用户自己输入一 些参数，参数的输入不当将对聚类结果造成重大影响。某些改进的d b s c a n 算法 1 0 l 由于参数选取的不同导致聚类结果的臣大差异。所以对普通用户来说，如何选 取参数是比较麻烦的事情。即使对于有经验的用户来说，当你面对一大堆有待聚 类的数据时，要想确定聚类参数的参数初值也不是那么容易! 因为不同数据集很 可能具有不同程度的数据聚类。为了解决上述问题，本文提出了一种新的聚类算 法：一种基于网格的带有参考参数的聚类算法。这个研究课题的开展，相对以髓 的聚类算法来说，更多的是站在普通用户的角度来看待数据聚类。相似的例子可 以说明前沿技术或暂时的商端技术最终会走向普及化。在w i n d o w s9 5 诞生之前那 时操作系统的冥面不甚友好，操作电脑必须要具备不少的计算机专鼗知识。这样 使得大量的普通用户被隔离在计算机世界之外。自从w i n d o w s9 5 诞生之后尤其是 w i n d o w s9 8 诞生以来，个人电脑迅速普及，进入了千家万户。究其原因，这是因 为现在的w i n d o w s 搽作系统界面非常友好，人性化非常强。w i n d o w s 系统开发人 员是真正地站在普通用户的角度来开发系统的! 所以才有计算机的大众化和互联 网的流行。数据挖掘作为一门极具潜力极有价值的嘉嘴学科，在它成熟之后必将 走向大众，普惠大众。而聚类作为数据挖掘中的一个重要分支亦如此! 本文的研 究课题就是在这种理念的指导下作些先驱住的探索工作。 1 3 论文研究内容 本论文对数据挖掘中聚类算法的分析与研究，主要完成了以下几个方面的工 2 硕士学位论文 俸： 1 介绍了数据挖掘这一知识领域，包括其产生背景，定义。任务和方法，工 作流程。同时还介绍了数据挖掘工具及其选择并且对它今后的发展趋势作了展望。 2 对数据挖掘中的重瑟分支之即聚类分析进行比较详细的阐述，包括其定 义，数据类型，基本要求及常见的成熟算法。 3 在基于网格算法的基础上利用密度的思想并结合新的想法提出了一种薪 的聚类算法即基于网格的带有参数参考值的聚类算法。阐述了它的相关定义，算 法过程。分析了它的算法性能弗且用实验对其迸行了验证。 4 从可伸缩性和高维数据处理两方面，对基于网格匏带有参数参考值的聚类 算法进行了扩展并取得了良好的效果。 1 4 论文组织结构 论文全文共分五章： 第一章绪论部分，介绍了研究课题的背景、目的及其意义 第二章数据挖掘概述，从数据挖掘的产生背景、定义和过程等几个方面对数 据挖掘技术进行了系统的分析和研究。 第三章概述了聚类分析的概念、原理、数据类型及常见的成熟的算法。 第四章提出了一种新的算法即一种基于网格的带有参数参考值的聚类算法 第五章对提出的新算法进行扩展并将其做简单的实际应用 最后，对本文的王作进行了总结，并且说明了本文的研究工作取得的进展以 及慰这一领域做出的贡献，此外还对今后的研究工作提出了展望。 3 基于网格的带有参数考值的聚类算法 第2 章数据挖掘概述 早在1 9 8 2 年，趋势大师约翰奈斯比( j o h nn a i s b i t ) 在他的首部著作大趋势 f m e g a t r e n d s ) 1 1 1 1 中就提到：“人类正被信息淹没，却饥渴子知识”。计算机硬件 技术的稳定进步为人类提供了大量的数据收集设备和存储介质。数据库技术的成 熟和普及使人类积累的数据量正在以指数方式增长。同时互联网技术的出现和发 展己将整个世界连接成一个地球村，人们可以穿越时空般地在网上交换信息和协 同工作。 2 1 数据挖掘的产生背景 在这个信息爆炸的时代，面对着浩瀚无垠的信息海洋，人们迫切需要一种新 技术和自动工具，以便能够利用智能技术帮助我们将这巨大数据资源转换为有用 的知识与信息资源，从两可以帮助我们科学地进行各种决策。于是，一个新的研 究领域。知识发现就应运丽生。由于蕴藏知识的数据信息大多存储于数据库中，因 此又称作数据库中的知识发现( 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 ) 或数据挖 掘( d m d a t am i n i n 蓟。从2 0 世纪8 0 年代末至今，k d d 和数据挖掘技术得到了很太 的发展。k d d 这一术语首先出现在1 9 8 9 年在美国底特律召开的第1 1 届国际人工智 能联合会议的专题讨论会上，1 9 9 1 ，1 9 9 3 和1 9 9 4 年又接着继续举行k d d 专题讨论 会。1 9 9 5 年在加拿大召开了第一届知识发现和数据挖掘国际学术会议。从1 9 9 7 年 开始，k d d 已经拥有了专门的杂志k n o w l e d g ed i s c o v e r ya n d d a t am i n i n g ，国 外在这方面发表了众多的研究成果和论文，并且开发了一大批数据挖掘软件，建 立了大量的相关网站，对k d d 和数据挖掘的研究已成为计算机领域的一个热门课 题。我国近几年也逐渐跟上国际步伐，许多诗算机、数据库、人工智能、机器学 习领域的专家学者投入到k d d 和数据挖掘的研究中，并已取得了一定的成果。下 表1 1 所示的是数据挖掘的进化阶段 1 2 , 1 3 】。 4 硕上学位论文 表2 + 1 数据挖搦进化阶段 进化阶段商业问题支持技术产晶厂家产品特点 数据搜索 “过去五年中 计算机，磁带 提供历史性 我的总收入是 i b m ，c d c 的，静态的数 ( 6 0 年代) 和磁盘 多少” 据信息 “在广州的分 数据访问部去年三月的 关系数据库和 o r a c l e ，s y b a s e 在记录级提供 ( 8 0 年代) 销售额是多 结搦化查询语i n f o r m i x ，i b m ，历史性的，动 少” 言。o d b c m i c r o s o f t 态的数据信息 “在北京的分 数据仓库： 都去年三月的 联机分析处理在各种层次上 决策支持销售额多少? r o l a p ) ，多维 p i l o t ，c o m s h a r e ， 提供阐溯的。 ( 9 0 年代) 深圳据此可得 数据库，数据 a r b o r ，c o g n o s 动态的数据信 出什么结论” 仓库息 数据挖掘 下个月上海的高级算法，多 销售会怎么处理计算机， p i l o t ，l o c k h e e d ，i b m提供预测性的 ( 正在流行) s g i ，其他初创公司信息 样? 为什么?海量数据库 2 2 数据挖掘的定义 数据挖掘( d a t am i n i n g ) ，就是从存放在数据库。数据仓库或其他信息仓库中 的数据中挖掘有趣知识的过程 4 1 。也可以说，数据挖掘( d a t a mi n i n g ) 就是从大量 的、不完全筋、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、 人们事先不知道的、但又是潜在有用的信息和知识的过程l “1 这个定义包括好几层含义： ( 1 ) 数据源必须是真实的、大量的、含噪声的； ( 2 ) 发现的是用户感兴趣的知识； ( 3 ) 发现的知识要可接受、可理解、可运用； ( 4 ) 并不要求发现放之四海皆准的知识，仅支持特定的发现问题。 何为知识? 从广义上理解，数据、信息也是知识的表现形式，但是人们更把概 念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉， 好像从矿石中采矿或淘金一样。原始数握可以是结构他的。如关系数摆库中的数 据；也可以是半结构化的，如文本、图形和图像数据；镁至是分布在网络上的异 构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的， 也可以是归纳的。发现豹知识可以被用于信息管理，查询优化，决策支持和过程 控制等，还可以用于数据自身的维护。 因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查 询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同 5 基十阿饼的带有参数考值的聚类算法 领域的研究者，尤其是数据痒技术、人工智能技术、数理统计、可视化技术、并 行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形 成新的技术热点。这里所说的知识发现，不是要求发现放之四海而皆准的真理， 也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。 实际上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域 的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果。 作为一种数据处理和分析的方法，数据挖掘与传统的数据分析f 如查询、报表、 联机应用分析) 的本质区别是数据挖播是在没有明确假设的前提下去挖掘信息、发 现知识。数据挖掘所得到的信息应具有预先未知、有效和实用三个特征。它与传 统的统计方法的不同之处主要体现在：通常的统计方法是在已有的假设基础上，从 大量的数据中得到验证，而数据挖掘则建从大量的数据中得到崭新的模式、结论 和假设：数据挖掘是纯粹的给予数据驱动豹方式，而统计方法则更多地引入人为 因素并加以分析。探索式数据分析是统计方法中与数据挖掘最相似的分支，但它 所面向的数据集还是比数据挖掘对象小得多。 数据挖掘的范围非常广泛，数据结构可以是层次的、网状的、关系的和面向 露象的。数据对象不仅有结构化的还有非结构化的，可以是数据库和数据仓库、 文本、w e b 信息、空间数据以及图像、视频和音频数据等，更广义的说，数掘挖 掘意味着在一些事实或观察的各种数据的集合中寻找模式的决策支持过程。它的 对象，可以是任何组织在一起的数据集合i ”1 。 与数据挖掘意愚稠近的另一个概念就是知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s ek d d ) i 1 6 1 。我们来看看k d d 的处理过程就能知道d m 与k d d 的差别了。数 据库中的知识发现是一个多步骤的处理过程，一般分为：问题定义，了解相关领 域的有关情况，熟悉背景知识，弄清用户要求；数据摄取根据要求从数据库中提 取相关的数据；数据预处理主要对前一阶段产生的数据进行再加工，检鹰数据的 完整性及数据的一致性，对其中的噪音数据进行处理，对丢失的数据进行填补； 数据挖掘运用选定的知识发现算法，从数据中提取出用户所需要的知识，这些 知识可以用一种特定的方式表示或使用一些常用的表示方式；知识评估将发现的 知识以用户能了解的方式呈现，根据需要对知识发现过程中的菜些处理阶段进行 优化，直到满足要求。由此可见，数据挖掘只是数据库中知识发现的一个步骤， 但又是最重要的一步。因此，往往可以不加区别地使用k d d 和数据挖掘。一般在 研究领域被称作数据库中知识发现的，在工程领域则称之为数据挖掘。 2 3 数据挖掘的任务和方法 数据挖掘任务一般可以分为两类即描述式挖掘和预测式挖掘。描述式挖掘任 务刻划数据库中数据的一般特性。而预测式挖掘任务在当前数据上进行推断，以 6 硕士学位论文 进行预测。数据挖掘的任务主要是关联分析、聚类分析、分类、预测、时序模式 和偏差分析等。数据挖掘的方法，可粗分为：统计方法、机器学习方法、神经网络 方法和数据库方法。 2 3 1 数据挖掘的任务 ( 1 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 关联援刘挖掘是由r a k e s h a p w a l 等人首先提出的。一般用支持度和可信度两 个阀值来度量关联规则的相关性，还不断引入兴趣度、相关性等参数，使得所挖 掘的规则更符合需求f j 。数据关联是数据库中存在的一类重要的、可被发现的知 识。关联分为简单关联、时序关联和因果关联。关联分析的目的是找出数据库中 隐藏的关联溺。一般用支持度和可信度掰个阀值来度量关联规则的相关性，还不 断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。 ( 2 ) 聚类分析( c l u s t e r i n g ) 聚类是把数据按照相似性归纳成若干类别，砑一类中豹数据彼此相似，不同 类中的数据相异【堋。聚类分析可以建立宏观的概念，发现数据的分布模式，以及 可能的数据属性之间的相亘关系。 ( 3 ) 分类( c l a s s i f i c a t i o n ) 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类 的内涵攒述，并用这种描述来构造模型，一般用规则或决策树模式表示p 踟。分类 是利用训练数据集通过一定的算法而求得分类规则。分类可被用于规则描述和预 测。 ( 4 ) 预测( p r e d i c a t i o n ) 预测是利用历史数据找出变化授律，建立模型，并由此模型对未来数据的种 类及特征进行预测f ”】。预测关心的是精度和不确定性，通常用预测方麓来度量。 ( 5 ) 时序模式( t i m e s e r i e sp a t t e r n ) 时序模式是指遥过时间序列搜索出的重复发生概率较高的模式。与回归一样， 它也是用己矫的数据预测未来的值，但这些数据的区别是变量所处时问的不屈。 ( 6 ) 偏差分析( d e v i a t i o n ) 在偏差中包括很多有用的知识数据库中的数据存在很多异常情况，发现数据 库中数据存在豹异常情况是非常重要的。偏差检验的基本方法就是寻找观察结果。 与参照之间的差别。 2 。3 2 数据挖掘的常见方法 数据挖掘的方法大体上可分为：神经网络方法、统计方法、机器学习方法和数 据库方法。神经网络方法，可细分为：前向神经网络( b p 算法等1 、自组织神经网络 ( 自组织特征映射、竞争学习等) 等。统计计方法中，可细分为：回归分析( 多元回归、 7 基于j _ 【畸格的带有参数考值的聚类算法 自涸归等) 、判别分辑( 贝时斯判别、费歇尔判别、非参数判别等) 、聚类分柝( 系统 聚类、动态聚类等) 、探索性分析( 主元分析法、相关分析法等) 、以及模糊集、粗 糙集、支持向量机等。机器学习中，可细分为：归纳学习方法f 决策树、规则归纳 等、鏊于范例的推理c b r 、遗传算法、爱叶斯信念丽络等。数据库方法主要是基 于可视化的多维数据分析或o l a p 方法，另外还有面向属性的归纳方法。下面概 要地说明几类常见的方法f 2 0 】： f 1 1 神经网络方法 神经网络由于本身良好的备棒性、囱组织自适应性、并行处理、分布存储和 高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关 注。典型的神经网络模型主要分3 大类：以感知机、b p 反向传播模型、函数型网络 为代表的，用于分类、预测和模式识别的前馈式神经网络模型：以h o p f i e l d 的离 散模型帮连续摸型为代表的，分别用于联想记忆和优化计算的反馈式神经髓络摸 型；以a r t 模型、k o h o l o n 模型为代表的，用于聚类的自组织映射方法。神经网络 方法的缺点是”黑箱”性，人们难以理解网络的学习和决策过程。 ( 2 ) 遗传算法 遗传算法是一种基于生物自然选择与遗传祝理的隧枧搜索葬法，是一种仿生 全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它 在数据挖掘中被加以应用。s u n i l 己成功地开发了一个基于遗传算法的数据挖掘工 具，利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结粟袁鸹遗 传算法是进行数据挖掘的有效方法之一。遗传算法的应用还体现在与神经网络、 粗集等技术的结合上。如利用遗传算法优化神经网络结构，在不增加错误率的前 提下，删除多余的连接和隐层单元；用遗传算法和b p 算法结合训练神经网络，然 后从阏络提取规则等。但遗传算法的算法较复杂，收敛于局部极小的较早收敛问 题尚未解决。 ( 3 1 决策树方法 决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中 找到一些有价值的，潜在的信息它的主要优点是描述简单，分类速度快，特别适 合大援模的数据处理。最鸯影响和最早的决策极方法是由q u i n l a n 提出的著名鲍基 于信息嫡的i d 3 算法。它的主要问题是：i d 3 是非递增学习算法；i d 3 决策树是单变 量决策树，复杂概念的表达困难；同性间的相互关系强调不够：抗噪性差。针对上 述问题，出现了许多较好的改进算法，如s c h l i m m e r 和f i s h e r 设计了i d 4 递增式学习 算法：钟鸣，陈文伟等提出了i b l e 算法等。 ( 4 ) 粗集方法 税集理论是一种研究不精确、不确定知识的数学工具。粗集方法有几个优点： 不需要给出额外信息：简化输入信愚的表达空间；算法篱单，易于操作。租集处 8 硕上学位论文 理的对象是类似二维关系表的信息表。曩兹成熟的关系数据库管理系统和新发展 起来的数据仓库管理系统，为粗集的数据挖掘奠定了坚实的基础。但粗集的数学 基础是集合论，难以直接处理连续的属性。而现实信息表中连续属性是普遍存在 的因此连续属性的离敖亿是制约粗集理论实用化的难点。现在国际上已经研制出 来了一些基于粗集蛉工具应用软件，如加拿大r e g i n a 大学开发的k d d 。r ，美国 k a n s a s 大学开发的l e r s 等。 ( 5 ) 覆盖正例排斥反例方法 它是利孀覆盖所有正例、排斥所有反例的思想来寻找规刚。首先在正例集含 中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去， 相反则保留。按此思想循环所有正例种予，将得到征例的规则( 选择予的合取式1 。 比较典型的算法有m i c h a l s k i 的a 0 1 l 方法、洪家荣改进的a q l 5 方法以及他的a e 5 方法。 ( 6 ) 统计分柝方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性关 系) 和相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对它们的分析可 采用统计学方法，郎利用统计学原理对数据库中的信息进行分析。可进行常用统 计( 求大量数据中的最大值、最小值、总和、平均值等) 、回归分柝( 用回归方程来 表示变最问的数量关系) 、相关分析( 用相关系数来度量变量问的相关程度1 、差异 分析( 肮样本统计量的值得渤差异来确定总体参数之间是否存在差异) 等。 ( 7 ) 模糊集方法 即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和 模糊聚类分析。系统的复杂性越高，模糊性越强，一般模糊集合理论是用隶属度 来刻画模糊事物的亦此亦彼性的。李德毅等人在传统模糊理论和概率统计的基础 上，提出了定性定量不确定性转换模型即云模型，并形成了云理论。 2 。4 数据挖掘流程 数据挖掘是指一个完整的过程，该过程从大型数据库中挖掘先前未知的，有 效的，可实用的信息，并使用这些信息做出决策或丰富知识。作为一个学术领域， 数据挖掘和数据库知识发现具有银- 大的重合度，大韶分学者认为数据挖掘和知识 发现是等价的概念。相对来讲，数据挖掘主要流行于统计、数据分析和数据库领 域；而知识发现则主要流行于人工智能和机器学习领域。从数据处理的过程看， 可以把数据挖掘看作翔识发现过程中同算法相关的一步，借助于算法在可按受的 计算范围内从数据中枚举模式或模型结构。其基本过程包括数据准备( d a t a p r e p a r a t i o n ) 、数据挖掘( d a t a mi n i n g ) 和结果的解释和评估( i n t e r p r e t a t i o na n d e v a l u a t i o n ) 1 2 1 1 。 9 基于 回格的带有参数考值的聚类算法 f 1 1 数据准备阶段 数据准备又可分为三个子步骤：数据选取( d a t as e l e c t i o n ) 、数据预处理( d a t a p r e p r o c e s s i n g g ) 和数据变换( d a t at r a n s f o r m a t i o n ) 。数据选取的目的是搜索所有与业 务对象有关的内部和外部数据信息，并从中选择出适用于数据挖掘应用的数据。 数据预处理一般可能包括消除噪声、推导计算缺僮数摄、消除重复记录、完成数 据类型转换等。当数据挖掘的对象是数据仓库时，一般来讲，数据预处理已经在 生成数据仓库时完成了。数据变换的主要目的是消减数据维数即降维( d i m e n s i o n r e d u c t i o n ) ，即从初始特征中找出真难有用的特征以减少数据挖掘时要考虑的特征 或变量个数。 ( 2 ) 数据挖掘阶段 数据挖掘阶段首先要确定挖掘的任务或目的。清晰地定义出业务问题，认清 数据挖掘的目的是数据挖掘的重要一步。挖掘的最后结果是不可预测的，但要探 索的问题应是有预见的。然后，决定使用什么样的挖掘算法。同样的任务可以用 不同的算法来实现，选择实现算法有两个考虑因素：一是不同的数据有不同的特 点，因此需要用与之相关的算法来挖掘：二是用户或实际运行系统的要求，有的 用户可能希疆获取描述型的、容易理解的知识，雨有的用户或系统的目的是获取 预测准确度尽可能高的预测型知识。 ( 3 ) 结果解释和评价阶段 数据挖掘阶段发现出来的模式，经过用户或机器的评价，可能存在冗余或无 关豹摸式，这时需要将其剔除；也蠢可能模式不满足用户要求，这时煲i j 需要整个 挖掘过程重新选取数据、采用耨的数据变换方法、设定新的数据挖掘参数值，甚 至采用其它的挖掘算法。因此，数据挖掘的过程一般要经过反复多次，是一个不 断反馈的过程。值得注意的是，可视化在数据挖掘的整个过程中的各个阶段都起 着重要作用。在数据准备阶段，用户可能要使用壹方霉等统计可视化技术来显示 有关数据，以期对数据有个初步的理解，从而为更好的选取数据打下基础；在 挖掘阶段，用户则要使用与领域问题有关的可视化工具；在对数据挖掘的结果进 行解释和评价时，通常对发现的模式进行可视化。 2 5 数据挖掘工具及其选择 伴随越来越多的软件供应商加入数据挖掘这一行列，使得现有的挖掘工具的 性能得到进一步的增强，使用更加便捷，也使得其价格门槛迅速降低，为应用的 普及带来了可糍1 2 ”。当然数据仓库技术的发展同样功不可没。数据仓库是将海量 复杂的客户行为数据集中起来建立的一个整合的、结构化的数据模型，是实施数 据挖掘的基础，这里不作为讨论的重点。一般来讲，数据挖掘工具根据其适用的 范围分为两类：专用数据挖掘工兵和通用数据挖掘工具【2 2 1 。专用数据挖掘工具是针 顿上学位论文 慰某个特定领域的问题提供解决方案，在涉及算法的时候充分考虑了数据、需求 的特殊性，并作了优化。而通用数据挖掘工具不区分具体数据的含义，采用通用 的挖掘算法，处理常见的数据类型。常用的数据挖掘工具比较著名的有i b m i n t e l l i g e n tm i n e r ，s a se n t e r p r i s em i n e r ，s p s sc l e m e n t i n e 等1 2 ”，它们都能够提供常 规的挖掘过程和挖掘模式。 如何选择满足自己需要的数据挖掘工具呢? 对于一个数据挖掘工具，需要从 以下几个方面来考虑： ( 1 ) 产生的模式种类的多少 f 2 ) 解决复杂问题的能力 数据量的增大，对模式精细度、准确度要求的增高都会导致问题复杂