A Nonparametric Valley-Seeking Technique for Cluster Analysis

I. Introduction

It is not difficult to i~gine a collection of object· whole members can be classified into two or more categories limply on the ba1is of their ob1ervable characteristic·. It is not always neces1ary to rely on a similar collection of labeled objects as a ba1i1 for classification. For example, biological taxonomists have classified living things into a large number of meaningful categories . Yet at no time in history did any plant or ani~l bear a label. Rather, categories have been e1tablished without superviaion.

Recently, aethods. for automatic un1upervised classification, or clustering, have been proposed. A machine algorithm for clustering can be a valu­

able tool in

1. pattern recognition - Often, a training set of labeled objects is difficult or impo11ible to obtain. Further, a known class of objects may contain unknown
2. subclasses.

necessary because an exhaustive check of all possible classifications is usually impractical . Thus, for our purpo1es, the clustering problem con1ists of two basic elements :

1. definition of a clu1tering criterion

and

• ii) construction of a clustering algorithm.

The idea of using a clustering criterion i1 not new. Many procedurea reported in Ball's Iurvey (1) are ba1ed on criteria. Friedman and Rubin (2) pre1ent a cla1s of criteria and di1cuss the property of transfo~tion invariance . Fukunaga and Koontz (3) show condition· where the criteria of (2) become equivalent to a simpler criterion. Watanabe (4) proposes a criterion, which he calls coheaion, which can detect more subtle relationship· among object· than pairwise similarities .

Pre1ently, no universal clustering criterion haa been defined. This is simply a con1equence of the lack of a preciae mathe~tical definition of a cluster. That ia, the clustering problem i1 one whole aolution cannot be characterized in a definite way. Thus, in order to derive a ~theaatical criterion, we must postulate a rigorous definition or clultering. Thi· poatulate can then be tested by experiments with objects

whole clasa 1tructure i1 known and well defined.

The remainder of this paper consists of four section· and a ·u ... ry. In the next 1ection, (section II) we pre1ent our characterization of the clustering problem and compare it with other notions. We will then u1e thi1 characterization to derive a criterion. In the following section we will state and di1cu1s a general algorithm for finding the cla11ification which extremizes our criterion. Section IV concern· the aly.pto­ tic behavior of the procedure , i . e., what bappen1 when the number of objects i1 very large . Re ­ sults of computer experiments are given in 1ection

v.

II. A Clu1tering Criterion

The criterion derived in this section i1 baaed on the notion that information il lo1t when object· are repre1ented only by cla11 l1bela. Suppo1e that each member of a collection of N objects is repreaented by an L-dimenlional vector. Then the set of N vector·, {! 1 , ·· · ,~}, contains all of the available information concerning the objects. The clustering operation re~laces this 1et of vectors withe set of labels, fut·····UN}. The i-th label, ~· i1 an integer between 1 and M (M ~ N), and denotes the cla1s to which !i is a1signed. The label set contains leas informa­ tion about the objects than does the vector set. Therefore, clustering is viewed here as a data reduction algorithm which destroys information.

This losa of info~tion can be viewed as the representation error committed by r eplacing

(! 1 , ... ,~} with (~, ·· · ,~}. A quantitative

.. aaure of thia error can aerve as a cluatering criterion to be ·inimized. There are at leaat two waya to derive a nu·rical ·aaure of repreaenta­ tion error. The ·thod which haa been uaed moat often in the pa1t ia to .. aaure the error commit­ ted by uaing a repreaentative vector, £<wt>· aa an eati .. te of !i· An error vector can be de­ fined u

If £(j) ia the ·an of claas j, i.e.,

where N is the population of class j, then!!!. is the totJl intragroup acatter matrix. Several criteria which are functions of !!!. are discuased in (2) and (3).

An alternate definition of representation error ia uaed in the preaent development. We will concern ouraelvea with the error committed in eatimating diatancea between pairs of vectors. Let d~(!i·!j) be the euclidean diatance between ~ an !j'

Further, let d (w ,w) be a auitably defined .. tric of inte~cl1ssjdiatances. For example

