图表示下的知识约简_苗夺谦

第2卷第6期 智 能 系 统 学 报 V ol.2 .62007年12月 CAAI T ransactions on Intelligent Systems D ec.2007粒计算研究综述王国胤1,2,张清华1,2,胡 军1,3(1.重庆邮电大学计算机科学与技术研究所,重庆400065; 2.西南交通大学信息科学与技术学院,四川成都610031;3.西安电子科技大学电子工程学院,陕西西安710071)摘 要:粒计算(gr anular computing)是当前计算智能研究领域中模拟人类思维和解决复杂问题的新方法.它覆盖了所有有关粒度的理论、方法和技术,是复杂问题求解、海量数据挖掘、模糊信息处理的有效工具.首先回顾了粒计算研究和发展状况,介绍了粒计算的基本组成和问题,综述了粒计算的基本模型和方法,并讨论了它们之间的相互关系,最后探讨了构建统一的粒计算模型、复杂问题空间的粒化、粒层之间的转换、高效的粒计算方法、新的粒计算模型、动态粒计算模型、自主粒计算模型、粒计算方法的模糊化以及粒计算模型的应用和推广等几个方面的关键问题.关键词:粒计算;数据挖掘;智能信息处理;粗糙集;模糊集;商空间中图分类号:T P18 文献标识码:A 文章编号:1673 4785(2007)06 0008 19An overview of granular computingWAN G Guo yin 1,2,ZHANG Qing hua 1,2,HU Jun 1,3(1.Institute of Comput er Science &T echno lo gy ,Cho ng qing U niversit y of Po st s and T eleco mmunications,Chong qing 400065,China;2.Scho ol of Infor matio n Science &T echnolog y,Southwest Jiao tong U niv ersit y,Chengdu 610031,China; 3.School of Electro nic Engineer ing,Xidian U niver sity,Xi an 710071,China)Abstract:In the field of com putational intelligence,granular computing (GrC)is a new w ay to simulate hu m an thinking to help solve co mplicated problems.Gr C involv es all the theories,methodo logies and tech niques o f granularity,pr oviding a pow erful to ol for the so lution of complex problems,m assiv e data min ing,and fuzzy information pr ocessing.In this paper,first the current situation and the developm ent pros pects of GrC are introduced,then the fundamental and ex isting problem s r elated to GrC ar e presented and its basic models and metho ds summ arized.Finally,som e future research topics abo ut GrC are presented,such as,uniform granular co mputing mo del,granulation of complex pro blem space,transform ation be tw een granule spaces,efficient g ranular co mputing algor ithm,nov el g ranular co mputing model,dy namic granular co mputing m odel,data driven g ranular co mputing m odel,fuzzy gr anular co mputing method,and the applications of gr anular computing models,etc.Keywords:g ranular computing;data m ining;intelligent inform ation processing;roug h sets;fuzzy sets;quotient space收稿日期:2007 04 02.基金项目:国家自然科学基金资助项目(60573068);新世纪优秀人才支持计划;重庆市教委科学技术研究资助项目(KJ060517).自Zadeh 1979年发表论文!Fuzzy sets and in form ation granularity ∀以来[1],研究人员对信息粒度化的思想产生了浓厚的兴趣.Zadeh 认为很多领域都存在信息粒的概念,只是在不同领域中的表现形式不同.自动机与系统论中的!分解与划分∀、最优控制中的!不确定性∀、区间分析里的!区间数运算∀、以及D S 证据理论中的!证据∀都与信息粒密切相关.H obss 在1985年直接用!粒度(granularity)∀作为论文题目发表论文[2],讨论了粒的分解和合并,以及如何得到不同大小的粒,并提出了产生不同大小粒的模型.Lin 在1988年提出邻域系统并研究了邻域系统与关系数据库之间的关系[3].1996年,他在U C Berkeley 大学访问时,向Zadeh 提出作!granular computing∀的研究,Zadeh称之为!g ranular mathematics∀,Lin改称为!granular co mputing∀,并缩写成Gr C.他发表了一系列关于粒计算与邻域系统的论文[4-10],主要是研究二元关系(邻域系统、Rough集和信任函数)下的粒计算模型,论述基于邻域系统的粒计算在粒结构、粒表示和粒应用等方面的问题,讨论了粒计算中的模糊集和粗糙集方法,并将粒计算方法引入数据挖掘和机器发现.依据人们在解决问题时能从不同的粒度世界去分析和观察同一问题,并且很容易地从一个粒度世界转到另一个粒度世界,张钹和张铃在1990年针对复杂问题求解,建立了一种复杂问题求解的商结构形式化体系,给出了一套解决信息融合、启发式搜索、路径规划和推理等问题的理论和算法[11-12].1997年,Zadeh进一步指出[13],世上有3个基本概念构成人类认知的基础:粒化、组织及因果关系.其中,粒化是整体分解为部分,组织是部分结合为整体,而因果关系则涉及原因与结果间的联系.物体的粒化产生一系列的粒子,每个粒子即为一簇点(物体),这些点难以区别,或相似、或接近、或以某种功能结合在一起.一般来说,粒化在本质上是分层次的,时间可粒化为年、月、日、小时、分、秒就是大家熟悉的例子.在Lin的研究基础上,Yao结合邻域系统对粒计算进行了详细的研究[14-16],发表了一系列研究成果[17-22],并将它应用于知识挖掘等领域,建立了概念之间的if then规则与粒度集合之间的包含关系,提出利用由所有划分构成的格求解一致分类问题,为数据挖掘提供了新的方法和视角.结合粗糙集理论,Yao探讨了粒计算方法在机器学习、数据分析、数据挖掘、规则提取、智能数据处理和粒逻辑等方面的应用.Yao给出了粒计算的3种观点[22]:1)从哲学角度看,粒计算是一种结构化的思想方法;2)从应用角度看,粒计算是一个通用的结构化问题求解方法;3)从计算角度看,粒计算是一个信息处理的典型方法.随着粒计算研究的发展,近年来国内外又有很多学者加入到了粒计算研究的领域.为了探讨粗糙集理论在各种环境下的应用,Skow r on[23-27]以包含度概念来研究粒近似空间上的Rough下近似和Rough上近似.刘清[28-30]在Roug h逻辑的基础上,提出了粒-逻辑的概念(G 逻辑),构造了这种逻辑的近似推理系统,并应用于医疗诊断.近几年来,在掀起粒计算研究的热潮中,商空间理论被人们广泛认识和推广,2003年张铃和张钹将模糊概念与商空间理论结合,提出模糊商空间理论,为粒计算提供了新的数学模型和工具,并成功应用于数据挖掘等领域[31-35].2002年苗夺谦等人[36]对知识的粒计算进行探讨,引入属性的重要度,并在求最小属性约简方面得到应用.王飞跃等人[37]对词计算和语言动力学进行了探讨,以词计算为基础,对问题进行动态描述、分析和综合,提出了设计、控制和评估的语言动力学系统.王国胤等人[38-44]提出了基于容差关系的粒计算模型,利用属性值上的容差关系给出了不完备信息系统的粒表示、粒运算规则和粒分解算法,同时结合粗糙集中的属性约简问题,提出了不完备信息系统在粒表示下属性必要性的判定条件,对粒计算方法在规则提取方面进行了探索.郑征等人[45-47]提出了相容粒度空间模型,并在图像纹理识别和数据挖掘中取得了成功,他们认为,人类具有根据具体的任务特性把相关数据和知识泛化或者特化成不同程度、不同大小的粒的能力,以及进一步根据这些粒和粒之间的关系进行问题求解的能力.卜东波等人[48]从信息粒度的角度剖析聚类和分类技术,试图使用信息粒度原理的框架来统一聚类和分类,指出从信息粒度的观点来看,聚类是在一个统一的粒度下进行计算,而分类却是在不同的粒度下进行计算,并根据粒度原理设计了一种新的分类算法,大规模中文文本分类的应用实践表明,这种分类算法有较强的泛化能力.Zhang等人[49-50]对粒神经网络进行了探讨,并在高效知识发现中得到很好的应用.李道国等人[51]研究了基于粒向量空间的人工神经网络模型,在一定程度上提高了人工神经网络的时效性、知识表达的可理解性.杜伟林等人[52]根据概念格[53]与粒度划分在概念聚类的过程中都是基于不同层次的概念结构来进行分类表示,而且粒度划分本身构成一个格结构的特点,研究了概念格与粒度划分格在概念描述与概念层次转换之间的联系,通过对概念的分层递阶来进行概念的泛化与例化,使概念在递阶方面忽略不必要的冗余信息.Yager[54]探讨了基于粒计算的学习方法和应用.Lin[55]在2006年粒计算国际会议上提出了新的研究思路!infrastruc tures for AI engineering∀.同时,Bargiela和Pe dry cz[56]也从各个侧面对粒计算的根源和实质进行了详细的探讨和总结.Yag er指出,发展信息粒的操作方法是当前粒计算研究的一个重要任务[57].1 粒计算的基本组成粒计算的基本组成主要包括3部分:粒子、粒层#9#第6期 王国胤,等:粒计算研究综述和粒结构.1 1 粒 子粒子是构成粒计算模型的最基本元素[58-59],是粒计算模型的原语.一个粒可以被解释为许多小颗粒构成的一个大个体,现实生活中,粒子无处不在,如在地图上观察洲、国家、海洋、大陆和山脉等是一些粗的粒子(大的粒子),观察省、市、区等是一些中等的粒子,而观察街道、饭店、机场等是一些相对较小的粒子.一个粒子可以被同时看作是由内部属性描述的个体元素的集合,以及由它的外部属性所描述的整体.一个粒子的存在仅仅在一个特定的环境中才有意义.一个粒子的元素可以是粒子,一个粒子也可以是另外一个粒子的元素.而衡量粒子!大小∀的概念是粒度,一般来讲,对粒子进行!量化∀时用粒度来反映粒化的程度[59].1 2 粒 层按照某个实际需求的粒化准则得到的所有粒子的全体构成一个粒层,是对问题空间的一种抽象化描述.根据某种关系或算子,问题空间产生相应的粒子.同一层的粒子内部往往具有相同的某种性质或功能.由于粒化的程度不同,导致同一问题空间会产生不同的粒层.粒层的内部结构是指在该粒层上的各个粒子组成的论域的结构,即粒子之间的相互关系.在问题求解中,选择最合适的粒层对于问题求解尤为关键,因为,在不同粒层求解同一问题的复杂度往往不同.在高一级粒层上的粒子能够分解成为下一级粒层上的多个粒子(增加一些属性),在低一级粒层上的多个粒子可以合并成高一级粒层上的粒子(忽略一些属性).粒计算模型的主要目标是能够在不同粒层上进行问题求解,且不同粒层上的解能够相互转化.1 3 粒结构一个粒化准则对应一个粒层,不同的粒化准则对应多个粒层,它反应了人们从不同角度、不同侧面来观察问题、理解问题、求解问题.所有粒层之间的相互联系构成一个关系结构,称为粒结构[20].粒结构给出了一个系统或者问题的结构化描述.通过从系统思维、复杂系统理论和层次结构理论(技术)中得到的启发至少需要确定一个粒结构网[20]中3个层次的结构:粒子的内部结构、粒子集结构和粒子网的层次结构.粒子集的集体结构可以看作是全部层次结构中一个层次或者一个粒度视图中的结构.它本身可以看作是粒的内部连接网络.对于同一个系统或者同一个问题,许多解释和描述可能是同时存在的.所以,粒结构需要被模型化为多种层次结构,以及在一个层次结构中的不同层次.虽然一个粒子在某个粒层上被视为一个整体,但粒子内部元素(子粒子)的结构在问题求解时也很重要,因为它能提供粒子更为详细的特性.而在同一层上的粒子之间也具有某种特殊的结构,它们可能是相互独立,或者部分包含.如果同一粒层上的粒子之间的独立性越好,可能问题求解后合并起来越方便;反之,如果粒子之间的相关性越好,则问题求解后的合并工作相对越繁杂.粒子网的层次结构是对整个问题空间的概括,它的复杂性在一定程度上决定了问题求解的复杂程度.2 粒计算的基本问题粒计算中存在2个最基本的问题,即粒化和粒的计算.问题空间的粒化是指将问题空间分解为许多子空间,或是基于有用的信息和知识将问题空间中的个体聚集成不同的类,这些类称之为粒.粒中的元素可以理解为对应概念的实例.可以把粒计算和概念生成、知识发现和数据挖掘联系起来,因为概念生成的目的之一是对具有某些概念的粒的表示、特征化、描述和解释,而知识发现和数据挖掘就是在粒之间建立关联和因果等联系.2 1 粒 化粒化是问题求解空间的一个构造性过程,它可以简单理解为在给定粒化准则下得到一个粒层的过程,是粒计算基础单元的构建,包括粒子、粒视图、粒网和层次结构.在不同的粒化准则下就得到多个粒层,进而得到粒层的网络结构.通常的粒化方法有自顶而下通过分解粗粒子得到细粒子的方法,和自底向上将细粒子通过合并得到粗粒子的方法.粒化过程是粒计算的必要过程.问题空间的粒化过程主要涉及粒化准则、粒化算法(方法)、粒子和粒结构的表示(描述)以及粒子和粒结构的定性(定量)描述等问题[59].粒化准则主要是语义方面的问题,解决为什么2个对象能放进同一个粒子内的问题.它是根据实际问题求解的具体需求和具体精度要求得到的.粒化准则的一个基本要求是忽略掉那些无关紧要的细节,从而达到降低问题求解复杂度的目的.粒化方法面对实际问题,回答如何对问题空间进行粒化,采用什么算法或工具实现粒层的构造,它属于算法方面的问题.如在粗糙集理论中,如何对对象集进行划分产生粒层,如何高效实现属性的约简等问题.粒子的结构描述主要是用粒化方法得到的粒子,如何用形式化的语言表述出来,以便后面进行计算.例如在粗糙集理论模型中,粒子的表示可能是一个子集.而#10#智 能 系 统 学 报 第2卷在概念格理论中,粒子的表述就是一个概念,它包括概念的外延(一个对象子集)和内涵(一个属性子集) 2部分.粒结构的描述往往形式多样,在商空间理论模型中,粒结构是一种分层递阶的结构,在概念格模型中,粒结构是一种H asse图.粒子和粒结构的定性、定量描述主要指粒子和粒结构的大小(主要是指粒度的结果)和复杂性度量.当前,成功的粒化方法往往都是以将解空间形成划分空间为主要的目标,这样便于将子空间上的解合成原问题空间的解,商空间理论就是这样一个成功的实例.当然,如果用某种粒化方法形成的解空间不是划分(如覆盖),这将增加合成的复杂度.2 2 粒的计算以粒子为运算对象进行问题的求解或推理,是狭义的粒计算.粒计算可以通过系统访问粒结构来解决问题,包括在层次结构中向上和向下2个方向的交互,以及在同一层次内的移动,主要分为2种[59]:同一粒层上粒子之间相互转换和推理,不同粒层上粒子之间的转换或推理.不同粒层之间的联系可以由映射来表示,在不同粒层上同一问题以不同的粒度、不同的细节表示,粒层之间的映射就建立了同一问题的不同细节描述之间的关系.商空间理论模型就是通过自然投影建立了分层递阶的商空间链式结构.粒计算的主要特点是同一问题的解可以在不同粒层之间自由转化.正是基于这一点,人们才能用粒计算方法高效地实现复杂问题的求解.模糊商空间上的分层递阶结构可以通过模糊等价关系的截关系建立相应的转化联系;粗糙集理论中的划分粒度可以通过属性的增加或删减来控制;而概念格理论模型中的概念粒子的相互转化可以通过改变概念的内涵来实现.这些转化虽然方式不同,但一个共同的特点是在转化的过程中,问题求解的重要性质必须能在不同粒层上表现出来,这也是评价粒化方法好坏的一个重要指标.如果在粒化后粒层之间的相互转化过程中,某些重要属性不能体现出来,这不但不利于问题的求解,反而会导致问题求解过程发散,从而增加问题求解的复杂度.商空间理论模型中的!保真∀和!保假∀原理使得粒化后形成的商空间具有!保序∀性,使得问题求解的搜索空间大大减少,复杂度由相乘变为相加.粒计算的2个基本问题中,粒化是关键,它直接决定粒计算的成功与否.因此,粒化方法是人们研究的热点问题.目前,粒化方法很多,如基于等价关系的划分产生粒子[17],基于模糊集产生模糊信息粒[1],基于模糊等价关系截集产生分层递阶粒空间[35],基于概念格产生概念信息粒和概念知识粒[60],基于邻域系统产生邻域粒子[3]等等.总之,粒计算是一个多准则学科,它从许多领域中获得其基本的思想、准则和方法,是基于不同层次粒度和细节的问题求解的一般性理论.在粒计算的!大伞∀下进行统一的研究,可以发现不同学科之间原理的关联,它与具体的学科研究是相互独立的[59].一旦掌握了粒计算中的结构化思维和结构化问题求解的抽象思想,就可以很容易地在任何领域中运用.3 粒计算的主要模型与理论方法3 1 词计算模型高标准的精确表达,普遍存在于数学、化学、工程学和另外一些!硬∀科学之中,而不精确表达却普遍存在于社会、心理、政治、历史、哲学、语言、人类学、文学、文艺及相关的领域中[61].针对复杂且非明晰定义的现象,无法用精确的数学方法来描述,但可以用一些程度词语,如不很可能、十分不可能、极不可能等,来对某些模糊概念进行修饰.尽管普通的精确方法(如数学)在某些科学领域应用相当广泛,也一直尝试着应用到人文学科中,但人们在长期的实践中已经清楚地认识到精确的方法应用到人文学科有很大的局限性.面对巨大而又复杂的人文学科系统,区别于传统方法的新方法∃∃∃模糊计算方法被Zadeh提出.在人类的认识中,粒的模糊性直接源于无区别、相似性、接近性以及功能性等这些概念的模糊性.人类具有在不精确性、部分知识、部分确定以及部分真实的环境下作出合理决策这一不同寻常的能力,而模糊信息粒化正是这种能力的基础.在模糊逻辑中,模糊信息粒化是语言变量、模糊!if then∀规则以及模糊图的基础.词计算(com puting w ith w o rds)是用词语代替数进行计算及推理的方法[62].如何利用语言进行推理判断,这就要进行词计算.信息粒化为词计算提供了前提条件,词计算在信息粒度、语言变量和约束概念上产生了自己的理论与方法,意在解决模糊集合论的数值化隶属度函数表示法的局限性、表达的概念缺乏前后联系、逻辑表达和算子实现的复杂性等问题,使它们能够更符合人类的思维特点.词计算有狭义和广义2个方面的概念.狭义的模糊词计算理论是指利用通常意义下的数学概念和运算(如加、减、乘、除等)构造的带有语义的模糊数值型的词计算的理论体系;广义的词计算理论统指用词进行推理、用词构建原型系统和用词编程,前者是后者的基#11#第6期 王国胤,等:粒计算研究综述础[63].模糊逻辑在词计算中起中心作用,它可以近似地被认为与词计算相同[62].在词计算中存在2个核心问题:模糊约束的表现问题和模糊约束的繁殖问题,它们是模糊信息粒化的基本准则.信息粒化(infor mation granulation)是粒化的一种形式.在众多的信息粒化中,非模糊粒化的方法很多,如将问题求解空间形成划分空间,每个粒子都是精确的.但这种粒化方法不能解决很多现实问题,如将人的头部粒化为脸、鼻子、额头、耳朵、头盖、脖子等粒子,这些粒子之间没有明确的分界线,它们都是模糊的粒子.模糊信息粒化是传统信息粒化的一种推广.模糊信息粒化理论[64-65](theor y of fuzzy information g ranulation,TFIG)建立在模糊逻辑和信息粒化方法基础之上,是从人类利用模糊信息粒化方式中获得的启发,其方法的实质是数学.Zadeh指出[64],除模糊逻辑外,没有一种方法能提供概念框架及相关技术,它能在模糊信息粒化起主导作用.继Zadeh之后,许多学者开始了有关词计算的研究工作,Wang[66]编写了词计算一书.广义词计算理论的研究工作,中国刚刚起步,李征等人[67-68]通过研究模糊控制器的结构,认为模糊控制实际上是应用了信息粒化和词计算技术,但却只是应用了该技术的初级形式,而基于信息粒化和词计算(IGCW)的模糊控制系统,将具有更强的信息处理和推理判断能力,是对人类智能更高程度的模拟.他们指出,基于信息粒化和词计算的模糊控制系统是通过信息粒化和重组、多层次的思维决策,动态地改变下层控制器的参数和推理方法或控制规则,因而使控制器具有变结构和多模态的特性.信息太多会延误推理计算的时间,给系统带来不必要的处理任务;而信息太少,则会降低推理结果的完善性.因此,提出了合理重新组织信息的研究课题.随着近年来智能信息处理的不断深入与普及,特别是处理复杂系统分析与评估时的迫切需要,人们越来越发现排除自然语言的代价太大了.首先,从应用角度来看,人类已习惯于用自然语言描述和分析事物,特别是涉及社会、政治、经济和管理中的复杂过程.人类可以方便地利用以自然语言表示的前提进行推理和计算,并得到用自然语言表达的结果;其次,从理论角度来看,不利用自然语言,现有的理论很难甚至不能够处理感性信息,而只能处理测度信息.感性信息或知识通常只能用自然语言来描述,由于人类分辨细节和存储信息的认知能力的内在限制,感性信息在本质上是不精确的[69-72].W ang利用自然语言知识和信息,建立以词计算为基础的语言动力学系统(linguistic dynamic system s,LDS),并通过融合几个不同领域的概念和方法[37],提出基于词计算的语言动力学系统的计算理论框架,根据这个计算理论框架,利用常规或传统数值动力学系统中已有的成熟概念和方法,对语言动力学系统进行动力学分析、设计、控制和性能评估.这些研究的目的是建立连接人类的语言知识表示与计算机的数字知识表示的桥梁,成为下一代智能化人机交互的理论基础之一.总之,词计算理论和方法对于复杂信息系统的模糊推理和控制非常重要,但由于自身的局限性,它必须和其他理论体系相结合,才能更有效地处理复杂信息.3 2 粗糙集模型一个对象属于某个集合的程度随着属性粒度的不同而不同,为了更好地刻画集合边界的模糊性,波兰学者Paw lak[73]在20世纪80年代提出了粗糙集理论,其本质思想是利用不可分辨关系(等价关系)来建立论域的一个划分,得到不区分的等价类(即不同属性粒度下的概念粒),从而建立一个近似空间(由不同大小的概念粒形成).在近似空间上,用2个精确的集合(上近似集和下近似集)来逼近一个边界模糊的集合.如果近似空间的粒度较粗,被近似的集合的边界域较宽,而如果近似空间的粒度较细,被近似集合的边界域较窄.给定集合X上的一个划分等价于在X上给定一个等价关系R.X/R表示U上由R导出的所有等价类,[x]R表示包含元素x的等价类,其中x%U. Paw lak称之为在论域上给定了一个知识基(X,R),然后讨论一个一般的概念X(U中的一个子集)如何用知识基中的知识来表示.对那些无法用(X,R)中的集合的并来表示的集合,借用拓扑中的内核和闭包的概念,引入下近似和上近似的概念:R-(X)= {x%U|[x]R X}和R-(X)={x%U|[x]R&X∋ }.当R-(X)∋R-(X)时,就称X为粗糙集,从而创立了!粗糙集理论∀.粗糙集理论是一种软计算方法.软计算(soft computing)概念是由模糊集创始人Zadea提出的[61-65].传统的计算方法即所谓硬计算,使用精确、固定和不变的算法来表达和解决问题;而软计算的指导原则是利用所允许的不精确、不确定性和部分真实性得到易于处理、鲁棒性强和成本较低的解决方案,以便更好地与现实系统相协调.粗糙集理论的研究,已经经历了20多年的时间,无论是在系统理论、计算模型的建立和应用系统的研制开发上,都已经取得了很多成果,也建立了一套较为完善的粗糙集理论体系[74-75].目前粗糙集理#12#智 能 系 统 学 报 第2卷。

