2.3. Clustering ¶

similarity = np.exp(-beta * distance / distance.std())
See the examples for such an application.
Examples:
Spectral clustering for image segmentation: Segmenting objects
from a noisy background using spectral clustering.
Segmenting the picture of greek coins in regions: Spectral clustering
to split the image of coins in regions.
2.3.5.1. Different label assignment strategies¶
Different label assignment strategies can be used, corresponding to the
assign_labels




    
 parameter of SpectralClustering.
"kmeans" strategy can match finer details, but can be unstable.
In particular, unless you control the random_state, it may not be
reproducible from run-to-run, as it depends on random initialization.
The alternative "discretize" strategy is 100% reproducible, but tends
to create parcels of fairly even and geometrical shape.
The recently added "cluster_qr" option is a deterministic alternative that
tends to create the visually best partitioning on the example application
below.
assign_labels="kmeans"
assign_labels="discretize"
assign_labels="cluster_qr"
“Multiclass spectral clustering”
Stella X. Yu, Jianbo Shi, 2003
“Simple, direct, and efficient multi-way spectral clustering”
Anil Damle, Victor Minden, Lexing Ying, 2019
2.3.5.2. Spectral Clustering Graphs¶
Spectral Clustering can also be used to partition graphs via their spectral
embeddings.  In this case, the affinity matrix is the adjacency matrix of the
graph, and SpectralClustering is initialized with affinity='precomputed':
>>> from sklearn.cluster import SpectralClustering
>>> sc = SpectralClustering(3, affinity='precomputed', n_init=100,
...                         assign_labels='discretize')
>>> sc.fit_predict(adjacency_matrix)  
References:
“A Tutorial on Spectral Clustering”
Ulrike von Luxburg, 2007
“Normalized cuts and image segmentation”
Jianbo Shi, Jitendra Malik, 2000
“A Random Walks View of Spectral Segmentation”
Marina Meila, Jianbo Shi, 2001
“On Spectral Clustering: Analysis and an algorithm”
Andrew Y. Ng, Michael I. Jordan, Yair Weiss, 2001
“Preconditioned Spectral Clustering for Stochastic
Block Partition Streaming Graph Challenge”
David Zhuzhunashvili, Andrew Knyazev
2.3.6. Hierarchical clustering¶
Hierarchical clustering is a general family of clustering algorithms that
build nested clusters by merging or splitting them successively. This
hierarchy of clusters is represented as a tree (or dendrogram). The root of the
tree is the unique cluster that gathers all the samples, the leaves being the
clusters with only one sample. See the Wikipedia page for more details.
The AgglomerativeClustering object performs a hierarchical clustering
using a bottom up approach: each observation starts in its own cluster, and
clusters are successively merged together. The linkage criteria determines the
metric used for the merge strategy:
Ward minimizes the sum of squared differences within all clusters. It is a
variance-minimizing approach and in this sense is similar to the k-means
objective function but tackled with an agglomerative hierarchical
approach.
Maximum or complete linkage minimizes the maximum distance between
observations of pairs of clusters.
Average linkage minimizes the average of the distances between all
observations of pairs of clusters.
Single linkage minimizes the distance between the closest
observations of pairs of clusters.
AgglomerativeClustering can also scale to large number of samples
when it is used jointly with a connectivity matrix, but is computationally
expensive when no connectivity constraints are added between samples: it
considers at each step all the possible merges.
FeatureAgglomeration
The FeatureAgglomeration uses agglomerative clustering to
group together features that look very similar, thus decreasing the
number of features. It is a dimensionality reduction tool, see
Unsupervised dimensionality reduction.
2.3.6.1. Different linkage type: Ward, complete, average, and single linkage¶
AgglomerativeClustering supports Ward, single, average, and complete
linkage strategies.
Agglomerative cluster has a “rich get richer” behavior that leads to
uneven cluster sizes. In this regard, single linkage is the worst
strategy, and Ward gives the most regular sizes. However, the affinity
(or distance used in clustering) cannot be varied with Ward, thus for non
Euclidean metrics, average linkage is a good alternative. Single linkage,
while not robust to noisy data, can be computed very efficiently and can
therefore be useful to provide hierarchical clustering of larger datasets.
Single linkage can also perform well on non-globular data.
Examples:
Various Agglomerative Clustering on a 2D embedding of digits: exploration of the
different linkage strategies in a real dataset.
2.3.6.2. Visualization of cluster hierarchy¶
It’s possible to visualize the tree representing the hierarchical merging of clusters
as a dendrogram. Visual inspection can often be useful for understanding the structure
of the data, though more so in the case of small sample sizes.
2.3.6.3. Adding connectivity constraints¶
An interesting aspect of AgglomerativeClustering is that
connectivity constraints can be added to this algorithm (only adjacent
clusters can be merged together), through a connectivity matrix that defines
for each sample the neighboring samples following a given structure of the
data. For instance, in the swiss-roll example below, the connectivity
constraints forbid the merging of points that are not adjacent on the swiss
roll, and thus avoid forming clusters that extend across overlapping folds of
the roll.
 
These constraint are useful to impose a certain local structure, but they
also make the algorithm faster, especially when the number of the samples
is high.
The connectivity constraints are imposed via an connectivity matrix: a
scipy sparse matrix that has elements only at the intersection of a row
and a column with indices of the dataset that should be connected. This
matrix can be constructed from a-priori information: for instance, you
may wish to cluster web pages by only merging pages with a link pointing
from one to another. It can also be learned from the data, for instance
using sklearn.neighbors.kneighbors_graph to restrict
merging to nearest neighbors as in this example, or
using sklearn.feature_extraction.image.grid_to_graph to
enable only merging of neighboring pixels on an image, as in the
coin example.
Examples:
A demo of structured Ward hierarchical clustering on an image of coins: Ward clustering
to split the image of coins in regions.
Hierarchical clustering: structured vs unstructured ward: Example of
Ward algorithm on a swiss-roll, comparison of structured approaches
versus unstructured approaches.
Feature agglomeration vs. univariate selection:
Example of dimensionality reduction with feature agglomeration based on
Ward hierarchical clustering.
Agglomerative clustering with and without structure
Warning
Connectivity constraints with single, average and complete linkage
Connectivity constraints and single, complete or average linkage can enhance
the ‘rich getting richer’ aspect of agglomerative clustering,
particularly so if they are built with
sklearn.neighbors.kneighbors_graph. In the limit of a small
number of clusters, they tend to give a few macroscopically occupied
clusters and almost empty ones. (see the discussion in
Agglomerative clustering with and without structure).
Single linkage is the most brittle linkage option with regard to this issue.
2.3.6.4. Varying the metric¶
Single, average and complete linkage can be used with a variety of distances (or
affinities), in particular Euclidean distance (l2), Manhattan distance
(or Cityblock, or l1), cosine distance, or any precomputed affinity
matrix.
l1 distance is often good for sparse features, or sparse noise: i.e.
many of the features are zero, as in text mining using occurrences of
rare words.
cosine distance is interesting because it is invariant to global
scalings of the signal.
The guidelines for choosing a metric is to use one that maximizes the
distance between samples in different classes, and minimizes that within
each class.
2.3.6.5. Bisecting K-Means¶
The BisectingKMeans is an iterative variant of KMeans, using
divisive hierarchical clustering. Instead of creating all centroids at once, centroids
are picked progressively based on a previous clustering: a cluster is split into two
new clusters repeatedly until the target number of clusters is reached.
BisectingKMeans is more efficient than KMeans when the number of
clusters is large since it only works on a subset of the data at each bisection
while KMeans always works on the entire dataset.
Although BisectingKMeans can’t benefit from the advantages of the "k-means++"
initialization by design, it will still produce comparable results than
KMeans(init="k-means++") in terms of inertia at cheaper computational costs, and will
likely produce better results than KMeans




    
 with a random initialization.