or

Then a measure of distance representation error, which will be used as a clustering criterion, is

where f(~, ! 1 ) is a set of weighting coefficientL This kind of ~riterion is often used to measure .. pping error and cluatering ia a kind of mapping. However, aome apecial considerations are import­ ant in ita use as a cluatering criterion. First of all, not all of the distances are euclidean. A more important point, however, ia the fact that the wi'a are variables and the Xi's are fixed. Due to the discrete and unordered nature of the Wf'a, ordinary aradient methods cannot be uaed to minimize J.

Criteria of the same form as J have been used in hierarchical clustering. In hierarchical cluatering, objects are classified according to a diverging tree structure. A tree metric is defined which numerically defines the distance between two objects according to their position on the tree. The degree of fit between the euclidean distances and tree distances is used as a measure of validity of the classification tree (5,6).

The general criterion, J is too cumberaome to use in practice. The summation contains N2 terms in general. Therefore, we would like to assign zero weight to most of the terms. Suppose f satisfies

If R is sufficiently imated as small, then J can be approx-

A specific example of J 1 follows when f is defined by

Since fR is aymmetric with respect and since dw(wi,u..i) · 0, i·l, ... ,N of any metric), we can write J 1 as to !i and !j (a property

where the notational equivalence

is implied.

JlR assigns a nonzero. penalty for each pair of vectors closer together than R and classified into different classes.

If [6] is taken as the definition of dw, the following special cases of J1 and J1R result:

where

J2R is the simplest criterion we will derive. It is equal to the total number of distinct pairs of vectors separated by a distance less than R and assi&ned to different classes. We will some­ times refer to J 2R as · the fixed neighborhood penalty rule. The remainder of this paper mainly concerns J 2R.

The following properties of J 2 R support its use as a clustering criterion.

i) Computation For a given classification, J 2R is evaluated by a counting process rather than by complex calculations. Since the vectors are fixed, the neigh­ boring pairs need be determined only once.

• ii) Storage When R is sufficiently small, the number of neighboring pairs of vectors is moderate. The storage requirement is governed primarily by
• this number.
• iii) Classification Contributions to J 2R come from pairs of vectors near the boundaries separating classes. Thus, it is preferable for the boundary to pass through a region of low vector concentration. This kind of classifica­ tion is quite reasonable when there is no supervision available.

At this point, the reader may wonder if a K nearest neighbor penalty rule can be defined. The answer is yes, since we can write

where

Notice that f is not symmetric. Although the K nearest neigh~or penalty rule has a valuable counterpart in supervised pattern recognition, it is unsuitable in the present case. The K nearest neighbor rule does not favor one region over an­ other because of density. Therefore, it may well prescribe a boundary through a mode in the vector

distribution.

At this point, we have a family of nonpara­ metric criteria with three levels of complexity. The parent criterion, J, is the most complex and is in the closest accord with our original concept of clustering (distance preservation). Its descendants are J1 followed by J 2, with special cases JlR and J 2R. Criteria at the J1 level are more general in that they allow the penalty to be class dependent, but J2R is easier to· implement and admits an interpretation which seems very suitable. Unfortunately, criteria of the J 1 level and below have an absolute mini­ mum of zero when all vectors are assigned to the same class. This is not a serious problem in practice because there will be local minima corresponding to more interesting classifica­ tions. The degenerate case is easily detected.

We have not specified how to choose either the number of classes, M, or the region size, R. We have no rigorous theory to rely on here, and we can only offer suggestions based on experi­ mental results. Therefore, we postpone discus­ sion of these points until section V.

III. The Clustering Algorithm

The algorithm for finding the optimum assignment with respect to a given criterion is the second essential ingredient of clustering. Although clustering need not take place in real time, there are still practical constraints which rule out inefficient procedures, such as exhaustive searching. We have made use of a general type of algorithm. This algorithm can be applied to a wide variety of criteria, but in the special caaes of J2R it becomes particu­ larly easy to implement.

Consider a criterion of the form

