一种基于分辨矩阵的属性约简改进算法.pdf

《一种基于分辨矩阵的属性约简改进算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第20卷第3期兰州工业学院学报Vol_20No．32013年6月JoumalofLanzhouInstituteofTechnologyJun．2013文章编号：1009—2269(2013)03—0018—04一种基于分辨矩阵的属性约简改进算法吕林霞(兰州工业学院软件工程系，甘肃兰州730050)摘要：运用粗糙集理论，对基于分辨矩阵的属性约简，提出了一种改进算法．该算法通过对分辨矩阵的简化处理，化简分辨函数，快速求解分辨函数的最小析取范式，从而得到决策表的核和所有约简．该算法简化了分辨函数的求解过程，经实例验证该算法简单、快速、有

2、效．关键词：分辨矩阵；属性约简；粗糙集；决策系统中图法分类号：TP391．1文献标志码：A0引言1粗糙集基本理论波兰科学家Z·Pawlak教授于1982年提出了1．1决策表一种处理不精确、不确定知识的粗糙集理论¨，它在粗糙集中，信息系统是对知识进行表达和处是一种在保持分类能力不变的情况下，通过知识约理的基本工具。决策表是一类特殊而重要的信息简，导出问题的决策和分类规则，客观揭示潜在规系统，它表示当满足某些条件时，决策(行为、操律的数学工具．经过多年的研究与发展，粗糙集理作、控制)应当如何进行．论已在理论和实际应用上取得了长足的发展，

3、特别定义1S=(U，A，是一个信息系统，其是近二十年间，在知识发现等领域得到了成功的应中表示对象的非空有限集合，统称为论域；A表用，受到国际学术界广泛关注．目前正被广泛应用示属性的非空有限集合；V=U，其中是属于规则提取、机器学习、决策分析、过程控制、模式aEH识别和数据挖掘等领域引．属性约简是粗糙集理性0∈A的值域；f：U×A—I，是一个信息函数，它论中的重要研究内容之一．常见的有Z·Pawlak提为每个对象的每个属性赋予唯一的信息值，即：对出的基于正区域的属性约简¨J，基于信息熵的属VM∈U，Vn∈A，有，(u，0)∈．性约简]

4、，基于分辨矩阵的属性约简。．由于基定义2在信息系统S=(U，A，中，如果于分辨矩阵的属性约简定义直观，易于理解，能快A=CUD，D={d}，且cnD=，子集c和速求出核和所有约简，故这种属性约简得到成功应D分别称为条件属性和决策属性，那么信息系统Js用．基于分辨矩阵的属性约简算法，首先计算分辨则称为决策信息系统，简称为决策表，简记为S=矩阵，由分辨矩阵生成分辨函数，求分辨函数的最(，A)或S=(U，CUD)．小析取分量，以此推出决策表的属性约简．但是分1．2属性约简辨函数的最小析取分量的计算，常常较为复杂．对基于粗糙集的知识获取，主

5、要是通过对决策表此，本文提出了一种改进算法，可以大大简化分辨函数，快速求得最小析取分量．的属性约简．收稿日期：2013-03-19基金项目：甘肃省自然科学研究基金计划(1208RJZA186)；甘肃省技术研究与开发专项计划(1205TCYA037)作者简介：吕林霞(1964·)，女，陕西岐山人，副教授．第2期吕林霞：一种基于分辨矩阵的属性约简改进算法·19·定义3在决策表S=(，A)中，对0∈A，分辨函数的每个析取分量即对应于决策表的如果INZ)(A一{0})：IND(A)，则称属性0在一个约简．但是，整理分辨函数，求解分辨函数的最

6、中是不必要的；否则称属性口在A中是必要的．小析取分量常常比较复杂．本文通过对分辨矩阵的定义4在决策表S=(，)中，A=CuD，简化，简化分辨函数，求解最小析取分量．CnD=，C中所有必要属性组成的集合称为2基于分辨矩阵属性约简的改进算法属性集的核，记作：Core(a)．2．1分辨矩阵的简化定义5在决策表S=(，4)中，PA，如果对每个0∈P在P中都是必要的，则称P是独立根据合取的吸收律，可以得到如下性质．的；否则，称P是相关的．性质2S是一个决策表，(S)=(m)⋯为其分辨矩阵．找出分辨矩阵中屙l生个数最少的元相关属性集中含有冗余属

7、性，而独立属性集去掉任何一个属性，都将破坏决策信息系统的分类能素，逐一对矩阵的所有其它非空且属性个数等于或多于此项的元素进行检查和简化：如果其中包含此力．定义6在决策表S：(，A)中，对于PA，项的所有属性，则将被检查的元素置为空．对简化后的分辨矩阵，再找到属性个数最少的元素，同样如果：IND(P)=IND(A)，且P是独立的，则称P是A的一个约简．处理，直到矩阵中再无包含其它元素所有屙陛的元素为止，此时得到的矩阵记作(S)=(m，)⋯，核是所有约简的子集．1．3基于分辨矩阵的属性约简通过M(S)，可将(3)式简化整理，得到定义7在

8、决策表S=(，cuD)中，U=01，n2，⋯，0m)=／＼，{V口l0∈{lZ，2，⋯，M}为论域，C={。。，0：，⋯，0}为条m，m：≠}．(4)件属性，D={d}为决策属性，cnD=，决策由性质2，可以直接由(．s)实现分辨函数