Paper Info
Title
Yet a Faster Algorithm for Building the Hasse Diagram of a Concept Lattice
Abstract
Formal concept analysis (FCA) is increasingly applied to data mining problems, essentially as a formal framework for mining reduced representations (bases) of target pattern families. Yet most of the FCA-based miners, closed pattern miners, would only extract the patterns themselves out of a dataset, whereas the generality order among patterns would be required for many bases. As a contribution to the topic of the (precedence) order computation on top of the set of closed patterns, we present a novel method that borrows its overall incremental approach from two algorithms in the literature. The claimed innovation consists of splitting the update of the precedence links into a large number of lower-cover list computations (as opposed to a single upper-cover list computation) that unfold simultaneously. The resulting method shows a good improvement with respect to its counterpart both on its theoretical complexity and on its practical performance. It is therefore a good starting point for the design of efficient and scalable precedence miners.
Year
DOI
Venue
2009
10.1007/978-3-642-01815-2_13
ICFCA
Keywords
Field
DocType
lower-cover list computation,closed pattern,faster algorithm,closed pattern miner,good improvement,hasse diagram,scalable precedence miner,concept lattice,formal concept analysis,generality order,data mining problem,precedence link,formal framework,data mining
Discrete mathematics,Combinatorics,Closed pattern,Lattice (order),Computer science,Hasse diagram,Algorithm,Formal concept analysis,Generality,Scalability,Computation
Conference
Volume
ISSN
Citations 
5548
0302-9743
11
PageRank 
References 
Authors
0.65
12
4
Name
Order
Citations
PageRank
Jaume Baixeries19912.57
Laszlo Szathmary21019.63
Petko Valtchev390272.38
Robert Godin4956.47