（计算机应用技术专业论文）基于粗糙集理论的分类规则挖掘.pdf

摘要 随着数据库技术的发展和信息时代的来l 临各行各业都积累了大量的数据，数据 库中存储的数据量急剧增加。因此，为了提高工作效率和生活质量，人们必须获取 蕴藏在其中的有价值的信息。为了达到这个目的，人们开始致力于从数据库中发现 知识的研究。然而，众所周知，数据库中往往存在j 几余数据、缺失数据、不确定的 数据和不一致的数据等诸多情况，这些数据成了发现知识的一大障碍。 租糙集理论是1 9 8 2 年p a w l a k 提出，经历了2 0 多年的发展，己经在理论和应用上 取得了丰硕的成果。它不依赖于数据集之外的附加信息，是处理含有噪声、不精确、 不完整数据的有力工具。许多知识发现技术仅仅适用于精确集，不适用于租糙集， 而现实中粗糙集是普遍存在的现象，因此基于粗糙集的知识发现模型在信息系统的 研究领域具有重要意义。 本文首先介绍了知识发现的历史、现状和可能的发展方向，并回顾了它的主要 方法和技术。然后，论文对粗糙集理论进行了介绍，并对数据挖掘中的各环节运用 粗糙集理论的方法进行了分析。接着论文研究了在数据缺失或信息不完备的情况下 基于粗糙集理论进行分类规则的挖掘。结合前人的研究成果提出一种从不完备信息 系统中提取有用的关系和规则的综合性方法。另外从租糙集和决策树两种方法具有 的优势互补性出发，提出了一种基于租糙集的决策树生成方法。通过例子和实验，说 明这两个方法的有效性。 关键词：数据挖掘，粗糙集，分类，不完备信息系统 a b s t r a ct w i t hd e v e l o p m e n to fd a t a b a s et e c h n o l o g ya n dt h ec o m i n go f 山f o r m a t i o ne r a 1 a r g e a m o u n to fd a t ai sa c c u m u l a t i n gi nm a n yi n d u s t r i e s t h ev o l u m e so ft h ed a t a b a s ea r e z o o m i n g i no r d e rt oi m p r o v et h ee f f i c i e n c yo fw o r ka n dq u a l i t yo fl i f e ，p e o p l eh a v et o d e r i v ev a l u a b l ek n o w l e d g ee m b e d d e di nd a t af r o md a t a b a s e s f o rt h ea i m ，p e o p l eh a v e b e g u nt h e r es e a r c ho nk n o w l e d g ed i s c o v e r yi nd a t a b a s e s a sw ea l lk n o w ，h o w e v e r , u s u a l l yt h e r ee r er e d u n d a n td a t a , m i s s i n gd a t a , u n c e r t a i nd a t aa n di n c o n s i s t e n td a t ai nt h e d a t a b a s e sa n dt h e yb e c o m eag r e a tb a r r i e rt oe x l a a c t i n gk n o w l e d g ef r o md a t a b a s e s r u n g hs e t s ( r s ) t h e o r yw a sp u tf o r w a r db yp a w l a kz d z i s l a wi n19 8 2 a f t e rm o r e t h a n2 0y e a r so f d e v e l o p i n g ，i th a sr e c e i v e df r u i t f u la c h i e v e m e n t si nb o t hoft h e o r ya n d a p p l i c a t i o n s r sd o e s n td e p e n do na d d i t i o n a li n f o r m a t i o nb e y o n dt h ed a t aw h i c hi sa p o t e n tt o o lf o rd e a l i n gw i t hi m p r e c i s e ，i n c o m p l e t e v a g ea n du n c e r t a i nd a t a s o m e t r a d d i t i o n a lm e t h o do fk n o w l e d g ed i s c o v e r yi so n l ys u i t a b l ef o rp r e c i s es e tn o tf o rr o u g h s e t s i n c em a n ys e to fd a t ai nr e a ll i f ei sr o u g h ，t h em o d e lo fk n o w l e d g ed i s c o v e r yb a s e d o nr o u g hs e t st h e o r yp l a y sa ni m p o r t e n tt ol ei ni n f o r m a t i o ns y s t e m f i r s t l y , t h eh i s t o r y ，s t a t u sa n dp o s s i b l ed e v e l o p m e n td i r e c t i o no fk d da r ei nt r o d u c e d a n dt h em a i nm e t h o d sa n dt e c h n i q u e so fk d da r ea l s or e v i e w e d s e c o n d l y ，t h er o u g h s e t st h e o r yi si n t r o d u c e da n dg e n e r a la p p l i c a t i o np r o c e d u r eo fr o u g hs e t st h e o r yi nk d d i sa n a l y z e d i nt h ep a p e r ，a no v e r v i e wo f t h ec u r r e n ts i t u a t i o no f r e s e a r c h e so nr o u g hs e t , a n dt h em a i ni s s u e sr e l a t e dt ot h ei n c o m p l e t ed a t ap r o b l e ma n dt h ec o m m o n l y - u s e d m e t h o d so fh a n d l i n gi n c o m p l e t ed a t ap r o b l e m sa r ed e t a i l e d o nr e s e a r c hr e s u l t so f p r e d e c e s s o r sb a s i s 。ac o m p r e h e n s i v em e t h o di sp r o p o s e d ，w h i c hc a ns i m u l t a n e o u s l y d e r i v er u l e sf r o mi n c o m p l e t ed a t as e t sb a s e do nr o u g hs e t s i na d d i t i o n , r o u g hs e t sa n d d e c i s i o nt r e eh a v ec o m p l e m e n t a r yc h a r a c t e r i s t i c s an e wa p p r o a c ht o g e n e r a t i o na d e c i s i o n ，t r e eb a s e do nr o u g hs e t si st h u sp r o p o s e dc o m b i n i n gb o t ha d v a n t a g e s t h e e x p e r i m e n tr e s u l t ss h o wt h a tt h e s em e t h o d sa d v a n c e da n dp r a c t i c a k e y w o r d s ：d a t am i n i n g ；r o u g hs e tt h e o r y ；c l a s s i f i c a t i o n ；i n c o m p l e t ei n f o r m a t i o n s y s t e m j i 独创性声明 本人声明所呈交的学位沦文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，沦文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得 或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名= 碚翠 签字哺扣二年印月。，弓目 学位论文版权使用授权书 本学位论文作者完全了解 有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 琴群屯 i 签字日期：o 一1 年4 月j 日 学位论文作者毕业去向： 工作单位： 二通i 凡 出匀 ： 导师签名 净p 懒 签字日期：犹司年4 - 月形日 电话 嶂编 第一章绪论 第一章绪论 1 1 论文的选题背景及意义 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据 越来越多。激增的数据背后隐藏着许多重要信息，人们希望能从海量的数据中发现 其中潜在有用的关系和规则，从而做出对未来发展趋势的预测。然而，现有的数据 库技术和专家系统技术都无法达到这个目的。数据挖掘正是为满足人们的这种需要 而产生并迅速发展起来的一门交叉学科，有着非常广阔的应用前景，是当前的研究 热点之一。 数据库中隐藏着许多可以为商业、科研等活动的决策提供所需要的知识。分类 可用来抽取能够描述重要数据集合的模型。分类方法用于预测数据对象的离散类别。 分类是数据挖掘的一个主要方法，人们在分类这个领域做了大量的工作，获得了很 多行之有效的方法。分类是找出一个类别的要领描述，它代表了这类数据的整体信息， 即该类的内涵描述，一般用规则或决策树模式表示。分类规则的建立可以预测准确 度、计算复杂度及优化模式的简洁度。粗糙集( r o u g hs e t ) 理论是二十世纪八十年代 由波兰科学家p a w l a k 提出的一种新的处理不精确、不确定和模糊知识的软计算工 具，近年来己成为一种重要的数据挖掘与知识获取方法。粗糙集理论认为知识就 是基于对对象分类的能力。它的内在的分类特点使得它尤其适合于发现分类规则。 结合粗糙集方法的分类自然成为一个重要的研究方向。 在数据挖掘的分类过程中所常使用的一些方法有基于决策树的分类，贝叶斯分 类器，神经网络分类方法，基于关联的分类方法，k 一最近临方法，基于示例推理， 遗传算法，模糊集合方法，粗糙集方法。这些方法就是在数据挖掘的分类过程中所 常使用的一些方法，它们各自有自己的优点，同时也各有不足，没有一个分类算法 在对所有数据集上进行分类学习均是最优的。如何克服这些方法内在的缺陷，提高 这些方法的性能，是当前数据分类问题中研究的热点。将各个方法相融合，取长补 短，有机高效得整合在一起，是当前探索的个热点，再有一种趋势是将别的学科 基丁粗糙集理论的分类规则挖掘 的知识应用到当前的算法中，来改善当前的方法。 由于粗糙集独有的观点，使它具备一些其它分析方法所不具备的特点。粗糙集 方法不需要先验知识。租糙集是一个强大的数据分析工具。它能在保留关键信息的 前提下对数据进行化简并求得知识的最小表示； 能识别并评估数据之间的依赖关 系， 揭示出概念简单的模式； 能从经验数据中获取易于证实的规则知识。 原始数据是知识和信息提取的源泉，对于数据挖掘十分重要。现实世界中，由 于数据测量方面的错误、对数据理解或获取的限制以及数据录入时的疏忽等原因， 使得在数据挖掘时往往面临的是不完备信息系统。对于以建立模型和知识发现为目 的的数据挖掘任务而言，空缺数据的处理是很关键的，因为不完备的数据能够使挖 掘过程陷入混乱，导致不可靠的输出。目前所进行的关于数据挖掘的研究工作，大 多着眼于数据挖掘算法的探讨而忽视了对现实数据复杂多样性的考虑。许多数据挖 掘模型或算法的研究都是建立在理想数据之上的，对其处理的数据集合的完整性一 般也都有要求，这样挖掘出来的规则和知识与实际应用存在一定的差距。另一方面， 不完备信息系统中所表现出来的不确定性更加显著，系统中蕴涵的确定性成分更难 把握，这大大增加了数据挖掘的难度，许多数据挖掘方法难以通过自身的理论和算 法去很好地处理不完备数据。正确处理缺失数据是数据挖掘的一个难点问题，从不 完备信息系统中发现有用的关系和规则也是数据挖掘的重要研究方向之一。基于粗 糙集理论对不完备信息系统进行数据挖掘具有以下几大优势： ( 1 ) 数据库中的关系表可以看作粗糙集理论中的信息表，从而为基于粗糙集 方法的数据挖掘奠定了基础。 ( 2 ) 粗糙集理论无需提供问题所处理数据集之外的任何先验知识。它能在保留 关键信息的前提下对数据进行化简并求得知识的最小表示； ( 3 ) 粗糙集识别并评估数据之间的依赖关系，揭示出概念简单的模式；能从 经验数据中获取易于证实的规则知识 ( 4 ) 粗糙集理论，算法简单、易于操作，并且有利于并行执行。 ( 5 ) 利用粗糙集方法，可以发现数据库中数据的异常，排除数据挖掘过程中的 噪声干扰，大大提高挖掘效果。 ( 6 ) 现实世界中的规则有确定性的，也有不确定性的，而不完备信息系统中不 第一章绪论 确定成分更多。从数据库中发现不确定性的知识，为粗糙集方法提供了用武之地。 ( 7 ) 租糙集以完善的数学理论为基础，由粗糙集方法得出的决策知识便于用数 学方法进一步处理，并且由柑糙集方法得出的规则更易于理解。 ( 8 ) 对传统粗糙集理论进行适当扩充后建立不完备信息系统的粗糙集模型，可 以直接处理缺失数据而不必先进行数据完备化处理。 基于以上分析，本文将粗糙集理论应用在分类挖掘和不完备信息系统中，旨在 通过对粗糙集理论和数据挖掘数据的研究，为分类研究和不完备信息系统中的数据 挖掘找到新的分析处理方法，减少数据挖掘研究与现实应用之间的差距：同时丰富粗 糙集的基本理论，扩展粗糙集的应用领域。 1 2 国内外研究现状 在众多的数据挖掘方法中，大多应用与发展了数理统计、机器学习、模式识别 等，而近年来粗糙集理论在数据挖掘中的应用也有了很大的进展，基于粗糙集方法 已成为数据挖掘主流方法之一。 属性约简和规则提取是粗糙集理论中非常重要的内容，同时也是基于粗糙集的 数据挖掘过程的核心步骤。属性约简方面己经发展了许多基于不同属性重要性度量 的前向、后向、双向约简算法、自寻优算法、动态约简算法等：规则提取方面则有基 于核值的规则提取算法、基于概率的最大覆盖算法、基于投影的软规则提取算法、 基于二元属性的规则生成算法，等等”1 。 面向属性的归纳方法是数据挖掘的重要技术之一。h u x h 等”1 提出了一种将基 于属性的归纳方法和租糙集方法相结合的方法，首先使用面向属性的概念树爬升技 术对属性进行泛化，然后使用粗糙集方法计算约简并生成规则。 经典的粗糙集理论缺乏对复杂系统的处理机制，z i a r k o w “1 提出了可变精度 的粗糙集模型，通过引入集合的两种相对误分度，对集合包含运算进行了推广，以 利于在不确定信息情况下使用。 将租糙集与模糊集、神经网络、遗传算法相结合，也是提高数据挖掘能力与效 率的一条重要途径。 在基于粗糙集的应用系统方面，国外已开发了不少数据挖掘系统，其中具有代 基f 粗糙集理论的分类规则挖掘 表性的有k d d r ，l e r s ，r o s e t a ，r o u g h d a s r o u g h c l a s s ，d a t a l o g i c r 和p r i m e r o s e 等。 国内，以粗糙集理论为基础的数据挖掘软件主要有中国科学院计算技术研究所研制 的知识发现工具k d t 和南京大学研制的通用知识挖掘工具k n i g h t 虽然基于粗糙集的 数据挖掘技术研究已经取得了很大进展，然而以上这些研究都仍然没有超脱完备信 息系统的环境。目前国内外涉足不完备信息系统下粗糙集理论研究的人还很少。接 下来对该领域极其有限的研究成果做简要的介绍： 1 9 9 7 年，m k r y s k i e w i c z 提出了不完备信息系统的基于容差关系的粗糙集模型及 其知识约简方法，还比较了几种不完备信息系统的数据分析方法“。 1 9 9 9 年，j st e f a n o w s k i 等人区分了不完备信息系统的两个不同语义：“遗失值” 语义和“缺省值，语义，引入了非对称相似关系“缺省值”语义，在此基础上提出 了基于非对称相似关系的租糙集扩展模型“2 0 0 1 年，s t e f a n o w s k i 又提出了基于量 化容差关系的粗糙集模型”3 2 0 0 2 年王国胤在对以上三个模型分析的摹础上提出了基于限制容差关系的粗糙 集扩展模型。1 ，赵卫东等人基于m k r y s k i e w i c z 的容差关系对传统的粗糙集理论在 不完备信息系统下进行了初步的拓展“。2 0 0 3 年张宏宇等人则是基于 m k r y s k i e w i c z 的容差关系，提出了不完备信息系统下的交精度粗糙集模型“ 而在属性约简和规则提取方面，国内外学者己提出了在对不完备决策表进行规 则提取的同时补充遗失值的算法“、基于最大相容块技术的规则提取算法“、分层 递阶约简算法“”和基于散列的约简算法“，这些算法是在m k r y s k i e w i c z 模型理论框 架下提出的：基于非对称相似关系，则有求解不完备信息系统最小约简的遗传算法 “”。除此之外，也有学者拓展了粗糙集理论的一些相关概念，提出了新颖的规则提 取方法“7 ”1 。以上算法大部分都是在2 0 0 4 年及之后提出的。 以上文献显示出，粗糙集方法在不完备信息系统中的应用越来越受到学者们的 关注。然而，将粗糙集应用于不完备信息系统仍有很多方面工作有待完成：首先，这 几个模型都各自存在局限性，有待改进：其次，基于不完备信息系统的知识约简和规 则提取算法研究还没有真正开展起来；在应用系统方面，目前还没有针对性强、能够 很好地对不完备信息系统进行分析处理的数据挖掘系统。因此，基于租糙集理论对 不完备信息系统进行数据挖掘，无论在理论上还是应用上都有待深入研究和发展， 4 第一章绪论 这为本文的研究提供了契机。 1 3 论文的主要工作 本文从处理不完备信息系统的各种数据挖掘技术入手，在对粗糙集理论研究 的基础上，将粗糙集理论应用于对不完备信息系统的数据挖掘中。论文主要完成了 以下几个方面的工作： 1 、研究了数据挖掘技术，数据挖掘存在的问题与闲难，对数据挖掘中的数据不 完备问题展开了探讨，归纳总结了处理不完备数据的常用方法。 2 、研究了租糙集的基本理论和方法，讨论了粗糙集应用于数据挖掘的现状和面 临的问题。 3 、在前人研究的基础上提出了不完备信息系统的约简和决策规则集提取算法， 并通过实例和实验说明了算法的有效性。 4 、提出了一个用粗糙集的方法将信息系统中的决策表进行数据约简得到极小化 决策规则集，然后在极小化规则集的基础上构造出近似最优决策树的方法。 1 4 论文的组织结构 第一章绪论 介绍了论文的选题背景，阐述了论文选题的意义，并对本课题的国内外研究现 状进行了介绍。 第二章数据挖掘 首先对数据挖掘进行了概述：详细阐述了数据挖掘的定义，研究了数据挖掘的过 程、目标、任务、对象和方法，指出了数据挖掘中存在的问题和用难。 第三章粗糙集理论概述 介绍了其基本概念及知识约简方法，研究了其在数据挖掘中的应用。 第四章基于粗糙集的不完备信息系统的分类规则提取 提出了针对实用性用途的基于条件信息量的最大分布约简的不完全信息粗糙集 处理方法。并验证了其有效性。 第五章基于粗糙集和决策树理论的分类挖掘方法 基于粗糙集理论的分类规则挖掘 在粗糙集和决策树理论的基础和方法上提出构造近似最优决策树方法。举例并 用实验说明其有效性。 第六章总结 对论文工作进行了总结，对后续研究讲行了展望。 6 第二章数据挖掘 第二章数据挖掘 2 1 数据据挖掘概述 2 1 1 数据挖掘的定义 数据挖掘( d a t a m i n i n g ) 就是指从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程“”“数据挖掘”常常和另一个术语“数据库中知识发现( k n o w l e d g e d i s c o v e r i n gd a t a b a s e ，或k d d ) ”一起出现。1 9 9 6 年，f a y y a d ，p i a t e t s k y - s h a p i r o 并1 1 s m y t h 对k d d 和数据挖掘的关系进行了阐述：k d d 是识别出存在于数据库中有效的、新颖的、 具有潜在效用的、最终可理解的模式的非平凡过程，而数据挖掘则是该过程中的一 个特定步骤。“但是，随着该领域的不断发展，研究者们目前趋向认为k d d 和数据挖掘 具有相同的含义，即认为数据挖掘就是从大型数据库中提取人们感兴趣的知识。“数 据挖掘”主要流行于统计界、数据分析、数据库和管理信息系统( g l s ) 界：而“k d d ” 主要流行于人工智能和机器学习界。 数据挖掘是一门来自各种不同领域的研究者关注的交叉性学科，受多个学科的 影响，最主要的包括：数据库技术、统计学、人工智能、机器学习、模式识别、高性 能计算、可视化技术、信息科学等。 2 1 2 数据挖掘的过程 数据挖掘，b u k d d 过程是一个由多个步骤相互连接起来的、交互的迭代过程( 如 图2 1 所示) ，包括许多由用户参与给出决策的步骤。“。 ( 1 ) 数据清理：消除噪声和不一致数据： ( 2 ) 数据集成：多种数据源可以组合在一起； ( 3 ) 数据的选择：从数据库中检索与分析任务相关的数据； ( 4 ) 数据的变换：数据变换或统一成适合挖掘的形式； ( 5 ) 数据挖掘：使用智能方法提取数据模式； ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式； 7 基于粗糙集理论的分类规则挖掘 ( 7 ) 知识表示：使用可视化和只是表示技术，向用户提供挖掘的指示。 知识 清理，雏成 删2 1 数据挖掘过程 2 1 3 数据挖掘任务 数据挖掘的两个高层目标是描述和预测。描述性挖掘试图刻画数据库中数据的 一般特性：而预测性挖掘则根据当前数据进行推导，已进行预测。根据可以发现的 模式类型，将数据挖掘任务归纳为以下几类： ( 1 ) 概念类描述 数据库中通常存放大量的细节数据，然而用户往往希望以简洁而精确的描述形 式来观察汇总的数据。这种数据描述可以提供一类数据的概貌。或可将它与其他类 相区别。这种描述性数据挖掘就称为概念描述。 ( 2 ) 分类和回归 分类是寻找描述数据或概念的模型或函数的过程，以便能够使用这些模型来预 测类标号未知的对象所属的类。这些模型基于对训练数据集的分析而得到，可以用 多种形式表示，如分类规则、判定树、数学公式或神经网络等。 回归则是通过具有已知值的变量来预测其他变量的值和分类方法不同的是，分 类输出的是离散的类别值，而回归输出的则是连续数值。 ( 3 ) 聚类分析 与分类回归不同，聚类在处理数据对象时不考虑标号，而时根据最大化类内的相 似性最小化类间的相似性的原则对数据对象进行聚类或分组的聚类分析可以建立 宏观的概念发现数据的分布模式，以及可能的数据属性之间的相互关系。 第。二章数据挖掘 ( 4 ) 关联分析 关联分析用于发现大量数据中项集之间有意义的关联或相互关系，寻找给定数 据集中项之间的有趣联系关联规则的支持度和置信度是两个规则兴趣度度量，他们 分别反映发现规则的有用性和确定性。 ( 5 ) 孤立点分析和演变分析 数据库中可能包含一些数据对象与大部分的一般行为或模式不一致，称为孤立 点大部分数据挖掘方法将孤立点视为噪声或例外丢掉，然而在一些应用如欺诈检测 中，罕见的事件可能比正常出现的事件更有趣针对孤立点的数据分析称为孤立点挖 掘。 数据演变分析描述行为随时间变化的对象的规律或趋势，它包括趋势分析、相似 性查找、序列模式挖掘、周期性模式分析等方面。 2 1 4 数据挖掘的对象 按照存储格式，用语挖掘的对象有关系数据库、面向对象数据库、数据仓库、 文本数据库、多媒体数据库、空间数据库、时态数据库、异质数据库以及w e b 等。目 前，关系数据库仍然是最主要的数据挖掘对象。 2 1 5 数据挖掘方法 数据挖掘受多个学科的影响，因此根据数据挖掘方法所属领域的不同可以分为 如下几类：数学统计方法机器学习方法、面向数据库的方法及其他方法，如可视化 和信息科学等。 具体的说，主要有以下几种数据库挖掘技术。“： ( 1 ) 决策树：利用信息论中的信息增益寻找数据库中具有最大信息量的字段， 建立决策树的一个结点，再根据字段的不同取值建立树的分枝，在每个分枝子集中 重复建树的下层结点和分支的过程，即可建立决策树。 ( 2 ) 神经网络方法：在结构上模拟人脑神经元结构，通过训练来学习，是一个 具有联想记忆力功能的非线性模型，可用于分类、回归和聚类等。但用神经网络来 进行数据挖掘存在着以下几个问题：神经网络很难解释；神经网络会学习过度；除 非问题非常简单，训练一个神经网络可能需要相当可观的时间才能完成：建立神经网 络需要做的数据准备工作量很大。 9 基于粗糙集理论的分类规则挖掘 ( 3 ) 覆盖正例排斥反例方法：利用覆盖所有正例、排斥所有反例的思想来寻找 规则。比较典型的有m i c h a l s l d 举j a q ll 方法、洪家荣改进的a q l 5 方法，以及洪家荣的 a e 5 方法。 ( 4 ) 粗糙集方法：一种处理含糊和不确定问题的新的数学工具。利用租糙集可 以处理的问题包括数据约简、数据相关性的发现、数据意义的评估、由数据产生决 策算法、数据中范式的发现及因果关系的发现等。 粗糙集理论作为数据挖掘的一种方法，近年来得到了计算机研究领域的广泛关 注和青睐。这不仅是因为它具有良好的数学基础和性质，而且还因为它恰好反映了 人们用粗糙集方法处理不分明问题的常规性，即以不完全信息或知识去处理一些不 分明现象的能力，或依据观察、度量到的某些不精确的结果而进行分类数据的能力。 租糙集理论也不是万能的，对建模而言，尽管粗糙集理论对知识不完全的处理 是有效的。但是，由于这个理论未包含处理不精确或不确定原始数据的机制，因此， 单纯地使用这个理论不一定能有效地描述不确定或不精确的实际问题。同时，由于 粗糙集理论只能作用于具有离散值的系统，其应用领域也受到了局限。这意味着， 需要其他方法的补充。 ( 5 ) 可视化技术：数据与结果被转化和表达成可视化形式，如图形、图象等， 使用户对数据的剖析更清楚。 ( 6 ) 其他方法：云模型方法、概念树方法、遗传算法、模糊论方法、公式发现、 s v m ( 支持向量机) 等。 2 1 6 数据挖掘存在的问题与困难 现实的数据库本身固有的一些性质会对数据挖掘的发展产生不利影响 ( 1 ) 动态数据。大多数数据库的内容经常变化。在一个在线系统中，必须采用 预警机制来保证这些变化不会导致错误的发生。 ( 2 ) 噪声和不确定性。错误的数据对于现实的数据库是难免的。不确定性可能 同时存在于时间和空间上，时间上的不确定性即是动态数据：空间上的不确定性是指 发现的模式可能只在一部分数据上有效，或指建造数据库时所采集的数据本身的不 确定性。 ( 3 ) 冗余数据。重复的数据或多余的信息会给模式提取带来困难，也将导致用 1 0 第二章数据挖掘 户对抽取出来的知识不感兴趣。 ( 4 ) 稀疏数据。导致抽取出来的模式不能反映整体情况，或者抽取模式如同大 海捞针，难度很大。 ( 5 ) 不完整数据。也称不完全或不完备数据，即有些数据属性的值缺失的情况。 后面将针对这个问题展开研究讨论。 ( 6 ) 大规模数据。搜索空间的庞大是知识发现系统的一大难题，它会影响到算 法的效率甚至可行性。 2 2 数据挖掘的数据缺失问题及处理方法 2 2 1 造成数据缺失的原因 在各种实用的数据库中，属性值缺失的情况经常发生甚至是不可避免的。因此， 在大多数情况下，信息系统是不完备的，或者说存在某种程度的不完备。造成数据 缺失的原因是多方面的，主要有以下几种。“： ( 1 ) 有些信息暂时无法获取。例如在医疗数据库中，并非所有病人的所有l 临床 检验结果都能在给定的时间内得到，致使一部分属性值空缺出来。又如在某申请表 数据中，对某些问题的反映依赖于对其它问题的回答。 ( 2 ) 有些信息是被遗漏的。可能是因为输入时认为不重要，忘记填写或对数据 理解错误而遗漏，也可能是由于数据采集设备、存储介质、传输媒体的故障等一些 人为因素而丢失了。 ( 3 ) 有些对象的某个或某些属性是不可用的。也就是说，对于这个对象来说， 该属性值是不存在的，如一个未婚者的配偶姓名、一个儿童的固定收入状况等。 ( 4 ) 有些信息( 被认为) 是不重要的。如一个属性的取值与给定语境无关，或 训练数据库的设计者并不在乎某个属性的取值。 ( 5 ) 获取这些信息的代价太大。 ( 6 ) 系统实时性能要求较高，即要求得到这些信息前迅速作出判断或决策。 2 2 2 数据缺失机制 在对缺失数据进行处理前，了解数据缺失的机制和形式是十分必要的。将数据 集中不含缺失值的变量( 属性) 称为完全变量，数据集中含有缺失值的变量称为不 基丁粗糙集理论的分类规则挖掘 完全变量，l i r l e 和r u b i n 定义了以下三种不同的数据缺失机制”“： ( 1 ) 完全随机缺失。数据的缺失与不完全变量以及完全变量都无关。 ( 2 ) 随机缺失。数据的缺失仅仅依赖于完全变量。 ( 3 ) 非随机、不可忽略缺失。不完全变量中数据的缺失依赖于不完全变量本身， 这种缺失不可忽略。 2 2 3 空值语义 对于某个对象的属性值未知的情况，称它在该属性的取值为空值。空值的来源 有许多种，因此现实世界中的空值语义也比较复杂。总的来说，可以把空值分成以 下三类： ( 1 ) 不存在型空值。即无法填入的值，或称对象在该属性上无法取值，如一个 未婚者的配偶姓名等。 ( 2 ) 存在型空值。即对象在该属性上取值是存在的，但暂时无法知道。一旦对 象在该属性上的实际值被确知以后，人们就可以用相应的实际值来取代原来的空值， 使信息趋于完全。 ( 3 ) 占有型空值。即无法确定是不存在型空值和还是存在性空值，这要随着时 间的推移才能够清楚，是最不确定的一类。这种空值除填充空位以外，并不代表任 何其它信息。 2 2 4 空值处理的重要性和复杂性 数据缺失在许多研究领域都是一个复杂的问题。对数据挖掘来说，空值的存在， 造成了以下影响：首先，系统丢失了大量的有用信息；第二，系统中所表现出的不 确定性更加显著，系统中蕴涵的确定性成分更难把握；第三，包含空值的数据会使 挖掘过程陷入混乱，导致不可靠的输出。 数据挖掘算法本身更致力于避免数据过分适合所建的模型，这一特性使得它难 以通过自身的算法去很好地处理不完整数据。因此，空缺的数据需要通过专门的方 法进行推导和填充等，以减少数据挖掘算法与实际应用之间的差距。 2 2 5 空值处理方法的分析比较 处理不完备数据集的方法主要分为以下三大类： ( 一) 删除元组 第二章数据挖掘 也就是将存在遗漏信息属性值的对象( 元组，记录) 删除，从而得到一个完备 的信息表。这种方法简单易行，它在对象有多个属性缺失值、被删除的含缺失值的 对象与信息表中的数据量相比非常小的情况下是非常有效的，在类标号( 假设是分 类任务) 缺少时通常使用该方法。然而，这种方法却又有很大的局限性。它是以减 少历史数据来换取信息的完备，会造成资源的大量浪费，丢弃了大量隐藏在这些对 象中的信息。在信息表中本来包含的对象很少的情况下，删除少量对象就足以严重 影响到信息表信息的客观性和结果的准确性，当每个属性空值的百分比变化很大时， 它的性能非常差。因此，当缺失数据所占比例较大，特别当缺失数据非随机分布时， 这种方法可能导致数据发生严重偏离，从而引出错误的结论。 ( 二) 数据补齐 这类方法使用一定的值去填充空值，从而使信息表完备化。通常基于统计学原 理，根据决策表中其余对象取值的分布情况来对一个空值进行填充，譬如用其余属 性值的平均值来进行填充等。数据挖掘中有以下几种常用的补齐方法”3 ： ( 1 ) 人工填写 由于最了解数据的还是用户自己，因此用这个方法产生的数据偏离较小，可能 是填充效果最好的一种。然而，一般来说，该方法很花费时间，当数据规模很大， 空值很多的时候，该方法是不可行的。 ( 2 ) 特殊值填充 将空值作为一种特殊的属性值来处理，它不同于其它的任何属性值。如有的空 值都用“ ”填充。这样将形成另一个有趣的概念，可能导致严重的数据偏离，一般 不推荐使用。 ( 3 ) 平均值填充 将信息表中的属性分为数值属性和非数值属性来分别进行处理。如果空值是数 值型的，就用该属性在其它所有对象的取值的平均值来填充该缺失的属性值；如果 空值是非数值型的，就根据统计学中的众数原理，用该属性在其它所有对象的取值 次数最多的值( 即出现频率最高的值) 来填充该缺失的属性值。另外有一种与其相 似的方法叫条件平均值填充法。在该方法中，缺失属性值的补齐同样是通过对该属 性在其它对象中的取值求平均得到，但不同的是用于求平均的值并不是从信息表所 基于粗糙集理论的分类规则挖掘 有对象中去取，而是从与该对象具有相同决策属性值的对象中取得。这两种数据的 补齐方法，其基本的出发点都是一样的，以最大概率可能的取值来补充缺失的属性 值，只是在具体方法上有一点不同。与其它方法相比，它是用现存数据的多数信息 来推测缺失值。 ( 4 ) 就近补齐 对于一个包含空值的对象，就近补齐法在完整数据中找到一个与它最相似的对 象，然后用这个相似对象的值来进行填充。不同的问题可能会选用不同的标准来判 定对象是否相似。该方法概念上很简单，且利用了数据间的关系来进行空值估计。 这个方法的缺点在于难以定义相似标准，主观因素较多。 ( 5 ) 使用所有可能的值填充 这种方法是用空缺属性值的所有可能取值来填充，能够得到较好的补齐效果， 但是，当数据量很大或者遗漏值较多时，其计算的代价很大，可能的测试方案很多。 另一种方法，填补遗漏属性值的原则是一样的，不同的只是从决策相同的对象中尝 试所有的属性值的可能情况，而不是根据信息表中所有对象进行尝试，这样能够在 一定程度上减小计算代价，但有可能无法将所有空值补齐。 ( 6 ) 组合完整化方法 这种方法是用空缺属性值的所有可能的属性取值来试，并从最终属性的约简结 果中选择最好的一个作为填补的属性值。这是以约简为目的的数据补齐方法，能够 得到很好的约简结果。但是，当数据量很大或者遗漏的属性值较多时，其计算的代 价也很大。另一种称为条件组合完整化方法，填补遗漏属性值的原则是一样的，不 同的只是从决策相同的对象中尝试所有的属性值的可能情况，而不是根据信息 表中所有对象进行尝试。条件组合完整化方法能够在一定程度上减小组合完整化的 代价。在信息表包含不完整数据较多的情况下，可能的测试方案将剧增。 其它还有：回归、期望值最大化方法和多重填补等。 ( 三) 不处理 所谓不处理，即不对数据集进行完整化处理，直接在包含空值的数据上进行数 据挖掘。 并不存在种处理空值的方法可以适用于任何问题。大多数的数据挖掘系统都 1 4 第二章数据挖掘 是在数据挖掘之前的数据预处理阶段采用第一、第二方法来对空缺数据进行处理。 这些方法各有优缺点，但无论哪种方式填充，都无法避免主观因素对原系统的影响， 而且在空值过多的情形下将系统完备化是不可行的。目前基于不确定信息理论处理 数据的不完备性已得到了广泛的研究。不完备数据的表达方式所依据的理论主要有 可信度理论、概率论、模糊集合论、可能性理论、d - s 证据理论等。 本课题研究所采用的粗糙集理论正是其中的一种，将经典粗糙集理论中的相关 理论作适当的拓展以适应不完备信息系统的处理。 基丁粗糙集理论的分类规则挖掘 第三章粗糙集基本概念 3 1 基本概念 定义3 1 ( 信息系统) 信息系统用一个列表的形式给出研究对象的信息， 表的行对应于研究对象，表的列对应于对象的属性。信息系统可表示为个四元组 s ：，a ，v ，j 其中? 是对象的非空有限集合，即论域ja 是属性的非空 优先集合。v 是属性的值域集，v 。uv a ，其中，v a 是属性日月的值域j e ，是信息函数，fj 月一v ，即，r x ，v a ，它指定中每一对象的属性 值。信息系统也称为知识表达系统，为了简化符号，通常也用s = d r , 创来代替s = tu a v ，f 1 。 定义3 2 ( 决策表) 决策表是一类特殊而重要的信息系统，多数决策问题都可 以用决策表形式来表达。 设s = ，a ，v ，f ，为一个信息系统，a = c u d ，c r d = 驴，c 称为条 件属性，d 称为决策属性。具有条件属性和决策属性的信息系统称为决策表。 一个决策表中决策属性有时是唯一的，称为单一决策；有时是不唯一的，称为多 决策。对于具有多个决策属性的决策表我们可以变换成为单一决策表，这样有利于 问题的简化和求解。 表3 1 给出了一个关于某些病人的信息系统，其中u = e l ，e 2 ，e 3 ，e 4 ， a = 头痛，肌肉痛，体温，流感) 。 为了直观方便u 也可以写成表的形式称为信息表。纵轴表示实例标记，横轴 表示实例属性，实例标记与属性的交会点就是这个实例在这个属性的值。 若表中 属性有决策属性与条件属性之分该表也称决策表。表3 1 就是一个决策表。第一行 表示对象的属性，该表有4 个属性，其中头疼、肌肉疼、体温是条件属性，流 感是决策属性。下面的每一行代表一个对象。 1 6 第三章粗糙集基本概念 表3 1 决策表 病人头痛肌肉痛体温流感 e l 是是正常否 e 2 否否高否 e 3 是 是 很高是 e 4 否是正常否 3 2 粗糙集 粗糙集是一种刻画不完整性和不确定性的数学工具。它通过约简能有效地发现 数据中起主要或决定性作用的因素，从而实现对数据的简化和提炼。同时粗糙集理 论扩展了经典的集合理论，在处理不准确和不完整信息方面表现出独有的优势，被 公认为是进行机器学习、知识获取、决策分析的有效工具 3 2 1 粗糙集理论的观点 粗糙集理论具有一些独特的观点这些观点使得粗糙集特别适合于进行数据分 析。如： ( 1 ) 等价类与不分明关系：对于论域设r 是定义在，上的一簇等价关系， r 对确定了一种分类，r 表示r 在上导出的所有等价类。每个属性集合p 可以认为是一个等价关系，因为任意两个元组x 、y 若它们在p 上的值都相等，则 说这两个对象之间是关于p 的不分明关系( i n d i s c e r n i b l er e l a t i o n ) 记作x p y ，它们 对于属性集p 来说是等价的，所以p 决定了一种等价关系用i n d ( p ) 表示， t i n d ( p ) 通常也写作t p 由于属性集与等价关系之间存在着一一对应关系这两个 概念是等价的，可以相互替换，因此，下面的讨论中，在不引起混淆的情况下，本 文不区分属性与等价关系。p 对u 同样可以给出一个划分。例如表3 1 中 令p = 头疼，肌肉疼】o p ：“e 1 ，e 3 ) ， e 2 ) ， e 4 ) ) 是属性p 对的划分，其中任 一子集称为一个等价类如 e ，e ，) 用 x ，表示在不分明关系p 下包含x 的等价 类， x ，= yly u a y p x ) 。 ( 2 ) 概念与知识：r s 理论认为概念是对象的集合体，因此对论域u ，子集x c _ u 基丁- 粗糙集理论的分类规则挖掘 称为上的一个概念，空集中也视为一个概念。论域中的任意概念簇称为关于 的抽象知识，简称为知识，它代表了对，中个体的分类。这样，知识可以定义为： 给定一组数据和等价关系集合r ，在等价关系集合r 下对数据集合的划分。 可见知识即是将对象进行分类的能力。分类后的每个等价类都是一个概念。因此粗 糙集中的等价关系和属性集常常也称知识。 如表3 1 中，设知识p = 【头疼，肌肉疼) 该知识可把分成 e 1 ，e 3 ，( e 2 ) ，( e 4 ) 三个概念。上分类的簇集( 即等价关系的簇集) 称为上的一个知识库。也就 是说，概念是对象的集合，知识库是分类方法的集合“” ( 3 ) 新型的隶属关系：粗糙集理论与传统的集合论不同，传统的集合论认为一 个元素要么属于这个集合要么不属于。粗糙集中定义了知识，若一个元素x ，包含 其的等价类 x ，属于集合x 才可以说x 在知识p 下完全属于x ，对表3 1 ，设知 识p = 头疼 给定集合x = e 1 ，e 2 ，e 3 ) ，e l ，e