An Application of AI Techniques to Structuring Objects into an Optimal Conceptual Hierarchy

ABSTRACT

A aethod of "learning froa obaervation" 1a preaented which atructurea a collection of objecta into hierarchlea of aubcategoriea, auch that each aubcategory ia characteriaed by a conjunctive deacription involving relatione on aelected object attribute&. The conjunctive deacriptiona aprouting froa each node are ~tually diajoint and optimal aa a group accordiQ& to a flexibly defined criterion. Each level of the hierarchy ia deterained by an iterative proceaa which repetitively applies a veraion of the A* aearch algoritha.

Experiaenta with the prograa CLUSTEI/PAF iaplementing the method indicate that the obtained hierarchiea represent aolutiona which have a aiaple conceptual interpretation and which aeea to agree well with the way people atructure objecta.

I INTRODUCTION

The problea of intelligently atructurina a given collection of entitiea baa practical significance not only for applied aciencea in general, but alao for deaigning and iapl ... ntina AI ayateaa. For exaaple, knowledge about the structure underlying given data can help in reducing the search apace in problea aolvina, in organizing large data baaea (or rule baaea), in dividiQI knowledge acquisition taaka into useful aubcaaea, or in conciaely characteriaina a large collection of object& for human underatandina.

The problem of data atructuring can be viewed aa a problea of ·learning froa obaervation" ("learning without a teacher·). A aiaple fora of data structuring is cluatering, which deterainea a hierarchy of subcategories ("clustera·) within a given collection of objecta. In the traditional methods of clustering, developed in cluater analysia and numerical taxonoay (6), the baaia for forming aubcategoriea 1a a ·degree of aiaUarity" between object&: the aubcategoriea are collection& of objects whoae intra-cluater aiailarity ia high and inter-cluster aiailarity is low.

The traditional cluatering techniquea have one major diaadvantage. Since the only baaia for forming cluster& ia the degree of object aiailarity (which ia a measure dependent only on propertiea of

This reaearch waa aupported in part by the National Science Foundation grant No. HCS-79-o6614, the Univeraity of Paria IX, and INRIA (France).

AN APPLICATION OF AI TECHNIQUES TO STRUCTURING OBJECTS INTO AN OPTIMAL CONCEPTUAL HIERARCHY

lyaaard s. Michalak! and Robert E. Stepp

Departaent of Computer Science Univeraity of Illinoia at Urbana-Champaign

coapared objects), the reaulting cluatera do not neceaaarily have any aiaple conceptual interpretation. The problea of determining the · .. aning" of the obtained cluatera ia aimply left to the reaearcher. Thia disadvantage 1a aignificant becauae a reaearcher typically wanta not only to find cluatera, but alao wanta to find an explanation of the cluatera in huaan teraa.

Thia paper ia concerned with the problem of deteraining a hierarchical atructure underlying a given collection of objec.u, in which each node correaponda to a aubcategory of objects characterized by a conjunctive concept (a logical product of relatione on aelected object attributes). Structuring objecta into auch ·conjunctive hierarchiea· ia called conjunctive conceptual cluaterina.

The idea of conceptual cluatering and a general .. thod for deteraining conjunctive hierarchiea waa introduced in (3). This paper diacuaaea in more detail one specific algorithm (iaplemented in the proaraa CLUSTER/PAF) and illuatratea it by a practical problea found in auaicology.

II THE SIMILARITY MEASURE VERSUS CONcEPTUAL COHESIVENESS __ _

The aiailarity between any two objecta in the population to be clustered ia characteriaed in the conventional data analyaia aethoda by a aingle nuaber--the value of the aiailarity function applied to ayaboUc descriptions of objecta ("data pointe·). Theae descriptions are typically vectora, whoae co.ponenta repreaent acorea on selected qualitative or quantitative variablea uaed to deacribe objects. Frequently a reciprocal of a distance measure ia uaed as a aiailarity function .

Since the aiailarity function ia aolely dependent on the propertiea of individual objects , the traditional aethoda are fundaaentally unable to capture the "Ceatalt propertiea" of objects that characterize a collection of object& aa one whole and are not derivable by conaidering objects individually . In order to detect auch properties, the syatea auat know not only the data pointe, but alao certain "concepta·. To illuatrate this point, let ua consider a problea of cluatering data pointe in Figure 1.

·

·

Figure 1. An illustration of conceptual clustering

A person considering the problem in Figure 1 woul d typically describe it as .. two circles ... Thus, the points A and B, although being very c l ose , are placed in separate clusters. Here, human solution involves partitioning the data points into groups not on the basis of pairwise distance between points, but on the basis of .. concept membership... This means that the points a re placed in the same cluster if together they r epr esent the same concept. In our example the concept is a circle.

This idea is the basis of conceptual clus tering. From the view of conceptual clustering, the .. similarity.. between two data points A and B, which we will call the conceptual cohesiveness, depends not only on these points but also on a set of concepts which are available for describing A and B together. In this paper the concepts into which objects are structured are conjunctive descriptions involving relations on se lected object attributes.

III TERMINOLOGY

This section te rmi nology. A conta ined in [3] . gives a brief overview more detailed presentation of is

A. Variables and Their Typea

Let xl,xz, ··· ,xn denote discrete variables which are selected to describe objects in the population to be analyzed. For each variable a va lue set (or domain) is defined, which contains a ll possible values this variable can take for any object in the population. We shall assume that the value sets of variables xi, i·1,2, ··· ,n are finite. In general, the value sets may differ not only with r espec t to their size, but also with respect to the st r uc ture relating their elements (reflecting the scale of measurement). We distinguish between nominal (qualitative), linear (quantitative), and s tructured variables , whose domains are unordered, linear, and tree ordered sets, respectively. The structured variables represent generalization hierarchies of related concepts.

B. Event Space and Syntactic Distance

An event e is defined as any sequence of values ~ariables xl,xz, ··· ,xn· The set of all poss i ble events, r, is called the event space. The syntactic distance, o(el,ez), between two events el and ez is the number of variables which have di f ferent values in e1 and ez.

c. Selectors

A relational statement [xi# Ril· where Ri, called the reference, is a list of elements from the domain of xi, and # stands for one of the relational operators ~ ~ ~. i! called a ~ selector or, briefly, a selector. A selector [xi I RiJ is said to be satisfied by an event e · (xl,x2····,Xn), if the value of variable xi in e, is in relation# with any element of Ri.

o. L-complexes and ~-complexes

A logical product of selectors, written -as a concatenation of selectors, is called a ~ logical complex (or briefly, an ! - complex). An event e is said to satisfy an 1-complex if values of variables in e satisfy all the selectors in the l - complex · For example, event e · (2,7,0,1,5,4,6,3) satisfies the l-complex [xr·2,3)[x3~3][xs·3 ·· B][xa·long] (where x1 is a nominal variable, x3 and xs are linear variables and xa is a structured variable) if the value of x 8 in e (i.e., 3) is in the class .. long,·· as defined by the structure of the value set of xa· An l-complex can be viewed as a symbolic description of the events which satisfy it. For example, the above l-complex is the symbolic description of all events in which x1 is 2 or 3, x3 is smaller than or equal to 3, xs is between 3 and 8, and xa has a value belonging to the category .. long.. {the values of any other variables are irrelevant).

Any set of events for which there exists an l-complex satisfied by these events and only by these events is called a set-complex or, briefly an a-complex. Henceforth, ~a is an l-complex, then by a we will denote the corresponding a-complex, i.e., the set of events described by the l-complex. For simplicity, whenever the distinction between an 1-complex and an a-complex is not important, then we will use just the term complex.

E. Sparseness

Let E be a set of events in r, which represent objects to be clustered. The events in E are called data events (or observed events) and events in r \--E--(~ events in r which are not data events) are called empty events (or unobserved events). Let a be--&n a-complex which covers (includes) some data events and some empty events . The number of data events (points) i n a is denoted by p(a). The number of empty events in a is called the sparseness and denoted by s(a). The total number of events in a is thus t(a) · p(a) + s(a).

The l-complex can be viewed as a generalized description of the data events contained in the corresponding a-complex. The sparseness, as defined above, can be used as a simple measure of the degree to which the l-complex generalizes over (or .. fits .. ) the data events. If the sparseness is zero, then the description covers only data events ( .. zero degree of generalization .. ). As the sparseness of the complex increases, so does the degree to which it generalizes over the data events. A related but more precise measure of the degree of generalization is the information­ theoretic uncertainty of the location of data events in the complex [3].

*VL1 is the variable-valued logic system one, which uses such selectors [2].

F. Star

The (theoretical) star G(eiF) of event e against event set F is formally define~[3y-ag-the set of a~aximal under inclusion a-complexes covering the event e and not covering any event in F. (An a-complex a is maximal under inclusion with respect to property P, if there does not exist an a-complex a* with property P, such that a c a*.) Such maximal complexes, however, have high sparseness and thus are not directly useable in our approach. Therefore, the algorithm produces a reduced star. The reduced star is obtained from the theoretical star by transforming each complex into a new one that covers the same observed events but has the minimum sparseness (or, in general, minimizes a certain criterion).

G. Cover

Let E1 and E2 be two disjoint event sets, E1 n E2 · ~· A cover COV(E1IE2) of E1 against E2, is any set of a-complexes, {aj}jeJ· such that for each event e E E1 there is an a-complex aj, j E J, covering it, and none of the complexes aj cover any event in E2· Thus we have:

A cover in which all a-complexes are pairwise disjoint sets is called a disjoint cover. If set E2 is empty, then a cover COV(E1IE2) · COV(Ell~) is simply denoted as COV(El)· A partition of data events into k subsets, each contained in one set­ complex of a disjoint cover is called a conjunctive k-partition. The corresponding !-complexes constitute conjunctive descriptions of these subsets. A simple measure of the .. fit.. of a k­ clustering to the data events is the sparseness of the k-partition defined as the sum of the sparsenesses of the complexes in the partition.

IV THE METHOD AND ITS IMPLEMENTATION

algorithm for implemented in consists of an described in This section describes the conjunctive conceptual clustering program CLUSTER/PAF. The algorithm inner layer and an outer layer, sections IV-A and IV-C, respectively.

A. Inner layer (algorithm PAF)

The inner layer of the algorithm (called PAF) was introduced in [3] . Its function can be described as:

• Given: · a collection of events to be clustered,
• the number of clusters desired (k),
• the criterion of k-clustering optimality, Find: a conjunctive k-partition of the collection of events that is optimal according to the criterion of k-clustering optimality.

The flow diagram of the algorithm PAF is shown in Figure 2.

Given: E - a set of data events

k - the desired no. of 'clusters

A - the evaluation functional

PAF works iteratively, starting with a set of k initial, randomly chosen seed events ( .. seeds .. ) from the given collection of events. The seeds are used to determine a set of complexes, which constitute the first conjunctive k-partition of the event set. Subsequent iterations consist of two repeated steps:

1 given k complexes, determine the data events (clusters) covered by them,

2 given clusters of data events, determine new .. seeds, .. and then a new set of k complexes (a conjunctive k-partition).

The process continues until a termination criterion is satisfied (a local optimum is achieved). The general structure of the algorithm is based on the so-called dynamic clustering method [1].

B. Generating.! ~-partition from ''seeds' '

The process of determining a k-partition from seeds involves determining a reduced star of each seed against other seeds, and then selecting complexes fro~ the stars and modifying them in such a way that they constitute a k-partition. The selection is done by a best-first search method.

The existence of such a solution is guaranteed by the "sufficiency principle" proved in [3].

The theoretical star G(eiF) has been defined in section III as the set of maximal complexes covering event e and no events in the set F. Here is a simple algorithm to produce such a star. Assume first that F·{el}, e1~e. To generate the star G(elel) one determines all variables in e that have different values in e1· Suppose, with no loss of generality, that they are xl,x2,···,Xk, and that el a (rl,r2,···,rk·····rn)· Assuming that the variables are nominal, the complexes of the star G(ele1) are [xi~ riJ, i·l,2, ··· ,k, since these are the largest complexes which cover e and do not cover e1· The number of complexes in a star G(eiF), when F is a single e;ent, is at most n (the number of variables), and at least 1, since e1~e. Assume now that F · {e1,e2, ··· ,es}· A star G(eiF) is constructed by building first stars G(elei), i·1, 2, ··· , s, and then set-theoretically multiplying these stars by each other, using absorption laws to eliminate redundancy.

This theoretical star is replaced by a reduced star in which complexes cover the same observed events but have the minimum sparseness. To do that, for each complex of the theoretical star observed events contained in it are determined. The list of all values taken by each attribute in the observed events is used as the reference (see section III) of the selector in the corresponding complex of the reduced star (i.e., a refunion operation is performed, as described in [3]). If the reference is equal to the value set (or implies the value set in the case of linear or structured attributes) then the selector is removed.

The upper bound on the size of a star is nm, where n is the number of variables and m is the number of events in F. Absorption laws will usually eliminate many redundant complexes, but the size of a star may still become unmanageable. Therefore a bounded star is used, which has a specified upper limit, MAXSTAR, on the number of complexes it may contain. Whenever a star exceeds this number, the complexes are ordered in ascending order according to sparseness (or, in general, to any assumed clustering optimality criterion; see end of this section) and only the first MAXSTAR complexes are retained.

The above two steps produce a bounded reduced star. For simplicity, from now on by star and the notation G(eiF) we will mean a bounded reduced star.

At each iteration of algorithm PAF, k stars are produced, each of a single seed event against the remaining k-1 seed events. From each star one complex is selected in such a way that the resulting set will consist of k disjoint complexes (be a conjunctive k-partition), and be optimal according . to the assumed criterion. If un-bounded stars were used, each could contain up to N·n(k-1) complexes, and therefore up toNk sets of complexes would have to be inspected in order to determine the optimal k-partition. To combat this immense search problem the best-first search strategy is used. This search uses a form of algorithm A* {Nilsson [SJ).

Assume that k events ("seeds") el,e2····,ek, have been selected from the collection E and k stars Gi · G(eilremaining seeds) have been generated. For simplicity, we will assume that the criterion of clustering optimality is simply to minimize the total sparseness of complexes in the k-partition. At each level of the search tree, a complex is selected from the star corresponding to this level and is added to the partial partition (a sequence of fewer than k complexes). The selected complex is the one which most likely will lead to the optimal k-partition. This procedure avoids testing (possibly very many) clusterings, for which it is possible to predict that they will not be optimal.

Figure 3. A search tree illustrating algorithm PAF

Branches emanating from a node at level i represent complexes in star Gi· A path from the root to a node at level i represents a partial k-partition with i complexes. When i·k, the path represents a complete k-partition.

In the first step, the sequence of complexes a~, a2,···, ai is determined, where ay is the complex in star Gi with the smallest sparseness. In the next step, node (1) (Figure 3) is expanded by pairing the "beat" complex in G1, i.e., ay, with every complex in G2· If the complexes intersect, a special procedure NID modifies them so that they become disjoint. If NID cannot make the complexes disjoint, the path is abandoned (procedure NID is described in detail in [3]). Every so obtained pair of complexes is a partial k-partition with i·2 complexes. This process is repeated for the other complexes in G1, in the order of their increasing sparseness. Nodes corresponding to all these clusterings (first generation nodes) are assigned a value of the evaluation function: f · h + g, where h is is the sparseness of the obtained partial disjoint cover and g is the expected cost of the remainder of the k-clustering to be determined (the sum of the sparsenesses of the complexes along the path from node i+l to leaf node k).

A lower bound for g is determined on the basis of complexes a~ generated in the first step. If any of these complexes intersect, procedure NID transforms them into certain "core" complexes, of which it can be proven [3], that the sum of their sparsenesses is a lower bound on the sparseness of the optimal k-partition constructed from complexes

of the stars.

According to the algorithm A*, the node to be expanded at the next step is the one which is associated with the lowest value of the evaluation function. The order of expanding nodes in the tree in Figure 3 is shown by numbers in circles. The value of the evaluation function associated with each node is given in parentheses. If complete (not-bounded) stars are used, this algorithm will produce the optimal k-clustering (i.e., in this case, a k-clustering with the minimum total sparseness).

The method can simultaneously use not just one, but several criteria of clustering optimality. In addition to sparseness, these other component criteria include [4]:

• maximizing inter-cluster differences,
• maximizing essential dimensionality,
• maximizing simplicity of cluster representations, and
• maximizing uniformity of cluster populations.

C. Outer layer of CLUSTER/PAF

As described above, the inner layer (PAF) determines an optimal or suboptimal k-clustering of a given collection of events. The outer layer performs two loops, one iterative and one recursive. The iterative loop repeats algorithm PAF for a sequence of values of k (say, k·2,3, ··· ,7) in order to find the value of k for which the most desirable clustering of the given event set is obtained. It is assumed that interesting solutions should have only a few (e.g., less than 7) different clusters.

The recursive loop applies the above process recursively in order to create a hierarchy of clusterings. In the first step, the process is executed for the initial event set E, and a collection of subcategories (clusters) of E is determined. Consecutive steps repeat the same operation for each event set (cluster) obtained in the previous step.

The obtained hierarchy grows in a top-down fashion until a "continuation-of-growth" criterion fails. This criterion requires that the "fit" (measured by sparseness) of the complexes to the events they describe be better by a certain threshold at each next level of the hierarchy. When this criterion is not met, the latest obtained subcategories become leaves of the hierarchy.

The algorithm described above implemented in program CLUSTER/PAF, has been written in

PASCAL.

V A MUSICOLOGICAL EXAMPLE

This example illustrates an application of the described method to structuring a collection of one hundred old Spanish folksongs.

The folksongs were characterized by 22 musicological attributes, such as degree of rubato (rhythmic freedom), tonal range, style (monophonic vs. polyphonic), etc. The attributes and the data for the experiment were provided by musicologist Pablo Poveda who studied this problem using traditional methods of numerical taxonomy [6]. The results obtained by those methods, however, were very difficult to interpret because they do not provide any description of the generated clusters.

The top five levels of the conjunctive hierarchy of folksongs produced by CLUSTER/PAF are presented in Figure 4. The criterion of clustering optimality was "minimizing the total sparseness. The branches in the hier~rchy have been labeled with the particular characteristic of the folksongs which discriminates between the left and right subcategories. The number of clusters (k) formed at each level was 2 to meet a requirement imposed by the musicologist.

Tips of the hierarchy marked by a1,a2·····a11

represent groups of songs (the number of songs is indicated above the tip), whose complete description consists of properties indicated along the path from the root to the tip, and some additional properties not shown in the figure. (These additional properties are less relevant for classifying the songs, as they occur at the lower levels of the hierarchy.) For example, the group denoted by a4 has the following complete description:

[style-monophonic] [rubato-low][tonal range·low] [type·secular] [instruments-no] (A)

A [no. of tones·5 ·· 8](panegyric·no] [tension·! ·. 3] [no. of phrases·l ·· 2][melisma·0 ·· 2][dance·no] (B)

Part A contains properties shown in the (Figure 4) while part B contains properties selected by the program complete set of attributes. hierarchy additional from the

One interesting aspect of the determined hierarchy is that the value sets of some variables have been split into ranges. These ranges can be considered as new constructed (generalized) values of variables. For example, the range of the degree of "rubato" has been split into two ranges 0 ·· 3 and 4 ·· 5, which can be described as "low" and "high," respectively (see complex a4). Similar partitioning of value sets into ranges of values was found for the degree of embellishment, the degree of melisma, the tonal range, and the number of tones in the song. It should be noted that although the nodes in this particular hierarchy are marked by single attributes, the method, in general, labels attributes. the nodes by products of

VI SUMMARY

The described method for conjunctive conceptual clustering determines a hierarchy of subcategories characterizing a collection of objects. The subcategories are formed in such a way that an appropriate generalization of the description of each subcategory yields a single conjunctive statement. The difference between this method and methods of numerical taxonomy is in extending the concept of the measure of similarity into a more general notion of "conceptual cohesiveness". Such a measure takes into consideration not only the distance between the objects, but also their relationship to other events and, most importantly, their relationship to some predetermined "concepts" (in our case, conjunctive statements). The musicological example described in the paper (as well as other experiments performed with CLUSTER/PAF) indicate that this method has the potential to be a useful new tool for analyzing data.

ACKNOWLEDGEMENTS

The authors thank Mr. Pablo Poveda for ~roviding data used in the musicological experiment and for many helpful comments.