On attribute reduction in concept lattices: Experimental evaluation shows discernibility matrix based methods inefficient

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F18%3A73588203" target="_blank" >RIV/61989592:15310/18:73588203 - isvavai.cz</a>
Result on the web
<a href="https://www.sciencedirect.com/science/article/pii/S0020025518306091" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0020025518306091</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ins.2018.08.004" target="_blank" >10.1016/j.ins.2018.08.004</a>

Result language
angličtina
Original language name
On attribute reduction in concept lattices: Experimental evaluation shows discernibility matrix based methods inefficient
Original language description
In recent years, discernibility matrix based methods of attribute reduction in concept lattices (DM-methods) enjoyed an increase in attention and were applied in many extensions of formal concept analysis. In our previous paper, we pointed out that there exists an older method (CR-method) with theoretically lesser time complexity and we proposed a wrapping procedure to use the CR-method in any extension where the DM-methods are used. Now we evaluate the methods experimentally. Results of the evaluation assert our previous theoretical findings that the CR-method is strictly superior as it outperforms the DM-methods by several order of magnitude. To emphasize the poor performance of the DM-methods we introduce a new naive and deliberately slow algorithm called SIMPEL. Subsequently, we show that even its performance is not so bad in comparison with the DM-methods. Our conclusions are that it is inefficient to use the DM-methods for attribute reduction in concept lattices and that the CR-method should be used instead in practice.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)