Cluster analysis

From Wikipedia, the free encyclopedia - View original article

  (Redirected from Data clustering)
Jump to: navigation, search





Clusters and clusterings[edit]


A "clustering" is essentially a set of such clusters, usually containing all objects in the data set. Additionally, it may specify the relationship of the clusters to each other, for example a hierarchy of clusters embedded in each other. Clusterings can be roughly distinguished as:

There are also finer distinctions possible, for example:

Clustering algorithms[edit]



Connectivity based clustering (hierarchical clustering)[edit]



These methods will not produce a unique partitioning of the data set, but a hierarchy from which the user still needs to choose appropriate clusters. They are not very robust towards outliers, which will either show up as additional clusters or even cause other clusters to merge (known as "chaining phenomenon", in particular with single-linkage clustering). In the general case, the complexity is \mathcal{O}(n^3), which makes them too slow for large data sets. For some special cases, optimal efficient methods (of complexity \mathcal{O}(n^2)) are known: SLINK[5] for single-linkage and CLINK[6] for complete-linkage clustering. In the data mining community these methods are recognized as a theoretical foundation of cluster analysis, but often considered obsolete. They did however provide inspiration for many later methods such as density based clustering.

Centroid-based clustering[edit]



Most k-means-type algorithms require the number of clusters - k - to be specified in advance, which is considered to be one of the biggest drawbacks of these algorithms. Furthermore, the algorithms prefer clusters of approximately similar size, as they will always assign an object to the nearest centroid. This often leads to incorrectly cut borders in between of clusters (which is not surprising, as the algorithm optimized cluster centers, not cluster borders).

K-means has a number of interesting theoretical properties. On the one hand, it partitions the data space into a structure known as a Voronoi diagram. On the other hand, it is conceptually close to nearest neighbor classification, and as such is popular in machine learning. Third, it can be seen as a variation of model based classification, and Lloyd's algorithm as a variation of the Expectation-maximization algorithm for this model discussed below.

Distribution-based clustering[edit]

The clustering model most closely related to statistics is based on distribution models. Clusters can then easily be defined as objects belonging most likely to the same distribution. A nice property of this approach is that this closely resembles the way artificial data sets are generated: by sampling random objects from a distribution.

While the theoretical foundation of these methods is excellent, they suffer from one key problem known as overfitting, unless constraints are put on the model complexity. A more complex model will usually always be able to explain the data better, which makes choosing the appropriate model complexity inherently difficult.


Distribution-based clustering is a semantically strong[clarification needed] method, as it not only provides you with clusters, but also produces complex models for the clusters that can also capture correlation and dependence of attributes. However, using these algorithms puts an extra burden on the user: to choose appropriate data models to optimize, and for many real data sets, there may be no mathematical model available the algorithm is able to optimize (e.g. assuming Gaussian distributions is a rather strong assumption on the data).

Density-based clustering[edit]

In density-based clustering,[8] clusters are defined as areas of higher density than the remainder of the data set. Objects in these sparse areas - that are required to separate clusters - are usually considered to be noise and border points.

The most popular[9] density based clustering method is DBSCAN.[10] In contrast to many newer methods, it features a well-defined cluster model called "density-reachability". Similar to linkage based clustering, it is based on connecting points within certain distance thresholds. However, it only connects points that satisfy a density criterion, in the original variant defined as a minimum number of other objects within this radius. A cluster consists of all density-connected objects (which can form a cluster of an arbitrary shape, in contrast to many other methods) plus all objects that are within these objects' range. Another interesting property of DBSCAN is that its complexity is fairly low - it requires a linear number of range queries on the database - and that it will discover essentially the same results (it is deterministic for core and noise points, but not for border points) in each run, therefore there is no need to run it multiple times. OPTICS[11] is a generalization of DBSCAN that removes the need to choose an appropriate value for the range parameter \varepsilon, and produces a hierarchical result related to that of linkage clustering. DeLi-Clu,[12] Density-Link-Clustering combines ideas from single-linkage clustering and OPTICS, eliminating the \varepsilon parameter entirely and offering performance improvements over OPTICS by using an R-tree index.


