Cluster analysis

Cluster analysis, or clustering, is a data analysis technique aimed at partitioning a set of objects into groups such that objects within the same group (called a cluster) exhibit greater similarity to one another (in some specific sense defined by the analyst) than to those in other groups (clusters). It is a main task of exploratory data analysis, and a common technique for statistical data analysis, used in many fields, including pattern recognition, image analysis, information retrieval, bioinformatics, data compression, computer graphics and machine learning. Cluster analysis refers to a family of algorithms and tasks rather than one specific algorithm. It can be achieved by various algorithms that differ significantly in their understanding of what constitutes a cluster and how to efficiently find them. Popular notions of clusters include groups with small distances between cluster members, dense areas of the data space, intervals or particular statistical distributions. Clustering can therefore be formulated as a multi-objective optimization problem. The appropriate clustering algorithm and parameter settings (including parameters such as the distance function to use, a density threshold or the number of expected clusters) depend on the individual data set and intended use of the results.…

Cluster analysis, or clustering, is a data analysis technique aimed at partitioning a set of objects into groups such that objects within the same group (called a cluster) exhibit greater similarity to one another (in some specific sense defined by the analyst) than to those in other groups (clusters). It is a main task of exploratory data analysis, and a common technique for statistical data analysis, used in many fields, including pattern recognition, image analysis, information retrieval, bioinformatics, data compression, computer graphics and machine learning. Cluster analysis refers to a family of algorithms and tasks rather than one specific algorithm. It can be achieved by various algorithms that differ significantly in their understanding of what constitutes a cluster and how to efficiently find them. Popular notions of clusters include groups with small distances between cluster members, dense areas of the data space, intervals or particular statistical distributions. Clustering can therefore be formulated as a multi-objective optimization problem. The appropriate clustering algorithm and parameter settings (including parameters such as the distance function to use, a density threshold or the number of expected clusters) depend on the individual data set and intended use of the results. Cluster analysis as such is not an automatic task, but an iterative process of knowledge discovery or interactive multi-objective optimization that involves trial and failure. It is often necessary to modify data preprocessing and model parameters until the result achieves the desired properties. Besides the term clustering, there are a number of terms with similar meanings, including automatic classification, numerical taxonomy, botryology (from ), typological analysis, and community detection. The subtle differences are often in the use of the results: while in data mining, the resulting groups are the matter of interest, in automatic classification the resulting discriminative power is of interest. Cluster analysis originated in anthropology by Driver and Kroeber in 1932 and introduced to psychology by Joseph Zubin in 1938 and Robert Tryon in 1939 and famously used by Cattell beginning in 1943 for trait theory classification in personality psychology. File:SLINK-Gaussian-data.svg|Single-linkage on Gaussian data. At 35 clusters, the biggest cluster starts fragmenting into smaller parts, while before it was still connected to the second largest due to the single-link effect. File:SLINK-density-data.svg|Single-linkage on density-based clusters. 20 clusters extracted, most of which contain single elements, since linkage clustering does not have a notion of "noise". File:KMeans-Gaussian-data.svg|k-means separates data into Voronoi cells, which assumes equal-sized clusters (not adequate here). File:KMeans-density-data.svg|k-means cannot represent density-based clusters. The following pseudocode describes the standard iterative refinement form of k-means. The algorithm alternates between an assignment step, which labels each point by its nearest centroid, and an update step, which recomputes each centroid as the mean of its assigned points. Convergence is guaranteed in a finite number of iterations, though the result may be a local optimum. input: dataset \mathbf{x}_1,...,\mathbf{x}_P , initializations for centroids \mathbf{c}_1,...,\mathbf{c}_K , maximum number of iterations J for \,\,j = 1,\ldots,J # Cluster assignments for \,\,p = 1,\ldots,P a_p =\underset{k=1,\ldots,K}{\mbox{argmin}}\,\,\left\Vert \mathbf{c}_{k}-\mathbf{x}_{p}\right\Vert _{2} # Update centroid locations for \,\,k = 1,\ldots,K \text{denote } S_k \text{ the index set of points } X_p\text{ currently assigned to the }k_{th}\text{ cluster} \text{update }c_k\text{ via }c_k=\frac{1}{\left|S_{k}\right|}\underset{p\in S_{k}}{\sum}\mathbf{x}_{p} # Update cluster assignments using final for \,\,p = 1,\ldots,P a_p =\underset{k=1,\ldots,K}{\mbox{argmin}}\,\,\left\Vert \mathbf{c}_{k}-\mathbf{x}_{p}\right\Vert _{2} output: optimal centroids and assignments Centroid-based clustering problems such as k-means and k-medoids are special cases of the uncapacitated, metric facility location problem, a canonical problem in the operations research and computational geometry communities. In a basic facility location problem (of which there are numerous variants that model more elaborate settings), the task is to find the best warehouse locations to optimally service a given set of consumers. One may view "warehouses" as cluster centroids and "consumer locations" as the data to be clustered. This makes it possible to apply the well-developed algorithmic solutions from the facility location literature to the presently considered centroid-based clustering problem. File:EM-Gaussian-data.svg|On Gaussian-distributed data, EM works well, since it uses Gaussians for modelling clusters. File:EM-density-data.svg|Density-based clusters cannot be modeled using Gaussian distributions. File:DBSCAN-density-data.svg|Density-based clustering with DBSCAN. File:DBSCAN-Gaussian-data.svg|DBSCAN assumes clusters of similar density, and may have problems separating nearby clusters. File:OPTICS-Gaussian-data.svg|OPTICS is a DBSCAN variant, improving handling of different densities clusters. DB = \frac {1} {n} \sum_{i=1}^{n} \max_{j\neq i}\left(\frac{\sigma_i + \sigma_j} {d(c_i,c_j)}\right) where n is the number of clusters, c_i is the centroid of cluster i , \sigma_i is the average distance of all elements in cluster i to centroid c_i , 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 = \frac{\min_{1 \leq i 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 of 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. RI = \frac {TP + TN} {TP + FP + FN + TN} where TP is the number of true positives, TN is the number of true negatives, FP is the number of false positives, and FN is the number of false negatives. The instances being counted here are the number of correct pairwise assignments. That is, TP is the number of pairs of points that are clustered together in the predicted partition and in the ground truth partition, FP is the number of pairs of points that are clustered together in the predicted partition but not in the ground truth partition etc. If the dataset is of size N, then TP + TN + FP + FN = \binom{N}{2} . One issue with the Rand index is that false positives and false negatives are equally weighted. This may be an undesirable characteristic for some clustering applications. The F-measure addresses this concern, as does the chance-corrected adjusted Rand index. 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: F_{\beta} = \frac {(\beta^2 + 1)\cdot P \cdot R } {\beta^2 \cdot P + R} 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. Also TN is not taken into account and can vary from 0 upward without bound. J(A,B) = \frac = \frac{TP}{TP + FP + FN} This is simply the number of unique elements common to both sets divided by the total number of unique elements in both sets. Note that TN is not taken into account. DSC = \frac{2TP}{2TP + FP + FN} .

