（计算机应用技术专业论文）粗糙集在海量科学数据挖掘中的应用.pdf

粗糙集在海量科学数据挖掘中的应用 中文摘要 随着科学技术的高速发展，需要处理的信息量迅速增加，要把海量科 学数据作为信息，信息成为知识，迫切需要利用能从海量科学数据信息中 发现、推理知识的有效方法。数据挖掘( d a t am i n i n g ) 就是从大量的、不完 全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不 知道的、但又是潜在有用的信息和知识的过程。为了得到好的挖掘结果， 数据预处理是进行数据挖掘工作前不可缺少的工作。数据预处理就是把不 便识别的数据转化为易于识别的规范数据的信息处理过程。在整个数据处 理过程中，规范化和属性约简是处理的核心。如何除去无意义的属性不但 是技术上的关键问题也是理论研究上的重要课题。近几年来，粗糙集理论 已在属性约简方面开始表现出它的潜力。多方面的研究和测试表明，针对 科学数据采用粗糙集的方法进行约简可以为后面的知识发现提供方便，提 高模式识别的性能，从而达到更好的挖掘效果。 科学数据具有维数高、数据量大，数据不完全，有噪声等特点，本课 题在现有的数据库和w i n d o w s 平台上，开发一个具有开放体系结构的、易 扩充的、易维护的、具有良好人机交互界面的数据挖掘系统，从科学数据 中提取隐含在其中的有用的知识，为科学计算中的仿真信息提供符合规律 的模拟结果分析。目前已经完成了一个最基本的数据挖掘系统，实现了如 下功能：在数据预处理方面，包括对数据库中数据进行离散化处理、对冗 余属性的约简，降维；在知识发现方面主要是分类、聚类以及关联规则提 取。测试结果表明基本上达到了设计要求。 本论文主要讲述数据挖掘中采用粗糙集方法实现数据预处理中冗余属 性约简的问题。论文首先介绍了数据挖掘的基本概念，接着介绍了粗糙集 的一些基本知识及其在属性约简方面的应用：第四章介绍了信息熵及其与 粗糙集的结合应用：第五章介绍了一些基于粗糙集的属性约简的常用算法， 并提出了对m i b a r k 算法的改进；第六章介绍了目前的数据挖掘系统的功 能及属性约简在整个系统中的应用。n q l 一_ _ 。，、 门慕洋 关键词：数据挖掘，粗糙集，、属性药简，互信息 粗糙集在海量科学数据挖掘中的应用 a b s t r a c t w i t h a c c e l e r a t i n gp a c e o fs c i e n c e d e v e l o p m e n t ，t h e d e m a n d so n c a p a b i l i t yo fl a r g e s c a l ei n f o r m a t i o na n a l y s i sa r ei n c r e a s i n g d a t am i n i n g i st h ep r o c e s st h r o u g hw h i c hw ec a ne x t r a c th i d d e nb u tu s e f u lk n o w l e d g e f r o mh a l f - b a c k e d ，n o i s i n g ，f u z z ya n dr a n d o md a t as e t s i no r d e rt oo b t a i n s a r i s f y i n gr e s u l t s ，i t i s n e c e s s a r y f o rt h ed a t a b a s et ob e p r e p r o c e s s e d b e f o r et h ea c t u a lm i n i n g p r e p r o c e s s i n gc o n v e r t st h eo r i g i n a l d i r t y d a t a i n t on o r m a l i z e dd a t a d a t an o r m a l i z a t i o na n da t t r i b u t er e d u c t i o na r et h e c o r eo ft h ew h o l e p r o c e s s h o w t or e m o v er e d u n d a n ta t t r i b u t e si s h i g h l i g h t e di nb o t ht e c h n o l o g ya n dt h e o r yr e s e a r c h i nr e c e n tf e wy e a r s ， r o u g h s e t t h e o r y h a ss h o w n p o t e n t i a l i na t t r i b u t e r e d u c t i o n ， c o m p r e h e n s i v e r e s e a r c h e sa n dt e s t sr e v e a lt h a t a p p l y i n gr o u g h s e t m e t h o do ns c i e n t i f i cd a t at or e d u c ed i m e n s i o nc a ni m p r o v et h ee f f i c i e n c y o f p a t t e r nr e c o g n i t i o n ， s c i e n t i f i cd a t ah a st h ec h a r a c t e r i s t i co fh i g hd i m e n s i o n a l ，i n c o m p l e t e ， n o i s i n g ，a n ds oo n o u rp u r p o s ei st od e v e l o pa no p e n ，e a s i l ym a i n t a i n a b l e ， e x t e n s i b l ea n d u s e r f r i e n d l ys c i e n t i f i cd a t am i n i n gs y s t e m ( s d m s ) w h i c h c a ne x t r a c tu s e f u l k n o w l e d g e f r o ms c i e n t i f i cd a t aa n d a n a l y z e t h e s i m u l a t i o nr e s u l to fs c i e n t i f i cc o m p u t i n g t h es y s t e mi sh o s t e do nd b m s a n dw i n d o w sp l a t f o r m c u r r e n t l ya p r o t o t y p es y s t e mw i t hf u n c t i o n so f a t t r i b u t e r e d u c t i o n ，d i s c r e t i o n ，c l a s s i f y i n g a n d c l u s t e r i n g h a sb e e n c o m p l e t e d t e s tr e s u l t ss h o wt h a tt h es y s t e mh a sb a s i c a l l ya c h i e v e dt h e d e s i g n i n gr e q u i r e m e n t t h i s p a p e rm a i n l y d i s c u s s e s t o p i c s o n s o l v i n g a t t r i b u t er e d u c t i o n p r o b l e m sb ya p p l y i n gr o u g hs e tm e t h o d si nt h ef i e l do fs c i e n t if i c d a t a m i n i n g f i r s t ，b a s i cc o n c e p t so fd a t am i n ga r ei n t r o d u c e d ；t h e nt h et h e o r yo f r o u g hs e ta n di t sa p p l i c a t i o no na t t r i b u t er e d u c t i o ni sp r o v i d e d ；i nt h e4 1 “ c h a p t e r ，t h ec o n c e p to fe n t r o p ya n dt h ea p p l i c a t i o no fe n t r o p yc o m b i n i n g w i t hr o u g hs e ti s r e c o u n t e d ；s o m ec o m m o na t t r i b u t er e d u c i n ga l g o r i t h m s b a s e do i l r o u g hs e tt h e o r ya r ee x p l a i n e d ，a n d an e wm i b a r kb a s e d a l g o r i t h mi sp r o p os e d ；f i n a l l y ，f u n c t i o n a l i t yo ft h ed a t am i n i n gs y s t e mis p r e s e n t e da n dt h ep e r f o r m a n c eo fa t t r i b u t er e d u c t i o ni nt h es y s t e ma r e 粗糙集在海量科学数据挖掘中的应用 s h o w nb ys o m ee x p e r i m e n t s k e y w o r d s ：d a t am i n g ，r o u g hs e t ，a t t r i b u t er e d u c t i o n ，m u t u a li n f o r m a t i o n i i i - 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：蒿函日期：渺乒年屈月功日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 啦 日期：叫年月叫日 粗糙集在海量科学数据挖掘中的应用 1 1 项耳概述 第一章引言 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高， 无数个数据库被用于商业管理、政府办公、科学研究和工程开发等，这 势头仍将持续发展下去。于是，一个新的挑战被提了出来：在这被称之为 信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何才能不被 信息的汪洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢? 要 想使科学实验数据真正地为科研服务，只有充分对其进行分析、挖掘，帮 助科研工作者发现以前不能发现的问题，找出以前不能找出的规律。要想 使数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决策 和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。因 此，面对“人们被数据淹没，却饥饿于知识”的挑战，数据挖掘和知识发 现( d m & k d ) 技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命 力。 数据挖掘( d a t a m i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用 的信息和知识的过程。还有很多和这一术语相近似的术语，如从数据库中 发现知识( k d d ) 、数据分析、数据融合( d a t af u s i o n ) 以及决策支持等。人们 把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据可 以是结构化的，如关系型数据库中的数据，也可以是半结构化的，如文本、 图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可 以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现 的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以 用于数据自身的维护。因此，数据挖掘是一门广义的交叉学科，它汇聚了 不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行 计算等方面的学者和工程技术人员。 数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的 简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、 分析、综合、推理、学习和评估，以指导实际问题的求解，发现事件间的 相互关联，甚至利用已有的数据对未来的活动进行预测。 在科学研究领域，技术的革新使科学家能够以不断增加的速度，从试 粗糙集在海量科学数据挖掘中的应用 验、仿真及观测中收集数据，数据容量从近来的百万字节到现在的千兆字 节，并且不久就将达到万亿字节。我们产生数据的能力已经远远超过了我 们对它们的研究、分析和理解的能力，并且经常收集的可利用的复杂数据 都是图像或者时间序列。为了实现我们的科学目标，我们需要通过从这些 数据中提取有用的信息来充分的对它们进行知识开采。可不幸的是，由于 在许多科学领域中数据的尺度范围如此之大、复杂度如此之高，以至于使 用人工来对它们进行分析、研究和理解完全是不切实际的。这导致的结果 是，有用的信息经常被忽视掉，并且增强了的计算能力和数据搜集能力的 潜在优势只能部分发挥出来。为了解决这个问题，我们应用并扩展了数据 挖掘领域的方法，开发了新的科学数据挖掘技术，希望能够提高科学家与 大规模、高维度、时变的科学数据之间的交互性。这些技术能够帮助我们 自动地在数据中进行模式识别，并且使科学家们能够以交互方式对感兴趣 的某些领域的数据进行知识开采。 随着科学仿真实验数据的越来越多，且不同实验采集的数据分散于不 同的计算机中。科学家们几乎不可能通过手工的方式来发现各数据源之间 的潜在联系。这迫切需要研究出与此对应的新的数据挖掘技术及其挖掘工 具来解决此类问题。目前，国外对数据挖掘技术的研究比较多，但专门针 对科学数据的研究非常少。国内此领域的研究处于初步的起始阶段，成熟 的研究成果基本空白。 此项目在一般数据挖掘技术的基础上，通过对科学仿真数据的具体研 究，应用统计学、人工智能、机器学习、数据挖掘、软件体系结构、软件 工程等各学科中的相关方法，搭建起合理且高效的科学数据挖掘架构、研 究出科学高效的数据挖掘算法，并开发出应用于实际的科学数据挖掘平台， 以填补国内本研究领域和相关产品的空白。 科学数据挖掘技术可以应用到仿真数据，试验数据，以及在各个不同 科学领域中收集的观测数据中。每秒万亿次的计算环境使对复杂现象的仿 真变为现实，并且仿真输出的数据量越来越庞大。这些仿真在许多领域中 都扮演着十分关键的角色，例如核武器管理领域中，计算机仿真已经用来 代替了试验；又如天气建模领域中，利用试验是不切实际的也是不明智的。 为了让科学家能够理解这些仿真的输出，可视化技术正频繁的应用于数据 的展示。由于仿真输出的数据规模是如此之大，因此可视化技术并不能充 分的对它们进行展示。如果将可视化技术和数据挖掘技术结合在一起，那 么就能够实现交互式的数据展示，仅仅将科学家们感兴趣的某些领域的数 据展示出来，使他们能够快速的对输出数据进行知识开采。这样不仅能够 粗糙集在海量科学数据挖掘中的应用 帮助科学家理解单个仿真的输出数据，而且能够使他们对比多个仿真的输 出结果，同时还可以将试验同仿真进行对比，且可以交互式的对仿真进行 控制。 1 2 论文的研究背景 1 2 1 数据挖掘的发展及研究状况 1 2 1 1 知识发现和数据挖掘的起源 早在八十年代，人们就估算全世界的数据总量2 0 个月就会翻一番，进 入九十年代后，数据量会增长的更快。在这样的数据增长速度下，“信息爆 炸”和“数据过剩”成为了当今数字化社会面临的巨大挑战。 进入九十年代后，数据库技术的一个新领域一一数据仓库( d a t a w 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 ab a s e ，k d d ) 及其核心技术一一数据采掘 ( d a t a m i n i n g ，d m ) 就这样应运而生了。数据库技术的日益成熟和数据仓库 的发展为知识发现和数据挖掘提供了发挥的平台，而机器学习又为数据挖 掘提供了大量的方法。因此，知识发现和数据挖掘是应用需求推动下跨学 科发展的产物 2 1 。 1 2 1 2 知识发现和数据控掘的发展概祝 目前，知识发现不仅被许多研究人员看作是数据库系统和机器学习方 面一个重要的研究课题，而且被许多工商界人士看作是一个能带来巨大回 报的重要领域。 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 国际会议。从19 9 7 年开始，k d d 也拥有自己的专门杂志k n o w l e d g ed i s c o v e r y a n dd a t a m i n i n g 。1 9 9 5 年以来，国外在知识发现和数据挖掘方面的论文非常多，已 形成了热门研究方向 3 j 。 粗糙集在海量科学数据挖掘中的应用 1 2 2 粗糙集发展及研究状况 1 2 21 粗糙集的发展概况 1 9 8 2 年波兰数学家p a w l a k z 提出了粗糙集( r o u g hs e t ，简称r s ) 理论， 它是一种处理模糊和不确定知识的数学工具。同时也开发了一些应用系统， 但是最初该项研究当时并未引起国际计算机学界的重视，研究局限于东欧 国家。 1 9 9 1 年，p a w l a k z 发表了专著r o u g h s e t ：t h e o r e t i c a l a s p e c t s o f r e a s o n i n ga b o u t d a t a ) ) 【4 】，奠定了粗糙集理论的基础，从而掀起了粗糙集的 研究高潮。1 9 9 2 年，在波兰召开了第一届国际粗糙集研讨会，这次会议着 重讨论了集合近似的基本思想及其应用，其中粗糙集环境下机器学习的基 础研究是这次会议的四个专题之一。1 9 9 3 年在加拿大召开了第二届国际粗 糙集与知识发现研讨会，这次会议积极推动了国际上对粗糙集应用的研究。 由于这次会议正值知识发现成为热门研究话题，一些著名的知识发现学者 参加了这了次会议，并且介绍了许多应用扩展粗糙集理论的数据挖掘的方 法与系统。1 9 9 6 年在日本东京召开的第五届国际粗糙集研讨会以及2 0 0 0 年 在我国重庆举行的研讨会推动了亚洲地区和我国对粗糙集理论与应用的研 究。现在，美国、加拿大、波兰、日本都有粗糙集研究的专门机构 5 】。 1 2 2 2 粗糙集的应用和研究状况 由于粗糙集理论可以支持知识发现的多个步骤，如数据预处理、数据 约简、规则生成等，因此基于粗糙集理论的k d d 系统被认为具有独特的优 势 3 。 近几年来，粗糙集合理论已应用于机器学习、知识发现、决策支持与 分析、专家系统、智能控制、模式识别等领域。目前国际上已经开发出了 一些基于粗糙集理论的k d d 系统。如r e g i n a 大学利用粗糙集理论开发的 知识发现系统k d d r ，该系统目前被广泛的应用于医疗诊断、电信业等领 域 6 。还有美国k a n s a s 大学开发的l e r s ( l e a m i n gf r o me x a m p l e sb a s e d0 n r s ) 系统，该系统被应用于医疗诊断、社区规划、全球气象研究等方面。波 兰p o a n a n 工业大学开发的一个模块化的软件系统r o s e ，这个系统已经成 功地应用于处理很多实际数据集，如医学、药剂学、技术诊断、金融和管 理科学、图像与信号处理等。r o s e t t a 是由挪威科技大学和波兰华沙大学合 作开发的一个基于r o u g h 集理论框架的表格逻辑数据分析工具包。r o s e t t a 粗糙集在海量科学数据挖掘中的应用 的目的是要作为基于不可分辨关系模型的通用工具，而不是为某个特定的 应用领域设计的专用系统。 目前国外在粗糙集领域的研究主要集中在约简的优化算法、粗糙集理 论和模糊理论，粗糙集理论同神经网络理论等其他人工智能技术的结合、 粗糙逻辑等课题上。本文对于约简算法的研究正是粗糙集领域中一个非常 重要的课题。 我国在粗糙集领域的研究起步较晚，但我国在这个领域的发展速度很 快，目前中科院、清华大学、南京大学等研究所和高校己加入到这个领域 中，并取得了一定的成果。 1 3 论文研究内容 本次课题主要有以下几个方面的研究工作： 1 、了解知识发现的体系结构，学习粗糙集理论的基本概念，研究粗糙 集理论进行数据约简的算法。 2 、通过对传统的可辨识矩阵求核算法的研究和实验分析，提出结合信 息熵的求核算法，通过实验证明这个算法能够明显的减少在大多数数据集 中获得核值属性的时间。 3 、通过实验发现导致无核数据集在传统的可辨识矩阵算法中需要大量 时间的原因是由于合并无法减少可辨识矩阵项的数量。在信息熵的求核算 法的基础上，应用信息熵求出约简属性集。并与传统的基于可辨识矩阵的 约简算法对比，通过实验证明这个算法能够明显的减少在大多数数据集中 获得约简属性集的时间。 4 、通过实验发现基于信息熵的约简算法存在的问题，如：得到的约简 属性集有时候并不是最佳约简属性集，本文还提出了基于信息熵约简算法 的改进方案。 6 、参加国家自然科学基金项目基于神经网络的大规模科学数据分析， 独立完成了基于粗糙集算法的属性约简模块。 粗糙集在海量科学数据挖掘中的应用 2 1 数据挖掘的定义 第二章数据挖掘概述 简单地说，数据挖掘就是从大量数据中“挖掘”或提取知识。一种比 较公认的定义由g ，p i a t e t s k y s h a p i o r ，w j f r a w l e y 等人提出的，即：数据挖 掘是指从数据库的大量数据中揭示出隐含的、先前未知的、潜在有用的信 息的非平凡过程，但是，有些人认为数据挖掘是数据库知识发现过程中的 一个关键步骤。数据库知识发现的过程如下： ( 1 ) 数据清洗清除噪声数据和与挖掘主题明显无关的数据。 ( 2 ) 数据集成将来自多个数据源中的相关数据组合在一起。 ( 3 ) 数据选择从数据库中检索与分析人物相关的数据。 ( 4 ) 数据转换将数据转换为易于进行数据挖掘的数据形式。 ( 5 ) 数据挖掘它是数据库知识发现的一个基本步骤，使用智能方法提 取数据模式。 ( 6 ) 模式评估根据一定的评估标准从挖掘结果中筛选出有意义的模 式。 ( 7 ) 知识表示利用可视化技术和知识表示技术，为用户提供所挖掘的 知识。 从上述步骤可以看出，数据挖掘只是整个过程的一个步骤。然而，在 大多数场合人们采用广义的数据挖掘观点，即数据挖掘是指从存放在数据 库、数据仓库以及其他信息库中的大量数据中挖掘有趣知识的过程。这样， 我们可以不加区分地使用数据挖掘和数据库知识发现这两个术语。基于这 种观点，典型的数据挖掘系统如图2 1 所示，它包括以下几个主要部分。 ( 1 ) 数据库、数据仓库或其他信息库。它表示数据挖掘对象是由一个或 一组数据库、电子表格、数据仓库或其他类型的信息库组成。通常需要使 用数据清洗和数据集成操作初步处理这些数据对象。 ( 2 ) 数据库服务器和数据仓库服务器。根据用户的数据挖掘请求，服务 器负责提取相关的数据。 ( 3 ) 知识库。它存放数据挖掘所需要的领域知识，这些知识用于指导数 据挖掘的搜索和用于帮助对挖掘结果的评估。用户确信方面的知识也包含 在内。挖掘算法中所使用的用户定义的阀值就是最简单的领域知识。 ( 4 1 数据挖掘引擎。这是数据挖掘系统最基本的部件，通常由一组功能 粗糙集在海量科学数据挖掘中的应用 数据 图形用户界面j l l 模式评估 丘i ： l 数据挖掘引擎 j 置岳 图2 1 典型的数据挖掘系统结构 模块组成，可以完成定性归纳、关联分析、分类归纳、进化计算和偏差分 析等功能。 ( 5 ) 模式评估模块。该模块可根据兴趣度量标准，协助数据挖掘模块挖 掘更有意义的模式。以便将搜索聚焦在有趣的模式上。比如它可以使用兴 趣度阀值过滤发现的模式。如果数据挖掘算法能够与模式评估方法有机结 合将有助于提高数据挖掘的效率，而该模块能否与数据挖掘模块有机结合， 则与数据挖掘模块所使用的具体挖掘算法有关。 ( 6 1 可视化用户界面。该模块帮助用户与数据挖掘系统进行交流，允许 用户与系统交互。一方面用户通过该模块将自己的挖掘查询或任务提交给 数据挖掘系统；另一方面系统通过此模块向用户展示数据挖掘的中间结果 和最终结果：此外，该模块还允许用户浏览数据库和数据仓库或数据结构， 评估挖掘的模式，用不同的形式对模式进行可视化。 从数据仓库的角度来看，数据挖掘可以被认为是在线分析处理( o l a p ) 的高级阶段，结合了多种数据理解先进技术的数据挖掘比数据仓库的汇总 型分析处理走得更远。 粗糙集在海量科学数据挖掘中的应用 2 。2 数据挖掘的功能 利用数据挖掘技术可以获得多种知识，在许多情况下，用户并不知道 数据库中存在哪些有价值的知识，因此一个数据挖掘系统应该能够同时发 现多种模式的知识，以便满足用户的需要。下而介绍一下数据挖掘的功能。 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任 务一般可以分为两类：描述和预测。描述性挖掘要刻画数据库中数据的一 般特性。预测性挖掘要在当前数据上进行推理，来进行预测。 1 、概念描述：定性与对比 通过对含有大量数据的数据集进行概述性的总结，可以获得简明、准 确的描述，这种描述就称为概念描述。获得概念描述的方法主要有以下三 种： ( 1 ) 3 0 用更为广义的属性，对所分析的数据进行概要总结，被分析的数 据称为目标数据集； ( 2 ) 将所分析的两类数据的特点进行对比，并对对比结果进行概要总结， 这两类数据分别称为目标数据集和对比数据集。 ( 3 ) 数据特征化和比较。 2 、关联分析 关联分析就是从给定的数据集中发现频繁出现的项集模式知识，即关 联规则，形如( x jy ) ，即( a ia a 4 b ia a b ) 。关联分析广泛用于市 场营销、事务分析等应用领域。 关联规则的挖掘i ；3 题可形式化描述如下，设i = ，f 。) 是数据项集 合，d 是与任务相关的数据集合，也就是一个交易数据库，其中每个交易丁 是一个数据项子集，即t d ，t 1 ，每个交易均有一个识别编号t i d 。设 a 为一个数据项集合，当且仅当a e i 时，称交易r 包含4 。一个关联规则 就是具有a ；b 形式的蕴涵式，这里a c i ，b c i ，并且4 n b = 西。关联规 则a j b 在交易数据库d 中成立，并且具有j 支持度和c 信任度。这也就意 味着交易数据库d 中有s 比例的交易r 包含a u 口数据项，并且交易数据库 d 中有c 比例的交易r 满足“如果包含a ，则包含b ”的条件。即 s u p p o r t ( aj 矗) = p ( a u 曰)( 2 1 ) c o n f i d e n c e 口j 口) = p ( aib )( 2 2 ) 满足最小支持度阀值和最小信任度阀值的关联规则称为强规则。通常 将最小支持度阀值简写为m i n s u p ，最小信任度阀值简写为m i n c o n f ，这两个 粗糙集在海量科学数据挖掘中的应用 阀值都在o o o 至l j1 0 0 之间。 一个数据项的集合称为项集，一个包含k 个数据项的项集称为k 一项集。 一个项集的出现频度就是交易数据库d 中包含该项集的交易记录数。如果 一个项集的出现频度大于或等于最小支持度闭值乘以交易记录集d 中的记 录数，那么该项集满足最小支持度阀值。满足最小支持度阀值的项集称为 频繁k 项集。所有频繁项集的集合记作l 。 关联规则的挖掘问题可以分解为两个子问题。 ( 1 ) 找出所有的频繁项集。这些项集的频度至少应等于最小支持度： ( 2 ) 根据所获得的频繁项集生成相应的强关联规则。对于每个频繁项集 ，如果y c x ，y ，且s u p p o n ( x ) s l l p p o n 吖) m i n c o n f ，则有关联规则 y j x y 。 3 、分类和预测 分类和预测是两种数据分析形式，它们可用于抽取能够描述重要数据 集和预测未来数据趋势的模型。分类方法用于预测数据对象的离散类别， 预测方法用于预测数据对象的连续取值。机器学习、专家系统、统计学和 神经生物学等领域的研究人员已经提出了许多具体的分类预测方法。数据 分类过程主要包含两个步骤，第一步是建立一个描述己知数据集类别的模 型。该模型通过对数据库中各数据对象内容的分析获得。它是在已知训练 样本类别的情况下，通过学习建立相应的模型。通常分类学习所获得的模 型可以表示为分类规则形式、决策树形式和数学公式形式。第二步是利用 所获得的模型进行分类操作。经过评估，如果模型的分类准确率是可以接 受的，那么就可以使用这一模型对未来的数据对象进行分类。与分类学习 方法相比，预测方法可以认为是对未知类别数据对象的类别取值，利用学 习所获得的模型进行预测。目前分类与预测方法己被广泛应用于各行各业， 如信用评估、医疗诊断、性能预测和市场营销等应用领域。 4 、聚类分析 根据对象之间的相似程度，将一群对象分为若干组的过程就是聚类过 程。一个聚类就是由彼此相似的一组对象所构成的集合，不同聚类中的对 象通常是不相似的。聚类分析就是从给定的数据集中搜索数据对象之间所 存在的有价值的联系。在许多应用中，一个聚类中所有对象常常被当作一 个对象进行处理，聚类分析己被应用于模式识别、数据分析、图象处理和 市场分析等领域。聚类分析与分类预测方法的区别在于两者的学习方法不 同，前者是无监督的学习方法，后者属于有监督的学习方法。 5 、孤立点分析 粗糙集在海置科学数据挖掘中的应用 与其它数据不一致或非常不同的数据就称为孤立点数据。大部分挖掘 将孤立点视为噪声或异常而丢弃了。但在一些应用场合，如各种商业欺诈 行为的自动检测，小概率事件往往比经常发生的事件更有价值。对孤立点 的分析处理通常称为孤立点挖掘。它的用途很广，例如，它可以用于欺诈 检测，即监测信用卡使用或电信服务中的异常行为；还可以用于市场分析， 即通过分析花费较小或较高顾客的消费行为制定营销策略。 6 、演变分析 演变分析就是对随时间变化的数据对象的变化规律进行描述并建模。 这类分析包括时间序列数据分析、序列或周期模式匹配和基于近似性的数 据分析。例如，利用演化分析方法，我们可以分析股票市场上主要股票的 交易数据，获得整个股票市场的股票演化规律。这样，我们能够准确地预 测股票市场上的股票价格，提高投资回报率。 2 3 数据挖掘的主要方法 数据挖掘的方法很多，每种方法都有其特定适用领域。某一种方法不 可能胜任所有的数据挖掘任务，一个复杂的数据挖掘系统常常采用多种数 据挖掘方法，通过整合多种数据挖掘方法来弥补不同数据挖掘方法所存在 的不足。数据挖掘的方法主要有以下几种： 1 、基于决策树的方法 决策树也称为判定树。它是用于分类和预测的主要方法之一。决策树 技术发现数据模式和规则的核心是归纳算法。它的目的是根据某个新记录 的属性，将其分派到预先定义好的若干类中的一个，并为其添加一个字段 以标识该记录的类别。构建决策树的算法很多，其中最具代表性的是c a r t 和c 4 5 算法。它们的算法思想大致如下： 将给定训练集作为决策树的根节点，训练集中的记录具有标识类别的 字段，利用信息增益来寻找节点上具有最大信息量的字段，根据对该字段 的不同取值建立该节点的若干分支，并为所有分支子集建立对应的节点。 在每个分支子集中重复建立下层分支和节点，直到节点中所有记录的类别 都相同为止，这样便生成了一棵完整的决策树。因为完整的决策树不利于 分类和预测，因此还要对该决策树进行剪枝处理，产生最终的决策树。然 后把决策树的节点分裂过程转化为“i f t h e n ”的规则，利用这些规则就 可以对新数据进行分类。 决策树方法在许多应用领域被广泛地应用，主要优点有： 粗糙集在海量科学数据挖掘中的应用 第一，生成的规则容易理解：决策树产生的规则能够轻易地转化为 “i f t h e n ”这种形式的关联规则，也可以被翻译成自然语言或s q l 语句t 而且决策树模型的建立过程也比较直观。 第二，决策树进行分类时所需的计算量不大。 第三，决策树既支持离散数据也支持连续数据。 第四，决策树的输出包含属性的排序：决策树能够清楚地指出哪一个 数据域对决策是最重要的。 当然，决策树方法也存在着一定的不足。例如，训练一棵决策树的耗 费很大；对具有连续值的属性预测比较困难；在类过多的情况下分类容易 出错等。 2 、基于神经网络的方法 神经网络最早是由心理学家和神经生物学家提出的。神经网络是大量 的简单神经元按一定规则连接构成的网络系统。网络能够模拟人类大脑的 结构和功能，采用某种学习算法从训练样本中学习，并将获取的知识存储 在网络各单元之间的连接权中。神经网络和基于符号的传统人工智能技术 相比，具有直观性、并行性和抗噪声等优点。目前已出现了多种网络模型 和学习算法，主要用于分类、优化、模式识别、预测和控制等领域。在数 据挖掘领域，主要采用前向神经网络提取分类规则。从网络中提取规则， 主要有下述两种方向： f 1 ) 网络结构分解的规则提取。 它以神经网络的隐层结点和输出层结点为研究对象，把整个网络分解 为许多单层子网的组合。通过研究较简单的子网，便于从中挖掘知识。k t 算法是有代表性的方法：k t 方法的缺点是通用性差，并且当网络比较复杂 时算法的复杂性高，容易产生组合爆炸问题。所以，对于大规模网络，此 类算法在提取规则前，需要对网络结构进行剪枝和删除冗余结点等预处理 工作。 ( 2 ) 由神经网络的非线性映射关系提取规则。这种方法直接从网络输入 和输出层数据入手，不考虑网络的隐层结构，避免了基于结构分解的规则 提取算法的不足。s e s t i t o 等人的相似权值法是一个典型的算法。 在数据挖掘领域，神经网络的规则提取还存在许多问题。如，进一步 降低算法的复杂度；提高所提取规则的可理解性：提取规则的评估标准： 在训练中从神经网络动态提取规则以及时修正神经网络并提高神经网络性 能等。 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 4 数据挖掘的应用 目前国际上数据挖掘技术在科学研究、金融投资、市场营销、保险、 医疗卫生、产品制造业和通信网络管理等行业己得到广泛应用；国内在数 据挖掘方面也有成功的应用，例如宝钢已应用数据挖掘系统辅助生产决策， 每年能节省近千万元资金。现在我国的研究人员正在加紧研制有关领域的 数据挖掘工具，并且数据挖掘技术的应用领域正不断扩大。 1 、科学研究 在信息量极为庞大的天文、气象、生物技术等领域中，由于所获得的 大量实验和观测数据靠传统的数据分析工具已难以应付，因此对功能强大 的智能化自动分析工具有迫切的需求，这种需求推动了数据挖掘技术在科 学研究领域的应用发展，并且已获得一些重要的应用成果，例如，美国加 州理工学院喷气推进实验室与天文学家合作开发的s k i c a t 系统通过对几 百万个天体进行分类，已帮助天文学家发现了1 6 个新的类星体。 2 、金融投资 由于金融投资的风险很大，因此在进行投资决策时，需要对各种投资 方向的有关数据进行分析，以选择最佳的投资方问。数据挖掘可以通过对 己有数据进行处理，并利用学习得到的模式进行市场预测，例如，国内开 发的指南针、神光、r m r 等智能股票分析系统可以对股票行情进行分析预 测。 3 、市场营销 在市场营销领域中，数据挖掘可以辅助制定市场策略，分析购物模式， 还可以用来预测销售行情，例如，i b m 公司开发的q u e s t 和i n t e l l i g e n t m 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 大学开发了一个基于通信网络中警报数据库的知识 发现系统t a s a ，它可用于寻找通信网络中警报序列规则，以便进行故障预 测。 2 5 粗糙集在数据挖掘中的应用 粗糙集理论从诞生到现在虽然只有十几年的时间，但已经在许多领域 取得了令人鼓舞的成果。 ( 1 ) 股票数据分析，g o l a n 等应用粗糙集方法分析了十年间股票的历史数 据，研究了股票价格与经济指数之间的依赖关系，获得的预测规则得到了 华尔街证券交易专家的认可。 ( 2 ) 模式识别，n e j m a n 应用粗糙集方法研究了手写字符识别问题，提取 出了特征属性。 ( 3 ) 地震预报，t e g h e m 等研究了地震前的地质和气象数据与里氏地震级 别的依赖关系。 ( 4 ) 冲突分析，d e j a 应用粗糙集方法建立了反映以色列、巴勒斯坦、约 旦、埃及、叙利亚和沙特阿拉伯等六国关于中东和平问题各自立场的谈判 模型。 ( 5 ) 从数据库中发现知识，粗糙集方法现成为k d d 的一种重要方法，其 导出的知识精练且更便于存储和使用。 ( 6 ) 粗糙控带l j ( r o u g hc o n t r 0 1 ) ，把控制过程中的一些有代表性的状态以及 操作人员在这些状态下所采取的控制策略都记录下来，形成决策表，然后 对其分析化简，总结出控制规则。粗糙集方法是