Approaches to Conceptual Clustering

Abstract

Methods for Conceptual Clustering may be explicated in two lights. Conceptual Clustering methods may be viewed as extensions to techniques of numerical taxonomy, a col­ lection of methods developed by social and natural scien­ tists for creating classification schemes over object sets. Alternatively, conceptual clustering may be viewed as a form of learning by observation or concept formation, as opposed to methods of learning from examples or con­ cept identification. In this paper we survey and compare a number of conceptual clustering methods along dimen­ sions suggested by each of these views. The point we most wish to clarify is that conceptual clustering processes can be explicated as being composed of three distinct but inter-dependent subprocesses: the process of deriving a hi­ erarchical classification scheme; the process of aggregating objects into individual classes; and the process of assigning conceptual descriptions to object classes. Each subpro­ cess may be characterized along a number of dimensions related to search, thus facilitating a better understanding of the conceptual clustering process as a whole.

I. INTRODUCTION

Classification is a process critical to the success of an intelligent organism. The ability to classify objects (events, states, observations, etc.) as members of object families or concepts, is the basis of all inferential capac­ ity. Work in Artificial Intelligence has concentrated sig­ nificantly on developing mechanisms for classification, and the conceptual representations necessary to support these mechanisms. Machine Learning research, specifically work in learning from examples, has facilitated a better under­ standing of processes of concept identification, that is the derivation of concepts for a teacher imposed classification. Learning from examples however, has not addressed the problem of how a learner can originate classes, but only how conceptual descriptions can be assigned to externally provided classes. Recently methods of conceptual clus­ tering have been forwarded, which do provide (partial) solutions to the object class origin problem.

t This work was supported by Contract N00014-84-K-0345 from the Information Sciences Division, Office of N a.val Research.

Approaches to Conceptual Clustering t

Douglas Fisher and Pat Langley

Irvine Computational Intelligence Project Department of Information and Computer Science University of California, Irvine, California 92717

Methods of conceptual clustering are best explicated and compared with respect to two alternative, but com­ plementary views.

Two Views of Conceptual Clustering

1. Methods of conceptual clustering are viewed as ex­ tensions or analogs to techniques of numerical tax­ onomy, a collection of methods developed by natu­ ral and social scientists used to form classification schemes over data sets.
2. Already alluded to is that conceptual clustering is a form of concept formation or learning by observation as opposed to learning from examples.

Each of these views has utility in explicating pro­ cesses of conceptual clustering, and each view will con­ tribute to a unified set of dimensions along which we may characterize various conceptual clustering techniques.

IT. CONCEPTUAL CLUSTERING and NUMERICAL TAXONOMY

Conceptual clustering is a process abstraction orig­ inally motivated and defined by Michalski (1980) and Michalski and Stepp (1983a) as an extension of processes of numerical taxonomy. Any clustering method, whether it be of the conceptual clustering or numerical taxonomy variety may be abstracted as follows.

The Abstract Clustering Task

Given: A set of symbolically described objects, 0.

Task: Distinguish clusters (ie. subsets of 0), C1, ··· , C,., such that the set of clusters (ie. a clustering) is of high quality (perhaps not optimal) with 1espect to a clustering quality function.

Methods of numerical taxonomy cluster objects that are symbolically described as sets of variable--value pairs (ie. attribute-feature pairs). In methods of numerical tax­ onomy, the quality of a clustering is a function only of the clusters of the clustering. That is, numerical taxonomy techniques attempt to find a clustering which maximizes a (numeric) quality function of the following form.

Despite the usefulness of numerical taxonomy tech­ niques, any such method suffers from a major limitation, in that the resultant clusters may not be well character­ ized in some human-comprehensible conceptual language. This limitation can be of concern to a data analyst (or learning program) who (which) wishes to abstract the un­ derlying conceptual structure of object groups in order to hypothesize about future observations, or to simply com­ press the data in an intelligent, easily recoverable way. Michalski (1980) defines conceptual clustering as an ex­ tension over the techniques of numerical taxonomy, which directly addresses the problem of determining conceptual representations. In methods of conceptual clustering, the quality of a clustering is dependent on the quality of con­ cepts which may be used to characterize clusters of the clustering (eg. the 'simplicity' of concepts) and/or the map between concepts and the clusters they cover ( eg. the 'fit' or generality of derived concepts). That is, methods of conceptual clustering seek to obtain clusterings which maximize a quality function of the following form.

