Formal Concept Analysis (FCA) is one of the major formats for knowledge extraction, reduction, representation and analysis. FCA is formulated based on a formal context represented by a binary relation between a set of objects and a set of attributes. Formal concept lattice is the core of the mathematical theory of FCA.
Applying FCA methods to large formal contexts could bring many challenges, because the algorithm to extract formal concepts can have an exponential complexity in the worst case. Hence, the determination problem has been widely discussed in many scientific works ever since, which leads to the development of many efficient algorithms. In general, these algorithms can be divided into two categories, i.e. batch algorithms and incremental algorithms. Batch algorithms usually construct the lattice in a bottom-up (or top-down) approach, while incremental algorithms compute the lattice by adding objects (or attributes) to a given context one by one.
Among all types of lattice construction algorithms, incremental algorithms have a unique advantage. The input formal context may not be fixed in a realistic application of FCA, which means the present lattice has to be updated or a new lattice should be computed from scratch. Obviously, computing the corresponding changes only and updating the current lattice should be a better choice, which can be handled by incremental algorithms.
Generating all extents of the generalized one-sided concept lattice by the incremental algorithm is usually based on the operation of Galois connection, and the operation needs to scan the formal context. This becomes a significant computing overhead, especially when the formal context is large.
With respect to the description problem, the researcher who formulated FCA mentioned that the most communicative description is given by Hasse diagrams. However, it is difficult to autonomously understand the hierarchy of the concepts from Hasse diagrams for any information retrieval software. Thus, Pak Chol Hong, a researcher at the Faculty of Applied Mathematics, has proposed methods of describing the hierarchy of a concept lattice by using a hierarchy-matrix, estimating the connectivity of concepts by the hierarchy-matrix and describing the Hasse diagram via a hierarchy-matrix.
If there is a method of determining the generalized one-sided concept lattice and describing its Hierarchy-matrix sequentially, the more useful software with autonomous intelligence, which is based on FCA from the generalized one-sided formal context, can be built. On this basis, he has presented a new efficient incremental algorithm that performs the operation of Galois connection for determining the generalized one-sided concept lattice only once and describes its hierarchy-matrix sequentially. In addition, he has evaluated the feature and effectiveness of the proposed algorithms.
...