（计算机应用技术专业论文）聚类分析在科学数据挖掘中的应用研究.pdf

摘要 摘要 如何让各种数据挖掘技术更好地为实际工程所服务，一直是数据挖 掘领域的一个挑战。一方面是人们对快速、准确而全面获取信息的渴望， 而另一方面却是各种信息的纷繁芜杂，在这两者之问架设一座桥梁的确 是一个巨大的挑战。聚类分析在数据挖掘技术中占有重要的位置。所谓 聚类，是将一个数据单位的集合( 数据源) 分割成几个称为类或类别的子 集，每个类内的对象之间是相似的，但不同类的对象间区别相对较大。 聚类分析是在没有先验知识支持的前提下，根据事物本身的特性研究被 聚类对象的类别划分，实现满足这种要求的类的聚合，它所依据的原则是 使同一类中的对象具有尽可能大的相似性，而不同类中的对象具有尽可 能大的差异性。 论文基于大规模核物理科学数据挖掘的背景，全面介绍了数据挖掘 的关键技术和主要任务，从理论、算法和应用三个层次，结合科学数据 的特点来分析预处理技术和聚类方法，提出了很多实用的预处理方法： 对h d f 5 科学数据进行分块、除噪、集成、变换等，同时对它使用“截断 法”和“逐层求差法”进行规约，并对数据进行信息提取。在聚类方面， 经过比较各种聚类算法和分析科学数据的特点，提出了结合k 一平均思想 的改进型系统聚类算法。此聚类算法有如下特点：能生成具有代表性的 数据簇中心；使用相似系数计算距离，避免了距离受量纲影响的缺点； 不需要多次迭代计算，减少了计算量；不需要指定初始中心；改进了聚 类图，更容易得出聚类阀值。实验结果表明这种改进的系统聚类算法非 常适合科学数据的处理。 本文最后简单介绍了我们开发的科学数据挖掘系统。其中重点介绍 了聚类分析模块的设计和功能。 关键词：数据挖掘，聚类分析，科学数据，预处理，知识发现 a b s t r a c t a b s t r a c t i t sar e a lc h a l l e n g ef o ru st om a k ed a t am i n i n ga l g o r i t h me a s i e rt o u s ei no u rp r o j e c t ，t h ei n f o r m a t i o ni nr a wd a t ai ss h o r to fo r g a n i z a t i o n ， a n df u l lo fam a s so fn o i s e ，a n do nt h eo t h e rs i d e ，p e o p l ew a n tt oo b t a i n t h ei n f o r m a t i o nq u i c k l ya n da c c u r a t e l y c l u s t e r i n ga n a l y s i s i sa n i m p o r t a n tp a r to ft h ew h o l ed a t am i n i n gs y s t e m c l u s t e r i n gi st h ep r o c e s s o fg r o u p i n gt h ed a t ai n t oc l a s s e so rc l u s t e r ss ot h a to b je c t sw i t h i nt h e s a m ec l u s t e rh a v eh i g hs i m i l a r i t yi nc o m p a r i s o nt oo n ea n o t h e r ，b u ta r e v e r y d i s s i m i l a rt oo b j e c t si no t h e rc l u s t e r s c l u s t e r i n ga n a l y s i si st h e m e t h o dw h i c hp a r t i t i o n sc l a s st ot h ec l u s t e r e do b je c t sa sr e q u i r e do f t h i n g sc h a r a c t e r i s t i c 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 n c o n d i t i o nw i t hn op r e k n o w nk n o w l e d g e ，s ot h em o s tr e s e a r c ht a s ki st o s o l v eh o wt og e tt h ec l u s t e r i n gr e s u l t si nt h i sp r e m i s e s t h i st h e s i sa i m sf od i s c u s st h e c l u s t e r i n gf e c h n i q u e s w i t ht h e b a c k g r o u n do fl a r g e s c a l en u c l e a rp h y s i c ss c i e n c ed a t am i n i n g f i r s t ，w e i n t r o d u c et h ek e yt e c h n i q u e sa n dt h em a i nt a s ki nd a t am i n i n g t h e nw e a n a l y z e t h ed a t a p r e p r o c e s s i n gt e c h n i q u e s a n dc l u s t e r i n gt e c h n i q u e s c o m b i n ed a t am i n i n gt e c h n i q u e s w i t hs c i e n c ed a t a f r o md a t a p r e p r o c e s s i n ga s p e c t ，w ep r o p o s e s o m em e t h o d so f s e g m e n t i n g ， d e n o i s i n g ，i n t e g r a t i n ga n dt r a n s f o r m i , n g ，a n dw eu s e “t r u n c a t i o nm e t h o d a n d“s u c c e s s i v ed i f f e r e n c em e t h o d ”i nd a t ar e d u c t i o n a t1 a s tw ee x t r a c t i n f o r m a t i o nf r o mt h es c i e n c ed a t a i nt h ef i e l do fc l u s t e r i n g ，b y c o m p a r i n gs o m ec l u s t e r i n g m e t h o d sa n da n a l y s i n gc h a r a c t e r i s t i c so f s c i e n c ed a t a ，w ep r o p o s ea ni m p r o v e dh i e r a r c h i c a lc l u s t e r i n gm e t h o d c o m b i n i n gt h ei d e ao fk - m e a n sm e t h o d t h i sm e t h o dh a ss o m es p e c i a l i t i e s ： b r i n g i n gt h ed a t ac l us t e rc e n t e r ，u s i n gs i m i l a r i t ya sc l u s t e r i n gd i s t a n c e ， 1 i a b s t r a c t a v o i d i n g d i m e n s i o ni n f l u e n c i n g t h e d i s t a n c e ，r e d u c i n g i t e r a t i v e c o m p u t a t i o n ，d on o tn e e dd e s i g n a t i n gt h ed a t ac e n t e r ，t h ec l u s t e r i n gm a p h a sb e e ni m p r o v e d ，w ec a ng e tt h e c l u s t e r i n g t h r e s h o l de a s i l y t h e c l u s t e r i n g r e s u l t s p r o v et h i si m p r o v e d h i e r a r c h i c a l c l u s t e r i n gm e t h o d s u i t a b l ef o ro u rs c i e n c ed a t ap r o c e s s a tl a s t ，t h et h e s i si n t r o d u c eo u rs c i e n c ed a t am i n i n gs y s t e m ，a n dt h e d e s i g na n df u n c t i o no ft h ec l u s t e r i n gm o d u l 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 g ，s c i e n c ed a t a ，d a t ap r e p r o c e s s i n g ， k n o w l e d g ed i s c o v e r y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 杏；建良 日期：御6 年厂月2 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：冷j | p 0导师签名： 日期：刎6 年厂月i z 日 第一章引言 1 1 研究背景 第一章引言 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，无数个数 据库被用于商业管理、政府办公、科学研究和工程开发等，这一势头仍将持续发展 下去。当今数据库的容量已经达到上万亿的水平( t ) l ，0 0 0 ；0 0 0 ，0 0 0个字节。,000 在这些丈量数据的背后隐藏了很多具有决策意义的信息，那么怎么得到这些“知 识”呢? 也就是怎样通过一颗颗的树木了解到整个森林的情况? 于是，一个新的挑 战被提了出来：在这被称之为信息爆炸的时代，信息过量几乎成为人人需要面对的 问题。如何爿能不被信息的汪洋大海所淹没，从中及时旋现有用的知识，提高信息 利用率昵? 要想使科学实验数据真正地为科研服务，只有充分对其进行分析、挖 掘，帮助科研工作者发现以前不能发现的问题，找出以前不能找出的规律。要想 使数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决策和战略 发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。 计算机科学对这个问题给出的最新回答就是：数据挖掘，在“数据矿山”中 找到蕴藏的“知识余块”，帮助企业减少不必要投资的同时提高资金回报。数据挖 掘给企业带来的潜在的投资回报几乎是无止境的。世界范围内具有创新性的公司 都开始采用数据挖掘技术来判断哪些是他们的最有价值客户、重新制定他们的产 品推广策略( 把产品推广给晟需要他们的人) ，咀用最小的花费得到晟好的销售。 因此，面对”人们被数据淹没，人们却饥饿于知识“的挑战，数掘挖掘和知识发现 ( d m k d ) 技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力“。 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的 过程。还有很多和这一术语相近似的术语，如从数据库中发现知识( k d d ) 、数据分 析、数据融合( d a t a v u s i o n ) 以及决策支持等。人们把原始数据看作是形成知识的源 泉，就像从矿石中采矿一样。原始数据可咀是结构化的，如关系型数据库中的数据， 也可以是半结构化的如文本、图形、图像数据，甚至是分布在网络上的异构型数 掘。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是 归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等， 电子科技大学硕士学位论文 还可以用于数据自身的维护。因此，数据挖掘是一门广义的交叉学科，它汇聚了不 同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等方面 的学者和工程技术人员。 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定 数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、 分析、综合、推理、学习和评估，以指导实际问题的求解，企图发现事件间的相互 关联，甚至利用已有的数据对未来的活动进行预测。 在科学研究领域，随着科学仿真实验数掘的越来越多，且不同实验采集的数据 分散于不同的计算机中。科学家们几乎不可能通过手工的方式来发现各数据源之 间的内在联系。这迫切需要研究出与此对应的新的数据挖掘技术及其挖掘工具来 解决此类问题。目前，国外对数据挖掘技术的研究比较多，但专门针对科学数据 的研究非常少。国内此领域的研究处于初步的起始阶段，成熟的研究成果基本空 白。 聚类分析是数据挖掘领域中的一个重要研究课题，它依据数据对象的特点和 对象之间的关系来分组，其目标是使得分在一个组内的对象具有较大的相似性， 而分在不同组中的对象具有较高的相异性。在数据挖掘领域，聚类的研究工作主 要集中在为大型数据库的有效性和实际的聚类分析寻找适当的方法，提高聚类可 伸缩性，提高聚类算法对高维复杂分布数据聚类的有效性等方面。 技术的革新使科学家能够以不断增加的步速，从试验、仿真和观测中收集数 据，数据容量从近来的十亿字节到现在的干兆字节，并且不久就将达到力| 亿字节。 我们产生数据的能力已经远远超过了我们剥它们的研究、分析和理解的能力，而 且所收集到的可利用的复杂数据其表示都是图像或者时| 1 j 】j 序列。为了实现我们的 科学目标，我们需要从这些数据中提取有用的信息来充分的对它们进行知识丌采。 可不幸的是，由于在许多科学领域中数据的尺度范围7 7 m i - l 之大、复杂度如此之高， 以至于使用人工来对它们进行分析、研究和理解完全是不切实际的。这导致的结 果是，有用的信息经常被忽视掉，并且增强了的计算能力和数据搜集能力的潜在 优势只能部分发挥出来。 为了解决这个问题，我们应用并扩展了数据挖掘领域的方法，开发新的科学 数据挖掘技术，希望能够提高科学家与大规模、高纬度、时变的科学数据之间的 交互性。这些技术能够帮助我们自动的在数据中进行模式识别，并且使科学家们 能够交互性地只对感兴趣的某些领域的数据进行知识开采o ”。 科学数据挖掘技术可以应用到仿真数据，试验数据，以及在各个不同科学领 第一章引言 域中收集的观测数据中。万亿次的计算环境使对复杂现象的仿真变为现实，并且 仿真输出的数据量越来越庞大。这些仿真在许多领域中都扮演着十分关键的角色， 例如核武器管理领域中，计算机仿真已经用来代替了试验；又如天气建模领域中， 利用试验是不切实际的也是不明智的。为了让科学家能够理解这些仿真的输出， 可视化技术正频繁的应用于数据的展示。由于仿真输出的数据规模是如此之大， 因此可视化技术并不能充分的对它们进行展示。如果将可视化技术和数据挖掘技 术结合在一起，那么就能够实现交互式的数据展示，仅仅将科学家们感兴趣的某 些领域的数据展示出来，使他们能够快速的对输出数据进行知识开采。这样不仅 能够帮助科学家理解单个仿真的输出数据，而且能够使他们对比多个仿真的输出 结果，同时还可以将试验同仿真进行对比，且可以交互式的对仿真进行控制“h ”。 科学数据挖掘是数据挖掘中较复杂且国内研究较少的领域。现在科学仿真数 据，试验数据越来越多，越来越复杂，给表示、存储、理解、分析和可视化这些 数据带来了困难。目前，国外已有不少的科学数据格式系统，如c d f 、n e t c d f 、 h d f 5 等，也相应地诞生了各种各样的科学数据管理系统，它们给科学数据的存储 和管理带来了方便。对于模拟数据，常常以网格( m e s h ) 形式表示，通用的格式系 统如上述三种数据格式系统均支持网格数据( m e s hd a t a ) 的存储和处理。尽管如此， 要理解、分析这些数据，并从中获取知识仍是不易。科学数据集有其本身的特性， 如数据的时空相关性，使得现有的数据挖掘技术不能够完全适应这种特性，又如 数值模拟科学数据具有特征互相交错、复杂、难于抽取，数据维数高、数据集大、 运算效率低等特性，利用传统的数据挖掘算法进行知识发现执行效率底下，且效 果较差。由此科学数据挖掘势在必行。 由于科学数据的特殊特点，使得科学数据挖掘不但具有很高的应用价值，同 时也具有显著的理论研究价值。 对科学数据的挖掘在方法的研究和应用上都具有空前的挑战性和驱动力。如 何对数值模拟的海量数据进行分析? 如何智能地从中获取科学家们感兴趣的有益 信息? 如何从已知的海量数据去分析其间的相互关联、预测未知信息及趋势? 这 些都是我们在研究中需要克服的困难和关键问题。因此，我们将考虑新的适用解 决方案，以解决科学数据挖掘中不同于商业和传统数据挖掘中的特征析取和数据 集成等问题旧“。 电子科技大学硕士学位论文 1 2 作者所做工作及本文内容安排 1 2 1 作者所做工作 本人目前主要研究科学数据的预处理和聚类技术及其在大规模科学数据中的 实现技术，这一课题涉及到了当前科学界的研究热点，具有显然的科学意义和很 高的应用价值。可概括为以下几个方面： ( 1 )作者通过查阅国内外大量相关技术文献，在了解各种数据挖掘技术的 基础上，针对大规模科学数掘集研究数掘挖掘技术，初步确定了数据挖掘实验平 台的采掘方案。 ( 2 )针对科学数据的特点以及科学数据的物理意义寻找合适的方法对科学 数据做预处理。 ( 3 )在理解和掌握聚类算法的基础上，针对现有聚类算法的优点和缺点， 结合科学数据的特点，提出了一种改进的系统聚类算法。而且，对此聚类算法进 行了大量的实验与分析研究。 ( 4 )在分析比较数据挖掘的各种方法技术上，采用系统聚类分析方法实现 了具体的聚类模型。利用此聚类模型和相关预处理技术，丌发了一个科学数据专 用的数据挖掘软件，并以实例进行了具体的实验和研究。 ( 5 )在构思科学数据挖掘系统的基础上，学习j a v a 丌发语言的一些上层功 能，粟用软件重用思想将界面和算法相分离，便于软件的扩展和更新，在科学数 据挖掘系统开发完成之后，作者针对改进的聚类算法，结合物理学的相关知识， 进行了进一步改进的尝试与探索。 1 2 2 本文内容安排 第1 章介绍了本课题的研究背景、研究内容以及论文章节安排。 第2 章回顾了课题相关技术的发展历史和研究现状。 第3 章介绍和分析了数据挖掘的基本原理、相关技术及应用领域。 第4 章介绍了和分析了科学数掘相关处理技术，着重探讨了科学数据的预 处理技术和科学数据的聚类分析技术。 第5 章详细介绍和探讨了我在项目中对科学数据所做的预处理。 第6 章详细介绍和探讨了我在项目中对科学数据所做的聚类分析以及对系 统聚类算法所做的改进。 4 第一章引言 第7 章介绍了我们的数据挖掘软件的开发设计，着重介绍了聚类模块的设 计与分析。 第8 章总结了存在的问题及进一步发展。 电子科技大学硕士学位论文 第二章国内外相关技术发展综述 2 1 人工智能发展综述 2 1 1 人工智能的起源 从1 9 5 6 年正式提出人工智能学科算起，4 0 多年来，取得长足的发展，成为一 门广泛的交叉和前沿科学。总的说来，人工智能的目的就是让计算机这台机器能 够像人一样思考。如果希望做出一台能够思考的机器，那就必须知道什么是思考， 更进步讲就是什么是智慧。什么样的机器才是智慧的呢? 科学家已经做出了汽 车，火车，飞机，收音机等等，它们模仿我们身体器官的功能，但是能不能模仿 人类大脑的功能昵? 到目前为止，我们也仅仅知道这个装在我们天灵盖里面的东 西是由数十亿个神经细胞组成的器官，我们对这个东西知之甚少，模仿它或许是 天下最困难的事情了。 当计算机出现后，人类开始真正有了一个可以模拟人类思维的工具，在以后 的岁月中，无数科学家为这个目标努力着。现在人工智能已经不再是几个科学家 的专利了，全世界几乎所有大学的计算机系都有人在研究这门学科，学习计算机 的大学生也必须学习这样一门课程，在大家不懈的努力下，现在计算机似乎已经 变得十分聪明了。例如，1 9 9 7 年5 月，i b m 公司研制的深蓝( d e e pb l u e ) 计算机 战胜了国际象棋大师卡斯l 旧洛夫( k a s p a r o v ) 。大家或$ - q ：不会注意到，在一些地方 计算机帮助人进行其它原来只属于人类的工作，计算机以它的高速和准确为人类 发挥着它的作用。人工智能始终是计算机科学的前沿学科，计算机编程语言和其 它计算机软件都因为有了人工智能的进展而得以存在。 2 1 2 人工智能的发展过程 人工智能理论进入2 l 世纪，唯酝酿着新的突破人工生命的提出，不仅意 味着人类试图从传统的工程技术途径，而且将开辟生物工程技术途径，去发展人 工智能；同时人工智能的发展，又将作为人工生命科学的重要支柱和推动力量。 可以预言：人工智能的研究成果将能够创造出更多更高级的智能“制品”，并使之 在越来越多的领域超越人类智能；人工智能将为发展国民经济和改善人类生活做 第二章国内外相关技术发展综述 出更大贡献。 著名的英国科学家图灵被称为人工智能之父，图灵不仅创造了一个简单的通 用的非数字计算模型，而且直接证明了计算机可能以某种被理解为智能的方法工 作。1 9 5 0 年，图灵发表了题为计算机能思考吗? 的论文，给人工智能下了一 个定义，而且论证了人工智能的可能性。定义智慧时，如果一台机器能够通过称 之为图灵实验的实验，那它就是智慧的。图灵实验的本质就是让人在不看外型的 情况下不能区别是机器的行为还是人的行为时，这个机器就是智慧的。 后来通过对人脑模型的研究，人们认为人工智能源于仿生学。它的代表性成 果是1 9 4 3 年由生理学家麦卡洛克( m c c u l l o c h ) 并1 3 数理逻辑学家皮茨( p i f l s ) 创立的脑 模型，即m p 模型。6 0 一7 0 年代，联结主义，尤其是对以感知机( p e r c e p t i o n ) 为代 表的脑模型的研究曾出现过热潮，由于当时的理论模型、生物原型和技术条件的 限制，脑模型研究在7 0 年代后期至8 0 年代初期落入低潮。直到h o p f i e l d 教授在 1 9 8 2 年和1 9 8 4 年发表两篇重要论文，提出用硬件模拟神经网络时，联结主义又重 新抬头。i 9 8 6 年鲁梅尔哈特( r u m e l h a r t ) 等人提出多层网络中的反向传播( b p ) 算法。 此后，联结主义势头大振，从模型到算法，从理论分析到工程实现，为神经网络 计算机走向市场打下基础。现在，对人工神经网络的研究热情仍然不减。 9 0 年代，人们逐渐认识到，实现人工智能必须以生物技术、信息技术和新材 料技术三大高科技作为手段。生物技术是“侦察兵”，它负责揭开智能之谜，为人 工智能提供方向；信息技术是主力军，它负责人工方式等模拟人工智能；而新材 料技术是“后勤部队”，为人工智能的实现提供了物质基础。 21 3 人工智能的研究领域 在大多数学科中存在着几个不同的研究领域，每个领域都有其特有的感兴趣 的研究课题、研究技术和术语。在人工智能中，这样的领域包括语言处理、自动 定理证明、智能数据检索系统、视觉系统、问题求解、人工智能方法和程序语言 以及自动程序设计等。今后的人工智能的研究领域将主要体现在以下七个方面： ( 1 ) 问题求解 人工智能的第一个大成就是发展了能够求解难题的下棋( 如国际象棋) 程序。 在下棋程序中应用的某些技术，如向前看几步，并把困难的问题分成一些比较容 易的子问题，发展成为搜索和问题归约这样的人工智能基本技术。今天的计算机 程序能够下锦标赛水平的各种方盘棋、十五子棋和国际象棋。另一种问题求解程 电子科技大学硕士学位论文 序把各种数学公式符号汇编在一起，其性能达到很高的水平，并正在为许多科学 家和工程师所应用。有些程序甚至还能够用经验来改善其性能。 ( 2 ) 逻辑推理与定理证明 逻辑推理是人工智能研究中最持久的子领域之一。其中特别重要的是要找到 一些方法，只把注意力集中在一个大型数据库中的有关事实上，留意可信的证明， 并在出现新信息时适时修正这些证明。对数学中臆测的定理寻找一个证明或反证， 确实称得上是一项智能任务。为此不仅需要有根据假设进行演绎的能力，而且需 要某些直觉技巧。 ( 3 ) 自然语言理解 n l p ( n a t u r a ll a n g u a g ep r o c e s s i n g ) 自然语言处理也是人工智能的早期研究领域 之一，已经编写出能够从内部数据库回答用英语提出的问题的程序，这些程序通 过阅读文本材料和建立内部数据库，能够把句子从一种语言翻译为另一种语言， 执行用英语给出的指令和获取知识等。有些程序甚至能够在一定程度上翻译从话 筒输入的口头指令( 而不是从键盘打入计算机的指令) 。目前语言处理研究的主要 课题是：在翻译句子时，以主题和对话情况为基础，注意大量的一般常识世界 知识和期望作用的重要性。 ( 4 ) 自动程序设计 也许程序设计并不是人类知识的一个十分重要的方面，但是它本身却是人工 智能的一个重要研究领域。这个领域的工作叫做自动程序设计。已经研制出能够 以各种不同的目的描述( 例如输入输出对，高级语言描述，甚至英语描述算法) 来 编写计算机程序。这方面的进展局限于少数几个完全现成的例子。 ( 5 ) 专家系统 一般地说，专家系统是一个智能计算机程序系统，其内部具有大量专家水平 的某个领域知识与经验，能够利用人类专家的知识和解决问题的方法来解决该领 域的问题。也就是说，专家系统是一个具有大量专门知识与经验的程序系统，它 应用人工智能技术，根据某个领域一个或多个人类专家提供的知识和经验进行推 理和判断，模拟人类专家的决策过程，以解决那些需要专家决定的复杂问题。 ( 6 ) 机器人学 人工智能研究日益受到重视的另一个分支是机器人学，其中包括对操作机器 人装置程序的研究。这个领域所研究的问题，从机器人手臂的最佳移动到实现机 器人目标的动作序列的规划方法，无所不包。 ( 7 ) 机器学习和人工神经网络 第二章国内外相关技术发展综述 学习能力无疑是人工智能研究上最突出和最重要的一个方面。人工智能在这 方面的研究近年来取得了一些进展。学习是人类智能的主要标志和获得知识的基 本手段。机器学习( 自动获取新的事实及新的推理算法) 是使计算机具有智能的根 本途径。正如香克f r s h a n k ) 所况：“一台计算机若不会学习，就不能称为具有智能 的。”此外，机器学习还有助于发现人类学习的机理和揭示人脑的奥秘。所以这是 一个始终得到重视，理论正在创立，方法日臻完善，但远未达到理想境地的研究 领域。 人工智能研究己经对计算机技术的各个方面产生并将继续产生较大影响。人 工智能应用要求繁重的计算，促进了并行处理和专用集成片的开发。算法发生器 和灵巧的数据结构获得应用，自动程序设计技术将开始对软件开发产生积极影响。 所有这些在研究人工智能时开发出来的新技术，推动了计算机技术的发展，进而 使计算机为人类创造更大的经济实惠。 2 2 数据挖掘技术发展综述 随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储的 数据量急剧增大，在这些大量的数据背后隐藏着许多重要的信息，如果能把这些 信息从数据库中抽取出来，将为数据的拥有者创造出很多潜在的利润和价值，而 这种从海量数据库中挖掘信息的技术，就称之为数据挖掘。 数据挖掘是从大型数据库或数据仓库中发现并提取隐藏在其中的信息的一种 新技术，目的是帮助决策者寻找数据间潜在的关联，发现被忽略的要素，而这些 信息对预测趋势和决策行为也许是十分有用的。数据挖掘技术涉及数据库、人工 智能、机器学习和统计分析等多种技术。数据挖掘技术能从大型数据库或数据仓 库中自动分析数据，进行归纳性推理，从中发掘出潜在的模式：或者产生联想， 建立新的业务模型，帮助决策者调整市场策略，做出正确的决策。数据挖掘表明： 知识就隐藏在日常积累下来的大量数据之中，而仅仅依靠复杂的算法和推理并不 能发现知识。同时数据挖掘思想也为a i 的发展指出了一个新的研究方向。 数据挖掘是一个利用各种分析工具在海量数据中发现模型和数据间关系的过 程，这些模型和关系可以用来做出预测。 数据挖掘的第一步是描述数据一计算统计变量( 比如平均值、均方差等) ，再 用图表或图片直观的表示出来，进而可以看出一些变量之间的相关性( 比如有一 些值经常同时出现) 。选择正确的数据源对整个数据挖掘项目的成败至关重要，在 9 电子科技大学硕士学位论文 后面数据挖掘的步骤中我们会着重强调这一点。 单单是数据描述并不能为人们制订行动计划提供足够的依据，你必须用你的 这些历史数据建立一个预言模型，然后再用另外一些数据对这个模型进行测试。 一个好的模型没必要与数据库中的数据1 0 0 的相符( 城市交通图也不是完全的实 际交通线路的等比缩小) ，但他在你做决策时是一个很好的指南和依据。 最后一步是验证你的模型。比如你用所有对你的产品推广计划做出回应的人 之数据库做了一个模型，来预测什么样的人会对你的产品感兴趣。 第三章数据挖掘基本原理 第三章数据挖掘基本原理 知识信息处理是实现信息共享和智能化的重要技术。智能系统的迅速发展， 使知识工程成为8 0 年代人工智能发展的主要潮流，将智能系统的开发由手工作业 方式转变为半自动化、自动化的批量生产方式，可提高智能系统开发速度，达到 迅速原型化、逐步结构化、知识工程化，减少系统开发成本，扩大智能系统的应 用范围，提高智能系统的应用水平。 国内外专家普遍认为，知识获取是知识信息处理的关键问题之一。f e i g e n b a u m 在他的名著人工智能对世界的挑战一书中提到：“知识获取是人工智能的一个 长期存在的问题”。上个世纪8 0 年代人们在知识发现方面取得了一定的进展。数 据挖掘和数据库知识发现是上个世纪9 0 年代初期新崛起的一个活跃的研究领域。 数据挖掘是一个多学科交叉领域。一方面，想要以非平j ；l 的方法发现蕴藏在 大量数据集中的有用知识，数据挖掘必须从数据库技术、人工智能、机器学习、 神经网络、统计学、模式识别、知识库系统、知识获取、信息提取、高性能计算 和数据可视化等学科领域汲取营养。另一方面，这些学科领域也要发展，也在从 不同角度关注数据的分析和理解，数据挖掘也为这些学科领域的发展提供了新的 机遇与挑战。数据挖掘广阔的应用前景，引起了学术界和产业界的j 一泛关注。 3 1 知识发现和数据挖掘 知识发现( 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 ，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 e d i s c o v e r ya n d d a t am i n i n g ) 。国外在这方面发表了众多的研究成果和论文，并且开 发了一大批数据挖掘软件，对数据挖掘的研究己成为计算机领域的一个热门课 题。 k d d 是发现知识的完整过程，数据挖掘( d a t am m i n gd m ) 为其中的一个主要 的步骤。图3 - 1 示意了知识发现的主要过程。 数据库中的知识发现具有四个特征，即发现的知识用高级语盲一表示，发现 1 1 电子科技大学硕士学位论文 的内容是对数据内容的精确描述，发现的结果是用户感兴趣的，发现的过程是高 效的。 知识发现的过程主要由以下几个步骤组成： 数报清理( 消除噪声或不一致数据) ； 数据集成( 多种数据源可以组合在一起) ； 数据选择( 从数据库中检索与分析任务相关的数据) ； 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作) ； 数据挖掘( 基本步骤，使用智能方法提取数据模式) ； 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) ： 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 其中，我 们将前4 个步骤统称为数据预处理过程( d a t ap r e p r o c e s s i n g ) 。 图3 1 知识发现的过程 由于在产业界、媒体和数据库领域中，数据挖掘的叫法更为流行，因此，本 文中采用数据挖掘表示数据库中的知识发现过程。本文中使用u f a y y a d 等对数据 挖掘的定义： 定义3 1 ：数据挖掘是从数据集中识别出有效的、新颖的、潜在有用的、并且 最终可理解的模式的非平凡过程。 对于上面数据挖掘的定义需要说明几点： 第三章数据挖掘基本原理 ( 1 ) 定义中涉及的以下几个概念，需要进一步解释。 过程通常指多阶段的一个过程，涉及数据准备、模式搜索、知识评价，以及 反复的修改求精；该过程要求是非平凡的，意思是要有一定程度的智能性、自动 性( 仅仅给出所有数据的总和不能算作是一一个发现过程) 。有效性是指发现的模式 对于新的数据仍保持有一定的可信度。新颖性要求发现的模式应该是新的，以前 未知的。潜在有用性是指发现的知识将来有实际效用，如：用于决策支持系统里可 提高经济效益。最终可理解性要求发现的模式能被用户理解，目前它主要是体现 在简洁性上。有效性、新颖性、潜在有用性和最终可理解性综合在一起可称之为 兴趣。 生( i n t e r e s t i n g n e s s ) 。 通常，我们使用支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 这两个参数来粗略地衡 量挖掘结果的兴趣性。支持度表示满足规则的样本百分比，置信度则是对规则的 蕴涵强度的估计。对于形如x = y 的关联规则，其支持度和置信度可以表示为： s u p p o r t ( x = y ) = p ( x uy ) c o n f i d e n c e ( x = y ) = p ( y ) 习 ( 2 ) 数据挖掘质量的好坏受两个因素的影响： 一是所采用的数据挖掘算法的有效性，二是用于挖掘的数据的质量和数量( 数 据量的大小) 。如果选择了错误的数据或不适当的属性，或对数据进行了错误的转 换，则有可能得到不正确的挖掘结果，即所谓的“g a r b a g ei ng a r b a g eo u t ”。所以， 数据预处理对于数据挖掘来讲也是非常重要，同时，数据预处理也是数据挖掘中 的一个重要研究课题。 ( 3 ) 整个挖掘过程是一个不断重复的过程。 假如用户在挖掘过程中发现选择的属性或数据有偏差，或者使用的挖掘技术 产生不了预期的结果，这时就需要根据反馈结果，不断重复先前的过程，甚至从 头重新开始，最终得到令人满意的挖掘结果。 ( 4 ) 可视化在数据挖掘的各个阶段都扮演着重要的作用。 在数据准备阶段，用户可能要使用散点图、直方图等可视化统计技术来显示 有关数据，以便对数据有一个初步的理解，从而为更好地选取数据打下基础。在 挖掘阶段，用户有可能要使用与领域问题有关的可视化工具，来选择挖掘算法或 者调整挖掘算法的参数。在结果表示阶段，则可能又要用到其它的可视化技术， 以利于用户对挖掘结果的理解。 电子科技大学硕士学位论文 3 2 数据挖掘的任务及主要技术 数据挖掘是从数据中便捷地抽取出以前未知的、隐含的、有用的信息，所挖 掘出来的知识可应用于信息管理、决策支持、过程控制和其它许多应用。确切地 讲，数据挖掘是一种决策支持过程，它主要基于人工智能、机器学习、统计学技 术，高度自动化地分析企业原有的数据，作出归纳性的推理，从中挖掘出潜在的 模式，预测客户的行为，帮助企业的决策者调整市场策略，减少风险，作出正确 的决策。 科学数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。科 学数据挖掘的目标是从目标数据库中发现隐含的、有意义的知识，主要有以下五 类任务： ( 1 ) 自动预测趋势和行为 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析 的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测问题， 数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它可预 测的问题包括预报破产以及认定对指定事件最可能做出反应的群体。 ( 2 ) 关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量 的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因 果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中 数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。 ( 3 ) 聚类 数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们 对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统 的模式识别方法和数学分类学。8 0 年代初，m c h a l s k i 提出了概念聚类技术及其要 点是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵 描述，从而避免了传统技术的某些片面性。 ( 4 ) 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概 念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述 不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的 共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 1 4 第三章数据挖掘基本原理 ( 5 ) 偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏 差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与 模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结 果与参照值之间有意义的差别。 其实现技术主要有以下几类： ( 1 ) 决策树的技术 大部分数据挖掘工具采用规则发现或决策树分类技术来发现数据模式和规 则，其核心是某种归纳算法。这类技术通常是对数据库的数掘进行开采，生产规 则和决策树，然后对新数据进行分析和预测。这类技术的主要优点是，规则和决 策树都是可读的。 ( 2 ) 基于距离，密度，网格的聚类分析技术 聚类分析技术是科学数据挖掘中的核心技术之一，它是一种在无导师的情况 下，根据样本数据间的相似程度进行自动分类的技术，这类技术不需要事先知道 数据内部结构，只要给出聚类的规则，它可以自己发现数据内部的规则和数据之 间的联系。聚类有时直接满足用户的需要，有时是其它发现过程的“预处理”。 聚类分析已经广泛地用在许多应用中，包括模式识别，数据分析，图象处理，以 及市场研究。 ( 3 ) 基于神经网络的技术 由于对非线性数据的快速建模能力，基于神经网络的数据挖掘技术现在越来 越流行。其开采过程基本上是将数据聚类，然后分类计算权值。神经网络很适合 非线性数据和含噪声数据，所以在市场数据库的分析和建模方面应用广泛。 ( 4 ) 基于模糊逻辑的技术 其发现方法是应用模糊逻辑进行数据查询、排序等。该技术使用模糊概念和 “最近”搜索技术的数据查询工具，它可以让用户指定目标，然后对数据库进行 搜索，找出接近目标的所有记录，并对结果进行评估。 ( 5 ) 综合多方法技术 不少数据挖掘技术采用了多种开采方法，这类技术一般很复杂，适于大型数 据库包括并行数据库。这类技术开采能力很强，但代价很大，要花很长时间进行 学习。 电子科技大学硕士学位论文 3 4 数据挖掘的应用 由于数据挖掘带来的显著的经济效益，使数据挖掘越来越普及。数据挖掘可 以应用在各个不同的领域。电讯公司和信用卡公司是用数据挖掘检测欺诈行为的 先行者。保险公司和证券公司也开始采用数据挖掘来减少欺诈。医疗应用是另一 个前景广阔的产业：数据挖掘可以用来预n # i - 科手术、医疗试验和药物治疗的效 果。零销商更多的使用数据挖掘来决定每种商品在不同地点的库存，通过数据挖 掘更灵活的使用促销和优惠卷手段。制药公司通过挖掘巨大的化学物质和基因对 疾病的影响的数据库来判断哪些物质可能对治疗某种疾病产生效果。 随着各种传感器使用的越来越普遍，数据分析技术很早以前就已经用来对科 学和工程数据进行分析。近来，计算仿真的复杂过程正以越来越不可预料的速度 向前迈进，并且数据的存储能力也得到了历史上从未有过的提高，由此科学试验 产生亿万字节的数据集已经变得很平常。这些导致了数据挖掘技术领域的革新， 同时也带来了很多新的挑战和难以解决的问题。 由于来自视频和计算机仿真的数据大多是带有时间、空间信息的高维序列， 因此如何对其进行低耗有效的分析而得到科学家们想知道的信息，是我们需要解 决的一个重要问题。科学数据挖掘，或称“从科学仿真数掘库中发现知识”，是 指从科学实验仿真时得到的数据库