（计算机应用技术专业论文）粗糙集理论在知识发现中的应用.pdf

原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及耿得的研究 成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得兰州理工大学或其他单位的学位或证书 而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在论文中作了明确的 说明。 作者签名：日期：d 兰 年彳羔日 关于学位论文使用授权说明 本人了解兰州理工大学有保留、使用学位论文的规定，即：学校有权保留学位论 文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采 用复印、缩印或其它手段保存学位论文：学校可根据国家或甘肃省有关部门规定送交 学位论文。 作者签名：导师签名i 。磊2 ；!日期：d 趟年互月上日导师签名：么l2 4日期：d 塑年旦月量日 j 兰州理t 大学硕士研究生毕业论文 摘要 摘要 粗糙集理论是一种新型的处理含糊和不确定性知识的数学工具，它能够分析 隐藏在数据中的事实，且不需要关于数据的任何刚加知识。该理论以其独特的优 势赢得越来越多的研究者的关注，并在各个领域得到了j 、泛的应用。本文的研究 工作主要包括以下几个方面： ( 1 ) 偏好关系下的最优约简：现有粗糙集中求取所有约简的算法是典型的 n p 一问题，这在一定程度上限制了粗糙集理论的广泛应用，其中的一个主要原因 是在求取约简的过程中可能同时存在多个可以缺省的属性，删除不同的属性将形 成不同的约简，因此在选择可以删除的属性时存在冲突。在研究过程中，我们采 用了人工智能领域中解决冲突的办法偏好关系，在属性上加上偏好关系后，约 简在该偏好关系下是有序的，通过对特殊情况的归纳，我们设计了一种特殊的树， 并由此得到了获取偏好关系f 的最优约简的算法。最后，通过在属性的可缺省性 与函数依赖之间建立对应关系，我们改进了算法，提高了其有效性。 ( 2 ) 粗糙集理论与熵理论：在粗糙集理论中，知识被看成是一种分类能力， 即在域上构造分区的能力。从信息论的角度上讲，知识是那些对我们有用的信息， 而信息是从数据中提取出来的，对于信息中的数据存在着不确定性，信息论中采 用熵这种尺度来量化地衡量这种不确定性。因此，在粗糙集理论中运用熵理论衡 量知识具有理沦上的r u 行性。研究过程中，我们提出了知识熵的概念，从代数的 角度讨论了知识熵的性质，并从粗糙集理论的核心之一一属性的可缺省性出 发，在粗糙集理论的基本概念与知识熵之间建立对应关系，通过这种机械式的数 字计算来得到粗糙集理论中的一些基本概念，如约简，核等。 ( 3 ) 基于偏序关系的粗糙集理论扩展：在现有的研究成果中，已经有着许 多对粗糙集理论进行的扩展，如基于容差关系的扩展，基于相似关系的扩展等。 研究针对s a i ，y i n gq - y a o ，y y 提出的在有序信息表中进行挖掘的方法，提出了 一种基于偏序关系的粗糙集理论框架，并, q - 以在此框架f 挖掘任何有序信息。算 法分析与实验表明，该方法的复杂度是前述方法的七，其中一是域中所含的样本 n 数。 关键字粗糙集，知识发现，字典序，知识熵，冲突，偏好关系，有序信息 表偏序关系 兰型垄三盔主璧圭生茎生芝些鲨塞 垒丝盥l a b s t r a c t r o u g hs e tt h e o r yi san e w l y e m e r g i n gm a t h e m a t i c a lt o o lt od e a lw i t hv a g u ea n d u n c e r t a i nk n o w l e d g e ，w h i c hc a l la n a l y z et h er o l eh i d d e ni nt h ed a t aw i t h o u ta n ya d d i _ r i o n a li n f o r m a t i o n i tw i n sn l o r ea n dl n o r ea t t e n t i o nb e c a u s eo fi t ss p e c i a la d v a n t a g e ， a n di sa p p l i e di nv a r i o u sk i n d so f d o m a i n s t h em a i nr e s e a r c ho ft h i sp a p e ri sa sf o l l o w s ： ( 1 ) o p t i n l a lr e d u c tu n d e rp r e f e r e n c e ：t h ea l g o r i t h mt og e ta l lr e d u c t so f r o u g h s e t ji j p ：。ii i p 一。u f i 。i 。i c l k ：；i ，。l ：i c h ! ；i 、；i s 1 l ea p p l i c a t i o no fr o u p hs e ti n r e dl i f e t h er e a s o ni sm 矗jt h e r ea r em o r et h a no n ea t t r i b u t e st h a ti sd i s p e n s a b l ei nt h e p r o c e d u r eo f g e t t i n gr e d u c t s ，d e l e t i n gd i f f e r e n to n e sw i l lg e td i f f e r e n tr e d u c t s ，s ot h e r e i sc o n f l i c t sw h e nw ed e c i d et od e l e t ea t t r i b u t e s i no u rr e s e a r c h ，w ea d o p tt h ec o m m o n m e t h o dt oa v o i dc o n f l i c t si na i ，w h i c hi sp r e f e r e n c e a f t e rw ea d dp r e f e r e n c er e l a t i o n o na t t r i b u t e s ，r e d u c t sa r eo r d e r e du n d e rt h i sr e l a t i o n t h r o u g ht h ei n d u c t i o no fs p e c i a l c a s e s ，w ed e s i g nak i n do ft r e e ，a n dg e tt h ea l g o r i t h mt 0r e l d e v eo p t i m a lr e d u c tu n d e r p r e f e r e n c e 。e v e n t u a l l y , 、v cc r e m er e l a t i o n s h i pb e t w e e nt h ed i s p e n s a b l ep r o p e r t ya n d f u n c t i o n a ld e p e n d e n c y , t h r o u g hw h i c hw ei m p r o v et h ea l g o r i t h ma n di t se f f i c i e n c y ( 2 ) r o u g hs e tt h e o r ym a de n t r o p y ：i nr o u g hs e tt h e o r y , k n o w l e d g ei ss e e na st h e a b i l i t 3o fc l a s s i f i c a t i o q w h i c hi st h ea b i l i t yt oc o n s t r u c tp a r t i t i o n so v e ru n i v e r s e f r o m i h 。、j c 、o fi n l b r m a t i o nl h e o r y , k n o w l e d g ei si l f f o r m a t i o nw h i c hi su s e f u lt ou s ，w h i l e 。1 i 。i i sr c i r j “c dt i o md a t a 7 i t hr e s p e c t e dt or i c o , 1 m a t i o n t h e r ee x i s t su u c c f l a h i t ) ，w l f i e hi sm e a s u r e db ye n t r o p y t h e r e f o r e ：i ti sf e a s i b l et om e a s u r eu n c e r t a i n t y i nr o u g hs e tt h e o r y , h io u rr e s e a r c h , w ep r o p o s et h ec o n c e p to fk n o w l e d g ee n t r o p y ， d i s c u s sa l g e b r a i cp r o p e l l , y , a n dc r e a t er e l a t i o n s l f i pb e t w e e nb a s i cc o n c e p t si nr o u g hs e t t h e o r ya n dk n o w l e d g ee n t r o p y ；t h r o u g hw h i c hw ec a r tg e ts u c hb a s i cc o n c e p t si n r o u g hs e tt h e o r ya sr e d u c t , c o r e ，a n de r e ( 3 ) e x t e n s i o no fr o u g hs c tt h e o r yb a s e d0 1 1p a r t i a lo r d e r ：o fa l lr e s u l t sp r e s e n l t h e r ea r em a n yt h e o r i e st og e n e r a l i z er o u g hs e t ，s u c ha se x t e n s i o nu n d e rt o l e r a n c e ， u n d e rs i m i l a r i t ya n de t c t h i sr e s e a r c hp r e s e a a taf r a m e w o r ko f r o u g hs e tu n d e rp a r t i a l o r d e r , w i t hr e s p e c tt ot h em e t h o dt om i n eo i tp r o p o s e db ys a i ，y i n ga n dy a o ，y y ， a n dc a nm i n ea n yo r d e r e di n f o r m a t i o n t h ea n a l y s i sa n de x p e r i m e n ts h o wt h a tt h e c o m p l e x i t yi so n l yo n et o n 2o ft h ef o r m e rm e t h o d ，w h i l ehi st h en u m b e ro ft h e e n t i f i e s k e d v o r d sr o u g hs e tt h e o r y , k n o w l e d g ed i s c o v e r y d i c t i o n a r yo r d e r , c o n f l i c t ， k n o w l e d g ee n t r o p y , p r e f e r e n c er e l a t i o n ，o r d e r e di n f o r m a t i o nt a b l e ，p a r t i a lo r d e r 第一章绪论 在经典逻辑中，只有真假值之分。但是在现实生活中有许多含糊而不能简单 地用真、假值来表示。长期以来许多逻辑学家和哲学家就致力于研究含糊概念。 早在1 9 0 4 年，谓词逻辑的创始人f r e g e ，g 就提出了含糊一词( v a g u e ) ，并把它 归结到边界线区域，也就是说论域中存在一些个体既不能在其某个子集上分类， 也不能在该子集的补集上分类。 1 9 6 5 年，z a d e h ，l a 提出了模糊集的概念“，不少理论计算机学家和逻辑学 家试图通过这理论解决f r c g e ，g 的含糊概念，但遗憾的是模糊集是不可计算 的，即没有给出数学公式描述这一含糊概念，故无法计算出它的具体的含糊元素 数目，如模糊集中的隶属度函数和模糊逻辑中的算子五均是如此。时隔近2 0 年的八十年代初，波兰学者p a w l a k ，z 针对f r e g e ，g 提出韵边界区思想提出了粗 糙集( r o u g hs e t ) ”，他把那些无法确定的个体都归属于边界线区域，而这种边 界线区域被定义为上近似集与下近似集之差集。由于它有确定的数学公式描述， 所以含糊元素数目是可以计算的，即在真假二值之间的含糊程度是可以计算的。 粗糙集理论主要兴趣在于它恰好反映了人们用粗糙集方法处理不分明问题的常 规性，即以不完全信息或知识去处理一些不分明现象的能力，或依据观察、度量 到的某些不精确的结果而进行分类数据的能力。 2 0 世纪8 0 年代末，经过许多计算机科学家和数学家的不懈研究，粗糙集理 论从理论上日趋完善，特别是由于二十世纪八十年代末和九十年代初在知识发现 和数据挖掘等领域得到了成功的应用而越来越受到国际上的关注。相对于其他处 理不确定性和含糊性的理论工具而言，粗糙集理论有着许多不可替代的优越性。 经过二十多年的研究和发展，它已经在信息系统分析、人工智能及应用、决策支 持系统、知识发现、模式识别与分类、故障检铡等方面取得了较为成功的应用。 1 1 粗糙集理论在人工智能发展历程中的地位 1 9 5 6 年夏天，美国数学家、计算机科学家m c c a r t h y 和一些数学家、信息学 家、心理学家、神经生理学家及计算机学家等在达德茅斯大学召开了世界上第一 次人工智能学术大会。在会上正式决定使用“人工智能”这个词来概括这个研究 方向，由此产生了计算机领域的个新学科人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) ，m c c a r t h y 也被誉为“人工智能之父”。 在1 9 5 6 年前后，人工智能研究取得了许多引人注目的成果，主要有以下凡 兰州理工大学硕士研究生毕业论文 第一章绪论 方面： ( 1 ) 机器翻译。在1 9 5 3 年由美国乔治敦大学的语言系主任组织了第一次公 开实验，】9 5 4 年7 月，i 酬公司在7 0 1 计算机上作了俄译英的公开表演； ( 2 ) 机器证明。1 9 5 6 年，n e w e l l 和s i m o n 等人编制的程序l o g i ct b e o r i s t 证明了数学原理第二章中的3 8 条定理，经过改进后，于1 9 6 3 年证明了该章 中的全部5 2 条定理； ( 3 ) 博奕。1 9 5 6 年，s a m u e l 研制了跳棋程序，1 9 5 9 年，该程序打败了s a m u e l 本人，1 9 6 2 年打败了美国康涅狄克州的冠军； ( 4 ) 字符识别。1 9 5 6 年，s e l f r i d g e 研制出了第一个字符识别程序，接着 在1 9 5 9 年推出功能更强的模式识另程序。1 9 6 5 年，r o b e r t s 编制了可以分辨积 木构造的程序，开创了计算机视觉的新领域。 人工智能领域出现的成果使人们兴奋起来，醉心予人工智能的专家们作出了 种种乐观的预言。1 9 5 8 年，n e w e l l 和s i m o n 充满自信地说：不出l o 年，计算机 将要成为世界象棋冠军；不出1 0 年，计算机将要发现和证明重要的数学定理； 不出1 0 年，计算机将能谱写高水平的乐曲；不出1 0 年，大多数心理学理论将在 计算机上形成。甚至有人预言：2 0 世纪8 0 年代将是全面实现人工智能的时代； 到了2 0 0 0 年，机器的智能就可以超过人了。 但是，初战告捷只是暂时的，在人们进行了深入的工作后，发现这里的困难 比想象中的要多得多。主要表现在以下几个领域： ( 1 ) 机器翻译。在最初的设想中，人们曾以为只要用一部双向字典和某些语 法知识就可以很快地解决自然语言之闺的互译闯题，结果发现了许多问题。著名 的例子是：英语句子“t h es p i r i ti sw i l l i n gb u tt h ef l e s hi sw e a k ”( 心有 余而力不足) 翻译成俄语再翻回来竟成了“t h ew i n ei sg o o db u tt h em e a t i s s p o i l e d ”( 酒是好的，肉坏了) 。因此有人说，美国政府花2 0 0 0 万美元为机器翻 译立了一块墓碑。 ( 2 ) 机器证明。1 9 6 5 年r o b i n s o n 提出了与传统的自然演绎法完全不同的消 解法，掀起了研究计算机定理证明的又一次高潮。但是，人们很快发现了消解法 的能力有限，用消解法证明“两个连续函数的和仍是连续函数”，推了十万步也 没有推出来。 ( 3 ) 博奕。s a m u e i 的下棋程序也没那么神气了，当了州冠军后没有进一步 当上全国冠军。1 9 6 5 年，世界冠军h e l m a n n 与该程序下了四局，获得全胜，唯 一的平局是世界冠军“匆忙地同时和几个人对奕”。 ( 4 ) 从神经生理学的角度研究人工智能的人发现了他们遇到了几乎不可逾 越的困难，人的脑子有1 0 ”以上的神经元，每个神经元可能不只是一个信息存储 转送单位，而是一台完整的自动机。计算机技术虽然有了很大的发展，但是要把 兰州理工大学硕士研究生毕业论文 第一章绪论 这么多台机器，哪怕是最小的微型机组成一个联合运行的网络，这在2 l 世纪能 否做到恐怕也是一个问题。r o s e n b l a t t 在1 9 5 8 年提出的感知机模型缓解了这一 困难。但在1 9 6 9 年m i n s k y 和p a p e r t 出版的感知机书中明确指出：感知机 的功能十分有限，连“异或”这样简单的逻辑运算都做不了，神经网络的研究被 打入冷宫1 0 年之久。 种种困难对人们的乐观情绪打击非常大，与此同时，英国政府在1 9 7 1 年委 托剑桥大学j a m e s 教授起草了一份综合报告在1 9 7 2 年发表，指责人工智能的研 究即使不是骗局，也是庸人自忧。报告被英政府采纳后，人工智能的研究经费被 削减，研究机构被解散；与此同时，i b m 公司也明确取消了本公司范围内的人工 智能研究活动，理由是人工智能解决不了实际问题。 人工智能的研究者们开始冷静下来，查找挫败的原因。自从人工智能成为一 个学科以来，研究者们遵循着一条明确的指导思想：研究和总结人类思维的普遍 规律，并用计算机模拟它的实现。他们必信：计算机一定能达到人的智能，关键 就是建立一个通用的、万能的符号逻辑运算体系，对于任何输入都可以给出一个 回答。n e w e l l 等称此为“物理符号系统假设”。n i l s s o n 的观点更进一步，认为 这种体系的方法应该是逻辑演绎方法，他提出“命题主义”的方法，主张一切人 工智能研究应该在一个类似逻辑的框架内进行。与此同时，老一辈科学家的思想 受到了年轻一代的挑战。斯坦福大学的f e i g e n b a u m 教授认为，所有的智能活动， 即理解、解决问题的能力，基于学习能力，全靠知识。他重新举起了b a c o n 的旗 帜：知识就是力量。在这种思想下，以知识为背景的专家系统( e x p e r ts y s t e m ) 诞生了，在2 0 世纪8 0 年代，迅速地成为软件产生的一个分支：知识产业。 f e i g e n b a u m 给它起了一个新的名字：知识工程( k n o w l e d g ee n g i n e e r i n g ) ，并在 1 9 7 7 年第五届国际人工智能大会的讲台上公诸于世。到目前为止，它是人工智 能研究领域中最有成就的分支之一，在恢复和推进人工智能方面起了重大的作 用。另外，日本的五代机计划及许多发达国家的高技术计划也推动了人工智能的 进一步发展。与此同时，神经网络的研究者们也在探索，通过将神经网络改为多 层，并加上反馈信息，它的功能就会大大加强。1 9 7 4 年，w e r b o s 提出了具有反 馈功能的多层网络；1 9 8 2 年，h o p f i e l d 提出了具有前馈功能的神经网络，并用 电路加以实现。 在人工智能中，人工智能可以通过提高机器和算法的速度来实现。照此说来， 只要造出更快的计算机就可以了。但是计算机科学的复杂性理论告诉我们：如果 问题的复杂性到了指数机，计算枧速度的提高对问题的解决能力起不到多大的作 用。 鉴于确定性算法的效率往往不如人意，各种概率算法和不确定性算法被提上 e l 程，另一批科学家主张用神经网络、遗传算法的原理，结合大量的计算来实现 兰州理工大学硕士研究生毕业论文 第一章绪论 人工智能，通常称为计算智能( c o m p u t i n gi n t e l l i g e n e e ) 。与单纯依靠计算机速 度的思想不同，它借鉴了生物学中的某些原理，在计算智能的指导下，还产生了 一个新的研究分支，称为软计算( s o f tc o m p u t i n g ) 。它除了神经网络、演化算法、 蚊群算法以外，还包括粗糙集理论等一些处理不确定性的方法。但是，这些方法 在处理某一类问题方面略显优势外，还尚未能证明自己是通过人工智能的坚实大 道， 从上面我们可阻看出，粗糙集理论是在人工智能的复苏中出现的，主要是用 来进行不确定性问题的处理的，从学科上看，它属于软计算，从属于计算智能。 1 2 粗糙集理论的研究现状 粗糙集理论是由波兰学者p a w l a k ，2 在1 9 8 2 年提出的，由于最初的研究大 多是以波兰文字发表在“b u l l e t i no f t h ep o t i s ha c a d e m yo fs c i e n c e s ： m a t h e m a t i c s ”上，所以该项研究当时并未弓l 起国际计算机学界的重视，研究地 域也仅限于东欧各国。后在8 0 年代末9 0 年代初，该理论才引起了世界各国学者 的注意。特别是1 9 9 1 年p a w l a k ，z 发表了专著r o u g hs e t ：t h e o r e t i c a la s p e c t s o fr e a s o n i n ga b o u td a t a ，系统全面地阐述了粗糙集理论。奠定了严密的数学 基础，从而掀起了粗糙集的研究高潮。该书与1 9 9 2 年出版的粗糙集理论应用专 集较好地总结了这一时期该理论与实践的研究成果，促进了它的进步发展，现 已成为学习和应用粗糙集理论的重要文献。从1 9 9 2 年至今，每年都召开以粗糙集 理论为主题的国际会议，推动了该理论的拓展和应用。目煎已成为人工智能领域 中一个较新的学术热点，引起了越来越多的科研人员的关注。 1 9 9 2 年在波兰k i e k r z 召开了第1 届国际粗糙集讨论会。这次会议主要讨论 了集合近似定义的基本思想及其应用，其中粗糙集环境下机器学习的基础研究是 这次会议的四个专腿之一。但参加这次会议的研究者较少，范围也不太广泛。这 次会议选出1 5 篇论文刊登在“f o u n d a t i o no fc o m p u t i n ga n dd e c i s i o ns c i e n c e s ” 1 9 9 3 年第1 8 卷上。从此每年召开一次以租糙集理论为主题的国际研讨会。 1 9 9 3 年在加拿大b a n f f 召开了第2 届国际粗糙集与知识发现研讨会。这次 大会极大地推动了国际上对粗糙集理论与应用的研究，其主题是粗糙集，f u z z y 集与知识发现。由于此时正值f ( d d 成为研究的热门话题，一些著名的k d d 专家参 加了这次会议，并且介绍了许多基于扩展的粗糙集理论的知识发现方法与系统。 1 9 9 4 年在美国的s a nj o s e 召开了第3 届国际租糙集与软计算研讨会，这次会议 广泛的探讨了粗糙集与模糊集、神经网络、进化理论等的融合问题。 粗糙集理论的几位主要倡导者，在1 9 9 5 年第1 1 期a c m 通讯上撰文，概括性 地介绍了目前人工智能应用新技术之一的粗糙集理论的基本概念以及其在知识 获取和机器学习、决策分析、知识发现等领域的具体研究项目和进展。特别值得 9 兰州理工大学硕士研究生毕业论文 第一章绪论 一提的是1 9 9 5 年召开的第四届模糊理论与国际技术研讨会，在这次会议上，针 对粗糙集与模糊集合的基本观点与相互关系展开了激烈地讨论，较大地促进了粗 糙集的研究。 1 9 9 6 年底在日本东京召开了第5 届国际租糙集研讨会，这是第一次在亚洲 召开的范围广泛的研讨会。1 9 9 8 年6 月在波兰华沙召开了“第1 届粗糙集和计 算的当前趋势”学术会议。1 9 9 9 年9 一1 1 月在日本召开了“第7 届粗糙集，f u z z y 集、数据挖掘和粒度一软计算的国际学术研讨会”，阐述了当前粗糙集、模糊集 的研究现状和发展趋势，指出将着重在软计算、数据库、a i 和近似推理等理论 和应用方面发展。 2 0 0 0 年1 0 月在加拿大召开了“第2 届粗糙集和计算的当前趋势”学术会议。 目前，在许多关于人工智能、模糊理论、信息管理与知识发现等国际学术会议上 经常可以看到涉及粗糙集的论文。 中国学者也积极投身于粗糙集理论的研究，2 0 0 1 年5 月在重庆召开了“第1 届中国粗糙集与软计算学术研讨会”，邀请了粗糙集之父p a w l a k ，z 教授做大 会报告；2 0 0 2 年1 0 月在苏州召开了“第2 届中国粗糙集与软计算学术研讨会” ”1 ；2 0 0 3 年5 月在重庆召开了“第3 届中国粗糙集与软计算学术研讨会”“1 ， 并同时召开了“第9 届粗糙集、模糊集、数据挖掘和粒度一软计算学术研讨会” 。1 ，2 0 0 4 年9 月，在浙江舟山召开了“第4 届中国粗糙集与软计算学术研讨会” 。1 。在国内的计算机核心刊物上，也不时出现涉及粗糙集的论文。此外，也有不 少有关粗糙集的专著“”“”“”。国内研究租糙集理论的立项研究的有中科院计算 所、中科院自动化所、重庆邮电学院、西安交大、南昌大学等，他们都得到了国 家自然科学基金和9 7 3 计划等的资助，也涌现出了一大批像王国胤、史忠植、王 珏、张文修、刘清、王驹、吴伟志等粗糙集理论的专家学者。 目前，对粗糙集理论的研究主要集中在其数学性质、粗糙集理论的扩展模型、 与其他不确定性方法的关系与互补、有效算法等。 1 3 知识发现 本文主要研究了粗糙集理论在知识发现中的应用，本节将简要介绍一下知识 发现。 1 3 1 知识发现的含义 知识发现( k n o w l e d g ed i s c o v e r y , k d ) 是从数据集中抽取和精化新的模式。知识 发现的范围非常广泛，可以是经济、工业、农业、军事、社会、商业、科学的数 据和卫星观测的数据；数据的形态有数字、符号、图形、图像、声音等；数据组 织方式也各不相同，可以是有结构、半结构、非结构的；知识发现的结果可以表 示成各种形式：包括规则、法则、科学规律、方程或概念网。 1 0 兰州理工大学硕士碜f 究生毕业论文第一章绪论 目前，关系数据库应用广泛，并且具有统一的组织结构、体化的查询语言 关系之间及属性之间具有平等性等优点郾j ，因此，数据库中的知识发现 ( 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 , g o d ) 的研究非常活跃。数据库中的知识发现， 又称数据挖掘( d a t a m i n i n g ，d m ) ，该术语于1 9 8 9 年出现，其定义几经变动，1 9 9 6 年f a y y a d ，u m 给出了目前公认的定义：k d d 是从数据集中识别出有效的、新颖 的、潜在有用的以及最终可理解的模式的非平凡过程【3 7 】【3 8 l 。 由于知识发现是一门受到来自各种不同领域的研究者关注的交叉性学科，因 此导致了很多不同的术语名称。其中最常用的是“知识发现”和“数据挖掘”。 相对来讲，数据挖掘主要流行于统计界、数据分析、数据库和管理信息系统界； 而知识发现主要流行于人工智能和机器学习【4 0 】界。 目前，k d d 不仅被许多研究者看作是数据库系统和机器学习方面一个重要 的研究课题，而且被许多工商界人士看作是一个能带来巨大回报的重要领域。从 数据库发现的知识可以用在信息管理、查询响应、决策支持、过程控制等许多方 面。g o d 这个术语首先出现在1 9 8 9 年8 月在美国底特律召开的第1 i 届国际人 工智能联合会议的专题讨论会上，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 年，g o d 拥有了属于自己的杂志k n o w l e d g ed i s c o v e r ya n d d a t a m i n i n g ： ) 。 1 3 2 知识发现的过程 知识发现可粗略地理解为三部曲：数据准备、数据挖掘以及结果的评估解释， 如图1 2 所示。 圈2 知识发现过程示意图 数据准备 数据准备又可分为两个子步骤；数据采取选择及数据预处理。数据选取的目 的是确定发现任务的操作对象，即目标数据( t a r g e t d a t a ) ，它是根据用户需要从原 始数据中抽取的一组数据。预处理一般包括除去噪声、推导计算缺值数据、消除 重复数据、完成数据类型转换，消减数据维数或降维。 兰州理工大学硕士研究生毕业论文 第一章绪论 数据挖掘 数据挖掘阶段首先要确定挖掘的任务或目标是什么，如数据总结、分类、聚 类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样 的挖掘算法。同样的任务可以用不同的挖掘算法来实现，选择实现算法有两个考 虑因素：一是不同的数据有不同手特点，需要用与之相关的算法来实现；二是用 户与实际运行的要求，有的用户可能希望获取描述型的、容易理解的知识，而有 的用户或系统的目的是获取预测准备尽可能高的预测型知识。 完成了上述准备工作以后，就可以实施数据挖掘工作了。需要指出的是，尽 管数据挖掘算法是数据挖掘的核心，也是目前研究人员主要努力的方向，但要获 得好的挖掘结果，必须对各种挖掘算法的要求或前提假设有充分的理解。 v ，结果解释和评倍 数据挖掘阶段发现出来的模式，经过用户或机器的评估，可能存在冗余或无 关的模式，这时需要将其剔除；也可能有的模式不满足用户的需求，这时需要整 个发现过程退回到发现之前，如重新选取数据、采用新的数据变换方法、设定新 的数据挖掘参数值，甚至换一种算法。另外，由于k d d 始终是面向人类用户的， 因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的另种表 示，如把分类决策树转换为“i f t h e n ”规则。 i ，3 3 知识发现的分类 根据知识发现的任务分，有如下几种：分类或预测型知识发现、数据总结、 数据聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋 势发现等等。 根据知识发现的对象分，有如下若干种数据源：关系数据库、面向对象数据 库，空间数据库、时态数据库、文本数摆库、多媒体数据库、异质数据库、遗留 数据库以及w 曲数据源。 根据知识发现的方法分，可粗分为：统计方法、机器学习方法、神经网络方 法和数据库方法。统计方法中，可细分为：回归分析、判别分析、聚类分析、探 索性分析、以及模糊集、粗糙集、支持向量机等。机器学习方法中。可缅分为： 面向归纳的学习方法、基于范例的推理、遗传算法、贝叶斯信念网络等。神经网 络方法可细分为：前向神经网络、自组织神经网络等等。数据库方法主要是基于 可视化的多维数据分析或0 l a p 方法，另外还有面向属性的归纳方法。 1 4 粳糙集理论与知识发现 基于租糙集理论的方法已成为知识发现的主流方法之一。但是，尽管翱糙集 理论对不完全知识和模糊知识的处理比较出色，但其对原始模糊数据的处理能力 较弱，仍然有许多问题尚在争论或有待解决，因此和其它方法如模糊数学、神经 兰州理工大学硕士研究生毕业论文 第一章绪论 网络等结合将会取得更好的效果。 基于粗糙集的知识发现系统一般由数据预处理、基于粗糙集或其扩展理论的 数据约简、决镶算法等部分组成。其大概思想是先进行必要的数据预处理，为数 据约简做准备，然后求出约简或近似约简，并在此基础上根据值约简等减少属性 和个体数目，最终提取规则并将之应用于新对象的分类。 在过去的几年里，建立了不少基于粗糙集的知识发现系统，其中最有代表性 的有r o s e t t a 、l e r s 、r o s e 、k d d - r 、r o u g he n o u g h 等。 r o s e t t a 该软件是挪威科技大学计算机与信息科学系和波兰华沙大学研究所合作开 发的一个基于粗糙集理论框架的表格逻辑数据分柝包，能够在微软的w i n d o w n t 9 8 9 5 操作系统上运行。该软件的设计实现了对数据挖掘和知识获取的知识 从数据的初始浏览和预处理，计算最小属性约简和产生i f - t h e n 决策规则或描述 模式，到对所得到的规则或模式的验证和分析。 l e g s l e r s ( l e a r n i n g f r o m e x a m p l e s b a s e d o n r o u g h s e t ) 系统是美国k a n s a s 大学 开发的基于粗糙集的实例学习系统。它是甭c o m m o n l i s p 在v a x 9 0 0 0 上实现的。 l e r s 已经为n a s a 的j o h n s o n 空间中心应用了多年，它是作为一种专家系统的 工具被引用的，这种类型的专家系统大多数可能被用于空间站释放的板上医疗决 策。此外，l e r s 还被广泛地用于环境保护、气候研究和医疗研究。 r o s e 波兰p o z n a n 科技大学基于粗糙集开发了r o s e ( r o u g h s e t d a m e x p l o r e r ) ， 用于决策分析。它是r o u g hd a s & r o u g hc l a s s 系统的新版，其中r o u g hd a s 执 行信息系统数据分析任务，r o u g hc l a s s 支持新对象的分类，这两个系统已经在 许多实际领域中得到应用。r o s e 是运行在p c 兼容机w i n d o w sn t 上的交互式 软件系统。i t o s e 的计算模块具有如下特点： 数据校验和预处理； 采用f a y y a d 和i r a n i 离散化算法对连续值进行自动离散化处理； 用标准的粗糙集模型或可变精度粗糙集模型对条件属性进行定性估计： 用r o m a n s k i 和s k o w r o n 等人的算法发现属性核及信息表的约简； 考察属性对目标分类的相对重要性； 选择最重要的属性进行目标分类，删除冗余属性； 用l e m 2 算法或e x p l o r e 算法获取挟策规则： 获取规则的后处理； 用决策规则对新目标进行分类； 用k 叉验证方法对决策规则进行评价。 兰州理工大学硕士研究生毕业论文第一章绪论 r o s e 的信息表数据采用i s f ( i n f o r m a t i o ns y s t e mf i l e ) 文件格式，是一种纯 文本格式。属性分为条件属性和决策属性。 k d d r 该软件是由加拿大的r e g i n a 大学开发的基于可变精度粗糙集模型的k d d 系 统，这个系统被用来对医学数据进行分析，以此产生症状与病症之间新的联系， 另外它还支持电信工业的市场研究。由以下四部分组成： 数据预处理； 基于v p r s 模型的属性依赖分析和消除冗余属性： 规则提取； 决策； r o u g he n o u g h 基于粗糙集理论，挪威t r o l ld a t a 公司开发了数据挖掘工具r o u g h e n o u g h 。 该系统可以根据信息系统计算得到区分矩阵。系统提供许多工具进行集合近似诸 如等价类、决策类、下近似、上近似、边界区域、租糙成员值、泛化决策规则等， 且采用遗传算法生成约简结果。 在国内，中科院计算所智能信息处理重点实验室将多种数据约简算法集成到 多策略知识发现平台m s m i n e r 中；而重庆邮电学院计算机科学与技术研究所研 制了粗糙集智能数据分析软件r i d a s ，这是个基于粗糙集理论的平台，该系 统能够完成数据补齐、离散纯属性约简、值约简、不完备数据算法处理等功能。 1 5 本文研究的主要内容及组织结构 利用粗糙集作为研究知识发现的工具有许多优点：首先，粗糙集理论提供了 一套数学方法从数学上严格处理数据分类问题，尤其是当数据有噪声、不完全性 或不精确性时：其次，粗糙集理论仅仅分析隐藏在数据中的事实，并没有校正数 据中所表现的不一致性，而是一般将所生成的规则分为确定与可能的规则；第三， 粗糙集理论包含了知识的一种形式模型，这种模型将知识定义为不可区分关系的 一个族集，这就使得知识有了一种清晰的数学意义，并且可使用数学方法来分析 处理；最后，粗糙集理论不需要关于数据的附加知识。 但是，粗糙集理论运用于实际系统时，仍然有一些间题，比如现有算法的低 效性在一定程度上限制了该理论的广泛应用。基于此，本文分析了粗糙集理论低 效算法的根源，在粗糙集理论的算法与数据库中的函数依赖建立了映射关系，并 基于此提出了字典序下的最优约简，并设计了算法求出该约简；进一步研究了粗 糙集理论与熵理论的结合，提出了知识熵的概念并讨论了其性质。 本文的具体组织结构如下： 第一章是绪论，对粗糙集理论和知识发现进行了较为全面的概述。首先介绍 1 4 兰州理工大学硕士研究生毕业论文 第一章绪论 了粗糙集理论的提出背景，然后详细地阐述了租糙集理论的研究现状；最后介绍 了知识发现的含义、过程、分类，并讨论了粗糙集理论在知识发现中的应用。 第二章介绍了粗糙集的基本理论和概念。首先对粗糙集的基本概念做了简要 的介绍，其次介绍了租糙集的数学性质、粗糙集理论的扩展模型以及它与其他不 确定性方法的比较与互补，最后介绍了粗糙集理论的有效算法。 第三章研究了偏序关系下的最优约简。首先分析了粗糙集理论低效算法的根 源，在粗糙集理论中的一些基本概念与关系数据库中的函数依赖之间建立映射关 系：提出了字典序下的最优约简的概念；随后设计了相应的数据结构和算法来求 出字典序下的最优约简，并证明算法的完备性和正确性。最后，将算法推广，给 出了如何求出全序关系下的最优约简的方法， 第四章研究了粗糙集理论稻熵理论的关系。熵是统计热力学中的概念，用栗 对物理系统的无组织( 紊乱) 程度进行度量的量。而这种无组织情况，就是序的不 定性的表现，所以熵也被称为不定性的数值度量。我们提出了知识熵的概念，提 出并证明了它的些代数性质，最后在知识熵与粗糙集中的一些基本算法之间建 立了映射关系。 第五章研究了粗糙集理论的一个应用领域有序信息表，通过将传统的粗 糙集理论进行扩展，可以将原有的算法效率大大提高，并可以有效地挖掘规则。 第六章为全文的总结和进一步的展望。 第二章基本理论与概念 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具，其主要思想就是 在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。目前， 粗糙集已经被成功地运用于机器学习、决策分析、过程控制、模式识剐与数据挖掘 等领域，本章介绍标准粗糙集理论( p a w l a k 粗糙集) 的基本概念，作为后续章节的 基础。 1 1 粗糙集理论的基本概念 粗糙集理论假定知识是一种对对象进行分类的能力，这里的“对象”是指我们 所能言及的任何事物，比如实物、状态、抽象概念、过程和时刻等等。也就是说， 知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定 部分称之为论域( u n i v e r s e ) ，简称为域。对于论域及知识的特性并没有任何特别假 设，事实上，知识构成了某一感兴趣领域中各种分类模式的一个族集( f a m i l y ) ，这 个族集提供了关于现实的显事实，以及能够从这些显事实中推导出隐事实的推理能 力。 为数学处理方便，在下面定义中用等价关系来表示分类，详细内容可参看 3 。 定义2 i 一个知识库( k n o w l e d g eb a s e ) 可以表示为一个关系系统 k = ( ，爿)( 2 1 ) 其中u 是非空有限对象集合，称为论域( u n i v e r s e ) ：a 为u 上的等价关系集。 定义2 2 设，a ，且p ，贝f j p 中所有等价关系的交集称为上的一种不可 区分关系( i n d i s c e r n i b i l i t yr e l a t i o