Research And Implementation Of A Fast Algorithm For Generating Concept Lattice

Formal concept analysis, elaborated by Wille, is a very general method to analyze a binary relationship between arbitrary objects and attributes. Its output is a lattice of so-called concept lattice, which offers non-trivial insight into the structure underlying the original relationship. FCA has grown into an international research community with applications in many disciplines and still has a significant potential for applications. The main drawback to this approach is the inherent complexity of the lattice structure. So it is always very import, both theoretically and experimentally, to study out an efficient algorithm to generate concept lattice. Some researches and experiments suggest that the Godin algorithm should be used for small and sparse contexts; for dense and large contexts, the algorithm based on the canonicity test, such as NextClosure, should be used. But the experiments also tell us that NextClosure is still not efficient enough so that we make a special study with the purpose of studying out a method able to deal with large and dense data fast. First, as one of results of research, we propose a new algorithm, called TABLE, which is able to generate concepts much faster than NextClosure does in many cases. This algorithm views the space for searching concepts as a Trie (or says a prefix tree). A new data structure, called Attribute Table, is designed to help to prune the Trie layer by layer, and concepts are calculated out at the same time. Both TABLE and NextClosure were implemented in C++ in order to study practical performance of algorithms. Some "classical" (well-recognized in data analysis community) databases and three types of "randomly generated contexts" were used for the comparison, and three parameters, |G|, |M| and the number of attributes per object, were taken into account. According to the execution time of the algorithms depends on various parameters, we draw a conclusion that TABLE is probably a much better choice than NextClosure in most cases. It makes TABLE is very flexible having a Concept Index Tree instead of a concept lattice as the result. For example, the Hasse graph of a concept lattice could be easily generated and the corresponding concept lattice could be facile to be updated. Second, a parallel algorithm, called ParTable, is designed to generate...