This variant is more efficient to agglomerative clustering if the number of clusters is
small compared to the number of data points.
This variant also does not produce empty clusters.
There exist two strategies for selecting the cluster to split:

bisecting_strategy="largest_cluster" selects the cluster having the most points
bisecting_strategy="biggest_inertia" selects the cluster with biggest inertia
(cluster with biggest Sum of Squared Errors within)
Picking by largest amount of data points in most cases produces result as
accurate as picking by inertia and is faster (especially for larger amount of data
points, where calculating error may be costly).
Picking by largest amount of data points will also likely produce clusters of similar
sizes while KMeans is known to produce clusters of different sizes.
Difference between Bisecting K-Means and regular K-Means can be seen on example
Bisecting K-Means and Regular K-Means Performance Comparison.
While the regular K-Means algorithm tends to create non-related clusters,
clusters from Bisecting K-Means are well ordered and create quite a visible hierarchy.
References:
“A Comparison of Document Clustering Techniques”
Michael Steinbach, George Karypis and Vipin Kumar,
Department of Computer Science and Egineering, University of Minnesota
(June 2000)
“Performance Analysis of K-Means and Bisecting K-Means Algorithms in Weblog Data”
K.Abirami and Dr.P.Mayilvahanan,
International Journal of Emerging Technologies in Engineering Research (IJETER)
Volume 4, Issue 8, (August 2016)
“Bisecting K-means Algorithm Based on K-valued Self-determining
and Clustering Center Optimization”
Jian Di, Xinyue Gou
School of Control and Computer Engineering,North China Electric Power University,
Baoding, Hebei, China (August 2017)
2.3.7. DBSCAN¶
The DBSCAN algorithm views clusters as areas of high density
separated by areas of low density. Due to this rather generic view, clusters
found by DBSCAN can be any shape, as opposed to k-means which assumes that
clusters are convex shaped. The central component to the DBSCAN is the concept
of core samples, which are samples that are in areas of high density. A
cluster is therefore a set of core samples, each close to each other
(measured by some distance measure)
and a set of non-core samples that are close to a core sample (but are not
themselves core samples). There are two parameters to the algorithm,
min_samples and eps,
which define formally what we mean when we say dense.
Higher min_samples or lower eps
indicate higher density necessary to form a cluster.
More formally, we define a core sample as being a sample in the dataset such
that there exist min_samples other samples within a distance of
eps, which are defined as neighbors of the core sample. This tells
us that the core sample is in a dense area of the vector space. A cluster
is a set of core samples that can be built by recursively taking a core
sample, finding all of its neighbors that are core samples, finding all of
their neighbors that are core samples, and so on. A cluster also has a
set of non-core samples, which are samples that are neighbors of a core sample
in the cluster but are not themselves core samples. Intuitively, these samples
are on the fringes of a cluster.
Any core sample is part of a cluster, by definition. Any sample that is not a
core sample, and is at least eps in distance from any core sample, is
considered an outlier by the algorithm.
While the parameter min_samples primarily controls how tolerant the
algorithm is towards noise (on noisy and large data sets it may be desirable
to increase this parameter), the parameter eps is crucial to choose
appropriately for the data set and distance function and usually cannot be
left at the default value. It controls the local neighborhood of the points.
When chosen too small, most data will not be clustered at all (and labeled
as -1 for “noise”). When chosen too large, it causes close clusters to
be merged into one cluster, and eventually the entire data set to be returned
as a single cluster. Some heuristics for choosing this parameter have been
discussed in the literature, for example based on a knee in the nearest neighbor
distances plot (as discussed in the references below).
In the figure below, the color indicates cluster membership, with large circles
indicating core samples found by the algorithm. Smaller circles are non-core
samples that are still part of a cluster. Moreover, the outliers are indicated
by black points below.
Examples:
Demo of DBSCAN clustering algorithm
Implementation
The DBSCAN algorithm is deterministic, always generating the same clusters
when given the same data in the same order.  However, the results can differ when
data is provided in a different order. First, even though the core samples
will always be assigned to the same clusters, the labels of those clusters
will depend on the order in which those samples are encountered in the data.
Second and more importantly, the clusters to which non-core samples are assigned
can differ depending on the data order.  This would happen when a non-core sample
has a distance lower than eps to two core samples in different clusters. By the
triangular inequality, those two core samples must be more distant than
eps from each other, or they would be in the same cluster. The non-core
sample is assigned to whichever cluster is generated first in a pass
through the data, and so the results will depend on the data ordering.
The current implementation uses ball trees and kd-trees
to determine the neighborhood of points,
which avoids calculating the full distance matrix
(as was done in scikit-learn versions before 0.14).
The possibility to use custom metrics is retained;
for details, see NearestNeighbors.
Memory consumption for large sample sizes
This implementation is by default not memory efficient because it constructs
a full pairwise similarity matrix in the case where kd-trees or ball-trees cannot
be used (e.g., with sparse matrices). This matrix will consume \(n^2\) floats.
A couple of mechanisms for getting around this are:
Use OPTICS clustering in conjunction with the
extract_dbscan method. OPTICS clustering also calculates the full
pairwise matrix, but only keeps one row in memory at a time (memory
complexity n).
A sparse radius neighborhood graph (where missing entries are presumed to
be out of eps) can be precomputed in a memory-efficient way and dbscan
can be run over this with metric='precomputed'.  See
sklearn.neighbors.NearestNeighbors.radius_neighbors_graph.
The dataset can be compressed, either by removing exact duplicates if
these occur in your data, or by using BIRCH. Then you only have a
relatively small number of representatives for a large number of points.
You can then provide a sample_weight when fitting DBSCAN.
References:
“A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases
with Noise”
Ester, M., H. P. Kriegel, J. Sander, and X. Xu,
In Proceedings of the 2nd International Conference on Knowledge Discovery
and Data Mining, Portland, OR, AAAI Press, pp. 226–231. 1996
“DBSCAN revisited, revisited: why and how you should (still) use DBSCAN.”
Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017).
In ACM Transactions on Database Systems (TODS), 42(3), 19.
2.3.8. HDBSCAN¶
The HDBSCAN algorithm can be seen as an extension of DBSCAN
and OPTICS. Specifically, DBSCAN assumes that the clustering
criterion (i.e. density requirement) is globally homogeneous.
In other words, DBSCAN may struggle to successfully capture clusters
with different densities.
HDBSCAN alleviates this assumption and explores all possible density
scales by building an alternative representation of the clustering problem.
This implementation is adapted from the original implementation of HDBSCAN,
scikit-learn-contrib/hdbscan based on [LJ2017].
2.3.8.1. Mutual Reachability Graph¶
HDBSCAN first defines \(d_c(x_p)\), the core distance of a sample \(x_p\), as the
distance to its min_samples th-nearest neighbor, counting itself. For example,
if min_samples=5 and \(x_*\) is the 5th-nearest neighbor of \(x_p\)
then the core distance is:
\[d_c(x_p)=d(x_p, x_*).\]
Next it defines \(d_m(x_p, x_q)\), the mutual reachability distance of two points
\(x_p, x_q\), as:
\[d_m(x_p, x_q) = \max\{d_c(x_p), d_c(x_q), d(x_p, x_q)\}\]
These two notions allow us to construct the mutual reachability graph
\(G_{ms}\) defined for a fixed choice of min_samples by associating each
sample \(x_p\) with a vertex of the graph, and thus edges between points
\(x_p, x_q\) are the mutual reachability distance \(d_m(x_p, x_q)\)
between them. We may build subsets of this graph, denoted as
\(G_{ms,\varepsilon}\), by removing any edges with value greater than \(\varepsilon\):
from the original graph. Any points whose core distance is less than \(\varepsilon\):
are at this staged marked as noise. The remaining points are then clustered by
finding the connected components of this trimmed graph.
Taking the connected components of a trimmed graph \(G_{ms,\varepsilon}\) is
equivalent to running DBSCAN* with min_samples and \(\varepsilon\). DBSCAN* is a
slightly modified version of DBSCAN mentioned in [CM2013].
2.3.8.2. Hierarchical Clustering¶
HDBSCAN can be seen as an algorithm which performs DBSCAN* clustering across all
values of \(\varepsilon\). As mentioned prior, this is equivalent to finding the connected
components of the mutual reachability graphs for all values of \(\varepsilon\). To do this
efficiently, HDBSCAN first extracts a minimum spanning tree (MST) from the fully
-connected mutual reachability graph, then greedily cuts the edges with highest
weight. An outline of the HDBSCAN algorithm is as follows:
Extract the MST of \(G_{ms}\)
Extend the MST by adding a “self edge” for each vertex, with weight equal
to the core distance of the underlying sample.
Initialize a single cluster and label for the MST.
Remove the edge with the greatest weight from the MST (ties are
removed simultaneously).
Assign cluster labels to the connected components which contain the
end points of the now-removed edge. If the component does not have at least
one edge it is instead assigned a “null” label marking it as noise.
Repeat 4-5 until there are no more connected components.
HDBSCAN is therefore able to obtain all possible partitions achievable by
DBSCAN* for a fixed choice of min_samples in a hierarchical fashion.
Indeed, this allows HDBSCAN to perform clustering across multiple densities
and as such it no longer needs \(\varepsilon\) to be given as a hyperparameter. Instead
it relies solely on the choice of min_samples, which tends to be a more robust
hyperparameter.
HDBSCAN can be smoothed with an additional hyperparameter min_cluster_size
which specifies that during the hierarchical clustering, components with fewer
than minimum_cluster_size many samples are considered noise. In practice, one
can set minimum_cluster_size =




    
 min_samples to couple the parameters and
