Optimizations in computing the Duquenne–Guigues basis of implications

Annals of Mathematics and Artificial Intelligence. 2014. Vol. 70. No. 1-2. P. 5–24.

Konstantin Bazhanov, Obiedkov S.

In this paper, we consider algorithms involved in the computation of the Duquenne–Guigues basis of implications. The most widely used algorithm for constructing the basis is Ganter’s Next Closure, designed for generating closed sets of an arbitrary closure system. We show that, for the purpose of generating the basis, the algorithm can be optimized. We compare the performance of the original algorithm and its optimized version in a series of experiments using artificially generated and real-life datasets. An important computationally expensive subroutine of the algorithm generates the closure of an attribute set with respect to a set of implications. We compare the performance of three algorithms for this task on their own, as well as in conjunction with each of the two algorithms for generating the basis. We also discuss other approaches to constructing the Duquenne–Guigues basis.

Keywords: algorithms, formal concept analysis, алгоритмы, implications, LinClosure, Horn formulae, Duquenne–Guigues basis, импликации, Хорновские формулы, базис Дюкенна–Гига, формальный анализ понятий, LinClosure

Publication based on the results of: Mathematical Models, Algorithms, and Software Tools for the Intelligent Analysis of Big Textual and Structural Data (2013)