where

and

The assignment, D, is variable and the configura­ tion, ~. is fixed. We are seeking an assignment, Q*, such that

Because of the discrete and unordered nature of D. ordinary gradient methods cannot be used. Still, it is possible to specify an iterative search based on first order variations in J with respect to D· Let D(k) the assignment at the kth step. If the rth vector is reclaasified from its present class, wr(k), to class s, then the change in J, AJ(r,s,~, is given by

The succeeding classification of ~r' u:r(k+l), should be the one which yields the most negative change in J. Therefore, the following clustering algorithm is proposed.

Step 1: Choose an initial classification, 9(0).

Step 2: Having determined the kth classi­ fication, calculate AJ(r,s,k) for r·l, ··· ,N and s·l, ··. ,M.

Step 3: The k+lst classification is deter­ mined by

Ties involving ~(k) are resolved in its favor. Other ties are resolved arbitrarlly. Step 4: If any vector is placed in a new class, return to Step 2 and repeat.

OtheNise, stop.

Note that all computation occurs in step 2 and the vectors are reclAssified simultaneously in step 3.

There is no guarantee that this algorithm will converge. Even if it does, there is little we can say about the strength of the minimum obtained. Fortunately, empirical evidence seems to favor this procedure. Fukunaga and Koontz

(7) have successfully used a variation of this algorithm earlier.

The algorithm, in effect, applies a decision rule at each iteration. Let us first consider JlR of [11). Omitting the iteration index, k, for simplicity, we have

Eq. [23) can be expressed as the sum two terms, one of which is independent of s. .Thus we can reclassify each !r on the basis of an abbreviated decision function, n1R(r,s) where

In the case of J 2 R, the fixed neighborhood penalty rule, the decision function is

The left hand side of [251 is a constant minus the number of vectors within a distance R of !r which are assigned to class s. The algorithm can be restated as follows for D2R·

Step 1: Choose an initial classification.

Step 2: For each vector, !r· count the number of vectors within a distance R of !r which are assigned to each class.

Step 3: Reclassify each !r to the class with the largest number of members within a distance R of !r·

Step 4 : If any vector is placed in a new class, repeat from step 2. Otherwise, stop.

This procedure, which follows from applica­ tion of the general algorithm to a specific criterion, J2R· is a valley seeking technique. To see this, consider vectors along the boundary separating class s 1 from class s2 at the kth iteration. Suppose there is a heavier concentra­ tion of vectors on the s, side of the boundary . Then vectors near the boundary are reclassified into class s 2 . Hence, the boundary moves into the region previously assigned to class s1. Therefore, the boundary moves away from the higher concentrations and toward valleys in the distri­ bution.

Two kinds of difficulty may arise when the fixed neighborhood decision rule is used. First of all, the algorithm may get stuck with the boundary passing through a region of relatively sparse population when better boundaries exist. Secondly, the boundary may diverge, leaving all of the vectors in a single class. Both of these difficulties are combatted by altering the initial assignment, ~(0), and adjusting the con­ trol parameter, R.

The clustering algorithm and the clustering criterion together make up a clustering proce­ ~· The clustering procedure has become the iterative application of the fixed neighborhood decision rule. We can easily apply ·it to numerical examples, and we do this in section V. First, however, let us aee how the procedure behaves when N is very large.

IV. Asymptotic Behavior

The performance of the clustering algorithm developed in sections II and III can be studied analytically when N is very large. In this section, we will derive the asymptotic version of o2R and discus& its properties. The asympto­ tic properties provide acme in&ight into the general behavior of our procedure. They also auggest how the procedure can be expected to perform with finite data sets.

Let us first rewirte the expression for o 2 R, normalizing by a factor of 1/N.

The first term of r26l is independent of s. Therefore, choosing the minimum of o 2 R is equiva­ lent to choosing the maximum of

Let Qs be the set of all vectors assifned to class s. Then, as N becomes large, n 2 R approaches an integral.

where p(!) is the mixture probability density function of the !i's. Let y be an arbitrary point to be reclassified and let SR(y) be the set of all vectors separated from y by a distance less than R. Then

The behavior of the decision rule corresponding to [29l is easily illustrated when the dimension, L, is two. Figure 1 shows a region around the boundary separating classes s 1 and s 2 · For the value of R shown, y 1 clearly remains in class s1. However, if the probability mass within R of Y, and to the right of the boundary is larger tha~"that to the left of the boundary, then y 2 is reassigned to class s 2 . If [291 reassigns no vectors, then the boundary is said to be stationary.

If R is sufficiently small, we can charact­ erize a stationary boundary rather nicely. Figure 2 shows a small region about a point on the boundary between classes s 1 and s 2 · The boundary has unit normal vector w and Vp(Y) is the gradient of the mixture density evalu;ted at y, i.e.,

Since R is sm.ll, p(!) can be approximated closely with a truncated Taylor expansion about y. The decision rule then becomes

where Vi ia the volume of .Qs n SR(!) and the i superscript T denotes transposition. Again noting that R ia amall, we asaume that the boundary splits SR(!) into two L dimensional hemispheres so that vl · v2. The integrals in (32: are given by

and

where

Thus, the final form of the decision rule is

Suppose the left hand side of C35] is positive. Then! will be assigned to s 1 · Further, all vectors within a small ne~ghborhood of the boundary will also go to ·1· Thus the boundary shifts to the right (see Fig. 2). Similarly, if the right hand side of [35] is negative, the boundary moves to the left. The condition for stationarity of the boundary is

A final boundary between two clRsses must be stable as well as stationary. This means that if the boundary is perturbed it must not tend to move farther away from the stationary point. ~e can establish a condition for unstability as follows. Figure 3 is an exagerated illustration of a small perturbation of a stationary boundary. The vector !' is a point on the new boundary such that

where w 1 is the new unit normal vector. If the compon;nt of ?p(y') along~' is negative, then the boundary will tend to move farther away from the stationary position. Hence the boundary is unstable if ·

for any small pertur;bation. We C3n express 9p(! ) using a T~ylor series about y as

Using (37] and [39 ]

? SupposE 7-p(!) is n;ga tive: semidef i nite . ThE: tl tqe s~cond term of [.41 ~ 1 i.s nonpositive for all w . Ti1c direction of w is Arbitrar y so t hJ t we ~.1n ch;,ose '" 1 such the. t the fi.rs t t e rm of ~41 ~ i~ negative~ Hence , if v2P,(Y) is nega t ive semi­ definitE, then for some::£ L3B J holds and t he boundary is therefore unstable.

In conclusion , the final boundary must satisfy ti.'O conditions.

1. The component of the gradient of t he density normal to the bound~ry must be zero.
2. ii) The boundary may not puss through r~gi ons where V2p is negative semide­ finite.

This development shows that our algorithm leads to reasonable classifications in the asymptotic case. Hopefully, it also provides insight into the behavior of the algorithm in the finite sample case ns well. ·

V. Examples

The algorithm ha s been tested on artifically generated bivariate data. There is no additional difficulty in the multivariate case.

The value of R has considerable effect on the performance of the algorithm. We found that the procedure works best when R is such that the number of distances less than R is 10 to 20 times the sample size.

The choice of N is more difficult. In one case, ~ lnrge value of M resulted in most of the vectors being plated in one of two classes, but we cannot guarantee that this would ~lway s be the result.

Figure 4 show the results of one example with M·2. The initial boundary is random. Note that the data are not linearly separable .

The number of iterations required in the experiments ranged from 4 to 10. Total computa­ tion time was-under 10 seconds on a- CDC 6500 .

VI. Su11111ary

A clustering procedure consists of a crite~ and an algorithm. We have developed a general clustering procedure of which the fixed neighbor­ hood decision rule is a special case. The asymptotic behavior of the procedure was studied and computer experiments testified to its practical value.

The procedure has been shown to be suitable even for non ellipsoidal clusters. It has modest storage requirements and the computational loop, which involves only counting, is very rapid.