simplify the hyperparameter space.
References:
[CM2013]
Campello, R.J.G.B., Moulavi, D., Sander, J. (2013). Density-Based Clustering
Based on Hierarchical Density Estimates. In: Pei, J., Tseng, V.S., Cao, L.,
Motoda, H., Xu, G. (eds) Advances in Knowledge Discovery and Data Mining.
PAKDD 2013. Lecture Notes in Computer Science(), vol 7819. Springer, Berlin,
Heidelberg.
Density-Based Clustering Based on Hierarchical Density Estimates
[LJ2017]
L. McInnes and J. Healy, (2017). Accelerated Hierarchical Density Based
Clustering. In: IEEE International Conference on Data Mining Workshops (ICDMW),
2017, pp. 33-42.
Accelerated Hierarchical Density Based Clustering
2.3.9. OPTICS¶
The OPTICS algorithm shares many similarities with the DBSCAN
algorithm, and can be considered a generalization of DBSCAN that relaxes the
eps requirement from a single value to a value range. The key difference
between DBSCAN and OPTICS is that the OPTICS algorithm builds a reachability
graph, which assigns each sample both a reachability_ distance, and a spot
within the cluster ordering_ attribute; these two attributes are assigned
when the model is fitted, and are used to determine cluster membership. If
OPTICS is run with the default value of inf set for max_eps, then DBSCAN
style cluster extraction can be performed repeatedly in linear time for any
given eps value using the cluster_optics_dbscan method. Setting
max_eps to a lower value will result in shorter run times, and can be
thought of as the maximum neighborhood radius from each point to find other
potential reachable points.
The reachability distances generated by OPTICS allow for variable density
extraction of clusters within a single data set. As shown in the above plot,
combining reachability distances and data set ordering_ produces a
reachability plot, where point density is represented on the Y-axis, and
points are ordered such that nearby points are adjacent. ‘Cutting’ the
reachability plot at a single value produces DBSCAN like results; all points
above the ‘cut’ are classified as noise, and each time that there is a break
when reading from left to right signifies a new cluster. The default cluster
extraction with OPTICS looks at the steep slopes within the graph to find
clusters, and the user can define what counts as a steep slope using the
parameter xi. There are also other possibilities for analysis on the graph
itself, such as generating hierarchical representations of the data through
reachability-plot dendrograms, and the hierarchy of clusters detected by the
algorithm can be accessed through the cluster_hierarchy_ parameter. The
plot above has been color-coded so that cluster colors in planar space match
the linear segment clusters of the reachability plot. Note that the blue and
red clusters are adjacent in the reachability plot, and can be hierarchically
represented as children of a larger parent cluster.
Examples:
Demo of OPTICS clustering algorithm
Comparison with DBSCAN
The results from OPTICS cluster_optics_dbscan method and DBSCAN are
very similar, but not always identical; specifically, labeling of periphery
and noise points. This is in part because the first samples of each dense
area processed by OPTICS have a large reachability value while being close
to other points in their area, and will thus sometimes be marked as noise
rather than periphery. This affects adjacent points when they are
considered as candidates for being marked as either periphery or noise.
Note that for any single value of eps, DBSCAN will tend to have a
shorter run time than OPTICS; however, for repeated runs at varying eps
values, a single run of OPTICS may require less cumulative runtime than
DBSCAN. It is also important to note that OPTICS’ output is close to
DBSCAN’s only if eps and max_eps are close.
Computational Complexity
Spatial indexing trees are used to avoid calculating the full distance
matrix, and allow for efficient memory usage on large sets of samples.
Different distance metrics can be supplied via the metric keyword.
For large datasets, similar (but not identical) results can be obtained via
HDBSCAN. The HDBSCAN implementation is
multithreaded, and has better algorithmic runtime complexity than OPTICS,
at the cost of worse memory scaling. For extremely large datasets that
exhaust system memory using HDBSCAN, OPTICS will maintain \(n\) (as opposed
to \(n^2\)) memory scaling; however, tuning of the max_eps parameter
will likely need to be used to give a solution in a reasonable amount of
wall time.
References:
“OPTICS: ordering points to identify the clustering structure.”
Ankerst, Mihael, Markus M. Breunig, Hans-Peter Kriegel, and Jörg Sander.
In ACM Sigmod Record, vol. 28, no. 2, pp. 49-60. ACM, 1999.
2.3.10. BIRCH¶
The Birch builds a tree called the Clustering Feature Tree (CFT)
for the given data. The data is essentially lossy compressed to a set of
Clustering Feature nodes (CF Nodes). The CF Nodes have a number of
subclusters called Clustering Feature subclusters (CF Subclusters)
and these CF Subclusters located in the non-terminal CF Nodes
can have CF Nodes as children.
The CF Subclusters hold the necessary information for clustering which prevents
the need to hold the entire input data in memory. This information includes:
Number of samples in a subcluster.
Linear Sum - An n-dimensional vector holding the sum of all samples
Squared Sum - Sum of the squared L2 norm of all samples.
Centroids - To avoid recalculation linear sum / n_samples.
Squared norm of the centroids.
The BIRCH algorithm has two parameters, the threshold and the branching factor.
The branching factor limits the number of subclusters in a node and the
threshold limits the distance between the entering sample and the existing
subclusters.
This algorithm can be viewed as an instance or data reduction method,
since it reduces the input data to a set of subclusters which are obtained directly
from the leaves of the CFT. This reduced data can be further processed by feeding
it into a global clusterer. This global clusterer can be set by n_clusters.
If n_clusters is set to None, the subclusters from the leaves are directly
read off, otherwise a global clustering step labels these subclusters into global
clusters (labels) and the samples are mapped to the global label of the nearest subcluster.
Algorithm description:
A new sample is inserted into the root of the CF Tree which is a CF Node.
It is then merged with the subcluster of the root, that has the smallest
radius after merging, constrained by the threshold and branching factor conditions.
If the subcluster has any child node, then this is done repeatedly till it reaches
a leaf. After finding the nearest subcluster in the leaf, the properties of this
subcluster and the parent subclusters are recursively updated.
If the radius of the subcluster obtained by merging the new sample and the
nearest subcluster is greater than the square of the threshold and if the
number of subclusters is greater than the branching factor, then a space is temporarily
allocated to this new sample. The two farthest subclusters are taken and
the subclusters are divided into two groups on the basis of the distance
between these subclusters.
If this split node has a parent subcluster and there is room
for a new subcluster, then the parent is split into two. If there is no room,
then this node is again split into two and the process is continued
recursively, till it reaches the root.
BIRCH or MiniBatchKMeans?
BIRCH does not scale very well to high dimensional data. As a rule of thumb if
n_features is greater than twenty, it is generally better to use MiniBatchKMeans.
If the number of instances of data needs to be reduced, or if one wants a
large number of subclusters either as a preprocessing step or otherwise,
BIRCH is more useful than MiniBatchKMeans.
How to use partial_fit?
To avoid the computation of global clustering, for every call of partial_fit
the user is advised
To set n_clusters=None initially
Train all data by multiple calls to partial_fit.
Set n_clusters to a required value using
brc.set_params(n_clusters=n_clusters).
Call partial_fit finally with no arguments, i.e. brc.partial_fit()
which performs the global clustering.
Tian Zhang, Raghu Ramakrishnan, Maron Livny
BIRCH: An efficient data clustering method for large databases.
https://www.cs.sfu.ca/CourseCentral/459/han/papers/zhang96.pdf
Roberto Perdisci
JBirch - Java implementation of BIRCH clustering algorithm
https://code.google.com/archive/p/jbirch
2.3.11. Clustering performance evaluation¶
Evaluating the performance of a clustering algorithm is not as trivial as
counting the number of errors or the precision and recall of a supervised
classification algorithm. In particular any evaluation metric should not
take the absolute values of the cluster labels into account but rather
if this clustering define separations of the data similar to some ground
truth set of classes or satisfying some assumption such that members
belong to the same class are more similar than members of different
classes according to some similarity metric.
2.3.11.1. Rand index¶
Given the knowledge of the ground truth class assignments
labels_true and our clustering algorithm assignments of the same
samples labels_pred, the (adjusted or unadjusted) Rand index
is a function that measures the similarity of the two assignments,
ignoring permutations:
>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]
>>> metrics.rand_score(labels_true, labels_pred)
0.66...
The Rand index does not ensure to obtain a value close to 0.0 for a
random labelling. The adjusted Rand index corrects for chance and
will give such a baseline.
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
0.24...
As with all clustering metrics, one can permute 0 and 1 in the predicted
labels, rename 2 to 3, and get the same score:
>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.rand_score(labels_true, labels_pred)
0.66...
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
0.24...
Furthermore, both rand_score adjusted_rand_score are
symmetric: swapping the argument does not change the scores. They can
thus be used as consensus measures:
>>> metrics.




    
rand_score(labels_pred, labels_true)
0.66...
>>> metrics.adjusted_rand_score(labels_pred, labels_true)
0.24...
Perfect labeling is scored 1.0:
>>> labels_pred = labels_true[:]
>>> metrics.rand_score(labels_true, labels_pred)
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
Poorly agreeing labels (e.g. independent labelings) have lower scores,
and for the adjusted Rand index the score will be negative or close to
zero. However, for the unadjusted Rand index the score, while lower,
will not necessarily be close to zero.:
>>> labels_true = [0, 0, 0, 0, 0, 0, 1, 1]
>>> labels_pred = [0, 1, 2, 3, 4, 5, 5, 6]
>>> metrics.rand_score(labels_true, labels_pred)
0.39...
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
-0.07...
2.3.11.1.1. Advantages¶
Interpretability: The unadjusted Rand index is proportional
to the number of sample pairs whose labels are the same in both
labels_pred and labels_true, or are different in both.
Random (uniform) label assignments have an adjusted Rand index
score close to 0.0 for any value of n_clusters and
n_samples (which is not the case for the unadjusted Rand index
or the V-measure for instance).
Bounded range: Lower values indicate different labelings,
similar clusterings have a high (adjusted or unadjusted) Rand index,
1.0 is the perfect match score. The score range is [0, 1] for the
unadjusted Rand index and [-1, 1] for the adjusted Rand index.
No assumption is made on the cluster structure: The (adjusted or
unadjusted) Rand index can be used to compare all kinds of
clustering algorithms, and can be used to compare clustering
algorithms such as k-means which assumes isotropic blob shapes with
results of spectral clustering algorithms which can find cluster
with “folded” shapes.
2.3.11.1.2. Drawbacks¶
Contrary to inertia, the (adjusted or unadjusted) Rand index
requires knowledge of the ground truth classes which is almost
never available in practice or requires manual assignment by human
annotators (as in the supervised learning setting).
However (adjusted or unadjusted) Rand index can also be useful in a
purely unsupervised setting as a building block for a Consensus
Index that can be used for clustering model selection (TODO).
The unadjusted Rand index is often close to 1.0 even if the
clusterings themselves differ significantly. This can be understood
when interpreting the Rand index as the accuracy of element pair
labeling resulting from the clusterings: In practice there often is
a majority of element pairs that are assigned the different pair
label under both the predicted and the ground truth clustering
resulting in a high proportion of pair labels that agree, which
leads subsequently to a high score.
Examples:
Adjustment for chance in clustering performance evaluation:
Analysis of the impact of the dataset size on the value of
clustering measures for random assignments.
2.3.11.1.3. Mathematical formulation¶
If C is a ground truth class assignment and K the clustering, let us
define \(a\) and \(b\) as:
\(a\), the number of pairs of elements that are in the same set
in C and in the same set in K
\(b\), the number of pairs of elements that are in different sets
in C and in different sets in K
The unadjusted Rand index is then given by:
\[\text{RI} = \frac{a + b}{C_2^{n_{samples}}}\]
where \(C_2^{n_{samples}}\) is the total number of possible pairs
in the dataset. It does not matter if the calculation is performed on
ordered pairs or unordered pairs as long as the calculation is
performed consistently.
However, the Rand index does not guarantee that random label assignments
will get a value close to zero (esp. if the number of clusters is in
the same order of magnitude as the number of samples).
To counter this effect we can discount the expected RI \(E[\text{RI}]\) of
random labelings by defining the adjusted Rand index as follows:
\[\text{ARI} = \frac{\text{RI} - E[\text{RI}]}{\max(\text{RI}) - E[\text{RI}]}\]
References
Comparing Partitions
L. Hubert and P. Arabie, Journal of Classification 1985
Properties of the Hubert-Arabie adjusted Rand index
D. Steinley, Psychological Methods 2004
Wikipedia entry for the Rand index
Wikipedia entry for the adjusted Rand index
2.3.11.2. Mutual Information based scores¶
Given the knowledge of the ground truth class assignments labels_true and
our clustering algorithm assignments of the same samples labels_pred, the
Mutual Information is a function that measures the agreement of the two
assignments, ignoring permutations.  Two different normalized versions of this
measure are available, Normalized Mutual Information (NMI) and Adjusted
Mutual Information (AMI). NMI is often used in the literature, while AMI was
proposed more recently and is normalized against chance:
>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
0.22504...
One can permute 0 and 1 in the predicted labels, rename 2 to 3 and get
the same score:
>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
0.22504...
All, mutual_info_score, adjusted_mutual_info_score and
normalized_mutual_info_score are symmetric: swapping the argument does
not change the score. Thus they can be used as a consensus measure:
>>> metrics.adjusted_mutual_info_score(labels_pred, labels_true)  
0.22504...
Perfect labeling is scored 1.0:
>>> labels_pred = labels_true[:]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
>>> metrics.normalized_mutual_info_score(labels_true, labels_pred)  
This is not true for mutual_info_score, which is therefore harder to judge:
>>> metrics.mutual_info_score(labels_true, labels_pred)  
0.69...
Bad (e.g. independent labelings) have non-positive scores:
>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
-0.10526...
2.3.11.2.1. Advantages¶
Random (uniform) label assignments have a AMI score close to 0.0
for any value of n_clusters and n_samples (which is not the
case for raw Mutual Information or the V-measure for instance).
Upper bound  of 1:  Values close to zero indicate two label
assignments that are largely independent, while values close to one
indicate significant agreement. Further, an AMI of exactly 1 indicates
that the two label assignments are equal (with or without permutation).
2.3.11.2.2. Drawbacks¶
Contrary to inertia, MI-based measures require the knowledge
of the ground truth classes while almost never available in practice or
requires manual assignment by human annotators (as in the supervised learning
setting).
However MI-based measures can also be useful in purely unsupervised setting as a
building block for a Consensus Index that can be used for clustering
model selection.
NMI and MI are not adjusted against chance.
Examples:
Adjustment for chance in clustering performance evaluation: Analysis of
the impact of the dataset size on the value of clustering measures
for random assignments. This example also includes the Adjusted Rand
Index.
2.3.11.2.3. Mathematical formulation¶
Assume two label assignments (of the same N objects), \(U\) and \(V\).
Their entropy is the amount of uncertainty for a partition set, defined by:
\[H(U) = - \sum_{i=1}^{|U|}P(i)\log(P(i))\]
where \(P(i) = |U_i| / N\)




    
 is the probability that an object picked at
