An Efficient Method to Reduce the Size of Consistent Decision Tables

János Demetrovics; Hoang Minh Quang; Vu Duc Thi; Nguyen Viet Anh

doi:10.14232/actacyb.23.4.2018.4

János Demetrovics Computer and Automation Institute Hungarian Academy of Sciences
Hoang Minh Quang Institute of Information Technology, Vietnam Academy of Science and Technology https://orcid.org/0000-0003-3581-1041
Vu Duc Thi The Information Technology Institute (ITI), Vietnam National University, Hanoi https://orcid.org/0000-0003-0567-2570
Nguyen Viet Anh Institute of Information Technology, Vietnam Academy of Science and Technology https://orcid.org/0000-0001-7736-2470

DOI: https://doi.org/10.14232/actacyb.23.4.2018.4

Keywords: attribute reduct, object reduct, consistent decision table, rough set theory, relational database theory

Abstract

Finding reductions from decision tables is one of the main objectives in information processing. Many studies focus on attribute reduct that reduces the number of columns in the decision table. The problem of finding all attribute reducts of consistent decision table is exponential in the number of attributes. In this paper, we aim at finding solutions for the problem of decision table reduction in polynomial time. More specifically, we deal with both the object reduct problem and the attribute reduct problem in consistent decision tables. We proved theoretically that our proposed methods for the two problems run in polynomial time. The proposed methods can be combined to significantly reduce the size of a consistent decision table both horizontally and vertically.

Downloads

Download data is not yet available.