证据理论与熵值融合的知识约简新方法吴根秀;吴恒;黄涛【摘要】求解决策表的最小约简已被证明是NP-hard问题，在粗糙集和证据理论的基础上提出了一种知识约简的启发式算法。

利用粗糙集等价划分的概念给出属性的信息熵，定义每个属性的熵值重要性并由此确定知识的核。

引入二分mass函数对每个属性建立一个证据函数，证据融合得到每个属性的证据重要性。

以核为起点，以证据重要性为启发，依次加入属性直至满足约简条件。

实例表明，该方法能够快速找到核和相对约简，并且该约简运用到分类上正确率也是较高的。

%It is proved that solving the minimal reduction of decision table is a NP-hard problem. This paper puts on a heuristic algorithm based on rough set and evidence theory. It gives attribute information entropy by using the concept of equivalence partitioning of rough set, and defines the attribute importance to get the core of the knowledge. It establishes an evidence function for each attribute by the concept of dichotomous mass functions, combining which to get the evi-dence importance of each attribute. Setthe core as the start of the algorithm and make size of attributes importance as heu-ristic information until it meets the reduction condition. Examples show that it can find the core and reduction quickly, and the reduction used in classification accuracy is higher.【期刊名称】《计算机工程与应用》【年(卷),期】2016(052)019【总页数】4页(P167-170)【关键词】粗糙集;知识约简;二分mass函数;熵;属性重要性【作者】吴根秀;吴恒;黄涛【作者单位】江西师范大学数学与信息科学学院，南昌 330022;江西师范大学数学与信息科学学院，南昌 330022;江西师范大学数学与信息科学学院，南昌330022【正文语种】中文【中图分类】TP31WU Genxiu，WU Heng，HUANG Tao.Computer Engineering and Applications，2016，52（19）：167-170. Rough Set［1］是波兰数学家Pawlak于1982年提出的，该理论是一种处理不精确、不完全与不相容知识的数学方法。

