Rough Rule Extracting From Various Conditions: Incremental and Approximate Approaches for Inconsistent Data

• Autorzy: Liu Y. , Xu C. , Zhang Q , Pan Y.
• Języki publikacji: EN

Abstrakty

EN

Rough rule extraction refers to the rule induction method by using rough set theory. Although rough set theory is a powerful mathematical tool in dealing with vagueness and uncertainty in data sets, it is lack of effective rule extracting approach under complex conditions. This paper proposes several algorithms to perform rough rule extraction from data sets with different properties. Firstly, in order to obtain uncertainty rules from inconsistent data, we introduce the concept of confidence factor into the rule extracting process. Then, an improved incremental rule extracting algorithm is proposed based on the analysis of the incremental data categories. Finally, above algorithms are further extended to perform approximate rule extraction from huge data sets. Preliminary experiment results are encouraging.

Słowa kluczowe

EN

rough sets; improved discernibility matrix; inconsistent rules; incremental algorithm; approximate rule-extracting

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 84, nr 3-4
• Strony: 403--427
• Opis fizyczny: bibliogr. 49 poz., wykr.

Twórcy

autor

Liu Y.

autor

Xu C.

autor

Zhang Q

autor

Pan Y.

• State Key Lab. of Industrial Control Technology, Zhejiang University, 310027 Hangzhou, China [e-mail],

Bibliografia

