AN INCREMENTAL CONCEPT-FORMATION APPROACH FOR LEARNING FROM DATABASES

This paper describes a concept formation approach to the discovery of new concepts and implication rules from data. This machine learning ap proach is based on the Galois lattice theory, and starts from a binary relation between a set of objects and a set of properties (descriptor s) to build a concept lattice and a set of rules. Each node (concept) of the lattice represents a subset of objects with their common proper ties. In this paper, some efficient algorithms for generating concepts and rules are presented. The rules are either in conjunctive or disju nctive form. To avoid the repetitive process of constructing the conce pt lattice and determining the set of implication rules from scratch e ach time a new object is introduced in the input relation, we propose an algorithm for incrementally updating both the lattice and the set o f generated rules. The empirical behavior of the algorithms is also an alysed. The implication problem for these rules can be handled based o n the well-known theoretical results on functional dependencies in rel ational databases.