资源描述：
《基于信息熵的不完备信息系统属性约简算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、http://www.paper.edu.cn基于信息熵的不完备信息系统属性约简算法12付昂，胡军1重庆邮电大学计算机科学与技术学院，重庆（400065）2西安电子科技大学电子工程学院，西安（710071）E-mail：hifuang@yahoo.com.cn，hujun@cqupt.edu.cn摘要：从信息论角度出发引入信息熵的概念，定义了知识的熵，提出了基于信息熵的不完备信息系统知识约简算法，该算法支持多种Rough集关系扩展模型(容差关系、相似关系、限制容差关系等)。通过仿真实验说明了算法的高效性和有效性。关键词：粗糙
2、集，容差关系，不完备信息系统中图分类号：TP181.引言[1]1982年，由波兰数学家Z.Pawlak提出的Rough集理论，由于它能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律，近[2]年来在机器学习、数据挖掘、人工神经网络等多个领域得到了广泛应用,成为当前计算机、人工智能、信息科学等领域的研究热点之一。知识约简是Rough集理论处理信息系统的重要手段，它在保持信息系统分类能力不变的前提下，删除掉系统中冗余信息，为进一步高效的知识获取奠定基础。经典Rough集以完备信息系统为
3、研究对象，然而在现实中，信息的不完备(对象的属性值缺损)现象的广泛存在使等价关系不再成立，从而极大地限制了Rough集向实用化方向发展。研究如何在不改变信息系统的前提下对不完备信息系统直接进行处理，成为基于Rough[3-7]集理论的不完备信息系统知识获取的主要研究方向。已有许多基于代数观的不完备信息[8]系统属性约简算法被提出，黄海基于近似分类质量不发生变化这一约束条件在完备和不完备信息系统中均适用的性质，提出了一种直接处理不完备信息系统的方法，该方法可以适用[9]于各种Rough集扩充模型，并且对完备信息系统和不完备信息
4、系统是统一的。李然等结合粒计算的方法，对不完备信息系统的属性重要度和相对于决策属性的重要度作了定义，在此基础上提出了基于粒计算的启发式知识约简算法，但对于不完备决策表的知识约简算法，并[10]不能直接应用到完备决策表知识约简中。闫德勤提出了不完备信息系统基于概率差别矩[11]阵的不完备信息系统属性约简算法。冯朝一等通过构造不完备信息系统的相关矩阵，把不完备信息系统的最小属性约简问题与最小属性覆盖问题联系起来，给出了基于集合覆盖的不完备信息系统最小属性约简算法。本文结合信息论从反映知识的分类能力的角度给出了知识的熵的度量方法，
5、在此基础上提出了不完备信息系统中基于信息熵的启发式属性约简算法，该算法支持多种关系扩充模型(容差关系、相似关系、限制容差关系)，也可直接应用于完备信息系统。最后通过仿真实验1说明了算法的有效性。2.基本概念定义1一个决策表信息系统S=(U,A,V,f)，U表示对象的非空有限集合，称为论1本课题得到重庆邮电大学自然科学基金（项目编号：A2006-56）的资助。-1-http://www.paper.edu.cn域，A=C∪{d}是属性集合，子集C和{d}分别为条件属性集和决策属性集，V=ΥV，Vaaa∈A表示属性a的值域，f表
6、示U×A→V的一个信息函数，它为每个对象在每个属性上赋予一个信息值，即∀a∈A，x∈U，f(x,a)∈V。若存在一个x∈U，a∈C，f(x,a)未知(记a作:f(x,a)=∗)，则称信息系统S是不完备的，否则称信息系统S是完备的。[5]定义2不完备信息系统S=(U,A,V,f)，A=C∪{d}是属性集合，子集C和{d}分别为条件属性集和决策属性集，U上的容差关系T定义为：∀x,y∈U，(x,y)∈T当且仅当∀a∈A(a(x)=∗∨a(y)=∗∨a(x)=a(y))。[6]定义3不完备信息系统S=(U,A,V,f)，A=C∪{
7、d}是属性集合，子集C和{d}分别为条件属性集和决策属性集，U上的限制容差关系L定义为：∀x,y∈U，(x,y)∈L当且仅当∀a∈A(a(x)=a(y)=∗)∨，(P(x)∩P(y)≠∅∧∀a∈A((a(x)≠∗)∧(a(y)≠∗)→(a(x)=a(y))))其中P(x)={a∈A
8、a(x)≠∗}。[7]定义4不完备信息系统S=(U,A,V,f)，A=C∪{d}是属性集合，子集C和{d}分别为条件属性集和决策属性集，U上的非对称相似关系S定义为：∀x,y∈U，(x,y)∈S当且仅当∀a∈A(a(x)=∗∨a(x)=a(y))
9、。n[8]定义5设集合簇F={X,X,Λ,X}(U=ΥX)是论域U上定义的知识，B是一个属12nii=1性子集，定义B对F的近似分类质量r(F)为：BnrB(F)=∑
10、B−(Xi)
11、/
12、U
13、，i=1其中B(X)为集合X关于属性集合B的下近似。−ii3.不完备信息系统约简以容差关系T为例，对
