基于粗糙集理论的动态约简研究
|
摘要
本论文的研究工作，主要围绕着基于粗糙集理论的动态约简和完成约简后决策规则的如何制定展开。涵盖了粗糙集理论的基本原理、不同决策表抽样策略的分析、如何利用差别矩阵和差别函数对决策表进行约简等内容。形成了较为完善的决策表动态约简理论和技术方案。
针对不同决策表约简的特殊要求，分析了现有约简方法的优缺点。通过引入动态约简的概念，用动态约简方法处理决策表相当于在决策表约简前预先对决策表进行了抽样处理，提高了约简的精度。并且动态约简挑选出各子决策表中相对稳定的约简作为最终结果，这种处理方法也提高了决策规则的稳定性和描述能力。
在对不同决策表随机抽样方法的研究中，采用了两种新的抽样策略，并详细阐述了此两种抽样策略的适用范围和具体优势。结合概率抽样策略和差别矩阵构造出一个动态约简算法。
从制定决策规则的角度，比较了当前求取决策规则的一些方法，并详细阐述了各方法的优缺点。详细介绍了两种根据决策表直接求取决策规则的方法，以及如何由动态约简计算决策规则。最后建立了一种决策规则的修正算法，完善了决策规则制定后的误差修正。
总结全文，粗糙集理论与方法对于处理复杂系统不失为一种较为有效的手段，被广泛应用于数据挖掘(DM)和数据库知识发现(KDD)领域中。而动态约简及其由约简结果制定决策规则的方法更能为以上两个领域提供高效、精确的数据保证。
The research of this thesis is mainly about the dynamic reduct based on rough set theory as well as how to establish and develop the decision rules after completing the reduct. This paper also covers the basic principle of rough set, the analysis of the sample strategy on different decision tables and how to make use of the discernibility matrix and discernibility function to do reduction with the decision table. Thus a relatively perfect theory and technique scheme of dynamic reduct of the decision table is formed.
According to specific requirement of the reduct of different decision tables, the concept of dynamic reduct is introduced in this dissertation through analysis on current method of reduct.
Using the method of dynamic reduct to deal with the decision table, is equal to take sample from the decision table in advance before the reduction of decision table, which increases the accuracy of reduction. And the relatively stable reduct are chosen from each decision subtable as the ultimate results, which also increases stability and description ability of the decision rules.
At the aspect of randomly choose a sample towards different decision tables, this paper puts forward two kinds of new sampling strategy, and expatiates their application scope and concrete advantages. Combining the max rate sampling strategy and the discernibility matrix together creates the dynamic reduct algorithm.
From the angle of establishing decision rules, this paper compares current methods on accessing the decision rules, and expatiates their merit and shortcoming. The paper emphasizes on two kinds of methods on directly accessing the decision rules with decision table and how to calculate decision rules with dynamic reduct. Finally, a modified algorithm of decision rules is mentioned, which perfect the error modification after the decision rules are established.
In brief, the rough set theory and method is quite an efficient means to deal with complex system, which is applied to the field of data
ABSTRACT
mining(DM) and knowledge discovery in database(KDD). Moreover, dynamic reduct and the method on establishing the decision rules resulted from it can offer more efficient and precise data for the two fields mentioned above.
针对不同决策表约简的特殊要求，分析了现有约简方法的优缺点。通过引入动态约简的概念，用动态约简方法处理决策表相当于在决策表约简前预先对决策表进行了抽样处理，提高了约简的精度。并且动态约简挑选出各子决策表中相对稳定的约简作为最终结果，这种处理方法也提高了决策规则的稳定性和描述能力。
在对不同决策表随机抽样方法的研究中，采用了两种新的抽样策略，并详细阐述了此两种抽样策略的适用范围和具体优势。结合概率抽样策略和差别矩阵构造出一个动态约简算法。
从制定决策规则的角度，比较了当前求取决策规则的一些方法，并详细阐述了各方法的优缺点。详细介绍了两种根据决策表直接求取决策规则的方法，以及如何由动态约简计算决策规则。最后建立了一种决策规则的修正算法，完善了决策规则制定后的误差修正。
总结全文，粗糙集理论与方法对于处理复杂系统不失为一种较为有效的手段，被广泛应用于数据挖掘(DM)和数据库知识发现(KDD)领域中。而动态约简及其由约简结果制定决策规则的方法更能为以上两个领域提供高效、精确的数据保证。
The research of this thesis is mainly about the dynamic reduct based on rough set theory as well as how to establish and develop the decision rules after completing the reduct. This paper also covers the basic principle of rough set, the analysis of the sample strategy on different decision tables and how to make use of the discernibility matrix and discernibility function to do reduction with the decision table. Thus a relatively perfect theory and technique scheme of dynamic reduct of the decision table is formed.
According to specific requirement of the reduct of different decision tables, the concept of dynamic reduct is introduced in this dissertation through analysis on current method of reduct.
Using the method of dynamic reduct to deal with the decision table, is equal to take sample from the decision table in advance before the reduction of decision table, which increases the accuracy of reduction. And the relatively stable reduct are chosen from each decision subtable as the ultimate results, which also increases stability and description ability of the decision rules.
At the aspect of randomly choose a sample towards different decision tables, this paper puts forward two kinds of new sampling strategy, and expatiates their application scope and concrete advantages. Combining the max rate sampling strategy and the discernibility matrix together creates the dynamic reduct algorithm.
From the angle of establishing decision rules, this paper compares current methods on accessing the decision rules, and expatiates their merit and shortcoming. The paper emphasizes on two kinds of methods on directly accessing the decision rules with decision table and how to calculate decision rules with dynamic reduct. Finally, a modified algorithm of decision rules is mentioned, which perfect the error modification after the decision rules are established.
In brief, the rough set theory and method is quite an efficient means to deal with complex system, which is applied to the field of data
ABSTRACT
mining(DM) and knowledge discovery in database(KDD). Moreover, dynamic reduct and the method on establishing the decision rules resulted from it can offer more efficient and precise data for the two fields mentioned above.
引文
[1] Pawlak Z. Rough sets theory and its applications to data analysis. Cybernetics and Systems, 1998, 29: 661～668
[2] Pawlak Z. Vagueness and uncertainty-a rough set perspective. Computational intelligence, 1995, 11 (2): 227～232
[3] Wygralak M. Rough sets and fuzzy sets-some remarks on interrelations. Fuzzy sets and systems, 1989, 29(3): 241～243
[4] Nanda S. Fuzzy rough sets. Fuzzy sets and systems, 1992, 45(2): 157～160
[5] Banerjee M and Pal S K. Roughness of a fuzzy set. Information Science, 1996, 93(3, 4): 235～246
[6] Skowton A. From rough set theory to evidence theory. Advances in the Dempster Shafer Theory of Evidence, New York: John Wiley&Sons Inc., 1994, 193～246
[7] Golan R and Ziarko W. Methodology for stock market analysis utilizing rough set theory. Proc. of IEEE/IAFE Conference on Computational Intelligence for Financial Engineering, New Jersey, 1995, 32～40
[8] Nejman D. A rough set based method of handwritten numerals classification. Institute of Computer Science Reports, Warsaw University of Technology, Warsaw, 1994, 40～46
[9] Teghem J. Use of rough set method to draw premonitory factors for earthquakes by emphasizing gas geochemistry. In: Intelligent Decision Support-Handbook of applications and Advances of the Rough sets theory Dordrecht: Kluwer Academic Publishers, 1992, 165～179
[10] Deja R. Conflict model with negotiations. In: Institute of Computer Science Reports. Warsaw University of Technology, Warsaw, 1995. 44～50
[11] Hu Xiaohua. Mining knowledge rules from databases-a rough set approach. Proc. of IEEE International Conference on data engineering, Los Alamitos, 1996, 96～105
[12] Tsumoto Sh. Extraction of domain knowledge from databases based on rough set theory. IEEE International Conference on Fuzzy systems, New Jersey, 1996, 748～754
[13] Sienkiewicz J. Rough set and rough function approaches to the control algorithm reconstruction. Institute of Computer Science Reports, Warsaw University of Technology, Warsaw, 1996. 102～108
[14] Mrozek A. Methodology of rough controller synthesis. Proc. of IEEE International Conference on Fuzzy systems, New Jersey, 1996, 1135～1139
[15] Pawlak Z. Rough sets. rough relations and rough functions. Fundamental Informatics, 1996, 27(2, 3): 103～108
[16] Plonka L and Mrozek A. Rule-based stabilization of the inverted pendulum. Computational Intelligence, 1995, 11(2): 348～356
[17] Czogala E. Idea of a rough fuzzy controller and its application to the stabilization of a pendulum-car system. Fuzzy sets and systems, 1995, 72(1): 61～73
[18] Mrozek A. Rough sets and dependency analysis among attributes in computers implementations of expert's inference models. International Journal of Man-Machine Studies, 1989, 30(4): 457～473
[19] Arima M. Fuzzy logic and rough sets controller for HVAC systems. Proc. of IEEE WESCANEX Communication, Power, and Computing, New York, 1995, 133～138
[20] Pawlak Z. Rough sets. Communications of ACM, 1995, 38(11): 89～95
[21] Tsumoto S. Automated discovery of medical expert system rules from clinical databases based on rough set. Proc. of Second International Conf. on Knowledge discovery and data Mining, USA, 1996, 63～72
[22] Jelonek J. Rough set reducts of attributes and their domains for neural networks. Computational Intelligence, 1995, 11 (2): 339～347
[23] Peng C. Multi-valued neural network and the knowledge acquisition method by
the rough sets for ambiguous recognition problem. Proc. of the IEEE International Conference on Systems, Man and Cybemetics, Beijing, 1996, 736～740
[24] Yasdi R. Combining rough sets learning and neural learning-method to deal with uncertain and imprecise information. Neurocomputing, 1995, 7(1): 61～84
[25] 杨炳儒，樊广诠，陈泓婕．一类基于信息挖掘的智能决策支持系统的结构建模．模式识别与人工智能，2003．6，(2)：225～226
[26] Lim M. Software system for intelligent data processing and discovering based on the fuzzy-rough sets theory[D]. San Diego: San Diego State University, 1995. 142～146
[27] 韩祯祥，张琦，文福栓．粗糙集理论及其应用综述．控制理论与应用，1999，16(2)：153～157
[28] Slowinski R. Rough-set reasoning about uncertain data. Fund Inform, 1996, 27: 229～244
[29] Slowinski R. Rough set approach to decision analysis. AI expert, March 1995, 19～25
[30] Daijin Kim. IRIS data classification using tolerant rough set, Journal of advanced computational intelligence, 2000, 4(5): 327～334
[31] 李永敏，朱善均．基于粗集理论的数据开采模型．清华大学学报，1999，39(1)：110～113
[32] 王珏，王任，苗夺谦等．基于Rough Set理论的数据浓缩，计算机学报，1998，21(5)：393～399
[33] 金龙，李晓红．连续属性的整体离散化．哈尔滨工业大学学报，2000，32(3)：48～53
[34] Yu Songnian. Parallel data mining model based on genetic algorithm and rough set approach in PVM environment. Intelligent Engineering Systems Through Artificial Neural Network, 1999, 10: 505～510
[35] Ziarko W. Variable Precision Rough Sets Model. Computer. Syst. Scie, 1993, 46: 39～59
[36] Mrozek K. A rough Sets and Dependency Analysis Among Attributes in Computer Implementation soft Expert's Inference Models, International Journal of Man-Machine Studies, 1989, 30: 457～473
[37] Slowinski R. Rough Sets Sorting of Firms According to Bankruptcy Risk. In Applying Multiple criteria Aid for Decision To Environmental Management, M.Paruccini, Ed.Klunwer, Dordrecht, Netherlands, 1994: 339～357
[38] 曾黄麟．粗糙集理论及其应用(修订版)．重庆：重庆大学出版社，1998．
[39] 张文修，吴伟志．粗糙集理论介绍与研究综述．模糊系统与数学，2000，14(4)：1～12
[40] 张文修，吴伟志．粗糙集理论与方法．科学出版社，2000，8．
[41] 王清毅，范焱，蔡庆生．知识的约简研究．小型微型计算机系统，2000，6 21(6)：623～625
[42] Jakub W. Finding minimal reducts using genetic algorithm. Warsaw: Warsaw University of Technology, 1995.1125～1130
[43] 唐建国，谭明术．粗糙集理论中的求核与约简[J]．控制与决策，2003，7． 18(4)：449～452．
[44] Jan G. Bazan, Andrzej Skowron, Piotr Synak. Dynamic Reduets as a Tool for Extracting Laws form Decisions Tables[D]. In: Z. W. Ras, M. Zemankowa (eds.), Proceedings of the Eighth, Symposium on Methodologies for Intelligent Systems, Charlotte, NC, October 16-19, Lecture Notes in Artificial Intelligence 869, Springer-Verlag(1994) 346～355
[45] Jan G. Bazan. Dynamic reducts and statistical inference. In: Proceedings of the Sixth International Conference, Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU'96), July 1-5, Granada, Sipain(1996) 2 1147～1152
[46] 韩斌，吴铁军，杨明晖．结合粗集理论的动态约简研究．系统工程理论与
实践，2002，6，(6)：68～73
[47] Mollestad T. A rough set approach to default rules data mining. PhD Thesis, supervisor J. Komorowski, Norvegian Institute of Technology, Trondheim, Norway (1996).
[48] Mienko, R., Slowinski, R., Stefanowski, J, Susmaga, R.: Rough Family-soft ware Implementation of rough set based data analysis and rule discovery techniques. In: S.Tsumoto, S.Kobayashi, T.Yokomori, H.Tanaka, and A. Nakamura (eds.): Proceeding of the Fourth International Workshop on Rough Sets, Fuzzy Sets, and Machine Discovery (RSFD'96), The University of Tokyo, November 6-8 (1996) 437～440
[49] Polkowski, L., Skowron, A.: Synthesis of decision systems from data tables. In: T. Y. Lin, N. Cercone (eds.): Rough Sets and Data Mining. Analysis of Imprecise Data, Kluwer Academic Publishers, Dordrecht (1997) 259～299
[50] Skowron, A.: Extracting laws from decision tables. In: W. Ziarko (ed.): Proceedings of the Second International Workshop on Rough Sets and Knowledge Discovery (RSKD'93), Banff, Alberta, Canada, OCTOBER 12-15 (1993) 101～104
[2] Pawlak Z. Vagueness and uncertainty-a rough set perspective. Computational intelligence, 1995, 11 (2): 227～232
[3] Wygralak M. Rough sets and fuzzy sets-some remarks on interrelations. Fuzzy sets and systems, 1989, 29(3): 241～243
[4] Nanda S. Fuzzy rough sets. Fuzzy sets and systems, 1992, 45(2): 157～160
[5] Banerjee M and Pal S K. Roughness of a fuzzy set. Information Science, 1996, 93(3, 4): 235～246
[6] Skowton A. From rough set theory to evidence theory. Advances in the Dempster Shafer Theory of Evidence, New York: John Wiley&Sons Inc., 1994, 193～246
[7] Golan R and Ziarko W. Methodology for stock market analysis utilizing rough set theory. Proc. of IEEE/IAFE Conference on Computational Intelligence for Financial Engineering, New Jersey, 1995, 32～40
[8] Nejman D. A rough set based method of handwritten numerals classification. Institute of Computer Science Reports, Warsaw University of Technology, Warsaw, 1994, 40～46
[9] Teghem J. Use of rough set method to draw premonitory factors for earthquakes by emphasizing gas geochemistry. In: Intelligent Decision Support-Handbook of applications and Advances of the Rough sets theory Dordrecht: Kluwer Academic Publishers, 1992, 165～179
[10] Deja R. Conflict model with negotiations. In: Institute of Computer Science Reports. Warsaw University of Technology, Warsaw, 1995. 44～50
[11] Hu Xiaohua. Mining knowledge rules from databases-a rough set approach. Proc. of IEEE International Conference on data engineering, Los Alamitos, 1996, 96～105
[12] Tsumoto Sh. Extraction of domain knowledge from databases based on rough set theory. IEEE International Conference on Fuzzy systems, New Jersey, 1996, 748～754
[13] Sienkiewicz J. Rough set and rough function approaches to the control algorithm reconstruction. Institute of Computer Science Reports, Warsaw University of Technology, Warsaw, 1996. 102～108
[14] Mrozek A. Methodology of rough controller synthesis. Proc. of IEEE International Conference on Fuzzy systems, New Jersey, 1996, 1135～1139
[15] Pawlak Z. Rough sets. rough relations and rough functions. Fundamental Informatics, 1996, 27(2, 3): 103～108
[16] Plonka L and Mrozek A. Rule-based stabilization of the inverted pendulum. Computational Intelligence, 1995, 11(2): 348～356
[17] Czogala E. Idea of a rough fuzzy controller and its application to the stabilization of a pendulum-car system. Fuzzy sets and systems, 1995, 72(1): 61～73
[18] Mrozek A. Rough sets and dependency analysis among attributes in computers implementations of expert's inference models. International Journal of Man-Machine Studies, 1989, 30(4): 457～473
[19] Arima M. Fuzzy logic and rough sets controller for HVAC systems. Proc. of IEEE WESCANEX Communication, Power, and Computing, New York, 1995, 133～138
[20] Pawlak Z. Rough sets. Communications of ACM, 1995, 38(11): 89～95
[21] Tsumoto S. Automated discovery of medical expert system rules from clinical databases based on rough set. Proc. of Second International Conf. on Knowledge discovery and data Mining, USA, 1996, 63～72
[22] Jelonek J. Rough set reducts of attributes and their domains for neural networks. Computational Intelligence, 1995, 11 (2): 339～347
[23] Peng C. Multi-valued neural network and the knowledge acquisition method by
the rough sets for ambiguous recognition problem. Proc. of the IEEE International Conference on Systems, Man and Cybemetics, Beijing, 1996, 736～740
[24] Yasdi R. Combining rough sets learning and neural learning-method to deal with uncertain and imprecise information. Neurocomputing, 1995, 7(1): 61～84
[25] 杨炳儒，樊广诠，陈泓婕．一类基于信息挖掘的智能决策支持系统的结构建模．模式识别与人工智能，2003．6，(2)：225～226
[26] Lim M. Software system for intelligent data processing and discovering based on the fuzzy-rough sets theory[D]. San Diego: San Diego State University, 1995. 142～146
[27] 韩祯祥，张琦，文福栓．粗糙集理论及其应用综述．控制理论与应用，1999，16(2)：153～157
[28] Slowinski R. Rough-set reasoning about uncertain data. Fund Inform, 1996, 27: 229～244
[29] Slowinski R. Rough set approach to decision analysis. AI expert, March 1995, 19～25
[30] Daijin Kim. IRIS data classification using tolerant rough set, Journal of advanced computational intelligence, 2000, 4(5): 327～334
[31] 李永敏，朱善均．基于粗集理论的数据开采模型．清华大学学报，1999，39(1)：110～113
[32] 王珏，王任，苗夺谦等．基于Rough Set理论的数据浓缩，计算机学报，1998，21(5)：393～399
[33] 金龙，李晓红．连续属性的整体离散化．哈尔滨工业大学学报，2000，32(3)：48～53
[34] Yu Songnian. Parallel data mining model based on genetic algorithm and rough set approach in PVM environment. Intelligent Engineering Systems Through Artificial Neural Network, 1999, 10: 505～510
[35] Ziarko W. Variable Precision Rough Sets Model. Computer. Syst. Scie, 1993, 46: 39～59
[36] Mrozek K. A rough Sets and Dependency Analysis Among Attributes in Computer Implementation soft Expert's Inference Models, International Journal of Man-Machine Studies, 1989, 30: 457～473
[37] Slowinski R. Rough Sets Sorting of Firms According to Bankruptcy Risk. In Applying Multiple criteria Aid for Decision To Environmental Management, M.Paruccini, Ed.Klunwer, Dordrecht, Netherlands, 1994: 339～357
[38] 曾黄麟．粗糙集理论及其应用(修订版)．重庆：重庆大学出版社，1998．
[39] 张文修，吴伟志．粗糙集理论介绍与研究综述．模糊系统与数学，2000，14(4)：1～12
[40] 张文修，吴伟志．粗糙集理论与方法．科学出版社，2000，8．
[41] 王清毅，范焱，蔡庆生．知识的约简研究．小型微型计算机系统，2000，6 21(6)：623～625
[42] Jakub W. Finding minimal reducts using genetic algorithm. Warsaw: Warsaw University of Technology, 1995.1125～1130
[43] 唐建国，谭明术．粗糙集理论中的求核与约简[J]．控制与决策，2003，7． 18(4)：449～452．
[44] Jan G. Bazan, Andrzej Skowron, Piotr Synak. Dynamic Reduets as a Tool for Extracting Laws form Decisions Tables[D]. In: Z. W. Ras, M. Zemankowa (eds.), Proceedings of the Eighth, Symposium on Methodologies for Intelligent Systems, Charlotte, NC, October 16-19, Lecture Notes in Artificial Intelligence 869, Springer-Verlag(1994) 346～355
[45] Jan G. Bazan. Dynamic reducts and statistical inference. In: Proceedings of the Sixth International Conference, Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU'96), July 1-5, Granada, Sipain(1996) 2 1147～1152
[46] 韩斌，吴铁军，杨明晖．结合粗集理论的动态约简研究．系统工程理论与
实践，2002，6，(6)：68～73
[47] Mollestad T. A rough set approach to default rules data mining. PhD Thesis, supervisor J. Komorowski, Norvegian Institute of Technology, Trondheim, Norway (1996).
[48] Mienko, R., Slowinski, R., Stefanowski, J, Susmaga, R.: Rough Family-soft ware Implementation of rough set based data analysis and rule discovery techniques. In: S.Tsumoto, S.Kobayashi, T.Yokomori, H.Tanaka, and A. Nakamura (eds.): Proceeding of the Fourth International Workshop on Rough Sets, Fuzzy Sets, and Machine Discovery (RSFD'96), The University of Tokyo, November 6-8 (1996) 437～440
[49] Polkowski, L., Skowron, A.: Synthesis of decision systems from data tables. In: T. Y. Lin, N. Cercone (eds.): Rough Sets and Data Mining. Analysis of Imprecise Data, Kluwer Academic Publishers, Dordrecht (1997) 259～299
[50] Skowron, A.: Extracting laws from decision tables. In: W. Ziarko (ed.): Proceedings of the Second International Workshop on Rough Sets and Knowledge Discovery (RSKD'93), Banff, Alberta, Canada, OCTOBER 12-15 (1993) 101～104