Article Preview
Top1. 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.