Recent developments[edit]

In recent years considerable effort has been put into improving algorithm performance of the existing algorithms.[14][15] Among them are CLARANS (Ng and Han, 1994),[16] and BIRCH (Zhang et al., 1996).[17] With the recent need to process larger and larger data sets (also known as big data), the willingness to trade semantic meaning of the generated clusters for performance has been increasing. This led to the development of pre-clustering methods such as canopy clustering, which can process huge data sets efficiently, but the resulting "clusters" are merely a rough pre-partitioning of the data set to then analyze the partitions with existing slower methods such as k-means clustering. Various other approaches to clustering have been tried such as seed based clustering.[18]


Ideas from density-based clustering methods (in particular the DBSCAN/OPTICS family of algorithms) have been adopted to subspace clustering (HiSC,[21] hierarchical subspace clustering and DiSH[22]) and correlation clustering (HiCO,[23] hierarchical correlation clustering, 4C[24] using "correlation connectivity" and ERiC[25] exploring hierarchical density-based correlation clusters).

Several different clustering systems based on mutual information have been proposed. One is Marina Meilă's variation of information metric;[26] another provides hierarchical clustering.[27] Using genetic algorithms, a wide range of different fit-functions can be optimized, including mutual information.[28] Also message passing algorithms, a recent development in Computer Science and Statistical Physics, has led to the creation of new types of clustering algorithms.[29]

Evaluation of clustering results[edit]

Evaluation of clustering results sometimes is referred to as cluster validation.


Internal evaluation[edit]

When a clustering result is evaluated based on the data that was clustered itself, this is called internal evaluation. These methods usually assign the best score to the algorithm that produces clusters with high similarity within a cluster and low similarity between clusters. One drawback of using internal criteria in cluster evaluation is that high scores on an internal measure do not necessarily result in effective information retrieval applications.[30] Additionally, this evaluation is biased towards algorithms that use the same cluster model. For example k-Means clustering naturally optimizes object distances, and a distance-based internal criterion will likely overrate the resulting clustering.



 DB = \frac {1} {n} \sum_{i=1}^{n} \max_{i\neq j}\left(\frac{\sigma_i + \sigma_j} {d(c_i,c_j)}\right)
