（管理科学与工程专业论文）基于粗糙集理论的关联规则挖掘方法研究.pdf

摘要 粗糙集( r o u g l ls e t s ) 理论是由p a w l a k 教授于2 0 世纪8 0 年代初提出的一种 用于处理不确定性和含糊性知识的数学工具，其基本思想是在保持分类能力不变 的前提下，通过知识约简，导出概念的分类规则。它无需提供相关数据集合外的 任何先验信息，适合于发现数据中隐含的、潜在有用的规律，即知识，找出其内 部数据的关联关系和特征。近年来，粗糙集理论和应用取得了很大的成功，己成 为软计算方法的重要分支，其涉及的领域包括模式识别、机器学习、决策分析和 决策支持、知识获取、知识发现等。提取关联规则的决策树模型具有易构造、结 构简单、易于理解、分类精度高且易于转化成s q l 语句有效地存取数据库，易十 算法实现等优点，尤其适于规则提取。 首先，本文介绍了经典( p a w l a k 型) 粗糙集的基本理论及其在不完全信息 f 的推广模型。经典粗糙集是建立在完全信息和等价关系基础之上的，用一对上 下近似集合来表示一个不精确的概念。其次，研究了粗糙集理论的属性约简和规 则提取问题，已经证明求所有约简和最小约简是n p h a r d 问题。由于在实际应 用中，我们应用关联规则进行决策时感兴趣的是一种能够提供决策支持的强规 则，为保证有用规则的有效挖掘，属性约简和规则提取应在这个条件下进行。本 文提出了一种基于限制条件的属性约简和规则提取的方法，它可以求出满足我们 耍求的所有强规则，并且运算量比较小。然后研究了粗糙集理论和决策树的结合， 提出了限制条件下的一种基于粗糙集理论的决策树算法，并把它用到了保险分 析。最后，本文研究了粗糙集在不完全信息下的推广，提出了一种基于限制条件 的不完全信息处理模型。 关键词：粗糙集理论；关联规则；限制条件；属性约简；决策树；不完全信息： a b s t r a c t r o u g hs e tt h e o 吼i n i t i a l i z e db yp r o f e s s o rp a w l a k i n e a 订y1 9 8 0 s ，h a s b e e n p r o v e d t ob ea ne x c e l l e n tm a t h e m a t i c a lt o o l d e a l i n g w i t hu n c e r t a i na n d v a g u e d e s c r i p t i o no fo b j e c t s ，w h o s eb a s i ci d e ai st od e r i v ec l a s s 讯c a t i o nm l e so fc o n c e p t i o n b yk n o w l e d g e r e d u c t i o nw i t ht h ea b i l i t yo fc l a s s i f i c a t i o nu n c h a n g e di tm a yf i n dt h e h i d i n ga n dp o t e n t i a lm l e s ，t h a ti sk n o w l e d g e ，f r o m t h ed a t aw i t h o u t a n yp r e l i m i n a r y o r a d d i t i o n a l i n f o m a t i o ni nr e c e my e a r s ，a sa ni m p o r t a i l tp a r to fs o f tc o m p u t i n 舀r o u g h s e tt h e o r ya n di t s 印p l i c a t i o n sh a v ep l a y e da ni m p o r t 觚t r 0 1 e ，e s p e c i a l l yi nt h ea r e a s o f p a n e mr e c o g n i t i o n ，m a c h i n e1 e a r n i n g ，d e c i s i o na n a l y s i s ，k n o w l e d g ed i s c o v e r y a n d k n o w l e d g ea c q u i s i t i o ne t c f i r s t l y t h ec l a s s i c a lp a w l a l 【r o u g l ls e t sb a s e d o nt h ec o m p l e t ei n f o r m a t i o ns y s t e m a n dt h ee q u i v a l e n c er e l a t i o ni si n t r o d u c e d ，w h i c ha p p r o x i m a t e ss e t so f o b j e c tb y u p p e r a n d1 0 w e rs e ta p p r o x i m a t i o n s b u tt h e r ee x i s ts o m el i m i t s ，0 n eg e n e r a l i z e dr o u 曲s e t m o d e l sa r ei m m d l l c e d ： i n c o m p l e t e i n f o r m a t i o n r o u g h s e t m o d e l ；s e c o n d l m t h e p r o b l e mo f a t t 曲u t er e d u c t i o na n dr u l ee ) ( t r a c ta r ed i s c u s s e dt h ep r o b l e mo fa t t m u t e r e d u c t i o nh a sb e e np r 0 v e dt ob en p h a r dt of i n da ur e d u c t i o n sa n dam i n i m a l r e d u c t i o nh e n c e ，i ti sh e l p m l t ou s ed i 娲r e n td e c i s i o nt r e ea l g o r i t h m st of l n das e to f d e c i s i o nm l e si f lp r a c t i c a la p p i y t h em l e sm u s ta r es a t i s f i e ds o m ec o n d i t i o n sw h i c h w e p a ya t t e n t i o nt o ，a n dt h ep m c e s sm u s tb es i m p l ei nc o m p u t e i no r d e rt oa c h i e v e t h o s e ，a na l g o r i t h mw i t har e s t r i c tc o n d i t j o nw a sp r o v i d ei nt h i sa r t i c l e t l l i r d l y ，t h e d e c i s i o nr u l ea k o r i t h mi si n t r o 血l c e d ，i ti sav e r ys i m p l em 融h o do nd e c i s i o nm l e s e x t r a c t i m e g r a t et h er o u 曲s e tt h e o 叮t ot h ed e c i s i o nt r e ea l g o r i t h m an e wd e c i s i o n r u l e se x t r a c tm e t h o d t h ed e c i s i o nt r e ea l g o r i t h mb a s e do nr o u g hs 吼t h e o r yw i t ht w o r e s t r i c tc o n d i t i o n sw a sp r o v i d e da n dg i v e sa ne x a m p l e 、sg i v e np r o v et h a tt h i s a l g o r i t h mi se 岱j c t i v e a t1 a s t ，i n c o m p l e t ei n f o r m a t i o nr o u 曲s e tm o d ew a ss t u d i e d b a s e do nt h ea c h i e v e m e n t si nt h e p a s t ， am e t h o de ) ( t r a c tm l e so n i n c o m p l e t e i n f o r m a t i o nw a s p r o v i d e dw h i c h c a nn o to n l yd i a wd e c i s i o nm l e sb u ta l s od e t e r m i n e t h em i s si n f o r m a t i o na tt h es 锄et i m e a n di ti ss i m p l ei nc o m p u t e r e l a t i v e l y k e yw o r d s ：r o u g h s e t st h e o r y ；a t t r i b u t er e d u c t j o n ；r e s t r i c tc o n d i t i o n ；a s s o c i a t i o nm l e d e c i s i o nt r e e ：i n c o m p l e t ei n f o r m a t i o n ； 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：二 日期：咝年月丝日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的 全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校 可根据国家或湖南省有关部门规定送交学位论文。 作者虢誊坦翩签名壁丝嗽避堑年上脚 硕士学位论文第1 章绪论与综述 1 1 选题背景 第1 章绪论与综述 在过去的数十年里，随着计算机和网络的发展，计算机应用的普遍推广，我 们产生和收集数据的能力迅速提高。其主要表现在条码在大部分商业产品中的广 泛使用，许多商务、科学和行政事务的计算机化，以及由文本和图像扫描平台到 卫星遥感系统的数据收集工具的进步。其次，在全球经济一体化的驱动下，企业 业务将越来越多的发生在世界各地不同的地点，不同的硬件平台和不同的数据库 中。企业大量的数据信息能不能够实现真正的共享使得工作位置变得更加复杂， 使企业获得有效信息和决策的快捷化、适时化变得更加困难。因此，基于网络数 据库，网络存贮的数据挖掘技术就有了巨大的市场潜力。技术的不断进步使得高 伸缩性的基础设施应运两生，网络存储化的流行，存储虚拟化，独立于服务器的 存储以及模块化存储的技术使企业用户要想更方便并有效的使用这些数据，快捷 的做出决策，必须不得不借助于数据挖掘技术。此外，作为全球信息系统的万维 网的流行，己经使整个社会淹没在数据和信息的汪洋之中。随着数据库技术的迅 速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。激增的数据 背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好 地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等 功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发 展趋势。缺乏挖掘数据背后隐藏知识的手段，导致了“数据爆炸但信息、知识贫 乏”的现象。而我们要想在这些数据和信息的基础上进行迅捷正确的决策就必 须借助一些新的技术和自动工具，以便将海量的数据转化成信息和知识。这些都 促使了数据挖掘的出现并将继续推动着其发展。 在激烈的市场竞争中，企业只有通过了解和分析某一产品潜在消费群体的特 征，才能在未来的市场竞争中取得主动权。在市场决策中需要很多支持信息，传 统的市场调查数据分析主要是用统计方法对调查数据进行单项统计处理。而如何 揭示事物间客观存在而未被人所知的内在联系( 如，主体用户群具有什么样的特 征，他们在购买前主要通过哪一个媒体渠道了解该产品的等) 具有更重要的实际 意义。 关联规则模式作为当前数据挖掘研究的主要模式之一，侧重于数据中不同领 域之间的联系，找出满足给定条件的多个域之间的依赖关系。根据这种关联性就 可从某数据对象的信息来推断另一数据对象的信息。这也就在一定程度提供了 硕士学位论文第l 章绪论与综述 解决上述问题的办法，因此在这个领域的研究具有很大的实际意义。 粗糙集理论作为一个具体的数据挖掘技术，也是新兴的一门学科，它是波 兰科学院和波兰华沙大学的一些学者长期共同研究的成果，由波兰学者p a w l a k z 于1 9 8 2 年正式提出。在粗糙集的研究上，同样存在着两个方向一个方向是将粗 糙集作为数学的研究范畴和领域，把粗糙集理论当作一种纯粹的集合理论，侧 重于构造粗糙集的数学理论体系。另外一个方向则是将粗糙集理论作为人工智 能和知识发现的一种实用技术，运用到生产生活中的各个方面。基于自己实际 情况和专业要求，本文主要着重第二方面的研究，这也是选题的背景之二。 由于数据挖掘和糨糙集理论都是瓶兴的学科，两者在国内的研究都明显的落 后国外，作为二者结合的一种方法，基于粗糙集理论的关联规则挖掘方法及应用 的研究国内更是明显的落后于国外。因此，对之进行研究具有重大的意义。这也 是本文选题的最终原因。 1 2 选题意义 自从7 0 年代的改革开放到8 0 年代的企业改革、9 0 年代的改制，中国的企 业经历了一系列重大改变，企业的现代化进程中取得了长足进步。可我们也不得 不清醒的认识到，国内企业与国际现代化企业依然存在很大差距，尤其是在其 决策方式和决策效率上。在进入世贸后，我们更应该更加重视这个问题，努力缩 小差距，使企业更具活力和市场竞争力。要解决这个问题，除了思想上的重视和 政策的保障外，更需要具备智力上的支持。因此，研究这个课题具有如下重要意 义： 第一、虽然在国内数据挖掘的研究近年来开展很快，可因为起步较晚，在很 大程度上依旧落后于国外，在粗糙集理论研究上更是如此。基于粗糙集理论的数 据挖掘方法的研究上尤为突出，由于国内从事这项研究的人比较少，有不少地方 还是空白。因此，进行这项研究，可以有效缩小国内外的差距，填补一些地方存 在的空白，为企业决策现代化提供智力上的保障和支持。 第二、虽然我国企业在这几十年里取得了巨大进步，甚至一些企业已经走到 了世界前列，可大多企业与先进企业相比依然存在很大差距，尤其在商业、金融 ( 譬如银彳亍、保险、信贷和投资等) 、电信业等领域。由于改革进行较晚，很多 地方还保留有很多非企业的做法，决策常常是依靠经验而非科学。进行这项研究， 可以改变这些企业的决策方式和方法，使其决策科学化、信息化。 第三、由于数据挖掘和粗糙集理论分别都是一个用途十分广泛的学科和工 具，它广泛应用在医药，生物，化工，人工智能自动化，图像处理等等多个学科。 2 硕士学位论文 第l 章绪论与综述 因此，进行这项研究具有更深远的意义，它可以为别的学科的研究提供一定的借 鉴意义。 1 3 国内外研究概况 1 3 1 粗糙集理论及应用的研究 1 3 1 1 粗糙集的理论研究 粗糙集理论是波兰科学院和波兰华沙大学的一些学者长期共同研究的成果， 由波兰学者p a w l a l ( z ( 1 9 8 2 ) 【1 】年正式提出。p a w l a kz ( 1 9 9 9 ) 2 】出版的专著系 统全面的阐述了粗糙集理论，给出了严密的数学定义和表达。1 9 9 2 年出版了粗 糙集理论的应用专辑，总结了当时的粗糙集理论和应用。自1 9 9 2 年开始至今每 年都召开以粗糙集为主题的国际会议，国际上成立了粗糙集学术研究会，国内从 2 0 0 1 年开始由中国计算机学会和人工智能与模式识别专业委员会主办，每年召 开一届粗糙集与软计算学术研讨会。 粗糙集是一种软计算方法。传统的硬计算方法，是使用精确、固定和不变的 算法来表达和解决问题。而软计算则是利用所允许的不精确性、不确定性和部分 真实性以得到易于处理、鲁棒性强和成本较低的解决方案。常用的软计算方法包 括模糊集、神经网络、遗传算法和粗糙集等。模糊集提供了一个分析不确定性的 框架，神经网络和粗糙集则被广泛的应用于分类以及规则生成，遗传算法应用在 许多优化和寻找过程中，其他的方法包括证据理论和决策树方法也被广泛的运 用。 在粗糙集理论中，关于知识有两个重要的概念，一个是知识的颗粒性。知识 被认为是一种对现实事物进行分类的概念簇。当人们讨论一个论域中的事物的时 候，通常是用论域对象的一些属性及其取值来描述它们。利用这些属性及其取值 可以对论域对象进行分类。不同的属性或者它们的组合可以构成对论域对象的不 同分类方法。这些对论域对象的划分方法在粗糙集中被称为等价关系。按照某个 属性或者属性组合，即某一等价关系是被划分为一类的论域对象，不论它们在其 它属性上是否取值相同，在该等价关系之下，这些对象相互之间是无法区分的。 这就是粗糙集中的不可分辨关系。属性及其取值，等价关系，等价类以及类中的 不可分辨关系就构成了论域对象的知识。这样的定义揭示了论域知识的颗粒状结 构。粗糙集关于知识的另外一个重要概念是近似关系。一个对象是否属于一个集 合需根据现有的知识来判断，可分为三种情况：对象肯定属于该集合；对象肯定 不属于该集合；对象既可能属于该集合也可能不属于该集合。如图ll 所示： 3 硕士学位论文第l 章绪论与综述 图1l 上界、下界、边界示意 图l1 中，由于某一等价关系的存在，整个论域集合中的对象被分成些子集( 小 格) ，这些子集就是知识的颗粒。一个知识颗粒中的对象在这一特定等价关系下 是不可区分的。对于论域中的任意一个集合( 图中不规则曲线包含部分) ，该集 合所完全包含的知识颗粒就组成了在该等价关系下的下界( 图中黑色部分) 。所 有与该集合交集不为空集的知识颗粒就组成了该等价关系的上界( 图中灰色及 黑色部分) 。知识上界和知识下界的差就是边界( 图中灰色部分) 。下界中的对 象肯定属于该集合，边界中的对象可能属于也可能不属于该集合，上界的补集 是那些肯定不属于该集合的对象( 图中空白部分) k o m o r o w s k ij ，p a w l a kz ( 1 9 9 8 ) 【3 】等人阐述了经典的粗糙集理论，系统的 介绍了包括特征选择、特征提取，规则获取与评判在内的基于粗糙集的建模方法 过程，总结了粗糙集理论的几种推广形式，探讨了粗糙集理论与其它几种理论方 法的关系，列举了粗糙集的一些应用，比较了几种进行粗糙集理论和应用研究的 软件系统。p a w j a kz ( 2 0 0 2 ) 【t 5 1 在对基于粗糙集的数据分析方法的理论研究及应 用状况进行的回顾中，提到基于粗糙集理论的智能数据分析技术在很多方面取得 的最新进展。粗糙集为在数据中寻找隐藏的模式提供了有效的算法，能够有效的 对数据进行压缩，并给出了一个评价数据质量的标准，可以宜接从数据中获取决 策规则，对数据分析的结果提供了一些直观的解释，数据分析的结果容易理解， 大多数基于粗糙集理论的算法都适用于并行计算， 在粗糙集的研究上，有两个主要的方向，个方向是将粗糙集作为数学的 研究范畴和领域，把粗糙集当作一种纯粹的数学方法，侧重于构造粗糙集的数 学理论体系。另外一个方向则是将粗糙集理论作为人工智能和知识发现的一种 实用技术，运用到生产生活中的各个方面。涉及的主要研究内容包括；粗糙集 理论的系统化，粗糙集的非参数统计建模和定量分析( 包括专家系统与智能系 统) ，基于粗糙集的非精确推理，粗糙控制理论及系统开发，寻找粗糙集的约简 算法等。本文遵循第二种研究思路，试图将粗糙集数据挖掘方面的应用进一步 拓展。 粗糙集理论方面的研究主要集中在粗糙集模型的推广、粗糙集与其它理论 4 硕士学位论文第l 章绪论与综述 的关系讨论以及利用粗糙集对知识进行定性和定量分析研究上。 ( 1 ) 在粗糙集模型的推广上有两种思路，分别是构造性方法和公理化方法 ( y a oy y ，1 9 9 8 ) 州。其中较为实用的是构造性方法。构造性方法是对原始的 租糙集模型的一般性推广，即从近似空间的概念出发研究粗糙集及其近似算子。 粗糙集的三个基本概念是论域空间、等价关系和概念集合。因此构造性方法的 粗糙集模型推广分别有将论域从一个推广到多个，将二元等价关系推广为多元 等价关系以及将近似空间进行推广三个分支。三种主要的粗糙集扩展模型分别 是基于概率的粗糙集模型，模糊粗糙集模型和交精度粗糙集模型。 y a o y y ( 1 9 9 6 ) 【7 】提出了基于概率的粗糙集模型。概率粗糙集模型建立在 条件概率的基础之上，将知识系统中的概念作为概率事件，通过定义粗糙隶属 函数重新定义粗糙集理论中的上界、下界和边界概念。概率粗糙集模型中的边 界一般比相应的经典粗糙集的边界小。而正域和负域都比经典粗糙集的正域和 负域大。概率粗糙集模型与概率统计，信息熵理论及b a v e s 理论有着深刻的联 系。 模糊集理论和粗糙集理论是处理不完整性和不确定性系统的两种方法，都 是对经典集合理论的改进。模糊理论主要处理论域中对象之间的差异在中间过 渡中的不分明性。普通集合论中，一个对象对于一个集合，或者属于、或者不 属于。模糊集认为一个对象对于一个集合，总是以某种程度属于该集合。模糊 集合以一个取值在【o ，l 】的函数描述这种隶属关系。模糊集的运算处理的是集合 中个体对于集合的隶属关系。模糊集方法需要一些先验附加知识，例如，模糊 隶属函数、基本概率分布函数。粗糙集则是另外一种刻划不完整性和不确定性 的数学工具。它能从不精确、不一致、不完备的信息中发现知识，它几乎不需 要任何先验知识。模糊集和粗糙集可以通过模糊一粗糙集模型和粗糙一模糊集 模型联系起来。d u b o i g da n d p a r a d e h 等人( 1 9 9 0 ) 嘲讨论了如何对粗糙集进行 模糊化，详尽的分析研究了模糊一租糙集模型及其特性，比较了几种不同的模 糊一粗糙集模型。模糊集和粗糙集的混合模型，将粗糙集理论与模糊集理论很 好的结合了起来，提供了一种在模糊关系和等价关系之下对知识进行分析的模 型。 b o y n o nm a i c o l m ( 2 0 0 1 ) p j 详细分析了变精度粗糙集的属性依赖度，属性约 简等特性。变精度粗糙集的产生是基于经典粗糙集的两个局限性。其一，是它 所处理的分类必须是完全正确的或者是完全肯定的，没有体现某种程度的分类 关系。其次，经典粗糙集模型中的所有结论仅仅适用于获得这些结论的对象， 因为这些对象已经精确定义了，所以在这些对象上继续讨论这些结论意义不大， 而在实际应用中，往往需要把小论域空间获得的结论应用到更大的论域空间中 5 硕士学位论文 第l 章绪论与综述 去n 变精度粗糙集模型是对经典粗糙集模型的扩充，该模型允许一定程度分类 错误的存在。集合的上界、下界和边界的定义都要考虑分类误差。当分类误差 为o 时，变精度粗糙集模型就与经典粗褪集模型等价了。变精度模型在理论上 与关联规则、模糊理论关系密切；在应用方面，则在预测建模和故障诊断中具 有良好的应用前景。 j a r o s l a ws t e p a n i u k ( 1 9 9 8 ) 和s 1 0 w i n s k i r ，、，a n d e r p o o t e nd ( 2 0 0 2 ) 川等 人在粗糙集扩展模型方面也作了楣应的工作。通过与其它理论的结合，还可以构 造更多的其它类型的粗糙集模型。 ( 2 ) 在粗糙集与其它理论的关系方面，粗糙集理论与拓扑空闻、数理逻辑、 模态逻辑、格理论、布尔代数、算子代数、概率论、模糊数学、证据理论、图论、 信息论等均在理论上有密切联系，而与证据理论，含混集( v a 鼬es e t ) 理论，神 经网络理论、b a v e s 理论等等的联系则主要是在应用方面。 粗糙集可咀表示不可区分关系，因丽b e a u b o u e ft 等人在2 0 0 1 、2 0 0 2 年对 空间地理信息系统中的含混关系与粗糙集理论之间的联系与区别作了研究盼”】。 直接利用粗糙集中上界、下界和边界的概念来分析鳃决空间数据库中的临近、相 交、覆盖等含混及不确定性关系。他们认为粗糙集作为一种处理不确定性关系的 工具，可以在一定程度上表示和处理含混关系。尽管他们试图用粗糙集理论处理 含混关系，但是由于粗糙集理论的限制，一些基本的含混关系无法用粗糙集理论 进行表示。因此粗糙集理论与含混集理论不可能存在等价和同构关系。 表1 1 模糊集与粗糙集的比较分析 模糊集理论租糙集理论 描述的对象属于同一类的不同对象不同类之间的对象 描述的关系对象对于集合的隶属关系对象在集台内的不可分辨 关系 描述内容对象对于集合的隶属度集合在论域空间牟的糨糙 度 描述方法隶属函数上、下近似集，正、负域， 边界 先验知识需要不需要 与经典集合的联系截集上近似，下近似 计算方法模糊集的运算蒗性约祷和属性值约筒 模糊集与粗糙集都是攒述知识不确定性的工具。y 如y y ( 1 9 9 8 ) 嘲对粗糙 集理论和模糊集理论进行了比较分析研究，对模糊集理论从形式逻辑和多值逻辑 6 硕士学位论文 第l 章绪论与综述 的角度进行讨论，对粗糙集则从集合与运算的角度进行讨论。表l1 对比了模糊 集和粗糙集在各个方面的差晃。模糊集和粗糙集都可以用以描述知识的不确定 性，两者具有很强的互补性，两者的综合运用可以在处理知识的不确定性和不完 全性上取得更好的效果。 粗糙集理论在神经网络的建模与训练过程中通常是用于数据的预处理，即通 过粗糙集来简化神经网络的训练样本，在保留重要信息的前提下消除冗余的数 据，以提高训练速度。李永敏，朱善君等( 1 9 9 9 ) 【“】，王玮，蔡莲红( 2 0 0 1 ) 【1 5 l 根据粗糙集信息系统约简后产生的决策规则构造多层神经网络。m a kb r e n d a ， m u n a k a t at 0 s h i n o r i 等( 2 0 0 2 ) 【1 6 】比较分析了粗糙集和神经网络以及基于信息熵 的i d 3 算法在分类精度和预测精度上做了比较。评价了三种方法的鲁棒性。但是 他们所做的工作与与其他学者一样，其结果仅建立在三种方法对实验数据的测试 之上，而没有从原理上加以说明。 ( 3 ) 粗糙集信息系统中，对象通过属性及其取值进行分类。对于每一个属 性，我们如果知道它的取值范围，那么这些属性取值的所有组合在理论上构成一 个可能的实例集合，其中每个实例构成最小的知识颗粒，这个可能的实例集 可以认为是一个最大论域空间( z h o n g n ，1 9 9 8 ) 1 1 。”。在粗糙集信息系统未经 约简的原始决策表中，每一个对象即为个最小的知识颗粒。当我们仅仅考虑由 部分属性所构成的等价关系时，论域中知识颗粒的粒度会增大。知识变得“粗糙” 起来。如果粗糙集的初始论域u = ，则论域中所有对象都是完全确定的，这时 不需要通过粗糙集方法再来对u ，u 进行各种各样的讨论。只有当u ，对 于论域空间的讨论才有意义。在u c 的情况下如何在论域空间u 中抽取知识 和决策规则? 这些知识和规则对又有什么样的划分? 如何衡量这种粒度划分 及其不确定性的大小? 这些问题对于基于知识的建模都具有非常重要的影响。 知识的粒度可以从输入数据的粒度( 离散化问题) ，知识颗粒的操作，知识 颗粒的包含关系( 知识的逼近和近似计算) 以及基于粒度的知识的推理机制设计 来考虑。p e t e r sj ，s k o w m n a ，等( 2 0 0 1 ) 【1 8 】，p e d f y c z w ( 2 0 0 0 ) 【1 9 l 等系统阐 述了粒度计算的概念，分析了粒度计算的稳定性。 p o l k o w s kl ，s k o w m n a 等( 1 9 9 6 ) 【2 圳，d u m s c hi v o ，g e d i g ag u n t h e r 等人 ( 1 9 9 8 ) 以及b e a u b o u e f t h e r a s a ，f r e d e r i c kep e t n r 等( 1 9 9 8 ) 【2 2 】在利用熵的 概念分析了粗糙集预测模型中的不确定性和粗糙集连续属性离散化的所造成的 知识不确定性。苗夺谦，王珏等( 1 9 9 9 ) 【2 3 l 着重讨论了知识粗糙性与信息熵的 关系。梁吉业孟晓伟等( 2 0 0 2 ) 【2 4 】年对信息熵在粗糙集理论中的应用进行了综 述。信息熵在粗糙集理论中被用以度量知识的不确定性，属性关联的重要性和粗 糙集的不确定性。 7 硕士学位论文 第1 章绪论与综述 不完全信息系统会导致知识的不确定性。m a r z e n ak n r s z k i e w i c z ( 1 9 9 8 ) 【2 5 】 提出了在不完全的信息系统中进行规则提取及知识发现的方法。a m i nm o u s a v i ， p a r v i z j a b e d a r - m a r a l a n i ( 2 0 0 0 ) 【2 6 j 分析了粗糙集理论的两个方面：不完全信息系 统的分析能力和对不同信息源之间的依赖关系的分析能力，提出了在多智能体之 间进行通讯交流的粗糙通讯( a m i nm o u s a v i ，p a r v i zj a b e d 小m a r a l a n i ，2 0 0 2 ) 【2 7 】 方法。 13 1 2 粗糙集的应用研究 许多专家学者在粗糙集的应用方面都已经做了广泛深入的研究，在国际和国 内上发表了大量的文章。已经有很多基于粗糙集理论的分析系统和工具，其中有 代表性的研究系统有：d a t a i o g i c 瓜一加拿大r e d u c ts v s t e m 有限公司；u e r s ( l e a r n i n g 疔o me x a m p l e sb a s e do nr o u g hs e t ，经验学习系统) 一美国肯萨斯大 学；r d u g h d a s 和r o u g h c i a s s 一波兰波兹南科技大学；r o s e ( r o u 曲s e td a t a e x p l o r e r ) 一波兰工业大学计算机科学研究所智能决策支持系统实验室；k d d r ( i ，n 环境) 一加拿大里贾纳大学；r o s s e t a 挪威科技大学计算机与信息科 学系知识系统教研组和波兰华沙大学数学所逻辑教研组；r o u g he n o u g h 一波兰 国际有限公司；r i d a s 一中国重庆邮电学院计算机科学与技术研究所； p r 玎e r o s e 3 ( p r o b a b i l i s t i cr u l ei n d u c t i o nm e t h o db a s e do nr o u g hs e t sv e r s i o n 3o ) 一t s u m o t os ；r s d m ( r d u 曲s e td a t a m i n i n g ) 一西班牙马德里工艺大学语 言与系统系；r s l 一中科院自动化研究所。 粗糙集的一般应用领域非常广泛，在生产生活中的不同领域中分别有以下一 些应用成果。 ( 1 ) 在商业领域，z i a r k ow ( 1 9 9 5 ) 和w a n gy i f a n ( 2 0 0 3 ) 社9 1 分别利用 纯粹的粗糙集和模糊粗糙集对股票价格进行了数据挖掘，寻找与股票价格相关的 规则以进行预测。w i 嚷一f a n 所构建的预测模型在预测精度上达到了9 3 的准 确度。r rh a s h e m i ，l al eb l a n c ( 19 9 8 ) 【3 0 】利用粗糙集对银行分类数据进行 预处理，在属性个数及其取值上对数据压缩，消除冗余和噪声，将神经网络模型 的预测精度从8 4 提高到了9 6 。l i n g m sp ( 2 0 0 2 ) 【3 l 】将粗糙集与遗传算法中 的编码技术结合起来，对网络用户进行分类；c h a n 窖c 1 1 i e n ，w e s l e vs ( 2 0 0 1 ) 【3 2 1 等对电子商务中的网上购物进行数据挖掘，用粗糙集对网上购物的顾客进行购物 行为分析，从中寻找关联规则，根据购物习惯向在线购物的顾客提供相应的商 品推荐。m c k e e ( 2 0 0 2 ) 【3 3 】利用粗糙集对数据进行预处理，用遗传算法建立企业 破产的预测模型，将预测的精度由6 7 提高到8 0 。黄沛，李剑( 2 0 0 2 ) 1 3 4 】利 用变精度粗糙集模型，借助基于粗糙集理论的数据挖掘工具r o s e t i a 对车险保 单数据进行分析，挖掘出隐含在其中的风险规则。 8 硕士学位论文第l 章绪论与综述 ( 2 ) 在生物和医学领域，n g u v e nht ( 1 9 9 4 ) ，1 如m o t os ( 1 9 9 8 ) 等将粗糙集理论用于对医学临床数据库进行基于规则的建模、分析和规则提取。 f r e e m a n r l 等( 2 0 0 1 ) 旧在基于粗糙集理论的应用系统l 王r s 上分析了生理反 应、环境因素和不正常言行之间的关系。q u e s t i e rf ( 2 0 0 2 ) 例等将粗糙集运用 于假单胞菌的分类研究，在分类过程中，由于属性之间存在关联和冗余，对冗余 属性的有效处理可以大大减少分类的计算量和计算时间。 ( 3 ) 在空间和地理信息的处理上，l il o n g s h u ( 2 0 0 2 ) 将粗糙集理论运 用于地理信息系统的信息处理，研究了影响冬小麦产量的地理特性，获得了一些 有用的规则和知识。w a n g z h i _ l i a n g ( 2 0 0 2 ) i 删用粗糙集方法对大量的无规则的 地理信息系统中的数据进行简化，从大量的汽车运行的轨迹数据中发掘车辆经常 报警或者拥挤的地段和区域，帮助公安警察部门合理的分配和布置警力。 ( 4 ) 在环境检测方面，韩斌( 2 0 0 1 ) f 4 1 】等将粗糙集理论作为数据挖掘的方 法运用于环境检测和软测量。s h e nq ( 2 0 0 1 ) 【4 2 】利用模糊粗糙集模型对水中的 藻类的数量进行，其基本流程是利用粗糙集对数据集进行约简和规则获取，然后 利用模糊推理机制进行估计和预测，与传统方法相比大大提高了估计的精度。 n a t h a l i ec h e v r e ，f r a n c o i s ，g a g n e ( 2 0 0 3 ) m 】等比较了基于规则的粗糙集和决策 树方法与传统的多元判别式方法( c l a s s i c a l 肌j l t i v a r i a t ed i s c r i m i n a n ta n a l y s i s ) 在 环境检测中的运用。他们认为由于粗糙集方法不需要先验的概率分布，因此克服 了由于环境不同造成的概率分布未知带来的问题。因此基于规则的方法比传统的 方法更为通用。 ( 5 ) 在工业领域，g ux p ( 2 0 0 0 ) “1 将粗糙集与神经网络结合起来进行电 力系统瞬态稳定性分析。g u 等将粗糙集作为神经网络的数据预处理部分，利用 粗糙集的属性约简去除多余的属性，然后利用神经网络作为分类器进行训练。 h o rc h i n 母l a i ( 2 0 0 2 ) 【4 5 】在对一个变电站的故障信息提取中用粗糙集处理故障场 景中的数据，简化场景模式，提取故障信息。刘振华等( 2 0 0 2 ) 【舶j 建立了基于 粗糙集的我国缓倾斜薄煤层采煤方式选择模型，以信息系统属性值表为主要工 具，揭示了采煤方式选择信息中内在的冗余性，降低了采煤方式选择构成的复杂 性，并给出了简化后的决策规则。 ( 6 ) 在语音和图像识别方面，c h e ny i q i a n g ( 2 0 0 2 ) f 4 7 等利用粗糙集对语 音信号进行分析，挑选出最主要的语音特征，结合贝叶斯等理论解决人工合成语 音中的语音单调和不自然的问题。张文字，薛惠锋等( 2 0 0 2 ) f 4 研则应用粗糙集 方法从一个语音识别数据库中发现男音和女音两种声音的分类规则。a n d r z c j c z y z e w s k i ( 2 0 0 3 ) 4 9 j 采用粗糙集方法利用多传感器对声音的方位进行判断。g a n g z h a o ( 2 0 0 2 ) 【5 0 l 利用粗糙集方法，将图像的特征作为属性，将这些特征的取值 9 硕士学位论文第l 章绪论与综述 作为属性值，对图像决策表构造和规则提取，再利用这些规则进行信息恢复和增 强。p a ls k ( 2 0 0 2 ) f 5 1 l 在采用最大期望值法处理卫星照片的多谱图像分割中， 用粗糙集进行初始化。胡静，曹先彬等( 2 0 0 2 ) 【”l 在相容粗糙集理论基础上对 图像进行预检索，提高了图形图像的检索效率。 粗糙集的一般应用范围包括模式识别，知识发现与数据挖掘，专家决策支持 系统，近似推理，预测建模，结构建模，地震预报，冲突分析，工业控制，医疗 诊断，金融证券分析，软件工程数据分析，图像处理，化工晶体结构分析，投票 分析，电力系统等等。 1 32 关联规则挖掘的研究 关联规则挖掘是由a g m w a l r ( 1 9 9 3 ) 【5 3 】等人提出来的。关联规则是描述数 据库中数据项之间某种潜在关系的规则，它己成为数据挖掘中非常重要的一个方 向。关联规则挖掘的对象一般是大型事务数据库。 关于关联规则的挖掘方法有很多，最早的也是一个重要的方法是由r a k e s h a g m w a l 等人( 1 9 9 4 ) 提出的a p r i o r i 算法( 亦称b r e a d t hf i r s t 或l e v e l 谢s e 算 法) 【5 ”，它是目前频繁集发现算法的核心，是一个基于两阶段频繁集的方法， 将关联规则挖掘算法分解为两个子问题： ( 1 ) 求出事务数据库中满足最小支持度的所有频繁集； ( 2 ) 利用频繁集一生成满足最小支持度的所有关联规则。 其中第一个问题是算法的关键问题，a p r i o r i 算法基于频繁集理论的递推方 法来解决这一问题。寻找频繁集是规则发现的核心部分，因为在求取频繁项集时， a p r i o r i 算法使用一种称作逐层搜索的迭代方法，频繁项集用于搜索频繁( 尼+ 1 ) 一 项集。首先，找出频繁l 一项集的集合，该集合记作厶。厶用于找出频繁2 一项集 的集合厶，l 而用于找出厶，如此下去，直到找不到频繁七一项集。找每个 需要扫描一次数据库。由于不同的项集数量可能达到2 ”( 是所有项的集合中的 项数) ，况且数据库中的事务可能很多，若对不同的项集都对数据库进行扫描计 算支持度，可能产生大量的频繁集，在生成一个很长的规则时产生的中间元素也 是大量的，几乎是不可能的。这也是所谓的数据爆炸问题。 针对这些不足，后人又提出了一些a p r i o r i 算法的优化算法，这些方法有： 减少搜索事务的方法【5 ”、基于划分的方法【5 6 1 以及基于抽样的方法 ”。这几种优 化方法虽然有了不同程度的改进，但有些改进是在牺牲了一些精度的上得到的， 因此，仍有难以令人满意的地方。 另外一种经典的频繁集算法是频繁模式增长( f r e q u e m p a t e mg r 0 、) l r t h ) 垆， 简称f p 窟r o 、t h 方法。它的优点是不需要产生大量的侯选集，它将发现长频繁模 式问题转化为递归的发现一些短模式，然后连接后缀。大大降低了搜索开销，提 l o 硕士学位论文第1 章绪论与综述 高了算法的效率。可当数据库很大时，构造基于内存的f p 窑r o h 是不现实的。 后来学者逐渐把其他方法应用到了规则挖掘中来，这些方法包括神经网络、 粗糙集理论、概率理论等。这些知识在规则挖掘中的应用，大大丰富了规则的挖 掘方法，提高了规则挖掘的效率。 1 33 基于粗糙集的关联规则挖掘研究 基于粗糙集提取规则的方法就是应用粗糙集理论进行规则挖掘的方法。规则 的提取主要依据决策信息表来进行。该方法的一般过程是： ( 1 ) 对数据进行预处理，建立决策信息表； ( 2 ) 进行属性约简； ( 3 ) 提取规则 进行属性约简，根据一般的方法，首先要考虑x 的所有l2 。 2 畔个子集。 其次，对于每一个子集瓦，需要计算s ，( j ，) ，这样，对于每个子集互，计算 s n ( y ) 的时间复杂性是0 ( 1 4 卜l u l 2 ) 。因此，整个代价是d ( 2 心l1 4 u 1 2 ) 。找 所有约简的时间复杂性是指数的。与之类似规则提取的时间复杂性也是指数的。 首先因为粗糙集它是一种刻划不完整性和不确定性的数学工具，能有效地分 析不精确( i m p r e d s e ) 、不一致( i n c o n s i s t e n t ) 、不完整( i n c o m p 】e t e ) 等各种不完备的信 息，还可以对数据进行分析和推理，从中发现隐含的知识、揭示潜在的规律。因 此它无需提供问题所需处理的数据集合之外的任何先验信息。其次较之基于频繁 集的方法，规则易获得、含义明了、可解释性强。虽