非完备信息系统基于信息熵的约简
|
摘要
在信息时代,存在着大量的信息集合,人们可以从这些信息中挖掘有用的信息,但是实际中大多数这样的信息系统的数据具有不确定性。随着在实际问题中处理不确定性集合方法的不断发展,粒计算理论成为世界范围内一种常用的研究方法和应用广泛的处理不确定性的方法。粒计算现已成为人工智能领域研究的热点之一。
本文是基于粒计算理论的信息熵等相关知识对非完备决策表进行约简的研究,并对比分析了该非完备决策表信息更新前后信息熵及约简的情况。本文主要工作如下:
(1)概述了粒计算基本理论、研究趋势和发展现状;
(2)介绍了非完备决策表、粒计算理论中的信息熵、信息粒度等定义;
(3)在完备信息系统基于信息熵的约简算法基础上,给出了非完备决策表基于信息熵的约简算法;
(4)对比分析了非完备决策表数据更新前后信息熵、约简过程和约简结果的变化。得出信息熵值会发生变化,信息熵值的降序排列也会发生变化,并且对于非海量信息的信息系统动态数据更新是必要的。
In the information age, there are a lot of assemble of information in the world. People can dig out a lot of useful information from these assembles, but in the real some data from information systems is uncertainty. Develping of the methodologies for dealing with uncertainty in real-world problems, granular computing is becoming a widespread and useful method in the worldwide research community and exhibiting a broad range of applications. Granular computing now has become one of hot spots in artificial intelligence.
In this article, the research of reduction in the incomplete decision table base on the granular computing theory. It also analyse the data of information entropy and the result of the reduction. The main works are as follows.
(1) The article gives a brief introduction about granular computing and its development, current research;
(2) It introduces the definition about the incomplete decision table and information entropy, information granularity in granular computing theory and so on;
(3) Basing on the reduction algorithm using information entropy theory in the complete information systems, the article gives the other reduction algorithm in the incomplete decision table;
(4) Contrast the date of information entropy, the procedure for reduction and the result of reduction after data update. We can know that the information entropy and the sequence of the decreasing order about the data of information entropy would change. We also can know that when the data set of the information systems is not very big, it is necessary to update the information in time.
本文是基于粒计算理论的信息熵等相关知识对非完备决策表进行约简的研究,并对比分析了该非完备决策表信息更新前后信息熵及约简的情况。本文主要工作如下:
(1)概述了粒计算基本理论、研究趋势和发展现状;
(2)介绍了非完备决策表、粒计算理论中的信息熵、信息粒度等定义;
(3)在完备信息系统基于信息熵的约简算法基础上,给出了非完备决策表基于信息熵的约简算法;
(4)对比分析了非完备决策表数据更新前后信息熵、约简过程和约简结果的变化。得出信息熵值会发生变化,信息熵值的降序排列也会发生变化,并且对于非海量信息的信息系统动态数据更新是必要的。
In the information age, there are a lot of assemble of information in the world. People can dig out a lot of useful information from these assembles, but in the real some data from information systems is uncertainty. Develping of the methodologies for dealing with uncertainty in real-world problems, granular computing is becoming a widespread and useful method in the worldwide research community and exhibiting a broad range of applications. Granular computing now has become one of hot spots in artificial intelligence.
In this article, the research of reduction in the incomplete decision table base on the granular computing theory. It also analyse the data of information entropy and the result of the reduction. The main works are as follows.
(1) The article gives a brief introduction about granular computing and its development, current research;
(2) It introduces the definition about the incomplete decision table and information entropy, information granularity in granular computing theory and so on;
(3) Basing on the reduction algorithm using information entropy theory in the complete information systems, the article gives the other reduction algorithm in the incomplete decision table;
(4) Contrast the date of information entropy, the procedure for reduction and the result of reduction after data update. We can know that the information entropy and the sequence of the decreasing order about the data of information entropy would change. We also can know that when the data set of the information systems is not very big, it is necessary to update the information in time.
引文
[1]Kryszkiewicz M.Rough set approach to incomplete information systems.Information Sciences,1998,112:39-49.
[2]Kryszkiewicz M.Rules in incomplete information systems.Information Sciences.1999,113:271-292.
[3]苗夺谦,王国胤,刘清,林早阳,姚一豫等.粒计算:过去、现在与发展.北京:科学出版社,2007.
[4]Liang J Y,Shi Z Z,Li D Y,et al.The information entropy,rough entropy and knowledge granulation in incomplete information systems.Intenational Journal of General Systems,2006,35(6):641-654.
[5]Qian Y H,Liang J Y.Combination entropy and combination granulation in incomplete systems//Lecture Notes in Artificial Intelligence 4062.Berlin:Springer,2006:184-190.
[6]张文修,吴伟志,梁吉业,李德玉.粗糙集理论与方法.北京:科学出版社,2006
[7]Pawlak Z.Rough Sets:Theoretical Aspects of Reasoning about Data.Dordrecht:Kluwer Academic Publishers,1991.
[8]苗夺谦,范世栋.知识的粒度计算及其应用.系统工程理论与实践,2002,22(1):48-56.
[9]Zadeh L A.The key roles of information granulation and fuzzy logic in human reasoning[A].In:Hyatt R,ed.Proceedings of the Fifth IEEI International Conference on Fuzzy System,FUZZ -IEEI'96[C].Germany:Physica- Verlag GmbH Heidelberg,1996.100-106
[10]Zadeh L A.Some reflections on information granulation and its centrality in granular computing,computing with words,the computational theory of perceptions and precisiated natural language[A].In:Lin T Y,ed.Data Mining,Rough Sets and Granular Computing[M].Physica- Verlag GmbH Heidelberg,2002.110-153
[11]张铃,张钹.问题求解理论及应用[M].北京:清华大学出版社,1990.
[12]张铃,张钹.模糊商空间理论(模糊粒度计算方法)[J].软件学报,2003,14(4):770-776.
[13]侯利娟,王国胤,聂能,等.粗糙集理论中的离散化问题[J].计算机科学,2000,27(12):89-94.
[14]Yao Y Y.Granular computing:basic issues and possible solutions.In:Proc.Of the 5~(th) Joint Conf.on Information Sciences,Volume Ⅰ,Atlantic City,New Jersey,USA,February 27-March 3,2000,P.P.Wang Ed.,Association for Intelligent Machinery,2000.186-189.
[15]Pedrycz W.Granular Computing,An Emerging Paradigm.IEEE Trans.On Systems Man and Cybernetics,32(2):212-224.
[16]Lin T Y.Granular computing Ⅱ:Infrastructures for AI-engineering//The 2006 IEEE International Conference on Granular Computing,Atlanta,USA,2006:2-7.
[17]Sierpinski W,Krieger C.General Topology.Toronto:university of Toronto Press,1952.
[18]Zadeh L A.Fuzzy logic=Computing with words[J].I EEE Transactions on Fuzzy Systems,1996,2:103-111.
[19]李道国,苗夺谦,张红云.粒度计算的理论、模型与方法[J].复旦学报,2004,23(5):837-841.
[20]Yao Y Y.Granular computing using neighborhood systems[A].In:Roy R,ed.Advances in soft computing:Engineering design and manufacturing[M].London:Springer Verlag company,1999.539-553.
[21]罗敏.粒计算及其研究现状[J].计算机与现代化[J],2007,1:1-5.
[22]Pawlak Z,Grzymala B J,Slowinski R,et al.Rough set[J].Communication of the ACM,1995,38(11):89- 95.
[23]Zhang Wen-xiu,Wu Wei-zhi,Lang Ji-ye.Rough set theory and method[M].Beijing:Science Publishing Company,2001.
[24]曾正良,罗可,王莹.基于粒子群的不完备决策表属性约简PSO IDTAR法[J].计算机工程与应用,2008,44(14):149-151.
[25]王国胤.Rough集理论在不完备信息系统中的扩充.计算机研究与发展.2002,39(10):1238-1243.
[26]Skowron A.The Discernibility Matrix and Function in Information System.In:R.Slosinski(ED):Intelligent Decision Support:Handbook of Application and Advances of the rough sets Theory(M).Dordrecht Kluwer Academic Publishers,1992,331-362.
[27]Leung Y,Li D Y.Maximal consistent block technique for rule acquisition in incomplete information systems.Information Sciences,2003,153:85-106.
[28]Yao Y Y.Relational interpretations of neighborhood operators and rough set approximation.Information Sciences.1998,111:239-259.
[29]何先刚,黄兵,温平川.不完备信息系统中知识约简的一种启发式算法[J].压电与声光,2004,26(2):158-160.
[30]杨成福,舒兰.基于容差关系的不完备决策系统属性约简算法[J].计算机技术与发展,2006,16(9):68-71.
[31]孙晶晶,刘镔,刘粉林.基于遗传算法的不完备信息表约简方法[J].计算机工程与应用,2005,41(22):174-176.
[32]宫俊,唐加福.基于不完备信息系统的分配约简的启发式算法[J].东北大学学报,2007,28(1):19-22.
[33]Zadeh L A.Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic.Fuzzy Sets and Systems,1997,19(1):111-127.
[34]Pawlak Z.Rough sets.International Journal of Information and Computer Scienxes,1982,11:341-356.
[35]李道国,苗夺谦,张东星,张红云.粒度计算研究综述[J].计算机科学,2005,32(9):1-12.
[36]Shannon C E.A mathematical theory of communication.The Bell System Technical Journal,1948,27(3-4):373-423.
[37]Duntsch I,Gediga G.Uncertainty measures of rough set prediction.Artificial Intelligence,1998,106:109-137.
[38]Liang J Y,Xu Z B.The algorithm on knowledge reduction in incomplete information systems.International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(1):95-103.
[39]Jerzy W.Grzymala-Busse.Rough Set Strategies to Data with Missing Attribute Values[A].Proceedings of the Workshop on Foundations and New Directions in Data Mining,associated with the third IEEE International Conference on Data Mining,2003,Melboume,FL,USA,pp:56-63.
[40]刘清,孙辉,王洪发.粒计算研究现状及基因Rough逻辑语义的粒计算研究[J].计算机学报,2008,31(4):543-5.
[41]Zhang B,Chen W L.Theory and Applications of Problem Solving.Amsterdam:North-Holland,1992.
[42]Yang L,Chen W L,Zhang L.A paradigm of granular computing based on quotient closure space//Proceedings of the 6~(th) World Congress on Intelligent Control and Automation,Dalian,China,2006:1430-1433.
[43]Zhang L,Zhang B.The quotient space theory of problem solving.Fundamenta Informaticae,2004,59(2-3):287-298.
[44]Ma J M,Zhang W X,Li T.A covering model of granular computing//The 2005 International Conference onf Machine Learning and Cybernetics,Guangzhou,China,2005:1625-1630.
[45]Wang J,Zhao M,Zhao K,et al.Multilevel data summarization from information system:A "rule+exception" approach.AI Communications,2003,16(1):17-39.
[46]王钰,姚一豫,王飞跃.基于Reduct的“规则+例外”学习.计算机学报,2005,28(11):1778-1789.
[47]李道国,苗夺谦,张红云.粒度计算的基本问题和可能解决的方案设计.计算机科学,2004,31(2):195-198.
[48]梁吉业,李德玉.信息系统中的不确定性与知识获取.北京:科学出版社,2005.
[49]刘莹.基于泛系的粒度计算及相关模型研究[硕士学位论文].兰州:兰州大学,2006.
[50]邓蔚,王国胤,吴渝.粒计算对进化计算的一个改进.计算机科学,2004,31(10.A):209-211,214.
[51]Wang G Y,Hu F,Huang H,et al.A granular computing model based on tolerance relation.The Journal of China Universities of Posts and Telecommunications,2005,12(3):86-90.
[52]Mi J S,Wu W Z,Zhang W X.Approaches to knowledge reduction based on variable precision rough set model.Information Sciences,2004,159(2):255-272.
[53]Wu W Z,Leung Y,Zhang W X.On generalized rough fuzzy approximation operators.Transactions on Rough Sets,2006,5:263-284.
[54]Zhu W,Wang F Y.Relationshiops among three types of covering rough sets//The 2006 IEEE International Conference on Granular Computing,Atlanta,USA,2006:43-48.
[55]Zhu W.Topological approaches to covering rough sets.Information Sciences,2007,177(6):1499-1508.
[56]刘清,刘群.粒及粒计算在逻辑推理中的应用.计算机研究与发展,2004,41(4):546-551.
[57]刘清,黄兆华.G-逻辑及其归结推理.计算机学报,2004,27(7):865-873.
[58]刘清,孙辉.从Rough集的发展前景看粒计算的研究趋势.南昌工程学院学报,2006,25(5): 1-10.
[59] Zheng Z, Hu H, Shi Z Z. Tolerance relation based granular space//Lecture Notes in Artificial Intelligence 3642. Berlin:Springer, 2005:682-691.
[2]Kryszkiewicz M.Rules in incomplete information systems.Information Sciences.1999,113:271-292.
[3]苗夺谦,王国胤,刘清,林早阳,姚一豫等.粒计算:过去、现在与发展.北京:科学出版社,2007.
[4]Liang J Y,Shi Z Z,Li D Y,et al.The information entropy,rough entropy and knowledge granulation in incomplete information systems.Intenational Journal of General Systems,2006,35(6):641-654.
[5]Qian Y H,Liang J Y.Combination entropy and combination granulation in incomplete systems//Lecture Notes in Artificial Intelligence 4062.Berlin:Springer,2006:184-190.
[6]张文修,吴伟志,梁吉业,李德玉.粗糙集理论与方法.北京:科学出版社,2006
[7]Pawlak Z.Rough Sets:Theoretical Aspects of Reasoning about Data.Dordrecht:Kluwer Academic Publishers,1991.
[8]苗夺谦,范世栋.知识的粒度计算及其应用.系统工程理论与实践,2002,22(1):48-56.
[9]Zadeh L A.The key roles of information granulation and fuzzy logic in human reasoning[A].In:Hyatt R,ed.Proceedings of the Fifth IEEI International Conference on Fuzzy System,FUZZ -IEEI'96[C].Germany:Physica- Verlag GmbH Heidelberg,1996.100-106
[10]Zadeh L A.Some reflections on information granulation and its centrality in granular computing,computing with words,the computational theory of perceptions and precisiated natural language[A].In:Lin T Y,ed.Data Mining,Rough Sets and Granular Computing[M].Physica- Verlag GmbH Heidelberg,2002.110-153
[11]张铃,张钹.问题求解理论及应用[M].北京:清华大学出版社,1990.
[12]张铃,张钹.模糊商空间理论(模糊粒度计算方法)[J].软件学报,2003,14(4):770-776.
[13]侯利娟,王国胤,聂能,等.粗糙集理论中的离散化问题[J].计算机科学,2000,27(12):89-94.
[14]Yao Y Y.Granular computing:basic issues and possible solutions.In:Proc.Of the 5~(th) Joint Conf.on Information Sciences,Volume Ⅰ,Atlantic City,New Jersey,USA,February 27-March 3,2000,P.P.Wang Ed.,Association for Intelligent Machinery,2000.186-189.
[15]Pedrycz W.Granular Computing,An Emerging Paradigm.IEEE Trans.On Systems Man and Cybernetics,32(2):212-224.
[16]Lin T Y.Granular computing Ⅱ:Infrastructures for AI-engineering//The 2006 IEEE International Conference on Granular Computing,Atlanta,USA,2006:2-7.
[17]Sierpinski W,Krieger C.General Topology.Toronto:university of Toronto Press,1952.
[18]Zadeh L A.Fuzzy logic=Computing with words[J].I EEE Transactions on Fuzzy Systems,1996,2:103-111.
[19]李道国,苗夺谦,张红云.粒度计算的理论、模型与方法[J].复旦学报,2004,23(5):837-841.
[20]Yao Y Y.Granular computing using neighborhood systems[A].In:Roy R,ed.Advances in soft computing:Engineering design and manufacturing[M].London:Springer Verlag company,1999.539-553.
[21]罗敏.粒计算及其研究现状[J].计算机与现代化[J],2007,1:1-5.
[22]Pawlak Z,Grzymala B J,Slowinski R,et al.Rough set[J].Communication of the ACM,1995,38(11):89- 95.
[23]Zhang Wen-xiu,Wu Wei-zhi,Lang Ji-ye.Rough set theory and method[M].Beijing:Science Publishing Company,2001.
[24]曾正良,罗可,王莹.基于粒子群的不完备决策表属性约简PSO IDTAR法[J].计算机工程与应用,2008,44(14):149-151.
[25]王国胤.Rough集理论在不完备信息系统中的扩充.计算机研究与发展.2002,39(10):1238-1243.
[26]Skowron A.The Discernibility Matrix and Function in Information System.In:R.Slosinski(ED):Intelligent Decision Support:Handbook of Application and Advances of the rough sets Theory(M).Dordrecht Kluwer Academic Publishers,1992,331-362.
[27]Leung Y,Li D Y.Maximal consistent block technique for rule acquisition in incomplete information systems.Information Sciences,2003,153:85-106.
[28]Yao Y Y.Relational interpretations of neighborhood operators and rough set approximation.Information Sciences.1998,111:239-259.
[29]何先刚,黄兵,温平川.不完备信息系统中知识约简的一种启发式算法[J].压电与声光,2004,26(2):158-160.
[30]杨成福,舒兰.基于容差关系的不完备决策系统属性约简算法[J].计算机技术与发展,2006,16(9):68-71.
[31]孙晶晶,刘镔,刘粉林.基于遗传算法的不完备信息表约简方法[J].计算机工程与应用,2005,41(22):174-176.
[32]宫俊,唐加福.基于不完备信息系统的分配约简的启发式算法[J].东北大学学报,2007,28(1):19-22.
[33]Zadeh L A.Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic.Fuzzy Sets and Systems,1997,19(1):111-127.
[34]Pawlak Z.Rough sets.International Journal of Information and Computer Scienxes,1982,11:341-356.
[35]李道国,苗夺谦,张东星,张红云.粒度计算研究综述[J].计算机科学,2005,32(9):1-12.
[36]Shannon C E.A mathematical theory of communication.The Bell System Technical Journal,1948,27(3-4):373-423.
[37]Duntsch I,Gediga G.Uncertainty measures of rough set prediction.Artificial Intelligence,1998,106:109-137.
[38]Liang J Y,Xu Z B.The algorithm on knowledge reduction in incomplete information systems.International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(1):95-103.
[39]Jerzy W.Grzymala-Busse.Rough Set Strategies to Data with Missing Attribute Values[A].Proceedings of the Workshop on Foundations and New Directions in Data Mining,associated with the third IEEE International Conference on Data Mining,2003,Melboume,FL,USA,pp:56-63.
[40]刘清,孙辉,王洪发.粒计算研究现状及基因Rough逻辑语义的粒计算研究[J].计算机学报,2008,31(4):543-5.
[41]Zhang B,Chen W L.Theory and Applications of Problem Solving.Amsterdam:North-Holland,1992.
[42]Yang L,Chen W L,Zhang L.A paradigm of granular computing based on quotient closure space//Proceedings of the 6~(th) World Congress on Intelligent Control and Automation,Dalian,China,2006:1430-1433.
[43]Zhang L,Zhang B.The quotient space theory of problem solving.Fundamenta Informaticae,2004,59(2-3):287-298.
[44]Ma J M,Zhang W X,Li T.A covering model of granular computing//The 2005 International Conference onf Machine Learning and Cybernetics,Guangzhou,China,2005:1625-1630.
[45]Wang J,Zhao M,Zhao K,et al.Multilevel data summarization from information system:A "rule+exception" approach.AI Communications,2003,16(1):17-39.
[46]王钰,姚一豫,王飞跃.基于Reduct的“规则+例外”学习.计算机学报,2005,28(11):1778-1789.
[47]李道国,苗夺谦,张红云.粒度计算的基本问题和可能解决的方案设计.计算机科学,2004,31(2):195-198.
[48]梁吉业,李德玉.信息系统中的不确定性与知识获取.北京:科学出版社,2005.
[49]刘莹.基于泛系的粒度计算及相关模型研究[硕士学位论文].兰州:兰州大学,2006.
[50]邓蔚,王国胤,吴渝.粒计算对进化计算的一个改进.计算机科学,2004,31(10.A):209-211,214.
[51]Wang G Y,Hu F,Huang H,et al.A granular computing model based on tolerance relation.The Journal of China Universities of Posts and Telecommunications,2005,12(3):86-90.
[52]Mi J S,Wu W Z,Zhang W X.Approaches to knowledge reduction based on variable precision rough set model.Information Sciences,2004,159(2):255-272.
[53]Wu W Z,Leung Y,Zhang W X.On generalized rough fuzzy approximation operators.Transactions on Rough Sets,2006,5:263-284.
[54]Zhu W,Wang F Y.Relationshiops among three types of covering rough sets//The 2006 IEEE International Conference on Granular Computing,Atlanta,USA,2006:43-48.
[55]Zhu W.Topological approaches to covering rough sets.Information Sciences,2007,177(6):1499-1508.
[56]刘清,刘群.粒及粒计算在逻辑推理中的应用.计算机研究与发展,2004,41(4):546-551.
[57]刘清,黄兆华.G-逻辑及其归结推理.计算机学报,2004,27(7):865-873.
[58]刘清,孙辉.从Rough集的发展前景看粒计算的研究趋势.南昌工程学院学报,2006,25(5): 1-10.
[59] Zheng Z, Hu H, Shi Z Z. Tolerance relation based granular space//Lecture Notes in Artificial Intelligence 3642. Berlin:Springer, 2005:682-691.