收稿日期:2003-09-281 作者简介:郭秀娟(1961～),女,吉林省德惠市人,副教授,在读博士研究生.文章编号:100920185(2004)0120049205数据挖掘方法综述郭　秀　娟(吉林建筑工程学院计算机科学与工程系,长春　130021)摘要:数据挖掘方法结合了数据库技术、机器学习、统计学等领域的知识,从深层次挖掘有效的模式.数据挖掘技术的常见方法,关联规则、决策树、神经网络、粗糙集法、聚类方法、遗传算法和统计分析方法被应用到各个领域,数据挖掘技术具有广泛的应用前景.关键词:数据挖掘;挖掘工具;挖掘方法;挖掘理论中图分类号:N 37 文献标识码:A 数据挖掘(Data Mining )是从大量的、不完全的、有噪声的、模糊的和随机的数据中,提取隐含在其中的、人们事先不知道的,但又是潜在有用的信息和知识的过程[1-2].人们把原始数据看作是形成知识的源泉,就像从矿石中采矿一样,原始数据可以是结构化的,如关系数据库中的数据,也可以是半结构化的,如文本、图形、图像数据,甚至是分布在网络上的异构型数据.发现知识的方法可以是数学的,可以是非数学的,也可以是演绎的或是归纳的.发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等,还可以用于数据自身的维护.可以说数据挖掘是一门很广义的交叉学科,它汇聚了不同领域的研究者,尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员[2].数据挖掘技术从一开始就是面向应用领域,它不仅是面向特定数据库的简单检索查询调用,而且,要对数据进行微观、中观乃至宏观的统计、分析、综合和推理,以指定实际问题的求解,企图发现事件间的相互关联,甚至利用已有的数据对未来的活动进行预测.1　数据挖掘的方法 研究的对象是大量的隐藏在数据内部的有用信息,如何获取信息是我们所要解决的问题.数据挖掘从一个新的角度把数据库技术、人工智能、统计学等领域结合起来,从更深层次发掘存在于数据内部新颖、有效、具有潜在效用的乃至最终可理解的模式.在数据挖掘中,数据分为训练数据、测试数据和应用数据3部分.数据挖掘的关键是在训练数据中发现事实,以测试数据作为检验和修正理论的依据,把知识应用到数据中.数据挖掘利用了分类、关联规则、序列分析、群体分析、机器学习、知识发现及其他统计方法,能够通过数据的分析,预测未来.数据挖掘有以下几种常用方法:111　关联规则挖掘 1993年,R 1Agrawal 等人首先提出了关联规则挖掘问题,他描述的是数据库中一组数据项之间某种潜在关联关系的规则.一个典型的例子是:在超市中,90%的顾客在购买面包和黄油的同时,也会购买牛奶.直观的意义是:顾客在购买某种商品时有多大的倾向会购买另外一些商品.找出所有类似的关联规则,对于企业确定生产销售、产品分类设计、市场分析等多方面是有价值的.关联规则是数据挖掘研究的主要模式之一,侧重于确定数据中不同领域之间的关系,找出满足给定条件下的多个域间的依赖关系.关联规则挖掘对象一般是大型数据库(Transactional Database ),该规则一般表示式为:A 1∧A 2∧…A m =>B 1∧B 2∧…B m ,其中,A k (k =1,2,…,m ),B j (j =1,2,…,n )是数据库中的数据项.有Support (A =>B )=P (A ∪B ),Confidence (A =>B )=P (A|B )1数据项之间的　第21卷　第1期2004年3月吉　林　建　筑　工　程　学　院　学　报Journal of Jilin Architectural and Civil Engineering Institute Vol.21　No.1Mar 12004　05吉　林　建　筑　工　程　学　院　学　报第21卷关联,即根据一个事务中某些数据项的出现可以导出另一些数据项在同一事务中的出现[3-4].在关联规则挖掘法的研究中,算法的效率是核心问题,如何提高算法的效率是所要解决的关键.最有影响的是Apriori算法,它探查逐级挖掘,Apriori的性质是频繁项集的所有非空子集都必须是频繁的.112　决策树方法 决策树(decision tree)根据不同的特征,以树型结构表示分类或决策集合,产生规则和发现规律.利用信息论中的互信息(信息增益)寻找数据库中具有最大信息量的字段,建立决策树的一个结点,再根据字段的不同取值建立树的分枝.在每个分枝子集中,重复建立树的下层结点和分枝的过程,即可建立决策树.决策树起源于概念学习系统CL S(Concept Learning System)[5],其思路是找出最有分辨能力的属性,把数据库划分为多个子集(对应树的一个分枝),构成一个分枝过程,然后对每一个子集递归调用分枝过程,直到所有子集包含同一类型的数据.最后得到的决策树能对新的例子进行分类.CL S的不足是它处理的学习问题不能太大.为此,Quinlan提出了著名的ID3学习算法[6],通过选择窗口来形成决策树.从示例学习最优化的角度分析,理想的决策树分为3种:①叶子数最少;②叶子结点深度最小;③叶结点数最少且叶子结点深度最小.寻优最优决策树已被证明是N P困难问题.ID3算法借用信息论中的互信息(信息增益),从单一属性分辨能力的度量,试图减少树的平均深度,却忽略了叶子数目的研究.其启发式函数并不是最优的,存在的主要问题有:(1)互信息的计算依赖于属性取值的数目多少,而属性取值较多的属性并不一定最优.(2)ID3是非递增学习算法.(3)ID3决策树是单变量决策树(在分枝结点上只考虑单个属性),许多复杂概念表达困难,属性间的相互关系强调不够,容易导致决策树中子树的重复或有些属性在决策树的某一路径上被检验多次.(4)抗噪声性差,训练例子中,正例和反例的比例较难控制.针对上述问题,出现许多较好的改进算法,刘晓虎等在选择一个新属性时,并不仅仅计算该属性引起的信息增益,而是同时考虑树的两层结点,即选择该属性后继续选择属性带来的信息增益.Schlimmer和Fisher设计了ID4递增式算法,通过修改ID3算法,在每个可能的决策树结点创建一系列表,每个表由未检测属性值及其示例组成,当处理新例时,每个属性值的正例和反例递增计量.在ID4的基础上,Utgoff 提出了ID5算法,它抛弃了旧的检测属性下面的子树,从下面选择属性构造树.此外,还有许多算法使用了多变量决策树的形式,著名的C415系统也是基于决策树的.113　神经网络方法 模拟人脑神经元方法,以MP模型和HEBB学习规则为基础,建立了3大类多种神经网络模型,即前馈式网络、反馈式网络、自组织网络.它是一种通过训练来学习的非线性预测模型,可以完成分类、聚类等多种数据挖掘任务.神经网络(neural network)是由大量的简单神经元,通过极其丰富和完善的连接而构成的自适应非线性动态系统,并具有分布存储、联想记忆、大规模并行处理、自组织、自学习、自适应等功能[7].网络能够模拟人类大脑的结构和功能,采用某种学习算法从训练样本中学习,并将获取的知识存储于网络各单元之间的连接权中,神经网络和基于符号的传统A I技术相比,具有直观性、并行性和抗噪声性.目前,已出现了许多网络模型和学习算法,主要用于分类、优化、模式识别、预测和控制等领域.在数据挖掘领域,主要采用前向神经网络提取分类规则.神经网络模拟人的形象直觉思维,其中,最大的缺点是“黑箱”性,人们难以理解网络的学习和决策过程.因此,有必要建立“白化”机制,用规则解释网络的权值矩阵,为决策支持和数据挖掘提供说明,使从网络中提取知识成为自动获取的手段.通常有两种解决方案:①建立一个基于规则的系统辅助.神经网络运行的同时,将其输入和输出模式给基于规则的系统,然后用反向关联规则完成网络的推理过程.这种方法把网络的运行过程和解释过程用两套系统实现,开销大,不够灵活;②直接从训练好的网络中提取(分类)规则.这是当前数据挖掘使用得比较多的方法.从网络中采掘规则,主要有以下倾向:(1)网络结构分解的规则提取.它以神经网络的隐层结点和输出层结点为研究对象,把整个网络分解为许多单层子网的组合.这样研究较简单的子网,便于从中挖掘知识.Fu 的KT 算法和Towell 的MofM 算法是有代表性的方法.KT 方法的缺点是通用性差,且当网络比较复杂时,要对网络进行结构的剪枝和删除冗余结点等预处理工作.(2)神经网络的非线性映射关系提取规则.这种方法直接从网络输入和输出层数据入手,不考虑网络的隐层结构,避免了基于结构分解的规则提取算法的不足.Sestito 等人的相似权值法,以及CSW 算法(将网络输入扩展到连续取值),是其中的两种典型算法.当然,在数据挖掘领域,神经网络的规则提取还存在许多问题,即如何进一步降低算法的复杂度,提高所提取规则的可理解性及算法的适用性,研究提取规则集的评估标准和在训练中从神经网络动态提取规则,以及及时修正神经网络并提高神经网络性能等,都是进一步研究的方向.114　粗集方法粗集(rough set )理论的特点是不需要预先给定某些特征或属性的数量描述[4,8],如统计学中的概率分布,模糊集理论中的隶属度或隶属函数等,而是直接从给定问题出发,通过不可分辨关系和不可分辨类确定问题的近似域,从而找出该问题中的内在规律.粗集理论同模糊集、神经网络、证据理论等其它理论均成为不确定性计算的一个重要分支.粗集理论是根据目前已有的给定问题的知识,将问题的论域进行划分,然后对划分后的每一个组成部分确定其对某一概念的支持度,即肯定支持此概念或不支持此概念.在粗集理论中,上述情况分别用3个近似集合来表示正域、负域和边界.在数据挖掘中,从实际系统采集到的数据可能包含各种噪声,存在许多不确定的因素和不完全信息有待处理.传统的不确定信息处理方法,如模糊集理论、证据理论和概率统计理论等,因需要数据的附加信息或先验知识(难以得到),有时在处理大量数据的数据库方面无能为力.粗集作为一种软计算方法,可以克服传统不确定处理方法的不足,并且和它们有机结合,可望进一步增强对不确定、不完全信息的处理能力.粗集理论中,知识被定义为对事物的分类能力.这种能力由上近似集、下近似集、等价关系等概念体现.因为粗集处理的对象是类似二维关系表的信息表(决策表).目前,成熟的关系数据库管理系统和新发展起来的数据仓库管理系统,为粗集的数据挖掘奠定了坚实的基础.粗集从决策表挖掘规则,辅助决策,其关键步骤是求值约简或数据浓缩,包括属性约简Wong SK 和Ziarko W 已经证明求最小约简是一个N P hard 问题[9].最小约简的求解需要属性约简和值约简两个过程,决策表约简涉及到核和差别矩阵两个重要概念.一般来讲,决策表的相对约简有许多,最小约简(含有最小属性)是人们期望的.另一方面,决策表的核是唯一的,它定义为所有约简的交集,所以,核可以作为求解最小约简的起点.差别矩阵突出属性的分辨能力,从中可以求出决策表的核,以及约简规则.借助启发式搜索解决,苗夺谦等人从信息论的角度对属性的重要性作了定义,并在此基础上提出了一种新的知识约简算法M IBAR K ,但其对最小约简都是不完备的.此外,上述方法还只局限于完全决策表.Marzena K 应用差别矩阵,推广了等价关系(相似关系)、集合近似等概念,研究了不完全决策表(属性的取值含有空值的情况)的规则的发展问题,从而为粗集的实用化迈出了可喜的一步.Marzena K 还比较了几种不完全系统的分析方法,得出如下结论:①一个规则是确定的,如果此规则在原不完全系统的每个完全拓展中是确定的;②删除从不完全决策表包含空值的对象后,采掘的知识可能成为伪规则.粗集的数学基础是集合论,难以直接处理连续的属性.而现实决策表中连续属性是普遍存在的,因此,连续属性的离散化是制约粗集理论实用化的难点之一,这个问题一直是人工智能界关注的焦点.连续属性的离散化的根本出发点,是在尽量减少决策表信息损失的前提下(保持决策表不同类对象的可分辨关系),得到简化和浓缩的决策表,以便用粗集理论分析,获得决策所需要的知识.最优离散化问题(离散的切点数最少)已被证明是N P -hard 问题,利用一些启发式算法可以得到满意的结果.总体上讲,现有15　第1期郭秀娟:数据挖掘方法综述25吉　林　建　筑　工　程　学　院　学　报第21卷离散化方法主要分为非监督离散化和监督离散化.前者包括等宽度(将连续值属性的值域等份)和等频率离散化(每个离散化区间所含的对象相同).非监督离散化方法简单,它忽略了对象的类别信息,只能用在属性具有特殊分布的情况.针对上述问题,监督离散化方法考虑了分类信息,提高了离散效果.目前,比较有代表性的监督离散化方法有以下几种:①Holte提出了一种贪婪的单规则离散器(one rule dis2 cretizer)方法;②统计检验方法;③信息熵方法等.这些方法各有特点,但都存在一个不足,即每个属性的离散化过程是相互独立的,忽略了属性之间的关联,从而使得离散结果中含有冗余或不合理的分割点.针对这个问题,有人给出了一种连续属性的整体离散化方法,实验表明,不仅能显著减少离散化划分点和归纳规则数,而且提高了分类精度.连续属性离散化目前还存在的问题是缺乏递增的离散化方法,即当新的对象加入决策表时,原有的分割点可能不是最优或最满意的.粗集理论和其它软计算方法的结合,能够提高数据挖掘能力.Mohua Banerjee等利用集理论获得初始规则集,然后,构造对应的模糊多层神经网络(规则的置信度对应网络的连接权)[10],训练后可得到精化的知识.粗集与其它软计算方法的集成是数据挖掘的一种趋势.目前,基于粗集的数据挖掘在以下方面有待深化.(1)粗集和其它软计算方法的进一步结合问题;(2)粗集知识采掘的递增算法;(3)粗集基本运算的并行算法及硬件实现,将大幅度改善数据挖掘的效率.已有的粗集软件适用范围还很有限.决策表中的实例数量和属性数量受限制.面对大量的数据,有必要设计高效的启发式简化算法或研究实时性较好的并行算法;(4)扩大处理属性的类型范围,实际数据库的属性类型是多样的,既有离散属性,也有连续属性;既有字符属性,也有数值属性.粗集理论只能处理离散属性,因此,需要设计连续值的离散算法.115　遗传算法遗传算法(G A:genetic algorithms)是模拟生物进化过程,利用复制(选择)、交叉(重组)和变异(突变)3个基本算子优化求解的技术.遗传算法类似统计学,模型的形式必须预先确定,在算法实施的过程中,首先对求解的问题进行编码,产生初始群体,然后计算个体的适应度,再进行染色体的复制、交换、突变等操作,优胜劣汰,适者生存,直到最佳方案出现为止.遗传算法在执行过程中,每一代都有许多不同的种群个体同时存在,这些染色体中个体的保留与否取决于它们对环境的适应能力,适应性强的有更多的机会保留下来,适应性强弱是由计算适应性函数f (x)的值决定的,这个值称为适应值(fitness).适应函数f(x)的构成与目标函数有密切的关系,这个函数基本上是目标函数的变种.应用遗传算法解决实际问题,存在以下几方面的问题:(1)编码.把问题参数按某种形式进行编码形成个体,一组个体构成一个种群,编码是一项有创造性的工作,也是遗传算法应用的关键.(2)适应值函数.适应值是对种群中每个个体的评价.它涉及到的问题包括:问题的目标函数的确定、目标函数到适应值函数的映射、适应值函数调整等.(3)交叉.以一定概率P c,对两个个体进行交叉.好的交叉策略能够使种群迅速收敛到最优解.(4)变异.以一定概率P c,对个体上的某种基因(对应于位串上的某位)进行改变.变异是使当前种群进化的必不可少的条件.遗传算法的研究方向遗传算法是多学科结合与渗透的产物,它已发展成为一种自组织、自适应的综合技术,广泛应用在计算机科学、工程技术和社会科学等领域[11].它的研究工作主要集中在以下几个方面:(1)基础理论.包括进一步发展遗传算法理论的数学基础,从理论和试验方面研究它们的计算复杂性.怎样阻止过早收敛也是人们正在研究的问题之一.(2)分布并行遗传算法.遗传算法在操作上具有高度的并行性,许多研究人员都在探索在并行机和分布式系统上高效执行遗传算法的策略.(3)分类系统.分类系统是基于遗传算法的机器学习中的一类,它包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统.分类系统正在被人们越来越多地应用于科学、工程和经济领域中,是目前遗传算法研究领域中一个非常活跃的领域[12].(4)遗传神经网络.它包括联接权、网络结构和学习规则的进化.遗传算法与神经网络相结合,成功地从时间序列分析来进行财政预算.Muhienbein 分析了多层感知机网络的局限性,并预测下一代神经网络将会是遗传神经网络.(5)进化算法.模拟自然进化过程可以产生鲁棒的计算机算法———进化算法.除上述方法外,还有把数据与结果转化和表达成可视化形式的可视化技术、统计分析方法、云模型方法和归纳逻辑程序等方法[13].2　结语 数据挖掘算法是对上述挖掘方法的具体体现.数据挖掘研究具有广泛的应用前景,它既可应用于决策支持,也可应用于数据库管理系统(DBMS )中.数据挖掘作为决策支持和分析的工具,可以用于构造知识库,在DBMS 中,数据挖掘可以用于语义查询优化、完整性约束和不一致检验.参　考　文　献 [1]Han J ,K ambr M.Data Mining :Concepts and Techniques 〔M 〕.Beijing Higher Education Press ,2001. [2]　张　伟,廖晓峰,吴中福1一种基于遗传算法的聚类新方法〔J 〕1计算机科学,2002,29(6):114-1161 [3]Agrawal R ,Mannila H ,Srikant R ,et al.Fast discovery of association rules :Advances in knowledge discovery and data mining 〔M 〕.California :MIT Press ,1996:307-328. [4]Sanjay Soni Unisys ,Zhaohui Tang Microsoft Corporation ,Jim Y ang Microsoft Corporation Performance Study of Microsoft Data Mining Algorithms August ,2001. [5]　唐华松,姚耀文1数据挖掘中决策树算法的探讨〔J 〕1计算机应用研究,2001,(8):18-221 [6]　李德仁,王树良,李德毅,王新洲1论空间数据挖掘和知识发现的理论与方法〔J 〕1武汉大学学报・信息科学版,2002(6):221-2331 [7]　周志华,陈世福1神经网络集成〔J 〕1计算机学报,2002(6):587-5901 [8]　李永敏,朱善君等1基于粗糙理论的数据挖掘模型〔J 〕1清华大学学报(自然科学版),1999,39(1):110-1131 [9]Pawlak Z.Rough Set Theory and its Applications to Data Analysi 〔J 〕.Cybernetics and syst ,1998,29(7):661-688. [10]Tsumoto S.Automated discovery of positive and negative knowledge in clinical database based on rough set model 〔J 〕.IEEE EMB Mag 2azine ,2000,19(4):415-422. [11]　糜元根1数据挖掘方法的评述〔J 〕1南京化工大学学报,2001(9):105-1091 [12]　吉根林,帅　克,孙志辉1数据挖掘技术及其应用〔J 〕1南京师大学报(自然科学版),2000,23(2):25-271 [13]　李德毅,史雪梅,孟海军1隶属云和隶属云发生器〔J 〕1计算机研究与发展,1995,42(8):32-411Summary of Data Mining MethodsGUO Xiu 2juan(Depart ment of Com puter Engineering ,Jilin A rchitectural and Civil Engineering Institute ,Changchun 130021)Abstract :The good methods and technologies of data mining may get excellent knowledge.This paper presents an overview on data mining methods.First ,the concept of data mining is discussed.Then ,this paper de 2scribes the theories and technologies on data mining ,such as relational rules ,decision tree ,neural network ,rough sets ,clustering analysis ,genetic algorithms ,and statistics analysis.Finally ,how to study data mining is forecasted.K eyw ords :data mining ;mining tools ;mining methods ;data mining theories 35　第1期郭秀娟:数据挖掘方法综述。

