（计算机系统结构专业论文）一种基于粗糙集的不完备信息处理方法研究.pdf

硕十学位论文 摘要 在现实数据库知识发现过程中，由于数据采集能力有限或数据丢失等原因， 使得所面临的数据库往往是不完备的信息系统，即可能存在部分对象的某些属性 值未知的情况。空缺数据的处理非常关键，因为不完备的数据能够使知识挖掘过 程陷入混乱，导致不可靠的输出，将严重影响挖掘的效果。粗糙集理论作为一种 处理模糊、不确定知识的数学方法，其显著的优点是无需提供所需处理的数据集 合之外的任何先验信息，近年来已在知识发现上取得了令人瞩目的研究成果。目 的，基 ：羊n 糙集理论的不完备信息系统知识发现的理论框架已基本完整，但在具 体知识获取的多样性及知识质量的提高方面还需要进一步努力。 本文的主要工作就是以粗糙集理论为工具，对知识发现过程中信息不完备问 题的处理方法进行研究，以提高知识发现的质量和效率。不完备信息系统的知识 发现有两种实现途径：一是采用数据补齐算法对缺失值进行填充，在完备化的信 息系统基础上进行知识获取；二是在不改变原不完备信息系统的基础上直接进行 知识获取。本文从这两种途径入手，利用粗糙集的方法，提出了两个不完备信息 处理的有效算法。首先，分析了目前数据补齐算法存在的缺陷及产生这些缺陷的 原因。通过对拓展粗糙集理论模型作进一步的改进，并合理引入分治思想，提出 了。种新的数据补齐算法。结合理论分析和实例阐述了算法的有效性，并通过在 u c i 机器学习数掘库中选取的两个数掘集上进行实验，验证了该算法不仅能够提 高补齐率，而且能显著降低算法复杂性。其次，本文在不改变原不完备信息系统 的基础上，分析了现有知识约简算法的局限性，扩展定义了不完备熵概念，与传 统聿日糙熵结合，对不完备信息系统中的属性重要性进行了定义，并以此作为启发 式信息，提出了一种优化的不完备信息系统知识约简算法，与传统方法相比能够 找出更优的最小约简。通过理论和实例分析说明了算法的有效性。 关键词：知识发现；粗糙集：不完备信息系统；数据补齐；知识约简 二登茎王塑堡墨箜至塞鱼堕垦竺翌查鲨坚塑 a b s t r a c t i nt h ep r o c e s so fk n o w l e d g ed i s c o v e r yi n d a t a b a s e s ，p e o p l eo f t e n f a c e i n c o m p l e t ei n f o r m a t i o ns y s t e m ，t h a ti s ，as u b s t a n t i a lp r o p o r t i o no ft h ed a t am a yb e m i s s i n gi nr e a l w o r l da p p l i c a t i o n s i ti sv e r yi m p o r t a n tt od e a lw i t hi n c o m p l e t ed a t a ， b e c a u s ei tm a yl e a dt oc o n f u s i o na n di r r e s p o n s i b l eo u t f l u t si nd a t am i n n i n g a san e w m a t h e m a t i c a lt o o lf o rd e a l i n gw i t hi n e x a c t ，u n c e r t a i n t yo r v a g u ek n o w l e d g e ，t h e r o u g hs e tt h e o r yh a sg o tg r e a ts u c c e s si nk d d i nr e c e n ty e a r s ，a n dt h em o s tp r o m i n e n t a d v a n t a g ei st h a t ，i tn e e d so n l yt h ed a t ap r o v i d e di nt h ei n f o r m a t i o ns y s t e m s ，r e l y i n go nn o o t h e rm o d e la s s u m p t i o n s a tp r e s e n t ，t h et h e o r e t i c a lf r a m eo fk d di ni n c o m p l e t ei n f o r m a t i o n s y s t e mb a s e do nr o u g hs e tt h e o r yi sb a s i c l l yc o m p l e t e d ，b u tt h ev a r i e t ya n dq u a l i t yo f k n o w l e d g ee x t r a c t e di ss t i l ln e e dt ob ei m p r o v e d t h em a i nw o r ko ft h i sp a p e ri st og i v ei n - d e p t hs t u d yo nt h ep r o c e s s i n gm e t h o d o fi n c o m p l e t ed a t ap r o b l e mu s i n gr o u g hs e tt h e o r y ，t oi m p r o v et h eq u a l i t ya n d e f f i e n c yo fk d d t h e r ea r et w o m e t h o d so fk d d i ni n c o m p l e t ei n f o r m a t i o ns y s t e m s ： o n ei st oc o m p l e t et h ei n c o m p l e t ei n f o r m a t i o ns y s t e mf i r s t ，a n dt h e ne x t r a c t k n o w l e d g eb a s e do nt h ec o m p l e t e ds y s t e m ；t h eo t h e ri st oe x t r a c tk n o w l e d g ed i r e c t l y f r o mt h ei n c o m p l e t ei n f o r m a t i o ns y s t e mw i t hn oc h a n g eo no r i g i n a ls y s t e m ，t h i s p a p e rs t a r t sw i t ht h i st w ok i n d sm e t h o d ，p r o v i d e st w on e wa l g r i t h m su n d e rr o u g hs e t t h e o r yt oi m p r o v et h ek d dp e r f o r m a n c e f i r s t l y , t h i sp a p e ra n a l y z e st h el i m i t a t i o no f d a t af i l l i n ga l g o r i t h m si ne x i s t e n c e ，e x t e n d st h ev a l u e dt o l e r a n c er e l a t i o nm a t r i xi n r o u g h s e tt h e o r y ，i n t r o d u c e sd i v i d e a n d c o n q u e ri d e a ，a n dt h e np r o v i d e san e w a l g o r i t h mr s d i d a t h ee x p e r i m e n t a lr e s u l td e m o n s t r a t e st h a ti ti m p r o v e st h ef i l l i n g r a t i oa n de f f i c i e n c yg r e a t l y s e c o n d l y , t h i sp a p e rp r o v i d e sa no p t i m i z e dk n o w l e d g e r e d u c t i o na l g o r i t h mf o ri n c o m p l e t ei n f o r m a t i o ns y s t e mw i t hn oc h a n g eo no r i g i n a l s y s t e m i tf i r s ta n a l y z e st h el i m i t a t i o no ft r a d i t i o n a lr o u g he n t r o p ya n dc o r r e l a t i v e k n o w l e d g er e d u c t i o na l g o r i t h m ，e x t e n d st h ei n c o m p l e t ee n t r o p y ，w h i c hd e s c r i b e st h e u n c e r t a i n t yo fk n o w l e d g em o r ep r e c i s e l y ，a n dt h e n u s e sr o u g he n t r o p ya n dn e w i n c o m p l e t ee n t r o p yt od e f i n ea t t r i b u t es i g n i f i c a n c e a c c o r d i n g l y , t h en e wk n o w l e d g e r e d u c t i o na l g o r i t h mi sp r o v i d e d t h ee x a m p l ea n a l y s i sp r o v e si t sv a l i d i t y k e yw o r d s ：k n o w l e d g ed i s c o v e r y ；r o u g hs e t ；i n c o m p l e t ei n f o r m a t i o ns y s t e m ； d a t af i l l i n g ：k n o w l e d g er e d u c t i o n 硕士学位论文 插图索引 图1 1 论文结构3 图2 1f a y y a d 定义的数据库知识发现过程5 图2 2r o s e t t a 的图形用户界面1 5 图3 1 h 糙集概念示意图1 9 图4 1 补齐算法平均分类精确度比较3 8 图4 2 补齐算法运行时间比较3 8 图4 3 补齐算法补齐率比较3 8 i l l 一种基于粗糙集的不完备信息处理方法研究 附表索引 表3 1 不完备信息系统& 2 2 表3 2 瓯的容差关系矩阵瓦2 3 表3 3s 。的量化容差关系矩阵乃2 4 表4 1 氐的扩充区分矩阵肘3 0 表4 2 & 的改进量化容差关系矩阵毛3 2 表4 3 不完备信息系统s o 3 4 表4 4 不完备信息系统卵3 5 农4 ，5 不完备信息系统掣3 5 表4 6s o 经r s d i d a 算法补齐后的完备信息表3 5 表4 7s o 经r o u s t i d a 算法补齐后的完备信息表s ”3 5 表4 8h a y e s 数据集上的时间与补齐率测试结果一3 7 表4 9h a y e s 数掘集上的精确度测试结果一3 7 表4 1 0i r i s 数掘集上的时i 日j 与补齐率测试结果3 8 表4 1 1i r i s 数掘集上的精确度测试结果3 8 表5 1 信息表一4 2 表5 2 信息表二4 2 表5 3 信息表二三4 2 表5 4。个小完备的汽车信息表4 3 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 7 k 七羟日期：硼年1 月了。日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密卧 ( 请在以上相应方框内打“”) 作者签名： 丧髟荔 刷磁哆知。次 日期：卅年1 月即日 日期：刎年1 月弓。日 硕+ 学位论文 1 1 课题背景和意义 第1 章绪论 随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，使得 无论是商业企业、政府部门或是科研机构，在短时间内都积累了海量的数据资料。 i f 这蝗数掘庞大而繁杂，仅仅依靠数据库的查询检索机制和统计学方法已经远 远小能满足现实的需要了，迫切需要新技术和工具以便从海量的数据中智能地抽 取有价值的知识，从而达到为决策服务的目的。一个新的涉及人工智能和数据库 等学科的研究领域一一数据库知识发现( k 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 k d d ) 应运而生。知识发现是指能够从大型数据库中识别出有效的、新颖的、潜在有 用的，以及最终可理解的模式的非平凡处理过程，目前已成为一项重要研究课题。 尽管作为知识发现核心技术的数据挖掘【2 l ( d a t am i n i n g ，d m ) 技术日渐成熟， 但大都是基于理想数据的假设。在实际中，由于数据采集能力有限或数据丢失等 原因，使得所面临的往往是不完备信息系统，即可能存在部分对象的某些属性值 未知的情况。对于以知识发现为目的的数据挖掘任务而言，缺失数据的处理是很 重要的【3j ，因为不完备的数掘使得数据集中知识的不确定性成分增加，对确定性 知识的获取更难把握，且缺失数据易使挖掘过程陷入混乱，导致不可靠的输出， 这将严重影响挖掘的效果。因此，合理地处理缺失数据是一个非常关键的问题。 不完备信息系统的知识发现过程有两种实现途径1 4 j ：一是采用数据补齐算法 对缺失值进行填充，进而在完备化的信息系统上进行知识获取；二是在不改变原 不完备信息系统情况下直接进行挖掘，以获取知识。但无论采用何种途径和工具， 目前的研究方法都还没有达到最佳的效果，有待于深入研究。 粗糙集理论1 5j 是由波兰学者z p a w l a k 于1 9 8 2 年提出的。它是一种处理模糊 和不确定性知识的数学工具，可以对数据进行分析和推理，从中发现隐含的知识， 且具有非同寻常的简单实用性。粗糙集理论及其拓展模型为不完备信息的处理奠 定了良好的基础，既可以为不完备信息系统提供简单有效的补齐算法，又可以在 不改变不完备信息系统的基础上直接进行知识获取。它与统计方法、证据理论等 其它处理不完备性问题的方法相比，最显著的优点是无需提供所需处理的数据集 俞之外的任f o j 先验信息。因此，粗糙集理论对数掘的分析更具客观性。粗糙集理 论所具备的这些特性使得它成为k d d 中不完备信息处理的一种有效方法，对这 种基于粗糙集理论的不完备信息处理方法的研究具有十分重要的现实意义。 一种基丁祖槌集的不完备信息处理方法研究 1 2 研究内容 目前，基于粗糙集方法的不完备信息处理主要有以下几个研究方向： ( 1 ) 理论拓展 经典粗糙集理论研究的对象是完备信息系统，它以等价关系为基础，在保持 信息系统分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。 对于不完备信息系统，由于等价关系的要求过于严格，传统理论不再适用，因此 必须进行理论拓展。目前已有很多学者在进行这方面的研究，提出了一些比较成 功的拓展模型，如将等价关系放宽为要求相对宽松的容差关系i6 1 、非对称相似关 系【 、量化容差关系【7 1 、限制容差关系【8 】等等。 ( 2 ) 数据补齐 对于不完备信息系统，工程中常用的处理方法是先通过数据补齐算法对缺失 值进行填充，再在完备化的信息系统上进行知识提取。基于粗糙集理论的不可区 分关系1 9 j ，在信息系统中寻找相似对象对含有缺失值的对象进行补齐的方法，充 分利用了同类对象间的共性，产生的规则相对较集中，为数据补齐开辟了一条新 途径。但目前已有算法的补齐效果还不够理想，对现有算法的改进很有必要。 ( 3 ) 知识约简 知识约简h o 是粗糙集理论的重要内容之一，合理的约简能有效浓缩信息系统 的规模，并产生知识的精简集合及有意义的规则集合，提高知识获取的效率和准 确率。对于不完备信息系统，租糙集及其拓展理论既支持在补齐后的完备信息系 统上进行约简，又支持在不完备信息系统上直接进行知识约简。由于一个信息系 统可能存在多个约简，因此，求取一个信息系统所有约简的算法研究和寻找信息 系统最优约简的算法研究成为目前知识约简的两个研究目标。 ( 4 ) 规则提取 粗糙集及其拓展理论同样支持在完备和不完备的信息系统基础上进行规则提 取。现有的规则提取算法往往求取不完备信息系统中过多的或全部的规则，这使 得算法在大规模信息系统上难以实现，而且过多的知识在应用中并不一定有好的 效果【4 j 。因此在知识的产生和验证过程中加入相应的限制度量以提高产生知识的 质量也是研究的重点。 针对不同的应用环境，研究方向的侧重点也不同。本文的研究涉及了上述前 三个研究方向：一是针对缺失数据补齐的需要，对拓展粗糙集中的量化容差关系 模型进行了改进；二是基于这种改进，提出了一种新的不完备数据补齐算法，以 提高效率和补齐率；三是结合熵理论，对现有寻找不完备信息系统知识约简的算 法进行改进，提出了更优的约简算法。 2 硕十学位论文 1 3 本文的主要工作 本文以戈识发现为背景，以粗糙集理论为工具，围绕不完备信息处理的问题 展丌研究，主要工作具体内容如下： ( 1 ) 对知识发现的定义、过程及研究意义进行总结。剖析现实数据库中数据 缺失的原因及对缺失数据进行处理的重要性和复杂性，对目前不完备信息 处理的途径和方法进行分类和总结。 ( 2 ) 分析比较粗糙集理论在不完备信息处理上较其它方法的优势，对经典粗 糙集理论在不完备信息系统中的几种拓展模型进行评价，并总结现有基于 粗糙集理论的不完备信息处理方法。 ( 3 ) 分析现有基于粗糙集的数据补齐算法的不足，并针对这些不足之处提出 改进方案，以得到新的数掘补齐算法。编写程序实现算法，结合r o s e t t a 软件，在从u c i 机器学习数据库中选取的数据集上进行实验验证，并与同 类方法进行结果比较。 ( 4 ) 对基于粗糙熵的传统知识约简算法的局限性进行分析，针对求取不完备 信息系统最优约简的需要，重新定义属性重要性。以此作为启发式信息， 提出改进的知识约简算法，并通过实例进行验证。 1 4 论文的结构 第1 章绪论 第2 章相关研究综述 第3 章不完备信息系统中的拓展粗糙集理论 第4 章基于粗糙集理论 的不完备数据补齐算法 第5 章一种优化的不完 备信息系统知识约简算法 结论 图1 1 论文结构 一种基于粗糙集的不完备信息处理方法研究 第2 章相关研究综述 2 1 信息系统与知识发现 数据库知识发现的研究对象是存储于数据库中的数据集。目前，关系数据库 应用广泛，并且具有统一的组织结构、一体化的查询语言，关系之间及属性之间 具有平等性等优点【1 1 1 。因此，数据库知识发现的研究非常活跃。在关系数据库中， 每个数掘集都用二维表形式进行组织。在知识发现的过程中，这种以二维表形式 表示的数掘集，被研究者称之为信息系统。 2 1 1 信息系统 随着关系数据库技术的迅速发展，为便于数据的分析处理，现实世界中的海 黾信息，通常用一个二维信息表来统一表示，称为信息系统【9 】( i n f o r m a t i o n s y s t e m ) 。在这种二维信息表中，每一行是一个元组，对应于现实世界中的一个个 体，称为对象( 实例、实体) ，每一列代表对象的一个特征，称为属性。信息表中 的数据可以是从任意领域，诸如财务、医药或军事等领域中收集的。下面给出信 息系统的形式化定义。 定义2 1 1 四元组s ； 称为一个信息系统，其中，u = kl i = 1 , 2 ，以 表示对象的非空有限集合，称为论域；彳= 溆i i = l 2 朋 表示属性的非空有限集合； 用圪表示属性a 的值域，则v = t 3 圪( a a ) 表示属性集a 的值域；f 表示u x a 寸v 的一个信息函数，它为每个对象在每个属性上赋予一个信息值，即对v x u ， 口爿， 有力g ) 圪。 对象z 在属性口上的取值无g ) 也可用口b ) 形式来表示。 定义2 1 2 在信息系统s 中，当爿又可迸一步划分为两个不相交的集合：条 件属性集c 和决策属性集d ，即满足a = c u d 且c n d = m 时，信息系统称为决策 系统，其中，d 一般只含有个属性。 通常s = 也简记为s = 。容易看出，信息系统中一个属性对 应一个等价关系，一个表可以看作是一族等价关系。 2 1 2 知识发现 2 1 2 i 知识发现的定义 数据库知识发现( k 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 ，k d d ) 是从数据集中识 别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡处理过程。 4 硕士学位论文 这是由f a y y a d 等人对k d d 做出的最权威的定义。 知识发现的步骤为【1 2 1 ：先熟悉相关领域的知识。建立目标数据集并专注所选 择( s e l e c t i o n ) 的数据子集，再从目的数据中作预处理( p r e p r o c e s s i n g ) ，然后作数 掘简化与转换工作( t r a n s f o r m a t i o n ) ，再经由数据挖掘( d a t am i n i n g ) 技术生成模式 ( p a t t e r n s ) ，做回归分析或找出分类型态，最后经过理解评估( i n t e r p r e t a t i o n e v a l u a t i o n ) 成为有用的知识。这些程序是一个循环的关系，一直重复的步骤，最 后才得到一些有用的知识。所以，k d d 是一连串的程序。也有人将k d d 称为“资 料考古学”( d a t aa r c h a e o l o g y ) ，“数据模式分析”( d a t ap a t t e r na n a l y s i s ) 或“功 能相依性分析”( f u n c t i o n a ld e p e n d e n c ya n a l y s i s ) 。不论以何种形式出现，现在对 这些概念都己形成一个共识，即认为它们是数据库系统与机器学习技术相结合的 重要领域。 2 1 2 2 知识发现的过程 f a y y a d 于1 9 9 6 年给出了数据库知识发现过程模型，如图2 1 所示。这是 公认的通用知识发现过程定义。 消除噪音 r 不完备数据填充 j +j 类型转换 ，| ， 选择 预处理变换挖掘评价 j 。 j ，数据准备一 图2 1 f a y y a d 定义的数据库知识发现过程 从图中可以看出，知识发现的过程可概括为三部分：数据准备、数据挖掘和 结果的解释评估。 数据准备包含三个子过程，即数据选择、预处理和数据变换。数据选择是根 掘用户需要，从原始数掘库中选取组用于进行知识发现的数据，这组数据称为 目标数据；数据的预处理包含消除噪音、不完备数据填充、数据类型转换如连续 h ，鞣 1 7 叩 ，据掘 一数挖 一种基丁粗糙集的不完备信息处理方法研究 数据的离散化等过程；数据变换的主要目的是对数据集进行降维处理，即通过约 简，消除冗余特征，找出依赖于获取目标的表达数据的主要特征或变量个数，以 降低知识挖掘过程和最终获取的知识模式的复杂性。 数掘挖掘阶段的首要问题是明确数据挖掘的任务，如分类、聚类、关联规则 挖掘等。确定了挖掘任务后，就要根据数据的不同特点及用户或实际运行系统的 要求，选择恰当的挖掘算法进行处理。 结果的解释评估阶段要完成两项任务。首先是对挖掘阶段发现的模式进行评 估，判定是否存在冗余模式或不满足用户要求的模式，对于冗余模式要进行删除， 对于模式不满足用户要求的情况，需要整个发现过程回退至前续阶段，重新选取 算法甚至目标数据等：其次，由于知识发现最终是要面向人类用户的，因此有可 能需要对前阶段发现的模式进行可视化处理，转换为易于用户理解的表示形式， 如“i f t h e n ”规则形式。 2 2 不完备信息处理研究现状 由于数据测量的误差、数据获取的限制、存储介质的故障等等原因，使得数 据缺失的现象是不可避免的。因此，现实数据库中的数据，常常是不完备的。在 知识发现的过程中，由于不完备的数据很可能便挖掘技术受到严重影响，因此， 时数捌库中不完备信息的处理非常重要 3 】。 2 2 1 不完备信息系统 2 2 1 1 定义 所谓不完备信息系统 ”( i n c o m p l e t ei n f o r m a t i o ns y s t e m ) ，即存在某些属性值 缺失的信息系统。在一个信息系统中，如果论域中某个对象的属性值未知时，我 们称它在该属性的取值为空值( n u l lv a l u e ) 。下面给出不完备信息系统的形式化定 义。 定义2 2 1 四元组s = 是一个信息系统。其中u = x ，l f = 1 ，2 ，刀 表 示对象的非空有限集合，彳= ki k = l 2 , 耐表示属性的非空有限集合，用圪表示属 性a 的值域，则v = u 圪( 口a ) 表示属性集爿的值域：厂表示u x 彳专y 的一个信息 函数，它为每个对象在每个属性上赋予一个信息值。如果对于至少一个属性口a ， 屹包含空值，则称s 是一个不完备信息系统，记为i i s 。 本文约定，定义2 2 。l 所描述的不完备信息系统中，对象一在属性吼上的取 值用q “) 表示，空值用符号“”表示。当彳又可进一步划分为两个不相交的集 合：条件属性集c 和决策属性集d ，即满足a = c u d 且c n d = 中时，s 称为不完 备决策系统。 硕士学位论文 2 2 1 2 数据缺失的原因 数扼缺失的现象是多种原因造成的。现实情况下，有些数据受客观条件限制 无法观测到，或在数掘录入过程受人为因素影响导致数据缺失，或由于存储介质 的故障、传输媒体的故障等导致数据缺失，或数据被隐藏等等。总结起来，可以 归纳为如下几类【1 4 l ： 1 ) 有些信息无法获取。例如在医疗数据库中，随着先进医疗设备的不断引进， 病人临床检查的项目是不断变化的，在引进新设备前进行临床检查的病人记录中 就不存在新设备检查的结果，致使一部分属性值空缺出来。 2 ) 有些信息是被遗漏的。可能是因为输入时认为不重要、忘记填写了或对数 据理解错误而遗漏，也可能是由于数据采集设备的故障、存储介质的故障等原因 而互失了。 3 ) 有些对象的某个或某些属性是不可用的。即对于某个对象来说，该属性值 是不存在的，如对于一个未婚者来说，它在配偶姓名属性上的值就是不存在的。 4 ) 获取这些信息的代价太大。 5 ) 有些信息( 被认为) 是不重要的。如一个属性的取值与给定语境是无关的， 或训练数狲库的设计者并不在乎某个属性的取值( 称为d o n t ，c a r ev a l u e ) “。 6 ) 系统实时性能要求较高，即要求得到这些信息前迅速做出判断或决策。 2 2 2 数据缺失机制和空值语义 在对缺失数据进行处理前，了解数据缺失的机制和形式是十分必要的【l ”。将 数锯集中不合缺失值的变量( 属性) 称为完全变量，数据集中含有缺失值的变量称 为不完全变量，l i t t l e 和r u b i n 定义了以下三种不同的数据缺失机制【6 】： t ) 完全随机缺失( m i s s i n gc o m p l e t e l ya t r a n d o m ，m c a r ) 。数据的缺失与不 完全变量以及完全变量都是无关的。 2 ) 随机缺失( m i s s i n ga tr a n d o m ，m a r ) 。数据的缺失仅仅依赖于完全变量。 3 ) 非随机、不可忽略缺失( n o tm i s s i n ga tr a n d o m ，n m a r ，o rn o n i g n o r a b l e ) 。 不完全变量中数据的缺失依赖于不完全变量本身，这种缺失是不可忽略的。 空值的来源有许多种，因此现实世界中的空值语义也比较复杂。总的说来， 可以把空值分成以下三类【1 7 , 1 8 1 ： 1 ) 存在型空值，即数据遗漏( m i s s i n g ) 。对象在该属性上取值是存在的，只 是暂时无法知道。一旦对象在该属性上的实际值被确知以后，人们就可以用相应 的实际值来取代原来的空值，使信息趋于完全。存在型空值是不确定性的一种表 征，该类空值的实际值在当前是未知的，但它有确定性的一面，诸如它的实际值 确实存在，总足落在一个人们叮以确定的区i 日j 内。般情况下，空值是指存在型 空值。 一种基丁粗糙集的不完备信息处理方法研究 2 ) 不存在型空值，即数据缺席( a b s e n t ) 。对象在该属性上无法取值，如一个 未婚者的配偶姓名。该类空值不能与任意值相比较( 匹配，相等) 。 3 ) 占位型空值，即无法确定是存在型空值还是不存在型空值，这要随着时间 的推移才能够清楚，是最不确定的一类。这种空值除填充空位外，并不代表任何 其它信息。 2 2 3 不完备信息处理的重要性和复杂性 数据缺失在许多研究领域都是一个复杂的问题，也是智能数据处理中经常遇 到的技术难点。数据库中某些个别记录在某些属性上可能存在空值现象，给发现、 评估和解释一些重要的模式带来了困难。空值的存在会产生以下影晌【1 4 】；首先， 系统丢失了大量的有用信息：其次，系统中所表现出的不确定性更加显著，系统 中蕴涵的确定性成分更难把握；再次，包含空值的数据会使数据挖掘过程陷入混 乱，导致不可靠的输出。因此，对含有缺失数据的不完备信息系统进行处理，是 知识发现过程中非常重要的步骤。 作为知识发现核心技术的数据挖掘算法本身更致力于避免数据过分适合所建 的模型，这一特性使得它难以通过自身的算法去很好地处理不完备数据。因此， 空缺的数据需要通过专门的方法进行推导、填充等，以减少数据挖掘算法与实际 应用之间的差距。 2 2 4 不完备信息处理的方法 不完备信息系统的知识发现过程一般有两种途径【4 】：一是首先通过数据补齐 算法对缺失值进行填充，使信息表完备化，然后利用现有的数据挖掘技术在完备 的信息系统基础上进行知识获取；二是在不改变原不完备信息系统的前提下直接 处理，获取知识。下面将着重讨论不完备数据的补齐方法和在不完备信息系统上 商接进行知识获取方法的研究现状。 2 2 4 1 数据补齐方法 数据补齐就是通过专门的方法，利用已有的值或经验值，对不完备信息系统 中的空值进行推导、填充，使不完备信息系统转化为完备信息系统。目前已有的 数据补齐方法可分为如下几类( 1 8 , 1 9 ： ( 1 ) 人工填写( f i l l i n gm a n u a l l y ) 。由于最了解数据的还是用户自己，因此这 个方法产生数据偏离较小，填充效果较好，但很费时。当数据规模很大、空值很 多的时候，该方法是不可行的，也与目前数据处理的智能化发展趋势不一致。 ( 2 ) 特殊值填充( t r e a t i n gm i s s i n g a t t r i b u t ev a l u e sa ss p e c i a lv a l u e s ) ，即将空 值作为一种特殊的属性值来处理，它不同于其它的任何属性值。如所有的空值都 用“u n k n o w n ”填充，一个不完备的信息表就成了完备的信息表。但该方法可能 8 硕七学位论文 导致严重的数据偏离，般不推荐使用。 ( 3 ) 将存在空缺属性值的对象记录删除，从而得到一个完备的信息表。这种 方法简单易行，虽然不是严格意义上的数据补齐，但在信息表数量巨大而有缺失 值的对象数量远远小于信息表对象总量时，是一种可取的处理方法。但它是以减 少历史数据来换取信息的完备，会造成资源的浪费，丢弃了大量隐藏在这些对象 中的信息，特别是当缺失数据较多时，会严重影响到信息表信息的客观性和结果 的j 下确性。 ( 4 ) 从信息表中选取所有可能的值，或通过计算估计一个最可能的值来填充 守缺值。该类补齐方法根据选取填充值的方法不同，包含的具体算法也分为多种， 如： 基于统计学原理，根据信息表中其余对象在该属性上取值的分布情况来对缺 失属性值进行估计补充，如( 条件) 平均值填充( m e a n m o d e c o m p l e t e r ) 、( 条件) 组合完整化方法( c o m b i n a t o r i a lc o m p l e t e r ) 等。这类方法不会影响信息表中包含的 信息量，但这些统计技术常常依赖于一些统计假设如概率分布等，由于数据集的 状念空问巨大，对这些分布假设的判定常常是困难的。 利用回归 20 l ( r e g r e s s i o n ) 方法归纳确定空值。首先基于完整的数据集，建立 回归方程( 模型) ，对于包含空值的对象，将己知属性值代入方程来估计未知属性 值，以此估计值来进行填充。陔方法当变量不是线性相关或预测变量高度相关时 会导致有偏差的估计。 利用贝叶斯模型【2 1 】( b a y e s i a nm o d e l ) 和证据理论【2 2 】( e v i d e n c et h e o r y ) 也是比 较常见的数据补齐方法，但贝叶斯模型需要知道概率密度，而证据理论则需要证 掘函数，这些数据之外的信息往往很难得到。 在羊h 糙集理论中，t z u n g p e ih o n g 等人【2 3 】利用上下近似提出了一种填充空值 并同时提取规则的方法，但这种方法无法处理空值较多的信息系统。另一种基于 粗糙集理论的补齐方法是利用不可区分关系在信息表中选取一个与含有缺失值的 对象最相似的对象，用这个最相似对象的值来对缺失值进行填充 9 , 2 4 】。该方法充 分利用了同类对象f 日j 的共性来进行空值估计，概念上很简单，符合客观规律，是 。种填充效果较好的数掘补齐方法，在本文第4 章中将给出详细介绍。 在商业软件l e r s f 2 5 1 中，提到一种处理空值的方法：用所有可能的取值代替 空值( a s s i g n i n g a l lp o s s i b l e v a l u e so f t h e a t t r i b u t e ) ，根据不同的组合把不完备信 息系统转化为完备信息系统。这种方法当信息系统中空值较多时计算复杂度过高， 效率极其低下同时得到的知识也并非可靠。另外有一种方法【2 “，对空值进行填 充的原则是一样的，不同的只是从决策相同的对象中尝试所有的属性值的可能情 况，而不是根据信息表中所有对象进行尝试，这样能够在一定程度上减小原方法 的代价。 一种基丁租糙集的不完备信息处理方法研究 期望值最大化方法【2 7 l ( e x p e c t a t i o nm a x i m i z a t i o n ，e m ) 是一种在不完备数据情 况下计算极大似然估计或者后验分布的迭代算法。在每一迭代循环过程中交替执 行两个步骤：e 步，在给定完备数据和前一次迭代所得到的参数估计的情况下计 算完备数据对应的对数似然函数的条件期望：m 步，用极大化对数似然函数来确 定参数的值，并用于下步的迭代。算法在e 步和m 步之间不断迭代直至收敛，即两 次迭代之间的参数变化小于一个预先给定的阈值时结束。该方法可能会陷入局部 极值，收敛速度也不是很快，并且计算很复杂。 利用属性之间的关联来估计空值。如c 4 5 方法【2 8 】就是通过寻找属性间的关系 柬对空值进行填充。它寻找之蚓具有最大相关性的两个属性，其中没有遗失值的 一个称为代理属性，另一个称为原始属性，用代理属性决定原始属性中的遗失值。 但这种基于规则归纳的方法只能处理基数较小的名词型属性。 2 2 4 2 直接获取知识的方法 对于含有空值的不完备信息系统的处理，除了上述数据补齐方法外，还可以 直接在包含空值的数据集上进行知识获取【2 弘引1 。这类方法包括贝叶斯网络、证据 理论、人工神经网络和粗糙集方法等等。 贝叶斯网络【2 9 l 是用来表示变量间连接概率的图形模式，它提供了一种自然的 表示因果信息的方法，用来发现数据间的潜在关系。但该方法仅适合于对领域知 识具有一定了解，或至少对变量问的依赖关系较清楚的情况。因为如果直接从数 掘中学习贝叶斯网络的结构，不但复杂性高，网络维护代价昂贵，而且它的估计 参数也较多，容易给系统带来高方差，影响预测精度。当在任何一个对象中的空 值数量很大时，会存在指数爆炸的危险。 证掘理论【3 0 j 利用置信函数和似然推理函数作为主要工具，对不确定性问题进 行处理，以区间的形式给出信任度，既强调证据的客观作用，又强调人的判别作 用，能够很好地应用到不完备信息系统的知识发现上。但该理论非常依赖于先验 知识的支持，如对基本概率的赋值，对属性、数据或知识等局部的信念，以及计 算全局信念的函数等均需要凭借系统设计者的经验事先给定。 人工神经网络j 是由具有可调节权值的阈值逻辑单元组成，通过不断调节权 值，直至动作计算表现令人满意来完成学习。在数据挖掘应用中可使用径向基函 数等方法处理不完备数据，有效的对付空值。但目前该技术应用于数据挖掘主要 存在两大障碍，即神经网络学到的知识难于理解，且学习时间太长，不适于大型 数掘集。因此，人工神经网络在这方面的研究还有待进一步深入展开。 基于粗糙集的数据分析方法具有简单、客观的优点。经典粗糙集理论以完备 信息系统为研究对象，针对不完备信息系统，需要进行理论拓展，使其能在不改 变原信息系统的前提下直接对不完备信息系统进行处理。在针对不完备信息系统 o 硕士学位论文 的各种粗糙集拓展模型中，比较成功的有m k r y s z k i e w i c z 6 】提出的容差关系模型， j s t e f a n o w s k i 和a t s o u k i a s 7 】提出的非对称相似关系模型和量化相容关系模型， _ 1 i h 胤| s i 提出的限制容差关系模型等。在这些拓展粗糙集模型下，由等价关系拓 展而来的各种二元关系奠定了进步研究不完备信息系统的粗计算、知识约简和 规则提取的基础，可以不用对系统中的缺失值进行任何处理而直接进行知识获取。 对基于租糙集的直接知识获取方法，将在本文3 3 节进行讨论。 2 3 粗糙集理论研究现状 2 3 1 粗糙集理论的发展与特点 2 0 世纪8 0 年代初，波兰学者z p a w l a k 和一些波兰科学院、波兰华沙大学的 逻辑学家们，在从事关于信息系统逻辑特性的研究基础上，提出了粗糙集理论。 1 9 8 2 年，z ，p a w l a k 发表了经典论文“r o u 【g hs e t s ”【5 l ，宣告了祖糙集理论的诞生。 粗糙集理论自提出以来，很多学者都对其理论和应用进行了研究，取得了大 量的成果。特别是2 0 世纪8 0 年代末和9 0 年代初在知识发现等领域得到了成功的 应用，受到了国内外的广泛关注。 l9 91 年，z p a w l a k 出版专著“r o u g hs e t s ：t h e o r e t i c a la s p e c t so fr e a s o n i n g a b o u td a t a ” 3 2 】，系统全面地阐述粗糙集理论，为粗糙集理论奠定了严密的数学 基础，成为粗糙集理论研究的第一个里程碑。它与1 9 9 2 年出版的粗糙集理论及应 用专著1 3 3 ，极好地总结了这一时期租糙集理论与实践的研究成果，也进一步促进 了羊h 糙集理论的发展，推动了国际上对粗糙集理论和应用的研究。 自1 9 9 2 年在波兰k i e k r z 召开第一届国际粗糙集理论研讨会后，每年都要召 开以粗糙集为主题的国际会议。1 9 9 4 年国际上成立了粗糙集学会( i n t e r n