基于信息熵和变精度粗糙集的规则不确定性度量
摘要
粗糙集理论于1982年由波兰学者Zdzislaw Pawlak首次提出,作为一种新型的处理含有噪音的知识、不精确的知识的重要理论方法,受到了广泛关注。至今,粗糙集理论已经在机器学习,模式识别,决策分析,数据库知识发现,专家系统等众多领域得到成功的应用。
粗糙集理论是以不可分辨关系这一概念为基础的。不可分辨关系将论域U划分成一个个等价类的集合。通过上、下近似集合(等价类的集合),对某一给定概念进行近似表示。上、下近似集合之差为边界区域。等价类内的不可分辨关系和边界区域的存在,使得利用粗糙集算法处理数据存在不确定性。利用粗糙集算法处理数据的不确定性越大,越难得到确定的规则集合,引起规则的不确定性越大。因此,需要一种不确定性度量来表示规则的不确定性。
Duntch I.等人针对依赖度γ的某些局限,提出用衡量粒度大小的一种度量——信息熵来度量规则的不确定性。陈湘晖等人在此基础上借鉴变精度粗糙集思想,提出两种基于信息熵和变精度粗糙集的不确定性度量,使得导出的规则具有鲁棒性。本文对陈湘晖等人提出的基于信息熵的规则不确定性度量进行改进,形成一种新的规则不确定性度量,并将这种不确定性度量应用在变精度粗糙集属性约简、导出规则的启发式算法中。而后通过实验说明应用了新的不确定性度量的算法在相似精度下可以得到更小的约简属性集和更少的规则。
Rough set theory, firstly introduced by Zdzislaw Pawlak in 1982.is a new mathematical method to deal with vagueness, uncertainty knowledge and noise data. This approach has been used successfully in many fields, such as Machine Learning.Pattern Recognition. Knowledge Discovery, Expert Systems, Knowledge Acquisition, and Decision Support Systems.
Rough set theory is based on indiscernibility relation imposed on the universe. This equivalence relation partitions all objects into a finite set of equivalence classes.Any subset of the universe can be approximately described by upper approximation and lower approximation which are sets of equivalence classes.The indiscernibility relation and boundary region (the difference from upper and lower approximation) generate the uncertainty when databases are dealt with by rough set algorithm.With the increase of this uncertainty, the number of deterministic rules will decrease, meanwhile, uncertainty of decision rules will increase.So it is significant to measure the uncertainty of rules.
Duntsch.I gave three models for predicting the decision attribute.and defined different entropies-the measure of granular to describe uncertainty of decision rules.Xiang-Hui Chen proposed two entropies based on variable precision rough set theory. The two entropies make decision rules more robust.In this paper a new uncertainty measure of rules based on entropy and variable precision rough set is proposed to improve above-mentioned uncertainty measures, and applied to heuristic algorithms of attribute reduction.Comparing with one of Chen's entropies, the experiment results on CLEVE database show that the algorithm using the new uncertainty measure gets smaller attribute reduction and less decision rules with similar accuracy.
粗糙集理论是以不可分辨关系这一概念为基础的。不可分辨关系将论域U划分成一个个等价类的集合。通过上、下近似集合(等价类的集合),对某一给定概念进行近似表示。上、下近似集合之差为边界区域。等价类内的不可分辨关系和边界区域的存在,使得利用粗糙集算法处理数据存在不确定性。利用粗糙集算法处理数据的不确定性越大,越难得到确定的规则集合,引起规则的不确定性越大。因此,需要一种不确定性度量来表示规则的不确定性。
Duntch I.等人针对依赖度γ的某些局限,提出用衡量粒度大小的一种度量——信息熵来度量规则的不确定性。陈湘晖等人在此基础上借鉴变精度粗糙集思想,提出两种基于信息熵和变精度粗糙集的不确定性度量,使得导出的规则具有鲁棒性。本文对陈湘晖等人提出的基于信息熵的规则不确定性度量进行改进,形成一种新的规则不确定性度量,并将这种不确定性度量应用在变精度粗糙集属性约简、导出规则的启发式算法中。而后通过实验说明应用了新的不确定性度量的算法在相似精度下可以得到更小的约简属性集和更少的规则。
Rough set theory, firstly introduced by Zdzislaw Pawlak in 1982.is a new mathematical method to deal with vagueness, uncertainty knowledge and noise data. This approach has been used successfully in many fields, such as Machine Learning.Pattern Recognition. Knowledge Discovery, Expert Systems, Knowledge Acquisition, and Decision Support Systems.
Rough set theory is based on indiscernibility relation imposed on the universe. This equivalence relation partitions all objects into a finite set of equivalence classes.Any subset of the universe can be approximately described by upper approximation and lower approximation which are sets of equivalence classes.The indiscernibility relation and boundary region (the difference from upper and lower approximation) generate the uncertainty when databases are dealt with by rough set algorithm.With the increase of this uncertainty, the number of deterministic rules will decrease, meanwhile, uncertainty of decision rules will increase.So it is significant to measure the uncertainty of rules.
Duntsch.I gave three models for predicting the decision attribute.and defined different entropies-the measure of granular to describe uncertainty of decision rules.Xiang-Hui Chen proposed two entropies based on variable precision rough set theory. The two entropies make decision rules more robust.In this paper a new uncertainty measure of rules based on entropy and variable precision rough set is proposed to improve above-mentioned uncertainty measures, and applied to heuristic algorithms of attribute reduction.Comparing with one of Chen's entropies, the experiment results on CLEVE database show that the algorithm using the new uncertainty measure gets smaller attribute reduction and less decision rules with similar accuracy.
引文
[1]Zdzislaw Pawlak. Rough sets.International Journal of Computer and Information Sciences,1982. 11(5):341-356.
[2]S.K.M.Wong, W. Ziarko and R. Li Ye. Comparison of rough-set and statistical methods in inductive learning.International Journal of Man-Machine Studies.1986,25(1):53-72.
[3]Zdzislaw Pawlak. Rough set theoretical aspects of reasoning about data. Dordrecht. Boston,London: KluwerAca-demicPublishers,1991.9-51.
[4]Wojciech Ziarko. Variable precision rough set model.Journal of Computer and System Sciences,1993. 46(1):39-59.
[5]Zdzislaw Pawlak and Slowiriski R.Rough set approach to multi-attribute decision analysis.European Journal of Operational Research,1994,72:443-459.
[6]A.An,N.Shan, C.Chan,N.Cercone and W. Ziarko. Discovering Rules for Water Demand Prediction: An Enhanced Rough-Set Approach.Engineering Applications of Artificial Intelligence,1996,9(6): 645-653.
[7]Ivo Duntsch and Gunther Gediga. The rough set engine GROBIAN.Proceedings 15th IMACS World Congress,Wissenschaft und Tech& Berlin,1997,4:613-618.
[8]Beaubouef T and Arora G.Information-theoretic measures of uncertainty for rough sets and rough relational databases. Information Sciences,1998,109(1-4):185-195.
[9]Ivo Duntsch and Gunther Gediga. Uncertainty measures of rough set prediction. Artificial Intelligence, 1998,106:109-137.
[10]苗夺谦，胡桂容．知识约简的一种启发式算法．计算机研究与发展，1999，36(6)：681-684．
[11]蒋运承．Rough集和Rough关系数据库中熵的研究．广西：广西师范大学数学与计算机科学学院，2000．
[12]叶东毅，黄翠徽．赵斌．粗糙集中属性约简的一个贪心算法．系统工程与电子技术，2000．22(9)：63-65．
[13]陈湘晖．朱善君．占吟东．基于熵和变精度粗糙集的规则不确定性量度．清华大学学报(自然科学版)，2001．41(3)：110-113．
[14]张文修．吴伟志．梁吉业．粗糙集理论与方法．北京：科学出版社，2001．
[15]刘清Rough集及Rough推理．北京：科学出版社．2001．
[16]王国胤．于洪．杨大春．基于条件信息熵的决策表约简．计算机学报．2002年7月．25(7)：759-766．
[17]Zdzislaw Pawlak. Rough Sets and Intelligent Data Analysis. Information Sciences.2002 147(1-4): 1-12.
[18]姚明臣．孟凡超．属性约简的一种贪心算法．佳术斯大学学报(自然科学版)．2003年9月．21(3)： 307-311.
[19]李仁璞,王正欧.规则不确定性的几种度量及其相互关系.系统工程理论与实践,2004,24(1)：83-87.
[20]张雪峰.粗糙集数据分析系统应用平台的研究与程序开发.沈阳：东北大学信息科学与工程学院,2004.
[21]张海军,左洪福,梁剑.基于信息熵属性约简的航空发动机送修等级决策.系统工程,2005,23(7)：105-108.
[22]刘勇,丁香乾.一种新的粗集粗糙性度量方法.计算机应用,2005.25(12)：297-298.
[23]殷允强,黄晓昆,张振良.基于粗糙集的互信息求取属性约简的决策算法.云南民族大学学报(自然科学版),2006年6月,15(1)：15-17.
[24]王向阳,蔡念.杨杰,刘小军.基于近似精度和条件信息熵的粗糙集不确定性度量方法.上海交通大学学报.2006年7月，40(7)：1131-1134.
[25]何亚群,胡寿松.朱江.粗糙集中不确定性测量的修正粗糙熵方法.海军工程大学学报.2006年8月,18(4)：26-29.
[26]蔡娜,张雪峰.变精度粗糙集的约简及其参数β范围的确定.石油化工高等学校学报.2006年9月,19(3)：92-96.
[27]张雪峰,张庆灵.粗糙集数据分析系统MATLAB仿真工具箱设计.2007，28(1)：40-43.
[28]Zdzislaw Pawlak and Andrzej Skowron. Rudiments of rough sets. Information Science.2007,177(1): 3-27.
[29]颜艳,杨慧中.一种基于互信息的粗糙集知识约简算法.清华大学学报(自然科学版).2007年4月,47(S2)：1903-1906.
[30]刘立军,胡文彬,梅红岩.基于变精度粗糙集模型的Matlab实现.计算机工程与应用，2007,43(8)：110-111+114.
[31]孙士保.变精度粗糙集模型及其应用研究.四川：西南交通大学智能控制开发中心,2007年11月.
[32]蔡娜,张雪峰.王宇彤.变精度粗糙集属性约简的算法.系统工程与电子技术,2007年12月.29(12)：2064-2067.
[33]孟慧丽.粗糙集的不确定度量理论及启发式属性约简算法研究.河南：河南师范大学计算机与信息技术学院,2008年4月.
[2]S.K.M.Wong, W. Ziarko and R. Li Ye. Comparison of rough-set and statistical methods in inductive learning.International Journal of Man-Machine Studies.1986,25(1):53-72.
[3]Zdzislaw Pawlak. Rough set theoretical aspects of reasoning about data. Dordrecht. Boston,London: KluwerAca-demicPublishers,1991.9-51.
[4]Wojciech Ziarko. Variable precision rough set model.Journal of Computer and System Sciences,1993. 46(1):39-59.
[5]Zdzislaw Pawlak and Slowiriski R.Rough set approach to multi-attribute decision analysis.European Journal of Operational Research,1994,72:443-459.
[6]A.An,N.Shan, C.Chan,N.Cercone and W. Ziarko. Discovering Rules for Water Demand Prediction: An Enhanced Rough-Set Approach.Engineering Applications of Artificial Intelligence,1996,9(6): 645-653.
[7]Ivo Duntsch and Gunther Gediga. The rough set engine GROBIAN.Proceedings 15th IMACS World Congress,Wissenschaft und Tech& Berlin,1997,4:613-618.
[8]Beaubouef T and Arora G.Information-theoretic measures of uncertainty for rough sets and rough relational databases. Information Sciences,1998,109(1-4):185-195.
[9]Ivo Duntsch and Gunther Gediga. Uncertainty measures of rough set prediction. Artificial Intelligence, 1998,106:109-137.
[10]苗夺谦，胡桂容．知识约简的一种启发式算法．计算机研究与发展，1999，36(6)：681-684．
[11]蒋运承．Rough集和Rough关系数据库中熵的研究．广西：广西师范大学数学与计算机科学学院，2000．
[12]叶东毅，黄翠徽．赵斌．粗糙集中属性约简的一个贪心算法．系统工程与电子技术，2000．22(9)：63-65．
[13]陈湘晖．朱善君．占吟东．基于熵和变精度粗糙集的规则不确定性量度．清华大学学报(自然科学版)，2001．41(3)：110-113．
[14]张文修．吴伟志．梁吉业．粗糙集理论与方法．北京：科学出版社，2001．
[15]刘清Rough集及Rough推理．北京：科学出版社．2001．
[16]王国胤．于洪．杨大春．基于条件信息熵的决策表约简．计算机学报．2002年7月．25(7)：759-766．
[17]Zdzislaw Pawlak. Rough Sets and Intelligent Data Analysis. Information Sciences.2002 147(1-4): 1-12.
[18]姚明臣．孟凡超．属性约简的一种贪心算法．佳术斯大学学报(自然科学版)．2003年9月．21(3)： 307-311.
[19]李仁璞,王正欧.规则不确定性的几种度量及其相互关系.系统工程理论与实践,2004,24(1)：83-87.
[20]张雪峰.粗糙集数据分析系统应用平台的研究与程序开发.沈阳：东北大学信息科学与工程学院,2004.
[21]张海军,左洪福,梁剑.基于信息熵属性约简的航空发动机送修等级决策.系统工程,2005,23(7)：105-108.
[22]刘勇,丁香乾.一种新的粗集粗糙性度量方法.计算机应用,2005.25(12)：297-298.
[23]殷允强,黄晓昆,张振良.基于粗糙集的互信息求取属性约简的决策算法.云南民族大学学报(自然科学版),2006年6月,15(1)：15-17.
[24]王向阳,蔡念.杨杰,刘小军.基于近似精度和条件信息熵的粗糙集不确定性度量方法.上海交通大学学报.2006年7月，40(7)：1131-1134.
[25]何亚群,胡寿松.朱江.粗糙集中不确定性测量的修正粗糙熵方法.海军工程大学学报.2006年8月,18(4)：26-29.
[26]蔡娜,张雪峰.变精度粗糙集的约简及其参数β范围的确定.石油化工高等学校学报.2006年9月,19(3)：92-96.
[27]张雪峰,张庆灵.粗糙集数据分析系统MATLAB仿真工具箱设计.2007，28(1)：40-43.
[28]Zdzislaw Pawlak and Andrzej Skowron. Rudiments of rough sets. Information Science.2007,177(1): 3-27.
[29]颜艳,杨慧中.一种基于互信息的粗糙集知识约简算法.清华大学学报(自然科学版).2007年4月,47(S2)：1903-1906.
[30]刘立军,胡文彬,梅红岩.基于变精度粗糙集模型的Matlab实现.计算机工程与应用，2007,43(8)：110-111+114.
[31]孙士保.变精度粗糙集模型及其应用研究.四川：西南交通大学智能控制开发中心,2007年11月.
[32]蔡娜,张雪峰.王宇彤.变精度粗糙集属性约简的算法.系统工程与电子技术,2007年12月.29(12)：2064-2067.
[33]孟慧丽.粗糙集的不确定度量理论及启发式属性约简算法研究.河南：河南师范大学计算机与信息技术学院,2008年4月.