微阵列基因选择约简方法第19卷V oLl9第21期No.21电子设计工程ElectronicDesignEngineering2011年11月NOV.2011微阵列基因选择约简方法段旭.高尚(江苏科技大学计算机学院,江苏镇江212003)摘要:提出了一个基于Spearman秩相关分析的序值决策系统的约简方法,并成功地用于微阵列基因选择.约简是知识发现的重要过程.经典的基于等价关系的粗糙集理论没有考虑系统取值的序值性,并且对数据噪声较为敏感.文中的约简方法不但考虑了个体属性值的序值关系,并且对数据噪声不敏感,因而更符合实际应用的要求.关键词:Spearman秩相关分析;微阵列基因选择;约简;粗糙集;数据噪声中图分类号:TP391.4文献标识码:A文章编号:1674—6236(2011)21—0001一o3 ReductprocessforgeneselectionofmicroarrayDUANXu,GAOShang(SchoolofComputerScience&Engineering,JiangsuUniversityofScience&Tec hnology,Zhenjiang212003,China) AbstraceBasedonSpearmanrankcorrelationanalysisonordereddecisionsystem,areductio nmethodisproposedandis successfullyusedformicroarraygeneselection.Reductionisanimportantprocessofknowleparedtotheclassicroughsettheorybased'onequivalencerelations,whichdoesnottakethevaluesystemo ftheordervalueintoaccount,andissensitivetodatanoise,thismethodnotonlyconsiderstheorderedrelationsofattributeva luesbetweenobjects,andisnotsensitivetonoise,SOitismorepractica1.Keywords:Spearmanrankcorrelationanalysis;microarraygeneselection;reduction;rough settheory;datanoise微阵列技术给生物学研究领域提供了极为丰富,详尽的基因表达信息.基因表达谱和基因表达模式对解决包括代谢途径的研究,对未知基因功能的推断,疾病诊断以及通过基因诊断来提供个性化药物治疗等在内的种类繁多的生物学和生物医学问题很有帮助.研究人员已提出了众多的基因选择及其相应的样本分类方法.检测微阵列数据分析中差异表达显着的基因的方法可分为3大类:过滤法(filters)I.1,打包法(wrappers)t2],及嵌入法(embeddedapproaches)p].无论使用以上哪种基因选择方法.将这些选择出的差异表达基因集全部用来进行样本分类,并不能取得最佳效果.由于基因的相互作用是普遍存在的,所以基因的差异表达也是相关联的,因此在全部的差异表达基因集合中仍存在大量的特征数据冗余现象.而特征冗余不但增加分类算法的计算量,随着特征基因数量的增加,其分类效果并不一定有所提高.反而有可能会下降.所以,如果将选择的差异表达基因用于样本分类,有必要对基因选择的结果进行进一步的数据约简.数据约简嗍是知识发现的重要过程.是寻求最简知识表达的重要手段.在粗糙集理论研究中求解数据约简已有众多的研究成果四.但这些研究大多是基于等价关系的约简方法.基于等价关系的粗糙集约简方法在实际应用中受到了较大的限制.首先,基于等价关系的粗糙集约简对噪声数据非常收稿日期:2011-09—03稿件编号:201109017敏感.在标准粗集约简的定义下,信息表中即使仅仅一个对象被污染,整个系统的不可分辨关系都会改变,从而可能得到完全不同的约简结果.其次,基于等价关系的粗糙集约简方法没有考虑信息系统各属性值的序值关系(可比较大小的关系),然而,在实际应用中很多系统的属性取值具有序值性.众所周知,知识发现的基础是数据样本,如果没有统计学上的证据,那么从数据样本中得出的结论其泛化能力有限.文中依据无参数统计理论.提出了一个基于秩相关分析的约简方法(RankCorrelationbasedReduct,RCR),该方法考虑了系统属性值的序值关系,其结果在数据噪声干扰下也较为稳定,因而具有较好的实际应用前景.1秩相关序值决策系统分析一个决策系统是一个四元组S=<U,AUD,厂>,其中:为论域,A为条件属性集,D为决策属性,V=U"M为Ux(AuD)一的信息函数,V a∈ATUD,∈U厂(,a)E(是属性a的值域).如果一个决策系统在各个属性上的取值均是可比较大小的,则该决策系统称为序值决策系统(OrderedDecisionSystem).基于秩相关的序值决策系统分析是根据系统中各个个体与某一标准个体的关联度大小来决策的.在单个属性(设为第个属性)意义下,序值决策系统中基金项目:国家自然科学基金(51008143);江苏省高校自然科学基金(08KJB520003)作者简介:段旭(1978一),女,陕西三原人,硕士,讲师.研究方向:模式识别与智能系统.一1一《电子设计工程)2011年第21期个体的关联系数定义为论域中两个个体在该属性指标下接近程度的一种度量,记为EU).显然,指标关联系数E(『)越大.两个个体在相应属性指标下越接近.因此,可构造一标准个体(例如,该个体在各属性指标下取最大值),通过测量论域中个体与标准个体的接近程度对被决策个体做出决策.这里,记E(『)为论域中第i个个体在第个属性指标下与标准个体的接近程度,即关联系数.仅凭单个指标的关联系数El(,)还难以对个体作出合理的决策.为计算论域中个体在所有属性指标下的综合评价值,这里引入相关度的概念,记为A.相关度A定义为论域中第i个个体综合所有属性指标的关联系数Ei()与各属性指标的重要程度埘秩次一致性的一种度量.若某一个体与标准个体的相关度A越大,则说明该个体关联系数EiU)的结构分布与指标权重结构分布吻合越好,该个体与标准个体的关联程度也越高.据此.序值决策系统的决策问题便简化为关联度数值的大小比较.1.1单个指标关联系数计算取序值决策系统中各属性值域的最大值构造标准个体勒(考虑到不同属性取值的数量级不同,在数据处理前常对序值决策系统各属性的取值作标准化处理,这时,标准个体勒各属性的取值为1),以.为参照序列,以论域中第i个个体鼍为比较序列,则XO与施在第个属性上的关联系数(,)定义为[21:):揣(1)式中6ll血l=rninminIx0U)lO)l,8~=maxmaxU)O)t,U)=‰(,)(,)l,p∈[0,l】为分辨系数,其作用是削弱最大绝对差数值太大而产生的影响.用以提高关联系数之间的差异显着性,文中研究中取值为0I3.关联系数EU)描述了标准个体.与被决策个体她间第个属性标准下的取值的接近程度,EU)越大,说明两个体在该属性标准下越相似.1.2相关度的计算设序值决策系统中各条件属性的重要性指标(权重系数)为wj(j=l,2,…,n,n为条件属性的个数),根据非参数统计理论,各属性的关联系数El()与属性权重序列的Spearman秩相关系数定义为标准个体‰与被决策个体她的相关度A:6(6J)AF1一—一(2)rtLn.-lJ式中,嘶表示第个属性权重在权重向量中由大到小的排序数,bi表示关联系数最U)在其相应的序列中的排序数.若A.=1,表示属性权重与关联系数Ei(,)之间的秩次完全相同,呈正相关;A产一1表示两者之间的秩次完全相反,呈负相关;Ai=O则表示两者之间的秩次完全无关.显然,A值越大,属性权重与关联系数El(7)之间的相关性越好,被决策个-2-体她与标准个体‰越相似.如果是分类决策,则相关度越接近的两个个体越有可能属于同一类;如果是优劣判断,则相关度越大的样本越优异(假设系统中各属性指标取值越大越优异). 2基于秩相关系数的序值系统约简根据前述讨论,系统中个体与标准个体的相关度可以作为个体特征的一种度量,而这种相关度的计算取决于个体在各属性标准下的取值.如果系统中的某个条件属性不影响个体间这种相关度的秩次,则可认为该属性是冗余的.据此,可以给出基于这种相关度的序值决策系统约简算法:1)构造序值决策系统的标准个体‰;2)根据公式(1)计算属性集A的单个指标关联系数;3)根据公式(2)计算各个个体鼍与‰的秩相关系数并构成向量A:4)从属性集减去某个属性a;重复步聚1)一3),得到相应的相关系数向量;5)计算A,的秩相关系数k,如果k大于给定的阈值,则属性.是可约简的.3微阵列数据实验为了检验上述RCR方法在真实数据上的应用效果.下面将该方法应用于4个真实的微阵列数据集进行数据约简,然后将得到的约简作为特征基因集对样本进行分类测试.实验选用了4个公开的微阵列数据集.数据集概况如表1所示.表l实验微阵列数据集概况Tab.1Summaryofmicroarraysusedforexperiments据现有文献资料统计结果,一般微阵列数据分析的差异表达基因数在200以内,考虑到各类基因选择方法的差异性,在实验之前,通过￡一统计方法旧对所各数据集中的基因排序后保留前2000个基因数据,这样的选择不会影响后续实验结果.在使用t一统计法对基因进行初选后.再将RCR方法应用于这些差异表达基因集.为了便于比较,实验中使用了研究人员经常使用的文献提供的基因选择方法(SAM方法)作为参照.基因选择结果数如表2所示.为了检验RCR方法所选择的特征基因的分类能力.实验中分别将所选得的特征基因集在SVM.k—NN以及NB几种典型的分类器进行分类试验并与SAM方法进行比较.实验结果分别如图1,2,3所示.段旭,等微阵列基因选择约简方法表2RCR及SAM方法基因选择结果Tab.2NumberofgeneselectionunderSAMandSRCRComparisonofClassifyingabl1itY ofseleeted颤nsetonk—NNclassifiel-图lSVM分类器上的特征基因集分类能力Fig.1ClassifyingabilityofselectedgensetonSVMclassifier ComparlSOnofCLassifyingabi1ityOfse1ectedgensotonNBC1assifiel-Dataset:l—Leukemia,2-Lungcaricer,3-PYOState,4-DLBCL图2k—NN分类器上的特征基因集分类能力Fig.2Classifyingabilityofselectedgensetonk-NNclassifier虽然RCR方法所选择的特征基因数量要远小于SAM方法所确定的差异表达基因总数.但从图3中可以看出.这些特征基因集同样具备较好的样本分类能力.虽然在SVM分类器上,RCR方法所选择的特征基因集的分类能力没有明显的优势,但在k—NN和NB分类器上,这些经过约简的特征基因集其分类效果却比存在较大冗余的SAM方法选择的基因集分类效果要好.其主要原因是k-NN分类器在特征基因数较多时易产生过拟合现象.而NB分类器则要求各特征基因之间相互独立.这两点是微阵列数据分类的主要问题之一.4结论文中提出了一个基于秩相关性分析的数据约简方法.与CompariSOnofClass[fyingabi1itY ofseIeetedgenera1setonSVMC1assifierDataset:l—Leukemia,2-Lungcancer,3-Prostate,4-DLBCL图3NB分类器上的特征基因集分类能力Fig-3ClassifyingabilityofselectedgensetonNBclassifier传统的粗糙集中基于等价关系的数据约简方法相比.该方法不但考虑了决策系统中属性取值的序值性.还避免了基于等价关系的属性约简方法对数据噪声的过敏感的不足.实验结果表明.较之研究人员常用的基因选择方法,该方法在微阵列数据分析中明显提高所选择的基因集的分类能力.参考文献:【1]HwangT,SunCH,YunT,eta1.FIGS:afilter-basedgene selectionworkbenchformicroarrayda切BMCBioinformatics, 2010,11(1):50.[2】BlancoR.,LarranagaP.,InzaI.,eta1.Geneselectionfor cancerclassificationusingwrapperapproaches[J1.Internati0nalJournalofPatternRecognitionandArtificial Intenigence,2004,18(8):1373—1390.【3】"B,ZhengCH,HuangDS,eta1.Geneexpressiondata classificationusinglocallylineardiscriminantembedding[J]. ComputersinBiologyandMedicine,2010,40(10):802-810.『4】支天云,苗夺谦.二进制可辨矩阵的变换及高效属性约简算法的构造[J].计算机科学,2002,29(2):140-142,146.ZHITian-yun,MIAODuo-qian.ThebinarydiscernibilityMatrix'Stransformationandhighefficiencyattributes reductionalgorithm'Sconformation[J].ComputerScience,2002,29(2):140—142,146.【5】黄金杰,李士勇,左兴权.一种T—S型粗糙模糊控制器的设计与仿真[J].系统仿真,2004,16(3):480--484.HUANGJin-jie,LIShi-yong,ZUOXing—quan.edesign andsimulationofaT?Stypeofroughfuzzycontroller【J】. JournalofSystemSimulation,20o4,16(3):180-484.[6】FoxRJ,DimmicMW.Atwo—sampleBayesiant-testfor microarraydata[J].BMCBioinformatics,2006,7:126.-3-。