Clustering

Clustering is an unsupervised learning problem which tries to group a set of points into clusters such as that points in the same cluster are more similar to each other than points in different clusters, under a particular clustering distortion or distance measure.

There are two categorizations of clustering, e.g., hierarchical or partitional, depending on whether the algorithm clusters the data into a hierarchical structure or generates a flat partitioning of the data.

Hierarchical Clustering

In hierarchical clustering, the data is not partitioned into clusters in a single step. Instead, a series of partitions is created, which may run from a single cluster containing all objects to n clusters each containing a single object. This gives rise to a hierarchy of clusters, also known as the cluster dendrogram. Hierarchical clustering methods can be further subdivided into two kinds of methods as follows.

Divisive methods create the cluster dendrogram in a top-down divisive fashion, starting with every data point in one cluster and splitting clusters successively according to some measure until a convergence criterion is reached, e.g., COBWEB [36], PDDP or principal direction divisive partitioning [16], and recursive cluster-splitting using a statistical transformation [32].

Agglomerative methods create the cluster dendrogram in a bottom-up agglomerative fashion, starting with each data point in its own cluster and merging clusters suc-cessively according to a similarity measure till a convergence criterion is reached. A typical example is hierarchical agglomerative clustering algorithm.

To illustrate hierarchical clustering, let us consider hierarchical agglomerative cluster-ing in more detail.

Hierarchical Agglomerative Clustering

Hierarchical agglomerative clustering (HAC) is a bottom-up hierarchical clustering algo-rithm. In HAC, points are initially allocated to singleton clusters, and at each step the closest pair of clusters are merged, where closeness is defined according to a similarity measure between clusters. The algorithm generally terminates when a specified conver-gence criterion is reached. Different cluster-level similarity measures are used to determine the closeness between clusters to be merged—single-link, complete-link, or group-average [3].

Various HAC schemes have been recently shown to have well-defined underlying gen-erative models: single-link HAC corresponds to the probabilistic model of a mixture of

branching random walks, complete-link HAC corresponds to uniform equal-radius hyper-spheres, whereas group-average HAC corresponds to equal-variance configurations [51].

The pseudo-code for HAC is given in Algorithm 2.2.

Algorithm 2.2: Hierarchical Agglomerative Clustering (HAC) algorithm Input: Set of data points X ={x_i}ⁿ_i=1, x_i ∈R^d.

Output: Dendogram representing hierarchical clustering ofX.

1 Initialize clusters: Each data point x_i is placed in its own clusterC_i. These clusters form the leaves of the dendogram, and constitute the set of current clusters.

2 repeat

3 Merge the two closest clusters C_i and C_j from current clusters to get clusterC.

4 Remove C_i and C_j from current clusters, add cluster C to current clusters.

5 Add parent links from C_i and C_j toC in the cluster dendogram.

6 until convergence

Partitional Clustering Let X = xin

i=1, xi ∈ R^d be the set of n data points we want to cluster. A partitional clustering algorithm generates a K-partitioning² of the data (K given as input to the algorithm) by grouping the associated data points intoK clusters. Partitional algorithms can be classified into the following categories:

Graph-theoretic based These are discriminative clustering approaches, where an undi-rected graph G = (V, E) is constructed from the data set each vertex v_i ∈ V cor-responding to a data point x_i and the weight of each edge e_ij ∈ E corresponding to the similarity between the data points x_i and x_j according to a domain-specific similarity measure. TheK clustering problem becomes equivalent to finding the K-mincut in this graph, which is known to be a NP-complete problem forK >3. One class of methods for solving the graph partitioning problem take a real relaxation of the NP-complete discrete partitioning problem: these include spectral methods that perform clustering by using the second eigenvector of the graph Laplacian to define a cut [71]. The other class of methods use heuristics to find low-cost cuts inG:

groups nodes based on the idea of defining neighborhoods using inter-connectivity of nodes inG, performs fast multi-level heuristics on G at multiple resolutions to give good partitions, uses a modified cut criterion to ensure that the resulting clusters are well-balanced according to a specified balancing criterion [7].

Density-based These methods model clusters as dense regions and use different heuris-tics to find arbitrary-shaped high-density regions in the input data space and group points accordingly. Well-known methods include Denclue, which tries to analytically model the overall density around a point, and WaveCluster, which uses wavelet-transform to find high-density regions. Density-based methods typically have dif-ficulty scaling up to very high dimensional data (more than 10,000 dimensions), which are common in domains like text [7].

2K disjoint sets{X_k}^Kk=1 ofX, whose union isX

Mixture-model based In mixture-model based clustering, the underlying assumption is that each of the n data points {x_i}ⁿi=1 to be clustered are generated by one of K probability distributions {p_k}^K_k=1, where each distribution p_k is the conditional distribution corresponding to the clusterXk. The probability of observing any point x_i is given by:

P(x_i|Θ) =

∑K k=1

α_kp_k(x_i|θ_k) (2.7) where Θ = (α₁, . . . , α_k, θ₁, . . . , θ_k is the parameter vector, α₁, . . . , α_k are the prior probabilities of the clusters, and p_k is the probability distribution of cluster X_k parameterized byθ_k. The data generation process is assumed to be as follows: first, one of the K components is chosen following their prior probability distribution {α_k}^K_k=1; then, a data point is sampled following the distribution p_k of the chosen component.

Since the cluster assignment of the points are not known, we assume the existence of a random variable Y that encodes the cluster assignment y_i for each data point x_i and takes values in {1. . . K}. The goal of clustering in this model is to find the estimates of the parameter vector Θ and the cluster assignment variable Y such that the complete log-likelihood of the data:

L(X, Y|Θ) =

∑N i=1

logP(xi, yi|Θ) (2.8) is maximized, where the i.i.d. (identically and independently distributed) assump-tion over the data points inX leads to the factoring of the likelihood over the whole data set X into individual probabilities over each data point xi. Since Y is un-known, the log-likelihood cannot be maximized directly. So, traditional approaches iteratively maximize the expected log-likelihood in the Expectation Maximization (EM) framework (Dempster et al., 1977). Starting from an initial estimate of Θ, the EM algorithm iteratively improves the estimates of Θ and p(Y|X,Θ) such that the expected value of the complete-data log-likelihood is maximized, where the expecta-tion is computed w.r.t. the posterior class distribuexpecta-tionp(Y|X,Θ). It can be shown that the EM algorithm converges to a local maximum of the expected log-likelihood distribution (Dempster et al., 1977), and the final estimates of the conditional dis-tribution p(Y|X,Θ) on convergence of the algorithm, are used to find the cluster assignments of the points in X.

Most of the work in this area has assumed that the individual mixture density com-ponentsp_kare Gaussian, and in this case the parameters of the individual Gaussians are estimated by the EM procedure. The popular K-means clustering algorithm [57]

can be shown to be an EM algorithm on a mixture of K Gaussians under certain assumptions. Another interesting model for Gaussian mixture model-based clus-tering is AutoClass [21], which also has a Bayesian model selection component for choosing the optimal number of clusters.