Non-hierarchical clustering algorithms produce disjoint clusters and thus work well when a given set is composed of a number of distinct classes or when the data description is "flat".

1. K-Means

Suppose we have n feature vectors X₁, X₂, ... , X_n all belonging to the same class C and we know that they belong to k clusters such that k < n. If clusters are well separated we can use a minimum distance classifier to separate them. We first initialize the means m₁ ... m_k of k clusters. One of the ways to do this is just to assign random numbers to them. We then determine the membership of each X by taking the || X - m_i ||. The minimum distance determines X's membership in a respective cluster. This is done for all n feature vectors Here is the actual algorithm:

1. begin
2.     initialize n; c; m₁ ... m_c
3.     do
4.         classify n samples according to nearest m_i
5.         recompute m_i
6.     until no change in m_i
7.     return m₁ ... m_c
8. end

Figure 1 explains how the algorithm works in the case when k=2. We randomly select the values for m₁ and m₂, and the algorithm converges when the means no longer change. (Let m_i = m_i)

Figure 1

The are certain problems with this algorith, like when the means are chose such that some Mi happens to be 0, so that it cannot be updated. It is, hence, advisable to try a number of different starting points. The results depend a lot on the value of k, i.e. the actual number of clusters. Often, we have no way of knowing how many clusters exist. Figure 2 shows what happens when we use k=3. (Let m_i = m_i)

Figure 2

Sometimes the clustering division turns out to be better at higher k.We can go all the way up to k=n. However, this procedure will give us something known as the Nearest Neighbor Classifier which will be discussed later on. It performs great if the number of feature vectors is large; however, computationally it is much more expensive.

2. Fuzzy K-Means

In every iteration of the classical k-means procedure, we assumed that each feature vecotor belongs to exactly one cluster. We can relax this condition and assume that each sample X_i has some graded or "fuzzy" membership in a cluster m_j. The probabilities of cluster membership for each point are normalized as:

S^c_i=1 P(w_i | x_j) = 1, where j = 1, ..., n

Each m_i is then re-calculated as:

