Article,
An incremental concept formation approach for learning from databases
Theoretical computer science, 133 (2): 387--419 (1994)
Abstract
Godin, R. and R. Missaoui, An incremental concept formation approach
for learning from databases, Theoretical Computer Science 133 (1994)
3533385. This paper describes a concept formation approach to the
discovery of new concepts and implication rules from data. This
machine learning approach is based on the Galois lattice theory, and
starts from a binary relation between a set of objects and a set of
properties (descriptors) to build a concept lattice and a set of
rules. Each node (concept) of the lattice represents a subset of
objects with their common properties. In this paper, some efficient
algorithms for generating concepts and rules are presented. The rules
are either in conjunctive or disjunctive form. To avoid the repetitive
process of constructing the concept lattice and determining the set of
implication rules from scratch each time a new object is introduced in
the input relation, we propose an algorithm for incrementally updating
both the lattice and the set of generated rules. The empirical
behavior of the algorithms is also analysed. The implication problem
for these rules can be handled based on the well-known theoretical
results on functional dependencies in relational databases.
