（计算机应用技术专业论文）大规模科学数据挖掘中密度聚类算法的研究.pdf

摘要 摘要 数据挖掘就是从海量数据中提取知识，又被称为数据库中的知识发现。它是 一个跨学科的薪兴研究领域。聚类分析是其中的一个重要公支，它研究数据间逻 辑上或物理上的相互关系，通过一定的规则将数据集划分为在性质上相似的数据 点构成的若于个类。 本文首先介绍了数据挖掘的基本概念、存在问题及发展方向。其次介绍了聚 类分析的基本概念、分类及一些常见的算法思想，并着重讨论了一些经典的聚类 算法。 基于密度的聚类算法是本文的重点研究对象。研究表明，大多数基于密度的 聚类算法需要输入初始参数，参数通常由用户根据经验给出，这往往是困难的。 且密度参数通常简单的将聚类分为高低密度两种，无法反映整体数据的分布特点。 为了解决此类算法面临的问题，本文提出一种基于密度与网格聚类算法相结合的 自适应式聚类算法，它首先对数据进行网格化，然后分析网格的密度分布，从而 自适应的得出一系列密度区间，这些区间的划分进而作为聚类的参数。这样的区 间划分不再是简单的高低密度分界，而是反映了数据分布的特点。 数据挖掘与科学研究的结合是近来新兴的研究课题，在很多方面都有值得研 究的地方。大规模科学数据具有数据量大、特征复杂的特点，在对其进行处理时， 往往使得理解，分析这些科学数据，并从中获取知识变得十分困难，由此科学数 据挖掘势在必行。 本文对科学数据挖掘项目及其科学仿真数据进行了介绍。并且将所提出的自 适应式网格密度聚类算法应用于科学仿真数据。并对聚类结果进行聚类特征的分 析提取，提取的聚类特征表示了数据的整体物理变化过程。 在本文的最后对全文内容进行总结，并展望了数据挖掘进一步研究和应用的 方向。 关键词：数据挖掘；科学数据；聚类分析；密度：网格 a b s t r a c t d a t am i n i n g , a l s ok n o w na sk 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 i s t i l l sk n o w l e d g e f r o mam a s so fd a t a i ti san e wr e s e a r c ha r e ai n v o l v i n gs e v e r a lb m n c h e so fm a c h i n e l e a r n i n ga n dc o n t a i n i n gm a n yd o m a i n s c l u s t e ra n a l y s i si so n eo ft h em o s ti m p o r t a n t d o m a i n sa m o n gt h o s eo fd a t am i n i n g , w h i c hr e s e a r c h i n gl o g i c a lo rp h y s i c a lm u t u a l r e l a t i o nb e t w e e nd a t a , a n dd i v i d ed a t as e t si n t os e v e r a lc l u s t e r st h r o u g hc e r t a i nr o l e s , t h e s ed u s t e r sc u n s t i t u t eb yd a t ap o i n t sw h i c hs i m i l a ri nu a t u r e i nt h eb e g i n n i n go ft h i st h e s i ss o m eb a s i cp r i n c i p a lt h e o r i e s ，a p p r o a c h e sa n d p r o b l e m so fd a t am i n i n ga r ei n t r o d u c e d , f o l l o w e db yc o n c e p t i o n s ，c a t e g o r i e sa n d g e n e r a lt h o u g h t so fp o p u l a ra l g o r i t h m sa b o u to u s t e ra n a l y s i s af e wc l a s s i cc l u s t e r a l g o r i t h m sa r ed e e p l yd i s c u s s e d t h em a i no b j c c to fr e s e a r e hi nt h i sp a p e ri st h ed e n s i t y - b a s e dc l u s t e r i n ga l g o r i t h m r e s e a r c hs h o w st h a tm o s to fd e n s i t y - b a s e dc l u s t e r i n ga l g o r i t h mu e e d si n p u ti n i t i a l p a r a m e t e r s , w h i c ha r eu s u a l l yb a s e do nt h eu s e re x p e r i e n c e , t h i si sd i f f i c u l t i na d d i t i o n , d e n s i t yp a r a m e t e r sa r eu s u a l l ys i m p l yd i v i d e sc l u s t e r si n t oh i g h - d e n s i t yd u s t e r sa n d l o w - d e n s i t yc l u s t e r s , s ot h e yc a n n o tr e f l e c tt h eo v e r a l ld a t ad i s t r i b u t i o n i no r d e rt o s o l v es u c hp r o b l e m sf a c e db yt h e s ea l g o r i t h m s ，t h i sp a p e rp r e s e n t sas e l f - a d a p t i v e c l u s t e r i n ga l g o r i t h mb a s e d0 1 1d e n s i t ya n dg r i d d i n g f i r s t , i tb u i l d s 鲥d sf o rd a t a , t h e n a n a l y z e st h ed e n s i t yd i s t r i b u t i o no ft h e s e 鲥d s ，t h u sg e t sas e r i e so fd e n s i t yi n t e r v a l s s e l f - a d a p t i v e l y , t h e s ei n t e r v a l s a r eu s e da sc l u s t e r i n gp a r a m e t e r s ，a n dt h e ya r en ol o n g e r as i m p l eb o u n d a r yb e t w e e nh i g hd e n s i t ya n dl o wd e a s i 哆c l u s t e r s , b u tr e f l e c t st h e d i s t r i b u t i o no fd a t a t h ec o m b i n a t i o no fd a t am i n i n ga n ds c i e n t i f i cr e s e a r c hi sar e l a t i v e l yn e ws u b j e c t , a n di ti sw o r t hr e s e a r c h i n gi nm a n ya s p e c t s l a r g e s c a l es c i e n t i f i cd a t ah a v ei t su n i q u e c h a r a c t e r i s t i c s ，s u c ha sh u g ed a t aq u a n t i t i e sa n dc o m p l i c a t e df e a t u r e s ，w h i c hu s u a l l y m a k e si td i f f i c u l tt ou n d e r s t a n d ，a n a l y z ea n de x t r a c tk n o w l e d g ef r o mt h e m t h u s ， s c i e n t i f i cd a t am i n i n gi si m p e r a t i v eu n d e rt h es i t u a t i o n i nt h i sp a p e r , t h es c i e n c ed a t a - m i n i n gp r o j e c ta n ds c i e n t i f i cs i m u l a t i o nd a t aa r e p r e s e n t e d ，a n dt h es e l f - a d a p t i v ed e n s i t y - b a s e da n dg r i d d i n g b a s e dc l u s t e r i n ga l g o r i t h m i su s e df o rt h es c i e n t i f i cs i m u l a t i o nd a t a t h e nt h ep a p e ra n a l y s e sa n de x t r a c tt h e c l u s t e r i n gf e a t u r e so fc l u s t e r i n gr e s u l t s , t h e s ec l u s t e r i n gf e a t u r e si n d i c a t e dt h eo v e r a l l p h y s i c a lp r o c e s so f t h e d a t 如 a b s t r a c t i nt h el a s tp a r to ft h et h e s i s ，t h ec o n c l u s i o na n dp r o s p e c to fd a t am i n i n gr e s e a r c h a n da p p l i c a t i o ni sg i v e n k e yw o r d s - d a t am i n i n g ；s c i e n t i f i cd a t a ；c l u s t e ra n a l y s i s ；d e n s i t y - b a s e d ； g r i d - h a s e d m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名g日期：2 0 0 7 年4 月2 4 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：经尘：毛导师签名： 堕亟 第一章绪论 1 1 研究背景 第一章绪论 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，不计其 数的数据库被用于商业管理、政府办公、科学研究和工程开发等领域，这一势头 仍将持续发展下去。但是，现代化的数据库技术虽然能够经济、高效地储存、检 索与管理这些信息数据流，但却缺乏必要的技术来帮助我们分析、理解甚至是将 这些数据可视化地表达出来。在如此大量的数据背后隐藏了很多具有决策意义的 信息，怎样才能得到这些“知识”昵? 于是，一个新的挑战摆在我们面前：在这 信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何才能不被信息的 汪洋大海所淹没，而是从中及时发现有用的知识，提高信息利用率呢? 要想使科 学实验数据真正地为科研服务，只有充分对其进行分析、挖掘，帮助科研工作者 发现以前不能发现的问题，找出以前不能找出的规律。要想使数据真正成为一个 公司的资源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则 大量的数据反而可能成为包袱，甚至成为垃圾。因此，面对“人们被数据淹没， 却饥饿于知识”的挑战，数据挖掘和知识发现技术应运而生，并得以蓬勃发展， 越来越显示出其强大的生命力从技术层面上来看，数据挖掘是利用多种分析手 段【1 2 ，3 】( 基于机器学习、统计学习、神经网络、数据库系统、信息科学等技术) 从海 量数据中发现其中的模式。从应用层面看，数据挖掘是决策支持过程，运用各种 技术分析企业商务数据，为企业提供正确市场预测、销售组合、客户分析等支持。 在科学研究领域，技术的革新使科学家能够以不断增加的速度，从试验、仿 真及观测中收集数据，数据容量从近来的百万字节到现在的千兆字节，并且不久 就将达到万亿字节。我们产生数据的能力已经远远超过了我们对它们的研究、分 析和理解的能力，并且经常收集的可利用的复杂数据都是图像或者时间序列。为 了实现我们的科学目标，我们需要通过从这些数据中提取有用的信息来充分的对 它们进行知识开采。可不幸的是，在许多科学领域中数据的尺度范围如此之大、 复杂度如此之高，以至于使用人工来对它们进行分析、研究和理解完全是不切实 际的。科学家们几乎不可能通过手工的方式来发现各数据源之间的潜在联系。这 导致的结果是，有用的信息经常被忽视掉，并且增强了的计算能力和数据搜集能 电子科技大学硕士学位论文 力的潜在优势只能部分发挥出来。这迫切需要研究出与此对应的新的数据挖掘技 术及其挖掘工具来解决此类问题。为了解决这个问题，我们应用并扩展了数据挖 掘领域的方法，开发了新的科学数据挖掘技术，希望能够提高科学家与大规模、 高维度、时变的科学数据之间的交互性。这些技术能够帮助我们自动地在数据中 进行模式识别，并且使科学家们能够以交互方式对感兴趣的某些领域的数据进行 知识开采。 目前，国外对数据挖掘技术的研究比较多，但专门针对科学数据的研究非常 少。国内此领域的研究处于初步的起始阶段，成熟的研究成果基本空白。现在科 学仿真数据和实验数据越来越多、越来越复杂，给表示、存储、理解、分析和可 视化带来了困难。目前，国外已有不少的科学数据格式标准，如c d f 、n e t c d f 、 h d f 5 等，也相应地诞生了各种各样的科学数据管理系统，它们给科学数据的存储 和管理带来了方便。对于模拟数据，常常以网格( m e s h ) 形式表示，通用的格式系统 如上述三种数据格式系统均支持网格数据( m e s hd a t a ) 的存储和处理。尽管如此， 要理解、分析这些数据，并从中获取知识仍是不易。科学数据集有其本身的特性， 如数据的时空相关性，使得现有的数据挖掘技术不能够完全适应这种特性，又如 数值模拟科学数据具有特征互相交错、复杂、难于抽取，数据维数高、数据集大、 运算效率低等特性，利用传统的数据挖掘算法进行知识发现执行效率低下，且效 果较差。因此将数据挖掘的技术与科学研究结合起来，进行科学数据挖掘势在必 行 科学数据内在结构和应用上的特点，使得科学数据挖掘不但具有很高的应用 价值，同时也具有显著的理论研究价值。对科学数据的挖掘在方法的研究和应用 上都具有空前的挑战性和驱动力。如何对数值模拟的海量数据进行分析? 如何智 能地从中获取科学家们感兴趣的有益信息? 如何从已知的海量数据去分析其间的 相互关联、预测未知信息及趋势? 这些都是我们在研究中需要克服的困难和关键 问题。因此。我们将考虑新的适用解决方案，以解决科学数据挖掘中不同于商业 和传统数据挖掘中的特征析取和数据融合等问题 4 , 5 , 6 1 。 1 2 数据挖掘的发展及研究状况 早在八十年代，人们就估算全世界的数据总量2 0 个月就会翻一番，进入九十 年代后，数据量会增长得更快。在这样的数据增长速度下，。信息爆炸”和“数据 2 第一章绪论 过剩”成为了当今数字化社会面临的巨大挑战。 进入九十年代后，数据库技术的一个新领域数据仓库( d a t aw a r e h o u s e ) 以 及人工智能领域中的一个分支一机器学( m a c h i n el e a r n i n g ) 的研究取得了很大 进展。在这两门学科的相互融合下，数据库中的知识发现( 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 e ，k d d ) 及其核心技术数据挖掘就这样应运而生了数据库技术的日 益成熟和数据仓库的发展为知识发现和数据挖掘提供了发挥的平台，而机器学习 又为数据挖掘提供了大量的方法。因此，知识发现和数据挖掘是应用需求推动下 跨学科发展的产物i “。 目前，知识发现不仅被许多研究人员看作是数据库系统和机器学习方面一个 重要的研究课题。而且被许多工商界人士看作是一个能带来巨大回报的重要领域。 1 9 8 9 年8 月在美国底特律的第1 1 届国际人工智能联合会议的专题讨论会上召 开了第一届k d d 的w o r k s h o p ，1 9 9 1 、1 9 9 3 和1 9 9 4 年又接着举行k d d 专题讨论 会。 1 9 9 5 年，在加拿大蒙特利尔召开了第一届知识发现和数据挖掘学术会议，数 据挖掘一词随即流行开来。此后每年都举办一次k d d 国际会议。从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 1 9 9 5 年以 来，国外在知识发现和数据挖掘方面的论文非常多，已形成了热门研究方向。n 1 3 聚类分析研究及应用状况 聚类分析【_ 硼是研究数据问逻辑上或物理上的相互关系的技术，它通过一定的 规则将数据集划分为在性质上相似的数据点构成的若干个类。聚类分析的结果不 仅可以揭示数据问的内在联系与区别，同时也为进一步的数据分析与知识发现提 供了重要的依据，如数据间的关联规则，分类模式以及数据的变化趋势等。作为 统计学的重要研究内容之一，聚类分析具有坚实的理论基础并形成了系统的方法 学体系唧，然而，基于统计学的聚类分析方法大多局限于理论上的分析并依赖于对 数据分布特征的概率假设，较少考虑具体应用中的实际数据特征与差异。由于数 据挖掘技术的迅速崛起，聚类分析得以在数据库技术领域获得长足的发展 1 0 , l x a 2 l 。 电子科技大学硕士学位论文 1 4 作者所做工作及本文内容安排 1 4 1 作者所做工作 作者目前主要研究密度聚类算法以及各种数据挖掘方法在科学数据挖掘中的 应用，这一题目涉及到数据挖掘与领域科学研究的结合，具有显然的科学意义和 很高的应用价值。作者所做工作可概括为以下几个方面： 1 通过查阅国内外大量相关技术文献，在了解各种数据挖掘技术的基础上，针对 大规模科学数据集研究数据挖掘技术，确定了数据挖掘试验平台的流程设计和 采掘方案； 2 在分析比较数据挖掘的各种方法基础上，选定基于密度聚类算法进行深入研 究，并根据研究项目数据的需求情况，提出一种网格与密度思想相结合的聚类 算法； 3 对项目中的l a r e d p 数据应用所提出的聚类算法进行聚类特征的提取；并对提 取的聚类特征进行分析。 4 将整体处理过程整合成统一的数据挖掘平台，并以可视化的展示各项处理结 果，供物理研究人员分析。 1 4 2 本文内容安排 第1 章回顾了数据挖掘相关技术的发展历史和研究现状，介绍了本课题的 研究背景、研究内容以及论文章节安排。 第2 章介绍和分析了数据挖掘的相关技术及应用领域。 第3 章介绍了聚类算法的基础知识。 第4 章对现有的基于密度的聚类算法进行分析，并结合现有项目的实际需 求，提出一种基于统计的网格密度聚类算法，并分析了该算法的特点。 第5 章介绍了所研究科学数据挖掘项目的背景，将提出的聚类算法在该项 目上的应用进行了展示，并分析了应用效果。 第6 章总结了本文所述研究方向中存在的闯题及进一步发展的方向。 4 第一二章数据挖掘概述 第二章数据挖掘概述 在传统的决策支持系统中，知识库中的知识和规则是由专家或程序人员建立 的，是由外部输入的。而数据挖掘的任务是发现大量数据中尚未被发现的知识， 是从系统内部自动获取知识的过程。对于那些决策者明确了解的信息，可以用查 询、联机分析处理( o n l i n ea n a l y t i c a lp r o c e s s i n g ，简写为o l a f ) 或其它工具直接获 取；而另外一些隐藏在大量数据中的关系、趋势，即使是管理这些数据的专家也 是没有能力发现的，这些信息对于决策可能又是至关重要的，这类问题就可以用 数据挖掘来解决。 数据挖掘指的是从大型数据库或数据仓库等数据存贮中提取人们感兴趣的知 识。这些知识是隐含的、事先未知的潜在有用的信息。数据挖掘是目前国际上数 据库和信息决策领域的最前沿研究方向之一。 数据挖掘技术作为一种重要的商业决策技术已经越来越受到国际上的重视， 并成为企业界研究的一个热点。例如，电讯企业通过分析用户登录记录来识别线 路故障；保险公司在制定新的保险项目时通过历史记录来预测某项投保的风险性； 超市通过分析购买记录来做出能够促进销售的经营策略等等，无一不用到数据挖 掘的方法。 数据挖掘发现的知识可以直接提供给决策者，用以辅助决策过程，或者提供 给领域专家，修正专家已有的知识体系，也可以作为颓的知识转存到应用系统的 知识存储机构中，比如专家系统规则库等。 数据挖掘是一个多学科交叉领域，涉及到机器学习、模式识别、统计学、智 能数据库、知识获取、数据可视化、高性能计算、专家系统等多个领域。数据挖 掘的成果可以用在信息管理、过程控制、科学研究、决策支持等许多方面。 2 1 数据挖掘的定义 当今数据库的容量已经达到万亿字节f m , 1 0 1 2 b y t e ) 的水平。在如此大量数据 的背后隐藏了很多具有决策意义的信息，那么怎么从数据中得到这些“知识”? 怎样通过一棵棵的树木了解到整个森林的情况? 计算机科学对这个问题给出的最新回答就是：数据挖掘。数据挖掘技术在“数 5 电子科技大学硕十学位论文 据矿山”中寻找蕴藏的“知识金块”，帮助企业减少不必要投资的同时提高资金回 报。数据挖掘给企业带来的潜在的投资回报几乎是无止境的。世界范围内具有创 新性的公司都开始采用数据挖掘技术来判断哪些是他们的最有价值客户，重新制 定他们的产品推广策略( 把产品推广给最需要的人) ，希望以最小的花费得到最好的 销售结果。 数据挖掘是一个逐渐演变的过程。在计算机数据处理的初期，人们就试图通 过某些方法来实现自动决策支持，当时机器学习成为人们关心的焦点。机器学习 的过程就是将一些己知的并已被成功解决的问题作为范例输入计算机，机器通过 学习这些范例总结并生成相应的规则，这些规则具有通用性。使用它们可以解决 某一类的问题。随着神经网络技术的形成和发展，人们的注意力转向知识工程， 知识工程不同于机器学习那样给计算机输入范例，让它生成规则，而是直接向计 算机输入已被代码化的规则，而计算机则通过使用这些规则来解决某些问题。专 家系统就是这种方法所得到的成果，但它有投资大、效果不甚理想等不足。踯年 代人们又在新的理论指导下，重新回到机器学习的方法上，并将其成果应用于大 型商业数据库的处理。在踯年代末一个新的术语数据库中的知识发现0 d d k n o w l e d g ed i s c o v e r yi nm 妇b a 1 出现了，它泛指所有从源数据中发掘模式或联系 的方法。人们接受了这个术语，并用k d d 来描述整个数据发掘的过程，包括最开 始的制定业务目标到最终的结果分析，而用数据挖掘( d a 纽m i n i n g ) 来描述使用挖掘 算法进行数据挖掘的子过程。但最近人们却逐渐开始发现数据挖掘中有许多工作 可以由统计方法来完成，并认为最好的策略是将统计方法与数据挖掘有机的结合 起来。 数据挖掘( d a t am n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的 实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信 息和知识的过程。 这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现 的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现 放之四海皆准的知识，仅支持特定的发现问题。与数据挖掘相近的同义词有数据 融合、数据分析和决策支持等。 何为知识? 从广义上理解，数据、信息也是知识的表现形式，但是人们更愿 意把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的 源泉，如同从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库 中的数据；也可以是半结构化的，如文本、图形和图像数据：甚至是分布在网络 6 第一二章数据挖掘概述 上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演 绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持 和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科， 它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决 策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人 工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员， 投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发 现全新的自然科学定理和数学公式，更不是什么机器定理证明。实际上，所有发 现的知识都是相对的，是有特定前提和约束条件、面向特定领域的，同时还要能 够易于被用户理解。最好能用自然语言表达所发现的结果。 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是数据 挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息 应具有先前未知、有效与可使用三个特征其中先前未知的特征是指该信息是预 先未曾预料到的，即数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至 是违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越有价值。 2 2 数据挖掘的功能 利用数据挖掘技术可以获得多种知识，在许多情况下，用户并不知道数据厍 中存在哪些有价值的知识，因此一个数据挖掘系统应该能够同时发现多种模式的 知识，以便满足用户的需要。下而介绍一下数据挖掘的功能。 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般 可以分为两类：描述和预测。描述性挖掘要刻画数据库中数据的一般特性：预测 性挖掘在当前数据上进行推理，来进行预测 1 概念描述：定性与对比 通过对含有大量数据的数据集进行概述性的总结，可以获得简明、准确的描 述，这种描述就称为概念描述。获得概念描述的方法主要有以下三种： 1 1 利用更为广义的属性，对所分析的数据进行概要总结，被分析的数据称为 目标数据集； 将所分析的两类数据的特点进行对比，并对对比结果进行概要总结，这两 7 电子科技大学硕七学位论文 类数据分别称为目标数据集和对比数据集。 3 1 数据特征化和比较。 2 关联分析 关联规则基于数据项的同时出现特征从数据库中发现项或属性间事先未知且 隐藏的有趣联系，关联规则挖掘问题是r a g r a w a l 等人于1 9 9 3 年在文献【黻1 素定卫书簦i 中首先提出来的。一个典型的关联规则的例子就是：在超市中，9 0 的顾客在购买 面包和黄油的同时也会购买牛奶，其直观的意义是顾客在购买某种商品时有多大 的倾向会也购买另外一些商品。这样的规则对于企业确定生产销售、产品目录、 产品排放、市场分析以及市场营销策略等多方面都是很有价值的。 3 分类和预测 分类和预测是两种数据分析形式，它们可用于抽取能够描述重要数据集和预 测未来数据趋势的模型。分类方法用于预测数据对象的离散类别，预测方法用于 预测数据对象的连续取值。机器学习、专家系统、统计学和神经生物学等领域的 研究人员已经提出了许多具体的分类预测方法。数据分类过程主要包含两个步骤。 第一步是建立一个描述己知数据集类别的模型，该模型通过对数据库中各数据对 象内容的分析获得。它是在已知训练样本类别的情况下，通过学习建立相应的模 型。通常分类学习所获得的模型可以表示为分类规则形式、决策树形式和数学公 式形式。第二步是利用所获得的模型进行分类操作。经过评估，如果模型的分类 准确率是可以接受的，那么就可以使用这一模型对未来的数据对象进行分类。与 分类学习方法相比，预测方法可以认为是对未知类别数据对象的类别取值，利用 学习所获得的模型进行预测。目前分类与预测方法己被广泛应用于各行各业，如 信用评估、医疗诊断、性能预测和市场营销等应用领域。 4 聚类分析 根据对象之间的相似程度，将一群对象分为若干组的过程就是聚类过程一 个聚类就是由彼此相似的一组对象所构成的集合，不同聚类中的对象通常是不相 似的。聚类分析就是从给定的数据集中搜索数据对象之间所存在的有价值的联系 在许多应用中，一个聚类中所有对象常常被当作一个对象进行处理，聚类分析己 被应用于模式识别、数据分析、图象处理和市场分析等领域。聚类分析与分类预 测方法的区别在于两者的学习方法不同，前者是无监督的学习方法，后者属于有 监督的学习方法。详见第三章。 5 孤立点分析 与其它数据不一致或非常不同的数据就称为孤立点数据。大部分挖掘将孤立 b 第二章数据挖掘概述 点视为噪声或异常而丢弃了，但在一些应用场合，如各种商业欺诈行为的自动检 测，小概率事件往往比经常发生的事件更有价值。对孤立点的分析处理通常称为 孤立点挖掘。它的用途很广，例如，它可以用于欺诈检测，即监测信用卡使用或 电信服务中的异常行为；还可以用于市场分析，即通过分析花费较小或较高顾客 的消费行为制定营销策略。 6 演变分析 演变分析就是对随时间变化的数据对象的变化规律进行描述并建模。这类分 析包括时间序列数据分析、序列或周期模式匹配和基于近似性的数据分析。倒如， 利用演化分析方法，我们可以分析股票市场上主要股票的交易数据，获得整个股 票市场的股票演化规律。这样，我们能够准确地预测股票市场上的股票价格，提 高投资回报率。 2 3 数据挖掘的工作流程 数据挖掘中的工作流程大体内容如下： 1 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要步骤。挖掘 最后生成的结果是不可预测的，但要探索的问题应是有预见性的为了数据挖掘 而数据挖掘则带有盲目性，是不会成功的 2 数据准备 1 ) 数据的选择：搜集所有与业务对象有关的内部和外部数据信息，并从中选 择出适用于数据挖掘应用的数据。 劲数据的预处理：研究数据的质量，为进一步的分析做准备。并确定将要进 行的挖掘操作的类型。 数据的转换：针对挖掘算法将数据转换成一个分析模型。建立一个真正适 合挖掘算法的分析模型是数据挖掘成功的关键。 3 数据挖掘 对经过转换的数据进行挖掘。选择合适的挖掘算法是数据挖掘的关键，其余 一切工作都能自动地完成。 4 结果分析 解释并评估结果。其使用的分析方法一般应视数据挖掘操作而定，通常会用 到可视j 匕技术。 9 电子科技大学硕士学位论文 5 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 数据挖掘的工作流程如图2 - 1 所示。 图2 - 1 数据挖掘工作流程图 需要注意的是，数据挖掘的工作流程不是固定的，需要按照具体应用进行剪 裁，添加必要的处理步骤。而去掉无意义、不需要或价值不大的步骤，否则投入 的资源就不能得到充分的回报。 2 4 数据挖掘的主要方法 数据挖掘的方法很多，每种方法都有其特定适用领域。某一种方法不可能胜 任所有的数据挖掘任务，一个复杂的数据挖掘系统常常采用多种数据挖掘方法， 通过整合多种数据挖掘方法来弥补单个数据挖掘方法所存在的不足。数据挖掘的 方法主要有以下几种： 1 基于决策树的方法 决策树也称为判定树，它是用于分类和预测的主要方法之一。决策树技术发 现数据模式和规则的核心是归纳算法。它的目的是根据某个新记录的属性，将其 分派到预先定义好的若干类中的一个，并为其添加一个字段以标识该记录的类别。 构建决策树的算法很多，其中最具代表性的是c a r t 和c 4 5 算法。它们的算法思 想大致如下： 将给定训练集作为决策树的根结点，训练集中的记录具有标识类别的字段， 第二章数据挖掘概述 利用信息增益来寻找结点上具有最大信息量的字段，根据对该字段的不同取值建 立该结点的若干分支，并为所有分支子集建立对应的结点。在每个分支子集中重 复建立下层分支和结点，直到结点中所有记录的类别都相同为止，这样便生成了 一棵完整的决策树。因为完整的决策树不利于分类和预测，因此还要对该决策树 进行剪枝处理，产生最终的决策树。然后把决策树的结点分裂过程转化为 “i f t h c n ”的规则，利用这些规则就可以对新数据进行分类。 决策树方法在许多应用领域被广泛地应用，其主要优点有： 第一，生成的规则容易理解：决策树产生的规则能够轻易地转化为 “i f t h e n ”这种形式的关联规则，也可以被翻译成自然语言或s q l 语句；而且 决策树模型的建立过程也比较直观。 第二，决策树进行分类时所需的计算量不大。 第三，决策树既支持离散数据也支持连续数据。 第四，决策树的输出包含属性的排序：决策树能够清楚地指出哪一个数据域 对决策是最重要的。 当然，决策树方法也存在着一定的不足，例如训练一棵决策树的耗费很大， 对具有连续值的属性预测比较困难。在类过多的情况下分类容易出错等。 2 基于神经网络的方法 神经网络最早是由心理学家和神经生物学家提出的神经网络是大量的简单 神经元按一定规则连接构成的网络系统，这种网络能够模拟人类大脑的结构和功 能，采用某种学习算法从训练样本中学习，并将获取的知识存储在网络各单元之 间的连接权中。神经网络和基于符号的传统人工智能技术相比，具有直观性、并 行性和抗噪声等优点。目前已出现了多种网络模型和学习算法，主要用于分类、 优化、模式识别、预测和控制等领域。在数据挖掘领域，主要采用前向神经网络 提取分类规则。从网络中提取规则，主要有下述两种方向： 1 ) 网络结构分解的规则提取。它以神经网络的隐层结点和输出层结点为研究 对象，把整个网络分解为许多单层子网的组合。通过研究较简单的予网，便于从 中挖掘知识。k t 算法是有代表性的方法，但其缺点是通用性差，并且当网络比较 复杂时算法的复杂性高，容易产生组合爆炸问题。所以，对于大规模网络，此类 算法在提取规则前，需要对网络结构进行剪枝和删除冗余结点等预处理工作 2 ) 由神经网络的非线性映射关系提取规则。这种方法直接从网络输入和输出 层数据入手，不考虑网络的隐层结构，避免了基于结构分解的规则提取算法的不 足。s e s f i t o 等人的相似权值法是一个典型的算法 1 1 电子科技大学硕士学位论文 在数据挖掘领域，神经网络的规则提取还存在许多问题，如进一步降低算法 的复杂度、提高所提取规则的可理解性、提取规则的评估标准、在训练中从神经 网络动态提取规则从而及时修正神经网络并提高神经网络性能等。 3 基于遗传算法的方法 遗传算法利用了自然进化的思想，最早由h o l l a n d 于2 0 世纪7 0 年代提出。 遗传算法包括选择，交叉和变异三个基本算予。首先，创建一个随机产生的规则 组成的初始群体。每个规则可以用一个二进位串表示；然后，根据适者生存的原 则，形成由当前群体中最适合的规则组成的新的群体，以及这些规则的后代，一 般用规则的适应度来对训练样本集的分类准确率进行评估；第三，通过使用交叉 和变异等遗传操作来创建后代。在交叉操作中，通过来自规则对的子串交换，形 成新的规则，在变异操作中，反转规则串中随机选择的位。由先前的规则群体产 生新的规则群体的过程迭代进行，直到p “进化”，p 中每个规则满足事前指定的 适应度阀值。 在应用遗传算法进行数据挖掘时，需要把数据挖掘任务表达为一种搜索的问 题，以便发挥遗传算法的搜索能力。它是基于群体的、具有随机和定向搜索特征 的迭代过程， 4 贝叶斯方法 贝叶斯网络是由r h o w a r d 和j m a t h e s o n 于1 9 8 1 年提出的，它是一种概率推 理方法，它能从不完全、不精确和不确定的知识和信息中做出推理，可以处理不 完整和带有噪音的数据集，解决数据间不一致和相互独立的问题。贝叶斯分类是 统计学分类方法，它可以预测类成员关系的可能性。比较简单的朴素贝叶斯方法 是一种基于概率的分类方法，它通过样本的属性值计算样本属于某一个类的可能 性，然后，将样本归属到最有可能的类中朴素贝叶斯分类在应用于大型数据库 时，表现出高准确率和高速度。 5 基于粗糙集的方法 粗糙集作为一种软计算方法，它可以不需任何辅助信息，如统计学中的概率 分布、模糊集中的隶属度等，仅依据数据本身提供的信息就能对数据进行化简并 求得知识的最小表达。粗糙集方法可以克服传统的不确定信息的处理方法的不足， 并且能和它们有机结合，进一步增强对不确定、不完全信息的处理能力。粗糙集 方法首先用近似的方法把信息系统中的属性值离散化，然后对每一个属性划分等 价类，再利用集合的等价关系进行信息系统的属性约简，最后得到一个最小决策 关系，便于获得规则。目前成熟的关系数据库管理系统和新发展起来的数据仓库 第二章数据挖掘概述 管理系统为基于粗糙集的数据挖掘奠定了坚实的基础。 2 5 数据挖掘的应用 目前国际上数据挖掘技术在科学研究、金融投资、市场营销、保险、医疗卫 生、产品制造业和通信网络管理等行业已得到广泛应用；国内在数据挖掘方面也 有成功的应用，例如宝钢已应用数据挖掘系统辅助生产决策，每年能节省近千万 元资金。现在我国的研究人员正在加紧研制有关领域的数据挖掘工具，并且数据 挖掘技术的应用领域正不断扩大。下面列出一些有发展潜力的数据挖掘应用领域。 1 科学研究 在信息量极为庞大的天文、气象、生物技术等领域中，由于所获得的大量实 验和观测数据靠传统的数据分析工具已难以应付，因此对功能强大的智能化自动 分析工具有迫切的需求，这种需求推动了数据挖掘技术在科学研究领域的应用发 展，并且已获得一些重要的应用成果，例如，美国加州理工学院喷气推进实验室 与天文学家合作开发的s k i c a t 系统通过对几百万个天体进行分类，已帮助天文 学家发现了1 6 个新的类星体。 2 金融投资 由于金融投资的风险很大，因此在进行投资决策时，需要对各种投资方向的 有关数据进行分析，以选择最佳的投资方闷。数据挖掘可以通过对已有数据进行 处理，并利用学习得到的模式进行市场预测，例如，国内开发的指南针、神光、 r m r 等智能股票分析系统可以对股票行情进行分析预测。 3 市场营销 在市场营销领域中，数据挖掘可以辅助制定市场策略，分析购物模式，还可 以用来预测销售行情，例如，m m 公司开发的q u e s t 和i n t e l l i g e n tm i n e r 系统就 可以挖掘顾客的购物行为模式。 4 保险业 保险是一项风险业务，保险公司的一个重要工作就是进行风险评估。研究证 明，可以利用数据挖掘来进行风险分析，在保险公司建立的保单及索赔信息数据 库的基础上，寻找保单中风险较大的领域，从而得出一些实用的控制风险的规则， 以指导保险公司的工作。例如，利用s g i 公司的m i n s e t 系统提供的分类器就可以 预测投保人在将来的索赔概率。 5 制造业 电子科技大学硕十学位论文 制造业应用数据挖掘技术来进行零件故障诊断、资源优化和生产过程分析等。 例如，a c k n o s o f t 公司开发的c a s s i o p e e 系统已用于诊断和预测在波音飞机制造 过程中可能出现的问题。 6 通信网络管理 在通信网络运行过程中可能产生一系列警告，虽然有的警告可以置之不理， 但是有的警告如果不及时采取措施，则会带来不可挽回的损失。哪些警告可以不 予理睬，哪些警告必须迅速处理，这往往很难判断，一般需要由人工根据经验来 进行处理，因此效率不高。数据挖掘则可以通过分析已有的警告信息的正确处理 方法以及警告之间的前后关系获得警告之阃的关联规则，这些有价值的信息可用 于网络故障的定位检测和严重故障的预测。例如，芬兰h e l s i n k i 大学开发了一个基 于通信网络中警报数据库的知识发现系统1 a s a ，它可用于寻找通信网络中的警报 序列规则，以便进行故障预测。 1 4 第二章聚类方法基础 3 1 聚类分析 第三章聚类方法基础 聚类分柝是研究数据间逻辑上或物理上的相互关系的技术，它通过一定的规 则将数据集划分为在性质上相似的数据点构成的若干个类。聚类分析的结果不仅 可以揭示数据问的内在联系与区别，同时也为进一步的数据分析与知识发现提供 了重要的依据，如数据问的关联规则，分类模式以及数据的变化趋势等。作为统 计学的重要研究内容之一。聚类分析具有坚实的理论基础并形成了系统的方法学 体系，然而，基于统计学的聚类分析方法大多局限于理论上的分析并依赖于对数 据分布特征的概率假设，较少考虑具体应用中的实际数据特征与差异。由于数据 挖掘技术的迅速堀起，聚类分析褥以在数据库技术领域获得长足的发展。 3 1 。1 聚类的定义 聚