Centroid-based clustering is a type of clustering method that partitions or splits a data set into similar groups based on the distance between their centroids. Each cluster’s centroid, or center, is either the mean or median of all the points in the cluster depending on the data.

One of the most commonly used centroid-based clustering techniques is the k-means clustering algorithm. K-means assumes that the center of each cluster defines the cluster using a distance measure, mostly commonly Euclidean distance, to the centroid. To initialize the clustering, you provide a number of expected clusters, which represents the ‘K’ in K-means, and the algorithm attempts to find reasonable clusters across the data to match that number. The optimal k clusters in a given dataset is identified by iteratively minimizing the total distance between each point and its assigned cluster centroid.

K-means is a hard clustering approach, meaning each data point is assigned to a separate cluster and no probability associated with cluster membership. K-means works well when the clusters are of roughly equivalent size, and there are not significant outliers or changes in density across the data. K-means often performs poorly when the data is high dimensional or when clusters have significantly different sizes or densities. K-means is also especially sensitive to outliers since it tries to establish centroids based on the mean values of all values in the cluster and thus is susceptible to overfitting to include those outliers.

Another centroid based approach to K-means is K-medoids. Medoids are representative objects of a dataset or a cluster within a dataset whose sum of distances to other objects in the cluster is minimal. Instead of having an arbitrary centroid be the center of the graph, the algorithm creates clusters by using individual data points as the medoid or center of the cluster. Since the K-medoids algorithm uses extant data points rather than arbitrary centroids it is less sensitive to outliers.

Hierarchical clustering, sometimes called connectivity-based clustering, groups data points together based on the proximity and connectivity of their attributes. This method determines clusters based on how close data points are to one another across all of the dimensions. The idea is that objects that are nearer are more closely related than those that are far from each other. Unlike k-means, there is no need to pre-specify the number of clusters. Instead, the clustering algorithm creates a graph network of the clusters at each hierarchical level. This network is hierarchical, meaning that any given node in it only has one parent node but may have multiple child nodes. Hierarchical clusters can be graphed with a dendrogram to help visually summarize and organize discovered clusters and the hierarchy that they may contain.

There are two approaches to performing hierarchical cluster analysis:

Agglomerative: In agglomerative clustering a bottom-up approach starts with individual data points and successively merges clusters by compute the proximity matrix of all the clusters at the current level of the hierarchy to create a tree-like structure. Once one level of clusters has been created where all the clusters have no or low inter-cluster similarity, the algorithm moves to the set of newly created clusters and repeats the process until there is one root node at the top of the hierarchical graph. There are a variety of choices possible in terms of how these clusters should be merged with one another with tradeoffs in terms of the quality and efficiency of the clustering. In single-linkage clustering, the shortest distance between any pair of data points in two clusters is used as a similarity measure. In all-pairs linkage, the average across all pairs of data points is used, whereas in sampled linkage, a sampling of the data points in the two clusters is used for calculating the average distance. In centroid-linkage, the distance between the centroids is used. One challenge with agglomerative methods is that they can exhibit chaining, where larger clusters are naturally biased toward having closer distances to other points and so continue to get larger and larger and attract more data points into their cluster. Another disadvantage is that agglomerative methods may be much slower than divisive methods of constructing the hierarchy.

Divisive: In divisive hierarchical clustering methods, a top-down approach successively partitions the data points into a tree-like structure. The first step is to split the dataset into clusters using a flat-clustering method like K-Means. The clusters with the largest Sum of Squared Errors (SSE) are then partitioned further using a flat clustering method. The algorithm stops either when it reaches individual nodes or some minimum SSE. Divisive partitioning allows greater flexibility in terms of both the hierarchical structure of the tree and the level of balance in the different clusters. It is not necessary to have a perfectly balanced tree in terms of the depths of the different nodes or a tree in which the degree of every branch is exactly two. This allows the construction of a tree structure which allows different tradeoffs in the balancing of the node depths and node weights (number of data points in the node). Divisive hierarchical clustering can be faster than agglomerative hierarchical clustering, especially when the data doesn’t require constructing the tree all the way down to individual data points.

Distribution-based clustering, sometimes called probabilistic clustering, groups together data points based on their probability distribution. This approach assumes that there is a process generating normal distributions for each dimension of the data which create the cluster centers. It’s different from centroid-based clustering in that it doesn’t use a distance metric like a Euclidean or Manhattan distance. Instead, distribution based approaches look for a well-defined distribution which appears across each dimension. The cluster means are the means of the Gaussian distribution across each dimension. Distribution based clustering is a model-based approach to clustering because it requires fitting a distribution multiple times across each dimension to find clusters, which means that it can be computationally expensive when working with large data sets.

One commonly used approach to distribution-based clustering is to create Gaussian Mixture Model (GMM) through Expectation-Maximization. A GMM is named because of the assumption that each cluster is defined by a Gaussian Distribution, often called a normal distribution.

Consider a dataset with two distinct clusters, A and B, which are both defined by two different normal distributions: one along the x-axis and one along the y-axis. Expectation-Maximization begins a random guess for what those two distributions along each axis and then proceeds to improve iteratively by alternating two steps:

