Fast algorithms for implication bases and attribute exploration using proper premises

Uwe RysselUwe Ryssel, Felix DistelFelix Distel, Daniel BorchmannDaniel Borchmann

Download

Uwe Ryssel, Felix Distel, Daniel Borchmann
Fast algorithms for implication bases and attribute exploration using proper premises
Annals of Mathematics and Artificial Intelligence, Special Issue 65:1-29, 2013

Details
Bibtex

KurzfassungAbstract
A central task in formal concept analysis is the enumeration of a small base for the implications that hold in a formal context. The usual stem base algorithms have been proven to be costly in terms of runtime. Proper premises are an alternative to the stem base. We present a new algorithm for the fast computation of proper premises. It is based on a known link between proper premises and minimal hypergraph transversals. Two further improvements are made, which reduce the number of proper premises that are obtained multiple times and redundancies within the set of proper premises. We have evaluated our algorithms within an application related to refactoring of model variants. In this application an implicational base needs to be computed, and runtime is more crucial than minimal cardinality. In addition to the empirical tests, we provide heuristic evidence that an approach based on proper premises will also be beneficial for other applications. Finally, we show how our algorithms can be extended to an exploration algorithm that is based on proper premises.
Projekt:Project: HAEC B02, QuantLA
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@article{ RyDiBo-AMAI13,
  author = {Uwe {Ryssel} and Felix {Distel} and Daniel {Borchmann}},
  journal = {Annals of Mathematics and Artificial Intelligence},
  pages = {1--29},
  publisher = {Springer Netherlands},
  title = {Fast algorithms for implication bases and attribute exploration using proper premises},
  volume = {Special Issue 65},
  year = {2013},
}