# 2. Clustering with KMedoids and Common-nearest-neighbors¶

## 2.1. K-Medoids¶

`KMedoids`

is related to the `KMeans`

algorithm. While
`KMeans`

tries to minimize the within cluster sum-of-squares,
`KMedoids`

tries to minimize the sum of distances between each point and
the medoid of its cluster. The medoid is a data point (unlike the centroid)
which has the least total distance to the other members of its cluster. The use of
a data point to represent each cluster’s center allows the use of any distance
metric for clustering. It may also be a practical advantage, for instance K-Medoids
algorithms have been used for facial recognition for which the medoid is a
typical photo of the person to recognize while K-Means would have obtained a blurry
image that mixed several pictures of the person to recognize.

`KMedoids`

can be more robust to noise and outliers than `KMeans`

as it will choose one of the cluster members as the medoid while
`KMeans`

will move the center of the cluster towards the outlier which
might in turn move other points away from the cluster centre.

`KMedoids`

is also different from K-Medians, which is analogous to `KMeans`

except that the Manhattan Median is used for each cluster center instead of
the centroid. K-Medians is robust to outliers, but it is limited to the
Manhattan Distance metric and, similar to `KMeans`

, it does not guarantee
that the center of each cluster will be a member of the original dataset.

The complexity of K-Medoids is \(O(N^2 K T)\) where \(N\) is the number
of samples, \(T\) is the number of iterations and \(K\) is the number of
clusters. This makes it more suitable for smaller datasets in comparison to
`KMeans`

which is \(O(N K T)\).

Examples:

sphx_glr_auto_examples_plot_kmedoids_digits.py: Applying K-Medoids on digits with various distance metrics.

**Algorithm description:**
There are several algorithms to compute K-Medoids, though `KMedoids`

currently only supports K-Medoids solver analogous to K-Means called alternate
and the algorithm PAM (partitioning around medoids). Alternate algorithm is used
when speed is an issue.

Alternate method works as follows:

Initialize: Select

`n_clusters`

from the dataset as the medoids using a heuristic, random, or k-medoids++ approach (configurable using the`init`

parameter).Assignment step: assign each element from the dataset to the closest medoid.

Update step: Identify the new medoid of each cluster.

Repeat the assignment and update step while the medoids keep changing or maximum number of iterations

`max_iter`

is reached.

PAM method works as follows:

Initialize: Greedy initialization of

`n_clusters`

. First select the point in the dataset that minimizes the sum of distances to a point. Then, add one point that minimizes the cost and loop until`n_clusters`

points are selected. This is the`init`

parameter called`build`

.Swap Step: for all medoids already selected, compute the cost of swapping this medoid with any non-medoid point. Then, make the swap that decreases the cost the most. Loop and stop when there is no change anymore.

References:

Maranzana, F.E., 1963. On the location of supply points to minimize transportation costs. IBM Systems Journal, 2(2), pp.129-135.

Park, H.S. and Jun, C.H., 2009. A simple and fast algorithm for K-medoids clustering. Expert systems with applications, 36(2), pp.3336-3341.

Kaufman, L. and Rousseeuw, P.J. (2008). Partitioning Around Medoids (Program PAM). In Finding Groups in Data (eds L. Kaufman and P.J. Rousseeuw). doi:10.1002/9780470316801.ch2

Bhat, Aruna (2014).K-medoids clustering using partitioning around medoids for performing face recognition. International Journal of Soft Computing, Mathematics and Control, 3(3), pp 1-12.

## 2.2. Common-nearest-neighbors clustering¶

`CommonNNClustering`

provides an interface to density-based
common-nearest-neighbors clustering. Density-based clustering identifies
clusters as dense regions of high point density, separated by sparse
regions of lower density. Common-nearest-neighbors clustering
approximates local density as the number of shared (common) neighbors
between two points with respect to a neighbor search radius. A density
threshold (density criterion) is used – defined by the cluster
parameters `min_samples`

(number of common neighbors) and `eps`

(search
radius) – to distinguish high from low density. A high value of
`min_samples`

and a low value of `eps`

