（控制科学与工程专业论文）增量粗糙集及增量贝叶斯分类器算法研究与应用.pdf

增量耗l 集算法及增量贝叶斯分类器研究与应用 摘要 贝叶斯分类和粗糙集理论都是数据挖掘领域中的重要技术，在经济、金融、 科学观测和工程等各个领域广泛应用，是目前研究的热点。本文首先简要地介绍 了贝叶斯分类技术和粗糙集在挖掘上的发展和研究概况，阐述了当前研究的重点 和存在的难点。在给出了数据挖掘的基本概念之后，叙述了贝叶斯分类算法和粗 糙集算法的基本概念和算法原理，并详细介绍了数据预处理的各种情况与方法。 本文详细阐述了粗糙集理论的数学原理与方法，以及粗糙集在知识表达系统 中的简化和核的求取，并分析了基于粗糙集的静态约简和动态约简在数据挖掘中 模型的构建，针对动态约简中的不同抽样子集对决策表具有相同影响度的不足， 提出了一种概率抽样以子集权重的快速求解动态核的算法。对该模型的分析证明 了它的可行性。 针对贝叶斯分类器在高维多属性数据的情况下训练易受噪声干扰，鲁棒性不 强以及增量式贝叶斯分类器分类损失评估函数复杂度过高的情况。本文在朴素增 量贝叶斯分类器的基础上提出一种基于粗糙集动态约简的增量贝叶斯分类器学习 算法：通过分析原始数据集，挖掘出对分类最有利的极小值条件属性，将它作为 增量分类学习的输入属性。由于属性维度的减低及最大有利分类的属性存在，对 传统的增量式贝叶斯网络分类器在算法计算复杂度上有了一定的降低，也简化了 传统的分类损失评估函数，使贝叶斯分类器的增量学习效率得到了提高。仿真实 验表明，属性约简后的增量式贝叶斯网络分类器计算简单，有很好的实时性抗干 扰能力。 最后，在前面对数据挖掘技术的研究基础上，在实际氧化铝熟料烧成回转窑 智能控制系统中加入基于动态约简的增量贝叶斯网络分类器预测模块，并通过计 算机仿真及现场实验，证明了数据挖掘技术在氧化铝熟料烧成回转窑智能控制系 统的可行性。 关键词：贝叶斯分类器；粗糙集；增量挖掘；回转窑 l l 硕十学位论文 a b s t r a c t b a y e s i 姐c l a s s i f i e r 锄dr o u g l ls e t sa r ei m p o r 眦t e c l u l o l o g i e si i lt l l e 批m i i l i n gd o m 血， 诚d e l yu s e di i lv 撕o u sf i e l d ss u c h 弱i i lt h ee c o n o m i c ，f i i l a i l c i a l ，s c i e n t i f i co b s e r v a t i o n sa n d e n g i n e e r i n ga n d s oo n 1 1 1t i l ep a p e r h o wt og e tt h ec o r ew 弱e l a b o r a t e di nk n o w l e d g er e p r e s e n t a t i o ns y s t e ma n e r t h em a i np r i n c i p l ea l l dm e t h o do fr o u g hs e t sw 嬲i n 仃o d u c e d t h e nt l ：屺m 访i i l gm o d e lb a s e do n s 眦i cr e d u c t i o na n dd ”a m i cr e d u c t i o n 、a ss e p 撇_ t e l y 龇a l y z e d i nm ee n d ，a l lm g o r i t l l l i lw a s d i s c u s s e d ，w l l i c hc o u l dq u i c h yg e td ) r i l 锄i cc o r cw e i g h t e db y 廿1 ep r o b a b i l i 锣o fs u b - s e t s t h e 恤o r e t i c a lb a s i so fs u b - s e t sp r o b a b o l 姆w e i 曲t 、懈蚍s 锄p l i n gd i 疏r e n tn ：i l b e ro f s u b - s e t s l a i dd i f f e r e n t l ye 岱j c tf a c t o r st 0d e c i s i o nt a b l e t h ea i l a l y s i si m dp r 0 v e dm em o d e l f e 弱i b i l i 锣 d 埘n g 恤c a s eo 仆i 曲e rd i m e “o n a l 砒r i d u t e s 锄dl m g ed a t a 蛐，b a y e s i 趾c l 嬲s i f i e r s p a r a m e t e r s 砌1 1 i n gw a l se a s i l yd i s t u r b e db yn o i s e 锄dt l l ec l a s s i f i e r sr o b u s n l e s sw 硒n o tg o o d h 1m em e a r m r h i l e ，t 1 1 ec o m p l e x i 够o fi i l c r e m e n t 2 l le i a y e s i a i lc l a s s i f i e r sd a m a g e 硒s c s s m e n t m n c t i o nw 嬲t o ok 曲i i lo r d e rt 0s o l v em i sp r o b l e m ，a ni n c r e m e n t a lb a y e s i a l lc l a s s i f i e r l e a n l i n ga l g o r i t h j nb a s e d0 nd y i l a m i cr e d u c t i o nh a db e e np r o p o s e d t h ea l g o r i 咖nf i r s t l y 锄a l i z e dt l l eo r i g i n m s e t sm l dm i n e dt h em o s tf - a v o 阳b l ec o n d i t i o n 砌b u t e sf o r 吐l e c l a s s i f i 瑚m e dt h em i n i m u mc o n d i t i o na ：t t 抽u t e s a n dt l l ei i l c r e l n e n t 甜b a y e s i 觚c l a s s i f i e r c o u l db et 试n e da n dl e 锄e do i d yb y 廿l e s em o s tf - a 、r o r a b i ec o n d i t i o n 砌b u t e s b e c a u s eo f r e d u c e i n g l en 岫b e ro fc o n d i t i o n 砌b u t e s ，m a tc o u l dr e d u c en l ec o m p l e x i t ) ro fc l 嬲s i 丘e r s d a i l l a g ea s s e s s m e n t 劬c t i o n 锄de i l l 聊et 1 1 ec l a s s i f i e r si 1 1 c r e m e n t a ll e a m i n ge m c i e n c y a s e r i e so fe x l ) e r i m e n t sh a db e e nd o n et 0p r o v et l l ea l g o r i t h mi sp r a c t i c d b l e a tt l l e l a s t ，锄a p p l i c a t i o n o ft l l ei n c r e m e n t a lb a y e s i a nc l 舔s i f i e r2 l l g o r i t l l ma i l d i i l c f e m e n t 础m i i l i n ga l g o r i m mb a s e do nr o u g h t sw 弱p r e s e n t e d ，i i lm ea l u i i l i n am t a 巧l 【i l n a tm es a m et i m e ，am o d e lo fi n c r e m e n t a jb a y e s i a nc l 嬲s i f i e rb 嬲e do nd y r 姗i cr e d u c t i o n e w a sp r o p o s e di 1 1t l l e n l l 址d a t ap r e d i c t i o n f u t l l e m o r e ，1 1 j l l i l i n gt e s to ft l l em o d e lh a dr e c e i v e d g o o dp e o n n a i l c ei nf i e l d k e yw o r d ：b a y e s i a nc l a s s i f i e r ；r o u g hs e t s ；i n c r e m e n t a lm i n i n g ；r o t a r y “l n u i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 邵磅金，1 日期：力研年朋纠日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“) 作者签名：西p 刍1日期：立词年朋弓1 日 导师躲亨州眺m 年朋了f 日 硕上学位论文 1 1 研究背景 第1 章绪论 随着信息时代的到来，计算机、网络和通讯等信息技术和数据贮存技术的迅 速发展，数据存储量飞速增长。成千上万个数据库已用于商务管理、工业生产和 科学研究等领域。对于这些海量的数据，若采用传统的数据库管理系统和数据检 索机制，不仅耗费时间多，而且完全依赖于预先对数据之间关系的假设和估计， 已远远不能满足人们日益增长的对数据中隐含知识的渴求。如何有效地组织和 利用这些海量原始数据( r a wd a t a ) 分析现状和预测未来，是人们面临的一个巨大 挑战。数据挖掘( d a t am i n i n g ) 技术就此产生。 数据挖掘( d a t am i n i n g ) ，就是从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和 知识的过程【2 l 。它是一个新兴的边沿学科，它涉及多学科技术的集成，包括数据 库技术、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、 信息检索等等【3 l ，数据挖掘技术可以应用于决策、过程控制、信息管理等几乎所 以领域，例如超市业务数据、信用卡使用记录和d n a 数据、医疗数据等。多学 科的相互交融和相互促进，使得数据挖掘这一新兴学科得以蓬勃发展，而且己经 初具规模。因此，数据挖掘被信息产业界认为是数据库系统最重要的前沿之一， 是信息产业最有前途的交叉学科。 贝叶斯分类器和粗糙集约简理论都是数据挖掘技术的重要研究方向，其相关 研究在近年来都是飞速发展，理论框架趋于完整。在商业数据分析、工业生产控 制、医学研究等社会各方各面都有应用。 早在2 0 世纪8 0 年代末，9 0 年代初贝叶斯网络就广泛应用于医疗诊断了，其 中比较著名的包括p a t h f i n d er 【4 1 、m u n i n 【5 1 、c h i l d l6 1 、o m r d t 【7 1 等。这些 年来，贝叶斯网络在工业中的应用也越来越广，涉及金融分析、产品设计、生产 制作工艺、工业过程监控管理、在线故障诊断以及可靠性分析等等。另外，随着 机器学习在各社会领域的深入应用，贝叶斯网络已经成功应用于计算机系统、军 事应用、生态学、农牧业及气象学等领域。 2 0 世纪6 0 年代初，l a z a d e h 提出了模糊集，不少理论计算机科学家和逻辑 学家，试图通过这一理论解决g f r e g e 的含糊概念，但遗憾的是，模糊集是不可 计算的，没有给出数学公式描述这一含糊概念，故无法计算出它的边界线上的具 体的含糊元素数目。时隔2 0 年后的8 0 年代初，z p a w l a k 针对g f r e g e 的边界线 增量相l 集算泫及增量贝叶斯分类器研究j 应用 区域思想提出了粗糙集( ( r s ，或粗集) 【8 1 ，他把那些无法确认的个体都归于边界线 区域，而这种边界线区域被定义为上近似集和下近似集之差集。由于上近似集和 下近似集都可以通过等价关系给出确定的数学公式描述，所以含糊元素数目可以 被计算出来，即在真假二值之间的含糊程度可以计算，从而实现了g f r e g e 的边 界线思想。粗糙集理论主要兴趣在于它恰好反映了人们用粗糙集方法处理不分明 问题的常规性，即以不完全信息或知识去处理一些不分明现象的能力，或依据观 察、度量到的某些不精确的结果而进行分类数据的能力。 1 2 贝叶斯网络理论的发展与研究现状 贝叶斯网络又称为信念网络【9 1 ，是一种图型化的模型，能够图形化地表示一 组变量问的联合概率分布函数。一个贝叶斯网络包括了一个结构模型和与之相关 的一组条件概率分布函数。结构模型是一个有向无环图，其中的节点表示了随机 变量，是对于过程、事件、状态等实体的某特性的描述，边则表示变量间的概率 依赖关系。图中的每个节点都有一个给定其父节点情况下该节点的条件概率分布 函数。这样，一个贝叶斯网络就用图形化的形式表示了如何将与一系列节点相关 的条件概率函数组合成为一个整体的联合概率分布函数。因果贝叶斯网络是指具 有因果含义的贝叶斯网络，其中每个节点的父节点被解释为该节点相对于模型中 其它节点的直接原因。为了与之区别，有时也将没有因果意义的贝叶斯网络称为 概率贝叶斯网络。 1 7 6 3 年，英国数学家贝叶斯( t h o m a sb a y e s ) 撰写的一篇具有哲学性的论文关 于几率性问题求解的评论奠定了贝叶斯学派的基础。著名的数学家拉普拉斯 ( l a p l a c e p s ) 用贝叶斯的方法推导出了著名的“相继律 ，贝叶斯的方法和理论 逐渐被人们认识和重视起来。2 0 世纪数学的公理化倾向影响了统计界，对概率的 公理化经过许多人的努力，最终由科尔莫格洛夫( k o l m o g a r o v ) 完成且得到了普遍 的认同，概率是归一化的测度。但是，对主观概率应该用什么样的公理来描述， 还没有比较一致的看法。1 9 5 8 年英国历史最悠久的统计杂志b i o m e t r i k a 重新全文 刊登了贝叶斯的论文。早期对贝叶斯网络的研究并没有使用贝叶斯方法，只是在 推理中使用了贝叶斯公式。1 9 9 6 年，h e c k e 咖a n 等一些研究者使用贝叶斯方法进 行贝叶斯网络的学习【1 0 】，并把贝叶斯网络用于数据挖掘。 2 0 世纪8 0 年代后，人工智能的发展，尤其是机器学习、数据挖掘的兴起， 为贝叶斯理论的发展和应用提供了更为广阔的空间。尤其是近年来，贝叶斯方法 正以其独特的不确定性知识表达形式，丰富的概率表达能力，综合先验知识的增 量学习特性而成为人工智能、数据挖掘领域中引人注目的焦点之一。 进入9 0 年代，是贝叶斯理论发展和完善的重要时期，这一期间相继提出了许 多种经典的贝叶斯网络结构、推理等算法，使贝叶斯理论能很好地应用于各种实 2 硕_ i ：学位论文 际问题的解决。其中，d g e i g e r 等在深入研究图的拓扑结构和随机变量的独立性 之间关系的基础上，提出了有向分隔的概念，创建了一套关于条件独立的公理系 统【u l ，奠定了贝叶斯网络的理论基础。在此基础上，j p e a r l 提出了一种基于消息 传播的推理算法【1 2 】，从一个全新的角度表示了贝叶斯网络，使贝叶斯网络成为一 种可视的、推理过程清晰的知识表达过程。随后，r d e c h t e r 提出了基于消元的 推理算法【1 3 】；f v j e n s e n 提出了基于联合树的推理算法【1 4 】。g f c o o p e r 证明了 贝叶斯网络推理的计算复杂度1 1 5 l ，指出贝叶斯网络的推理的复杂度依赖于网络 结构，最佳情形为线性复杂度，最坏情形为n p h a r d 问题。 值得一提的是，2 0 0 2 年宫秀军等人将增量学习模式引入到贝叶斯学习算法 中，提出一种增量式贝叶斯分类模型。增量贝叶斯分类模型的主要特点是能在训 练数据集相对较小的情况下，通过逐一将测试数据转化为训练数据来达到参数的 完全训练；另外，增量贝叶斯分类模型还能在训练数据集相当大的情况下，分批 将训练数据集读入内存，解决了计算机存储的局限性问题。近年来，国内外学者 相继提出机器学习方面的增量学习模式，例如将增量学习引入遗传算法、s v m 等。 由此可见，增量模型在机器学习领域受到了越来越多的关注。 2 0 世纪末2 1 世纪初，贝叶斯网络己被广泛地应用于实际问题领域，贝叶斯 决策理论的概念及其不确定性表示和计算技术已融入到人工智能中不确定性处理 的主流中。其所涉及的领域包括计算机视觉、自然语言处理、机器人导航、规划、 机器学习，以及利用贝叶斯技术构建和分析软件系统。另外，贝叶斯网络和贝叶 斯技术也已广泛地应用于数据挖掘，并成为知识发现领域中的一种重要的学习方 法。贝叶斯网在不确定性知识表示及推理方面表现出的卓越性能，为人工智能的 其它研究领城提供了有力的工具。近年来，还出现了专门研究贝叶斯理论的组织 和学术刊物i s b a 。 目前，世界上很多著名学府及著名公司、企业都在积极开展贝叶斯网络学习 方法及其相关应用的研究，如斯坦福大学、普林斯顿大学、加州大学伯克利分校、 微软公司、美国航空航天局、美国电报电话公司、英国医疗研究学会等等。国内 对贝叶斯网络的研究起步较晚，但是发展很快，现在在学术期刊上能够看到较多 的研究成果。 1 3 基于粗糙集的数据挖掘发展与研究现状 基于粗糙集的数据挖掘系统一般由数据准备( 包括数据清洗、数据选择、数 据预处理、数据表示) 、对象分类、对象重要性分析、属性之间的依赖关系分析、 基于粗糙集或拓广理论的数据约简和求核、决策算法、规则生成、规则合并、知 识表示，评价等部分组成。 粗糙集理论作为数据挖掘的一种方法，近年来得到了广泛的关注和青睐。这 3 增量粗集算法及增量贝叶斯分类器研究j 应用 不仅是因为它具有良好的数学基础和性质，而且还因为它恰好反映了人们用粗糙 集处理不分明问题的常规性，即以不完全信息或知识去处理一些不分明现象的能 力，或依据观察、度量到某些不精确的结果而进行分类数据的能力。 1 粗糙集可作为数据挖掘方法的依据。 第一数据挖掘研究的对象多为关系型数据库，关系表可被作为粗糙集 论中的信息表和决策表，这给粗糙集方法带来了极大的方便。 第二粗糙集的约简理论可以用于高维数据的预处理，以去除冗余属性 达到降维的目的。 第三现实世界中的规则有确定的，也有不确定的。从数据库中挖掘不确定的 知识，为数据挖掘提供了用武之地。 第四运用粗糙集方法得到的数据挖掘算法有利于并行执行，这可以极大的提 高大规模数据库中数据挖掘的效率。 2 基于粗糙集的数据挖掘的要点。 在数据路中，将列元素看成属性( 条件属性和决策属性) 。等价关系r 定义 为不同对象在某个( 或几个) 属性上取值不同，这些满足等价关系的的对象组成 的集合称为该等价关系r 的等价类。条件属性的等价类z 和决策属性上的等价类 】，之间有三种情况：第一，下近似，】，包含凰第二，上近似，】，与x 的交不为空： 第三，无关，】，与x 交为空。对下近似建立确定性规则，对上近似建立不确定性 规则( 含可信度) ，无关情况不存在规则。 3 粗糙集理论的应用。 ( 1 ) 粗糙集理论在机器学习和规则生成等领域的应用。机器学习是粗糙集理 论的一个重要应用领域。对于机器学习，虽然已有不少方法，如 a q l 5 ，a e l ，a e 9 ，i d 3 ，c 4 5 等，但目前为止还没有一种被人们普遍接受的方法和 理论。粗糙集理论可以作为机器学习中研究某些问题的理论基础。基于粗糙集理 论的机器学习，主要是从数据中获取确定的或不确定的规则，组成知识库，形成 基于规则的专家系统，以便对新的对象进行分类。 构造决策矩阵和决策函数，运用布尔代数方法进行化简，可以求得隐含在数 据中的全部确定性和可能性的最小规则。s h a nn 提出了一种基于决策矩阵和决策 函数的增量学习算法【m 】，当添加新的数据时，只需对原有规则进行修正，就可以 得到关于新数据集的规则。 粗糙集与布尔推理的结合，可以从决策表中产生最优规则决策规则。b a x a nj g 运用动态核和约简从决策表中产生规则l 1 。 基于规则合并的思想，h a d i i m i c h a e lm & w a s i l e w s k aa 提出了条件概率学习 算法c p l a 和条件建议算法c s a l l 8 l 。利用规则的相似性，c s a 产生候选的条件提 交给c p l a ，再由c p l a 通过学习，将相同的规则合并，产生数目更少的规则。 4 硕j 二学位论文 有时候希望得到规则的一些附加信息，以便应用于特定领域。t s u m o t os 提 出了概率规则归纳方法p r i m r o s e 【1 9 l ，不仅得到了规则，还得到了规则的置信度、 覆盖度，已用于医疗领域。x i a n gy 对规则的不确定性提出了一种衡量方法【2 0 1 。 利用粗糙集，可对学习过程中的知识学习质量、知识学习的充分性、导师知 识的完备性提供一种定量描述和解释分析的方法。 目前，对各种机器学习方法的比较主要是通过数据实验进行，理论的比较分 析有一定的难度。机遇吧粗糙集的机器学习可以发现隐含在数据中的全部确定性 或可能性的决策规则，而a q 4 5 、a e l 、a e 3 、i d 3 、c 4 5 均通过启发式算法得到 规则的一个子集，且只能处理一致的数据集。但测试样本中含有不完整数据时， 基于粗糙集的机器学习可以获得满意的结果，而其他的机器学习方法就显得无能 为力了。 ( 2 ) 粗糙集理论在数据库知识发现中的应用。进入2 0 世纪8 0 年代后，数据 库大量涌现，对信息处理和数据理解的需求越来越大，依靠人工分析数据远远满 足不了这要求。于是在2 0 世纪9 0 年代初掀起了信息处理研究的热潮，数据库 中知识发现k d d ( 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 ) 或数据挖掘d m 应允而生。 k d d 或d m 是从大型数据库或数据仓库中提取人们感兴趣的知识，这些知识是固 有的、事先未知的潜在有用的信息，可以是概念、规则、规律、模式、约束、可 视化等。在k d d 9 6 国际会议上，f a y y a d ，u ，p i a t e s k ys h a p i r o 和g s m y r t h p 对k d d 下了新的定义。k d d 是识别存在于数据库中有效的、新颖的、具有潜在 作用的乃至最终可理解的模式的非平凡过程。 目前，知识发现大多基于机器学习、模式识别、统计分析等，如最常用的数 据挖掘技术有：人工神经网络、决策树、遗传算法、最近邻技术、规则归纳、可 视化技术，但就知识发现过程整体而言，尚缺乏完整的理论基础。尝试以粗糙集 理论为基本框架的知识发现过程的研究，越来越引起人们的重视。如前所述，我 们看到粗糙集可以支持k d d 的多个步骤：如数据预处理、数据缩减、规则生成、 数据依赖关系发现等。近年来，利用粗糙集理论挖掘数据中有用的决策规则，以 粗糙集理论为基本框架的知识发现方法引起了人们的密切关注。目前，粗糙集理 论在k d d 中的应用得到了飞速发展，基于粗糙集理论的知识发现方法已经成为 k d d 的主流方向之一。特别是将粗糙集理论与机器学习、模式识别、数据库理论 等结合，并融合其他有效的数据工具与方法研究，显示出强大的优越性。 另外，粗糙集理论的信息系统与关系数据库中的关系数据模型很相似，这便 于将粗糙集算法嵌入到数据管理系统中。b e a u b o u e ft 等提出了粗糙关系数据库 模型【2 1 1 ，能更灵活的处理查询，得到确定性和可能性的应答，检索能力和适应性相 应提高。 目前，基于粗糙集理论的k d d 研究正处于高潮，已有的建立在粗糙集理论上 5 增量：i j l 集算法及增量贝叶斯分类器研究j 应用 的k d d 系统有：r o u g h d a s & r o u g h c l a s s ，d a ，i a l o g i c r ，d b r o u g h ，k d d r 及l e r s 等。 ( 3 ) 粗糙集理论在决策支持分析中的应用。决策分析是人类最自然的一种行 为，科学的决策分析是阐明那些不为刃所知却能影响人的决策因素。数学决策分 析是建立函数或关系模型，而基于人工智能的决策分析则是通过示例学习建立决 策模型，它由分类规则组成。粗糙集理论可以从模糊或不一致的信息中获取决策 规则，因而是分析决策问题的有用工具。在粗糙集理论中，将决策问题分为四类： 一是多属性单决策分类问题。大部分决策问题属于这一类，论域中的对象由 多个条件属性和一个决策属性描述，通过粗糙集分析可得到如下结果：评价一个 特定属性的重要性；在保证相同分类质量前提下得到独立属性的最小集合，即约 简；从所有约简的交中得到属性核，核是最重要的属性值；从决策表中去除冗余 属性；从约简的决策表中产生分类规则，它代表了相应的决策策略，可用来对新 的对象进行分类。 二是多属性多决策分类问题。这类问题中有多个条件属性和多个决策属性。 运用粗糙集方法，对每个单决策属性，可以得到与多属性单决策分类一样的结果。 对不同的决策属性，还可以评价决策策略的相同性和不一致性，建立一致性决策 策略。 三是多属性描述问题。这类决策问题中，只有条件属性，没有决策属性。通 过粗糙集分析，可得到信息系统中各个对象的最小描述，矛盾分析属于此类决策 问题。 四是属性间依赖关系的发现。在这类决策问题中，只有决策属性，没有条件 属性，因此不能从信息系统中去除属性，利用粗糙集可以找出属性之间的最小函 数依赖关系。 s l o w i n s k ir 研究了多属性分类问题，利用导出的决策算法对新的对象进行 分类，首先找出一个与新对象匹配的规则，如果不存在匹配的规则，在值接近关 系下定义了一个新的距离函数，利用它提供一组“最近 分类规则给决策者【22 1 。 4 基于粗糙集理论的数据挖掘展望。 粗糙集是数据挖掘的有利工具，具有坚实的理论基础。粗糙集理论自l9 8 2 年波兰数学家p a w l a k 提出以来，已在很多领域得到了应用。但作为一种新事物， 粗糙集在实际应用中也遇到了许多困难。目前的有效途径有两条：一是粗糙集理 论的拓展，如z i a r k o 的变精度粗糙集模型【2 3 1 ；二是粗糙集与其他方法的结合。基 于粗糙集的数据挖掘在以下方面有待深化： 第一高效的约简算法，是粗糙集理论应用于数据挖掘的基础，目前尚不存在 一种非常有效的方法。因此，寻求快速的约简算法仍然是主要的研究方向之一。 第二粗糙集和其他软计算方法的进一步结合问题。 6 硕上学位论文 第三粗糙集知识挖掘的递增算法。这实际上是一个二次数据挖掘问题，即在 过去已挖掘知识的基础上，修正或补充不合理的部分，以便适应新的数据，而不 是重新开始。 第四粗糙集基本运算的并行算法及硬件实现，将大幅度提高数据挖掘的效 率。 第五扩大处理数据的范围。 第六现代信息系统具有分布异构的特点，解决的办法之一是分解，即将用户 提出的全局挖掘要求分解为不同节点的子数据库挖掘要求，然后在各个节点上单 独挖掘，最后集成。 1 4 文章的主要工作及结构 论文在相关国内外的书籍、文献资料和研究的基础上，针对静态约简算法在 面对海量数据和增量变化数据的处理时，所表现出的求得的约简非常不稳定，带 有很大的局部色彩，而且计算量巨大等问题，研究了基于粗糙集的动态约简的数 据挖掘模型，提出了一种概率抽样以子集权重的快速求解动态核的算法，并给出 了一个基于动态约简的增量数据挖掘模型；同时在研究了增量学习在贝叶斯学习 推理的基础上，提出了一种基于动态约简的增量贝叶斯分类器的算法，并应用在 氧化铝回转窑上。本文的主要内容和章节结构为： 第一章：概述了本文研究和探讨的背景和意义，简述了当前数据挖掘技术的 发展和应用，综合分析了贝叶斯网络分类器和粗糙集理论的发展和应用。在本章 结尾提出了本文的主要工作。 第二章：介绍了数据挖掘的一些常用技术，以及粗糙集在数据挖掘中的应用 进行概述，最后阐述了数据挖掘的前期工作一数据预处理，并对数据预处理方法中 的数据清理、数据集成、数据变换和数据规约进行详细的介绍和研究，在数据规 约中，重点介绍了连续属性数据的离散化，为后序章节做好铺垫。 第三章：介绍了粗糙集在知识表达系统中的简化和核的求取，并简述基于粗 集的静态约简和动态约简在数据挖掘中的模型构造。并针对动态约简中的不同抽 样子集对决策表具有相同影响度的不足，提出了一种概率抽样以子集权重的快速 求解动态核的算法。引用动态核的概念，对静态属性约简算法与动态约简进行了 比较，并从理论上证明了动态约简方法更为稳定、有效。通过对该算法的分析表 明：在充分利用已有的子集的约简结果的基础上，得到总决策表的近似约简核的 时间复杂度大大降低，适合对数据库的实时在线挖掘。 第四章：介绍了贝叶斯分类器的工作原理，详细叙述了增量贝叶斯分类器模 型的概念及原理，并以此提出一种基于动态约简的增量贝叶斯分类器，通过对分 类器输入属性的约简，挖掘出对分类最有利的极小值属性，这对传统的增量式贝 7 增量籽l 集算法及增量贝叶斯分类器研究j 应用 叶斯网络分类器算法复杂度上有了一定的降低。通过仿真实验表明，属性约简后 的增量式贝叶斯网络分类器计算简单，有很好的实时性。 第五章：结合前面对数据挖掘技术的研究，在实际氧化铝熟料烧成回转窑智 能控制系统中加入基于动态约简的增量贝叶斯网络分类器预测模块，并通过计算 机仿真及现场实验，证明了数据挖掘技术在氧化铝熟料烧成回转窑智能控制系统 的可行性。 8 硕上学位论文 第2 章。数据挖掘技术的研究与应用概述 2 1 数据挖掘的基本概念 数据挖掘比较公认的定义是由w j f r a w l e y 和g p i a t e t s k y s h a p i r o 等人提出的 【2 4 】：数据挖掘就是从大型数据库的数据中提取人们感兴趣的知识。这些知识是隐 含的、事先未知的、但潜在有用的信息：提取的知识可以表示为概念、规则、规律、 模式等形式。这种定义把数据挖掘的对象定义为数据库。而更广义的说法是：数据 挖掘意味着在一些事实或观察数据的集合中寻找模式的决策支持过程。 数据挖掘是对观察到的数据集( 通常是很庞大的集合) 进行分析，目的是发现 未知的关系和以数据拥有者可以理解并对其有价值的新颖方式来总结数据。其中 “观测到的数据 是与“实验得到的数据相对而言的。一般来说数据挖掘所处 理的数据是为了其它某种目的而己经收集好了的数据，而不是为数据分析者主动 去收集的( 例如，银行中正常业务需求而收集的) 。这意味着数据挖掘的目标不在 于数据采集策略。这是数据挖掘区别于大多数统计任务的一个特征，在统计中经 常是利用高效率策略来采集数据以回答特定的问题。因此数据挖掘经常被称为“次 级的 数据分析。 数据挖掘所分析的经常是很庞大的数据集。如果仅涉及很小的数据集，那么 就可以仅仅讨论统计学家们所使用的标准数据探测和分析方法了。当面对很庞大 的数据集时，就必须面对这样的问题：如何表示数据，如何在合理的时间内分析数 据，以及如何判定一个表面上的关系是偶然发生的，并不能反映任何潜在的事实。 大多数情况下，现有的数据仅仅是整个总体的一个样本：最终的目的可能是从这样 一个样本泛化( g e n e r a l i z e ) 到总体。而有时可能采用某种方式总结或压缩一个庞大 的数据集，使得过程更容易处理，结果更容易理解。数据挖掘是一门跨学科的技 术。统计学、数据库技术、机器学习、模式识别、人工智能、可视化技术都在数 据挖掘中起着作用。因此，在进行数据挖掘的过程中将用到多个学科的技术和方 法。 2 2 数据挖掘常用技术 随着数据挖掘研究逐步深入，理论逐步趋于完善，数据挖掘技术已经形成三 个技术方向：数据库、人工智能和数理统计。目前数据挖掘的主要研究内容包括 基础理论、挖掘算法、数据仓库、可视化技术、知识表示方法、发现知识的维护 和再利用、半结构化和非结构化数据中的知识发现以及网上数据挖掘等【25 1 。 9 增量机集算法及增量贝n f 斯分类器研究j 应用 数据挖掘算法的好坏将直接影响到所发现知识的质量。目前大多数的研究都 集中在数据挖掘算法及其应用上。以下将介绍数据挖掘技术中常用的几种挖掘算 法。 2 2 1 贝叶斯网络算法 贝叶斯网络是一个带有概率注释的有向无环图。这种概率图模型能表示变量 之间的联合概率分布，分析变量之间的相互关系。贝叶斯网络是基于概率推理的 数学模型，所谓概率推理，就是通过一些变量的信息来获得其它变量的概率信息 的过程1 2 6 】。假定有随机变量集合肛 蜀，髟，五 ，x ，表示五的取值。表达式尸= x j ，局鼍2 ，可一) 表示一个联合概率，即变量蜀，恐，的值分别是 x l ，耽，x n 时的概率。从理论上讲，给定一个随机变量集合的完全联合概率函 数，就能计算所有的边缘概率和更低阶的联合概率。但是当有一个很大的随机变 量集合时，指定所有的联合概率或更低阶联合概率的任务就难于处理了( n p 难 题) 。幸运的是，在大多数应用中，联合概率都满足一定的条件，这些条件可以简 化运算量，使得对它们的指定和计算变得可行。 用于分类的贝叶斯网络，最简单的就是朴素贝叶斯网络分类器( n a v eb a y e s 或者s i m p l eb a y e s ) 。朴素贝叶斯网络模型将训练实例，分为特征向量彳和决策类别 变量c ，朴素贝叶斯模型是假设特征向量的各分量相对于决策类别变量是相互条 件独立的，即尸ic ，五) = p ic ) 。如图2 1 ； 图2 1 朴素贝叶斯分类模型 朴素贝叶斯分类器的分类能力与经典c 4 5 分类器不分上下，由于其结构简单， 运算迅速，目前已得到大量应用。但是，朴素贝叶斯分类器由于其属性之间条件 独立的假设约束，很多现实世界的数据不想符合，导致了朴素贝叶斯分类器应用 受限。近年来，许多研究人员致力于放松特征见独立性的限制，以使它使用与更 广阔的范围。贝叶斯网络分类器便能很好的描述变量属性间的因果关系，摆脱属 性间条件的限制。 贝叶斯网络【2 7 儿2 8 1 结合图论和概率理论方面的知识，表达随机变量之间复杂的 l o 硕j ：学位论文 不确定性关系，并提供了一种自然的表示因果关联的方法，可以用于发现数据间 的潜在关系。贝叶斯网络作为一种图形化的建模工具，具有一系列的优点： 第一贝叶斯网络将有向无环图与概率理论有机结合，不但具有坚实的概率理 论基础，同时也具有直观的知识表示形式。一方面，它可以将人类所拥有的因果 知识直接用有向图的形式直观地表示出来。另一方面，也可以将统计数据以条件 概率的形式融入模型。这样贝叶斯网络就能将人类的先验知识和后验的数据无缝 地结合，克服框架、语义网络等模型仅能表达处理定量信息的弱点和神经网络等 模型不够直观的缺点。 第二贝叶斯网络直接对问题域建模，因此，当条件或行为等发生变化时，不 需要对模型进行修正：贝叶斯网络是随机变量间联合概率的最恰当的因子分解方 式，能够处理各种复杂的不确定性问题。 第三贝叶斯网络的推理以贝叶斯概率理论为基础，不区分是前向推理还是后 向推理，网络中的每个结点都可以输入信息和输出信息，具有灵活的信息推理机 制。贝叶斯推理既可以进行预侧又可以进行珍断，不但具有理论依据，而且将知 识表示与知识推理结合起来，形成统一的整体。 由于上述优点，贝叶斯网络很快就成为数据挖掘领域进行不确定性推理和建 模的一个有效工具【2 9 l 。利用贝叶斯网络可以对于事件或者属性间的带有不确定性 的数据进行分类和预测。 但是，如果贝叶斯网络直接应用于大规模数据建模，主要存在以下问题： 第一贝叶斯网络需要清楚表达系统中所有变量，以及变量之间所有的直接的 概率依赖关系或因果关系，随着系统规模的增大，变量个数的增多，完成这个任 务的难度会迅速增大。 第二贝叶斯网络的结构不够灵活，当需要增加或减少节点时，需要调整整个 网络结构和条件概率分布，以保证联合概率分布的完备性，在变量个数较多的情 况下，难度较大。 贝叶斯网络的推理和学习的计算复杂度都依赖于网络结构，在最坏情况下都 是n p h a r d 问题，在变量个数较多的情况下，难以对网络结构进行合理的评判， 现有的算法不可行。 用模块化和层次化方法来降低问题复杂度是研究贝叶斯网络的重要方法。近 年来，人们提出了许多改进的贝叶斯网络模型，分别在不同程度上解决了大规模 贝叶斯网络的知识表示等问题。代表性的有h e c k e r m a nd 的s i m i l a r i t yn e l w o r k s ， g e i g e rd 的b a y e s i a nm u l t i n e t s 和k o l l e rd 的o b j e c to r i e n t e db a y e s i a nn e t w o r k s 等。这些模型不同程度地降低了大规模贝叶斯网络知识表示地复杂度。 增量栅集算法及增量贝叶斯分类器研究与应用 2 2 2 时序相似性算法 时序相似性算法属于时间序列数据分析范畴( 见图2 2 ) ，是时间序列挖掘的最 常见也是最基本的研究方向之一。由图2 2 可见，与时序相似性算法联系非常密 切的还有时间序列的表示，大多数情况下，时序相似性算法都是建立在时间序列 的表示之上的。因此，在研究时间序列的相似性算法时，必须着重时间序列表示 方法的研究。 图2 2 时间序列分析组成 时间序列相似性分析的两个关键内容是时间序列的表示( r e p r e s e n t a t i o n ) 和序 列间距离的定义f 3 0 1 。时间序列相似性分析的目标是在大型高维度时序数据库中， 以可以满足要求的效率搜索到与给定查询序列合理相似的目标序列。其中满足要 求的效率指相似性分析的算法需要有较小的时间和空间复杂度。 由于时间序列数据挖掘的对象通常是连续的海量数据序列，其短期波动频繁、 大量噪声干扰以及非稳态的特点使得直接采用原始时间序列进行相似性查询、索 引、分类和聚类、时序模式挖掘等工作不但效率低下，甚至会影响时间序列数据 挖掘的准确性和可靠性。因此，许多研究者提出了时间序列的模式表示方法，从 更高层次上对时间序列重新进行描述和数据挖掘。 因此，时序相似算法的重点和关键就在于时序的表示方法。这一点可以从时 序相似性算法的发展看出来。时序的表示，旨在对时间序列压缩，但又能最大程 度的保存原有时间序列的信息。现有的时序表示方法主要分为基于变换和基于模 型两种方法。其中，时间序列基于变换的基本思想是从时间序列中提取特征，将 时间序列变换到特征空间，采用特征空间的特征模式来表示原始时间序列。时间 序列的模式表示有两个优点：首先是通过压缩时间序列实现维度约简，提高数据 挖掘工作的效率；其次时间序列的模式表示在保留时间序列主要特征的同时具有 去噪音功能，更能反应时间序列的变化情况，提高数据挖掘的质量。这种方法主 硕l 学位论文 要包含四种类型：频域表示法、奇异值表示法、符号表示法以及分段线性表示法。 2 2 3 其他用于数据挖掘的技术 除了以上提及的算法，按数据挖掘任务分类还有多种算法可以用于数据挖掘， 以下简述之： 除了以上所述，数据挖掘还包括几大应用技术： ( 1 ) 聚类分析：聚类分析是将一个数据集分成多个类别的群组，使同一个类 别的数据尽可能相似，而不同类别的数据差距尽可能大。聚类与分类不同，在一 开始聚类是不知道类别和类别的数量的。它是依据样本间关联的度量，将样本间 满足人为确定的距离标准聚为一类，而把相差比较大的分到其他类别当中。聚类 的效果除了算法的适当外，距离标准也很重要，如果距离标准不恰当，将导致聚 类效果下降。 ( 2 ) 关联分析：关联分析用于发现事物间的关联规则，关联规则的一般形式 是，如果彳发生，则b 发生的概率是c ，c 称为关联规则的支持度。关联分析的 核心是如何高效地计算频率项集，很多种算法都是围绕它来展开的。目前，关联 分析挖掘的主要算法有a p r i o “算法和d h p 算法。 根据数据挖掘应用领域的不同，数据挖掘还可以分为空间数据挖掘、媒体数 据挖掘、和文本数据挖掘f 3 l 】。 2 3 基于粗糙集的数据挖掘概述 2 3 1 概述 粗糙集理论是一种描述不完整和不确定性的数学理论，它从新的角度对知识 进行定义，把知识看做是关于论域的划分，从而认为知识是有粒度的，知识的粒 度性是造成使用已有知识不能清楚表示某些概念的原因。这产生了所谓关于不精 确的“边界 思想。著名哲学家f r e g e 认为“概念必须有明确的边界。没有明确 边界的概念，将对应于一个在其周围没有明确界线的区域 。粗糙集理论中的模糊 性就是一种基于边界的概念，即一个模