random from \(U\) falls into class \(U_i\). Likewise for \(V\):
\[H(V) = - \sum_{j=1}^{|V|}P'(j)\log(P'(j))\]
With \(P'(j) = |V_j| / N\). The mutual information (MI) between \(U\)
and \(V\) is calculated by:
\[\text{MI}(U, V) = \sum_{i=1}^{|U|}\sum_{j=1}^{|V|}P(i, j)\log\left(\frac{P(i,j)}{P(i)P'(j)}\right)\]
where \(P(i, j) = |U_i \cap V_j| / N\) is the probability that an object
picked at random falls into both classes \(U_i\) and \(V_j\).
It also can be expressed in set cardinality formulation:
\[\text{MI}(U, V) = \sum_{i=1}^{|U|} \sum_{j=1}^{|V|} \frac{|U_i \cap V_j|}{N}\log\left(\frac{N|U_i \cap V_j|}{|U_i||V_j|}\right)\]
The normalized mutual information is defined as
\[\text{NMI}(U, V) = \frac{\text{MI}(U, V)}{\text{mean}(H(U), H(V))}\]
This value of the mutual information and also the normalized variant is not
adjusted for chance and will tend to increase as the number of different labels
(clusters) increases, regardless of the actual amount of “mutual information”
between the label assignments.
The expected value for the mutual information can be calculated using the
following equation [VEB2009]. In this equation,
\(a_i = |U_i|\) (the number of elements in \(U_i\)) and
\(b_j = |V_j|\) (the number of elements in \(V_j\)).
\[E[\text{MI}(U,V)]=\sum_{i=1}^{|U|} \sum_{j=1}^{|V|} \sum_{n_{ij}=(a_i+b_j-N)^+
}^{\min(a_i, b_j)} \frac{n_{ij}}{N}\log \left( \frac{ N.n_{ij}}{a_i b_j}\right)
\frac{a_i!b_j!(N-a_i)!(N-b_j)!}{N!n_{ij}!(a_i-n_{ij})!(b_j-n_{ij})!
(N-a_i-b_j+n_{ij})!}\]
Using the expected value, the adjusted mutual information can then be
calculated using a similar form to that of the adjusted Rand index:
\[\text{AMI} = \frac{\text{MI} - E[\text{MI}]}{\text{mean}(H(U), H(V)) - E[\text{MI}]}\]
For normalized mutual information and adjusted mutual information, the normalizing
value is typically some generalized mean of the entropies of each clustering.
Various generalized means exist, and no firm rules exist for preferring one over the
others.  The decision is largely a field-by-field basis; for instance, in community
detection, the arithmetic mean is most common. Each
normalizing method provides “qualitatively similar behaviours” [YAT2016]. In our
implementation, this is controlled by the average_method parameter.
Vinh et al. (2010) named variants of NMI and AMI by their averaging method [VEB2010]. Their
‘sqrt’ and ‘sum’ averages are the geometric and arithmetic means; we use these
more broadly common names.
References
Strehl, Alexander, and Joydeep Ghosh (2002). “Cluster ensembles – a
knowledge reuse framework for combining multiple partitions”. Journal of
Machine Learning Research 3: 583–617.
doi:10.1162/153244303321897735.
Wikipedia entry for the (normalized) Mutual Information
Wikipedia entry for the Adjusted Mutual Information
[VEB2009]
Vinh, Epps, and Bailey, (2009). “Information theoretic measures
for clusterings comparison”. Proceedings of the 26th Annual International
Conference on Machine Learning - ICML ‘09.
doi:10.1145/1553374.1553511.
ISBN 9781605585161.
[VEB2010]
Vinh, Epps, and Bailey, (2010). “Information Theoretic Measures for
Clusterings Comparison: Variants, Properties, Normalization and
Correction for Chance”. JMLR
<https://jmlr.csail.mit.edu/papers/volume11/vinh10a/vinh10a.pdf>
[YAT2016]
Yang, Algesheimer, and Tessone, (2016). “A comparative analysis of
community
detection algorithms on artificial networks”. Scientific Reports 6: 30750.
doi:10.1038/srep30750.
2.3.11.3. Homogeneity, completeness and V-measure¶
Given the knowledge of the ground truth class assignments of the samples,
it is possible to define some intuitive metric using conditional entropy
analysis.
In particular Rosenberg and Hirschberg (2007) define the following two
desirable objectives for any cluster assignment:
homogeneity: each cluster contains only members of a single class.
completeness: all members of a given class are assigned to the same
cluster.
We can turn those concept as scores homogeneity_score and
completeness_score. Both are bounded below by 0.0 and above by
1.0 (higher is better):
>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]
>>> metrics.homogeneity_score(labels_true, labels_pred)
0.66...
>>> metrics.completeness_score(labels_true, labels_pred)
0.42...
Their harmonic mean called V-measure is computed by
v_measure_score:
>>> metrics.v_measure_score(labels_true, labels_pred)
0.51...
This function’s formula is as follows:
\[v = \frac{(1 + \beta) \times \text{homogeneity} \times \text{completeness}}{(\beta \times \text{homogeneity} + \text{completeness})}\]
beta defaults to a value of 1.0, but for using a value less than 1 for beta:
>>> metrics.v_measure_score(labels_true, labels_pred, beta=0.6)
0.54...
more weight will be attributed to homogeneity, and using a value greater than 1:
>>> metrics.v_measure_score(labels_true, labels_pred, beta=1.8)
0.48...
more weight will be attributed to completeness.
The V-measure is actually equivalent to the mutual information (NMI)
discussed above, with the aggregation function being the arithmetic mean [B2011].
Homogeneity, completeness and V-measure can be computed at once using
homogeneity_completeness_v_measure as follows:
>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
(0.66..., 0.42..., 0.51...)
The following clustering assignment is slightly better, since it is
homogeneous but not complete:
>>> labels_pred = [0, 0, 0, 1, 2, 2]
>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
(1.0, 0.68..., 0.81...)
v_measure_score is symmetric: it can be used to evaluate
the agreement of two independent assignments on the same dataset.
This is not the case for completeness_score and
homogeneity_score: both are bound by the relationship:
homogeneity_score(a, b) == completeness_score(b, a)
2.3.11.3.1. Advantages¶
Bounded scores: 0.0 is as bad as it can be, 1.0 is a perfect score.
Intuitive interpretation: clustering with bad V-measure can be
qualitatively analyzed in terms of homogeneity and completeness
to better feel what ‘kind’ of mistakes is done by the assignment.
No assumption is made on the cluster structure: can be used
to compare clustering algorithms such as k-means which assumes isotropic
blob shapes with results of spectral clustering algorithms which can
find cluster with “folded” shapes.
2.3.11.3.2. Drawbacks¶
The previously introduced metrics are not normalized with regards to
random labeling: this means that depending on the number of samples,
clusters and ground truth classes, a completely random labeling will
not always yield the same values for homogeneity, completeness and
hence v-measure. In particular random labeling won’t yield zero
scores especially when the number of clusters is large.
This problem can safely be ignored when the number of samples is more
than a thousand and the number of clusters is less than 10. For
smaller sample sizes or larger number of clusters it is safer to use
an adjusted index such as the Adjusted Rand Index (ARI).
These metrics require the knowledge of the ground truth classes while
almost never available in practice or requires manual assignment by
human annotators (as in the supervised learning setting).
Examples:
Adjustment for chance in clustering performance evaluation: Analysis of
the impact of the dataset size on the value of clustering measures
for random assignments.
2.3.11.3.3. Mathematical formulation¶
Homogeneity and completeness scores are formally given by:
\[h = 1 - \frac{H(C|K)}{H(C)}\]
\[c = 1 - \frac{H(K|C)}{H(K)}\]
where \(H(C|K)\) is the conditional entropy of the classes given
the cluster assignments and is given by:
\[H(C|K) = - \sum_{c=1}^{|C|} \sum_{k=1}^{|K|} \frac{n_{c,k}}{n}
\cdot \log\left(\frac{n_{c,k}}{n_k}\right)\]
and \(H(C)\) is the entropy of the classes and is given by:
\[H(C) = - \sum_{c=1}^{|C|} \frac{n_c}{n} \cdot \log\left(\frac{n_c}{n}\right)\]
with \(n\) the total number of samples, \(n_c\) and \(n_k\)
the number of samples respectively belonging to class \(c\) and
cluster \(k\), and finally \(n_{c,k}\) the number of samples
from class \(c\) assigned to cluster \(k\).
The conditional entropy of clusters given class \(H(K|C)\) and the
entropy of clusters \(H(K)\) are defined in a symmetric manner.
Rosenberg and Hirschberg further define V-measure as the harmonic
mean of homogeneity and completeness:
\[v = 2 \cdot \frac{h \cdot c}{h + c}\]
References
V-Measure: A conditional entropy-based external cluster evaluation
measure
Andrew Rosenberg and Julia Hirschberg, 2007




    

[B2011]
Identication and Characterization of Events in Social Media, Hila
Becker, PhD Thesis.
2.3.11.4. Fowlkes-Mallows scores¶
The Fowlkes-Mallows index (sklearn.metrics.fowlkes_mallows_score) can be
used when the ground truth class assignments of the samples is known. The
Fowlkes-Mallows score FMI is defined as the geometric mean of the
pairwise precision and recall:
\[\text{FMI} = \frac{\text{TP}}{\sqrt{(\text{TP} + \text{FP}) (\text{TP} + \text{FN})}}\]
Where TP is the number of True Positive (i.e. the number of pair
of points that belong to the same clusters in both the true labels and the
predicted labels), FP is the number of False Positive (i.e. the number
of pair of points that belong to the same clusters in the true labels and not
in the predicted labels) and FN is the number of False Negative (i.e the
number of pair of points that belongs in the same clusters in the predicted
labels and not in the true labels).
The score ranges from 0 to 1. A high value indicates a good similarity
between two clusters.
>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
0.47140...
One can permute 0 and 1 in the predicted labels, rename 2 to 3 and get
the same score:
>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
0.47140...
Perfect labeling is scored 1.0:
>>> labels_pred = labels_true[:]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
Bad (e.g. independent labelings) have zero scores:
>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
2.3.11.4.1. Advantages¶
Random (uniform) label assignments have a FMI score close to 0.0
for any value of n_clusters and n_samples (which is not the
case for raw Mutual Information or the V-measure for instance).
Upper-bounded at 1:  Values close to zero indicate two label
assignments that are largely independent, while values close to one
indicate significant agreement. Further, values of exactly 0 indicate
purely independent label assignments and a FMI of exactly 1 indicates
that the two label assignments are equal (with or without permutation).
No assumption is made on the cluster structure: can be used
to compare clustering algorithms such as k-means which assumes isotropic
blob shapes with results of spectral clustering algorithms which can
find cluster with “folded” shapes.
2.3.11.4.2. Drawbacks¶
Contrary to inertia, FMI-based measures require the knowledge
of the ground truth classes while almost never available in practice or
requires manual assignment by human annotators (as in the supervised learning
setting).
References
E. B. Fowkles and C. L. Mallows, 1983. “A method for comparing two
hierarchical clusterings”. Journal of the American Statistical Association.
https://www.tandfonline.com/doi/abs/10.1080/01621459.1983.10478008
Wikipedia entry for the Fowlkes-Mallows Index
2.3.11.5. Silhouette Coefficient¶
If the ground truth labels are not known, evaluation must be performed using
the model itself. The Silhouette Coefficient
(sklearn.metrics.silhouette_score)
is an example of such an evaluation, where a
higher Silhouette Coefficient score relates to a model with better defined
clusters. The Silhouette Coefficient is defined for each sample and is composed
of two scores:
a: The mean distance between a sample and all other points in the same
class.
b: The mean distance between a sample and all other points in the next
nearest cluster.
The Silhouette Coefficient s for a single sample is then given as:
\[s = \frac{b - a}{max(a, b)}\]
The Silhouette Coefficient for a set of samples is given as the mean of the
Silhouette Coefficient for each sample.
>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> X, y = datasets.load_iris(return_X_y=True)
In normal usage, the Silhouette Coefficient is applied to the results of a
cluster analysis.
>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.silhouette_score(X, labels, metric='euclidean')
0.55...
References
Peter J. Rousseeuw (1987). “Silhouettes: a Graphical Aid to the
Interpretation and Validation of Cluster Analysis”
. Computational and Applied Mathematics 20: 53–65.
2.3.11.5.1. Advantages¶
The score is bounded between -1 for incorrect clustering and +1 for highly
dense clustering. Scores around zero indicate overlapping clusters.
The score is higher when clusters are dense and well separated, which relates
to a standard concept of a cluster.
2.3.11.5.2. Drawbacks¶
The Silhouette Coefficient is generally higher for convex clusters than other
concepts of clusters, such as density based clusters like those obtained
through DBSCAN.
Examples:
Selecting the number of clusters with silhouette analysis on KMeans clustering : In this example
the silhouette analysis is used to choose an optimal value for n_clusters.
2.3.11.6. Calinski-Harabasz Index¶
If the ground truth labels are not known, the Calinski-Harabasz index
(sklearn.metrics.calinski_harabasz_score) - also known as the Variance
Ratio Criterion - can be used to evaluate the model, where a higher
Calinski-Harabasz score relates to a model with better defined clusters.
The index is the ratio of the sum of between-clusters dispersion and of
within-cluster dispersion for all clusters (where dispersion is defined as the
sum of distances squared):
>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> X, y = datasets.load_iris(return_X_y=True)
In normal usage, the Calinski-Harabasz index is applied to the results of a
cluster analysis:
>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.calinski_harabasz_score(X, labels)
561.62...
2.3.11.6.1. Advantages¶
The score is higher when clusters are dense and well separated, which relates
to a standard concept of a cluster.
The score is fast to compute.
2.3.11.6.2. Drawbacks¶
The Calinski-Harabasz index is generally higher for convex clusters than other
concepts of clusters, such as density based clusters like those obtained
through DBSCAN.
2.3.11.6.3. Mathematical formulation¶
For a set of data \(E\) of size \(n_E\) which has been clustered into
\(k\) clusters, the Calinski-Harabasz score \(s\) is defined as the
ratio of the between-clusters dispersion mean and the within-cluster dispersion:
\[s = \frac{\mathrm{tr}(B_k)}{\mathrm{tr}(W_k)} \times \frac{n_E - k}{k - 1}\]
where \(\mathrm{tr}(B_k)\) is trace of the between group dispersion matrix
and \(\mathrm{tr}(W_k)\) is the trace of the within-cluster dispersion
matrix defined by:
\[W_k = \sum_{q=1}^k \sum_{x \in C_q} (x - c_q) (x - c_q)^T\]
\[B_k = \sum_{q=1}^k n_q (c_q - c_E) (c_q - c_E)^T\]
with \(C_q\) the set of points in cluster \(q\), \(c_q\) the center
of cluster \(q\), \(c_E\) the center of \(E\), and \(n_q\) the
number of points in cluster \(q\).
References
Caliński, T., & Harabasz, J. (1974).
“A Dendrite Method for Cluster Analysis”.
Communications in Statistics-theory and Methods 3: 1-27.
2.3.11.7. Davies-Bouldin Index¶
If the ground truth labels are not known, the Davies-Bouldin index
(sklearn.metrics.davies_bouldin_score) can be used to evaluate the
model, where a lower Davies-Bouldin index relates to a model with better
separation between the clusters.
This index signifies the average ‘similarity’ between clusters, where the
similarity is a measure that compares the distance between clusters with the
size of the clusters themselves.
Zero is the lowest possible score. Values closer to zero indicate a better
partition.
In normal usage, the Davies-Bouldin index is applied to the results of a
cluster analysis as follows:
>>> from sklearn import datasets
>>> iris = datasets.load_iris()
>>> X = iris.data
>>> from sklearn.cluster import KMeans
>>> from sklearn.metrics import davies_bouldin_score
>>> kmeans = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans.labels_
>>> davies_bouldin_score(X, labels)
0.6619...
2.3.11.7.1. Advantages¶
The computation of Davies-Bouldin is simpler than that of Silhouette scores.
The index is solely based on quantities and features inherent to the dataset
as its computation only uses point-wise distances.
2.3.11.7.2. Drawbacks¶
The Davies-Boulding index is generally higher for convex clusters than other
concepts of clusters, such as density based clusters like those obtained from
DBSCAN.
The usage of centroid distance limits the distance metric to Euclidean space.
2.3.11.7.3. Mathematical formulation¶
The index is defined as the average similarity between each cluster \(C_i\)
for \(i=1, ..., k\) and its most similar one \(C_j\). In the context of
this index, similarity is defined as a measure \(R_{ij}\) that trades off:
\(s_i\), the average distance between each point of cluster \(i\) and
the centroid of that cluster – also know as cluster diameter.
\(d_{ij}\), the distance between cluster centroids \(i\) and \(j\).
A simple choice to construct \(R_{ij}\) so that it is nonnegative and
symmetric is:
\[R_{ij} = \frac{s_i + s_j}{d_{ij}}\]
Then the Davies-Bouldin index is defined as:
\[DB = \frac{1}{k} \sum_{i=1}^k \max_{i \neq j} R_{ij}\]
References
Davies, David L.; Bouldin, Donald W. (1979).
“A Cluster Separation Measure”
IEEE Transactions on Pattern Analysis and Machine Intelligence.
PAMI-1 (2): 224-227.
Halkidi, Maria; Batistakis, Yannis; Vazirgiannis, Michalis (2001).
“On Clustering Validation Techniques”
Journal of Intelligent Information Systems, 17(2-3), 107-145.
Wikipedia entry for Davies-Bouldin index.
2.3.11.8. Contingency Matrix¶
Contingency matrix (sklearn.metrics.cluster.contingency_matrix)
reports the intersection cardinality for every true/predicted cluster pair.
The contingency matrix provides sufficient statistics for all clustering
metrics where the samples are independent and identically distributed and
one doesn’t need to account for some instances not being clustered.
Here is an example:
>>> from sklearn.metrics.cluster import contingency_matrix
>>> x = ["a", "a", "a", "b", "b", "b"]
>>> y = [0, 0, 1, 1, 2, 2]
>>> contingency_matrix(x, y)
array([[2, 1, 0],
       [0, 1, 2]])
The first row of output array indicates that there are three samples whose
true cluster is “a”. Of them, two are in predicted cluster 0, one is in 1,
and none is in 2. And the second row indicates that there are three samples
whose true cluster is “b”. Of them, none is in predicted cluster 0, one is in
1 and two are in 2.
A confusion matrix for classification is a square
contingency matrix where the order of rows and columns correspond to a list
of classes.
2.3.11.8.1. Advantages¶
Allows to examine the spread of each true cluster across predicted
clusters and vice versa.
The contingency table calculated is typically utilized in the calculation
of a similarity statistic (like the others listed in this document) between
the two clusterings.
2.3.11.8.2. Drawbacks¶
Contingency matrix is easy to interpret for a small number of clusters, but
becomes very hard to interpret for a large number of clusters.
It doesn’t give a single metric to use as an objective for clustering
optimisation.
References
Wikipedia entry for contingency matrix
2.3.11.9. Pair Confusion Matrix¶
The pair confusion matrix
(sklearn.metrics.cluster.pair_confusion_matrix) is a 2x2
similarity matrix
\[\begin{split}C = \left[\begin{matrix}
C_{00} & C_{01} \\
C_{10} & C_{11}
\end{matrix}\right]\end{split}\]
between two clusterings computed by considering all pairs of samples and
counting pairs that are assigned into the same or into different clusters
under the true and predicted clusterings.
It has the following entries:
\(C_{00}\) : number of pairs with both clusterings having the samples
not clustered together
\(C_{10}\) : number of pairs with the true label clustering having the
samples clustered together but the other clustering not having the samples
clustered together
\(C_{01}\) : number of pairs with the true label clustering not having
the samples clustered together but the other clustering having the samples
clustered together
\(C_{11}\) : number of pairs with both clusterings having the samples
clustered together
Considering a pair of samples that is clustered together a positive pair,
then as in binary classification the count of true negatives is
\(C_{00}\), false negatives is \(C_{10}\), true positives is
\(C_{11}\) and false positives is \(C_{01}\).
Perfectly matching labelings have all non-zero entries on the
diagonal regardless of actual label values:
>>> from sklearn.metrics.cluster import pair_confusion_matrix
>>> pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 1])
array([[8, 0],
       [0, 4]])
>>> pair_confusion_matrix([0, 0, 1, 1], [1, 1, 0, 0])
array([[8, 0],
       [0, 4]])
Labelings that assign all classes members to the same clusters
are complete but may not always be pure, hence penalized, and
have some off-diagonal non-zero entries:
>>> pair_confusion_matrix([0, 0, 1, 2], [0, 0, 1, 1])
array([[8, 2],
       [0, 2]])
The matrix is not symmetric:
>>> pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 2])
array([[8, 0],
       [2, 2]])
If classes members are completely split across different clusters, the
assignment is totally incomplete, hence the matrix has all zero
diagonal entries:
>>> pair_confusion_matrix([0, 0, 0, 0], [0, 1, 2, 3])
array([[ 0,  0],
       [12,  0]])
References
“Comparing Partitions”
L. Hubert and P. Arabie, Journal of Classification 1985