kaiyun官方注册
您所在的位置: 首页> 嵌入式技术> 设计应用> 基于系统熵的粗糙集属性约简新方法
基于系统熵的粗糙集属性约简新方法
来源:微型机与应用2011年第9期
李伟涛,刘琼荪
(重庆大学 数学与统计学院,重庆 401331)
摘要:在系统熵的基础上,定义了一种新的属性重要度并提出了一种基于改进系统熵的粗糙集属性约简算法,实验分析表明,该属性重要度为启发式信息进行的属性约简,取得了理想效果。
Abstract:
Key words :

摘 要:系统熵的基础上,定义了一种新的属性重要度并提出了一种基于改进系统熵的粗糙集属性约简算法,实验分析表明,该属性重要度为启发式信息进行的属性约简,取得了理想效果。
关键词:粗糙集;属性约简;系统熵

 粗糙集(Rough Set)理论[1]是一种处理不确定、不完整知识的数学工具,最早是由Pawlak于1982年提出的。现在广泛应用于数据挖掘、智能控制、模式识别等领域[2-3]。属性约简是粗糙集理论中的核心内容之一,有许多学者致力于粗糙集属性约简算法的研究。其中应用较多的是基于差别矩阵及在此基础上的一些改进算法[4],虽然该算法可以得到所有的约简,但是只适合较小的数据集;基于代数观点的相对约简算法不能精确地度量粗糙集中的信息粒度划分;苗夺谦[5]等人提出基于互信息的属性约简算法,是建立在条件属性对决策属性的信息量基础上的。然而以上这些属性约简算法所依据的都是条件属性的分类能力,它们的出发点都是一样的,只是采用的标准有所不同。最近,有些学者提出新的属性约简定义,认为只关心条件属性的分类能力是不够的,决策属性的分类能力也应该充分考虑,即基于系统熵的属性约简定义[6],这种属性约简定义同时考虑到了条件属性和决策属性的分类能力,是一种较周全的属性约简模型。
 本文从系统熵的角度出发,改进了原先的属性重要度定义,给出了新的属性重要性的度量方法,并构造了相应的启发式算法,并通过实例验证了算法的有效性。


 这种新的度量方法同时兼顾了系统熵作为一种同时考虑了条件属性和决策属性的分类能力和数值大小对约简结果的影响,并充分考虑到了在属性子集R中添加属性a∈C-R后系统熵的增量(R自身的熵也被考虑在内)。这种新的属性重要性的定义有如下特点:(1)当系
3 仿真实例和相关比较
 为了验证上述算法的有效性,从UIC数据库中选取了三个具有离散属性的数据库实例进行验证。分别采用文中所提到的两种不同属性重要性定义的约简算法对其进行属性约简。约简结果如表1所示。其中C为该属性集合所包含的条件属性的个数,算法1和算法2分别是以系统熵增益率和本文改进的系统熵增益率为属性重要性度量方法的启发式属性约简算法。从表中可以看到本文所提出的算法在大多数情况下获得的相对约简属性个数较少。


 为了进一步验证文中所改进算法的特点,使用Zoo数据集如表2所示。其中论域U={1,…,101},条件属性C={hair,feathers,eggs,milk,airborne,aquatic,predator,toothed,backbone,breathes,venomous,fins,legs,tail,domestic,catsize},D={type}为决策属性。

 如果按照式(1)所提出的属性重要性来度量各个属性的重要性,经计算得出属性重要性最大的是{milk}。而依据本文所提出的属性重要性得到的结果是{eggs},算法1所得到的属性约简结果是:Ra={feathers,milk,airborne,aquatic,backbone,breathes,fins,legs}。
 依照本文算法2所得到的属性约简结果是:Rb={milk,eggs,aquatic,legs}。这是因为利用式(1)计算属性重要性的时候只考虑了属性本身的值的分布而没有考虑属性的相对信息熵,如果某一属性的相对信息熵较小会导致该属性的属性重要度较大,从而会使所选属性并不是最重要的,或者造成错选。
本文从系统熵的角度出发,定义了一种新的度量属性重要性的方法,构造了相应的启发式算法。相对于原算法,本文算法优势明显,通过实例证明,在大多数情况下本文的算法所得到的属性约简个数较少。
参考文献
[1] PAWLAK Z. Rough sets[J]. Int computer & science,1982;11(5):341-356.
[2] 常犁云,王国胤,吴渝.一种基于Rough Set理论的属性约简及规则提取方法[J].软件学报,1999,10(11):1206-1211.
[3] Hu Xiaohua, CERCONE N. Learning in relational databases a rough set approach[J]. International Journal of Computational Intelligence,1995,11(2):320-340.
[4] RAUSZER S. The discernibility matrices and functions in information systems[M]. Intelligent Decision Support-Handbook of Applications and Advances of the Rough Sets Theory. Dordrecht Kluwer,1992,31-362.
[5] 苗夺谦,胡桂荣.知识约简的一种启发式算法[J].计算机研究与发展,1999,36(6):681-684.
[6] Zhao Jun,Wu Zhongfu,Li Hua. System entropy and its application in feature selection[J]. The Journal of China Universities of Posts and Telecommunications, 2004,11(1):100-105.
[7] 苗夺谦,李道国.粗糙集理论算法与应用[M].北京:清华大学出版社,2008.
[8] 王雄彬,郑雪峰,等,基于系统熵的属性约简的简化差别矩阵方法[J].计算机应用研究,2009,26(7):2461-2464.

此内容为AET网站原创,未经授权禁止转载。
Baidu
map