（电路与系统专业论文）数据挖掘中分类属性数据聚类研究[电路与系统专业优秀论文].pdf

摘要 现代数据库和网络技术的发展，使得人们面对的数据量以惊人的速度增长，为 了获取有价值的信息，提出了数据挖掘技术。发展自统计学的聚类分析已成为数 据挖掘中的一个十分活跃的研究领域。本文详细介绍了数据挖掘技术，包括数据 挖掘的研究内容，任务和功能，数据挖掘的一般过程，数据挖掘的常用工具，主 要应用领域和发展趋势。在此基础上对数挖掘中的聚类分析作以详细地论述，总 结了数挖掘中聚类分析的方法和特点，并对聚类结果的评价方法进行了讨论，重 点讨论了分类属性数据聚类，具体研究了k - m o d e s 算法及其变形，并指出了它们 的优缺点。主要探讨了模糊k - m o d e s 聚类结果与原始数据的分类结构的对比方法， 对现有的精确度定义和计算方法进行修正，在划分相似度的基础上，重新定义模 糊k - m o d e s 聚类精确度。应用进化策略对属性进行加权，改进了f u z z yk - m o d e s 算 法，以丛于划分相似度的聚类精确度为聚类结柴的评价准则，进行实验分析，秋 得了较好的聚类效果。 关键词：数据挖掘聚奚分析分类属性进化策略 a b s t r a c t w i t ht h ed e v e l o p m e n to fd a t a b a s e sa n di n t e r a c t ，t h ev o l u m ei nd a t ac o l l e c t i o na n d s t o r a g ei nt h er e c e n td e c a d e sg r o w se x p l o s i v e l y h o wt oa n a l y z e ，e x p l o r ea r t dd i s c o v e r u s e f u lk n o w l e d g er a p i d l ya n de f f i c i e n t l yf r o mt h e s ed a t ab e c o m e st h ef o c u so fs c i e n t i s t s t od e a lw i t ht h i sc h a l l e n g e ，d a t am i n i n gt e c h n o l o g yh a sb e e ns t u d i e da n da p p l i e dt o m a n yi n d u s t r i e s t h ec l u s t e r i n ga n a l y s i sd e r i v e df r o ms t a t i s t i ch a sb e c o m ea na c t i v e a r e ai nt h er e s e a r c ho nd a t am i m n g i nt h ep a p e r ，t h et e c h n o l o g yo fd a t am i n i n gi si n t r o d u c e di nd e t a i l ，i n c l u d i n gt h e a i ma n df u n c t i o n a l i t i e so fd a t am i n i n g ，t h ep r o c e s so fd a t am i n i n g ，t h eu s u a lt o o l sa n d s y s t e m s ，t h em a i na p p l i c a t i o n sa n dt r e n d si n d a t am i n i n g s u b s e q u e n t l y ，c l u s t e r i n g a n a l y s i si nd a t am i n i n gi sd i s s e r t e d ，i n v o l v i n gt h em e t h o d sa n dc h a r a c t e r i s t i c so f c l u s t e r i n gu s e di nd a t am i n i n ga n dt h em e t h o d sf o re v a l u a t i n gt h ec l u s t e r i n gr e s u l t s ， w i t he m p h a s i so nc l u s t e r i n gt h ed a t aw i t hc a t e g o r i c a la t t r i b u t e s k m o d e sc l u s t e r i n g a l g o r i t h ma n di t sv a r i a t i o n sa r ei n t r o d u c e d 、析mt h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s t h e c l u s t e r i n gr e s u l to ff u z z yk m o d e sa l g o r i t h mi sc o n t r a s t e dt ot h ec l a s ss t r u c t u r eo f o r i g i n a ld a t a ，a n dt h ed e f i n i t i o no ft h ep r e s e n tc l u s t e r i n ga c c u r a c ya n di t sc o m p u t i n g m e t h o d sa r ea m e n d e d o nt h eb a s i so ft h ep a r t i t i o ns i m i l a r i t y ，an e wd e f i n i t i o nf o rt h e a c c u r a c yo ff u z z yk - m o d e sa l g o r i t h mi sp r e s e n t e d a ti a s t ，t h ef u z z yk - m o d e sc l u s t e r i n g a l g o r i t h mb a s e do nt h ea t t r i b u t e sw e i g h t e di sp r e s e n t e df o rt h ed i f f e r e n tc o n t r i b u t i o no f e a c ha t t r i b u t eo ft h ed a t as e tt ot h ec l u s t e r i n g w i t han e wf i t n e s s ，t h ee v o l u t i o n a r y s t r a t e g yi su s e dt oo p t i m i z et h ew e i g h tm a t r i xa n dt h ec l u s t e r i n ga c c u r a c yb a s e do nt h e p a r t i t i o ns i m i l a r i t yi su s e dt oe v a l u a t et h ec l u s t e r i n gr e s u l tt h ee x p e r i m e n tg i v e sa b e t t e rr e s u l tw i t l lt h es o y b e a nd i s e a s ed a t as e ta st h ei n p u ts a m p l e s k e y w o r d ：d a t am i n i n gc l u s t e r i n g a n a l y s i sc a t e g o r i c a la t t r i b u t e e v o l u t i o n a r ys t r a t e g y 创新性声明 y 魁 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容之外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其他教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的 兑明并表示了谢意。 本人签名：趣r 赴日期：一，f 妒 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容。可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本人签名：表堆日期：们f ，妒 导师签名：彳鍪蛐日期：塑墨： 一一 塑= 童篷垩 一二 h - _ - - _ - _ _ _ 一一一 一 第一耄绪论 1 1 数槲挖掘的产生背景 疆着数据摩搜零熬遗遮发袋稻i n t e r n e t 赘迅速普及，入销囊嚣薅熬数搀蹙怒裁 魏增长，无谂蘸致、企盐、释蹊枫构或者致麝熬门都积累了海量戆，浚不阏形式 存储的数据潦料。依靠传统的数据库技术对数据进哥亍豢询，检索等分析不能脊效 的帮助用户从数据中提取带有结论性的有用信息，远避不能满足数据分卡斤和处理 的要求。由于猩拥有丈量数据的同时我们对数据中所蕴涵的信息和知识缺怼充分 发搦帮裂躅，从蕊逡戏了整惑豹浪费，囱魏逛会产生太霪豹数据垃圾。鲻愆，人 髓遭甥需要毅豹强蠢力蕊鼗摆分撬方法帮技零鞋蒸凌“数据丰塞，翟篱惑贫乏” 这一现象，帮助入们腻繁杂的数据中挖播出有用静信惠，发现其中存在的关系和 规则，根据现确的数据来预测未来的发展趋势以辅助决策的智能化自动化，从而 带来商业上巨大的信息价值。在这种情况下，数据库知激发现( k d d ，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 ) 和数摄挖掘( d m ，d a l am i n i n g ) 技术应运丽生并显示出强 大蕊皇露力。 从2 0 毽纪姆零代末至夸，k d d 和数镭挖据技术褥妥了缀大静发震。k d d 遮 术语首先出现禚1 9 8 9 年在美国底特律召开的第l l 属阁际人工智能联合公议的 专题讨论会上，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 dd a t am i n i n g ) ，嚣癸在这方蕊发 表了众多鹃礴究成莱巍论文，菸嚣开发了一大拙数据拣稍软 孛，建立了大爨辩穰 哭阚站。对k d d 和数据挖掘的研究醚成为计算机领域的个热门课题。我阐近几 年也逐渐跟上圈际步伐，许多计算机，数据库、人工智能、机器学习领域的专家 学者投入到k d d 鞍数据挖掘的研究中，并已取得了一怒姻成梁。表1 ，1 基泳了数 援挖援蘸送纯历程8 8 进化阶段商业问题浅特技术产晶厂家产品特点 数据搜集“过去五年中计弹椒、磁带和i b m ，c d c提供历史性 ( 6 0 年代) 我的总收入是磁擞的、静态的数 多少? ”摆信息 数攥谤褥“在耨英藉兰关系数舞痒o r a c l e，在记录缀提 ( 8 0 年霞)鹃分帮去年三( r d b m s ) ，结 s y b a s e ，供历变瞧的、 周的销售额是构忧螽询语言 i n f o r m i x， 动态数据信 弗少? ” ( s q l ) ，o d b ci b m ，息 m i c m s o f t 数据挖掘中分类属性数据聚类研究 数据仓库“在新英格兰联机分析处理 p i l o t，在各种层次 决策支持的分部去年三( o l a p ) 、多维 c o m s h a r e ，上提供回溯 ( 9 0 年代) 月的销售额是数据库、数据仓 a r b o r，的、动态的数 多少? 波士顿库c o g n o s ，据信息 据此可得出什 m i c r o s t r a t e g y 么结论? ” 数据挖掘“下个月波士高级算法、多处p i l o t，提供预测性 ( 正在流行)顿的销售会怎理器计算机、海 l o c k h e e d， 的信息 么样? 为什量数据库 i b m ，s g i ， 么? ” 其他初创公 口j 数据挖掘充分利用了机器学习，数理统计，人工智能，模糊逻辑，神经网络， 进化计算等理论和方法，它是应用需求推动下多种学科融合的结果1 1 1 1 2 1 ( 3 1 。 首先是数据库技术，随着数据库技术的不断发展及数据库管理系统的广泛应 用，大型数据库系统已经在各行各业普及，数据库中存储的数据量急剧增大。在 大量的数据背后隐藏着许多重要信息，而这些重要信息可以很好地支持人们的决 策，可是目前用于对这些数据进行分析处理的工具却很少。目前人们用到的主要 是数据库的存储功能，而隐藏在这些数据之后的更重要的信息则没有充分利用。 这些信息是关于数据的整体特征的描述及对发展趋势的预测，在决策生成的过程 中具有重要的参考价值。数据库技术的日益成熟和数据仓库的发展为数据挖掘提 供了发挥的平台。 其次，在数据库技术飞速发展的同时人工智能领域的一个分支机器学习 的研究也取得很大进展。自2 0 世纪5 0 年代开始机器学习的研究以来，先后经历 了神经模型和决策理论，概念符号获取及知识加强和论域专用学习三个阶段。根 据人类学习的不同模式，人们提出了很多机器学习方法如实例学习观察和发现学 习，神经网络和遗传算法等等。其中某些常用且较成熟的算法已被人们运用于实 际的应用系统及智能计算机的设计和实现中。数据挖掘中的许多方法就来源于机 器学习。 最后是应用领域的推动。由于数据存储技术的日渐成熟，数据库和联机事务处 理( o l t p ) 已经被广泛应用于金融，证券，保险销售以及天气预报，工业生产， 分子生物学，基因工程研究等各行各业。这些行业都积累了大量数据两且在产生 着更多的数据，对于这些数据人们已经不满足于传统的统计分析手段而需要发现 更深层次的规律提供更有效的决策支持。从技术的角度来看，专家系统的研究虽 然取得了一定的进展。但是，知识获取仍然是专家系统研究中的瓶颈。知识工程 第一章绪论 师从领域专家处获取知识是非常复杂的个人到个人之间的交互过程，具有很强的 主观性。没有统一的方法。因此，有必要考虑从数据库中自动发现新的知识。 1 2 数据挖掘中的聚类分析 将物理或抽象对象的集合分组成由类似的对象组成的多个类的过程称为聚类。 由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相 似，与其它簇中的对象相异。 作为统计学的一个分支聚类分析已经被广泛研究了多年，主要集中在基于距 离的聚类分析。基于k - m e a n s ，k - m e d o i d s 和其他一些方法的聚类分析工具已经被加 入到许多系统中。在机器学习领域，聚类属于无监督学习。在模式识别领域，聚 类是非监督模式识别的一个重要分支。由于数据挖掘技术是在数据库，机器学习， 数理统计等技术的基础上发展而来，聚类分析也成为数据挖掘领域中一个非常活 跃的研究课题。 数掘挖掘中的聚类分析主要集中在针对海量数据的有效和实用的聚类方法研 究，聚类方法的可伸缩性，高维聚类分析，分类属性数据聚类和具有混合属性数 据的聚类，非距离模糊聚类等。因此，数据挖掘对聚类分析有其特殊的要求：可 伸缩性，能够处理不同类型属性，强抗噪性，高维性，对输入顺序不敏感性，可 解释性和可用性等。 本文正是在此背景下对数据挖掘中的聚类分析进行论述，并着重研究并改进了 具有分类属性数据聚类算法m z z yk - m o d e s 算法【4 】o 1 3 论文内容和结构安排 论文比较系统、完整的论述了数据挖掘技术和数据挖掘中的聚类方法，针对分 类属性数据聚类算法f u z z yk - m o d e s 的聚类精确度提出了新的定义，并利用进化策 略对算法进行改进，取得较好的结果。论文结构安排如下： 第一章， 绪论，简要介绍了论文的背景和意义，以及论文的主要工作。 第二章， 数据挖掘技术，主要论述了数据挖掘的基本理论，包括数据挖掘的 研究内容，任务和功能，数据挖掘的一般过程，数据挖掘的常用工 具，主要应用领域和发展趋势。 第三章， 数据挖掘中的聚类分析，讨论了聚类分析的数据结构和数据类型， 聚类准则的确定，聚类算法的分类，详细介绍了数据挖掘中用到的 主要聚类算法，最后对聚类结果的评价方法进行了讨论。 第四章， 分类属性数据聚类，讨论了k - m o d e s 聚类算法以及由此衍生的 k p r o t o t y p e s 算法，f u z z yk - m o d e s 算法等，指出了它们的优缺点。 数据挖攮中分类瑶性数据蒙娄研究 在_ l 毙基础上，探讨了模糊k - m o d e s 聚类络聚与原始数据的分类结构 的对比方法，对现有的糙确度定义和计算方法进行修正。在划分相 似腹的基础上，重新定义模糊k - m o d e s 聚必精确度。 第五章， 基于弱性加权g o j f u z z y k - m o d e s 算法，应用进化策赂对属性进行加投， 改避了f u z z yk - m o d e s 黪法，戳基于翔分稳数发懿蒙类壤确瘦凳聚樊 蹈莱的评价准慰，进行实验分析，获褥了较好的聚类效果。 结束语， 对论文的工作进行总结并提出以后进一步的研究方向。 第二章数据挖掘技术 一5 第二章数据挖掘技术 数据挖掘就是从数据中提取人们感兴趣的知识，这些知识是隐含的，有效的， 新颖的，潜在有用的以及最终可以理解的模式的高级过程。 其中，数据，是指一个有关事实f 的集合，如学生档案数据库中有关学生基 本情况的各条记录，它是用来描述事物有关方面的信息，是进一步发现知识的原 材料。 新颖，是指经过数据挖掘提取出的模式必须是新颖的，至少对系统来说应该如 此。模式是否新颖可以通过两个途径来衡量，其一是对比当前得到的数据和以前 的数据或期望得到的数据来判断该模式的新颖程度，其二是通过对比发现的模式 与已有的模式的关系来判断，通常我们可以用一个函数来表示模式的新颖程度 n ( e ，f ) ，该函数的返回值是逻辑值或是对模式e 的新颖程度的一个判断数值。 潜在有用，是指提取出的模式应该是有意义的，这可以通过某些函数的值来衡 挝，_ ju 表示模式e 的有作用程度u = u ( e ，1 7 ) 。 可被人理解，数据挖掘的一个目标就是将数据库中隐含的模式以容易被人理解 的形式表现出来从而帮助人们更好地了解数据库中所包含的信息数据。挖掘不同 于以往知识获取技术的一个特点是发现的知识是人们( 至少是领域专家) 可以理解 的，如i f t h e n 的形式，因此，挖掘过程也是一个人机交互螺旋上升的过程， 而以往的方法如人工神经网络不论是知t 发现过程还是知识应用过程内部都是一 个近似黑箱的过程。 模式，对于集合f 中的数据可以用语言l 来描述其中数据的特性，表达式e l ，e 所描述的数据是集合f 的一个子集f ， 只有当表达式e 比列举出所有一中 元素的描述方法更为简单时我们才可称之为模式。如如果成绩在8 1 - 9 0 之问则成 绩优良可称为个模式，而如果成绩为8 l8 2 8 3 8 4 8 58 6 8 78 88 9 或9 0 则成 绩优良就不能称之为一个模式。 高级的处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整， 形成一种螺旋式上升过程。 作为一种数据处理和分析的方法，数据挖掘与传统的数据分析( 如查询、报表、 联机应用分析) 的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发 现知识。数据挖掘所得到的信息应具有预先未知，有效和实用三个特征。它与传统 的统计方法的不同之处主要体现在：通常的统计方法是在已有的假设基础上，从 大量的数据中得到验证，而数据挖掘则是从大量的数据中得到崭新的模式、结论 和假设；数据挖掘是纯粹的给予数据驱动的方式，而统计方法则更多地引入人为 因素并加以分析。探索式数据分析是统计方法中与数据挖掘最相似的分支，但它 所面向的数据集还是比数据挖掘对象小得多。 数攥攘撼串分类蕊蛙数鼯聚裘磷褒 数据挖擒麓范罄器常广泛，数耀缡构可_ 譬是憝层次的、潮状静、关系静帮蕊商对 象的。数据鲋浆不仅育结构化的还商非结构化的，可以怒数据库和数凝仓库、文 本、w e b 信惑、空阁数据鞋及辫豫、撬频窝蠢额数掇莓，燮广义的说，数箨挖援 意昧餐在一些臻实藏鼹察静静糖数据静集会中寻我模式鹣决策支持激稔。它静对 象，w 奠是任何组织在一起鞠数撄集合f 2 2 1 。 2 。l 数耀挖糕魏褥究痰嚣 数攘挖糕粒籁谈爱疆鹁磷戆跫凌三个豢大辩菝拳支犍；羧舞瘴、视嚣攀嚣黎 鼗璎绫谤藜蒸磷主邃行鼹。其主要磷究凑容蕊旗数掇会霉、器矜擦撼冀滚鼯挖撼 语言、半结构他和非结构化数据巾韵数据挖弼、两络数据挖掘、智能诗簿和软计 算在数据挖掘中的艘用、知识液示方法、可襁健技术以及对已有知识瓣维护和群 爨援等。 数攥挖掇艇发现的知识簸鬻照熬霄以下辫类”“： 颤动预粥趋势霸行为 数据挖掘国勘在大型数据库中露找预测性信息，以犍需要谶 亍大鬣警工分析 敬辩瑟魏今可强邈这壹辕盘数爨本麓褥l 是绪论。一个凝艇懿锻子蹙市场预溅洒题， 数据挖攒使用避去有关援销豹数摄激寻找未来投资中剜缀最大黝用户，其它可鞭 溅鼹翘鬈趣耩臻缀被产苏爱试霆瓣撩定搴薛最哥魏骰擞葳囊鹁群落。 3 关联分辑 数撬津中蒋邂存在熬一类现象楚数掇关联。若嚣个或多个交藿筑数缎之糙存 猩某种规律性，就称为关联。关联可分为简单关联、时序关联、因果若联。关联 分褥瑟瑟翡是找爨羧攥露孛爨藏魏关联鼹。骞瑟黉不辩遂数据鬻孛数耀浆焚联遗 数，馨襞翔遵氇楚不确惑魏，嚣魏关联分舞生或熬援粼繁骞曩i 痿浚。 3 ) 聚粪努析 “物以类聚”，聚类分析是究愈从数据本身出发，挖掘数据内在的特征关系， 爨然体瑷数据申瞧岔鲍类别知谖。聚类壤强了人识对寮淡现实戆试潦，爨概念攒 述和偏麓分析簿t 牛多数攒分析和处蠼的前提条件。聚菇技术主要包括传统的模式 谈嶷方法窝数学分炎学。2 0 登瑟黝年代耪，m c h a l s k i 撬出了援念聚粪鼓术，其要 点是在麓分对象辩不仅考虑对象之溺豹距离，遂蘸求捌分蹬黥炎兵有蘩耱斑涵攘 述，从丽避免了传统技术的某些泞聪瞧。 4 ) 概念掇遮 概念攒述就憋对菜类对象的斑溺遴杼撼述，弗概撼漶类对象鼹毒关特强。娥 念描述分为特授瞧描述霸嚣澍髅攒遂，蓊誊摇述菜类黟象豹共溺特征，藤器籀述 不露类对象之麓煞送弱。囊或一个袋麓特征瞧藩述只涉及该类群袈孛掰霄辩象戆 共性。生成醒掰性描述的方法很多，麴庆策树方法、遗传算法等。 5 ) 偏差枪测 数爨簿中躺数据常脊一些髯常诧渌，扶数箍库中稔测这些偏差缀有愆义。偏 1 0 数据挖掘中分类属性数据聚类研究 差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与 模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结 果与参照值之间有意义的差别。 2 3 数据挖掘的一般过程 作为一个学术领域，数据挖掘和数据库知识发现具有很大的重合度，大部分 学者认为数据挖掘和知识发现是等价的概念，相对来讲，数据挖掘主要流行于统 计、数据分析和数据库领域；而知识发现则主要流行于人工智能和机器学习领域。 从数据处理的过程看，可以把数据挖掘看作知识发现过程中同算法相关的一步， 借助于算法在可接受的计算范围内从数据中枚举模式或模型结构。 其基本过程包括数据准备( 如t ap r e p a r a t i o n ) 、数据挖掘和结果的解释和评 竹( in t e r p r e t a t i o na n de v a l u a t i o n ) 1 。如图2 1 数据瓣 图2 1 数据挖掘的一般过程“2 1 数据准备 数据准备又可分为三个子步骤：数据选取( d a t as e l e c tio n ) 、数据预处理( d a t a p r e p r o c e s s i n g ) 和数据变换( d a t at r a n s f o r m a t i o n ) 。数据选取的目的是搜索所有 1 j 业务对象有关的内部和外部数据信息，并从q 一选择出适用于数据挖掘应用的数 嚣二章数据挖掇技术 据。数据予委筵建一般可蕤篷括溪滁噪声、整导诗簿缺值数攒、潜豫重鬟诡黎、完 成数据瓷型转换等。幽数据挖掘的对象是数据仓库时，一般来讲，数拊预处理已 经在生成数据愈库肘完成了。数据变换的主要目的是消减数据维数即降维 ( d i m e n s i o nr e d u c t i o n ) ，静获镌始特征中我积囊歪育麓豹特征 = = 熹减少数据挖掘 珏寸要考愆的特征鬣炎爨个数。 2 数据挖掘阶段 数搬挖掘阶段营毙器确定抡掇的任务或髫瓣。清濒地定义出业务阕禳，认潘 数据挖藏麴磊的是数鬻携弱酌羹骚一步。挖箍的最焉结构怒不可预溺静，德要探 索的问题应是有预见的。然后，决定使用什么样的挖掘算法。同样的任努可以用 不舄款簿法来实瑷，选择实现算法商聪个考虑鞠素：一是不霹斡数据有不霹豹特 点，霞鼗霭要建予之穰荚戆算法寒携镳；二莛麓户或实鞲运行系统豹簧浓，骞豹 瘸户可熊希望获敬描述爱韵、容弱瑷解的知识，而有的用户躐系统的目的遐获取 预测准确度尽可能商的预测型知识。 3 ，终采蜒铎秘评徐 数撼挖掘除段发现出来的摸式，缀过翅户袋钒器的湃价，可能存在冗余或无 关的模式，这时需要将其剔除；墩有可能模式不满足用户黉求，这时则灞骚整个 挖掘过程熏新选取数据、采用新的数据变换方法、设定新的数掇挖掘参数使，甚 至采鼹茭它戆挖援冀法。毽踅，数攘稼掘戆过耧簸要经遐爱复多次，怒一个不 断反馈的过程。 值得注意的鼹，可视化在数据挖掘的整个过程中的各个阶段都起蓑羹骚 乍鼹。 在数据瞧器除段，麓户可篷要使瘸囊方强等绕诗霹程侥羧零聚霪示有关数键，戳 魏潜数攒窍一个耪步靛理解，从稀梵爱好豹选敬数攒打下蕊勰；在挖攒除段，愆 户则要使用与领域闯题有关的可视化工具：在对数据挖掘的结果进行解释和评价 时，通常对发现的模式避行可视化。 2 。4 数据挖掘常鲻技术 在选定了数据挖掘过程模型聪，弱一个需要祷重考虑的魑擦掘算法的选择。如 兹舞述数矮擦舞燕铁人王餐戆领域熬个分支一穰嚣学嗣笈簇瑟来懿，瓣藏凝嚣 学习、模式识别、人工智能领域的常规技术，如聚类( c l u s t e r i n g ) 、 决策树 ( d e c i s i o nt r e e ) 、统计等方法经过改进大都可以应用于数据挖掘。 表2 1 是数撬挖糕投藏繁点k d n u g g e t s 。c o m 对运冬数爨挖撬产鑫秘z 爨瑟蘩 惩鼓零逡孳亍憨统诗m 。 数攥挖掘中分类耩性数据聚娄磷舞 表2 ，t 数据挖黧露磊技术缝谤 19 0 7f l ：2j i l1 9 0 8q - ：2j ；11 9 0 8 年1 0 目 1 4 l 镑 5 0 0 o 6 5 1 8 l i 6 0 o o 5 】2 1 8 2 7 6 1 0 6 0 2 6 1 9 1 4 l 珏 2 0 l3 2 3 1 霹鞋番臻，避稼寒耱经露终，关联凌粼等接拳凌数攥拣糍串煞痰露爱袋疆诀， 可筏继接零受戮越潦越多豹熏撬，以下藏数撂楚掇中常蹋援术进行奔绥。 l 、统计方法 统计方法悬从事物的外在数量上的袈现去推断像事物w 能的舰律性。料学的 蠼簿瞧一黢憨楚狳藏瓣毙较涤，最镪憨蹬从其数囊滚戳上遂过绞_ l + 分辨番蹴蹙 线索，熬嚣褥撼建静骏瀵袋学说，俘避一步深a 鹣理论磷究。遥委年来，缀谤 学褥刭裰大靛发蕊，在簿凌聿嚣器学砑通题串超着基旗蕊戆 筝舔。露霆熬统计方法 有回归分析( 多元回归、自回归) ，刿别分析( 贝叶新剡别、非参数判别等) ，聚 类分援( 系统蒙凝、动态聚类等) 戳及探索性分薇( 烹元分援法、耩荚分撰法簿) 。 目前国际上流行的绫计软件有s a s ，s p s s ，s t a t i s t i c s 等。 2 、攒羧絮鼓术 模耧囊楚袭示秘楚理苓确定糕数攒的霪要方法。穰鞭煞苓俊霹淡处理不跫垒数 据、噪声或不鞲礁数据，褥基在开发数撵的不确定拣摸激方面能掇撰魄传统方法 更灵巧、更平滑的性能。利用模糊勰含理论，对实际问题进行模糊判断、模糊决 策、模糊模式识别、模糊聚类分析。系统能复杂性越醛，精确能力就越低，模糊 瞧裁蘧强。 3 、多嫠次数舔獠稼燕蘩；数瓣藤中熬数夔露怼象缀鬻毽客豢戆毂念豢上瓣译 缁信患，将个数锩集合躲舔成离概念缮次信息的簸攘挖掘技术被称为数搬穰他 ( d a t ag e n e r 8 l i g 斑t i o n ) 。檄念汇总将数援痒中的棚芙数攒出低概念层抽象到巍概 念瑟，圭要窍数据立方体鞫褥向属饿两种方法。 4 、决策树 爰痿惑谂中黪互售慧蘩意趱蕊) 罨蔑数蠢疼孛蒸露爨大整塞慧麓字段，建立 决策撼戆一个麓患，孬摄撵字段酌不网取馕建立瓣瓣分支，在每个分支予黎中， 熏复建立树的下朦缩点和分支的过獠，期可建立决爨树。 决策树的每一个非终结节点表示所考虑的数据项的测试或决策。一个确定分 。糍终撩州 0孙笈醚移碰炎蚪至；暇涮鼢贼黻附 u疑跨垮足 i 第二章数据挖掘技术 支的选择取决于测试的结果。决策树也可以解释为特定形式的规则集，已规则的 层次组织为特征。 5 、支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 建立在计算学习理论的结构风 险最小化原则之上。其主要思想是针对两类分类问题，在高维空间中寻找一个超 平面作为两类的分割，以保证最小的分类错误率。s v m 的一个重要优点是可以处理 线性不可分的情况。 6 、范例推理 范例推理是直接使用过去的经验或解法来求解给定的问题。它常常是一种已 经遇到过并且有解法的具体问题。当给定一个特定问题，范例推理就检索范例库， 如果存在相似的范例，它们的解法就可以用来求解新的问题。该问题被加到范例 库，以便将来参考。 7 、人工神经网络 人工神经网络是模仿人脑神经网络的结构和某些工作机制而建立的一种计算 模型，其特点是利用大量的简单计算单元连成网络，来实现大规模并行计算。工 作机理是通过学习，改变神经元的连接强度。神经网络计算模型有感知器、b p 网 络、自适应映射网等。 由于神经网络的知识获取过程是一个黑箱系统，得到的知识也是以权值形式 存在的隐式知识，因此难以为人所理解”，这是人工神经网络在知识获取方面不足。 在风险决策领域。一个没有推理过程和决策依据的结论是很难被决策者所接受的。 在数据挖掘中对神经网络的改进重点是解决两个问题：知识表达和知识获取”1 。知 识表达( k n o w l e d g er e p r e s e n t a t i o n ) 是使神经网络中抽象的权值代表一定的知识。 例如使权值代表规则的编码，这样在网络训练结束后通过解码就可以得到规则。 这种方法已经在d n a 结构分析、自然语言处理的语法规则提取和化学反应的预测 中得到应用。知识提取( k n o w l e d g ee x t r a c t i o n ) 是给定一个已经训练好的神经网 络，从中提取显式的知识。般是符号形式知识。提取的方法分为白盒法( o p e n b o x ) 和黑盒法( c l o s e d b o x ) 白盒法是考察神经网络内部的每个神经元找出其中的联系与规律 黑盒法是不管神经网络内部结构只考察网络的输出与输入问的联系 一般来说白盒法更适合于理论分析，黑盒法更便于实际应用。今后从数据挖 掘的角度对人工神经网络进行研究的方向有两个，一个是研究出更好的知识提取 方法，另一个是设计新的网络使神经网络中的隐含知识更容易解码。 8 、进化计算 模仿生物进化的类计算方法统称进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 。 遗传算法( g e n e t i ca l g o r i t h m s ) 是其中最广为熟知的。除此之外，遗传规划 数据挖掘中分类属性数据聚类研究 ( g e n e t i cp r o g r a m m i n g ) 、进化策略( e v o l u t i o ns t r a t e g i e s ) 、进化规划 ( e v o l u t io n a r yp r o g r a m m in g ) 也是进化计算的重要成果。 生物的运行机理始终是人类模仿的对象。计算技术领域受达尔文的生物进化 论和孟德尔的遗传定律的启发，在二十世纪五六十年代开始有人考虑将这种优胜 劣汰的生物进化方式用于工程问题求解。1 9 6 7 年出现遗传算法这个术语。1 9 7 5 年 j h h o ll a n d 比较全面地介绍了遗传算法，随后遗传算法成为人工智能研究领域 的一个热点，出现了许多分支。九十年代初期出现了进化计算一词，其目的是将 模拟生物进化的不同分支的学者在思想上集中起来促进它们的共同发展。 大多数进化计算算法具有以下共同特点： 1 ) 智能式搜索进化计算的搜索策略既不是盲目的随机搜索，也不是全面 的穷举搜索，而是在适应度函数约束下的有指导搜索。在目标函数适应度 函数驱动下优胜劣汰逐步逼近目标。 2 ) 渐进式优化进化计算一般模仿生物进化的遗传、杂交、变异等，通过 多次迭代逐渐得出最优解。 3 ) 全局最优解由于进化计算一般都采用了杂交变异等操作，扩大了搜索 范围，因此从理论上讲，有跳出局部最优得到全部最优的可能。 4 ) 黑箱结构进化计算一般只要完成编码和适应度选择，其余的遗传、杂 交、变异等操作都可以自动完成，因此可以看成一种只考虑输入与输出的 黑箱系统。 5 ) 通用性强进化计算的算法大都是一种框架式算法，只有一些简单的原 则要求，在实旌过程中可以赋予更多的含义。 6 ) 并行式算法进化计算的算法中的操作大都是针对个体的，可以在一次 操作中同时进行。 如今进化计算已广泛应用于计算机科学，图像处理，模式识别等工程领域。 在数据挖掘领域，如果能够确定出知识空间，则寻找最优知识或规则的问题就能 用进化计算来解决。 9 、粗糙集( r o u g hs e t ) 方法 粗糙集理论是一种研究不精确不确定性知识的数学工具。由波兰科学家 z p a w l a k 在1 9 8 2 年首先提出“1 ，用于处理含糊性和不确定性。粗糙集由集合的 下近似和上近似来定义的。下近似中的每一个成员都是该集合的确定成员，而不 是上近似中的成员肯定不是该集合的成员，上近似是下近似和边界区的合并。边 界区的成员可能是该集合的成员，但不是确定的成员。可以认为粗糙集是具有三 值隶属函数的模糊集，即：“是”“不是”“也许”。 知识工程研究中一直存在着信息的含糊性( v a g u e n e s s ) 等问题。含糊性有三 种，术语的模糊性、数据的不确定性和知识自身的不确定性。人工智能的基础理 第二章数据挖掘技术 论之一经典逻辑不足以解决这些不确定性问题，为此人们提出了一些解决方 法，包括统计方法、模糊集理论以及d e m p s t e r s h a f f e r 证据理论，但这些方法都 有一些内在缺陷或限定范围。例如基于统计的方法在理论上还令人难以信服，而 模糊集方法则存在如何确定成员隶属度问题。相比之下租糙集方法则有几个优点： 不需要预先知道的额外信息，如统计中要求的先验概率和模糊集中要求的隶属度； 算法简单易于操作。 随着数据挖掘的兴起，粗糙集理论也受到数据挖掘研究者的重视进而受到研 究界的广为注意。粗糙集和数据挖掘关系密切，它为数据挖掘提供了一种新的方 法和工具。首先，数据挖掘研究的实施对象多为关系型数据库，关系表可以被看 作为粗糙集理论中的决策表，这给粗糙集方法的应用带来极大的方便；第二，现 实世界中的规则有确定性的也有不确定性的，从数据库中发现不确定性的知识为 粗糙集方法提供了用武之地；第三，从数据中发现异常，排除知识发现过程中的 噪声干扰也是粗糙集方法的特长：第四，运用粗糙集方法得到的知识发现算法有 剧j i ， ：行执行，极大地捉商了发现效率，划于火规模数抛库叶，的知识发现来说这 正是求之不得的；第五，数据挖掘中采用的其它技术如神经网络的方法不能自动 地选择合适的属性集，而利用粗糙集方法进行预处理，去掉多余属性可提高发现 效率，降低错误率；第六，粗糙集方法比模糊集方法或神经网络方法在得到的决 策规则和推理过程方面更易于证实和检测。 1 0 、可视化技术 可视化( v i s u m i z a t i o n ) 就是把数据、信息和知识转化为可视的表示形式的 过程。可视化技术为人类与计算机这两个最强大的信息处理系统提供了一个接口， 已成为众多商业和技术领域的基本工具。使用有效的可视化界面，可以快速高效 的与大量数据打交道，以发现其中隐藏的特征、关系、模式和趋势等。可视化具 有广泛而重要的影响，拓宽传统的图表功能，使用户对数据的剖析更清楚，能够 引导出新的预见和更高效的决策。 此外，还有规则归纳、公式推理、贝叶斯信念网络等许多其它用于数据挖掘 的技术和方法。复杂的数据挖掘系统通常采用多种数据挖掘技术，或是综合各种 方法技术优点的有效的、集成的技术。 2 5 数据挖掘工具 目前，国外有许多研究机构、公司和学术组织从事数掘挖掘系统的原型与产 品的研制和开发。这些系统和工具除了采用了传统的统计方法外，还采用基于人 工智能的技术，包括决策树、规则归纳、神经元网络、可视化、模糊建模等。这 些工具在挖掘功能和方法上差别很大，不仅体现在关键技术上，还体现在运行平 数据挖掘中分类属性数据聚类研究 台、处理的数据类型、与数据库或数据仓库的耦合关系、提供的数据挖掘查询语 南和可视化工具、价格等方而。 数据挖掘工具可根据应用领域分为三类： 1 ) 通用单任务类：仅支持k d d 的数据采掘步骤。并且需要大量的预处理和善 后处理工作。主要采用决策树、神经网络、基于例子和规则的方法，发现任务大 多属于分类范畴。 2 ) 通用多任务类：可执行多个领域的知识发现任务，集成了分类、可视化、 聚集、概括等多种策略，如i b m 公司的i n t e l l i g e n tb i n e r 和a l m a d e n 研究中心 开发的q u e s t 系统，s g i 公司开发的m i n e s e t 系统，加拿大s i m o n f r a s e r 大学开发 的d b m i n e r 系统，s p s s 公司的c l e m e n t i n e 以及s g i 公司的m i n e s e t 。 3 ) 专用领域类：特定领域的数据挖掘工具针对某个特定领域的问题提供解决 方案。在设计算法的时候，充分考虑到数据、需求的特殊性，并作了优化。现有 的r i ：多数据采掘系统是专为特定目的丌发的，用于专用领域的知识发现，对采掘 的数据库有语义要求，挖掘的知识和采用的方法也较单一，有些系统虽然能发现 多种形式的知识，但基本上以机器学习、统计分析为主，计算量大。如i b m 公司 的a d v a n c e d s c o u t 系统针对n b a 的数据，帮助教练优化战术组合；加州理工学院 喷气推进实验室与天文科学家合作开发的s k i c a t 系统，帮助天文学家发现遥远的 类星体；芬兰赫尔辛基大学计算机科学系开发的t a s a 帮助预测网络通信中的警 报等。 根据数据挖掘所采用的技术，数据挖掘工具可分为以下几种： 基于规则和决策树的工具：大部分数据挖掘工具采用规则发现或决策树分 类技术来发现数据模式和规则，其核心是某种归纳算法。这类工具通常是对数据 库的数据进行挖掘，生成规则和决策树，然后对新数掘进行分析和预测。这类工 具的主要优点是，规则和决策树都是可读的，典型产品有a n g o s ss o f t w a r e 开发 的k n o w l e d g es e e k e r 、a t t a rs o f t w a r e 开发的x p e r tr u l ep r o f i l e r 以及s a l f o r d s y s t e m 开发的c a r t 。 基于神经网络的工具：由于对非线性数据的快速建模能力，基于神经网络 的数据挖掘工具现在越来越流行。其开采过程基本上是将数据聚类，然后分类计 算权值。神经网络很适合非线性数据和含噪声数据，所以在市场数据库的分析和 建模方面应用广泛，典型产品有a d v a n c e ds o f t w a r e 开发的p b p r o f i l e 。 基于模糊逻辑的工具：其发现方法是应用模糊逻辑进行数据查询、排序等。 该工具使用模糊概念和“最近”搜索技术的数据查询工具，它可以让用户指定目 标，然后对数据库进行搜索，找出接近目标的所有记录，并对结果进行评估。 基于数据可视化的工具：这类工具大大扩展了传统商业图形的能力，支持 多维数据的可视化，同时提供了多方向同时进行数据分析的图形方法。 第二章数据挖掘技术 基于统计方法的工具：这些工具没有使用人工智能技术，因此更适于分析 现有信息，而不是从原始数据中发现数据模式和规则。 综合多方法工具：这类工具一般规模较大，适用于大型数据库包括并行数 据库。这类工具开采能力很强，但价格昂贵，并要花很长时间进行学习。 以下是一些典型的数据挖掘产品： 表2 2 典型的数据挖掘产品 产品供应商特点描述 主要采用决策树。自回归预测模型进行数据的分 c a r t & m a r ss a l f o r d 类和预测，能够进行数据的获取、预处理等操作， 并以图形方式表示。 集成了多种数据挖掘算法，具有面向对象的扩展 c 1o m e n t in e s p s s 旧模块价n 使川，一算法平| i 具可以加到它的可 视化编科环境中。 提供多种数据挖掘方法，它是基于数据立方体的 d b