m_j = ( Sⁿ_j=1 P(w_i | x_j)^b x_j ) / ( Sⁿ_j=1 P(w_i | x_j)^b

And each P(w_i | x_j) is then re-calculated as:

P(w_i | x_j) = ( 1 / d_ij )^1/(b-1) / ( S^c_r=1 ( 1 / d_rj )^1/(b-1) ), where d_ij = || x_j - m_i ||²

The algorithm looks as follows:

1. begin
2.     initialize n; m₁ ... m_c; P(w_i | x_j), where i = 1, ..., c and j = 1, ..., n
3.     normalize probabilities of cluster memberships
4.     do
5.         classify n samples according to nearest m_i
6.         recompute m_i
7.         recompute P(w_i | x_j)
8.     until no change in m_i & P(w_i | x_j)
9.     return m₁ ... m_c
10. end

It may seem that the graded membership, which fuzzy K-means offers, improves the convergence of the algorithm. There are still drawbacks to this method: incorrect specification of the number of clusters.

3. Sequential K-Means

It may sometimes happen that we do not have all the data points at once, but rather obtain them gradually over a period of time. The Sequential K-means procedure offers us the flexibility of updating the means as new data points arrive.

Our objective is to find such partitions of a set of n samples which extremize the criterion function (distance, etc.) Due to an overwhelming number of partitions of n elements into c subsets ( cⁿ /c! ), we cannot consider all possibilities. One approace is Iterative Optimization descibed by the Basic iterative minimum-squared-error clustering which could be modified to a Sequential K-Means procedure. The idea is to come up with a reasonable inital partition and to "move" samples from one group to another if such move improves the value of the criterion function.

Basic iterative minimum-squared-error clustering:

1. begin
2.     initialize n; c; m₁ ... m_c;
3.     do randomly select a sample x
4.         classify x: let i = arg min_i' || m_i' - x ||
5.         if n_i != 1 then compute:
6.             if j != i then p_j = || x - m_i ||² n_j / (n_j + 1) else p_j = || x - m_i ||² n_j / (n_j - 1)
7.             if p_k <= p_j for all j then
8.                 transfer x to C_k (cluster k)
9.                 recompute S^c_i=1 S_{x e Ci} || x - m_i ||²
10.     until no change in S^c_i=1 S_{x e Ci} || x - m_i ||² in n attempts
11.     return m₁ ... m_c
12. end

This procedure has certain drawbacks as well, one of them being the order in which the candidates are selected.

There are many times when clusters have sub-classes within them, and which in turn have sub-classes of their own. Examples of such occurences can be found in biological taxonomy when we have a species in the 'animal' kingdom, with a 'chordata' phylum, a sub-phylum of 'vertebrata, and so on. Such classifications are hierarchical and proper partitions can be found by the following classification methods.

More formally, a sequence is said to be a hierarchical clustering if there exists 2 samples, c₁ and c₂, which belong in the same cluster at some level k and remain clustered together at all higher levels > k.

One example of a hiearachical clustering is a correspondence tree, or a dendrogram (shown in Figure 1), which shows how samples are grouped together. The first level shows all samples x_i as singleton clusters. As we increase levels, more and more samples are clustered together in a hierarchical manner.

Figure 1

Another example is one based on sets where each cluster level may contain sets that are subclusters as shown in the Venn diagram in Figure 2.

Figure 2

The hierarchical clustering procedures can be divided into two different approaches: agglomerative and divisive. The agglomerative approach to cluster analysis, used by the nearest and farthest neighbour algorithms, is a bottom-up clumping approach where we begin with n singleton clusters and successively merge clusters to produce the other ones. The minimal spanning tree, on the other hand, uses the divisive approach which is a top-down approach where we start with one cluster and successively split clusters to produce others.

In general, all agglomerative algorithms usually yield the same results if the clusters are compact and well separated. However, if the clusters are close to one another or if their shapes are not hyperspherical, different results can be expected. The space and time complexities are O(n²) and O(cn²d²) respectively, where c is the number of clusters and d is the distance between them.

1. Nearest-Neighbour

The following is the nearest-neighbour clustering algorithm:

1. begin
2.     initialize c; c' = n; D_i = {x_i}; i = 1,...,n
3.     do
4.         c' = c' - 1
5.         Find nearest clusters D_i and D_j
6.         Merge D_i and D_j
7.     until c = c'
8.     return c clusters
9. end

To find the nearest clusters in step 5, the following clustering criterion function is used:

d_min(D_i, D_j) = min || x - x' ||, where x e D_i and x' e D_j

The merging of the two clusters in step 6 simply corresponds to adding an edge betwwen the nearest pair of nodes in D_i and D_j.

Also, if instead of terminating after a predetermined number of clusters have been obtained, it is possible to set the termination criteria to stop when the distance between nearest clusters exceeds a predetermined threshold, thus becoming the single-linkage algorithm.

Some interesting properties of this algorithm is that it will always produce a tree since edges linking clusters always go between distinct clusters, thus no cycles are produced as can be seen in Figure 3. Also, if the algorithm is allowed to run until all clusters are connected then a spanning tree is generated, or more precisely, a minimal spanning tree since the edges we are inserting between clusters are always the shortest ones in distance.

Figure 3

As a result, the nearest-neighbour algorithm can effectively detect elongated clusters but is not as effective when clusters are compact and of equal size. Therefore we look to the farthest-neighbour algorithm to detect such clusters.

2. Farthest-Neighbour

The following is the farthest-neighbour clustering algorithm:

1. begin
2.     initialize c; c' = n; D_i = {x_i}; i = 1,...,n
3.     do
4.         c' = c' - 1
5.         Find nearest clusters D_i and D_j
6.         Merge D_i and D_j
7.     until c = c'
8.     return c clusters
9. end

To find the nearest clusters in step 5, the following clustering criterion function is used:

d_max(D_i, D_j) = max || x - x' ||, where x e D_i and x' e D_j

Also, if instead of terminating after a predetermined number of clusters have been obtained, it is possible to set the termination criteria to stop when the distance between nearest clusters exceeds a predetermined threshold, thus becoming the complete-linkage algorithm.

The farthest-neighbour algorithm prevents the grouping of elongated clusters; instead, clusters are composed of complete subgraphs (Figure 4). As a result, the distance of two clusters is determined not by the distance between the two closest nodes (as in the nearest-neighbour algorithm), but by the distance between the two most distant nodes. Thus, when merging the two clusters, edges are added between every pair of nodes in the affected clusters.

Figure 4

This algorithm thus detects clusters which are compact and of roughly equal size, but has difficulties when the clusters are elongated and can generate groupings which are meaningless.

Possible compromises between the two agglomerative approaches suggested above are to use the following criterion to find the nearest clusters:

d_avg(D_i, D_j) = ( 1 / (n_in_j) ) S S || x - x' ||, where x e D_i and x' e D_j

d_mean(D_i, D_j) = || m_i - m_j ||

3. Minimal Spanning Tree

The minimal spanning tree algorithm is a divisive approach because we are given the minimal spanning tree of all the nodes thus providing us with only one cluster to work with initially.

There exists numerous ways to divide the clusters successively. One way is to simply remove the longest edge and create 2 clusters and then recursively removing the longest edge until the desired number of clusters is obtained.

Another method in selecting which edge to remove is to compare the length of the edges to the lengths of the edges incident upon its nodes. As a result, we can consider an edge to be inconsistent if its length l is significantly larger than l', where l' is the average length of all other edges incident on its nodes (Figure 5). This method has the advantage of determining clusters which have different distances separating one another.

Figure 5

Another use of the minimal spanning tree is to find dense clusters embedded in a sparse set of points (Figure 6). All that has to be done is to remove all edges longer than some predetermined length in order to extract clusters which are closer than the specified length to each other. If the length is chosen accordingly, the dense clusters are extracted from a sparse set of points easily.

Figure 6

1. Hypervolume Method and Hypervolume criterion

This method assumes that the data points X₁, X₂, ... , X_n come from a Poisson distribution (density function f(x)=e^-m m^x/x!) and that the clusters are convex. This procedure uses a method of maximum likelihood estimation. For C₁, C₂, ... , C_k clusters and n feature vectors, the likelyhood function is as follows:

f_C(x) = [1/(m(C))ⁿ] Pⁿ_i=1I_C (x_i), where C is the union of k disjoint domains or clusters

m(D) is the sum of Lebesgue measures of the k subsets of C. The maximum likelyhood estimation of k subsets C₁, C₂, ... , C_k is constituted by k subgroups of points such that the sum of the Lebesgue measures of their disjoint convex hulls is minimum. In a two-dimensional space (m=2), the optimal solution is given by k subgroups of points such that the areas of their disjoint convex hulls is minimum.

There are several implementations to this method. One is the global algorithm which is a dynamic programming procedure giving an optimal partition. (but not necesssarily unique) It takes polynomial time. Another approach is to apply a hierarchic divisive procedure which yeilds a partition of the set of objects into k clusters and then improve the partition according to the hypervolume criterion. The three methods below involve the hypervolume criterion.

2. A Classical Geometric Method (M1)

This method consists of plotting the value of a clustering criterion against the number of clusters k and analyzing the graph looking for discontinuities in the slope. A sharp step in the curve signifies the number of clusters whereas no sharp inclinations suggests only one cluster. This procedure however can be very unreliable by showing a large number of clusters when analyzing unstructured data.

3. Method based on the estimation of a convex set (M2)

This method looks at C₁, C₂, ... , C_k subsets making an assumption that the points come from a Poisson distribution. The solution is based on the dilation of the convex hull H(x) of x = {x₁, x₂, ... , x_k} about its centroid. A decision rule for estimating the number of clusters looks at whether the intersection of the convex sets is NULL or not starting at t=2 clusters and going up until a specified stopping condition.

4. A likelyhood ration test for clusters (M3)

This method assumes n data points from a Poisson process and k disjoint convex sets C₁, C₂, ... , C_k in an m-dimensional Euclidian space. For a given integer k >= 2, we test whether a subdivision into k clusters is significantly better than the subdivision into k-1 clusters. In practice, when the distribution is uknown, the hypothesis is rejected when the ratio is large. The ration has the form:

W(P,k)/W(P,k-1)

(For more information see (Hardy, 1992))

5. Wolfe's test (M4)

This method is based on the assumption of multivariate normality and is a likelihood ratio criterion to test the hypothesis of k clusters against k-1 clusters

6. The Upper Tail Rule (M5)

This is a test for the number of clusters in a hiearchical clustering sequence. The stopping rule selects the partition associated to the first stage j in the cluster sequence j = 2, ..., n-2 which satisfies:

z_j+1 > m + k s_z

where m is the mean of the distribution of n-1 values, s_z is the standard deviation of those same values, and k is the standard deviate.

As a result, z_j+1 lies in the upper tail of the distribution of criterion values m. The best results are when the number of clusters are found to be n-j for the first z_j+1 satisfying the condition. Therefore, if none satisfy the condition, there is no relevant classification.

7. The Moving Average Quality Control Rule (M6)

This test determines the number of clusters within a hierarchical sequence also. This time, the stopping rule chooses the partition associated with the first stage j in the partial cluster sequence j = r, r+1, ..., n-2 which satisfy the condition:

z_j+1 > m + L_j + b_j + k s_z

where r is the number of items in the moving average, m is the moving mean in stage j, L_j is the correction trend lag in stage j, b_j is the moving least squares slope in stage j, s_z is the moving estimate of the standard deviation in stage j.

As before, if no z_j+1 satisfies the condition, then we conclude there is no relevant classification for the data.

8. Marriot's test (M7)

This method assesses the number of clusters k by selecting the k for which k²|W| is a minimum, where W is the matrix of the group dispersion.

The above methods M1 through M7 have been tested (Hardy, 96) on a variety of data. It was shown that if the clusters are compact and well separated then almost every method succeded in finding the obvios clusters. However, what was more interesting was the behavior of these methods on specific arrangements of data points in 2D Euclidian space.

1. When data is represented as two well-defined clusters with a thin chain in between, M1, M2, M3, M4, M5, M6 were able to identify 2 clusters.
2. In the case of absence of any group structure, M1, M2, M3 - all methods bases on the hypervolume criterion - give the correct results and are very efficient.
3. When data has a shape of two elongated clusters, M1, M2, M3, M4, and M6 identify the correct number of clusters.
4. In the case of three non-linearly separable clusters, M1, M3, M4, and M6 give good results.
5. When data is represented by two unequal-size hyperspherical-shaped clusters, M1, M2, M3, M5, and M6 are able to identify 2 clusters.
6. In the case of two non-convex clusters, only M5 is able to indentify the correct number of clusters. Clearly, the hypervolume clustering method is not applicable because the convexity assumption is not fullfilled

It is pretty clear that the methods based on the hypervolume criterion performs well where applicable, even when there is no group structure present. One thing to mention is about the last method M7 which failed in every sigle test by being off by a factor of 10.

As can be seen from the above algorithms, there is a problem in implementing an algorithm which will work well in finding clusters in any set of data. Any approach chosen carries with it a set of implicit assumptions about the type of structure the data is in which prevents us from selecting any one algorithm and using it for all data. The methods may give the correct number of clusters contained within the data but whether the partitioning is accurate is another issue.

Since using different clustering criterion and methods for determining the number of clusters and their partitions can produce varying results when applied to identical data, we should be wary about accepting the results of a single clustering method. As a result, various cluster analysis methods should be used and an average obtained, or the data should be analyzed for size, shape and separation and only after that analysis has been done do we select an appropriate clustering algorithm to determine the number of clusters and their partitionings.

Duda, Richard. "Feature Selection and Clustering for HCI". http://www-engr.sjsu.edu/~knapp/HCIRDFSC/FSC_home.htm, 1996-97.

Duda, R. & Hart, P. & Stork, D. Pattern Classification: 2nd edition. John Wiley & Sons, Inc: California, USA, 1998.

Hardy, Andre. "On the Number of Clusters". Computational Statistics & Data Analysis: volume 23, p. 83-96, 1996.

Anatoly Likhatchev: e-mail, homepage.

Costa Siourbas: e-mail, homepage.