where CONCEPTS is a set of concepts which may be used to describe object clusters. 1

Conceptual clustering algorithms which have been framed as extensions to numerical taxonomy techniques include CLUSTER/2 by Michalski and Stepp (1983a, 1983b), DISCON by Langley and Sage (1984), and the RUMMAGE program by Fisher (1984). A number of other algorithms, although not explicitly labeled concep­ tual clustering techniques, but which nonetheless can be framed as such, include GLAUBER by Langley, Zytkow, Simon, and Bradshaw (1985), MKlO by Wolff (1980), and Lebowitz' IPP (Lebowitz, 1983) and UNIMEM (Lebowitz, 19.82) systems. Each of these systems has a rough analog with some methods of numerical taxonomy which we now touch upon.

The literature on numerical taxonomy distinguishes three classes of methods (Everitt, 1980).

1 This definition of conceptual clustering differs from but ill consistent with Michaleki's (1980) .

·

Optimization techniques of numerical taxonomy form a 'flat' (ie. unstructured) set of mutually exclusive clusters (ie. a partition over the input object set). Optimization techniques make an explicit search for a globally optimal K-partition of an object set, where K is a user supplied parameter. This search for glob­ ally optimal partitions make optimization techniques computationally expensive, thus constraining their use to small data sets and/or small values of K.

Hierarchical techniques form classification trees over object sets, where leaves of a tree are individual ob­ jects, and internal nodes represent object clusters. A 'flat' clustering of mutually-exclusive clusters may be obtained from the classification tree by sever­ ing the tree at some level. Hierarchical techniques are further divided into divisive and agglomerative techniques, which construct the classification tree top-down and bottom-up, respectively. Hierarchical techniques depend on 'good' clusterings arising from a series of 'local' decisimi.s. In the case of divisive techniques, a node in a partially constructed tree is divided independent of other (non-ancestrial) nodes of the tree. The use of 'local' decision-making in hi­ erarchical methods make them computationally less expensive than optimization techniques with an as­ sociated probable reduction in the quality of con­ structed clusterings.

Clumping techniques return clusterings where con­ stituent clusters possibly overlap. The possibility of cluster overlap stems from independently treat­ ing some number of clusters as possible hosts for an object which must be incorporated into a clustering.

We can impose a classification on conceptual clustering methods analogous to the one just discussed for meth­ ods of numerical taxonomy. The Partitioning Module of CLUSTER/2 by Michalski and Stepp can be viewed as a conceptual optimization technique which given an ob­ ject set to be partitioned and a parameter, K, specifing the number of desired clusters (ie. the partition size), at­ tempts to construct an optimal K-partition of the object set. The partitioning module is computationally expen­ sive and is prohibitive for large values of K. The Hierarchy­ building Module of CLUSTER/2 is a conceptual hierarchi­ cal technique which builds a classification tree top-down (ie. it is a divisive technique). In dividing each node in the classification tree, the hierarchy-building module calls the partitioning module for small partition sizes (ie. K), and selects the optimal partition from among these possi­ bilities. Other divisive hierarchical techniques of concep­ tual clustering include DISCON and RUMMAGE. Both RUMMAGE and DISCON form monothetic classification trees in which any set of siblings in the tree are distin­ guished by their value along a single variable. In contrast, CLUSTER/2 allows arcs to be labelled by a conjunction of values across several variables, and thus CLUSTER/ 2

I

I

I

I

I

I

I

/

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I I

forms polythetic classifications. DISC ON, unlike both RUMMAGE and CLUSTER/2, discovers an optimal clas­ sification tree (in terms of the number of nodes in the com­ pleted tree), whereas the latter two algorithms seek only to independently optimize the division of each node, in the hopes that the resultant trees will be of 'high quality'. MKlO by Wolff represents an agglomerative hierarchical technique. Conceptual clumping techniques include IPP and UNIMEM by Lebowitz and GLAUBER by Langley et .al.. Each of these systems builds classification schemes equivalent to reentrant, acyclic graphs, where each node represents a cluster, and objects may be included in mul­ t iple clusters.

The view of conceptual clustering methods as exten­ sions to methods of numerical taxonomy has served as a vehicle for presenting the input-output behavior of anum­ ber of algorithms. For a better understanding the process­ ing characteristics and utility of each of these techniques we turn to the view of conceptual clustering as learning by observation.

III. CONCEPTUAL CLUSTERING AS LEARNING

An alternative view of conceptual clustering relates this task to the well-studied problem of learning from ex­ amples. Both the conceptual clustering task and learning from examples are concerned with formulating some de­ scription that summarizes a set of data. In learning from examples, a tutor specifies which objects should be as­ signed to which class, and the learner must characterize each class. In conceptual clustering the learner has the two-fold task of creating object classes as well as charac­ terizing these classes. Thus there are two problems which must be addressed by a conceptual clustering algorithm, one of which is shared by processes of learning from ex­ amples.

The aggregation problem is the problem of distin­ guishing subsets of an initial object set, that is the formation of a set of classes, each defined as an ex­ tensionally enumerated set of objects. The aggre­ gation problem is addressed by tasks of conceptual clustering and not by processes of learning from ex­ amples which assume a set of classes has been sup­ pliedby an external source (ie. a tutor).

The characterization problem is the problem of de­ termining characterizations (ie. concepts) for an ex­ tensionally represented object class, or each of mul­ tiple object classes. This problem has been exten­ sively addressed in work on learning from examples where object classes are presented by a tutor, and the learner is responsible for assigning a conceptual description to each class. In fact, the characteriza­ tion problem, as defined here, and the problem of learning from examples are the same. Conceptual clustering processes must address the characteriza­ tion problem since cluster quality, as we have stated, is dependent on conceptual descriptions which may be used to describe clusters.

We do not mean to imply that the aggregation and characterization (ie. learning from examples) problems are independent, simply that they may be usefully mod­ ularlized, thus allowing us to make use of the wealth of information regarding learning from examples in analyz­ ing and formulating methods of conceptual clustering.

Given this view, a natural approach to solving the conceptual clustering problem involves first solving the aggregation problem, and then using traditional methods of learning from examples to solve the characterization problem. In fact, present conceptual clustering algorithms can be framed in this way. For instance, GLAUBER forms classes based on the most commononly occuring relation (defined over an object set) and then characterizes these classes with respect to the remaining relations. MKlO employs a very similar technique (in fact, GLAUBER's method is based on MKlO). UNIMEM and IPP construct a number of alternative classes each of which is based on the predictive features (ie. variable values) shared by all class members, and characterized by a conjunction of all predictable features shared by class members. 2

Both RUMMAGE and DISCON use a list of user­ specified attributes to form possible partitions over an object set. RUMMAGE considers a number of parti­ tions, each implied by the values of a distinct attribute and selects that partition (ie. clustering) which possesses the 'best' conceptual descriptions of objects over the re­ maining attributes. Thus, RUMMAGE solves the aggre­ gation problem by using individual attribute values to imply possible clusters (the values of a single attribute collectively imply a clustering), and then utilizes a learn­ ing from examples subroutine to characterize clusters in terms of the remaining attributes. RUMMAGE applies this method recursively to each of the resulting clusters, thus tracing out a single hierarchical classification scheme. Like RUMMAGE, DISC ON uses attribute values to imply possible partitions, thus solving the aggregation problem. Unlike RUMMAGE, DISCON does not construct an ex­ plicit description of the devised clusters over the remain­ ing attributes, but simply calls itself recursively on each of the possible clusters, thus forming a classification tree over the objects of each cluster with respect to the remain­ ing attributes. Both RUMMAGE and DISCON are to a greater or lesser extent based on Quinlan's ID3 program for learning from examples (Quinlan, 1983) An abstrac­ tion of the aggregation processes of both RUMMAGE and DISCON is given in figure 1.

2 See Lebowitz (1983) for definitions of predictive and predictable

features.

The Partitioning Module of Michalski and Stepp's CLUSTER/2 system uses a more experimental solution to the aggregation problem than the systems described above. Given the task of dividing the observed objects into N disjoint classes, the system initially selects N seed objects (initially this is done randomly). The system treats each such seed as a positive instance of some class and treats the other seeds as negative instances of the same class. The program then derives maximally-general discriminant descriptions for each class implied by the seeds. 3 The result is that for each seed a number of de­ scriptions (ie. concepts) are derived, each of which cov­ ers that seed and no other seed. Each description of each seed also covers some number of non-seed objects which are assigned to the same class as the appropri­ ate seed. Once all objects (seed and non-seed) have been classified with respect to the maximally-general discrim­ inant descriptions, these maximally-general descriptions are 'thrown out', and maximally-specific characteristic de­ scriptions are derived for each defined object class. By selecting one description for each seed, a set of (possibly overlapping) clusters, that is a clustering, is implied which classifies the input object set. A pictorial summary of the above process is given in figure 2.

The reasons for this seemingly roundabout means of aggregating and describing object classes are best expli­ cated in Michalski (1980}. By first formulating maximally­ general descriptions, any clustering implied by any combi­ nation of maximally-general descriptions (one description for each seed) can be shown to contain at least one clus­ ter which covers an arbitrary object. Thus by first formu­ lating maximally-general descriptions, CLUSTER/2 guar­ entees that every observed object can be classified. Once all objects are classified, derivation of maximally-specific descriptions serve to reduce the possibility of overlapping clusters with respect to unobserved objects. A 'fix-up' op­ eration is then employed to make all possible clusterings mutually-disjoint.

3 See Michalski (1983) for definitions of discriminant and character­ istic descriptions.

IV. OTHER DIMENSIONS FOR CHARACTERIZING CONCEPTUAL CLUSTERING ALGORITHMS

We have thus far characterized conceptual cluster­ ing algorithms in terms of the structuring of the clus­ terings they produce, and in terms of the ways in which each technique deals with the problems of aggregation and characterization. We now define dimensions relating to search, along which we may describe the subprocesses of conceptual clustering. We begin by discussing dimensions of characterization (ie. learning from examples).

A. Searching the Space of Characterizations

As we have seen, the characterization component of the conceptual clustering task is identical to the well­ studied task of learning from examples. Thus, we can em­ ploy previous results from the machine learning literature in our analysis of this component. For instance, Mitchell (1982), Dietterich and Michalski (1983}, and Langley and Carbonell (1984) have proposed various dimensions along which methods for learning from examples may vary. Mit­ chell points out that the space of concept descriptions is ordered according to generality. This ordering leads to three alternative schemes for systematically searching the space of hypotheses. First, one may start with a very spe­ cific hypothesis, and move toward more general descrip­ tions in search of one that covers the instances; this ap­ proach may be called learning by generalization. Second, one may start with a very general hypothesis, and move toward more specific descriptions that cover the data; this may be called learning by discrimination. Finally, one may search in both directions, hoping to converge on the correct hypothesis; this is Mitchell's version space strat­ egy.

Applying this analysis to the characterization com­ ponents of the existing conceptual clustering systems, we find that UNIMEM/IPP and GLAUBER use general­ ization in characterizing their groupings. Recall that CLUSTER/2 forms characterizations at two points in its processing: the derivation of maximally-general discrimi­ nant concepts uses a discrimination approach; the deriva­ tion of maximally-specific characteristic concepts uses a generalization approach. RUMMAGE and DISCON use attribute values to form a number of possible partitions, where each attribute value may be viewed as a maximally­ general discriminant concept of the object group it im­ plies. No discrimination or generalization is ~mployed in this process. RUMMAGE does however, use gener­ alization to derive characterizations of object groups over those attributes not used in partitioning the object groups. Wolff's MKlO does not form characterizations per se, though it does generate conjunctive descriptions based on co-occurrences.

A second dimension involves the method used to di­ rect search through the space of hypotheses. Some AI systems that learned from examples have used depth-first search to select hypotheses, others have used breadth­ first search, while still others have non-exhaustive meth­ ods such as beam-search and best-first search. The non­ exhaustive methods require some evaluation function to order hypotheses, so the same search technique may give different results depending on the evaluation function it employs. Because of the limited concept languages em­ ployed by each of the conceptual clustering systems dis­ cussed, there is exactly one maximally-specific concept description for any given object group, which is to say there is no (or only a degenerate) search occuring in most cases. Michalski and Stepp's CLUSTER/2 carried out a beam search in deriving maximally-general discrimi­ nant concepts, using evaluation functions supplied by the user (such as simplicity of class description). The for­ mation of maximally-specific characteristic descriptions in CLUSTER/2, as with all of the other systems, is deter­ ministic.

Third, one may distinguish between data-driven and model-driven learning systems. In data-driven systems, the operators for moving through the space of hypotheses require data as input; thus, these data direct the search through the problem space. In model-driven systems, some other knowledge is used to generate new hypothe­ ses, and the data are used only in the evaluation stage. CLUSTER/2, UNIMEM, GLAUBER, and MKlO employ data-driven characterization methods, while the remain­ ing systems can. be viewed as model-driven systems (to the extent that they form characterizations). However, the "models" used by DISCON and RUMMAGE consisted only of a list of attributes that might be used in construct­ ing a classification scheme.

A final dimension concerns whether all observations are processed together, or whether they are handled one at a time. The first situation may be called non-incremental learning, and is plausible for modeling scientific data anal­ ysis. The vast majority of conceptual clustering systems (CLUSTER/2, DISCON, RUMMAGE, GLAUBER, and MKlO) are all non-incremental learning systems. The sec­ ond situation may be called incremental learning, and is more plausible for modeling concept formation based on continuous interaction with one's environment. Of the ex­ isting conceptual clustering systems, only UNIMEM and IPP can be viewed as incremental learners. This dimen­ sion is associated with the entire conceptual clustering system, not only with the characterization component.

B. Searching the Space of Aggregations

As we have seen, conceptual clustering methods solve the aggregation problem as well as the characterization problem, suggesting another set of dimensions along which such methods may differ. In this case, two dimensions present themselves:

• Search control. One can imagine a conceptual clus­ tering system systematically considering all possible groupings, evaluating them, and then selecting the best. However, none of the systems we have con­ sidered employ such an inefficient approach. Upon inspection, we find that CLUSTER/2 uses a hill­ climbing method to home in on an acceptable aggre­ gation, using characterization techniques to evaluate its choices. In contrast, the remaining systems carry out only degenerate searches (of depth one) through the aggregation space, since they select their group­ ings in a one-step process.
• Nature of the operators. In order to understand why RUMMAGE, DISC ON, and most other sys­ tems require only one-step searches, we must ex­ amine the operators they use to generate candidate groupings. RUMMAGE and DISCON both require a user-specified list of attributes and their values; by selecting an attribute, these systems automati­ cally generate a candidate grouping (one for each value of the attribute), which can then be evaluated.

GLAUBER, MK10, and UNIMEM/IPP all accom­ plish the same effect in a more data-driven manner. Only in CLUSTER/2 do we find a less constrained operator, which selects seed objects that may or may not lead to a useful characterization.

C. Searching the Space of Hierarchies

We have seen that unlike systems that learn from examples, conceptual clustering methods must also deter­ mine their own aggregations. However, there remains an­ other issue that distinguishes conceptual clustering from the task of learning from examples. In the latter, one is generally concerned with forming concepts at a single level, while conceptual clustering usually focuses on gener­ ating hierarchies of concepts. Some numerical taxonomy methods (the optimization techniques) generate only sin­ gle level groupings, but most methods arrive at some tree of groupings.

The implication for our analysis of conceptual clus­ tering methods is clear - the search for aggregations and the search for characterizations are embedded within a higher level search through the space of classification trees. Moreover, we can classify the existing clustering systems in terms of two additional dimensions. These are:

• Direction of the search. Upon examining the existing conceptual clustering systems, we find that divisive (top-down) methods have been used by the majority, including CLUSTER/2, DISCON, and RUMMAGE. These systems start with a single class of obser­ vations, and proceed by subdividing the instances into classes, these classes into subclasses, and so forth. However, one can also imagine methods that begin with separate "classes" for each observation, joining these classes together to form larger classes, and joining these classes in turn. Such bottom-up (agglomerative) methods have been used by a mi­ nority of conceptual clustering systems, including GLAUBER and MK10. Other arrangements are also possible; for example, Mervis and Rosch (1981) have suggested an approach where one first forms classes of medium generality, and later forms both more general and more specific classes. UNIMEM/IPP behaves in roughly this manner and at any point in its processing classes of greater or lesser generality than existent classes may be added to the classifica­ tion.
• Search control. Conceptual clustering systems must somehow direct their search through the space of hi­ erarchies. Upon examining the existing systems, we find that CLUSTER/2, RUMMAGE, GLAUBER, and MK10 carry out only degenerate searches through this space. The reason is that their operators consist of techniques for finding optimal aggregations and characterizations. Search is involved at these lower

levels, but the result is an optimal extension to the hierarchical tree. In contrast, DISCON has degener­ ate search schemes at these lower levels, but carries out a best-first search through the space of hierar­ chies. It accomplishes this through an exhaustive look-ahead process, evaluating entire sub-trees and preferring those containing fewer nodes. UNIMEM and IPP also carried out search at this level, enter­ taining multiple organizations (thus using a form of beam search); however, these organizations might be revised later in the search, so backup was allowed.

Although these dimensions are similar to those presented for the characterization problem, it is important to note that the current dimensions are separate from those for characterization. For instance, CLUSTER/2 employed beam search to find maximally-general discriminant de­ scriptions, but employed only a degenerate search for de­ termining the best hierarchy.

V. CONCLUDING REMARKS

We have discussed the mechanics of a number of con­ ceptual clustering methods and defined dimensions which serve to clarify the differences and similarities between methods. Our bias has been that further work in con­ ceptual clustering is best facilitated by first understand­ ing these processes in terms of well-understood concepts. Following Michalski (1980), we have presented concep­ tual clustering as an extension of numerical taxonomy. Further, by framing conceptual clustering as a compo­ sition of aggregation and characterization processes, we have shown a relationship between conceptual clustering and methods of learning from examples. This dichotomy has led to a view of conceptual clustering processes as con­ ducting a three-tiered search: a search through a space of hierarchies; a search through a space of possible ag­ gregations; and a search through a space of conceptual descriptions.

It is our view that explicating conceptual clustering as multi-layered search will not only ease comprehension of existing methods, but facilitate work in a nillnber of still open problem areas. 4 One problem concerns the task of clustering structured objects, where object descriptions allow relations to be represented between attribute val­ ues of an object. Vere's TROTH system (Vere, 1978) is currently being investigated as a basis for a conceptual clustering system for structured objects. TROTH discov­ ers a minimal set of generalizations which cover a given set of relational production instances, where each production instance is a (before) state- (after) state pair. Each state representation is equivalent to a structured object repre­ sentation. TROTH traces out a hierarchical classification bottom-up and in many ways resembles an agglomerative approach to coneeptual clustering. A second area of inter­ est to us concerns the problem of utilizing information on the functionality of objects to aid the formation of useful clusters. An approach suggested in discussion by Nelson (1977) involves using domain-specific knowledge of object functionality to guide the search for possible aggregates, and to use perceptual information as the basis of char­ acterization. Distinct forms of knowledge may serve to guide the search for hierarchies. By distinguishing lev­ els of search we can more easily motivate and express the rules, heuristics, and descriptive languages, utilized at dif­ ferent levels.

4 See (Langley and Carbonell, 1984; Michalski and Stepp, 1983b) for comprehensive discussions of open problems in conceptual clustering.

ACKNOWLEDGEMENTS

We would like to thank Dan Easterlin, whose ter­ minology we partially adopted in describing conceptual clustering processes, and Dennis Kibler who pointed us to Vere's THOTH system as a possible basis for future work.