Michalski (1980) proposed conceptual clustering as a means of discovering `understandable' patterns in data. However, this definition does not specify a performance task that improves with learning (cf. Figure 1). Fisher (1987b, c) proposes that one such task is the prediction of unobserved properties. As such, Fisher's COBWEB system forms classification trees that are intended to yield `good' prediction along many attributes, rather than optimal prediction along a single `teacher'-defined attribute as in learning from examples. Despite COBWEB's reduced expectations, Fisher (1987a, b) shows that in many cases prediction with a single COBWEB classification tree approximates the accuracy obtained from multiple, special-purpose ID3 decision trees.
An important difference between COBWEB and earlier conceptual clustering systems is that it is incremental - COBWEB integrates an observation into an existing classification tree by classifying the observation along a path of `best' matching nodes. Like ID4, probabilistic summaries of previous observations are stored at each node, but the matching functions and the criteria used for subtree revision differ considerably. COBWEB uses the category utility function (Gluck & Corter, 1985) to guide classification and tree formation. Category utility bases its evaluation on all of the observation's attribute-values rather than a single one, making COBWEB a polythetic classifier as opposed to a monothetic classifier (e.g., CLS and ID4). Similarly, COBWEB's subtree revisions are triggered by considering prediction ability over all attributes, but concern for multiple attributes complicates subtree revision. In ID4 a subtree is simply deleted, but in COBWEB a deletion that benefits one attribute may be inappropriate for others. In response, the system identifies points in the tree for cost-effective prediction of individual attributes. These points are marked by normative (Kolodner, 1983) or default values that COBWEB dynamically maintains during incremental clustering.
COBWEB's main contribution to the present discussion is that it maintains a knowledge base that coordinates many prediction tasks, one for each attribute. This is in sharp contrast to learning from examples systems where a knowledge base need only support one task. However, despite COBWEB's greater knowledge base complexity, Fisher (1987c) argues that its tree structure is still too restrictive; more general structures like directed acyclic graphs (DAGs) would yield better prediction. These structures are used by COBWEB's main precursors, UNIMEM (Lebowitz, 1982) and CYRUS (Kolodner, 1983). Regrettably, neither UNIMEM and CYRUS is characterized in terms of prediction accuracy, the increased costs that maintaining a DAG is likely to incur, or the fundamental tradeoff that must exist between these dimensions.