Chapter 12 Clustering Analysis
So far, all the methods we discussed were presented in a supervised learning framework. However, in our discussion of clustering analysis we will focus on unsupervised learning problems.
In the sequel, in our framework we no longer have a response variable \(Y\), but we only have access to the features \(\{x_i\}_{i=1}^{n}\), and our goal is to learn patterns in \(\textbf{X}\).
Some examples of unsupervised learning include estimation of the density or the covariance or the network structure using a set of features, which can become very challenging in high-dimensional settings. Clustering analysis is also primarily used in an unsupervised learning framework.
Clustering analysis is the identification of multiple regions of the feature space that contain modes of density, or in other words, regions of the feature space with some common similarities. In some cases, we are also interested in dimension reduction, in which case we want to identify low-dimensional manifolds within the feature space \(\mathcal{X}\) that represent high data density.
Clustering
When we cluster, we group the data set into subsets so that those within each subset are more closely related (similar) to each other than those objects assigned to other subsets. Each subset is called a cluster. We have two main types of clustering: Flat Clustering and Hierarchical Clustering. Flat Clustering divides the data into \(k\) clusters, while hierarchical clustering arranges the clusters into a natural hierarchy.
Clustering results are dependent on the measure of similarity (or distance) between the “points” to be clustered. A distance metric or a distance function is a function that defines the dissimilarity of two elements (points, sets, etc.) Mathematically, a distance function is non-negative; it is zero when two points are the same; it is symmetric and it satisfies the triangle inequality. The most popular examples of distances we will use are:
- The Euclidean Distance (appropriate for continuous variables):
\[d(u,v) = \|u-v\|_2 = \sqrt{\sum_{j=1}^{p} (u_j - v_j)^2}\]
The squared Euclidean distance \(\|u-v\|_2^2\) is not a metric (it fails the triangle inequality), but it is the quantity minimized by \(K\)-means. The two distances yield the same nearest-center assignments.
- The Hamming Distance (suited for categorical variables):
\[d(u,v) = \sum_{j=1}^{p} \mathbf{1}_{u_j \neq v_j} \]
In general, there is no universally best approach, so distance measures should be defined based on the application.
The Python code for this chapter is available here Python Code for Clustering . It reproduces the main R examples (kmeans, hclust, and the spectral clustering demo).