INCREMENTAL CONCEPT FORMATION ALGORITHMS BASED ON GALOIS (CONCEPT) LATTICES

TLDR

The Galois (concept) lattice derived from a binary relation serves as a versatile tool for many applications and functions as a conceptual clustering method that yields a concept hierarchy. This work introduces incremental algorithms for updating the Galois lattice and its associated graph, thereby enabling incremental concept formation. The authors explore several update strategies based on characterizing the required modifications and evaluate them empirically against three batch algorithms. Empirical results show that the simplest incremental variant outperforms batch algorithms when total time is considered, and all incremental variants outperform batch algorithms when only update time is counted, with update time scaling linearly with the number of previously processed instances despite an exponential worst‑case bound that remains linear under a fixed feature‑size assumption.

Abstract

The Galois (or concept) lattice produced from a binary relation has proved useful for many applications. Building the Galois lattice can be considered a conceptual clustering method because it results in a concept hierarchy. This article presents incremental algorithms for updating the Galois lattice and corresponding graph, resulting in an incremental concept formation method. Different strategies are considered based on a characterization of the modifications implied by such an update. Results of empirical tests are given in order to compare the performance of the incremental algorithms to three other batch algorithms. Surprisingly, when the total time for incremental generation is used, the simplest and less efficient variant of the incremental algorithms outperforms the batch algorithms in most cases. When only the incremental update time is used, the incremental algorithm outperforms all the batch algorithms. Empirical evidence shows that, on the average, the incremental update is done in time proportional to the number of instances previously treated. Although the worst case is exponential, when there is a fixed upper bound on the number of features related to an instance, which is usually the case in practical applications, the worst‐case analysis of the algorithm also shows linear growth with respect to the number of instances.