Catalogue of Artificial Intelligence Techniques
Author(s): Jeremy Wyatt
Conceptual clustering is an Unsupervised Learning procedure which builds a Discrimination Net given a set of input patterns. It begins with the root node of a tree structure, all of the input patterns being attached to that node. A decision is made as to how split the set of all input patterns into two (or more) more specific classes. Each of these classes is represented by sub-nodes in the tree structure, each input pattern being attached to the node representing its class. The splitting of the tree continues until all nodes are singleton sets. Different approaches to conceptual clustering use different methods to decide how best to split the tree. COBWEB chooses the partition of a set of input patterns which maximises a measure of the total intra-class similarity and inter-class dissimilarity. Intra-class similarity can be expressed as the conditional probability of an object possessing a particular property given that the object belongs to a particular class. Inter-class dissimilarity can be expressed as the conditional probability of a particular class given a property. This is summed over all classes and their members for each possible partition of the set of input patterns. Conceptual clustering is related to the statistical technique of cluster analysis. The principal difference is that while cluster analysis requires that all the data (input patterns) are present at the beginning of process, conceptual clustering works incrementally, i.e., it adjusts its current partitioning of the space of input patterns as each new pattern is presented. This has the consequence that conceptual clustering methods may converge to suboptimal partitions. COBWEB attempts to overcome this problem by employing node merging and splitting operators. These effectively allow the learner to backtrack within the search space of possible partitions.
- Fisher, D. and Langley, P., Approaches to Conceptual Clustering, Proceedings of IJCAI-85, Morgan Kaufmann, Los Altos, CA, 1985, pp. 691--697.