The logic transformations for reducing the complexity of the discernibility function-based attribute reduction problem

Basit Öğe Kaydı
dc.contributor.authorHacibeyoglu, Mehmet
dc.contributor.authorSalman, Mohammad Shukri
dc.contributor.authorSelek, Murat
dc.contributor.authorKahramanli, Sirzat
dc.date.accessioned2024-02-23T13:55:57Z
dc.date.available2024-02-23T13:55:57Z
dc.date.issued2016
dc.departmentNEÜen_US
dc.description.abstractThe 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 .en_US
dc.identifier.doi10.1007/s10115-015-0824-9
dc.identifier.endpage628en_US
dc.identifier.issn0219-1377
dc.identifier.issn0219-3116
dc.identifier.issue3en_US
dc.identifier.scopus2-s2.0-84958107938en_US
dc.identifier.scopusqualityQ2en_US
dc.identifier.startpage599en_US
dc.identifier.urihttps://doi.org/10.1007/s10115-015-0824-9
dc.identifier.urihttps://hdl.handle.net/20.500.12452/11036
dc.identifier.volume46en_US
dc.identifier.wosWOS:000369911800005en_US
dc.identifier.wosqualityQ2en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.publisherSpringer London Ltden_US
dc.relation.ispartofKnowledge And Information Systemsen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectAttribute Reductionen_US
dc.subjectBit-Matrix Partitioningen_US
dc.subjectCnf To Dnf Conversionen_US
dc.subjectComputational Complexityen_US
dc.subjectDiscernibility Functionen_US
dc.subjectSet Coveren_US
dc.titleThe logic transformations for reducing the complexity of the discernibility function-based attribute reduction problemen_US
dc.typeArticleen_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu