Cluster analysis

Jump to: navigation, search



Types of clustering

Data clustering algorithms can be hierarchical or partitional. Hierarchical algorithms find successive clusters using previously established clusters, whereas partitional algorithms determine all clusters at once. Hierarchical algorithms can be agglomerative ("bottom-up") or divisive ("top-down"). Agglomerative algorithms begin with each element as a separate cluster and merge them into successively larger clusters. Divisive algorithms begin with the whole set and proceed to divide it into successively smaller clusters.

Two-way clustering, co-clustering or biclustering are clustering methods where not only the objects are clustered but also the features of the objects, i.e., if the data is represented in a data matrix, the rows and columns are clustered simultaneously.

Another important distinction is whether the clustering uses symmetric or asymmetric distances. A property of Euclidean space is that distances are symmetric (the distance from object A to B is the same as the distance from B to A). In other applications (e.g., sequence-alignment methods, see Prinzie & Van den Poel (2006)), this is not the case.

Distance measure

An important step in any clustering is to select a distance measure, which will determine how the similarity of two elements is calculated. This will influence the shape of the clusters, as some elements may be close to one another according to one distance and further away according to another. For example, in a 2-dimensional space, the distance between the point (x=1, y=0) and the origin (x=0, y=0) is always 1 according to the usual norms, but the distance between the point (x=1, y=1) and the origin can be 2,<math>\sqrt 2</math> or 1 if you take respectively the 1-norm, 2-norm or infinity-norm distance.

Common distance functions:

  • the Euclidean distance (also called distance as the crow flies or 2-norm distance). A review of cluster analysis in health psychology research found that the most common distance measure in published studies in that research area is the Euclidean distance or the squared Euclidean distance.
  • the Manhattan distance (also called taxicab norm or 1-norm)
  • the maximum norm
  • the Mahalanobis distance corrects data for different scales and correlations in the variables
  • the angle between two vectors can be used as a distance measure when clustering high dimensional data. See Inner product space.
  • the Normalized Google Distance (NGD). NGD computes the distance between objects based on their names using only the Google search engine. NGD is a non-feature similarity/distance which attempts to capture every effective distance (e.g. Hamming distance, Euclidean distance, edit distances) into a single metric. An example of the use of NGD in term clustering [1].

Hierarchical clustering

Creating clusters

Hierarchical clustering builds (agglomerative), or breaks up (divisive), a hierarchy of clusters. The traditional representation of this hierarchy is a tree (called a dendrogram), with individual elements at one end and a single cluster containing every element at the other. Agglomerative algorithms begin at the top of the tree, whereas divisive algorithms begin at the bottom. (In the figure, the arrows indicate an agglomerative clustering.)


Agglomerative hierarchical clustering

For example, suppose this data is to be clustered, and the euclidean distance is the distance metric.

The hierarchical clustering dendrogram would be as such:

File:Hierarchical clustering diagram.png
Traditional representation

This method builds the hierarchy from the individual elements by progressively merging clusters. In our example, we have six elements {a} {b} {c} {d} {e} and {f}. The first step is to determine which elements to merge in a cluster. Usually, we want to take the two closest elements, according to the chosen distance.

Optionally, one can also construct a distance matrix at this stage, where the number in the i-th row j-th column is the distance between the i-th and j-th elements. Then, as clustering progresses, rows and columns are merged as the clusters are merged and the distances updated. This is a common way to implement this type of clustering, and has the benefit of catching distances between clusters.

Suppose we have merged the two closest elements b and c, we now have the following clusters {a}, {b, c}, {d}, {e} and {f}, and want to merge them further. To do that, we need to take the distance between {a} and {b c}, and therefore define the distance between two clusters. Usually the distance between two clusters <math>\mathcal{A}</math> and <math>\mathcal{B}</math> is one of the following:

<math> \max \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B}\,\} </math>
  • The sum of all intra-cluster variance


Concept clustering

Another variation of the agglomerative clustering approach is conceptual clustering.

Partitional clustering

K-means and derivatives

K-means clustering



