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.
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.
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