Clustering is the process of breaking down a large population that has a high degree of variation and noise into smaller groups with lower variation. It is a popular data mining activity. In a poll conducted by Kdnuggets, clustering was voted as the 3rd most frequently used data mining technique in 2011. Only decision trees and regression got more votes.

Cluster analysis is an important part of an analyst’s arsenal. One needs to master this technique as it is going to be used often in business situations. Some common applications of clustering are –

- Clustering customer behavior data for segmentation
- Clustering transaction data for fraud analysis in financial services
- Clustering call data to identify unusual patterns
- Clustering call-centre data to identify outlier performers (high and low)

Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters).

Cluster analysis itself is not one specific algorithm, but the general task to be solved. It can be achieved by various algorithms that differ significantly in their notion of what constitutes a cluster and how to efficiently find them. Popular notions of clusters include groups with small distances among the 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 values 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.

Connectivity models: for example, hierarchical clustering builds models based on distance connectivity.

Centroid models: for example, the k-means algorithm represents each cluster by a single mean vector.

Distribution models: clusters are modeled using statistical distributions, such as multivariate normal distributions used by the Expectation-maximization algorithm.

Density models: for example, DBSCAN and OPTICS defines clusters as connected dense regions in the data space.

Subspace models: in Biclustering (also known as Co-clustering or two-mode-clustering), clusters are modeled with both cluster members and relevant attributes.

Group models: some algorithms do not provide a refined model for their results and just provide the grouping information.

Graph-based models: a clique, that is, a subset of nodes in a graph such that every two nodes in the subset are connected by an edge can be considered as a prototypical form of cluster. Relaxations of the complete connectivity requirement (a fraction of the edges can be missing) are known as quasi-cliques, as in the HCS clustering algorithm

There are also finer distinctions possible, for example:

strict partitioning clustering: here each object belongs to exactly one cluster

strict partitioning clustering with outliers: objects can also belong to no cluster, and are considered outliers.

overlapping clustering (also: alternative clustering, multi-view clustering): while usually a hard clustering, objects may belong to more than one cluster.

hierarchical clustering: objects that belong to a child cluster also belong to the parent cluster

subspace clustering: while an overlapping clustering, within a uniquely defined subspace, clusters are not expected to overlap.

**There are also finer distinctions possible, for example:**

strict partitioning clustering: here each object belongs to exactly one cluster

strict partitioning clustering with outliers: objects can also belong to no cluster, and are considered outliers.

overlapping clustering (also: alternative clustering, multi-view clustering): while usually a hard clustering, objects may belong to more than one cluster.

hierarchical clustering: objects that belong to a child cluster also belong to the parent cluster

subspace clustering: while an overlapping clustering, within a uniquely defined subspace, clusters are not expected to overlap.

**k-means clustering**

In centroid-based clustering, clusters are represented by a central vector, which may not necessarily be a member of the data set. When the number of clusters is fixed to k, k-means clustering gives a formal definition as an optimization problem: find the k cluster centers and assign the objects to the nearest cluster center, such that the squared distances from the cluster are minimized.

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

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

.