- Turkish Journal of Electrical Engineering and Computer Science
- Vol: 19 Issue: 4
- A logic method for efficient reduction of the space complexity of the attribute reduction problem
A logic method for efficient reduction of the space complexity of the attribute reduction problem
Authors : Mehmet Hacibeyoğlu, Fatih Başçiftçi, Şirzat Kahramanli
Pages : 643-656
View : 8 | Download : 4
Publication Date : 9999-12-31
Article Type : Makaleler
Abstract :The goal of attribute reduction is to find a minimal subset (MS) R of the condition attribute set C of a dataset such that R has the same classification power as C. It was proved that the number of MSs for a dataset with n attributes may be as large as (n/2n) and the generation of all of them is an NP-hard problem. The main reason for this is the intractable space complexity of the conversion of the discernibility function (DF) of a dataset to the disjunctive normal form (DNF). Our analysis of many DF-to-DNF conversion processes showed that approximately (1-2/(n/2n) \times 100)% of the implicants generated in the DF-to-DNF process are redundant ones. We prevented their generation based on the Boolean inverse distribution law. Due to this property, the proposed method generates 0.5 \times (n/2n) times fewer implicants than other Boolean logic-based attribute reduction methods. Hence, it can process most of the datasets that cannot be processed by other attribute reduction methods.Keywords : Information system, dataset, attribute reduction, feature selection, discernibility function, computational complexity, reduct