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, Объедков С. А.

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.

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

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Математические модели, алгоритмы и программные средства интеллектуального анализа больших данных (Big Data) в текстовой и структурной форме (2013)