（计算机应用技术专业论文）基于粒计算的不完备决策系统数据挖掘研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着信息技术和互联网的发展，庞大的数据库日益增加，为了在海量的 数据中获取有价值的信息和知识，数据挖掘应运而生，相应的数据挖掘技术 已成为国内外研究的热点，并且得到了广泛的应用。目前，一些成熟的数据 挖掘方法所处理的数据都是完备的。而在实际的数据挖掘中，待处理的数据 常存在某种程度的不完备，如果直接对其使用针对完备信息系统的数据挖掘 方法，往往会产生不合理的结果，甚至错误的信息和知识。因此研究不完备 系统上的数据挖掘具有一定的现实意义。 近年来，国内外诸多学者对粒计算在数据挖掘中的应用进行了探讨和研 究，提出了一些模型和方法，粒计算在数据挖掘中得到了广泛的应用。本文 将粒计算的方法应用到不完备决策系统的数据挖掘研究中，探讨了不完备决 策系统在粒表示下的属性约简方法和分类分析方法。并通过实验验证方法的 有效性。主要工作如下： 1 运用粗糙集( r o u g h s e t ) 和粒计算的有关理论，在基于容差关系下的 粒计算模型下，研究属性约简方法。提出粒表示下属性必要性和重要性的判 定条件，进而给出一种粒表示下的属性约简算法。 2 研究粒表示下的决策树分类分析方法。提出粒表示下决策树分裂属性 的选择标准，及决策树停止生长的条件，给出一种基于粒计算的决策树分类 分析算法g r c d c ( g r a n u l a rc o m p u t i n gd e c i s i o n t r e ec l a s s i f i c a t i o n ) ，最后通 过实验证明其有效性。 关键词：数据挖掘：粒计算；不完备决策系统 西南交通大学硕士研究生学位论文第1 i 页 a bs t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g ya n di n t e r n e t ，t h e h u g e d a t a b a s ei n c r e a s e sd a yb yd a y i no r d e rt oo b t a i nt h ev a l u a b l ei n f o r m a t i o na n d k n o w l e d g e i nt h eh u g ed a t a b a s e ，d a t am i n i n g ( d m ) e m e r g e sa st h et i m e sr e q u i r e a c c o r d i n g l y , t h ed mt e c h n o l o g y , w h i c hi sw i d e l yu s e d ，h a sb e c o m et h eh o t s p o t o fr e s e a r c hb o t ha th o m ea n da b r o a d r e c e n t l y , s o m em a t u r em e t h o d so fd m o n l y d e a lw i t ht h ec o m p l e t ei n f o r m a t i o n d u r i n gt h ep r a c t i c a ld m ，t h ed a t ad e a l tw i t h i sa l w a y si n c o m p l e t et os o m ee x t e n t i ft h ei n c o m p l e t ei n f o r m a t i o ni sd e a l tw i t h d i r e c t l yb yt h ed mm e t h o df o rt h ec o m p l e t ei n f o r m a t i o ns y s t e m ，i tw i l le n dw i t h u n r e a s o n a b l er e s u l t ，e v e n w r o n gi n f o r m a t i o na n dk n o w l e d g e t h e r e f o r e ，t h e r e s e a r c h e so nd mb a s e do n i n c o m p l e t es y s t e m h a v ec e r t a i n p r a c t i c a l s i g n i f i c a n c e i nr e c e n ty e a r s ，m a n yd o m e s t i ca n di n t e r n a t i o n a ls c h o l a r sh a v er e s e a r c h e d i n t ot h ea p p l i c a t i o no fg r a n u l a rc o m p u t i n g ( g r c ) i nd m ，a n da l s op u tf o r w a r d s o m em o d e l sa n dm e t h o d s t h e n g r ci sw i d e l yu s e di nd m t h em e t h o do fg r c i sa p p l i e di nd mo fi n c o m p l e t ed e c i s i o ns y s t e m a t t r i b u t er e d u c t i o nm e t h o da n d c l a s s i f i c a t i o n a n a l y s i sm e t h o do fi n c o m p l e t ed e c i s i o ns y s t e mu n d e rg r a n u l a r e x p r e s s i o na r ep u tf o r w o r di nt h i sp a p e r , w h i c hh a sv a l i d a t e db ye x p e r i m e n t s t h e m a j o rw o r ki si l l sf o l l o w s ： 1 w i t ht h e a p p l i c a t i o no ft h eb a s i ct h e o r yo fr o u g h s e ta n dg r c ，w e r e s e a r c h e so nt h em e t h o do fa t t r i b u t er e d u c t i o n w h i c hi sb a s e do nt h em o d e lo f g r cu n d e rt o l e r a n c er e l a t i o n s t h ed e t e r m i n a n tc o n d i t i o n so fa t t r i b u t en e c e s s i t y a n di m p o r t a n c eu n d e rg r a n u l a r e x p r e s s i o na r ep u tf o r w a r da n da na t t r i b u t e r e d u c t i o na l g o r i t h mu n d e rg r a n u l a re x p r e s s i o ni sp r o v i e d e s 2 t h em e t h o do fd e c i s i o n - t r e ec l a s s i f i c a t i o ni sp u tf o r w a r di nt h i sp a p e r t h e c h o i c ec r i t e r i o no ft h e s p l i t t i n g a t t r i b u t eo fd e c i s i o n t r e eu n d e r g r a n u l a r e x p r e s s i o na n dt h ec o n d i t i o nf o rs t o p p i n gd e c i s i o n t r e eg r o w i n g ，a r ep u tf o r w a r d w ep r o v i d e sak i n do fg r a n u l a rc o m p u t i n gd e c i s i o n - t r e ec l a s s i f i c a t i o n ( g r c d c ) 西南交通大学硕士研究生学位论文第l ii 页 a l g o r i t h m f i n a l l y , t a k ee x p e r i m e n t st op r o v et h ev a l i d i t yo ft h eg r c d c a l g o r i t h m k e yw o r d s ：d a t am i n i n g ；g r a n u l a rc o m p u t i n g ；i n c o m p l e t ed e c i s i o ns y s t e m 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部f 】或机构送交论文的复印件和电子舨，允许论文被查 阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位 论文。 本学位论文属子 1 保密口，在年解密后适用本授权书； 2 不保密嘶使用本授权书。 ( 请在以上方框内打“4 ) 学位论文作者签名：互嚣岛指导老师签名： o 艚 日期：矽孑雪罗 嚣期： 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作 所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 1 在原有容差关系下的粒表示基础上，提出属性必要性和属性重要性判 定条件，进而提出一种不完备决策信息系统在粒表示下的属性约简算法。 2 研究了在粒度表示下的分类分析方法，将粒计算的思想应用到决策树 分类分析中，提出粒表示下树的分裂属性选择标准及树的停止生长条件，进 而给出一种基于粒计算的决策树分类方法g r c d c ，并实验验证算法的有效 性。 3 在实验数据预处理中，研究连续属性值的离散化，提出一种基于s e m i n a i v es c a l e 算法的不完备信息系统的连续属性值离散化算法。 西南交通大学硕士研究生学位论文第 页 1 1 论文研究背景 第1 章绪论 1 9 7 9 年，美国著名数学家z a d e h 在模糊集合论的基础上，首次提出并讨论 了模糊信息粒仡的闻题，推动了模糊逻辑理论及其应用的发震。随着理论和 方法的进一步发展成熟，越来越多的科学家对此产生兴趣。1 9 9 7 年，美国s a n j o s es t 教e 大学教授t y l i n 首次提出粒计算( g r a n u l a rc o m p u t i n g ，g r c ) 的概念， 标志着涉及多学科的个应用研究领域产生。从此粒计算成为一个热门的研 究领域，为我们观察和分析问题带来很多方便。它不仅可以将复杂问题划分 为一系列更小的更容易管理的予问题，从而降低全局代价，还可以提供一种 对问题本质更好的洞察力，帮助我们更好地领悟问题，避免陷入不必要的细 节中。如今靛计算在软计算、知识发现、数据挖掘等领域中正扮演着越来越 重要的角色。 数据挖掘是挖掘海量信息的重要工具，一些挖掘方法已逐渐趋向成熟。 粒计算理论对些传统的数据挖掘方法进行了革新，粒计算采用粒度的思想 来处理问题和解决问题。针对一个或某些问题或理论，来设计与构造粒或粒 度，利用构造好的粒或粒度对闷题进行计算、分析等，最终获得问题解。 粒计算在数据挖掘领域中有着广泛的应用前景，目前，国际上已形成专 门的研究群体，定期召_ 开一定的学术会议，发表的相关文献越来越多，徨在 粒的计算方面，所提出的一些近似推理方法在理论上还缺乏完备性，同时也 缺少高效的粒计算算法，这也是本文的研究背景。而国内，对粒计算的研究 刚刚开始，目前还仅局限于理论方面的研究，对粒计算的应用很少涉及，本 文针对国内的这种情况，对粒计算在数据挖掘中的应用情况进行了深入的研 究与探讨，在此基础上，提出了基于粒计算的不完备信息系统上数据分类算 法。 现实中，数据挖掘所面对的透常是存在空缺值的信息系统，缺失值的存 在限制了很多理论与方法对不完备信息系统的有效处理。前人对空值已有了 大量研究，但基于粒计算理论的不完备信息系统的研究还很薄弱，特别是在 不改变原信息系统的前提下如何从不完备信息系统获取知识的理论和方法的 西南交通大学硕士研究生学位论文第2 页 研究还很少，这也是本文研究的一个出发点。 1 2 国内外研究现状 1 2 1 不完备信息处理研究现状 不完备信息系统的知识发现是人工智能领域的重要问题。目前有多种方 法用于不完备信息系统的知识获取问题，其中处理空值最简单直接的方法就 是删除带有空值的对象，但删除空值可能造成数据浪费。第二类方法就是通 过数据补齐的方法将不完备信息系统转化为完备信息系统，再利用完备信息 系统的方法进行处理。如通过统计分析填补空值【7 】，利用其他条件属性的取 值和决策属性的取值或属性之间的联系来估计空值：利用贝叶斯模型和证据 理论【8 】也是比较常见的数据补齐方法，但贝叶斯模型需要知道概率密度，而 证据理论需要证据函数，这些数据之外的信息往往很难得到；在粗糙集理论 中，t z u n g p e ih o n g 等人【9 】利用上下近似提出了一种填补空值并提取规则的方 法，但这种方法无法处理空值较多的信息系统。另一种做法是让专家根据一 定的条件给出空值的估计值，但这种方法有很大程度的主观性和随意性。 由于删除和补齐空值处理方法的局限性，人们提出了第三种处理方式： 在不改变信息系统的前提下对不完备信息系统进行研究。但由于不确定性值 的出现，不能够在对象集上找到符合实际需要的等价关系，因此，只能从对 象之间的相似性来考虑对象之间的关系。就目前的研究情况来看，对不完备 信息系统的粗糙集理论的研究主要采取了相容关系d o 、非对称相似关系和量 化容差关系l i t ，王国胤提出了限制容差关系 1 2 1 ，y a oy y 通过定义领域算子研 究了一般二元关系的粗糙集模型m 】，他在文中并未特别指出针对不完备信息 系统，但完全可以推广到不完备信息系统上的一般二元关系。 在不完备信息系统约简方面，最常见的是利用辨识矩阵和布尔推理方法 【l ，k r y s z k i e e w i c z 给出了不完备决策表的知识约简方法 i s l ，并且提出了一种 获取最优规则的方法。l e u n g 等利用极大相容块的概念，刻画了不完备信息 系统中隐含于相似关系中的知识信息，建立了不完备信息系统中知识获取的 一种方法极大相容块技术【1 6 l 。国内学者也提出了许多约简算法，如分层递 阶约简算法和基于散列的约简算法等，而且还在不断地发展和完善之中。本 文在基于r o u g h 集扩充模型的粒空间上提出一种基于分类的属性约简算法。 西南交通大学硕士研究生学位论文第3 页 1 2 2 粒计算研究现状 自美国控制论专家l a z a d e h 第一个介绍了信息粒化( i n f o r m a t i o n g r a n u l a t i o n ) 的概念后，对信息粒化的研究受到广泛关注。1 9 8 2 年，美国 s t a n f o r d 大学教授h o b b s 在第九届国际人工智能大会上提出了粒度 ( g r a n u l a r i t y ) 理论，该理论抓住了粒计算的基本特征，以不同的粒度来概 化世界，以粒度之间的交换来处理问题：1 9 9 6 年，z a d e h 提出了一个新的研究 分支词计算( c w ) ，为将来的智能计算以及基于词的信息系统实现计算 建立了理论基础，标志着模糊粒度化理论的诞生；1 9 9 7 年，z a d e h 重新阐述了 信息粒化的重要性，z a d e h 的工作激发了学者对粒度计算的研究兴趣。粒计算 和词计算的重要性在于它能达到高档机器智商m i q ( m a c h i n ei n t e l l i g e n c e q u o t i e n t ) 的目标，就是通过重新标记人的能力实现不用任何测量和任何复 杂计算就能达到的目标。 t y l i n 提出了使用邻域来作为粒计算的表达【l 2 】，它是基于r o u g h 集划分 理论的一个扩展；加拿大r e g i n a 大学教授y y y a o 探讨了粒计算的基本问题， 阐述了粒的构建和粒的计算，提出了基于幂代数概念下粒计算的集合理论模 型 。随后，粒计算的研究迅速发展，研究成果不断涌现。 国外学者针对粒计算在数据挖掘中的应用，也进行了广泛的研究。1 9 9 8 年，t y l i n 提出了基于二进制邻域系统的二进制粒结构，随后，t y l i n 着重 阐述了二进制邻域系统的表示，用表的格式来表示二进制关系，该表被称为 信息表的扩展，这样，将信息表处理扩展为二进制关系粒结构的处理。1 9 9 9 年，t y l i n 提出了一个新的数据挖掘理论，在原有的关系数据库中，附加了 粒计算的概念和二进制邻域系统，用粒计算来处理二进制关系，一系列二进 制关系就是粒结构，数据挖掘就是粒结构的处理【4 i 。该理论为基于粒计算基 础上的数据挖掘提供了导向。2 0 0 1 年，y y y a o 提出了一个基于粒计算规则挖 掘的框架。该框架是基于粒计算模型概念的外延来定义的，称为基于粒计算 模型的数据挖掘，提出的模型可被认为是数据挖掘形式和数学建模的第一步。 它通过内涵和外延的一部分作为特征，用信息表定义精确的内涵和外延，语 言的公式来定义内涵，论域对象的子集来定义外延，通过概念的内涵来表达 挖掘规则，通过概念的外延来解释，随着这个模型被提出，数据挖掘一些存 在的方法可以被比较和分析。2 0 0 5 年，t r q i u 等讨论了基于信息粒和粒 计算的基础上关联规则的挖掘【s - 1 ，以a p r i o r i 算法为基础，提出了基于粒计算 西南交通大学硕士研究生学位论文第4 页 一种新的关联规则抽取算法，和经典的a p r i o r i 算法相比，该算法有效地缩减 了候选元素的数目，解决t a p r i o r i 算法在寻找频繁项目集时，重复扫描信息 表的瓶颈问题。y c 。t a n g 提出了基于g s v m 模型一个新的算法g s v m d c t s 3 1 ， 该算法以粒支撑向量机为模型，能快速和精确地为生物医学数据进行二进制 分类。 在国内，对粒计算的研究阏l 刚开始，张镶院士和张铃教授提出了基于商 空间的粒度世界模型，并在此基础上于2 0 0 3 年把粒度世界模型理论推广到模 糊商空间理论模糊粒度计算方法潮，给出了模糊商空间的缩构，证明了 利用模糊等价关系可以将原来的商空间理论推广成模糊商空间理论，并给出 了模糊商空间理论的几个基本定理，这些定理为粒度计算提供了强有力的数 学模型和工具。一些学者的弟子利用商空间理论初步探索了信息粒度方法在 文本分类和挖掘中的应用，以便提高语义w 曲的服务质量。刘清教授重点阐 述了粒及粒计算在逻辑推理中的应用，讨论了信息粒的结构及箕实例，基于 r o u g h 集方法定义了决策规则粒，构造了决策规则粒库，定义了粒语言，描 述了这种语言的语法、语义、粒语句的运算法则和粒相关的几个性质，基于 这些概念，构造了一种逻辑推理的新模型f 6 】。我国学者王飞跃提出了建立以词 计算为基础，对问题进行动态描述、分析、综合，进而设计、控制和评估的 语言动力学系统湖，这对于设计和实现能够处理社会、经济、政治、管理及 法律等问题的复杂的智能系统非常必要，代表着复杂系统研究的一个重要而 有意义的方向。总的来看，粒度计算的研究在黧内属于起步阶段，尚未弓| 起 广泛关注，这也是本文研究的出发点。 1 3 论文的组织 本论文的组织结构如下： 第l 章绪论 首先分析了本文的选题背景和研究意义，然后介绍了国内外研究现状及 论文的组织安排。 第2 章不完备系统与粒计算 首先介绍了不完备系统的概念和与论文相关的粒计算理论，接着给出不 完备系统在容差关系下的粒表示、粒计算方法和粒子分解算法洲。 第3 章基于粒计算的属性约简与分类分析 西南交通大学硕士研究生学位论文第5 页 本章分为2 个部分：( 1 ) 不完备决策系统粒表示下的数据约简，提出了 粒表示下属性必要性和重要性的判定条件，给出计算属性核集及属性约简的 算法。( 2 ) 不完备决策系统粒表示下的分类分析。文中提出一种基于粒计算 的决策树分类分析方法，研究了在粒计算下决策树分裂属性的选择及树的停 止生长条件。 第4 章实验与评价 首先介绍论文实验所用数据集( 标准u c i 数据集) ；然后，描述了在不 完备系统数据挖掘中涉及的数据预处理内容，提出了基于s e m in a i v es c a l e 算法的不完备决策系统数据离散化方法；在w e k a 机器学习平台上对本文提 出的数据离散化方法、数据约简方法和g r c d c 方法在分类正确率和生成树 的规模上进行实验，并与常用决策树分类算法c 4 5 对比，验证其有效性。 总结与展望 总结了全文，对全文的工作给出了评价并指出今后要做的工作。 西南交通大学硕士研究生学位论文第6 页 第2 章不完备系统与粒计算 2 1 不完备系统 本节介绍不完备系统的概念，对信息系统、决策信息系统和不完备决策 信息系统给出定义。 定义2 1 ( 信息系统) 【z ，】：称四元有序组s = ( u ，a ，v ，厂) 为信息系统，其 中u 为所考虑对象的非空有限集合，称为论域；a 为属性的非空有限集合； v - - uv ，圪为属性的值域； ： 一y 是一个信息函数，o a fu x a v xg 移，a a ，f ( x ，口) 圪，对于给定对象x ，f ( x ，口) 赋予对象x 在属性a 下的 属性值。 信息系统可以用数据表格来表示，表格的行对应论域中的对象，列对应 描述对象的属性。一个对象的全部信息由表中一行属性的值来反映。 表2 1 为一个信息系统实例。 表2 1 信息系统实例 人员编号头疼肌肉疼体温流感 人员l是是正常否 人员2是是局是 人员3是是很高是 人员4否是正常否 人员5否否同否 人员6否是很高是 表2 1 中，对于研究对象( 人员) ，使用头疼、肌肉疼、体温、流感四种 特征描述。 定义2 2 ( 决策信息系统) ：给定信息系统s = ( u ，a ，v ，厂) ，a = c ud ， d 囝，cn d = 囝，子集c 和子集d 分别称为条件属性集和决策属性集，称 这时的信息系统为决策信息系统( d e c i s i o ni n f o r m a t i o ns y s t e m ) ，简称决策系 统。 通过一个决策信息系统，很容易得到一个规则集，例如( i f 条件属性符 合某种情况，t h e n 决策属性应该为某一唯一的特定值) 的决策规则。 定义2 3 ( 不完备决策信息系统) ：给定决策信息系统s = 缈，a ，v ，厂) ， 西南交通大学硕士研究生学位论文第7 贾 a = c u d ，c nd = f 2 j ，d g ，如果至少存在一个属性口毯c ，圪包含空值( 用 宰表示) ，则称决策信息系统s 为不完备决策信息系统，篱称不完备决策系统 或不完备系统。 由定义2 3 知，不完备决策系统即是条件属性的取值存在空缺值的决策 系统。如表2 2 的信息系统，属性“头疼 和“体温 的取值存在空缺值， 所以表2 2 是一个不完备决策信息系统。 表2 2 不完备决策系统实例 条件属性决策 人员编号 头疼肌肉疼体温( 流感) 人员1是是正常否 人员2 毒 是 弼是 人员3是是很高是 人员4否是 毒 否 人员5否否同否 人员6否是很高是 2 。2 粒计算 粒计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度的 理论、方法、技术和工具的研究。它是词计算理论、粗糙集理论、商空闻理 论、区间计算等的超集，也是软计算科学的一个分支。它已成为模糊的、不 完整的、不精确的及海量的信息处理的重要工具和人工智麓研究领域的热点 之一。下面介绍与论文相关的粒计算基础理论。 2 2 1 粒计算的基本成分 靛( g r a n u l e s ) 、粒度( g r a n u l a r i t y ) 和粒化( g r a n u l a t e ) 是粒计算中三个 基本的概念，是粒计算的基本成分，下面分别进行详细介绍。 1 ) 粒。 粒是构成一个粒计算模型的最基本元素，或者说是粒计算模型的原语。 可以把粒看成是问题域中的一个集合，这个集合可大可小，反映在粒度上就 是粗、细粒度的闯题。 西南交通大学硕士研究生学位论文第8 页 目前在不同的模型中，对于粒的定义是不同的，并且在具体的模型中， 粒的含义也会更清晰些。例如，在以集合论为基础的模型中，粒是集合的子 集；在粗糙集、商空间理论中，粒是论域集合的子集；在定理证明中，粒可 以是一个子定理；在一个任务计划中，粒可以是一个子计划。 2 ) 粒度 一般来说，粒度是用来对粒的“大小 进行度量的，是对问题不同层次 细化的度量。同样的，采用何种“测度 也是与具体模型相关的。粒度的大 小反映了抽象的程度，也是对问题不同层次细化的度量，例如，定义为一件 交易的粒度和定义每月交易的汇总的粒度所包含的含义是不一样的。如何计 算粒度的大小，目前仍然没有统一的方法，在各个模型中都分别有各自的定 义。 3 ) 粒化 f o s t e r 通过系统地比较、分析了各种关于分级的多种描述和解释，给出 了一个关于分级的定义。他认为分级的三个基本的问题是：定义、数目以及 各级之间的关系。定义可以简单的解释为对问题的一定程度的描述和对要点 的概述；数目是对究竟该分多少级的度量，这没有一个固定的特别的值，要 依赖于具体的环境和要求；多个分级形成了多层分级理论。它包含了两个方 面的抽象含义：一，自顶向下，从多层面进行表示；二，从包含详细信息量 的观点来看，沿一个层面从包含较少的信息到包含较多的信息的变化。 2 2 2 粒计算的基本问题 粒计算主要有两个方面的问题：粒的构造和利用粒作为对象的运算、推 理。对于其中的每个问题都可以从语义和算法两个方面来进行研究。 1 ) 粒的构造 粒构造的解释主要从语义方面展开。研究的主要问题是为什么两个对象 会被分到同一个粒中。典型的元素关系是元素间的不可分辨性、相似性、亲 近性和功能性，这些关系使得不同元素可能被分到同一粒中。信息的粒化依 赖于我们所具备的知识。换句话说，我们必须对不可分辨性、相似性、亲近 性、功能性等提供必要的语义解释，对论域不同粒化诱导产生的不同的粒化 结构、粒结构进行深入研究。论域采取不同的分类方式，如等价、相容划分 就会形成不同的粒结构。在这些划分之上可以研究和比较特定的论域不同的 粒化结构的优缺点，进而做出合适的选择。 西南交通大学硕士研究生学位论文第9 页 2 ) 利用粒为对象的运算和推理 利用粒为对象的运算和推理是处理怎样利用粒去求解问题，一般要涉及 到粒、粒层和所有粒层构成的层次结构，也可以从语义和算法两个角度来研 究。包含两个方面的问题：一方面是解释各种粒度之间的关系，如接近度、 关联度，从而确定和解释粒度上的算子；另方面是设计粒度计算的算法， 如逼近、推理等。针对粒的分解与合并方法的研究，是构建任何粒度体系的 本质要求。 2 2 3 粒计算模型 粒计算的思想实质是用简单易求、低成本的足够满意近似解替代精确解。 它是词计算理论、粗糙集理论、商空间理论、区间分析理论等的超集，凡是 在分析问题和求解问题中，应用了分组、分类和聚类手段的一切理论和方法 均属于粒计算的范畴。下面介绍粒计算的主要理论模型和方法。 1 ) f u z z y 集理论的粒计算模型 z a d e h 在模糊集的基础上提出了粒度计算的一个一般框架：粒度在一般约 束的概念下被建构和定义，粒度之间的关系依据模糊图或模糊规则 ( i f t h e n ) 来表示。z a d e h 认为人类在进行判断、推理时主要是用语言进行 的，而语言是一个很粗的“粒度 ，比如说“这人很漂亮，“很漂亮 就 比较笼统，也就是说其粒度很粗，如何利用语言进行推理判断，这就引出了 “词计算 。沿z a d e h 的模糊集论的方向，用模糊数学的方法进行有关粒度计 算的方法和理论的研究，就构成“粒度计算的一个非常重要的方法和方向。 这也是人们比较熟悉的个方法。 其模型为：设x 为论域u 的可变值，x 值上的一个普遍约束可以被表示为 xi s rr ，这里r 是一个约束关系，i s r 是一个可变的连接词，r 是个具体的变量， 它的值确定了r 用什么方法来约束x 。约束的例子有相等约束、可能性约束、 模糊约束等。例如，一个相等约束：r = e ，若xi s ea ，即表示x = a 。 2 ) r o u g h 集理论的粒计算模型 粗糙集理论是由波兰华沙理工大学z p a w l a k 提出的研究不完整数据、不 精确知识的表达、学习、归纳等的方法观4 9 1 ，他提出一个假设：人的智能( 知 识) 就是一种分类的能力。在此基础上提出概念可以用论域中的子集来表示， 于是在论域中给定一组子集族，或说给定一个划分。 从数学上知道，给定x 上的一个划分，等价于在x 上给定一个等价关系r ， 西南交通大学硕士研究生学位论文第10 页 p a w l a k 称之为在论域上给定了一个知识基( x ，r ) 。然后讨论一个一般的概 念x ( x 中的一个子集) ，如何用知识基中的知识来表示，就是用知识基中的 集合的并来表示。对那些无法用( x ，r ) 中的集合的并来表示的集合，借用 拓扑中的内核和闭包的概念，引入r 下近似r ( x ) ( 相当于x 的内核) 和r - 上近似r 一( x ) ( 相当于x 的闭包) ，当足( x ) r 一( x ) 时，就称x 为粗糙集。 从而创立了“粗糙集理论 。 对于粒度空间，人们把粒度中的元素看作一个整体而不是个体，通过粒 度而丢失的信息表明论域的某些子集只能被近似地描述。粗糙集理论主要处 理的是信息粒度的近似方面，目前粗糙集理论已被广泛应用于各个领域，特 别是数据挖掘领域，并获得成功。本文研究基于r o u g h 集扩充的粒计算模型。 3 ) 商空间理论的粒计算模型 张钹，张铃教授提出的商空间理论【s 】，建立了基于商空间理论的粒计算 模型，该模型用一个三元组( x ，f ，t ) 来描述一个问题，x 表示问题的论 域，f 是一个映射，表示论域的属性函数，用f ：x y 表示，y 是n 维空间 也可以是一般的空间，t 是论域的结构，指论域x 中各元素的相互关系，分 析或求解问题( x ，f ，t ) ，是指对论域x 及有关的结构、属性进行分析和 研究。在该模型中，当x 很复杂的时，就用比较粗的粒度来考察问题，也就 是在论域x 上给出一个等价关系r ，得到一个对应于r 的商集 x 】，将对应 的三元组变为( 【x 】，【f 】，【t 】) ，称为对应于r 的商空间，从而将问题( x ， f ，t ) 转化为新层次的问题( x 】， f 】， t 】) ，逐步细化，从而将问题表示 成不同的粒度世界，达到简化问题、解决问题的目的。商空间法是将不同的 粒度世界与数学上的商集概念统一起来，表示对象模型的方法，即以商集表 示不同粒度世界的数学模型的方法，该模型着重研究不同粒度世界之间的互 相转换、互相依存的关系。 2 3 不完备决策系统的粒表示及粒计算 在粒空间下进行信息处理，就要解决粒计算中的两个问题：粒度构造及 粒度计算。本节介绍不完备信息的粒表示、粒计算和不完备决策系统的粒子 分解算法f 5 4 ，将不完备系统映射到粒子空间中。 西南交通大学硕士研究生学位论文第1 1 页 2 3 1 不完备信息的粒表示 在完备系统中，刘清教授给出了完备信息系统的粒表示1 4 5 ，其表示方法 是基于属性值的相等关系( 等价关系) 。在不完备信息系统中，由于存在未知 的属性值，完备信息系统中属性上的等值关系不能直接用于不完备信息系统。 不完备信息系统中的空值分为“遗漏和“缺省 语义，一些学者已提出一 些不完备信息系统在“遗漏语义下的粒表示方法t “】。 在“遗漏语义下，如果一个对象的某个属性值为木，在容差关系下认为 该对象与其它所有对象都具有不可分辨关系。下面给出容差关系的定义。 定义2 4 ( 容差关系) ：设s = ( u ，a ，v ，f ) 是一个不完备信息系统。其中u 是对象集，a 是条件属性集和决策属性集。对于属性集b 彳，对v x ，y u 容 差关系t 定义为： r ( x ，y ) c ，v b b ，6 ( x ) = 6 ( y ) v b ( x ) = 木v b ( y ) = 宰 ( 2 1 ) 显然，容差关系是自反和对称的，但不一定是传递的。 个体对象x u 在属性集b 上的容差类记为巧( x ) ，；( x ) = 抄ly u r ( x ，y ) ) ( 2 - 2 ) 对于某个对象x ，设a ( x ) 是x 在属性a 上的属性值，定义如下的r o u g h 逻辑公式【5 】： ( 1 ) ( a ，v ) ( 或写成a v ，a a ，1 ，圪 v 木) 是原子公式，原子公式是公式。 ( 2 ) 如果a 和b 是原子公式，那么一，a b ，a v b ，( 彳) ，aj 曰是公式。 ( 3 ) 按( 1 ) 和( 2 ) 定义的公式，使用连接词1 ，八，v ，一，h 进行有限次 运算所组成的式子是公式。 由以上定义可以看出，在容差关系下，某个属性的属性值相等( 或为宰) 的对象可以构成一个集合，且这些对象在该属性上满足不可分辨关系( 容差 关系) ，我们利用这个集合来定义粒子。 设函数厂1 ( 口，v ) 表示在属性a ( a a ) 上值为v 或木的对象集合，那么我 们给出不完备信息系统的粒子定义：g r = ( ( 口，) ，f 。1 ( 口，d ) ，我们称( a ，v ) 为粒 子g r 的语法，g r 被称为不完备信息系统中的原子粒子。 设够是形如( a ，v ) 的原子公式使用逻辑连接词1 ， ，v ，一，付所得的逻辑组 合，那么厂- 1 ( 妒) 表示满足逻辑组合缈的对象集合。我们把g r = ( 缈，f 1 ( 缈) ) 称 作满足逻辑组合缈的组合粒子。 设l s 表示信息表s 上由原子粒子和组合粒子定义的语言，它的语法可 以被递归地定义： 西南交通大学硕士研究生学位论文第12 页 ( 1 ) v a a ，( ( 口，1 ，) ，f 一( 口，1 ，) ) 是l s 中的语句。 ( 2 ) 如果伊和矽是形如( a ，v ) 的原子公式使用逻辑连接词1 ，a ，v ，寸，h 所 得的逻辑组合，那么( 1 矿，f _ 1 ( - 1 伊) ) ，( 缈 矽，f - 1 ( 伊 ) ) ，( 9 v ，f - 1 ( 驴v 矽) ) ， ( 缈寸矽，f - 1 ( 缈j 矽) ) ，( 伊付矽，厂1 ( 缈h 矽) ) 也是l s 中的语句。 ( 3 ) 有限次引用( 1 ) ，( 2 ) 得到的语句都是l s 中的语句。 对于l s 上语句的语义我们可以给出如下的定义： 厂1 ( 口，1 ，) = 缸ix u ，n ( x ) = 1 ，va ( x ) = 宰，v v oav 木) ( 2 - 3 ) f 叫( 1 缈) = u - f 。1 ( 缈) ( 2 4 ) 厂q ( 妒a 矽) = f 一( 妒) n 厂一( 矽) ( 2 - 5 ) 厂- 1 ( 妒v 矽) = f 1 ( 缈) u f - 1 ( 矽) ( 2 - 6 ) 由于不完备信息系统中对象有“遗漏 属性值，一个对象可能属于多个 容差类，因而我们不能得到不完备信息系统的粒子划分，只能得到不完备信 息系统的粒子覆盖。 定义2 5 t 5 1 ( 粒子元素集合) ：设g s ( g r ) 表示从粒子到对象集合的映射函 数，对于任意粒子g r = ( 缈，f 1 ( 妒) ) ，有g s ( g r ) = f - 1 ( 妒) 。 2 3 2 不完备决策系统的粒计算 上一节我们给出了不完备信息系统的粒表示，粒子之间也应该具有运算 规则。我们给出粒子之间的运算规则【5 4 】。 设g 5 = ( 伊，f 。1 ( 妒) ) 和g r 2 = ( 矽，厂1 ( 矽) ) 是不完备信息系统中的两个粒子， 按照经典逻辑中的五个连接词，粒子之间的运算规则则递归地定义如下： 1 g 巧1 ( 缈，f 叫( 妒) ) ( - - , t p ，f 一( 缈) ) ( 2 - 7 ) g ag r 2 亡 ( 缈，f 叫( 缈) ) a ( 矽，f 叫( 矽) ) ( 妒八矽，f - 1 ( 缈) r 、f 叫( ) ) ( 2 - 8 ) g v g r 2 车，( q o ，f _ ( 缈) ) v ( 矽，f _ 1 ( 矽) ) 铮( 伊v 矽，f 1 ( 缈) u f 叫( 矽) ) ( 2 - 9 ) 专g 吒( 伊，厂1 ( 缈) ) 一( 矽，f - 1 ( 矽) ) 营( 伊一矽，f - 1 ( 妒) 厂1 ( 矽) ) ( 2 - 1 0 ) g hg 吒营( 妒，f 一( 缈) ) h ( 矽，f _ 1 ( 矽) ) ( 伊h 矽，f _ 1 ( 妒) = f _ 1 ( 矽) ) ( 2 - 1 1 ) 粒子计算中的逻辑连接词一，不表示经典逻辑下通常意义下的蕴含关 系，它表示两个粒子元素集合的包含关系。 2 3 3 不完备决策系统的粒分解 要使用粒子思想对决策系统进行直接处理，一个首要的条件就是要获得 西南交通大学硕士研究生学位论文第13 页 足够表达决策系统信息的粒子集合，即得到决策系统的粒空间分解。 设决策系统s 分解之后的粒子集合为g r s ，其中v g r g r s ，g r 的语法 是由条件集c 中的所有条件属性来表示的，即g r = ( 缈，f 一( 缈) ) ， 伊= ( ( a l ，h ) ，( a 2 ，v 2 ) ( 口埘以) ) ，( m 刊ci ) 且满足v x u ，j 西jx g s ( g r ) 。把满足 上面条件的粒子集合称为决策表的一个粒子空间。 我们给出求不完备决策系统粒子空间g r s 的算法：以u 中的每个对象x 为中心，找出包含x 且满足上述条件的粒子。如果当前对象x 的属性值不包 含，则直接使用x 的所有属性值构造粒子；如果x 在某些属性上的属性值为 ，则从x 的容差类中分别找到在这些属性上取值不为木的记录，用它们在这 些属性上值的组合和x 不为宰的属性值构造粒子。 算法2 1 ：求决策系统粒空间的算法【5 4 1 输入：不完备决策系统s = ( u ，c u d ，v ，f ) ，c 为条件属性集，d 为决策 属性集 输出：不完备决策系统s 的一个粒子空间g r s s t e p l ：令g r s = o ，m = ici ，n = lui ，i = 1 。 s t e p 2 ：w h i l e ( i n ) 1 令u 中第i 个元素为x ； 2 如果x 中的所有元素不为奉，则构造粒子g r = ( 伊，f 1 ( 妒) ) ， 伊= ( ( c l ，c l ( x ) ) ，( c 2 ，c 2 ( x ) ) ，( c m ，q ( x ) ) ) ，c f ( x ) 为对象x 在属性q 上的取 值，厂- 1 ( 缈) = 厂- 1 ( 缈) u x ) ，g r s = g r su g r ； 3 如果x 在属性q 。，c f ：气上为宰，令x 容差类中的对象在属性 上不为宰的属性值的集合为圪，如果某个属性c o ( 1 j k ) ，x 和容差 类中的对象在该属性上的值均为宰，则取k ，为u 中对象在该属性上的 任意一个属性值p 。取x 不为木的属性值和集合u v j s ( 1 j k ) 中的属性 值进行所有可能的组合，利用每一种组合构造一个粒子 g r = ( 缈，厂- 1 ( 妒) ) ，f 一( 缈) = f 一( 缈) u z ，g 心= g r su g r ) ； 4 i = i + l 。 实例分析：对表2 3 中的不完备决策系统用算法2 1 进行粒子分解。 西南交通大学硕士研究生学位论文第14 页 表2 3 一个不完备决策系统 u q c 2c 3巳d 五 3210矽 j c 2 232o 矽 屯 2320y 而 2 木 1矽 黾 木 2 1y 2321 沙 l 3 木木 3矽 j c 8 木 0o 木 沙 而3 2l3 沙 五o 1 幸 木幸 矽 i 木 2 木木 y 五2 321 t 矽 通过算法2 1 构造不完备决策系统s 的粒子空间g r s ，构造过程如下： 1 ) 在表2 3 中的不完备决策系统中对象五在各条件属性上的取值均不为 ，构造粒子g 5 = ( 仍，f - 1 ( 仍) ) ，其中仍= ( c l ，3 ) a ( c 2 ，2 ) 人( 乞，1 ) a ( q ，0 ) ， 厂- 1 ( 仍) = f 1 ( 仍) u “ = “) ( f - 1 ( 仍)