A logic method for efficient reduction of the space complexity of the attribute reduction problem
Küçük Resim Yok
Tarih
2011
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
TUBITAK SCIENTIFIC & TECHNICAL RESEARCH COUNCIL TURKEY
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
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)(n/2)) 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)(n/2)) x 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 x ((n)(n/2)) 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.
Açıklama
Anahtar Kelimeler
Information system, dataset, attribute reduction, feature selection, discernibility function, computational complexity, reduct
Kaynak
TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES
WoS Q Değeri
Q4
Scopus Q Değeri
Q3
Cilt
19
Sayı
4
