Noise-Tolerant Conceptual Clustering

1 Introduction

Machine concept learning has traditionally been con­ cerned with learning from examples (e.g., Quinlan, 1986), which assumes that observations are identified as members of a priori known classes (e.g., diseases); the learner must characterize the observations of each class . In contrast, conceptual clustering methods (Michalski & Stepp, 1983; Fisher, 1987b; Cheeseman, Kelly, Self, Stutz , Taylor, & Freeman, 1988) discover, as well as characterize meaningful classes.

In principle, learning should improve an organism's performance at some task(s). In learning from examples a performance task is apparent: improve prediction of class membership (e.g., diagnose the illness of a patient). On the otherhand, conceptual clustering is not tradi­ tionally associated with a performance task (Michalski & Stepp, 1983; Cheeseman, Kelly, Self, Stutz, Taylor, & Freeman, 1988). Fisher (1987a,b) proposes that a per­ formance task for conceptual clustering is flexible pre­ diction: the prediction of multiple attributes, not sim­ ply a single class 'attribute'. For example, a learning tively partition the observed objects. COBWEB incor­ porates a new object into the class that best matches the object according to category utility (Gluck & Corter, 1985), a measure that rewards the formation of object classes that maximize 'prediction ability'. More for­ mally, the category utility of a class, ck, is a func­ tion of the expected number of attribute values that can be correctly predicted about members of the class, E(#CorrectPredictions!Ck) · If P(A; = V;i!Ck) is the probability that a particular value, V;j' is true of ck members and the value will be predicted with the same probability then this expectation can be further for­ malized in terms of conditional probabilities that are stored at tree nodes: E( #CorrectPredictions!Ck) = I:; :L:i P(A; = V;i !Ck ) 2 . Category utility has some additional complexities (Gluck & Corter, 1985; Fisher , 1987b), but for our purposes we assume

*This work was supported by a grant from the Vanderbilt Uni­ versity Research Council.

where P( Ck) is the proportion of the observations to which the expectation applies; P( Ck) is the probability that the benefits (expectations) of a class will be realized.

COBWEB incrementally filters objects into appropri­ ate classes based on category utility. A new object is evaluated with respect to a class by tentatively placing the object in the class; each class's attribute-value dis­ tributions are tentatively updated to reflect the values of the new object. These distributions are actually stored as integer counts: P(A; = V;j !Ck) = ( # of Ck objects with V;j)/(# ofCk objects) . Probabilities are computed from the newly (tentatively) updated distributions and the category utility of the class is computed. The class that maximizes category utility after adding the new object is chosen to classify the object and appropriate distributions are updated permanently. This process is recursively applied to the subtrees rooted at the selected child until a leaf is reached. A leaf is a singleton class that represents a previously observed object . While ob­ jects are predominantly incorporated with respect to ex­ isting classes , operators also exist for new node (class) creation, node combination (merging), and node division (splitting) . A more complete description of COBWEB can be found in Fisher (1987b) .

Object incorporation is easily adapted to allow ob­ ject classification and flexible prediction: category util­ ity guides an object along a path of nodes to a 'best' matching leaf. If any value(s) are missing from the new observation, they may be predicted from the known val­ ues of the leaf. While COBWEB trees are reminiscent of decision trees, probabilistic concepts are polythetic in that multiple attributes guide classification. If an object has missing attribute values then category utility acts as a partial-matching function with summation limited to probabilities of known attributes.

In our experiments a classification tree is constructed from a training set of objects. Each object of a dis­ tinct testing set is repeatedly classified with respect to the tree; in each repetition a different attribute is re­ moved from the object description and must be pre­ dicted. Average prediction accuracy is computed over the test set for each attribute. In addition, prediction accuracy is tested for different size training sets. The result is a 'learning curve' for each attribute. Figure 2 shows the learning curve for three of the 37 attributes in a domain of soybean case histories (Stepp, 1984) . As the curves illustrate, learning difficulty may vary con­ siderably across attributes; some attributes (e.g. , con­ dition) are quickly and effect ively learned (i.e., simply guessing the most frequent condition value would yield about 35% accuracy), some are invariant to training (e.g., occurrence-of-hail), but most are somewhere in be­ tween (e.g., damage-severity). COBWEB learns to pre­ dict all attributes (with variable success) using a single probabilistic concept tree . In contrast , ID3 and other learning from examples systems would have to be applied separately for each attribute. Fisher (1987a) compares the performance of one COBWEB tree with multiple, special-purpose ID3 trees.

This paper investigates the impact of two environmen­ tal factors on flexible prediction. Foremost among these is noise: the incorrect reporting of an attribute's value. Noise alters attribute correlations that all inductive sys­ tems require for effective learning. For example, if we randomly replace attribute values in the soybean domain with a probability of 25% (i.e., artificially introduce 25% noise) then prediction of severity-of-damage degrades to roughly 60%. A second influence on prediction accuracy is the extent of training, which also effects perceived sta­ tistical relationships between attributes. Our investiga­ tion motivates two strategies for noise-tolerant conceptual clustering.

3 Chi-Square Preferences

Quinlan {1986) has extensively investigated the detri­ mental impact of noise on prediction in ID3. Original versions of ID3 decomposed the training set to the point where all observations classified under a decision tree node were members of the same class. However, Quinlan {1986) demonstrates that this strategy tends to 'overfit' the data in noisy domains: classification to a leaf may be guided by spurious, unjustified rules that do not benefit and actually detract from prediction accuracy. Several authors (Quinlan, 1986, in press; Breiman, Friedman, Olshen, & Stone, 1984) have explored methods for prun­ ing unjustified rules so as to mitigate the effects of noise . A well-known technique is chi-square pruning (Quinlan, 1986). A decision tree node is decomposed only if it will lead to class distributions (at the new children) that are significantly different than the class distribution at the node to be divided. If the distributions do not differ significantly then the subtree is pruned; deeper classifi­ cation will not benefit prediction.

The benefits of pruning in learning from examples are well-documented in noisy domains and motivate an ex­ ploration of the possible benefits to flexible prediction. COBWEB was modified to use a chi-square test of statis­ tical significance for individual attributes . In particular, the distribution of an attribute's values at each node , N, are compared to the distribution of the node's chil­ dren. If the distributions do not differ significantly by a user-specified confidence threshold (e.g., 90%) then N is taken as the prediction point for the attribute. Note that in flexible prediction we cannot simply prune a sub­ tree based on the significance test for any one attribute, since this may not be an appropriate pruning point for other attributes. Rather, a strategy of less finality is to identify preference points based on the chi-square test that are maintained for each attribute. Attribute pre­ diction requires that object classification proceed to an appropriate preference point, but no deeper . The most common attribute value at the preference point is the predicted value.

Experiments with the chi-square heuristic were run in three natural domains: the soybean disease case histo­ ries, a domain of poisonous and edible mushroom de­ scriptions over 23 attributes, and voting records of 435 U.S. Representatives defined over 17 votes each. Pre­ diction accuracy over a separate test set was checked at regular training intervals, for varying noise levels, and for 8 different chi-square confidence thresholds. Thresh­ olds included 0% and 100%. In the of case 0% confi­ dence any distribution difference is significant and using this threshold results in classification to a leaf, which is identical to previous COBWEB implementations. In contrast, 100% confidence can never be achieved and dis­ allows classification beyond the root; the prediction is the most common value over the entire training set .

Figure 3 plots the 'averaged' attribute learning curves of the mushroom domain with no noise, but with dif­ ferent confidence thresholds. Low confidence appears to be the best strategy early in training since predic­ tive patterns have been exposed, but have not reached statistical significance to the degree required by higher confidences. Chi-square preferences at high thresholds converge on equivalent accuracy (i.e., no significant dif­ ferences in accuracy levels) later in learning (also see Fisher & Schlimmer, 1988).

The graph of Figure 4 examines the effect of noise . This graph shows averaged attribute accuracy levels af­ ter significant training at noise levels of 0%, 25%, and 50%. In general, the optimal threshold tends to increase with noise. Over all attributes there is a significant pos­ itive correlation between noise level and optimal confi­ dence threshold (Pearson coefficient = 0.375, sample = 23 x 3 = 69) . As noise increases, the deeper the clas­ sification (i .e., beginning at 0% confidence) the greater the overfitting. In noisy domains, higher chi-square con­ fidences significantly increase accuracy.

A general trend in the data is that optimal confidence thresholds increase with noise and training, asymptot­ ing at very high confidence thresholds (e.g., 99%). Early in training and under noiseless conditions classification to a leaf is the optimal strategy. No chi-square con­ fidence threshold will maximize performance in all (or most) learning scenarios. Thus, unless we can make a priori assumptions about the amount of noise and avail­ able training data, inconsistent performance will be a weakness of any constant-threshold method. Section 4 introduces a simple, but effective means of preference identification that makes no assumptions about noise, training, or their interaction.

4 Past-Performance Preferences

A straight-forward heuristic is that prediction of a miss­ ing attribute should occur at a node that historically has facilitated the greatest number of correct predictions. As a new training object is recursively classified, each of its attribute values is compared against the correspond­ ing attribute values of the node; if the object's value equals that of the node's most common value, then the attribute's value would have been correctly predicted at the node. For each attribute and node, a count is main­ tained of the number of times the attribute was cor­ rectly predicted at the node (i.e., correct-at-node counts) during training. A count is also kept of the number of times that the attribute was correctly predicted at one of the node's descendents (i .e., correct-at-descendent) . This latter count is updated as the recursive classifica­ tion procedure unwinds; the correct prediction at a node is remembered and used to update the counts of its an­ cestors. When an object is added as a leaf we assume that it correctly predicts its own attribute values and there are no descendants (that correctly predict them). By convention, correct-at-node counts are initialized to 1 and correct-at-descendent counts are initialized to 0.

To predict the value of a missing attribute, classifica­ tion proceeds until a node is reached that has historically outperformed its descendents in terms of predicting the missing attribute. At this point, the most common at­ tribute value is forwarded as the correct answer . This method is similar in intent to Breiman, Friedman, 01shen, & Stone's (1984) cost-complexity pruning strategy and Quinlan's (in press) redt~ced error pruning. In these latter methods, a decision tree is fully constructed with a training set. The tree is then used to classify a separate test set . As each test item is classified a determination is made as to whether it would be correctly classified at each node (by the most coriunon class at the node) on the path to a leaf. The tree is pruned at those nodes that maximized prediction over the test set. A separate test set is required because the original decision tree was engineered to fit the training set; cross-validation is nec­ essary. In contrast, past performance is applicable to flexible prediction. A separate test set is not required, because the tradeoffs required to simultaneously improve prediction along many attributes introduces tradeoffs similar to those of training/cross-validation in ID3.

Experiments identical to those with chi-square were run. Figures 5 and 6 indicate that past-performance preferences roughly match the optimal chi-square thresh­ olds averaged over various training and noise lev­ els. Importantly, the optimal chi-square threshold dif­ fers between training and noise levels. Over each training/noise-level combination in the three (mush­ room, soybean, congressional) domains (i.e., a total of 51 situations), past performance's mean accuracy is greater in significantly (x 2 , a = 0.005) more situations than any single chi-square confidence level (i.e., ranging from 41/51 when compared to confidence level 0.00 to 49/51 for confidence level 0.50). These averaged results hide fluctuations among attributes, but conveniently and ac­ curately reflect past performance's advantage.

The simplicity and effectiveness of past-performance preferences underscores an important principle: overt performance is the best (and simplest) 'model' of the complex interactions between noise levels, training, and other factors. Past performance makes no a priori assumptions about individual attribute characteristics, noise levels, or extent of training. Rather, attribute pref­ erences are determined by the accumulated correct pre­ diction counts for each node and its descendents.

5 Related and Future Research

Our studies of flexible prediction suggest further research in conceptual clustering and related areas.

5.1 Default Reasoning

Default values are often used to support uncertain rea­ soning, but Brachman (1985) points out that the auto­ mated reasoning literature makes no mention of prescrip­ tive means for assigning default values. Not coinciden­ tally, there has been little (if any) work on default value maintenance during learning. Our research provides a partial prescription for default identification.

Kolodner's (1983) CYRUS system offers a probabilis­ tic interpretation of default values: normative values are true of a user-specified percentage (e.g., 67%) of class members. Normative (default) values at a top­ level node (e .g., 'conservative' congressmen vote 'yes' on budget cuts) can be shown otherwise by classification to deeper levels (e.g., 'southern democrats' vote 'no' on budget cuts). Unfortunately, normative values require a user-supplied parameter and only delimit when a value is likely to be true; they fail to capture the more sub­ tle notion of when it is best to predict that a value is true . Past-performance and chi-square preferences ad­ dress both issues by demarcating locations where the most common value should be predicted. Nonetheless, important issues remain unaddressed.

Attribute preferences are absolute - based on the pre­ sumption that a certain amount (most) of 'evidence' is known. An important goal of future research is a pro­ cess of default selection that is sensitive to the amount of available evidence (i.e., observed features) . One idea is to cease classification when the difference in category utility scores between the best node and alternatives be­ comes sufficiently small: evidence is not sufficient to dis­ tinguish classification paths. This value would be the default value unless (and until) further evidence could be obtained. This classification procedure is more in line with traditional efforts in automated and default reasoning. Future work will seek to flesh out the relationship between incremental concept formation and prescriptive mechanisms for default identification and exploitation.

5.2 Case-Based Reasoning

Case-based reasoning has emerged as a subfield of au­ tomated reasoning and learning. The subfield is distin­ guished by its reliance on cases or object-level descrip­ tions as a source of problem-solving information. The emergence of this subfield has the unfortunate effect of segregating research efforts that share fundamental spec­ ification and design principles, but differ (perhaps) only in implementation. Initial versions of COBWEB gener­ ated predictions from best matching leaves (previously observed objects) . Thus, COBWEB is an efficient im­ plementation of case-based reasoning, since generalized concepts help identify appropriate cases in logarithmic time versus linear time in the number of cases.

In addition to efficiency concerns, this paper illustrates the utility of case-based and abstraction-based inferenc­ ing. Reasoning at the case-level is most productive when few training observations are available and noise is not present (Ashley & Rissland, 1988), but this strategy overfits the data as training and noise increase. Past performance has the emergent effect of using cases very early in training - a case (observation) is initially added to a concept tree and is viewed as correctly predicting each of its attribute values . When very few observations have been seen these individual 'successes' will tend to outway the formative classes above. Gradually, solidify­ ing attribute correlations at higher-level nodes become more reliable classifiers. Past performance's emergent strategy can be viewed as a probabilistic and conserva­ tive specific to general search for the optimal prediction level of each attribute.

An alternative to abstraction-based reasoning is to retain carefully-selected cases only. Presumably, selec­ tive retention overcomes both problems of efficiency and accuracy that might otherwise hamper a nonselective case-based reasoner. Selective retention is employed by Bareiss & Porter (1987) and Aha & Kibler (1988) in their respective case-based learning from examples systems . Nonetheless, appropriate retention is difficult without the global guidance that abstracted knowledge can pro­ vide: Aha & Kibler report difficulties in dealing with irrelevant attributes and Bareiss & Porter use implicit sources of abstracted knowledge. Finally, while strict adherence to a case-based strategy is feasible in a learn­ ing from examples context, it is difficult to imagine an efficient implementation for flexible prediction, in which many prediction dimensions must be simultaneously co­ ordinated.

6 Concluding Remarks

Experiments with COBWEB uncovered data overfitting that was mitigated by adapting pruning techniques for flexible prediction. However , the use of a constant­ threshold method like chi-square often leads to non­ optimal performance; we cannot predict a priori the amount of noise, training, or their interaction.

Limitations of chi-square preferences appear to be re­ duced by past performance: classification ceases at a point that has historically outperformed its descendents. Thus, we do not model (or impose a model on) noise, training, and other statistical interdependencies beyond that which COBWEB is constructing through clustering. Rather, whatever these interdependencies, their effect is evident through prediction performance; nothing beyond past performance is used to guide classification. This principle is also implicit in COBWEB's use of category utility, a measure of the expectation of correct predic­ tion afforded by classes. Class quality is tied directly to the task that will benefit from clustering. The explicit consideration of a performance task that improves with learning distinguishes COBWEB from almost all other clustering work and frees the system from user-supplied parameters or distributional assumptions of any kind.

Acknowledgements

I thank Jungsoon Yoo, Hua Yang, Ray Bareiss, and Gautam Biswas for informative discussions . Comments on an earlier draft by Dennis Kibler and John Gennari improved discussion and style considerably. Reviewers helped improve the clarity and correctness of the paper.