• [1] The ROSETTA homepage, http://rosetta.lcb.uu.se/general/.
• [2] Rough Analysis, http://www.lsi.upc.es/ealvarez/rough.html.
• [3] The Rough Enough homepage, http://www.trolldata.no/renough/.
• [4] RSES: Rough Set Exploration System, http://logic.mimuw.edu.pl/rses.
• [5] The UCI KDD Archive, Http://kdd.ics.uci.edu.
• [6] UCI Machine Learning Data Repository, Http://www.ics.uci.edu/mlearnMLRepository.html.
• [7] Agrawal, R., Imielinski, T, Swami, A. N.: Mining Association Rules between Sets of Items in Large Databases, Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28,1993 (P. Buneman, S. Jajodia, Eds.), ACM Press, 1993.
• [8] Agrawal, R., Srikant, R.: Fast Algorithms for Mining Association Rules in Large Databases, VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile (J. B. Bocca, M. Jarke, C. Zaniolo, Eds.), Morgan Kaufmann, 1994, ISBN 1-55860-153-8.
• [9] Bazan, J. G., Nguyen, H. S., Nguyen, S. H., Synak, P., Wroblewski, J.: Rough set algorithms in classification problem, Rough set methods and applications: new developments in knowledge discovery in information systems, 2000,49-88.
• [10] Bian, X.: Certain rule learning of the inconsistent data., Journal of East China Shipbuilding Institute, 12(1), 1998, 25-30.
• [11] Blum, A., Langley, P.: Selection of Relevant Features and Examples in Machine Learning., Artif. Intell., 97(1-2),1997,245-271.
• [12] Chouchoulas, A., Shen, Q.: Rough Set-Aided Keyword Reduction for Text Categorization., Applied Artificial Intelligence, 15(9), 2001, 843-873.
• [13] Cohen, W. W.: Fast Effective Rule Induction., ICML, 1995.
• [14] Cohen, W. W., Singer, Y.: A Simple, Fast, and Effictive Rule Learner., AAAI/IAAI, 1999.
• [15] Dash, M., Liu, H.: Feature Selection for Classification., Intell. Data Anal, 1(1-4), 1997, 131-156.
• [16] Fern, A., Givan, R.: Online Ensemble Learning: An Empirical Study., ICML, 2000.
• [17] Frank, E., Witten, I. H.: Generating Accurate Rule Sets Without Global Optimization., ICML, 1998.
• [18] Grzymala-Busse, J. W.: Knowledge Acquisition under Uncertainty: A Rough Set Approach., Journal of Intelligence and Robotic System., 1(1), 1988, 3-36.
• [19] Grzymala-Busse, J. W.: LERS: a system of knowledge discovery based on rough sets., Proceedings of the 5th International Workshop RSFD'96, 1996, 443-444.
• [20] Grzymala-Busse, J. W.: LERS - A Data Mining System., in: The Data Mining and Knowledge Discovery Handbook, 2005, 1347-1351.
• [21] Hu, X.: knowledge discovery in database: an attribute-oriented rough set approach., issertation, Regina, 1995.
• [22] Hu, X., Cercone, N.: Mining Knowledge Rules from Databases: A Rough Set Approach., ICDE, 1996.
• [23] Hu, X., Cercone, N.: Learning Maximal Generalized Decision Rules via Discretization, Generalization, and Rough Set Feature Selection., ICTAI, 1997.
• [24] Hu, X., Cercone, N., Han, J.: An Attribute-Oriented Rough Set Approach for Knowledge Discovery in Databases., RSKD, 1993.
• [25] Jelonek, J., Krawiec, K., Słowiński, R.: Rough Set Reduction of Attributes and their Domains for Neural Networks., Computational Intelligence, 11, 1995, 339-347.
• [26] Jensen, R., Shen, Q.: Semantics-Preserving Dimensionality Reduction: Rough and Fuzzy-Rough-Based Approaches., IEEE Trans. Knowl. Data Eng., 16(12), 2004, 1457-1471.
• [27] Kalles, D., Morris, T.: Efficient Incremental Induction of Decision Trees., Machine Learning, 24(3), 1996, 231-242.
• [28] Kira, K., Rendell, L. A.: The Feature Selection Problem: Traditional Methods and a New Algorithm., AAAI, 1992.
• [29] Lin, T. Y., Yin, P.: Heuristically Fast Finding of the Shortest Reducts., Rough Sets and Current Trends in Computing, 2004,465-470.
• [30] Lovell, B. C, Bradley, A. P.: The Multiscale Classifier., IEEE Trans. Pattern Anal. Mach. Intell, 18(2), 1996, 124-137.
• [31] Mollestad, T., Skowron, A.: A Rough Set Framework for Data Mining of Propositional Default Rules., ISMIS, 1996.
• [32] Pal, S. K., Mitra, S., Mitra, P.: Rough-Fuzzy MLP: Modular Evolution, Rule Generation, and Evaluation., IEEE Trans. Knowl. Data Eng., 15(1), 2003, 14-25.
• [33] Pawlak, Z.: Rough sets., International Journal of Computer and Information Science., 11(5), 1982, 341-356.
• [34] Pawlak, Z.: Rough Sets: theoretical aspects and reasoning about data., Kluwer Academic Publishers, 1991.
• [35] Pawlak, Z., Grzymala-Busse, J. W., Słowiński, R., Ziarko, W.: Rough Sets., Commun. ACM, 38(11), 1995, 88-95.
• [36] Riickert, U., Kramer, S.: Towards tight bounds for rule learning., ICML, 2004.
• [37] Schlimmer, J. C, Fisher, D. H.: A Case Study of Incremental Concept Induction., AAAI, 1986.
• [38] Shan, N., Hamilton, H. J., Cercone, N.: Induction of Classification Rules from Imperfect Data., ISMIS, 1996.
• [39] Shan, N., Ziarko, W.: An Incremental Learning Algorithm for Constructing Decision Rules., Rough Sets, Fuzzy Sets and Knowledge Discovery, Springer-Verlag, 1993, 326-334.
• [40] Skowron, A.: Boolean Reasoning for Decision Rules Generation., ISMIS, 1993.
• [41] Skowron, A., Rauszer, C: The discernibility matrices and functions in information systems., in: R. Słowiński (Ed.), Intelligent Decision Support: Handbook of Applications and Advances to Rough Sets Theory, Kluwer Academic Publisher, Dordrecht, 1992, 331-362.
• [42] Słowiński, R., Vanderpooten, D.: A Generalized Definition of Rough Approximations Based on Similarity., IEEE Trans. Knowl. Data Eng., 12(2), 2000, 331-336.
• [43] Srikant, R.: Quest synthetic data generation code, San Jose: IBM Almaden Research Center
• [44] Swiniarski, R. W., Skowron, A.: Rough set methods in feature selection and recognition., Pattern Recognition Letters, 24(6), 2003, 833-849.
• [45] Utgoff, P. E.: Incremental Induction of Decision Trees., Machine Learning, 4, 1989,161-186.
• [46] Utgoff, P. E., Berkman, N. C, Clouse, J. A.: Decision Tree Induction Based on Efficient Tree Restructuring., Machine Learning, 29(1), 1997, 5-44.
• [47] Yasdi, R.: Learning Classification Rules from Database in the Context of Knowledge Acquisition and Representation., IEEE Trans. Knowl. Data Eng., 3(3), 1991,293-306.
• [48] Zhong, N., Dong, J., Ohsuga, S.: Using Rough Sets with Heuristics for Feature Selection., J. Intell. Inf. Syst, 16(3),2001,199-214.
• [49] Ziarko, W., Cercone, N., Hu, X.: Rule Discovery from Databases with Decision Matrices., ISMIS, 1996