Fowlkes–Mallows index

The Fowlkes–Mallows index computes the similarity between the clusters returned by the clustering algorithm and the benchmark classifications. The higher the value of the Fowlkes–Mallows index the more similar the clusters and the benchmark classifications are. It can be computed using the following formula: 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 , and is thus also known as the G-measure, while the F-measure is their harmonic mean. Moreover, precision and recall are also known as Wallace's indices B^I and B^{II} . Chance normalized versions of recall, precision and G-measure correspond to Informedness, Markedness and Matthews Correlation and relate strongly to Kappa.

Chi index

The Chi index is an external validation index that measure the clustering results by applying the chi-squared statistic. This index scores positively the fact that the labels are as sparse as possible across the clusters, i.e., that each cluster has as few different labels as possible. The higher the value of the Chi Index the greater the relationship between the resulting clusters and the label used.

Mutual information

The mutual information is an information theoretic measure of how much information is shared between a clustering and a ground-truth classification that can detect a non-linear similarity between two clustering. Normalized mutual information is a family of corrected-for-chance variants of this that has a reduced bias for varying cluster numbers.

Validity measure

The validity measure (short v-measure) is a combined metric for homogeneity and completeness of the clusters H=\frac{\sum_{i=1}^m{u_i^d}}{\sum_{i=1}^m{u_i^d}+\sum_{i=1}^m{w_i^d}} \,, With this definition, uniform random data should tend to have values near to 0.5, and clustered data should tend to have values nearer to 1. However, data containing just a single Gaussian will also score close to 1, as this statistic measures deviation from a uniform distribution, not multimodality, making this statistic largely useless in application (as real data never is remotely uniform).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1360782645 under CC BY-SA 4.0; modifications have been made.