Efficient Incremental Algorithm for Building Swiftly Concepts Lattices

Efficient Incremental Algorithm for Building Swiftly Concepts Lattices

Bakhta Amrane, Ghalem Belalem, Sarra Branci, Yahya Slimani
Copyright: © 2014 |Pages: 14
DOI: 10.4018/ijwp.2014010102
(Individual Articles)
No Current Special Offers


Efficient tool and platform for several areas, concept lattice are widely used in many fields of research. Dynamic environment requires an incremental algorithm to build formal concepts. It plays an essential role in the application of concept lattice. This paper presents a fast, efficient, incremental algorithm to compute formal concepts. Algorithmic complexity is studied both theoretically (in the worst case) and experimentally. It presents a complexity of at most (|M|.|G|.|L|) where M is set of attributes, G is set of objects and L is set of concepts of the lattice. Irrespective of the lattice, the algorithm computes incrementally all formal concepts without increasing time complexity. Algorithmic complexity of the most important incremental algorithms is compared theoretically, and an experimental study based on density/ sparseness of underlying formal contexts is performed with Norris' algorithm classified the most one efficient incremental in practice.
Article Preview

1. Preliminary

Several approaches (Bendaoud et al., 2008; Huchard et al., 2007) showed how powerful is Formal Concept Analysis (FCA) for data analysis and information extraction (Chang-sheng et al., 2013) and the lattice is usually considered as the knowledge model (Thao Tang et al., 2013). Introduced by Barbut and Monjardet (Barbut et al., 1970) and defined as a mathematical classification, the approach was popularized by Wille who used the notion of Galois lattices as a basis for Formal Concept Analysis (Wille, 1982). This method allows the discovery of possible combinations of elements, organized hierarchically, with characteristics in common. It proved to be a useful tool in many applied domains: knowledge discovery (Chekol et al., 2013), (Kumar, 2011), (Pfaltz et al., 2002), data mining (Hamrouni et al., 2011), information retrieval (Sakji et al., 2008), web services (Aversano et al., 2006; Azmeh, 2011; Chen, 2008), robotics (Zenou et al., 2004), etc.

The construction of concept lattice of a given binary relation can be made by:

  • 1.

    The list of formal concepts;

  • 2.

    The search for partial order relation between concepts;

  • 3.

    The graphical representation of the lattice (construction of the Hasse diagram corresponding to the lattice).

The first two points are the calculation problem of a lattice of concepts from a formal context and can be performed simultaneously or sequentially. The third point is a problem of graph visualization. Treated independently, these two problems gave rise to two complementary lines of research: The first is to propose algorithms more efficient (complexity, execution time, memory usage, scalability) for the construction of concept lattice and the second is to provide effective tools for the visualization of these lattices (Ben Tekaya et al., 2005).

Depending on the strategy for acquiring data from a set of instances of objects and properties (the formal context), there are three families of lattice construction algorithms:

  • The batch algorithms that consider the entire formal context from the start;

  • The incremental algorithms that consider an instance (object or property) one at the time;

  • The assembly algorithms that divide the context in two, calculate concepts corresponding to each part and then assemble.

The incremental algorithms allow management contexts where the number of objects and / or properties may change without having to recalculate the trellis from scratch following a modification of the formal context. The problem of generating the set of all concepts and the concept lattice of a formal context is extensively studied in literature. It is known that the number of concepts can be exponential in the size of the input context.

Complete Article List

Search this Journal:
Volume 15: 1 Issue (2024): Forthcoming, Available for Pre-Order
Volume 14: 2 Issues (2022): 1 Released, 1 Forthcoming
Volume 13: 2 Issues (2021)
Volume 12: 2 Issues (2020)
Volume 11: 2 Issues (2019)
Volume 10: 2 Issues (2018)
Volume 9: 2 Issues (2017)
Volume 8: 1 Issue (2016)
Volume 7: 2 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing