Using Case-Based Reasoning in Interpreting Unsupervised Inductive Learning Results

1 Introduction

Though the interpretation of induction results has a sig­ nificant role in machine learning applications, there have been little work in inductive learning, particularly in un­ supervised learning, associated with interpretation pro­ cedures, e.g., [Bergadano et al., 1992], [Wu, 1996].

There are three broad classes of logical, threshold, and competitive interpreters for intensional concept descrip­ tions [Langley, 1996]. Naturally, three types of outcomes occur when matching logically an unknown instance with learned concepts: no-match, single-match, and multiple­ match. Most work dealing with the cases of no-match and multiple-match employ a probabilistic estimation, e.g., [Michalski et al., 1986]. However, it is not always possible to obtain such an estimation in unsupervised learning when it requires using the class information. Moreover, the logical match of the concept intent does not always provide a prediction with enough satisfaction, particularly in boundary regions of concepts.

*This work is supported by Kokusai Electric Co., Ltd (Japan) to JAIST (Japan Advanced Institute of Science and Technology), and by the National Research Programme on Information Technology KC01-RD08 (Vietnam).

Chi Mai Luong Institute of Information Technology National Center for Natural Science and Technology Nghiado, Tuliem, Hanoi, Vietnam

One of two styles of case-based reasoning (CBR) is in­ terpretive by which new situations are evaluated in the context of old situations [Kolodner, 1992]. Rather than classifying new cases using the intensional concept de­ scriptions, CBR typically does classification by using the nearest neighbor methods which have been demon­ strated to be able to work often as well as other induc­ tive learning techniques [Aha et al., 1991]. However, one limitation of the CBR is that it does not provide the concept description which is the main advantage of in­ ductive learning about the knowledge understandability.

This paper highlights the intrinsic role of the interpre­ tive process in unsupervised inductive learning and pro­ poses a procedure that combines CBR with matching ap­ proaches in inductive learnin_g to interpret the concepts learned by method OSHAM [Ho, 1996], [Ho, 1997]. The reason for this combination lies in the fact that the use of results in unsupervised learning, obtained by a non­ exhaustive searching for regularities, can be suported by the nearest neighbor rule. The paper is organized as follows. Section 2 briefly resumes the learning phase in OSHAM consisting of an extended representation of concepts in the Galois lattice, and the essential ideas of the learning algorithm for extracting concept hierarchies from unsupervised data. Section 3 presents the inter­ pretation phase of OSHAM to classify unknown cases using learned knowledge. Section 4 presents an experi­ mental comparative study of four learning methods and the discussion. Section 5 is a short conclusion.

2 Learning Concept Hierarchies

2.1 Concept representation and extraction

Among views on concepts in cognitive science and ma­ chine learning, the classical, prototype and exemplar ones are widely known and used. Main strengths and limitations of these views on concepts have been widely reco~nized, e.g., [Van Mechelen et . al., 1993], [Wrobel, 1994]. Moreover, without the class information, unsu­ pervised learning systems often compose solutions by employing one or more of three main categorization constraints based on similarity, feature correlation, and syn­ tactical structure of conceptual knowledge.

. Recently, several concept learning systems have been de­ veloped using the classical view on concepts in the Galois lattice structure [Wille, 1982]. In [Godin and Missaoui, 1994], [Carpineto and Romano, 1996], the authors gen­ erate incrementally all possible concepts in the Galois lattice. In [Ho, 1995], an alternative approach to hierar­ chical conceptual clustering was proposed that extracts a part of the Galois lattice in the form of a concept hi­ erarchy. Although the Galois lattice provides a power­ ful structure for learning concepts, the classical view on concepts in this framework has some considerable limi­ tations, such as it does not capture typicality effects and vagueness. Otherwise, to find all possible concepts is not always tractable as in the worse case the number of concepts can be exponential in the size of datasets, e.g., even for the small well-known dataset of Congressional voting ( 435 instances X 17 attributes), the Galois lattice has about 150,000 nodes [Carpineto and Romano, 1996].

As analysed in [Van Mechelen et al., 1993], each system relies on a single view on concepts can be limited in cap­ turing the rich variety of conceptual knowledge. There­ fore, hybrid systems attempt to improve the concept learning process by combining fairly different theoreti­ cal views on concept and categorization constraints. In [Ho, 1996], the learning method OSHAM was improved by an extension of the classical view of concepts in the Galois lattice. Instead of characterizing a concept only by its intent and extent, OSHAM represents each con­ cept ck in a concept hierarchy 1{ by a 10-tuple

where

• l( ck) is the level of ck in 1£;
• f ( ck) is the list of direct superconcepts of ck;
• s( ck) is the list of direct subconcepts of ck;
• i( ck) is the intent of ck which is the set of all common properties of instances of ck;
• e ( ck) is the extent of ck which is the set of all instances satisfying properties of i( Ck);
• d( Ck) is the dispersion between instances of Ck;
• p( Ck) is the occurrence probability of Ck;
• d( Ck) is the dispersion of local instances of Ck which are not classified into subconcepts of Ck;
• p( c; I Ck) is the conditional probability of these unclassified instances of ck;
• q( ck) is the quality estimation of splitting ck into subconcepts ck,.

The induction and interpretation of components in (1) employ the following distance metrics. Denote by .A(X) for any instance set X the largest set of properties com­ mon to all elements of X, and by p( S) for any property set S the set of all instances satisfying S. The distance O(Op 1 o 9 ) between two instances Op and Oq is defined as an extension of Jaccard distance

where -y( a) E z+ are positive integer weights of at­ tributes a (with value 1 by default). The dispersion d( Ck) between instances in e( Ck), considered as the in­ verse of the homogeneity of e( Ck), is defined as the av­ erage distance between all pairs of instances in e( Ck)

If ck is a non-leaf concept, its local instances in c; can be considered to be more typical and representative than its instances classified into subconcepts Ck,. As an instance o is member of different concepts along a branch in the concept hierarchy, the concepts Ck that o E C{ is of particular interest. If ck is a leaf concept, we have e ( ck) = c; and all of its instances are considered with the same representative role.

The extent of all direct subconcepts Ck 1 , Ck,, ... , Ckn of ck and the set of local instances c; form a partition p of e(Ck)· Denote by W(Ck) the average of all d(Ck;) and d( Ck). The dissimilarity between subconcepts of Ck. denoted by B( Ck ), is defined as the average of distances ~(c(Ck;), c(Ck;)) between all pairs Ck 1 , Ck; in P, where the distance ~( c( ck, ), c( ck;)) is defined as the smallest distance among distances of all pairs Op E ck,, Oq E ck;

Table 1: Brief description of learning process

1. While Ck is still splittable, find a new subconcept of it that corresponds to the hypothesis minimizing the quality function q( Ck) among TJ hypotheses generated by the following steps
2. (a) Find a "good" attribute-value pair concerning the best cover of ck.
3. (b) Find a closed attribute-value subset S containing this attribute-value pair.
4. (c) Form a subconcept Ck 1 with the intent is S.
5. (d) Evaluate the quality function with the new hypothesized subconcept.

Form intersecting concepts corresponding to intersec­ tions of the extent of the new concept with the extent of existing concepts excluding its superconcepts.

1. If one of the following conditions holds then ck is con­ sidered as unsplittable
2. (a) There exist not any closed proper feature subset.
3. (b) The local instances set C{ is too small.
4. (c) The local instances set C{ is homogeneous enough.
5. Apply recursively the procedure to concepts generated in step 1.

The quality of splitting a concept Ck into subconcepts in the next level, denoted by q( Ck), is measured by

The basis of learning in OSHAM is a generate-and-test procedure to split a concept C into subconcepts at a higher level of 1£. Starting from the root concept of the Galois lattice with the whole set of training instances, it extracts the concept hierarchy 1i recursively in a top­ down direction. This algorithm is originally designed for discrete attributes with unordered nominal values. In the current version, continuous attributes are discretized before learning process by k-means clustering [Hartigan, 1975]. In fact, for each continuous attribute the k-means algorithm is applied to cluster its values into k groups (k = 1, 2, ... , K). A criterion similar to (5) with the Euclidean distance is used to choose a value of k that corresponds to the best partition according to this crite­ rion. The basic idea of learning algorithm in OSHAM, described fully in [Ho, 1996], is resumed in Table 1.

2.2 About learned concept hierarchies

By using different constraints for l.(a) in the learning algorithm, OSHAM is able to extract both overlap:{>ing or disjoint concepts depending the user's interest [Ho, 1997]. OSHAM has been implemented in the X Win­ dow on a Sparcstation with the direct manipulation style of interaction which allows the user to participate ac­ tively in the learning process. The user can initialize pa­ rameters to cluster data, visualize the concept hierarchy gradually, observe the results and the quality estimation, manually modify the parameters when necessary before the system continues to go further to cluster subsequent data or backtrack to regrow branches of the concept hi­ erarchy with respect to the categorization scheme. Fig­ ure 1 shows a main screen of the interactive OSHAM with a hierarchy of overlapping concepts learned from the Wisconsin breast cancer dataset. A full description of concept 43 in this figure is given below

CONCEPT 43 Level= 5 Super_Concepts = {29}, Sub_Concepts = {52, 53} Features= (Uniformity of Cell Size, 1) 1\ (Bare Nuclei, 1) 1\ (Bland Chromatin, 1) 1\ (Uniformity of Cell Shape, 2) LocaLinstances/Covered_instances = 6/25 LocaLinstances = {8, 127, 221, 236, 415, 661} Concept_probability = 0.041666 LocaLinstance_conditionaLprobability = 0.240000 Concept_dispersion = 0.258848 LocaLinstance_dispersion = 0.055556 SubconcepLpartition_quality = 0.519719

There is a considerable distinction in the concept de­ scription of OSHAM in contrast to those of other methods such as the supervised learning system C4.5 [Quin­ lan, 1993], the unsupervised learning systems COBWEB [Fisher, 1987] and AUTOCLASS [Cheeseman and Stutz, 1996]. C4.5 induces decision trees in which concepts are represented by their intent associated with a predicted error rate, and it has not to maintain intermediate con­ cepts. COBWEB represents each concept Ck as a set of attributes ai associated with a set of their possible values vi;, the occurrence probability, and the condi­ tional probability P( ai = vi; I Ck) associated with each value vi;. A classification in A UTOCLASS is defined as a set of classes, the probability of each class, and two ad­ ditional probabilities for each hypothesized model: the model probability P(H) and the conditional parameter probability distribution P(p I H).

We share the opinion in [Langley, 1996] that the inter­ pretive process is a central issue in learning. An inten­ sional representation has no meaning (e.g., no extension) without some associated interpreters and different inter­ preters can yield different meaning for the same repre­ sentation. Next section describes the second phase in OSHAM - its interpretive process.

3 Interpreting concept hierarchies

3.1 Interpretive CBR

Interpretive case-based learning is a process of evaluat­ ing situations in the context of previous experience. One way a case-based classifier works is to ask whether the unknown case is enough like another one known. It does classification by trying to find the closest matching case in its case base to the new case rather than using inten­ sional concept descriptions. Many studies have pointed out the strong points of CBR (e.g., simplicity, relatively robust, often excellent performance, etc.) and its weak points, e.g., [Aha et al., 1991), [Kolodner, 1992].

In inductive learning, the logical interpretation approach carries out an "all or none" matching process depend­ ing on whether the unknown instance satisfies the con­ cept intent. The threshold approach carries out a partial matching process and employs some threshold to deter­ mine an acceptable degree of match. The competitive approach also carries out a partial matching process and selects the best competitor based on estimated degrees of match [Langley, 1996]. The interpretation of induc­ tive learning results is commonly understood as the pro­ cess of comparing an unknown case to the learned con­ cepts. In OSHAM, as the generality decreases along branches of the concept hierarchy, we say that a con­ cept c/c matches the unknown instance e if c/c is the most specific concept in a branch that matches e inten­ sionally (though all superconcepts of C1c match e). Nat­ urally, there are three types of outcomes when matching logically an unknown instance e with the learned con­ cepts: only one concept that matches e (single-match), many concepts that match e (multiple-match), and no concept that matches e (no-match). We believe in the alternative roles of CBR and generalization in inductive learning. As noted in [Kolodner, 1992], rules could be used when they matched cases exactly, while cases would be used when rules were not immediately applicable. In fact, the nearest neighbor of e in the training set and the learned concept to which it belongs, denoted by NN(e) and c[NN (e)], provide useful information which could be used in all cases of single-match, multiple-match and no-match.

3.2 Interpretation of induction results

We develop an interpretation procedure for concept hi­ erarchies that uses the concept intent, the hierarchical structure information, the probabilistic estimations and the nearest neighbors of unknown instances. This in­ terpretation procedure consists of two stages: (1) find all concepts on the concept hierarchy that match e in­ tensionally, and (2) decide among these concepts which matches e best. This procedure shares the same scheme of the system POSEIDON [Bergadano et al., 1992), but functions differently. In the second stage, it determines the best matched concept of e with some satisficing de­ gree of prediction.

Consider the multiple-match case when we have to de­ cide among the competitors the best matched concept. To do it we need to determine and compare the degree of match of competitors. From various experiment case­ studies we note that a logically matched concept ck will match e well (with low error rate) if it satisfies a ma­ jority of the following conditions: l( C~c) is high, C~c is a leaf concept, p( C~c) x p( Ck) is high, d( C~c) is low, d( Ck) is low, and generally none of these factors has a clearly higher priority than the others. Formally, the follow­ ing functions rN,rL,rp,rv,rR can be used to compare these factors, respectively, between two concepts ck and ch which matched e intensionally

The following heuristic function r compares the degree of match of C1c and Ch. We say that C~c has a higher satisficing degree than ch in matching e if

Table 2: Interpretation procedure

Input concept hierarchy 11., unknown instance e. Re~ult best matched concept c[e), satisficing degree c/J. Variable~ q is a given threshold.

Procedure Interpretation{'H, e, c[ e), cjJ)

If there is only one concept C1c E 'H that matches e inten­ sionally then

If there are m concepts Ci 1 , ··· , Cim E 'H that match e in­ tensionally then

Choose iK E {il, ... , im} satisfying T( ciK' ci/c) ~ 0 when comparing Ci K with Ci/c for all i1c E { i1, ... , im }. If CiK = c[NN(e)) then c[e) +- CiK,cjJ +- M1 else ifT( CiK, c[NN( e))) ~ 0) then c[ e) +- CiK, cjJ +- M2 else c[e) +- c[NN(e)),c/J +- M3.

If there is not any concept that match e intensionally then if 6(NN(e), e):::; q then c[e) +- c[NN(e)),c/J +- N1 else c[e) = 0,4> +- N2.

where 9N,9L,()P,()D,(JR are positive weights for the im­ portance of the level, leaf concept, local instance condi­ tional probability, concept dispersion, and local instance dispersion (all with value 1 by default).

Denote by c[e] the best matched concept that e is finally decided to belong to, and by ifJ the satisficing degree of prediction. Table 2 presents the interpreta­ tion procedure in OSHAM based on the function T and the nearest-neighbor principle. Essentially, this proce­ dure makes final decision by comparing the best concept matching e with the concept c [ NN (e)] containing the nearest neighbor NN (e) of e regarding the function T. In this interpretation procedure, different symbolic val­ ues are assigned to the satisficing degree of prediction rp.

Values of ifJ indicate the decreasing rank of predic­ tion satisfaction. For example, we may consider S1 as "best prediction", M1 as "strong prediction" while N1 as "weakly accepted prediction" and N2 as "no prediction". The interpretation for different values of ifJ depends on the judgment of the user or domain experts.

4 Evaluation

4.1 Experimental Results

A way to evaluate unsupervised learning system is to em­ ploy supervised data but hide the class information in the whole learning and interpreting phases and use the class information only to estimate the predictive accuracy. We employ this way to evaluate unsupervised learning systems where the predicted name of each learned con­ cept C~.; is determined by the most frequently occurring name of instances in e ( C~.;). With this predicted name of learned concepts, the error rate of an unsupervised learn­ ing system can be estimated as the ratio of the number of testing instances correctly predicted regarding the pre­ dicted name over the total number of testing instances. It is worth mentioning that multiple train-and-test ex­ periments are much more computationally expensive but give more reliable evaluation than a single train-and-test experiment.

Experiments are carried out on ten datasets from the UCI repository of machine learning databases, includ­ ing the Wisconsin breast cancer (breast-w), Congres­ sional voting (vote), Mushroom (mushroom), Tic-tac­ toe (tictactoe), Glass identification (glass), Ionosphere (ionosphere), Waveform (waveform), Pima diabetes (di­ abetes), Thyroid (new) disease (thyroid), and Heart dis­ ease cleveland (heart-c). The numbers of attributes (dis­ crete and continuous), instances and "natural" classes of these datasets are given in columns 2-5 of Table 3. All experiments on these datasets are carried out with 10fold cross validation by four programs C4.5 [Quinlan, 1993], CART-like [Breiman et al., 1984], AUTOCLASS

and OSHAM in the same condition, i.e., the same ran­ domly divided datasets into subsets. For AUTOCLASS, we use the public version AUTOCLASS-C implemented in C and run three steps of search, report and predict with the default parameters. The predicted name and predictive accuracy of AUTOCLASS and OSHAM are obtained as mentioned above. Columns 6-8 report the predictive accuracies of C4.5, CART-like and AUTO­ CLASS, respectively.

For OSHAM we carried out experiments for two in­ terpretation procedures: OSHAM-NN (using only the nearest neighbors) and OSHAM-NN+r (using the near­ est neighbors and matching regarding the function T by the procedure described in Table 2). Experimental re­ sults are reported in columns 9--10, respectively. In order to avoid a biased evaluation of OSHAM, although with each dataset parameters can be adjusted to obtain the most suitable concept hierarchy, we fixed values a = 1% of the size of the training set, f3 = 15% and a = 10% of the number of attributes, and the beam size 11 = 3, commonly to all datasets. Two last columns in Table 3 give the average size of concept hierarchies (number of concepts) and CPU time (in second) of OSHAM learned from these datasets. ·

4.2 Discussion

The predicted name obtained in OSHAM and AUTO­ CLASS by the majority of occurring name of instances in concepts is different from the concept name obtained in supervised learning (e.g., C4.5) using the pruning thresh­ old based on the class information. An unsupervised con­ cept in the worse case may contain nearly equal numbers of instances belonging to different natural classes, and an unsupervised classification may be failed in distinguish­ ing very similar instances. It explains that while the predictive accuracies between these supervised and unsu­ pervised methods look not so different, they are slightly different in nature. Note that the recent release 8 of C4.5 [Quinlan, 1996] treats the continuous attribute better than the release we used in this work.

The predictive accuracies of OSHAM and AUTO­ CLASS in these experiments are only slightly different. In these first trials, each system is better in several datasets and these two systems can be considered having comparable performance. One advantage of OSHAM is its concept hierarchies can be easily understood by its extended classical view on concepts and the graphical support.

Empirical results with OSHAM-NN and OSHAM­ NN+r illustrate that these strategies are both good for interpreting unsupervised induction results. We believe that in general CBR can also be used to interpret re­ sults of unsupervised learning and this topic is worth for a further investigation.

5 Conclusion

In this paper we first briefly resumed the main ideas of the unsupervised learning method OSHAM in terms of description and extraction of concepts. We then de­ scribed how the nearest neighbor rule is combined with domain knowledge to interpret the induction results. Careful experiments with different datasets have demon­ strated that this combination provides a good solution to the use of unsupervised learned knowledge in pre­ diction. The main conclusions can be drawn from this research are {1) the interpretive process needs to be a part of a unsupervised learning method, and {2) the CBR can be used to interpret results obtained from the non-exhaustive search in unsupervised inductive learn­ ing. Our near future research concerns further investi­ gations on the effects of k-nearest neighbors and the dis­ cretization of continuous attributes to the interpretation of unsupervised induction results, based on experiments with a larger number of datasets.