corresponds to high density.

As such the method is related to other density-based cluster algorithms
like `DBSCAN`

or Jarvis-Patrick. DBSCAN
approximates local density as the number of points in the neighborhood
of a single point. The Jarvis-Patrick algorithm uses the number of
common neighbors shared by two points among the \(k\) nearest neighbors.
As these approaches each provide a different notion of how density is
estimated from point samples, they can be used complementarily. Their
relative suitability for a classification problem depends on the nature
of the clustered data. Common-nearest-neighbors clustering (as
density-based clustering in general) has the following advantages over
other clustering techniques:

The cluster result is deterministic. The same set of cluster parameters always leads to the same classification for a data set. A different ordering of the data set leads to a different ordering of the cluster assignment, but does not change the assignment qualitatively.

Little prior knowledge about the data is required, e.g. the number of resulting clusters does not need to be known beforehand (although cluster parameters need to be tuned to obtain a desired result).

Identified clusters are not restricted in their shape or size.

Points can be considered noise (outliers) if they do not fullfil the density criterion.

The common-nearest-neighbors algorithm tests the density criterion for
pairs of neighbors (do they have at least `min_samples`

points in the
intersection of their neighborhoods at a radius `eps`

). Two points that
fullfil this criterion are directly part of the same dense data region,
i.e. they are *density reachable*. A *density connected* network of
density reachable points (a connected component if density reachability
is viewed as a graph structure) constitutes a separated dense region and
therefore a cluster. Note, that for example in contrast to
`DBSCAN`

there is no differentiation in
*core* (dense points) and *edge* points (points that are not dense
themselves but neighbors of dense points). The assignment of points on
the cluster rims to a cluster is possible, but can be ambiguous. The
cluster result is returned as a 1D container of labels, i.e. a sequence
of integers (zero-based) of length \(n\) for a data set of \(n\)
points,
denoting the assignment of points to a specific cluster. Noise is
labeled with `-1`

. Valid clusters have at least two members. The
clusters are not sorted by cluster member count. In same cases the
algorithm tends to identify small clusters that can be filtered out
manually.

Examples:

examples/cluster/plot_commonnn.py Basic usage of the

`CommonNNClustering`

examples/cluster/plot_commonnn_data_sets.py Common-nearest-neighbors clustering of toy data sets

Implementation:

The present implementation of the common-nearest-neighbors algorithm in
`CommonNNClustering`

shares some
commonalities with the current
scikit-learn implementation of `DBSCAN`

.
It computes neighborhoods from points in bulk with
`NearestNeighbors`

before
the actual clustering. Consequently, to store the neighborhoods
it requires memory on the order of
\(O(n ⋅ n_n)\) for \(n\) points in the data set where \(n_n\)
is the
average number of neighbors (which is proportional to `eps`

), that is at
worst \(O(n^2)\). Depending on the input structure (dense or sparse
points or similarity matrix) the additional memory demand varies.
The clustering itself follows a
breadth-first-search scheme, checking the density criterion at every
node expansion. The linear time complexity is roughly proportional to
the number of data points \(n\), the total number of neighbors \(N\)
and the value of `min_samples`

. For density-based clustering
schemes with lower memory demand, also consider:

`OPTICS`

– Density-based clustering related to DBSCAN using a`eps`

value range.cnnclustering – A different implementation of common-nearest-neighbors clustering.

Notes:

`DBSCAN`

provides an option to specify data point weights with`sample_weights`

. This feature is experimentally at the moment for`CommonNNClustering`

as weights are not well defined for checking the common-nearest-neighbor density criterion. It should not be used in production, yet.

References:

B. Keller, X. Daura, W. F. van Gunsteren “Comparing Geometric and Kinetic Cluster Algorithms for Molecular Simulation Data” J. Chem. Phys., 2010, 132, 074110.

O. Lemke, B.G. Keller “Density-based Cluster Algorithms for the Identification of Core Sets” J. Chem. Phys., 2016, 145, 164104.

O. Lemke, B.G. Keller “Common nearest neighbor clustering - a benchmark” Algorithms, 2018, 11, 19.