下载文档原格式
龙源期刊网 一种基于粗糙熵的信息系统属性约简算法作者：史进玲来源：《电脑知识与技术》2012年第24期摘要：在信息系统中，研究了知识的粗糙性，定义了一种粗糙熵度量方法，并证明了知识的粗糙熵随着划分的增大而单调增加的结论，给出了属性的重要性度量方法，在此基础上提出了一种基于粗糙熵的启发式属性约简算法。
实例验证表明，该算法能有效地从信息系统中获取最优属性约简。
关键词：信息系统；粗糙熵；属性重要度；属性约简中图分类号：TP312文献标识码：A文章编号：1009-3044(2012)24-5872-03An Attribute Reduction Algorithm Based on Rough Entropy in Information SystemSHI Jin-ling(International School of Education, Xuchang University, Xuchang 461000, China)Abstract：In information system, a rough entropy is defined by studying roughness of knowledge, then knowledge rough entropy’s mo? notonous increasing property with the increase of partition is proved. On this basis, attribute significance measure method is given and a heuristic reduction algorithm based on rough entropy is proposed. A detailed example is shown that the algorithm can effectively extract op? timal reduction.Key words: information system; rough entropy; attribute significance; attribute reduction粗糙集理论(Rough Set )是一种有效的从不精确、不完备与不一致数据的知识库中获取知识的数学理论[1-2]。
广义信息系统的属性约简
巩增泰;郭永平;史战红
【期刊名称】《计算机工程与应用》
【年(卷),期】2010(046)023
【摘要】把完备信息系统、不完备信息系统、序信息系统、覆盖信息系统等常见信息系统统称为广义信息系统,采用新的知识表达形式将其知识结构进行统一表示,特别是将覆盖信息系统纳入了广义信息系统的框架之中.在广义信息系统中引入粒度熵的概念,对属性的重要性给出度量;在此基础上,提出一种广义信息系统属性约简的启发式算法,进而得到广义信息系统的知识约简,并给出了若干算例.
【总页数】5页(P34-37,58)
【作者】巩增泰;郭永平;史战红
【作者单位】西北师范大学,数学与信息科学学院,兰州,730070;西北师范大学,数学与信息科学学院,兰州,730070;甘肃农业大学,理学院,兰州,730070
【正文语种】中文
【中图分类】O159
【相关文献】
1.广义多粒度粗糙集属性约简和matlab计算 [J], 张先韬
2.广义分布保持属性约简研究 [J], 高学义;张楠;童向荣;姜丽丽
3.广义不完备直觉模糊信息系统的属性约简 [J], 杨柳娇;舒畅;莫智文
4.广义优势多粒度直觉模糊粗糙集的属性约简 [J], 梁美社;米据生;冯涛
5.基于三支决策的广义代价敏感近似属性约简 [J], 方宇;高磊;刘忠慧;杨新
因版权原因，仅展示原文概要，查看原文内容请购买。
集值信息系统的属性约简马建敏;朱朝晖【摘要】属性约简是粗糙集理论研究中的重要内容之一.本文主要研究集值信息系统的属性约简问题.在集值信息系统中基于拟序关系引入了信息量的概念,给出了属性特征的判定方法,以及信息量与属性约简之间的关系.根据信息量定义了属性重要性,研究了属性重要性与属性约简之间的关系.进而得到了基于信息量和属性重要性的属性约简算法,给出了该算法的时间复杂度.通过实例说明,该算法是有效的.【期刊名称】《工程数学学报》【年(卷),期】2010(027)005【总页数】6页(P883-888)【关键词】集值信息系统;拟序关系;信息量;属性重要性;属性约简【作者】马建敏;朱朝晖【作者单位】长安大学理学院数学与信息科学系,西安,710064;深圳卓成混凝土模块研究所,深圳,518000【正文语种】中文【中图分类】TPL81 引言粗糙集理论是由波兰数学家Pawlak于1982提出的一种数据分析理论[1]。
该理论由于能分析处理不精确、不协调和不完备等信息引起人工智能工作者的广泛关注，并被成功应用在机器学习与知识发现、数据挖掘、决策支持与分析、过程控制、模式识别等领域[2]。
属性约简作为粗糙集理论的重要研究内容之一[1,3]，是在保持分类能力不变的前提下删除其中的冗余属性。
由于属性约简并不唯一，人们希望找出所有约简或最小约简。
但寻找最小约简是NP-hard问题[4]。
解决这类问题的一般方法是采用启发式搜索方法求出最优或次优约简[5]。
苗夺谦等人[6]提出了基于互信息的知识相对约简的启发式算法。
王国胤等人提出了基于条件信息熵的决策表约简算法[7]。
梁吉业等人[8]提出了基于信息量的属性约简算法。
黄兵等人[9]给出了不完备信息系统的属性约简算法。
而对不确定或缺省信息，则需研究不完备信息系统或集值信息系统。
本文在集值信息系统中建立了拟序关系，由此引入了信息量的概念，通过信息量研究了属性特征，以及信息量与约简之间的关系。
粗糙集的研究对象是一个数据集，数据集一般被保存为数据表格形式，即数据库或信息系统。
信息系统的形式是由研究对象和属性值关系构成的二维数据表，类似于基础数学中的关系数据库。
信息系统实现了粗糙集模型的知识表示。
定义 2.1.1[46] 设(,,,)S U A V f =为一个数据库，即信息系统，也称为知识表示系统。
其中12{,}U U x x x = 为一个非空的有限对象集，12{,,}A A a a a = 是属性的有限非空集合，a V V =⋃，a A ∈，a V 为属性a 的值域；定义信息函数:U V c a f A ⨯→ .例如表2.1.1是一个信息系统，其中12345{,,,,}U x x x x x =，1234{,,,}A a a a a =，123a a a V V V ==={0,1}，4a V ={0,1,2}.表2.1.1 信息系统定义2.1.2[46] 对于a A ∀∈，x U ∀∈，(,)a f x a V ∈，对于P A ∀∅≠⊆，定义：{(,):(,)(,),}I x y U U f x q f y q q P =∈⨯=∀∈，I U 称为上的不可分辨关系。
(1)若(,)x y I ∈，则称：x y 和是不可分辨的。
(2)不可分辨关系是等价关系，具有：自反性：xIx ； 对称性：xIy yIx ⇒；传递性：,xIy yIz xIz ⇒ ．(3) I 是U 上的一个等价关系，[]{,}I x y y U xIy =∈，12{[]}{,}I k U I x x U X X X =∈= ，12,k X X X 称为U 关于I 的一个划分。
(4)P I ∅≠⊆,1,2I I I ∈, 112{,}k U I X X X = ,212{,}l U I Y Y Y = ,12{,1,2,1,2}i j U I I X Y i k j l ⋂=⋂== ,()I Pind P I P ∈== ，则称：()ind P U 是上的一个等价关系，称为P 上的不可区分关系。
2001年12月系统工程理论与实践第12期 文章编号:100026788(2001)1220076205信息系统的属性约简梁吉业1,2,曲开社2,徐宗本1(1.西安交通大学理学院信息与系统科学研究所,陕西西安710049;2.山西大学计算机科学系,山西太原030006)摘要: 粗糙集理论是一种新的处理模糊和不确定知识的数学工具.属性约简是粗糙集理论研究中的重要内容之一,现已证明寻找信息系统的最小约简是N P2hard问题.本文提出一个基于信息量的属性约简的启发式算法,该算法的时间复杂性为O( A 3 U 2).通过例子分析,表明该算法是有效的.关键词: 粗糙集理论;信息系统;属性约简;算法复杂性中图分类号: T P18 文献标识码: A αR educti on of A ttribu te in Info rm ati on System sL I AN G J i2ye1,2,QU Kai2she2,XU Zong2ben1(1.In stitu te fo r Info rm ati on and System Science,Facu lty of Science,X i’an J iao tong U n iversity,X i’an 710049,Ch ina;2.D epartm en t of Compu ter Science,Shanx i U n iversity,T aiyuan030006,Ch ina)Abstract: Rough set theo ry is a new m athem atical too l to deal w ith vagueness anduncertain ty.R educti on of attribu te is one of the i m po rtan t top ics in the research onrough set theo ry.It has been p roved that finding the m in i m al reducti on of aninfo rm ati on system is a N P2hard p rob lem.In th is paper,an info rm ati on quan tity2basedheu ristic algo rithm fo r reducti on of attribu te is p ropo sed,the ti m e comp lex ity of th isalgo rithm is O( A 3 U 2).T hough runn ing an examp le,w e show that th is algo rithmis effective.Keywords: rough set theo ry;info rm ati on system s;reducti on of attribu te;comp lex ityof algo rithm1 引言粗糙集理论[1,2]是一种新的处理模糊和不确定知识的数学工具.其主要思想是,在保持信息系统的分类能力不变的前提下,通过知识约简,导出问题的决策或分类规则.经过十几年的研究与发展,粗糙集理论已经在理论和实际应用上取得了长足的发展,特别是由于九十年代在知识发现等领域得到了成功的应用而受到国际学术界广泛关注.目前,它正在被广泛应用于机器学习、决策分析、过程控制、模式识别和数据挖掘等领域[3,4].属性约简是粗糙集理论中的重要内容之一[1]。