The algorithm steps are (J. MacQueen, 1967):

  • Choose the number of clusters, k.
  • Randomly generate k clusters and determine the cluster centers, or directly generate k random points as cluster centers.
  • Assign each point to the nearest cluster center.
  • Recompute the new cluster centers.
  • Repeat the two previous steps until some convergence criterion is met (usually that the assignment hasn't changed).

The main advantages of this algorithm are its simplicity and speed which allows it to run on large datasets. Its disadvantage is that it does not yield the same result with each run, since the resulting clusters depend on the initial random assignments. It minimizes intra-cluster variance, but does not ensure that the result has a global minimum of variance.

Fuzzy c-means clustering

In fuzzy clustering, each point has a degree of belonging to clusters, as in fuzzy logic, rather than belonging completely to just one cluster. Thus, points on the edge of a cluster, may be in the cluster to a lesser degree than points in the center of cluster. For each point x we have a coefficient giving the degree of being in the kth cluster <math>u_k(x)</math>. Usually, the sum of those coefficients is defined to be 1:

<math> \forall x \sum_{k=1}^{\mathrm{num.}\ \mathrm{clusters}} u_k(x) \ =1.</math>


<math>\mathrm{center}_k = {{\sum_x u_k(x)^m x} \over {\sum_x u_k(x)^m}}.</math>


<math>u_k(x) = {1 \over d(\mathrm{center}_k,x)},</math>

then the coefficients are normalized and fuzzyfied with a real parameter <math>m>1</math> so that their sum is 1. So

<math>u_k(x) = \frac{1}{\sum_j \left(\frac{d(\mathrm{center}_k,x)}{d(\mathrm{center}_j,x)}\right)^{2/(m-1)}}.</math>



  • Choose a number of clusters.
  • Repeat until the algorithm has converged (that is, the coefficients' change between two iterations is no more than <math>\epsilon</math>, the given sensitivity threshold) :

The algorithm minimizes intra-cluster variance as well, but has the same problems as k-means, the minimum is a local minimum, and the results depend on the initial choice of weights. The Expectation-maximization algorithm is a more statistically formalized method which includes some of these ideas: partial membership in classes. It has better convergence properties and is in general preferred to fuzzy-k-means.

QT clustering algorithm


The algorithm is:

  • The user chooses a maximum diameter for clusters.
  • Recurse with the reduced set of points.


Graph-theoretic methods

Formal concept analysis is a technique for generating clusters of objects and attributes, given a bipartite graph representing the relations between the objects and attributes. Other methods for generating overlapping clusters (a cover rather than a partition) are discussed by Jardine and Sibson (1968) and Cole and Wishart (1970).

Elbow criterion

The elbow criterion is a common rule of thumb to determine what number of clusters should be chosen, for example for k-means and agglomerative hierarchical clustering. It should also be noted that the initial assignment of cluster seeds has bearing on the final model performance. Thus, it is appropriate to re-run the cluster analysis multiple times.


On the following graph, the elbow is indicated by the red circle. The number of clusters chosen should therefore be 4. Percent of variance explained or percent of total variance is the ratio of within-group variance to total variance.

Explained Variance

Spectral clustering

Given a set of data points A, the similarity matrix may be defined as a matrix <math>S</math> where <math>S_{ij}</math> represents a measure of the similarity between points <math>i, j\in A</math>. Spectral clustering techniques make use of the spectrum of the similarity matrix of the data to perform dimensionality reduction for clustering in fewer dimensions.

One such technique is the Shi-Malik algorithm, commonly used for image segmentation. It partitions points into two sets <math>(S_1,S_2)</math> based on the eigenvector <math>v</math> corresponding to the second-smallest eigenvalue of the Laplacian matrix

<math>L = I - D^{-1/2}SD^{-1/2}</math>

of <math>S</math>, where <math>D</math> is the diagonal matrix

<math>D_{ii} = \sum_{j} S_{ij}.</math>

This partitioning may be done in various ways, such as by taking the median <math>m</math> of the components in <math>v</math>, and placing all points whose component in <math>v</math> is greater than <math>m</math> in <math>S_1</math>, and the rest in <math>S_2</math>. The algorithm can be used for hierarchical clustering by repeatedly partitioning the subsets in this fashion.

A related algorithm is the Meila-Shi algorithm, which takes the eigenvectors corresponding to the k largest eigenvalues of the matrix <math>P = SD^{-1}</math> for some k, and then invokes another (e.g. k-means) to cluster points by their respective k components in these eigenvectors.



In biology clustering has many applications

Market research


Other applications






Comparisons between data clusterings


Marina Meila's Variation of Information metric is a more recent approach for comparing distance between clusterings. It uses mutual information and entropy to approximate the distance between two clusterings across the lattice of possible clusterings.


In recent years considerable effort has been put into improving algorithm performance (Z. Huang, 1998). Among the most popular are CLARANS (Ng and Han,1994), DBSCAN (Ester et al., 1996) and BIRCH (Zhang et al., 1996).

See also


  1. *Wilson Wong, Wei Liu and Mohammed Bennamoun (June 2007). "Tree-Traversing Ant Algorithm for term clustering based on featureless similarities". Data Mining and Knowledge Discovery. doi:10.1007/s10618-007-0073-y.
  2. E. B. Fowlkes & C. L. Mallows (September 1983). "A Method for Comparing Two Hierachical Clusterings". Journal of the American Statistical Association 78 (383): 553–584.


  • H. Abdi (1990). "Additive-tree representations (with an application to face processing)", Lecture Notes in Biomathematics, 43–59. 
  • Ester, M., Kriegel, H.P., Sander, J., and Xu, X. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, Oregon, USA: AAAI Press, pp. 226–231.
  • Huang, Z. (1998). Extensions to the K-means Algorithm for Clustering Large Datasets with Categorical Values. Data Mining and Knowledge Discovery, 2, p. 283-304.
  • Jardine, N. & Sibson, R. (1968). The construction of hierarchic and non-hierarchic classifications. The Computer Journal 11:177.
  • MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations, Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1:281-297
  • Ng, R.T. and Han, J. 1994. Efficient and effective clustering methods for spatial data mining. Proceedings of the 20th VLDB Conference, Santiago, Chile, pp. 144–155.
  • Prinzie A., D. Van den Poel (2006), Incorporating sequential information into traditional classification models by using an element/position-sensitive SAM. Decision Support Systems 42 (2): 508-526.
  • Romesburg, H. Clarles, Cluster Analysis for Researchers, 2004, 340 pp. ISBN 1-4116-0617-5 or publisher, reprint of 1990 edition published by Krieger Pub. Co... A Japanese language translation is available from Uchida Rokakuho Publishing Co., Ltd., Tokyo, Japan.
  • Zhang, T., Ramakrishnan, R., and Livny, M. 1996. BIRCH: An efficient data clustering method for very large databases. Proceedings of ACM SIGMOD Conference, Montreal, Canada, pp. 103–114.

For spectral clustering :

  • see referenced articles here

For estimating number of clusters:

For discussion of the elbow criterion:

  • Aldenderfer, M.S., Blashfield, R.K, Cluster Analysis, (1984), Newbury Park (CA): Sage.

External links

cs:Shluková analýza de:Clusteranalysehr:Grupiranje it:Clusteringth:การแบ่งกลุ่มข้อมูล