The logic transformations for reducing the complexity of the discernibility function-based attribute reduction problem
Küçük Resim Yok
Tarih
2016
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Springer London Ltd
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
The basic solution for locating an optimal reduct is to generate all possible reducts and select the one that best meets the given criterion. Since this problem is NP-hard, most attribute reduction algorithms use heuristics to find a single reduct with the risk to overlook for the best ones. There is a discernibility function (DF)-based approach that generates all reducts but may fail due to memory overflows even for datasets with dimensionality much below the medium. In this study, we show that the main shortcoming of this approach is its excessively high space complexity. To overcome this, we first represent a DF of attributes by a bit-matrix (BM). Second, we partition the BM into no more than sub-BMs (SBMs). Third, we convert each SBM into a subset of reducts by preventing the generation of redundant products, and finally, we unite the subsets into a complete set of reducts. Among the SBMs of a BM, the most complex one is the first SBM with a space complexity not greater than the square root of that of the original BM. The proposed algorithm converts such a SBM with attributes into the subset of reducts with the worst case space complexity of .
Açıklama
Anahtar Kelimeler
Attribute Reduction, Bit-Matrix Partitioning, Cnf To Dnf Conversion, Computational Complexity, Discernibility Function, Set Cover
Kaynak
Knowledge And Information Systems
WoS Q Değeri
Q2
Scopus Q Değeri
Q2
Cilt
46
Sayı
3
