基于粗糙集理论的属性约简算法研究及应用
|
摘要
数据库技术已经从原始的数据处理，发展到开发具有查询和事务处理能力的数据库管理系统。进一步的发展导致越来越需要有效的数据分析和数据理解工具。粗糙集理论正是一种处理不确定、不一致数据的数学工具。本文的主要研究成果有以下三个方面：
1.提出了一种基于区分矩阵的属性约简算法ARDM
通过对基于区分矩阵的属性约简算法进行分析，找出影响时间效率的因素并将命题演算中的吸收率用于构造区分矩阵的过程中，从而去掉了在区分函数中不起作用的“重复”元素，提高了属性约简的效率。
2.提出了一种增量式属性约简算法
针对实际问题中数据库中的数据是不断变化的这一情况，以粗糙逻辑为基础，针对新加入的对象相对于原来的极小决策算法而言是全新的这种情况，提出了一种增量式属性约简算法，从而避免每次从庞大的原始决策表开始约简，实现了对原极小决策算法的更新与维护，提高了属性约简的效率。
3.依据上述属性约简算法，采用Visual FoxPro 6.0数据库管理系统，设计与实现了恒星光谱数据自动分类系统，实现了恒星光谱分类规则的自动提取。
Database Technology has already been developed from original data processing to Database Management System, which can inquire and process transaction. With the further development, the efficient data analysis and data understandability tools are more and more needed. Rough sets is just a mathematical tool to deal with imprecise and inconsistent knowledge. This paper shows three aspects as follow:
1. An algorithm of attribute reduction based on discernibility matrix ----ARDM is presented.
Through analyzing to the algorithm of attribute reduction based on discernibility matrix, the facts that affect time efficiency are found, and the absorptivity in the proposition calculation is used to the process of constructing the discernibility matrix, then the effectless repeated elements are deleted, accordingly the efficiency of attribute reduction is improved.
2. An dynamic algorithm of attribute reduction is presented.
In fact, data are always changing in database, so a dynamic algorithm of attribute reduction based on rough logic is presented, which can get new minimum decision algorithm based on the original one when new object is added. It can avoid reduction from large original decision table, update and vindicate the original algorithm, and improve the efficiency of attribute reduction.
3. According to the algorithm of attribute reduction, auto-classification system about stellar spectrum data is designed and implemented through using Visual FoxPro 6.0, which automatically extract rules from stellar spectrum.
1.提出了一种基于区分矩阵的属性约简算法ARDM
通过对基于区分矩阵的属性约简算法进行分析，找出影响时间效率的因素并将命题演算中的吸收率用于构造区分矩阵的过程中，从而去掉了在区分函数中不起作用的“重复”元素，提高了属性约简的效率。
2.提出了一种增量式属性约简算法
针对实际问题中数据库中的数据是不断变化的这一情况，以粗糙逻辑为基础，针对新加入的对象相对于原来的极小决策算法而言是全新的这种情况，提出了一种增量式属性约简算法，从而避免每次从庞大的原始决策表开始约简，实现了对原极小决策算法的更新与维护，提高了属性约简的效率。
3.依据上述属性约简算法，采用Visual FoxPro 6.0数据库管理系统，设计与实现了恒星光谱数据自动分类系统，实现了恒星光谱分类规则的自动提取。
Database Technology has already been developed from original data processing to Database Management System, which can inquire and process transaction. With the further development, the efficient data analysis and data understandability tools are more and more needed. Rough sets is just a mathematical tool to deal with imprecise and inconsistent knowledge. This paper shows three aspects as follow:
1. An algorithm of attribute reduction based on discernibility matrix ----ARDM is presented.
Through analyzing to the algorithm of attribute reduction based on discernibility matrix, the facts that affect time efficiency are found, and the absorptivity in the proposition calculation is used to the process of constructing the discernibility matrix, then the effectless repeated elements are deleted, accordingly the efficiency of attribute reduction is improved.
2. An dynamic algorithm of attribute reduction is presented.
In fact, data are always changing in database, so a dynamic algorithm of attribute reduction based on rough logic is presented, which can get new minimum decision algorithm based on the original one when new object is added. It can avoid reduction from large original decision table, update and vindicate the original algorithm, and improve the efficiency of attribute reduction.
3. According to the algorithm of attribute reduction, auto-classification system about stellar spectrum data is designed and implemented through using Visual FoxPro 6.0, which automatically extract rules from stellar spectrum.
引文
[1] R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. In: Proc. of the ACM SIGMOD Conference on Management of Data, May 1993,Washington, D.C., 207--216.
[2] J. Han , M. Kambr. Data Mining concepts and Techniques. Morgan Kaufmann Publishers.2000
[3] 欧阳为民、郑诚、张燕，国际知识发现与数据发掘工具评述，计算机科学，2001，28，3， 101-108
[4] 罗阿理博士论文，“LAMOST光谱自动处理的模式识别方法”，国家天文台，2001
[5] 《星星之友》，M.J.马丁，D.H.门泽尔，人民教育出版社，1985
[6] Z.Pawlak, Rough sets, Int . J. Inform.. Sci.11(1982),341---356.
[7] Z.Pawlak, Rough sets:Theoretical Aspects of Reasoning about Data , Kluwer Academic Publishers, Dordrecht ,1991.
[8] Pawlak, Z., Rough sets and intelligent data analysis, Information Sciences, 147(2002),1—12.
[9] Bonikowski Z. , Algebraic structures of rough stes .In: Ziarko W. (Ed.), Rough sets, Fuzzy Sets and Knowledge Discovery , Springer—Verlag, 1994, 242—247.
[10] Bryniarski E. , Formal description of rough sets. In: Ziarko W. (Ed), Rough sets, Fuzzy Sets and Knowledge Discovery, inger—Verlag,1994,208—216.
[11] Shan N. and Ziarko W., An incremental learning algorithm for constructing decision rules. In: Ziarko W.(ED.), Rough Sets, Fuzzy Sets and Knowledge Discovery, Springer-verlag,1994,326-334.
[12] Shan N. and Ziarko W., Data-based acquisition and incremental modification of classification rules, Computational Intelligence,1995,11(2): 357-369.
[13] Duntsh I.,A logic for rough sets.Theoretical Computer Science, 1997, 179(1,2):427-436.
[14] 刘清,Rough 集及Rough推理. 北京:科学出版社,2001.
[15] Nakamura A.,A rough logic based on incompute information and its application.International Journal of Approximate Reasoning,1996,15: 367-378.
[16] Skowron A.,The rough sets theory and evidence theory. Fundamenta Informaticae, 1990, XIII: 245-262.
[17] Biswas,R., On rough sets and fuzzy rough sets, Bull. Pol. Acad. Sci. Math. 42(1994),345-349.
[18] Chmielewski M. R. and Grzymala-Busse W., Global discretization of ontinuous attributes as preprocessing for machine learning. International Journal of Approximate Reasoning, 1996,15(4): 319-331.
[19] 王国胤,Rough 集理论与知识获取. 西安:西安交通大学出版社, 2001.
[20] A.Skowron , C. Rauszer , The discernibility matrices and functions in information system, in: R. Slowinski (Ed.), Intelligent Decision Support : Handbook of Applications and Advances of Rough Sets Theory , Kluwer Academic Publisher, Dordrecht, 1992, pp.331-362.
[21] Pawlak,Z., Rough sets algebraic and topological approach , ICS PAS Rep. 482 (1982).
[22] Yee Leung and Deyu Li ,Maximal consistent block technique for rule acquisition in incomplete information systems , Informational Sciences: An International Journal , (2003),(in press).
[23] Shannon , C. E., The mathematical theory of communication ,The Bell System Technical Journal , 27(3 and 4), 374-423 (see also pp.623-656).
[24] 王国胤 ,于洪, 杨大春, 基于条件信息熵的决策表约简[J]，计算机学报, 25(7)(2002), 759-766.
[25] Wang G Y, Algebra view and information view of rough sets theory , Proceedings of SPIE, 4384(2001), 200-207.
[26] Miao Duo-Qian and Wang Jue ,An information representation of the concepts and operation in rough set theory , Journal of Software,10(2)(1999),113-116.(in
Chinese)
[27] Miao Duo-Qian and Hu Gui-Rong , A Heuristic algorithm for reduction of knowledge, Journal of Computer Research and Development, 36(6)(1999),681-684.(in Chinese)
[28] 苗夺谦,王珏, Rough Set 理论中知识粗糙性与信息熵关系的讨论, 模式识别与人工智能, 11(1)(1998),34-40.
[29] Pawlak, z., Rough sets and fuzzy sets, Fuzzy Sets and Systems, 17(1985),99-102.
[30] Y. Y. Yao, A comparative study of fuzzy sets and rough sets,Journal of Information Sciences, 109(1998),227-242.
[31] Kankana Chakabarty, Ranjit Biswas and Sudarsan Nanda, Fuzziness in rough set, Fuzzy Sets and Systems,110(2000),247-251.
[32] Mohua Banerjee and Sankar K. Pal, Roughness of a Fuzzy Set, Informatics and Computer Science, 93(1996),235-246.
[33] Toshinori Munakata, Fundamentals of The New Artificial Intelligence ---Beyond Traditional Paradigms, Springer-Verlag, New York,1998.
[34] Wong S. K. and Ziarko W., On optimal decision rules in decision tables. Bulletin of Polish Academy of Sciences,1985,33: 693-696.
[35] Shan N. and Ziarko W., An incremental learning algorithm for constructing decision rules. In: Ziarko W.(ED.), Rough Sets, Fuzzy Sets and Knowledge Discovery, Springer-verlag,1994,326-334.
[36] Shan N. and Ziarko W., Data-based acquisition and incremental modification of classification rules, Computational Intelligence,1995,11(2): 357-369.
[37] Hu X. and Cercone N., Learning in relational databases: a rough set approach. Computational Intelligence,1995,11(2): 323-338.
[38] Jelonek J. et. al., Rough set reduction of attributes and their domains for neural networks. Computational Intelligence, 1995,11(2): 339-347.
[39] Muraszkieqicz M. and Rybinski H., Towards a parallel rough sets computer.
In: Ziarko W.(ED.),Rough Sets, Fuzzy Sets and Knowledge Discovery, Springer-Verlag,1994,167-181.
[40] Won-Chul Bang and Zeungnam Bien, New Incremental Inductive Learning Algorithm in the Framework of Rough Set Theory, International Journal of Fuzzy Systems, Vol. 1, No.1 September 1999.
[41] J. G. Bazan, A. Skowron and P. Synak, Dynamic reducts as a tool for extracting laws form decision tables, In: Proceedings of the International Symposium on Methodologies for Intelligent Systems, number 869, Lecture Notes in Artificial Intelligence, Springer, New York, 1994, pp. 346-355.
[42] 张文修，梁怡，吴伟志，信息系统与知识发现，（手稿）。
[43] 刘宗田，属性最小约简的增量式算法，电子学报，27（11），1999，96-98.
[44] 陈云化，叶东毅，基于粗糙集理论的一个增量算法，计算机科学，29（9）（专刊），2002，53-55.
[45]Won-Chul Bang, Zeungnam Bien, New incremental inductive learning algorithm in the framework of rough set theory, International Journal of Fuzzy Systems, Vol.1 (1), 1999, 25-36.
[46] Brodley C E, Utgoff P E.Multivariate Decision Trees,vol 19,1995:45-47.
[47] J W Guan,D A Bell. Rough Computational Methods for Information Systems, Artificial Intelligence, vol 105,1998:77-103.
[48] Skowron A. Crauser.The Discernibility Matrix and function in Information System, Handbook of Application and Advances of the Rough Set Theory. Kluwer Academic Publishers,1992:331-362.
[49] 苗夺谦, 胡桂荣. 知识约简的一种启发式算法[J]. 计算机研究与发展, 1999, 36(6): 681-684.
[2] J. Han , M. Kambr. Data Mining concepts and Techniques. Morgan Kaufmann Publishers.2000
[3] 欧阳为民、郑诚、张燕，国际知识发现与数据发掘工具评述，计算机科学，2001，28，3， 101-108
[4] 罗阿理博士论文，“LAMOST光谱自动处理的模式识别方法”，国家天文台，2001
[5] 《星星之友》，M.J.马丁，D.H.门泽尔，人民教育出版社，1985
[6] Z.Pawlak, Rough sets, Int . J. Inform.. Sci.11(1982),341---356.
[7] Z.Pawlak, Rough sets:Theoretical Aspects of Reasoning about Data , Kluwer Academic Publishers, Dordrecht ,1991.
[8] Pawlak, Z., Rough sets and intelligent data analysis, Information Sciences, 147(2002),1—12.
[9] Bonikowski Z. , Algebraic structures of rough stes .In: Ziarko W. (Ed.), Rough sets, Fuzzy Sets and Knowledge Discovery , Springer—Verlag, 1994, 242—247.
[10] Bryniarski E. , Formal description of rough sets. In: Ziarko W. (Ed), Rough sets, Fuzzy Sets and Knowledge Discovery, inger—Verlag,1994,208—216.
[11] Shan N. and Ziarko W., An incremental learning algorithm for constructing decision rules. In: Ziarko W.(ED.), Rough Sets, Fuzzy Sets and Knowledge Discovery, Springer-verlag,1994,326-334.
[12] Shan N. and Ziarko W., Data-based acquisition and incremental modification of classification rules, Computational Intelligence,1995,11(2): 357-369.
[13] Duntsh I.,A logic for rough sets.Theoretical Computer Science, 1997, 179(1,2):427-436.
[14] 刘清,Rough 集及Rough推理. 北京:科学出版社,2001.
[15] Nakamura A.,A rough logic based on incompute information and its application.International Journal of Approximate Reasoning,1996,15: 367-378.
[16] Skowron A.,The rough sets theory and evidence theory. Fundamenta Informaticae, 1990, XIII: 245-262.
[17] Biswas,R., On rough sets and fuzzy rough sets, Bull. Pol. Acad. Sci. Math. 42(1994),345-349.
[18] Chmielewski M. R. and Grzymala-Busse W., Global discretization of ontinuous attributes as preprocessing for machine learning. International Journal of Approximate Reasoning, 1996,15(4): 319-331.
[19] 王国胤,Rough 集理论与知识获取. 西安:西安交通大学出版社, 2001.
[20] A.Skowron , C. Rauszer , The discernibility matrices and functions in information system, in: R. Slowinski (Ed.), Intelligent Decision Support : Handbook of Applications and Advances of Rough Sets Theory , Kluwer Academic Publisher, Dordrecht, 1992, pp.331-362.
[21] Pawlak,Z., Rough sets algebraic and topological approach , ICS PAS Rep. 482 (1982).
[22] Yee Leung and Deyu Li ,Maximal consistent block technique for rule acquisition in incomplete information systems , Informational Sciences: An International Journal , (2003),(in press).
[23] Shannon , C. E., The mathematical theory of communication ,The Bell System Technical Journal , 27(3 and 4), 374-423 (see also pp.623-656).
[24] 王国胤 ,于洪, 杨大春, 基于条件信息熵的决策表约简[J]，计算机学报, 25(7)(2002), 759-766.
[25] Wang G Y, Algebra view and information view of rough sets theory , Proceedings of SPIE, 4384(2001), 200-207.
[26] Miao Duo-Qian and Wang Jue ,An information representation of the concepts and operation in rough set theory , Journal of Software,10(2)(1999),113-116.(in
Chinese)
[27] Miao Duo-Qian and Hu Gui-Rong , A Heuristic algorithm for reduction of knowledge, Journal of Computer Research and Development, 36(6)(1999),681-684.(in Chinese)
[28] 苗夺谦,王珏, Rough Set 理论中知识粗糙性与信息熵关系的讨论, 模式识别与人工智能, 11(1)(1998),34-40.
[29] Pawlak, z., Rough sets and fuzzy sets, Fuzzy Sets and Systems, 17(1985),99-102.
[30] Y. Y. Yao, A comparative study of fuzzy sets and rough sets,Journal of Information Sciences, 109(1998),227-242.
[31] Kankana Chakabarty, Ranjit Biswas and Sudarsan Nanda, Fuzziness in rough set, Fuzzy Sets and Systems,110(2000),247-251.
[32] Mohua Banerjee and Sankar K. Pal, Roughness of a Fuzzy Set, Informatics and Computer Science, 93(1996),235-246.
[33] Toshinori Munakata, Fundamentals of The New Artificial Intelligence ---Beyond Traditional Paradigms, Springer-Verlag, New York,1998.
[34] Wong S. K. and Ziarko W., On optimal decision rules in decision tables. Bulletin of Polish Academy of Sciences,1985,33: 693-696.
[35] Shan N. and Ziarko W., An incremental learning algorithm for constructing decision rules. In: Ziarko W.(ED.), Rough Sets, Fuzzy Sets and Knowledge Discovery, Springer-verlag,1994,326-334.
[36] Shan N. and Ziarko W., Data-based acquisition and incremental modification of classification rules, Computational Intelligence,1995,11(2): 357-369.
[37] Hu X. and Cercone N., Learning in relational databases: a rough set approach. Computational Intelligence,1995,11(2): 323-338.
[38] Jelonek J. et. al., Rough set reduction of attributes and their domains for neural networks. Computational Intelligence, 1995,11(2): 339-347.
[39] Muraszkieqicz M. and Rybinski H., Towards a parallel rough sets computer.
In: Ziarko W.(ED.),Rough Sets, Fuzzy Sets and Knowledge Discovery, Springer-Verlag,1994,167-181.
[40] Won-Chul Bang and Zeungnam Bien, New Incremental Inductive Learning Algorithm in the Framework of Rough Set Theory, International Journal of Fuzzy Systems, Vol. 1, No.1 September 1999.
[41] J. G. Bazan, A. Skowron and P. Synak, Dynamic reducts as a tool for extracting laws form decision tables, In: Proceedings of the International Symposium on Methodologies for Intelligent Systems, number 869, Lecture Notes in Artificial Intelligence, Springer, New York, 1994, pp. 346-355.
[42] 张文修，梁怡，吴伟志，信息系统与知识发现，（手稿）。
[43] 刘宗田，属性最小约简的增量式算法，电子学报，27（11），1999，96-98.
[44] 陈云化，叶东毅，基于粗糙集理论的一个增量算法，计算机科学，29（9）（专刊），2002，53-55.
[45]Won-Chul Bang, Zeungnam Bien, New incremental inductive learning algorithm in the framework of rough set theory, International Journal of Fuzzy Systems, Vol.1 (1), 1999, 25-36.
[46] Brodley C E, Utgoff P E.Multivariate Decision Trees,vol 19,1995:45-47.
[47] J W Guan,D A Bell. Rough Computational Methods for Information Systems, Artificial Intelligence, vol 105,1998:77-103.
[48] Skowron A. Crauser.The Discernibility Matrix and function in Information System, Handbook of Application and Advances of the Rough Set Theory. Kluwer Academic Publishers,1992:331-362.
[49] 苗夺谦, 胡桂荣. 知识约简的一种启发式算法[J]. 计算机研究与发展, 1999, 36(6): 681-684.