COBWEB is an incremental system for hierarchical conceptual clustering. COBWEB was invented by Professor Douglas H. Fisher, currently at Vanderbilt University.
COBWEB incrementally organizes observations into a classification tree. Each node in a classification tree represents a class (concept) and is labeled by a probabilistic concept that summarizes the attribute-value distributions of objects classified under the node. This classification tree can be used to predict missing attributes or the class of a new object.
There are four basic operations COBWEB employs in building the classification tree. Which operation is selected depends on the category utility of the classification achieved by applying it. The operations are:
Merging Two Nodes Merging two nodes means replacing them by a node whose children is the union of the original nodes' sets of children and which summarizes the attribute-value distributions of all objects classified under them.
Splitting a node A node is split by replacing it with its children.
Inserting a new node A node is created corresponding to the object being inserted into the tree.
Passing an object down the hierarchy Effectively calling the COBWEB algorithm on the object and the subtree rooted in the node.
Contents
The COBWEB Algorithm
COBWEB(root, record):
Input: A COBWEB node root, an instance to insert record
if root has no children then
children := {copy(root)}
newcategory(record) \\ adds child with record’s feature values.
insert(record, root) \\ update root’s statistics
else
insert(record, root)
for child in root’s children do
calculate Category Utility for insert(record, child),
set best1, best2 children w. best CU.
end for
if newcategory(record) yields best CU then
newcategory(record)
else if merge(best1, best2) yields best CU then
merge(best1, best2)
COBWEB(root, record)
else if split(best1) yields best CU then
split(best1)
COBWEB(root, record)
else
COBWEB(best1, record)
end if
Limitations and extensions
While the original COBWEB algorithm is a pioneering system for incremental conceptual clustering, it has several limitations:
Attribute independence assumption: Like Naive Bayes classifiers, COBWEB assumes that all attributes are conditionally independent of one another within a given category. Consequently, it cannot explicitly capture correlations or dependencies between features when calculating category utility.
Categorical attributes only: The 1987 formulation of COBWEB was designed strictly for nominal (categorical) attributes, storing probability distributions for discrete attribute-value pairs at each node.
Sensitivity to input sequence: Because COBWEB is an incremental algorithm, the final structure of the classification tree is sensitive to the order in which data points are presented. Although COBWEB employs bidirectional restructuring operators—specifically, "merging" and "splitting" nodes—to help correct suboptimal tree topology and reduce these order effects, they do not completely eliminate sensitivity to input sequences.
Several major extensions have been developed to address these limitations:
CLASSIT: Developed by John H. Gennari, Pat Langley, and Douglas H. Fisher in 1989, CLASSIT extends COBWEB to process continuous (real-valued) data. Instead of storing discrete conditional probability tables, CLASSIT models continuous attributes using a normal distribution, storing the mean and standard deviation for each feature at each node of the hierarchy.
COBWEB/3: Developed to handle datasets with mixed-type data, COBWEB/3 integrates the nominal attribute representation of the original COBWEB with the continuous attribute representation of CLASSIT. This allows the system to construct hierarchies over objects described by both categorical and continuous variables.