Cluster analysis


Jump to:navigation, search

Cluster analysis or clustering is the assignment of a set of observations into subsets (called clusters) so that observations in the same cluster are similar in some sense. Clustering is a method of unsupervised learning, and a common technique for statistical data analysis used in many fields, including machine learning, data mining, pattern recognition, image analysis and bioinformatics.

Besides the term clustering, there are a number of terms with similar meanings, including automatic classification, numerical taxonomy, botryology and typological analysis.


[edit] Types of clustering

Data clustering algorithms can be hierarchical. Hierarchical algorithms find successive clusters using previously established clusters. These algorithms can be either 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.





Many clustering algorithms require specification of the number of clusters to produce in the input data set, prior to execution of the algorithm. Barring knowledge of the proper value beforehand, the appropriate value must be determined, a problem for which a number of techniques have been developed.

[edit] Distance measure


Common distance functions:

[edit] Hierarchical clustering

Hierarchical clustering creates a hierarchy of clusters which may be represented in a tree structure called a dendrogram. The root of the tree consists of a single cluster containing all observations, and the leaves correspond to individual observations.

Algorithms for hierarchical clustering are generally either agglomerative, in which one starts at the leaves and successively merges clusters together; or divisive, in which one starts at the root and recursively splits the clusters.

Any valid metric may be used as a measure of similarity between pairs of observations. The choice of which clusters to merge or split is determined by a linkage criteria, which is a function of the pairwise distances between observations.


[edit] Agglomerative hierarchical clustering


Raw data

The hierarchical clustering dendrogram would be as such:

Traditional representation


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 caching distances between clusters. A simple agglomerative clustering algorithm is described in the single-linkage clustering page; it can easily be adapted to different types of linkage (see below).


 \max \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B}\,\}.
 {1 \over {|\mathcal{A}|\cdot|\mathcal{B}|}}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y).


[edit] Concept clustering

Another variation of the agglomerative clustering approach is conceptual clustering.

[edit] Partitional clustering

[edit] K-means and derivatives

[edit] k-means clustering


Example: The data set has three dimensions and the cluster has two points: X=(x_1,x_2,x_3)\, and Y=(y_1,y_2,y_3)\,. Then the centroid Z becomes Z=(z_1,z_2,z_3)\,, where:

z_1=\frac{x_1+y_1}{2}, z_2=\frac{x_2+y_2}{2} and z_3=\frac{x_3+y_3}{2}

The algorithm steps are [1]:

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. Another disadvantage is the requirement for the concept of a mean to be definable which is not always the case. For such datasets the k-medoids variant is appropriate.

[edit] 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 uk(k). Usually, the sum of those coefficients for any given x is defined to be 1:

 \forall x \left(\sum_{k=1}^{\mathrm{num.}\ \mathrm{clusters}} u_k(x) \ =1\right)


\mathrm{center}_k = {{\sum_x u_k(x)^m x} \over {\sum_x u_k(x)^m}}

The degree of belonging is related to the inverse of the distance to the cluster center:

u_k(x) = {1 \over d(\mathrm{center}_k,x)},

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

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


The fuzzy c-means algorithm is very similar to the k-means algorithm: [2]

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-c-means.

[edit] QT clustering algorithm

QT (quality threshold) clustering (Heyer, Kruglyak, Yooseph, 1999) is an alternative method of partitioning data, invented for gene clustering. It requires more computing power than k-means, but does not require specifying the number of clusters a priori, and always returns the same result when run several times.

The algorithm is:


[edit] Locality-sensitive hashing

Locality-sensitive hashing can be used for clustering. Feature space vectors are sets, and the metric used is the Jaccard distance. The feature space can be considered high-dimensional. The min-wise independent permutations LSH scheme (sometimes MinHash) is then used to put similar items into buckets. With just one set of hashing methods, there are only clusters of very similar elements. By seeding the hash functions several times (eg 20), it is possible to get bigger clusters. [3]

[edit] Graph-theoretic methods


[edit] Spectral clustering

See also: Kernel principal component analysis

Given a set of data points A, the similarity matrix may be defined as a matrix S where Sij represents a measure of the similarity between points i, j\in A. 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 (S1,S2) based on the eigenvector v corresponding to the second-smallest eigenvalue of the Laplacian matrix

L = I - D^{-1/2}SD^{-1/2}\;

of S, where D is the diagonal matrix

D_{ii} = \sum_{j} S_{ij}\;

This partitioning may be done in various ways, such as by taking the median m of the components in v, and placing all points whose component in v is greater than m in S1, and the rest in S2. 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 P = SD − 1 for some k, and then invokes another (e.g. k-means) to cluster points by their respective k components in these eigenvectors.

[edit] Applications

[edit] Biology

In biology clustering has many applications

[edit] Medicine

In medical imaging, such as PET scans, cluster analysis can be used to differentiate between different types of tissue and blood in a three dimensional image. In this application, actual position does not matter, but the voxel intensity is considered as a vector, with a dimension for each image that was taken over time. This technique allows, for example, accurate measurement of the rate a radioactive tracer is delivered to the area of interest, without a separate sampling of arterial blood, an intrusive technique that is most common today.

[edit] Market research


[edit] Other applications

Social network analysis
Image segmentation
Data mining
Search result grouping
Slippy map optimization
IMRT segmentation
Grouping of Shopping Items
Mathematical chemistry
Petroleum Geology
Cluster Analysis is used to reconstruct missing bottom hole core data or missing log curves in order to evaluate reservoir properties.
Physical Geography
The clustering of chemical properties in different sample locations.

[edit] Comparisons between data clusterings

There have been several suggestions for a measure of similarity between two clusterings. Such a measure can be used to compare how well different data clustering algorithms perform on a set of data. Many of these measures are derived from the matching matrix (aka confusion matrix), e.g., the Rand measure, Adjusted Rand Index and the Fowlkes-Mallows Bk measures.[5] With small variations, such kind of measures also include set matching based clustering criteria, e.g., the Meila and Heckerman.

Several different clustering systems based on mutual information have been proposed. One is Marina Meila's 'Variation of Information' metric (see ref below); another provides hierarchical clustering[6]. The adjusted-for-chance version for the mutual information is the Adjusted Mutual Information (AMI), which corrects mutual information for agreement solely due to chance between clusterings (Vinh et. al, 2009).

Recently, a new Mallows Distance based metric was also proposed for soft clustering comparisons.[citation needed]

[edit] Algorithms


[edit] See also

[edit] Bibliography

  1. J. MacQueen, 1967
  2. Bezdek, James C. (1981), Pattern Recognition with Fuzzy Objective Function Algorithms, ISBN 0306406713 
  3. Google News personalization: scalable online collaborative filtering
  4. Basak S.C., Magnuson V.R., Niemi C.J., Regal R.R. "Determing Structural Similarity of Chemicals Using Graph Theoretic Indices". Discr. Appl. Math., 19, 1988: 17-44.
  5. E. B. Fowlkes & C. L. Mallows (September 1983). "A Method for Comparing Two Hierarchical Clusterings". Journal of the American Statistical Association 78 (383): 553–584. doi:10.2307/2288117. 

[edit] Others

For spectral clustering:

For estimating number of clusters:

For discussion of the elbow criterion:

[edit] External links

Need Help
Share This Page