where n is the number of clusters, c_x is the centroid of cluster x, \sigma_x is the average distance of all elements in cluster x to centroid c_x, and d(c_i,c_j) is the distance between centroids c_i and c_j. Since algorithms that produce clusters with low intra-cluster distances (high intra-cluster similarity) and high inter-cluster distances (low inter-cluster similarity) will have a low Davies–Bouldin index, the clustering algorithm that produces a collection of clusters with the smallest Davies–Bouldin index is considered the best algorithm based on this criterion.
 D = \min_{1\leq i \leq n}\left\{\min_{1\leq j \leq n,i\neq j}\left\{\frac {d(i,j)}{\max_{1\leq k \leq n}{d^{'}(k)}}\right\}\right\}
where d(i,j) represents the distance between clusters i and j, and d^{'}(k) measures the intra-cluster distance of cluster k. The inter-cluster distance d(i,j) between two clusters may be any number of distance measures, such as the distance between the centroids of the clusters. Similarly, the intra-cluster distance d^{'}(k) may be measured in a variety ways, such as the maximal distance between any pair of elements in cluster k. Since internal criterion seek clusters with high intra-cluster similarity and low inter-cluster similarity, algorithms that produce clusters with high Dunn index are more desirable.

External evaluation[edit]

In external evaluation, clustering results are evaluated based on data that was not used for clustering, such as known class labels and external benchmarks. Such benchmarks consist of a set of pre-classified items, and these sets are often created by human (experts). Thus, the benchmark sets can be thought of as a gold standard for evaluation. These types of evaluation methods measure how close the clustering is to the predetermined benchmark classes. However, it has recently been discussed whether this is adequate for real data, or only on synthetic data sets with a factual ground truth, since classes can contain internal structure, the attributes present may not allow separation of clusters or the classes may contain anomalies.[32] Additionally, from a knowledge discovery point of view, the reproduction of known knowledge may not necessarily be the intended result.[32]


The F-measure can be used to balance the contribution of false negatives by weighting recall through a parameter \beta \geq 0. Let precision and recall be defined as follows:
 P = \frac {TP } {TP + FP }
 R = \frac {TP } {TP + FN}
where P is the precision rate and R is the recall rate. We can calculate the F-measure by using the following formula:[30]
 F_{\beta} = \frac {(\beta^2 + 1)\cdot P \cdot R } {\beta^2 \cdot P + R}
Notice that when \beta=0, F_{0}=P. In other words, recall has no impact on the F-measure when \beta=0, and increasing \beta allocates an increasing amount of weight to recall in the final F-measure.
 J(A,B) = \frac {|A \cap B| } {|A \cup B|} = \frac{TP}{TP + FP + FN}
 FM = \sqrt{ \frac {TP}{TP+FP} \cdot \frac{TP}{TP+FN}  }
where TP is the number of true positives, FP is the number of false positives, and FN is the number of false negatives. The FM index is the geometric mean of the precision and recall P and R, while the F-measure is their harmonic mean.[35] Moreover, precision and recall are also known as Wallace's indices B^I and B^{II}.[36]

Clustering Axioms[edit]

Given that there is a myriad of clustering algorithms and objectives, it is helpful to reason about clustering independently of any particular algorithm, objective function, or generative data model. This can be achieved by defining a clustering function as one that satisfies a set of properties. This is often termed as an Axiomatic System. Functions that satisfy the basic axioms are called clustering functions.[37]

Formal Preliminaries[edit]

A partitioning function acts on a set S of n \ge 2 points along with an integer k > 0, and pairwise distances among the points in S. The points are not assumed to belong to any specific larger set or space; the pairwise distances are the only data the partitioning function has about them.[citation needed] We may label the points in S using the numbers \{1, 2, \ldots, n\}. The pairwise distances define a distance function d: S \times S \rightarrow R which should have the properties of a semimetric: for any i, j \in S, we must have d(i, j) \ge 0, d(i, j) = d(j, i), and d(i, j) = 0 if and only if i = j. In other words, the distances must be nonnegative, symmetric, and two points have distance zero if and only if they are the same point.

A partitioning function F takes a distance function d on S \times S and an integer k \ge 1 and returns a k-partition of S, a collection of non-empty disjoint subsets of S whose union is S. The sets making up the k-partition are the clusters. Two clustering functions are equivalent if and only if they output the same partitioning on all values of d and k.


Now in an effort to distinguish clustering functions from partitioning functions, we lay down some properties that one may like a clustering function to satisfy. Here is the first one. If d is a distance function, then we define \alpha \cdot d to be the same function with all distances multiplied by \alpha.


For any distance function d, number of clusters k, and scalar \alpha > 0, we have F(d, k) = F(\alpha \cdot d, k)

This property simply requires the function to be immune to stretching or shrinking the data points linearly. It effectively disallows clustering functions to be sensitive to changes in units of measurement - which is desirable. We would like clustering functions to not have any predefined hard-coded distance values in their decision process.

The next property ensures that the clustering function is “rich" in types of partitioning it could output. For a fixed S and k, Let Range(F(\bullet , k)) be the set of all possible outputs while varying d.


For any number of clusters k, Range(F(\bullet, k)) is equal to the set of all k-partitions of S

In other words, if we are given a set of points such that all we know about the points are pairwise distances, then for any partitioning \Gamma, there should exist a d such that F(d, k) = \Gamma. By varying distances amongst points, we should be able to obtain all possible k-partitionings.

The next property is more subtle. We call a partitioning function “consistent" if it satisfies the following: when we shrink distances between points in the same cluster and expand distances between points in different clusters, we get the same result. Formally, we say that d' is a \Gamma-transformation of d if (a) for all i,j \in S belonging to the same cluster of \Gamma, we have d'(i,j) \le d(i,j); and (b) for all i,j \in S belonging to different clusters of \Gamma, we have d'(i,j) \ge d(i,j). In other words, d' is a transformation of d such that points inside the same cluster are brought closer together and points not inside the same cluster are moved further away from one another.


Fix k. Let d be a distance function, and d' be a F(d, k)-transformation of d. Then F(d, k) = F(d', k)

In other words, suppose that we run the partitioning function F on d to get back a particular partitioning \Gamma. Now, with respect to \Gamma, if we shrink in-cluster distances or expand between-cluster distances and run F again, we should still get back the same result - namely \Gamma.

The partitioning function F is forced to return a fixed number of clusters: k. If this were not the case, then the above three properties could never be satisfied by any function.[38] In many popular clustering algorithms such as k-means, Single-Linkage, and spectral clustering, the number of clusters to be returned is determined beforehand – by the human user or other methods – and passed into the clustering function as a parameter.


Biology, computational biology and bioinformatics
Plant and animal ecology
clustering is used to build groups of genes with related expression patterns (also known as coexpressed genes). Often such groups contain functionally related proteins, such as enzymes for a specific pathway, or genes that are co-regulated. High throughput experiments using expressed sequence tags (ESTs) or DNA microarrays can be a powerful tool for genome annotation, a general aspect of genomics.
Sequence analysis
High-throughput genotyping platforms
clustering algorithms are used to automatically assign genotypes.
Human genetic clustering
Medical imaging
On 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.
IMRT segmentation
Clustering can be used to divide a fluence map into distinct regions for conversion into deliverable fields in MLC-based Radiation Therapy.
Business and marketing
Market research
Grouping of shopping items
World wide web
Social network analysis
Search result grouping
Slippy map optimization
Computer science
Software evolution
Image segmentation
Evolutionary algorithms
Recommender systems
Markov chain Monte Carlo methods
Social science
Crime analysis
Educational data mining
Field robotics
Clustering algorithms are used for robotic situational awareness to track objects and detect outliers in sensor data.[39]
Mathematical chemistry
To find weather regimes or preferred sea level pressure atmospheric patterns.[41]
Petroleum geology
Physical geography
The clustering of chemical properties in different sample locations.

See also[edit]

See also[edit]

Related methods[edit]


  3. ^ Cattell, R. B. (1943). The description of personality: Basic traits resolved into clusters. Journal of Abnormal and Social Psychology, 38, 476-506.
  4. ^ a b c d e f Estivill-Castro, Vladimir (June 2002 2002). "Why so many clustering algorithms — A Position Paper". ACM SIGKDD Explorations Newsletter 4 (1): 65–75. doi:10.1145/568574.568575. 
  5. ^ R. Sibson (1973). "SLINK: an optimally efficient algorithm for the single-link cluster method". The Computer Journal (British Computer Society) 16 (1): 30–34. doi:10.1093/comjnl/16.1.30. 
  6. ^ D. Defays (1977). "An efficient algorithm for a complete link method". The Computer Journal (British Computer Society) 20 (4): 364–366. doi:10.1093/comjnl/20.4.364. 
  7. ^ Lloyd, S. (1982). "Least squares quantization in PCM". IEEE Transactions on Information Theory 28 (2): 129–137. doi:10.1109/TIT.1982.1056489.  edit
  8. ^ Hans-Peter Kriegel, Peer Kröger, Jörg Sander, Arthur Zimek (2011). "Density-based Clustering". WIREs Data Mining and Knowledge Discovery 1 (3): 231–240. doi:10.1002/widm.30. 
  10. ^ Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu (1996). "A density-based algorithm for discovering clusters in large spatial databases with noise". In Evangelos Simoudis, Jiawei Han, Usama M. Fayyad. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226–231. ISBN 1-57735-004-9. 
  11. ^ Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander (1999). "OPTICS: Ordering Points To Identify the Clustering Structure". ACM SIGMOD international conference on Management of data. ACM Press. pp. 49–60. 
  13. ^ S Roy, D K Bhattacharyya (2005). "An Approach to find Embedded Clusters Using Density Based Techniques". LNCS Vol.3816. Springer Verlag. pp. 523–535. 
  14. ^ D. Sculley (2010). "Web-scale k-means clustering". Proc. 19th WWW. 
  15. ^ Z. Huang. "Extensions to the k-means algorithm for clustering large data sets with categorical values". Data Mining and Knowledge Discovery, 2:283–304, 1998.
  18. ^ Can, F.; Ozkarahan, E. A. (1990). "Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases". ACM Transactions on Database Systems 15 (4): 483. doi:10.1145/99935.99938.  edit
  19. ^ Agrawal, R.; Gehrke, J.; Gunopulos, D.; Raghavan, P. (2005). "Automatic Subspace Clustering of High Dimensional Data". Data Mining and Knowledge Discovery 11: 5. doi:10.1007/s10618-005-1396-1.  edit
  26. ^ Meilă, Marina (2003). "Comparing Clusterings by the Variation of Information". Learning Theory and Kernel Machines. Lecture Notes in Computer Science 2777: 173–187. doi:10.1007/978-3-540-45167-9_14. ISBN 978-3-540-40720-1. 
  28. ^ Auffarth, B. (2010). Clustering by a Genetic Algorithm with Biased Mutation Operator. WCCI CEC. IEEE, July 18–23, 2010.
  29. ^ B.J. Frey and D. Dueck (2007). "Clustering by Passing Messages Between Data Points". Science 315 (5814): 972–976. doi:10.1126/science.1136800. PMID 17218491  Papercore summary Frey2007
  30. ^ a b Christopher D. Manning, Prabhakar Raghavan & Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press. ISBN 978-0-521-86571-5. 
  31. ^ Dunn, J. (1974). "Well separated clusters and optimal fuzzy partitions". Journal of Cybernetics 4: 95–104. doi:10.1080/01969727408546059. 
  32. ^ a b Ines Färber, Stephan Günnemann, Hans-Peter Kriegel, Peer Kröger, Emmanuel Müller, Erich Schubert, Thomas Seidl, Arthur Zimek (2010). "On Using Class-Labels in Evaluation of Clusterings". In Xiaoli Z. Fern, Ian Davidson, Jennifer Dy. MultiClust: Discovering, Summarizing, and Using Multiple Clusterings. ACM SIGKDD. 
  33. ^ W. M. Rand (1971). "Objective criteria for the evaluation of clustering methods". Journal of the American Statistical Association (American Statistical Association) 66 (336): 846–850. doi:10.2307/2284239. JSTOR 2284239. 
  35. ^ L. Hubert et P. Arabie. Comparing partitions. J. of Classification, 2(1), 1985.
  36. ^ D. L. Wallace. Comment. Journal of the American Statistical Association, 78 :569– 579, 1983.
  37. ^ R. B. Zadeh, S Ben-David. "A Uniqueness Theorem for Clustering", in Proceedings of the Conference of Uncertainty in Artificial Intelligence, 2009.
  38. ^ J Kleinberg, "An Impossibility Theorem for Clustering", Proceedings of The Neural Information Processing Systems Conference 2002
  39. ^ Bewley A. et al. "Real-time volume estimation of a dragline payload". "IEEE International Conference on Robotics and Automation",2011: 1571-1576.
  40. ^ Basak S.C., Magnuson V.R., Niemi C.J., Regal R.R. "Determining Structural Similarity of Chemicals Using Graph Theoretic Indices". Discr. Appl. Math., 19, 1988: 17-44.
  41. ^ Huth R. et al. "Classifications of Atmospheric Circulation Patterns: Recent Advances and Applications". Ann. N.Y. Acad. Sci., 1146, 2008: 105-152