Paper Info
Title
On attribute reduction in concept lattices: Experimental evaluation shows discernibility matrix based methods inefficient.
Abstract
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 naïve 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.
Year
DOI
Venue
2018
10.1016/j.ins.2018.08.004
Information Sciences
Keywords
Field
DocType
Experimental evaluation,Formal concept analysis,Reduction in concept lattice,Discernibility matrix
Lattice (order),Existential quantification,Matrix (mathematics),Wrapping procedure,Theoretical computer science,Artificial intelligence,Time complexity,Order of magnitude,Formal concept analysis,Mathematics,Machine learning
Journal
Volume
ISSN
Citations 
467
0020-0255
1
PageRank 
References 
Authors
0.35
12
2
Name
Order
Citations
PageRank
Jan Konecny111517.20
Petr Krajca2809.47