Expectation: Assign each data point to each of the clusters and compute the probability that it came from the Cluster A and the Cluster B.

Maximization: Update the parameters that define each cluster, a weighted mean location and a variance-covariance matrix, based on the likelihood of each data point being in the cluster. Then repeat the Expectation step until the equation converges on the distributions observed for each cluster.

Each data point is given a probability of being associated with a cluster. This means that clustering via Expectation Maximization is a soft clustering approach and that a given point may be probabilistically associated with more than one cluster. This makes sense in some scenarios, a song might be somewhat folk and somewhat rock or a user may prefer television shows in Spanish but sometimes also watch shows in English.

Density-based clustering works by detecting areas where points are concentrated and where they are separated by areas that are empty or sparse. Unlike centroid based approaches, like K-means, or distribution-based approaches, like Expectation Maximization, density-based clustering can detect clusters of an arbitrary shape. This can be extremely helpful when clusters aren’t defined around a specific location or distribution. Unlike other clustering algorithms, such as K-means and hierarchical clustering, a density-based algorithm can discover clusters of any shape, size, or density in your data. Density-based clustering also can distinguish between data points which are part of a cluster and those which should be labeled as noise. Density-based clustering is especially useful when working with datasets with noise or outliers or when we don’t have prior knowledge about the number of clusters in the data.

DBSCAN is an example of a clustering algorithm which takes a density-based approach to clustering. It uses a density-based spatial clustering approach to create clusters with a density passed in by the user which centers around a spatial centroid. The area immediately around the centroid is referred to as a neighborhood and DBSCAN attempts to define neighborhoods of clusters that have the specified density. For each cluster, DBSCAN will define three types of data points:

Core Points: A data point is a core point if the neighborhood around that data point contains at least as many points as the user specified minimum number of points.

Border Points: A data point is a border point if the neighborhood around that data point contains less than the minimum number of data points but the neighborhood around that point contains a core point.

Outlier: A data point is an outlier if it is neither a core point nor a border point. Essentially, this is the “other” class.

HDBSCAN is a variant of DBSCAN which doesn’t require any parameters to be set; this can make it even more flexible than the original. HDBSCAN is less sensitive to noise and outliers in the data. Also, DBSCAN can sometimes have trouble identifying clusters with non-uniform density. This was a primary motivation for HDBSCAN and so it handles clusters of varying density much more effectively.

Grid-based clustering algorithms are not used as often as the previous four approaches but can be helpful in high dimensional clustering where other clustering algorithms may not be as performant. In this approach, the algorithm partitions a high-dimensional data set into cells. Each cell is assigned a unique identifier called a cell ID, and all data points falling within a cell are considered part of the same cluster.

Grid-based clustering is an efficient algorithm for analyzing large multidimensional datasets as it reduces the time needed to search for nearest neighbors, which is a common step in many clustering methods.

One popular grid-based clustering algorithm is called STING, which stands for STatistical INformation Grid. In STING, the spatial area is divided into rectangular cells and several levels of cells at different resolution levels. High-level cells are divided into several low-level cells. STING can be very efficient at computing clusters in big data scenarios where the datasets are extremely large because it simply partitions the dataset iteratively into finer grids and evaluates the number of points within that grid. A disadvantage of STING is that the boundaries of clusters need to be horizontally or vertically defined, the algorithm can’t detect non-rectangular cluster boundaries.

Another grid based algorithm which is particularly powerful with high dimensional data is the Clustering In Quest or CLIQUE algorithm. CLIQUE combines a grid-based and density-based approaches to clustering. In this algorithm the dataspace is divided into a grid and the relative density of points within the cells of the grid are compared and subspaces that have similar densities are merged. This approach finds dense units in all subspaces of interest and then measures whether similar clusters should be connected together. This means that CLIQUE can detect clusters of arbitrary shapes in high-dimensional data.

Clustering can help uncover anomalies by measuring which data points are not included in the clustering structure defined by the cluster analysis. Data points that belong to small or very sparse clusters or that are far away from their assigned cluster can be considered anomalies. Density-based methods like Expectation Maximization are used to identify data points in dense regions as normal and those in low-density regions as anomalies.

When trying to understand what customer personas or subsets of markets might exist, clustering can be a powerful tool to help perform customer segmentation. You may be able combine demographic data with customer behavior data to find what kinds of characteristics and purchasing patterns most often correlate.

Images can have their pixels clustered in a variety of ways that can help cut the image into different sections to split a foreground from a background, detect objects using similarities in color and brightness, or split images into regions of interest for further processing. With images, clustering methods process the pixels in the image and define areas within the image that represent the cluster.

Clustering analysis can be helpful in processing documents in multiple ways. Documents can be grouped by similarity to show which documents are most similar to one another. This can be based on document length, word frequency distribution, or other various ways of quantifying key characteristics about the document. Another common use case is to analyze clusters of sections of a document based on keyword frequency, sentence length, or distributions of terms. This can help in doing document summarization or in breaking larger documents into smaller datasets for further analysis.