Greedy Algorithms for Construction of Approximate Tests for Decision Tables with Many-Valued Decisions

• Autorzy: Azad M. , Chikalov I. , Moshkov M. , Zielosko B.
• Języki publikacji: EN

Abstrakty

EN

The paper is devoted to the study of a greedy algorithm for construction of approximate tests (super-reducts). This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. We consider bounds on the precision of this algorithm relative to the cardinality of tests.

Słowa kluczowe

EN

decision table with many-valued decisions; test; reduct; greedy algorithm; set cover problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 120, nr 3/4
• Strony: 231--242
• Opis fizyczny: Bibliogr. 10 poz., tab., wykr.

Twórcy

autor

Azad M.

autor

Chikalov I.

autor

Moshkov M.

autor

Zielosko B.

• Mathematical and Computer Sciences & Engineering Division King Abdullah University of Science and Technology Thuwal 23955-6900, Saudi Arabia,

Bibliografia

• [1] Cheriyan, J., Ravi, R.: Lecture Notes on Approximation Algorithms for Network Problems, http://www.math.uwaterloo.ca/~jcheriya/lecnotes.html, 1998.
• [2] Frank, A., Asuncion, A.: UCI Machine Learning Repository, http://archive.ics.uci.edu/ml
• [3] Nguyen, H.S., Ślęzak, D.: Approximate reducts and association rules - correspondence and complexity results, in: Proc. 7th Int. Workshop New Directions in Rough Sets, Data Mining, and Granular-Soft Computing, RSFDGrC '99 (N. Zhong, A. Skowron, S. Ohsuga, Eds.), LNCS 1711, Springer, Heidelberg, 1999, 137-145.
• [4] Moshkov, M., Piliszczuk, M., Zielosko, B.: Partial Covers, Reducts and Decision Rules in Rough Sets: Theory and Applications, Studies in Computational Intelligence, vol. 145, Springer, Heidelberg, 2008.
• [5] Moshkov, M., Zielosko, B.: Combinatorial Machine Learning: A Rough Set Approach, Studies in Computational Intelligence, vol. 360, Springer, Heidelberg, 2011.
• [6] Moshkov, M., Zielosko, B.: Construction of tests for tables with many-valued decisions, in: Proc. 20th Int. Workshop Concurrency, Specification and Programming, CS&P 2011, September 28-30, Pułtusk, Poland (M. Szczuka, L. Czaja, A. Skowron, M. Kacprzak, Eds.), Białystok University of Technology, 2011, 376-384.
• [7] Pawlak, Z.: Rough Sets - Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.
• [8] Pawlak, Z., Skowron, A.: Rudiments of rough sets, Information Sciences, 177(1), 2007, 3-27; Rough sets: Some extensions, Information Sciences, 177(1), 2007, 28-40; Rough sets and boolean reasoning, Information Sciences, 177(1), 2007, 41-73.
• [9] Skowron, A., Rauszer, C.: The discernibility matrices and functions in information systems, in: Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory (R. Słowiński, Ed.), Kluwer Academic Publishers, Dordrecht, 1992, 331-362.
• [10] Ślęzak, D.: Approximate entropy reducts, Fundamenta Informaticae, 53, 2002, 365-390.