（系统工程专业论文）基于粗糙集的数据库知识发现的研究与应用.pdf

华中科技大学硕士学位论文 摘要 数据库知识发现( k d d ) 是涉及人工智能和数据库等学科的一门当前相当活跃 的研究领域。在当今数字化社会中，各种商业、政府、科学数据库和数据量的急剧 增长，远远超过了人类目前已有的分析和理解能力，因此从大量的数据中智能地、 自动地提取出有价值的知识和信息的研究，即数据库知识发现，具有十分重要的现 实意义。本文基于上述背景对数据库知识发现中的一些问题做了较深入的研究。 整个论文由绪论及k d d 概述、粗集挖掘理论、连续属性离散化和分类规则发现 及实例四大部分组成。 本文首先系统的概述了数据库知识发现和粗糙集的基本理论，然后介绍了离散 化的两种基本离散方法：归并与划分，给出了一种适用粗集离散的的离散算法 面向属性重要性的离散方法，并且在讨论归并策略基础上提出了一种新的归并策略 以及在此基础上的改进算法。实验结果表明，采用改进的离散化方法作为连续值属 性预处理手段，归并的效果要好于未改进的的离散方法。最后介绍了面向粗糙集的 缺省规则挖掘算法，给出f 虹集团赊帐主题挖掘实例。 k d d f 处在起步阶段，有许多问题值得探讨，本文的工作是一个尝试，还有待 进一步深入。但k d d 研究的应用前景非常广阔，将成为决策支持的一个重要的发展 方向，并使决策者真正成为数据的主人。 关键词：数据库知识发现，粗集理论，连续属性离散化，分类规则 华中科技大学硕士学位论文 a b s 丁r a c t k n o w l e d g ed i s c o v e r y i n d a t a b a s e s ( k d d ) i s ar a p i d l y e m e r g i n gr e s e a r c h f i e l d r e l e v a n tt oa r t i f i c i a l i n t e l l i g e n c e a n dd a t a b a s e s y s t e m i nt o d a y sd i g i t a ls o c i e t y , t h e e x p l o s i v eg r o w t h o fm a n yb u s i n e s s ，g o v e r n m e n t ，a n ds c i e n t i f i cd a t a b a s e sh a v ef a r o u t p a c e do u ra b i l i t yt oi n t e r p r e ta n dd i g e s tt h i sd a t a ，c r e a t i n gan e e df o ran e wg e n e r a t i o n o ft o o l sa n dt e c h n i q u e sf o ra u t o m a t e da n d i n t e l l i g e n td a t a b a s ea n a l y s i s ，a n dt h a ti st h eg o a l o fk d dt h i sp a p e rr e s e a r c hi nd e p t ho ns o m e p r o b l e m i nk d d t h ec o n t e n to ft h ew h o l e p a p e ri sm a d eu po f f o u rp a r t s ：t h es u r n l t t a r i z eo f k d d ，t h e b a s i so fd a t a m i n i n g b a s e d r o u g h s e ta n dd i s c r e t i z a t i o no fc o n t i n u o u s a t t r i b u t e s ， c l a s s i f i c a t i o i lr u l e si n d u c t i o na n dac a s e t h i sp a p e ra tf i r s ts u m m a r i z e sb a s i ct h e o r i e so fk d da n dr o u g hs e tt h e o r i e sa n d i n t r o d u c e s m e r g e rm e t h o da n dp a r t i t i o nm e t h o d t h e na n a l y z e sad i s c r e t i z a t i o nm e t h o d o r i e n t e d i m p o r t a n c e o fa t t r i b u t e sf o rr o u g hs e ta n dp r e s e n t si t s i m p r o v e m e n tw i t h a r e s e a r c hf o r m e r g e rs t r a t e g y ae x p e r i m e n tp r o v e s t h em e t h o di sm o r e e f f i c i e n t f i n a l l y e x p a t i a t e s aa l g o r i t h mc a l l e dm d r b r ( m i n i n gd e f a u l tr u l e sb a s e do i l r o u g hs e t ) a n di m p l e m e n t s i t sr e a l i z a t i o n k d dr e s e a r c hi sn o wi nab e g i n n i n gp h a s e ，t h i s p a p e ra t t e m p t st o d i s c u s ss o m e a s p e c t si ni t a n di tn e e dd e e p l yr e s e a r c h b u tk d dw i l lb ep r o s p e r i t ya n di tw i l lb e8 1 1 i m p o r t a n t r e s e a r c hd i r e c t i o no f d s s k e y w o r d ：k d d ，r o u g hs e t ，d i s c r e t i z a t i o no f c o n t i n u o u sa t t r i b u t e s ，c l a s s f i c a t i o nr u l e s l f 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 寻浮 日期；叫。年；月( 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被套阕和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密 ( 请在以上方框氏打“4 ”) 学位论文作者签名：于淖 日期：三守埠年i 月7 日 指导教师签名：四岔皂定 日期：撕碎年5 - 月，d 日 华中科技大学硕士学位论文 1 1课题来源 1绪论 本课题包括以下四个科研项目： 1 ) 湖南正虹集团原料管理系统； 2 ) 湖南正虹集团“公司+ 农户”管理系统； 3 ) 湖南正虹集团“内部信息系统”； 4 ) 小城镇试点示范工程子课题二先进试用技术评估与推广 1 _ 2 课题的背景与意义 随着大规模数据库的广泛使用和i n t e r n e t 的迅猛扩展，全球范围内数据库中存储 的数据量迅速增大。快速增长的海量数据收集并存放在在大型数据库或w e b 页面中， 没有强有力的工具，理解它们已经远远超出人的能力。海量的数据被描述为“丰富 的数据，贫乏的知识”。目前数据库系统所能做到的只是对数据库中已有的数据进行 存取，人们通过这些数据所获得的信息量仅仅是整个数据库所包含的信息量的一部 分，隐藏在这些数据之后的更重要的信息是关于这些数据的整体特征的描述及对其 发展趋势的预测，这些信息在决箫生成的过程中具有重要的参考价值。由于数据量 的爆炸性增长使得传统的处理方法变得不切合实际，需要采用自动化程度更高，效 率更高的数据处理方法帮助人们处理大量数据，并提供有效的信息。如何快速，准 确地获得有价值的信息，如何理解和解释已有历史数据并用于预测未来的行为，如 何从这些海量数据中发现知识，导致了知识发现领域的出现。 数据库知识发现( k d d - - k n o w l e d g ed i s c o v e r y i nd a t a b a s e s ) 中基于算法的核 心步骤在工程上我们也称之为数据挖掘( d m d a t a m i n i n g ) 。 知识发现( k d - - k n o w l e d g ed i s c o v e r y ) 是集统计学，人工智能，模式识别， 并行计算，机器学习，数据库等技术的一个交叉性的研究领域，是人工智能研究领 域中的研究热点。从数据库中发现出来的知识可以用在信息管理、查询响应、决策 支持、过程控制等许多方面【“。所以k d d 不仅被许多研究人员看作是数据库系统和 一 华中科技大学硕士学位论文 机器学习方面一个重要的研究课题，而且被许多工商界人士看作是一个能带来巨大 回报的重要领域。 本文的的作者参加了湖南正虹集团“公司+ 农户”管理系统，湖南正虹内部管 理系统等项目的设计和开发工作。深刻认识到各种信息系统深入渗透到企业的运作 中并积累了大量的数据，如何更好的利用这些数据以便能从中提取出有用的决策信 息给企业是一个很迫切的问题。 本文的研究工作源于上述背景，目的是对基于粗糙集的数据库知识发现的应用 与数据离散化进行深入的研究。 1 3 国内外研究现状 1 3 1 知识发现 k d d 的研究经历了从机器学习到机器发现再到k d d 几个阶段，从8 0 年代末， 人们开始研究k d d ，1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会 议的专题讨论会上首次出现k d d 这个术语。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都 举行k d d 专题讨论会，集中讨论数据统计、海量数据分析算法、知识表示、知识运 用等问题。随着k d d 在学术界和工业界的影响越来越大，k d d 组委会于1 9 9 5 年 把专题讨论会更名为国际会议，并改为大会代表自愿报名参加，1 9 9 5 年在加拿大蒙 特利尔市召开第一次k d d 国际学术会议，以后每年召开一次。1 9 9 8 年在美国纽约 举行的第四届知识发现与数据挖掘国际学术会议不仅进行学术讨论，并且有3 0 多家 软件公司展示了他们的数据挖掘软件产品，不少软件已在金融，气象，医疗等领域 应用 3 i o 我国k d d 的研究刚刚起步，1 9 9 6 年的全国性学术会议上只有零星的论文，1 9 9 7 年召开的全国数据库学术会议才设立“数据仓库、知识发现与数据采掘”专题，研 究k d d 的论文也只有十几篇。但目前巳成为热点研究课题，很多大学、研究所都在 进行这方面的工作。 近几年，国内在数据挖掘方面的最新发展如下：在分类技术的研究上，试图 建立其集合理论体系，井实现海量数据处理；以粗糙集和模糊集理论为基础，构 一 2 华中科技大学硕士学位论文 造模糊系统知识模型与模糊系统辨识方法，以及构造智能专家系统，将粗糙集与模 糊集融合，用于知识发现；中文文本挖掘的理论模型与实现技术；利用概念格 进行文本挖掘；知识发现机理的研究。 1 3 2 粗集知识发现 自1 8 世纪德国数学家g w l e i b n i s 倡导用通用符号语言和逻辑演算改革形式 逻辑学，到1 9 世纪德国数学家g f r e g e 等人建立命题演算和一阶谓词演算系统， 形成了数理逻辑学体系。这种经典逻辑学，只有真、假值之分。但在现实生活中， 有许多含糊现象井不能简单地用真、假值来表示。给出粗糙集的概念。 1 9 6 5 年，z a d e h 提出了模糊集理论，但遗憾的是模糊集是不可计算的。1 9 8 2 年， 波兰学者z p a w l a k 教授提出了粗糙集的概念。他把集合中那些无法确认的个体都 归属于边界区域，而这种边界区域被定义为上近似集和下近似集之差集，当差集不 为空时，这个集合称为粗糙集。粗糙集理论有确定的数学公式描述，可以计算其含 糊度。之后，许多波兰学者对粗糙集理论及其应用进行了深入的研究，主要分析了 粗糙集理论的数学性质与逻辑系统。1 9 9 2 年在波兰k i e k r z 召开了第一届国际粗糙集 学术讨论会，主要讨论了集合近似定义的基本思想及其应用。1 9 9 3 年在加拿大b a f f 召开了第二届粗糙集和知识发现研讨会。这次会议的主题是粗糙集、模糊集与知识 发现。1 9 9 4 年在美国s a nj o s e 召开了第三届国际粗糙集与软计算研讨会，这次会 议主要探讨了粗糙集与模糊逻辑、神经网络、进化理论等的融合问题。1 9 9 5 年召开 的第四届模糊理论与技术国际研讨会，主要针对租糙集与模糊集之间的关系进行了 讨论，促进了粗糙集的发展。1 9 9 9 年在日本召开第七届粗糙集、模糊集、数据挖掘 和粒度一软计算国际会议，主要阐述了当前粗糙集、模糊集的研究现状和发展趋势。 2 0 0 0 年在加拿大召开了第二届粗糙集和计算的当前趋势学术会议。当前许多重要的 国际学术会议都把粗糙集理论的研究列入主要内容之一。 粗集作为一种强大的工具渗透到知识挖掘从属性约简到规则发现的全过程。 x h f i u 等提出了一种将基于属性的归纳方法和租糙集相结合的方法【2 ”。该方法 使用面向属性的概念树爬升技术对属性进行泛化，用一个内部属性v o t e 来记录泛化 过程中的被合并的元组个数，并滤除v o t e 值低于噪音门限的元组，从而大大降低了 一 3 华中科技大学硕士学位论文 数据库学习过程的计算复杂度；然后使用粗糙集方法计算约简并生成规则。 t m o l l e s t a d 等提出了基于粗糙集理论的缺省规则的挖掘方法【2 2 】。该方法把粗糙集 理论与默认推理结合起来，从而实现信息不完备的倩况下仍能根据缺省规则进行推 理，得出当前合理的决策。n s h a h 等提出了一种发现基于粗糙集理论的最大泛化 规则和约简的增量自适应算法 2 3 1 。该算法将决策规则和约简的计算转化为一组相关 联的布尔表达式的化简和修改，而无需搜索算法去寻找与修改规则。 我国对人工智能的理论研究较多，对知识发现问题的研究在9 0 年代末以后才逐 渐兴起，比国外相对落后。随着对信息的依赖与全球信息化趋势的发展，知识发现 的重要性日益显著，而粗集作为一种新型数学工具，近年来在我国理论界才逐渐开 始被关注，并在利用粗集理论进行知识发现领域，已取得了较为显著的成果【l l l 埘， 但总体来说，我国目前对粗集知识发现的理论研究仍相对匮乏，有待进一步的研究。 1 4 本文内容与结构 本文系统的概述了粗集和数据库知识发现的基本理论，介绍了离散化的两种基 本离散方法：归并与划分，给出了一种适用粗集离散的的离散算法面向属性重 要性的离散方法，讨论了归并策略，并提出了一个断点归并框架以及在此基础上的 改进算法。改进算法明显提高了归并效率，实验结果表明，采用改进的离散化方法 作为连续值属性预处理手段，归并的效果要好于未改进的的离散方法。最后介绍了 面向粗糙集的缺省规则挖掘算法，并通过个案例对它进行了检验。全文共6 章； 第一章是全文的绪论。作者在第二章中对k d d 进行了较为全面的评述。首先介 绍了k d d 的含义和k d d 过程的各个组成部分，接着讨论了挖掘技术的分类与k d d 系 统和应用，最后给出了目前在k d d 研究中存在的问题。第三章详细阐述了粗集理论 以及在数据挖掘中的应用。第四章提出了基于属性重要性的连续属性离散化提出了 一种新的归并策略以及在此基础上的改进算法，并进行了实验比较。第五章介绍了 粗集理论在挖掘分类知识的应用及其作者实现的一个计算机模拟。第六章为总结与 展望。 4 华中科技大学硕士学位论文 2 数据库知识发现 2 。1 数据库知识发现的定义 k d d 是k n o w l e d g e d i s c o v e r y i n d a t a b a s e s 的缩写，该术语于1 9 8 9 年出现，其定 义几经变动，普遍采用的描述性定义是f a y y a d “1 等给出的： k d d 是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模 式的非平凡处理过程。 在上面的定义中，涉及几个需要进步解释的概念：“数据集”、“模式”、“过 程”、“有效性”、“新颖性”、“潜在有用性”和“最终可理解性”。 数据集： 是一组事实f ，它记录了数据的特性或数据之间的关系( 如关系数据库中的记 录 。 由于k d d 处理的数据是从现实世界中得到的，因而不能保证所有数据都规范， 一般需要对数据进行预处理，使之适于知识提取。 模式： 是一个用语言l 来表示的一个表达式，它可用来描述数据集f 的某个子集凡， e 作为一个模式要求它比对数据子集如的枚举要简单( 所用的描述信息量要少) 。如： “如果成绩在8 1 9 0 之间，则成绩优良”可称为一个模式，而“如果成绩为8 1 、8 2 、 8 3 、8 4 、8 5 、8 6 、8 7 、8 8 、8 9 或9 0 ，则成绩优良”就不能称之为一个模式。 模式可以看作知识，它给出了数据的特性或数据之间的关系，是对数据包含的 信息更抽象的描述。 过程： 在) d 中通常指多阶段的一个过程，涉及数据准备、模式搜索、知识评价，以 及反复的修改求精。该过程要求是非平凡的，意思是要有一定程度的智能性、自动 性( 仅仅给出所有数据的总和不能算作是一个发现过程) ，这个处理过程的大部分阶 段是系统自动进行的而无需人工干涉。 5 华中科技大学硕士学位论文 有效性： 是指发现的模式对于新的数据仍保持有一定的可信度。 新颖性： 要求发现的模式应该是新的。 潜在有用性： 是指发现的知识将来有实际效用，如用于决策支持系统里可提高经济效益。 最终可理解性： 要求发现的模式能被用户理解，目前它主要是体现在简洁性上。 k d d 的目标就是要将数据中隐含的模式提出出来，从而帮助人们更好地了解数 据中包含的信息。 有效性、新颖性、潜在有用性和最终可理解性综合在一起可称之为兴趣性 ( i n t e r e s t i n g n e s s ) 。 相对来讲，k d d 则主要流行于人工智能和机器学习界，而数据挖掘主要流行于 统计界( 最早出现于统计文献中) 、数据分析、数据库和管理信息系统( m r s ) 界。 由于k d d 的迅速发展和逐渐为各界所了解，有必要对关键术语( ) d 和数据挖掘) 进行统一规范。一种较为普遍的观点认为：d m 是k d d 中专门负责发现知识的核心 环节：而k d d 是一个交互式、循环反复的整体过程，除了包括数据挖掘外还包括数 据准备和发现结果解释评估等诸多环节。下节将详细介绍。 2 _ 2 数据库知识发现的过程 k d d 过程可概括为三郝分：数据准备( d a t ap r e p a r a t i o n ) 、数据挖掘及结果的解 释评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 8 1 0 k d d 的过程图如下： 图2 1k d d 过程幽 华中科技大学硕士学位论文 数据准备阶段： 数据准备又可分为三个子步骤： ( l ) 数据选取( d a t as e l e c t i o n ) 数据选取在理解领域知识和相关的先验知识，明确系统目标的基础上确定发现 任务的操作对象，即目标数据( t a r g e td a t a ) ，也即选择需要进行知识发现的变量或数 据样本的一个子集。 ( 2 ) 数据预处理( d a t ap r e p r o c e s s i n g ) 数据预处理一般可能包括消除噪声、数据补齐、消除重复记录、完成数据类型 转换( 如把连续值数据转换为离散型的数据，以便于符号归纳，或是把离散型的转 换为连续值型的，以便于神经网络归纳) 等。 ( 3 ) 数据变换( d a t a t r a n s f o r m a t i o n ) 。 数据变换的主要目的是数据约简和投影，寻找依赖于获取目标的表达数据的有 用特征，以约简数据模式。 数据挖掘阶段： 数据挖掘阶段首先要确定挖掘的任务或目的是什么，如分类、聚类关联规则发 现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样的挖掘算法。同样 的任务可以用不同的算法来实现，选择实现算法有两个考虑因素：一是不同的数据 有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要 求，有的用户可能希望获取描述型的、容易理解的知识( 采用规则表示的挖掘方法 显然要好于神经网络之类的方法) ，而有的用户或系统的目的是获取预测准确度尽可 能高的预测型知识。完成了上述准备工作后，就可以实施数据挖掘操作了。需要指 出的是，尽管数据挖掘算法是k d d 的核心，但要获得好的挖掘效果，必须对各种挖 掘算法的要求或前提假设有充分的理解。 结果解释和评估阶段： 数据挖掘阶段发现出来的模式，经过用户或机器的评估，可能存在冗余或无关 的模式，这时需要将其剔除；也有可能模式不满足用户要求，这时则需要整个发现 过程退回到发现阶段之前，如重新选取数据、采用新的数据变换方法、设定新的数 掘挖掘参数值，甚至换一种挖掘算法( 如当发现任务是分类时，有多种分类方法， 7 华中科技大学硕士学位论文 不同的方法对不同的数据有不同的效果) 。另外，k d d 由于最终是面向人类用户的， 因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示， 如把决策树转换为“i f t h e n ”规则。 说明： 数据挖掘仅仅是整个过程中的一个步骤。数据挖掘质量的好坏有两个影响要 素：一是所采用的数据挖掘技术的有效性，二是用于挖掘的数据的质量和数量( 数 据量的大小) 。如果选择了错误的数据或不适当的属性，或对数据进行了不适当的转 换，则挖掘的结果不会好的。 整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘途中发现选择的数 据不太好，或使用的挖掘技术产生不了期望的结果，这时，用户需要重复先村的过 程，甚至从头重新开始。 可视化在数据挖掘的各个阶段都扮演着重要的作用。特别在数据准备阶段， 用户可能要使用散点图、直方图等统计可视化技术来显示有关数据，以期对数据有 一个初步的理解，从而为更好地选取数据打下基础。在挖掘阶段，用户则要使用与 领域问题有关的可视化工具。在表示结果阶段，则可能要用到可视化技术。 2 3 数据库知识发现的分类 数据挖掘作为k d d 的核心部分，它被研究得最多。目前存在很多数据挖掘方法 或算法，有必要对这些方法进行分门别类。我们知道，描述或说明一个算法涉及三 个部分：输入、输出和处理过程。数据挖掘算法的输入是数据库，算法的输出是要 发现的知识或模式，算法的处理过程则涉及具体的搜索方法。从算法的输入、输出 和处理过程三个角度分，我们可以确定这样几种分类标准：挖掘对象、挖掘任务、 挖掘方法 3 1 0 根据挖掘对象分：数据库系统本身可以根据不同的标准( 如数据模型，数掘类 型等) 。根据数据模型分类可以有关系的、事务的、面向对象的、数据仓库的数据挖 掘系统：如果根据挖掘数据的特定类型来分有空间的、时间序列的、文本的、多媒 体的、w w w 数据挖掘系统。 根据挖掘的知识类型分类：有分类或预测模型知识发现、数据总结、聚类、关 华中科技大学硕士学位论文 联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等等。 根据挖掘方法可粗分为：统计方法、机器学习方法、神经网络方法和数据库方 法。统计方法中，可细分为：回归分析、判别分析、聚类分析、探索性分析等。机 器学习中，可细分为：归纳学习方法、基于范例学习、遗传算法等。神经网络方法 中，可细分为；前向神经网络、白组织神经网络等。数据库方法主要是多维数据分 析或o l a p ( o n l i n ea n a l y t i c a l p r o c e s s i n g ) 方法，另外还有面向属性的归纳方法1 2 1 0 2 4 数据库知识发现系统与应用 数据库知识发现的发展虽然只有短短数年时间，但各种系统却有如雨后春笋般 大量涌现。k d d 系统的典型结构如图2 2 ： 其中，数据库和数据仓库存储的原始数据经过数据清除、融合和过滤形成数据 库或数据仓库服务器，数据挖掘在服务器上进行挖掘，挖掘的结果经过模式评价与 知识库中的知识进行比较，评价的结果可反馈给数据挖掘引擎与模式评价，如果模 式评价的结果比较满意，则将结果通过图形用户界面提供给用户，用户反馈结果， 系统进行再挖掘【”1 。 图2 2k d d 系统的典型结构 下面主要介绍两个基于粗集的多任务型的通用系统：l e r s 和k d d r 【4 f 4 0 州1 。 l e r s ( 1 e a r n i n g f r o me x a m p l e sb a s e d o n r s ) 系统是美国k a n s a s 大学开发的基 华中科技大学硕士学位论文 于粗糙集的实例学习系统，该系统是用c o m m o nl i s p 在v a x 9 0 0 0 上实现的，主要用 于环境保护、气候研究和医疗研究等。 l e r s 系统的输入采用特定的类似于信息表的文件格式，其条件属性、决策属性 等信息采用附加信息的方式表示。l e r s 系统首先从输入文件将数据输入到计算机， 并检查输入数据的一致性，就计算每个概念的上近似集和下近似集。用户可以选择 系统提供的机器学习算法是对每个概念产生最小判别描述，提供的知识发现算法可 以从输入数据中归纳并产生出最小规则。 l e r s 系统有最大局限性，最主要局限是输入文件不能太大。这对于海量数据的 知识发现来说，该系统基本不能实现。 k d d r 4 0 系统是由加拿大r e g i n a 大学研制的，它基于可变精度粗糙集模型，采 用知识发现的决策矩阵方法。该系统具有w i n d o w s x 的菜单驱动界面，用于医学数 据分析和电信市场的决策分析等。 k d d r 系统是由4 部分组成：数据预处理、属性依赖分析和消除冗余属性、规 则提取和决策。数据预处理模块就是将原始信息表中的数据进行离散化处理；属性 依赖分析和消除冗余属性模块是基于可变精度粗糙集模型，计算条件属性和决策属 性之间的依赖性、相对约简和核；规则提取模块计算所有或部分带有决策概率的近 似规则；决策模块是对决策规则的控制模块，它使用最大条数原则，把尽量多的规 则组合在一起，并对输入计算每个决策类的决策分，来表示对某类决策的支持程度。 各个行业在数据库知识发现应用上既有相同之处，又有各自不同的独特地方。 我们将主要从科学和商业应用上来总结数据库知识发现的应用，因为它们分另f j 4 2 表 了相当不同的应用领域，如商业上最主要和普遍的应用是分类预测。 2 4 1科学应用 从科学研究方法学的角度看，科学研究可分为三类：理论科学、实验科学和计 算科学。计算科学是现代科学的一个重要标志。计算科学工作者主要和数据打交道， 每天要分析各种大量的实验或观测数据。随着先进的科学数据收集工具的使用，如 观测卫星、遥感器、d n a 分子技术等，数据量非常的大，传统的数据分析工具无能 为力，因此必须有强大的智能型自动数据分析工具才行。 华中科技大学硕士学位论文 在科学应用上一个非常有名的系统是加州理工学院喷气推进实验室与天文科学 家合作丌发的用于帮助天文学家发现遥远的类星体的一个工具s k i c a t 。利用 s k i c a t ，天文学家己发现了1 6 个新的极其遥远的类星体。s k i c a t 使用了决策树方 法构造分类器，结果使得能分辨的星体较以前的方法在亮度上要低一个数量级之多， 而且新的方法比以往方法的效率要高4 0 倍以上f 。 2 4 2 商业应用 商业或企业上对k d d 的应用需求很大，如行销、金融、制造和通讯领域等等。 商业上的大多数应用针对的是分类预测任务。 市场行销 数据挖掘在行销业上的应用可分为两类：数据库行销( d a t a b a s em a r k e t i n g ) 和货 篮分析( b a s k e ta n a l y s i s ) 。前者的任务是通过交互式查询、数据分割和模型预测等方 法来选择潜在的顾客以便向它们推销产品，而不是象以前那样盲目地选择顾客推销； 后者的任务是分析市场销售数据( 如p o s 数据库) 以识别顾客的购买行为模式，从 而帮助确定商店货架的布局排放以促销某些商品【4 5 1 。 金融投资 典型的金融分析领域有投资评估和股票交易市场预测，分析方法一般采用模型 预测法( 如神经网络或统计回归技术) 。这方面的系统有f i d e l i t ys t o c ks e l e c t o r ，l b s c a p i t a lm a n a g e m e n t 。前者的任务是使用神经网络模型选择投资，后者则使用了专家 系统、神经网络和基因算法技术辅助管理多达6 亿美元的有价证券。 欺诈甄别 银行或商业上经常发生诈骗行为，如恶性透支等。这方面应用非常成功的系统 有：f a l c o n 系统和f a i s 系统。f a l c o n 是h n c 公司的开发的信用卡欺诈估测系 统，它已被相当数量的零售银行用于探测可疑的信用卡交易：f a l c o n 系统的数据 格式只有几种，因为流行的信用卡公司只有几家( 如v i s a ，m a s t e r 等) ，因此它 的应用面很大。f a i s 是一个用于识别与洗钱有关的金融交易的系统，它使用的是一 般的政府数据表单【4 7 】。 华中科技大学硕士学位论文 2 5 数据库知识发现研究存在的问题 虽然数据挖掘领域已取得令人瞩目的进展，但由于数据挖掘技术还不成熟，其 应用还有很大的局限性，一些急需解决和完善的问题也摆在研究者的面前。 处理复杂的数据类型和数据库 以前的数据挖掘面对的主要是以结构化数据为主的关系数据库、事务数据库和 数据仓库，随着数据处理工具，先进数据库技术以及w w w 技术的迅猛发展，空阳j 数据、多媒体数据、时间序列数据、文本数据、w e b 数据，复杂类型的数据不断涌 现。 有效处理巨量和高维的数据 包含上百万条记录和数千兆字节甚至几兆兆字节的数据库已经司空见惯，另外 数据库关系表所涉及的属性或变量数也大到成百上千的数量。这种数据的巨量和高 维性使得数据挖掘时模式的搜索空间异常巨大。为了解决这些问题，需要有高效的 特别是可伸缩性算法、增量式算法、大规模并行处理技术、维数消减方法、利用背 景知识指导等技术。 数据质量的问题( 预处理问题) 数据挖掘中涉及到大量的数据不可避免地会出现一些错误的，冗余的数据，给 数据挖掘带来一定的困难。例如，数据离散化的效果；数据的缺值现象，则不能客 观地反映数据的属性和特征；含噪声的数据会影响抽取模式的准确性；对于超大数 据量，也给知识发现带来很大的麻烦。在对数据进行取样时，应该根据用户挖掘的 主题，选择有效的数据集，并对数据进行清理，归并和转换等操作，保证数掘的代 表性和客观性。 结果的验证与评价问题 结果的验证和评价是数据挖掘中不可缺少的环节。这是一个反复实验的过程， 运用其他的样品进行验证，也可以选择新的样品集进行评价，直到得出用户满意的 挖掘结果为止。数据挖掘的结果不一定是确切的答案，可能是一些有用的规则，模 式或模型，这与数据分析师和管理决策人员的知识背景与经验有一定的关系。 知识的维护与更新 新的数据积累可能导致以前发现的知识失效，这些知识需要动态维护和及时更 华中科技大学硕士学位论文 新，目前主要采用增量更新的方法来维护已有的知识。另外数据的动态性也提出了 新的问题：趋势或变化模式发现任务以及主动数据库挖掘研究。 应用系统的集成 一个单独的数据挖掘发现系统如果不和具体的应用系统集成或结合，将毫无意 义。数据挖掘应该和数据库管理系统或m i s 、电子表单、实时传感数据采集系统， 特别是决策支持系统集成在一起。目前数据仓库上的o l a p 技术是一种典型的集成， 但其他数据挖掘技术或系统的集成还有相当多的工作要做。 2 6 小结 本章介绍并讨论了数据库知识发现的定义、过程、分类、应用以及当前研究领 域存在的主要问题，主要讨论与分析了以下几项内容： 1 阐述了数据库知识发现的定义，剖析了定义中的概念“数据集”、“模式”、“过 程”、“有效性”、“新颖性”、“潜在有用性”和“最终可理解性”的含义。 2 介绍了数据库知识发现的过程，讨论了数据准备、数据挖掘与结果的解释评 估各阶段的任务、步骤、影响因素以及实际应用中的一些问题的说明。 3 按照挖掘对象、挖掘任务、挖掘方法三个标准对数据库知识发现进行了分类， 介绍了当前数据库知识发现系统典型结构，列举了两个基于粗集的多任务型的通用 系统：l e r s 和k d d r ；介绍了数据库知识发现在科学、商业领域的应用情况，列举 了在商业领域应用的热点应用。 4 指出了数据库知识发现研究存在的问题，列举了处理复杂的数据类型和数据 库、有效处理巨量和高维的数据、数据质量的问题( 预处理问题) 、结果的验证与评 价问题、知识的维护与更新等一些急需解决和完善的问题。 华中科技大学硕士学位论文 3 1粗集理论 3 基于粗集理论的数据挖掘 粗集理论( r o u g hs e t t h e o r y ) 是波兰数学家z ，p a w l a k 在1 9 8 2 年提出的一种研 究不精确和不确定性知识和数据的表达、学习、归纳的数学工具。采用粗集理论作 为不精确和不确定性知识的研究工具具有许多优点。粗集可以使用数学方法来处理 不精确和不确定性知识：粗集不需要预先给定某些特征或属性的数量描述，如统计 学中的概率分布、模糊集理论中的隶属度或隶属函数，直接从现有数据出发，分析 隐藏在数据中的事实；并且粗集还可以和其它方法融合，以进一步增强其分析不精 确和不确定性知识的能力。粗集在知识发现中的应用相当广泛，每年都有许多粗集 的文献发表，基于粗集的功能不断完善的应用系统也不断推出，涉及的领域有市场 预测、医疗数据分析、金融、过程控制、气象学、语音识别、图象处理等。 粗集理论以观察和测量所得的数据进行分类的能力为基础，它认为知识是基于 对对象分类的能力，知识直接与真实或抽象世界有关的不同分类模式联系在一起。 其主要思想是用不可分辨关系划分知识，用上下近似逼近描述概念，通过知识约简 导出决策或分类规则 5 1 1 2 6 j 。 3 1 1 信息系统与决策系统 定义3 1 1 4 i 四元组s = c 埘， v 。) ，户称为信息系统。其中：u 为对象的非空有限 集合，称为论域；a 为属性的非空有限集合；为属性a e a 的值域；厂为u x a 斗， 即va e a ，x u ，- ，阮圳a 若4 由条件属性c 与决策属性d 组脱且c n d = 毋，c u d = a ，则称s 为决策 系统。为简化起见，有时用 【，c u d ) ) 表示决策系统，即决策属性集合只包含一 个元素d 。 对于任何子集x u ，可称之为一个u 中的概念或范畴。为规范化起见，我们 认为空集也是一个概念，并且u 中的任何概念簇称为u 的抽象知识，简称知识，它 代表了对u 中个体的分类。在知识发现领域，决策表是一类特殊而重要的知识表达 华中科技大学硕士学位论文 系统，也可以表示为 u ，a 。 3 1 2 不可分辨关系 定义3 2 【4 1 如果集合z 上的二元关系r 是自反的，对称的和传递的，则称r 是等价 关系。 v x z 的等价类是抄l y r a ，即集合的所有等价对象的集合，我们称之为关于x 的等价类，记为 石 。z 中，r 的等价类集合 冈月ke z ，我们称之为z 关于j r 的 划分丌。 如集合a = a , b ，c ，d ，e ，d ，a 上的关系r = ( a ，a ) ，( b 如) ，( c ，c ) ，( d ，d ) ，( e ，e ) ，( f , 0 ，( a ，b ) ， ( b ，a ) ，( a ，c ) ，( c ，a ) ，( b ，c ) ，( c b ) ，( d ，e ) ，( e ，d ) ) 则r 的等价类为： a 卜 b - c 】- a ，b ，c ， d = e _ d ，e ) ， f l = f ) 。 u 关于r 的划分为 ( a ，b ，c ) ，( d ，e ) ，( f ) 。 用有向图表示为： 图3l 有向图 定义3 3 1 4 】v b a ，一等价关系i n d ( b ) = ( s ，j ) u x u ：v a b ，a ( s ) = a ( j ) ， 称为不可分辨关系。 显然i n d ( b ) 是一个等价关系，且i n d ( b ) = n n d ( b ) 。属性b 可以认为是用等 0 e d 价关系( 在该属性上的取值相等) 表示的知识的一个名称。 在决策系统中，关于某一个属性集b ea 的所有基于不可分辨关系的等价对象的 集合，我t f 称2 _ 2 关于属性集b 的等价类，记为 石】。，z u o 关于属性集占a 的 所有等价集，我们称之为u 中属性集b 的划分石即丌= f e ，e i 为u 中关于曰的等 价集i = 1 , 2 ，3n 。 n 华中科技大学硕士学位论文 313 近似集 定义3 , 4 【4 l 设有知识表示系统s = ( u 4 ) ，u 为论域4 为属性集。口是a 的 子集，i n d ) 是u u 上的等价关系。将子集埏u 的下近似集b g ) 和上近似集 b h ) 分别定义如下： b 一( x ) = u 一u i n d ( b ) ；一x ) b ( x ) = u f u i n d ( b ) ；r n x 定义3 5 川 关于占的边界区域为：b n d 。g ) = b - b ) 占一g ) 如果 b n d 。b ) = 庐，则称集合x 为b 可定义集合；否则，称x 为b 上不可定义集合，也 称粗糙集。 定义3 6 4 1 称p o s 。( 工) = bx ) 为x 的b 正域；把 旧g 。 ) = 【，一bg ) 称为 彳的口负域。 简单地蜕，正域p o s 。( x ) 或x 的下近似就是那些对于知识b ，u 中能完全确定地 归入集合兕的对象的集合。类似地，负域n e g 。( x ) 是那些对于知识b ，u 中所有不 能一定确定属于集合的元素的集合，它们是z 的补集。边界域是从某种意义上论 域的不确定域，对于知识曰属于边界域的对象不能确定地划分是属于x 或x 。x 的 上近似是由那些对于知识b 不能排除它们属于z 的可能性的对象构成，从形式上， 上近似就是正域和边界域的并集。 3 - 2 属性约简 粗糙集的一个重要应用是找出冗余属性。在一个决策系统中，各个条件属性之恻 往往存在着某种程度上的依赖和分类，简化可理解为在不丢失信息的前提下，可以 更简单地表示决策系统的决策属性对条件属性集合的依赖和分类。在属性集中去掉 多余的属性后的属性集称为最小属性集。 3 2 1属性集之间的依赖 定义3 7 c ，dc 爿，两属性集c 与d 之间的依赖程度r ( c ，d ) 定义为： 肥。) = i p o s 万( c 厂_ , d ) i 华中科技大学硕士学位论文 其中p o s ( c ，d ) = u c 一( x ，) 、z ，叫i n d ( d ) ，即表示划分u i n d ( d ) 中每个等 价类关于不可分辨关系i n d ( c ) 的下近似集合c 一( x ；) 的并集；y 表示了由条件属性c 的取值能准确判断出属于某个决策属性d 的等价集，的对象所占系统中的比例，即 表示条件属性c 能区分决策属性等价集的能力。r ( c ，d ) 的性质： ( ”r ( c ，d ) t o ，1 i 。 若r ( c ，d ) = o ，表示根据条件c 的取值无法将任何对象准确分类。 若r ( c ，d ) = 1 ，表示根据条件c 的取值可以将任何对象准确分类。 若o r ( c ，d ) 8 5 ) v( 平均成绩 8 5 科研评分= a ) ) t h e n 优秀 学生。 在粗集中，为了度量不确定性，我们引入置信度( c o n f i d e n c e ) 的概念。 定义3 1 1e 4 1 设e i eu i n dr q ，蜀u i n dr d j 一规则为： d e s ( e i , 9 一d e s ( x j , d j ，这里e n 髯， 其置信度定义为： a o ( e ，x ，) = l 巨n x ，l i e , i 当e ，y 视为条件属性c ，决策属性d 的划分。可以得到下面的分类规则。 ( i ) 当e jn i 时