Abstract
Most decision support systems based on rough set theory are related to the minimal reduct calculation problem, which is NP-hard. This paper investigates the problem of searching for the set of useful attributes that occur in at least one reduct. By complement, this problem is equivalent to searching for the set of redundant attributes, i.e. the attributes that do not occur in any reducts of the given decision table. We show that the considered problem is equivalent to a Sperner system for relational data base system and prove that it can be solved in polynomial time. On the base of these theoretical results, we also propose two different algorithms for elimination of redundant attributes in decision tables.
L.G. Nguyen—This work is partially supported by the Vietnam’s National Foundation for Science and Technology Development (NAFOSTED) via a research grant for fundamental sciences, grant number 102.01-2010.09 and Polish National Science Centre grant DEC-2012/05/B/ST6/03215.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The UCI machine learning repository, http://archive.ics.uci.edu/ml/.
References
Pawlak, Z.: Rough Sets-Theoretical Aspect of Reasoning About Data. Kluwer Academic Publishers, Norwell (1991)
Demetrovics, J., Thi, V.D.: Keys, antikeys and prime attributes. Ann. Univ. Sci. Bp. Sect. Comp. 8, 35–52 (1987)
Demetrovics, J., Thi, V.D.: Describing candidate keys by hypergraphs. Comput. Artif. Intell. 18(2), 191–207 (1999)
Nguyen, L.G., Nguyen, H.S.: On elimination of redundant attributes in decision tables. In: 2012 Federated Conference on Computer Science and Information Systems (FedCSIS). IEEE, pp. 317–322 (2012)
Pawlak, Z.: Rough sets. Int. J. Comput. Inf. Sci. 11(5), 341–356 (1982)
Nguyen, H.S.: Approximate boolean reasoning: foundations and applications in data mining. In: Peters, J.F., Skowron, A. (eds.) Transactions on Rough Sets V. LNCS, vol. 4100, pp. 334–506. Springer, Heidelberg (2006)
Pawlak, Z.: Rough sets and intelligent data analysis. Inf. Sci. 147(1), 1–12 (2002)
Skowron, A., Rauszer, C.: The discernibility matrices and functions in information systems. In: Słoński, R. (ed.) Intelligent Decision Support, vol. 11, pp. 331–362. Springer, Heidelberg (1992)
Wei, L., Li, H.R., Zhang, W.X.: Knowledge reduction based on the equivalence relations defined on attribute set and its power set. Inf. Sci. 177(15), 3178–3185 (2007)
Yao, Y.: Duality in rough set theory based on the square of opposition. Fundam. Inf. 127(1–4), 49–64 (2013)
Moshkov, M.J., Skowron, A., Suraj, Z.: On covering attribute sets by reducts. In: Kryszkiewicz, M., Peters, J.F., Rybiński, H., Skowron, A. (eds.) RSEISP 2007. LNCS (LNAI), vol. 4585, pp. 175–180. Springer, Heidelberg (2007)
Thi, V.D., Son, N.H.: On armstrong relations for strong dependencies. Acta Cybernetica 17(3), 521–531 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Nguyen, L.G., Nguyen, H.S. (2015). Searching for Reductive Attributes in Decision Tables. In: Peters, J., Skowron, A., Ślȩzak, D., Nguyen, H., Bazan, J. (eds) Transactions on Rough Sets XIX. Lecture Notes in Computer Science(), vol 8988. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47815-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-662-47815-8_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47814-1
Online ISBN: 978-3-662-47815-8
eBook Packages: Computer ScienceComputer Science (R0)