Improving Inference through Conceptual Clustering

Douglas H. FisherAAAI 1987

Abstract

COBWEB is an incremental learning system that organizes observations into a hierarchical tree of probabilistic concepts. By using a "category utility" metric to guide its growth, the system creates clusters that maximize the ability to infer missing information about new objects. This approach effectively "rediscovers" natural categories, such as medical diagnoses, without explicit supervision, bridging the gap between unsupervised clustering and predictive utility.

Introduction

In the late 1980s, machine learning research was largely bifurcated into supervised "learning from examples" and unsupervised "conceptual clustering." While clustering excelled at data summarization, its practical utility for specific tasks remained unclear. Fisher addressed this by asking how data could be automatically grouped to optimize predictive power. Unlike the batch algorithms of the time, Fisher proposed an incremental system that links cluster quality directly to its ability to inform us about an object's attributes.

The COBWEB Algorithm

The core of Fisher's work is COBWEB, an algorithm that constructs a classification tree where each node represents a "probabilistic concept." Rather than using rigid logical definitions, these nodes store the conditional probability of each attribute value within that class.

Category Utility and Incremental Growth

COBWEB employs a heuristic known as Category Utility, derived from psychological research on human categorization. This metric rewards partitions that maximize both predictability (the probability of an attribute given a category) and predictiveness (the probability of a category given an attribute). This allows the system to identify "basic level" categories that provide the most information about their members.

Hierarchical classification tree for soybean diseases generated by COBWEB.

The system processes objects one at a time, descending the tree and using four primary operators to update the structure: placing the object in an existing class, creating a new singleton class, merging two classes, or splitting a class. The merge and split operators are particularly vital, as they allow the system to backtrack and refine the hierarchy as more data becomes available.

Evaluation and Results

The system was primarily evaluated using the Soybean Disease Dataset, consisting of 47 cases described by 35 attributes. The objective was to determine if COBWEB could predict the "Diagnostic-condition" (the disease name) and other missing attributes.

Performance and Efficiency

COBWEB demonstrated rapid learning capabilities. On the soybean dataset, it achieved 100% accuracy in diagnosing diseases after seeing only 10 random instances. Across all attributes, COBWEB maintained an average prediction accuracy of approximately 88%, significantly outperforming a frequency-based baseline that simply guesses the most common value.

Comparison of COBWEB and frequency-based prediction accuracy over observed objects.

Furthermore, the algorithm's update cost is relatively low—roughly $O(B^2 \log_B n)$, where $B$ is the branching factor and $n$ is the number of objects—making it efficient for real-time, incremental learning tasks.

Key Insights and Discussion

A major finding was that COBWEB's unsupervised clustering naturally "rediscovered" disease labels. Even when the disease name was hidden during training, the resulting hierarchy contained nodes that corresponded directly to specific diseases. This suggests that the system excels at capturing the underlying correlations between attributes.

However, the 1987 version of COBWEB had limitations. It was restricted to nominal attribute-value pairs and could not handle continuous data or complex relational structures. Fisher also noted that while the study classified objects down to the leaves, it might be more efficient to stop at intermediate nodes where predictions are "satisficing" (good enough).

Conclusion

COBWEB represents a significant step in unifying clustering and inference. By optimizing for predictive utility, it provides a framework for building hierarchies that are not just summaries of data, but active tools for reasoning and prediction in complex domains.

Summary updated

BibTeX
@inproceedings{fisher1987improving,
  author = {Douglas H. Fisher},
  title = {{Improving Inference through Conceptual Clustering}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure