Physical Sciences and Mathematics Commons^™

A Logic Method For Efficient Reduction Of The Space Complexity Of The Attribute Reduction Problem, Mehmet Hacibeyoğlu, Fati̇h Başçi̇ftçi̇, Şi̇rzat Kahramanli

Turkish Journal of Electrical Engineering and Computer Sciences

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/2}^n) 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 …