GALOIS: An Order-Theoretic Approach to Conceptual Clustering

Abstract

The theory of concept (or Galois) lattices provides a natural and formal setting in which to discover and represent concept hierarchies. In this paper we present a system, GALOIS, which is able to determine the concept lattice corresponding to a given set of objects. GALOIS is incremental and relatively efficient, the time complexity of each update ranging from O(n) to O(n2) where n is the number of concepts in the lattice. Unlike most approaches to conceptual clustering, GALOIS represents and updates all possible classes in a restricted concept space. Therefore the concept hierarchies it finds are always justified and are not sensitive to object ordering. We experimentally demonstrate, using several machine learning data sets, that GALOIS can be successfully used for class discovery and class prediction. We also point out applications of GALOIS in fields related to machine learning (i.e., information retrieval and databases).