Reducts and Constructs in Attribute Reduction

• Autorzy: Susmaga R.
• Konferencja: International Conference on Soft Computing and Distributed Processing (SCDP'2002) (June 2002, Rzeszów, Poland).
• Języki publikacji: EN

Abstrakty

EN

One of the main notions in the Rough Sets Theory (RST) is that of a reduct. According to its classic definition, the reduct is a minimal subset of the attributes that retains some important properties of the whole set of attributes. The idea of the reduct proved to be interesting enough to inspire a great deal of research and resulted in introducing various reduct-related ideas and notions. First of all, depending on the character of the attributes involved in the analysis, so called absolute and relative reducts can be defined. The more interesting of these, relative reducts, are minimal subsets of attributes that retain discernibility between objects belonging to different classes. This paper focuses on the topological aspects of such reducts, identifying some of their limitations and introducing alternative definitions that do not suffer from these limitations. The modified subsets of attributes, referred to as constructs, are intended to assist the subsequent inductive process of data generalisation and knowledge acquisition, which, in the context of RST, usually takes the form of decision rule generation. Usefulness of both reducts and constructs in this role is examined and evaluated in a massive computational experiment, which was carried out for a collection of real-life data sets.

Słowa kluczowe

EN

rough set theory; attribute reduction; indiscernibility relation; similarity relation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 61, nr 2
• Strony: 159--181
• Opis fizyczny: Bibliogr. 35 poz., tab

Twórcy

autor

Susmaga R.

• Institute of Computing Science, University of Technology, Piotrowo 3A, 60-965 Poznań, Poland,

Bibliografia

• [1] Bazan J., Skowron A., Synak P.: 'Dynamic Reducts as a Tool for Extracting Laws from Decision Tables’, Methodologies for Intelligent Systems. Proceedings of the 8th International Symposium ISMIS'94, (Ras Z. W., Zemankowa M, Eds), Charlotte, NG, LNAI 869, Springer-Verlag, 1994, 346-355.
• [2] Dash M., Liu H.: 'Feature Selection for Classification', Intelligent Data Analysis, 1(3), 1997, http://wwweast.elsevier.com/ida.
• [3] Dougherty J. Kohavi R., Sahami M.: 'Supervised and Unsupervised Discretizations of Continuous Features', Proceedings of the 12th International Conference on Machine Learning, Morgan Kaufmann Publishers, 1995, 194-202.
• [4] Jelonek J., Krawiec K., Słowiński R.: 'Rough set reduction of attributes and their domains for neural networks'. Computational Intelligence, 11(2), 1995, 339-347.
• [5] Jelonek J., Krawiec K., Stefanowski J.: 'Comparative study of feature subset selection techniques for machine learning tasks'. Intelligent Information Systems: Proceedings of a Workshop, Malbork, Poland, June 1998, 68-77.
• [6] John H. G., Kohavi R., Pfleger K.: 'Irrelevant Features and the Subset Selection Problem', Machine Learning: Proceedings of the Eleventh International Conference, (Cohen W. W., Hirsh H., Eds), Morgan Kaufmann Publishers, San Francisco, CA, 1994, 121-129.
• [7] Kohavi R., Frasca B.: 'Useful Feature Subsets and Rough Set Reducts', Proceedings of the Third International Workshop on Rough Sets and Soft Computing, San Jose State University, San Jose, CA, 1994.
• [8] Krusiriska E., Babic A., Słowiński R., Stefanowski J.: 'Comparison of the Rough Sets Approach and Probabilistic Data Analysis Techniques on a Common Set of Medical Data', Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory, (Słowiński R., Ed.), Kluwer Academic Publishers, Dordrecht, 1992,251-264.
• [9] Kryszkiewicz M., Rybiński H.: 'Finding Reducts in Composed Information Systems', Fundamenta Informaticae,2(2-3), 1996, 183-196.
• [10] Modrzejewski M.: 'Feature selection using rough sets theory'. Proceedings of the European Conference on Machine Learning, (Brazdil P. B., Ed.), 1993, 213-226.
• [11] Murphy P.M., Aha D.W.: 'UCI Repository of Machine Learning Databases', University of California, Department of Information and Computer Science, Irvine, CA, 1992, http://www.ics.uci.edu /~mleam.
• [12] Nguyen, H. S., Skowron A.: 'Quantization of Real Value Attributes. Rough Set and Boolean Reasoning Approaches', In: Proceedings of the Second Annual Joint Conference on Information Sciences, Wrightsville Beach, NC, September/October 1995, 34-37.
• [13] Nieminen J.: 'Rough Tolcrance Equality' Fundamenta lnformaticae, 11, 1988,289-296.
• [14] Orłowska M., Orlowski M.: 'Maintenance of Knowledge in Dynamic Information Systems', Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory, (Słowiński R., Ed.), Kluwer Academic Publishers, Dordrecht, 1992, 315-330.
• [15] Pawlak Z.: Rough Sets. Theoretical Aspects of Reasoning About Data, Kluwer Academic Publishers, Dordrecht, 1991.
• [16] Pawlak Z., Słowiński R.: 'Rough Set Approach to Multi-Attribute Decision Analysis', European Journal of Operational Research, 72, 1994, 443-459.
• [17] Quinlan J.R.: C4.5: Programs for Machine Learning, Morgan Kaufmann, CA, 1993.
• [18] Romanski S.: 'Operations on Families of Sets for Exhaustive Search Given a Monotonic Function', Proceedings of the 3rd International Conference on Data and Knowledge Bases, (Beeri, C, Smith, J.W., Dayal, U., Eds), Jerusalem, Israel, 1998,28-30.
• [19] Skowron A.: 'Extracting Laws from Decision Tables: A Rough Set Approach', Computational Intelligence, 11(2), 1995,371-388.
• [20] Skowron A., Rauszer C: 'The Discemibility Functions Matrices and Functions in Information Systems', Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory, (Słowiński R., Ed.), Kluwer Academic Publishers, Dordrecht, 1992, 331-362.
• [21] Skowron A., Polkowski L.: 'Decision Algorithms: A Survey of Rough Set-Theoretic Methods', Fundamenta Informaticae, 30(3-4), 1997, 345-358.
• [22] Skowron A., Stepaniuk J.: 'Tolerance Approximation Spaces', Fundamenta Informaticae, 27,1996,245-253.
• [23] Ślęzak D.: 'Searching for Frequential Reducts in Decision Tables with Uncertain Objects', Proceedings of the First International Conference on Rough Sets and Current Trends in Computing, (Polkowski L., Skowron A., Eds), Springer-Verlag, Berlin, 1998, 52-59.
• [24] Słowiński. R., Stefanowski J., Antczak A., Kwias Z.: 'Rough set approach to the verification of indications for treatment of urinary stones by extracorporeal shock wave lithotrpsy (ESWL)', (eds) Soft Computing, (Lin T. Y, Wildberg A. M., Eds), Society for Computer Simulation, San Diego, CA, 1995,93-96.
• [25] Słowiński R., Vanderpooten D.: 'A generalized definition of rough approximations based on similarity', IFFF Transactions on Data and Knowledge Engineering, 12(2), 2000, 331-336.
• [26] Stepaniuk J.: 'Similarity Based Rough Sets and Learning', Proceedings of the Fourth International Workshop on Rough Sets, Fuzzy Sets, and Machine Discovery, The University of Tokyo, Tokyo, Japan, 1996,18-22.
• [27] Stepaniuk J.: 'Approximation Spaces, Reducts and Representatives', Rought Sets in Data Mining and Knowledge Discovery, (Skowron A., Polkowski L., Eds), Springer-Verlag, Berlin, 1998.
• [28] Susmaga R.: 'Experiments in Incremental Computation of Reducts', Rough Sets in Data Mining and Knowledge Discovery, (Skowron A., Polkowski L., Eds), Springer-Verlag, Berlin, 1998.
• [29] Susmaga R.: 'Parallel Computation of Reducts', Proceedings of the First International Conference on Rough Sets and Current Trends in Computing, (Polkowski L., Skowron A., Eds), Springer-Verlag, Berlin, 1998,450-457.
• [30] Susmaga R.: 'Computation of Shortest Reducts', Foundations of Computing and Decision Sciences, 23(2), Poznań, Poland, 1998,119-137.
• [31] Susmaga R.: 'Effective Tests for Minimality in Reduct Generation', Foundations of Computing and Decision Sciences, 23(4), Poznań, Poland, 1998, 219-240.
• [32] Tannhauser M.: Efficient Reduct Computation (in Polish), M. Sc. Thesis, Institute of Mathematics, Warsaw University, Warsaw, 1994.
• [33] Wróblewski, J.: 'Finding Minimal Reducts Using Genetic Algorithms', Proceedings of the Second Annual Join Conference on Information Sciences, September/October 1995, Wrightsville Beach, NC, 1995,186-189.
• [34] Wróblewski J.: 'Covering with Reducts - A Fast Algorithm for Rule Generation', Proceedings of the First International Conference on Rough Sets and Current Trends in Computing, (Polkowski L., Skowron A., Eds), Springer-Verlag, Berlin (1998), 402-407.
• [35] Ziarko W., Shan N.: 'Data-Based Acquisition and Incremental Modification of Classification Rules', Computational Intelligence, 11(2), 1995, 357-370.