Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes

• Autorzy: Ostonov Azimkhon , Moshkov Mikhail

Identyfikatory

DOI

10.15439/2024F8221

• Konferencja: Federated Conference on Computer Science and Information Systems (19 ; 08-11.09.2024 ; Belgrade, Serbia)
• Języki publikacji: EN

Abstrakty

EN

In this research paper, we examine classes of decision tables that are closed under attribute (column) removal and changing of decisions associated with rows. For decision tables belonging to these closed classes, we investigate lower bounds on the minimum cardinality of reducts. Reducts are minimal sets of attributes that allow us to determine the decision attached to a given row. We assume that the number of rows in the decision tables from the closed class is not limited by a constant. We divide the set of these closed classes into two families. In one family, the minimum cardinality of reducts for decision tables is bounded by standard lower bounds of the forms Ω(log cl(Τ), where cl(Τ) represents the number of decision classes in the table Τ. In the other family, these lower bounds can be significantly tightened to the form Ω(cl(Τ) 1/q) for some natural number q.

Słowa kluczowe

EN

lower bound; reductant; decision table; information system

PL

dolna granica; redukcja; tabele decyzyjne; system informacyjny

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2024
• Tom: Vol. 39
• Strony: 667--670
• Opis fizyczny: Bibliogr. 14 poz., wz.

Twórcy

autor

Ostonov Azimkhon

• King Abdullah University of Science and Technology (KAUST) Thuwal 23955-6900, Saudi Arabia

• https://orcid.org/0000-0001-5763-9751

autor

Moshkov Mikhail

• King Abdullah University of Science and Technology (KAUST) Thuwal 23955-6900, Saudi Arabia

• https://orcid.org/0000-0003-0085-9483

Bibliografia

• 1. E. Boros, P. L. Hammer, T. Ibaraki, and A. Kogan, “Logical analysis of numerical data,” Math. Program., vol. 79, pp. 163–190, 1997.
• 2. I. Chikalov, V. V. Lozin, I. Lozina, M. Moshkov, H. S. Nguyen, A. Skowron, and B. Zielosko, Three Approaches to Data Analysis - Test Theory, Rough Sets and Logical Analysis of Data, ser. Intelligent Systems Reference Library. Springer, 2013, vol. 41.
• 3. J. Fürnkranz, D. Gamberger, and N. Lavrac, Foundations of Rule Learning, ser. Cognitive Technologies. Springer, 2012.
• 4. E. Humby, Programs from Decision Tables, ser. Computer Monographs. Macdonald, London and American Elsevier, New York, 1973, vol. 19.
• 5. M. Moshkov, “Time complexity of decision trees,” in Trans. Rough Sets III, ser. Lecture Notes in Computer Science, J. F. Peters and A. Skowron, Eds., Springer, 2005, vol. 3400, pp. 244–459.
• 6. M. Moshkov and B. Zielosko, Combinatorial Machine Learning - A Rough Set Approach, ser. Studies in Computational Intelligence. Springer, 2011, vol. 360.
• 7. Z. Pawlak, Rough Sets - Theoretical Aspects of Reasoning about Data, ser. Theory and Decision Library: Series D. Kluwer, 1991, vol. 9.
• 8. S. L. Pollack, H. T. Hicks, and W. J. Harrison, Decision Tables: Theory and Practice. John Wiley & Sons, 1971.
• 9. L. Rokach and O. Maimon, Data Mining with Decision Trees - Theory and Applications, ser. Series in Machine Perception and Artificial Intelligence. World Scientific, 2007, vol. 69.
• 10. Z. Pawlak and A. Skowron, “Rudiments of rough sets,” Inf. Sci., vol. 177, no. 1, pp. 3–27, 2007.
• 11. D. Slezak, “Approximate entropy reducts,” Fundam. Informaticae, vol. 53, no. 3-4, pp. 365–390, 2002.
• 12. S. Stawicki, D. Slezak, A. Janusz, and S. Widz, “Decision bireducts and decision reducts - a comparison,” Int. J. Approx. Reason., vol. 84, pp. 75–109, 2017.
• 13. A. Janusz and S. Stawicki, “Reducts in rough sets: Algorithmic insights, open source libraries and applications (tutorial – extended abstract),” in Proceedings of the 18th Conference on Computer Science and Intelligence Systems, ser. Annals of Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, and D. Ślęzak, Eds., vol. 35. IEEE, 2023. http://dx.doi.org/10.15439/2023F0002 p. 71–71. [Online]. Available: http://dx.doi.org/10.15439/2023F0002
• 14. B. K. Vo and H. S. Nguyen, “Feature selection and ranking method based on intuitionistic fuzzy matrix and rough sets,” in Proceedings of the 17th Conference on Computer Science and Intelligence Systems, ser. Annals of Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, and D. Ślęzak, Eds., vol. 30. IEEE, 2022. http://dx.doi.org/10.15439/2022F261 p. 279–288. [Online]. Available: http://dx.doi.org/10.15439/2022F261

Uwagi

1. Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST).

2. Thematic Sessions: Short Papers