12.1 Introduction to Clustering
Consider a set of \(n\) data points. The goal is to form \(K \ll n\) clusters, indexed by \(k \in \{1, \ldots, K\}\). This implies that we need to search for a function \(C: \{1, \ldots, n\} \rightarrow \{1, \ldots, K\}\) that minimizes the within cluster distance, i.e.
\[W(C) = \frac{1}{2} \sum_{k=1}^{K} \sum_{C(i)=C(i')=k} d(x_i, x_{i'})\] where \(C(\cdot)\) is a cluster index function that assigns the \(i\)th observation to cluster \(C(i)\).
This is equivalent to maximizing the between cluster distance: \[B(C) = \frac{1}{2} \sum_{k=1}^{K} \sum_{C(i)=k}\sum_{C(i') \neq k} d_{i i'}\]
Note that the total distance can be broken down into \[\begin{align*} T &= \frac{1}{2} \sum_{i=1}^{n} \sum_{i'=1}^{n} d_{ii'} \\ &= \frac{1}{2} \sum_{k=1}^{K} \sum_{C(i)=k} \Biggl\{ \sum_{C(i') = k} d_{i i'} + \sum_{C(i') \neq k} d_{i i'} \Biggr\}\\ &= W(C) + B(C)\\ \end{align*}\]
Since, the total distance is fixed for a given set of data, we have that
\[\text{Minimize } W(C) \, \Leftrightarrow \, \text{Maximize } B(C)\]
Given a specific distance measure \(d(\cdot, \cdot)\), several algorithms can be used to find the clusters:
Combinatorial Algorithms
\(k\)-means Clustering
Hierarchical Clustering
Combinatorial Algorithms
For small \(n\) and \(K\), we could minimize \(W\) by using brute-force search. However, the number of ``tries” needed to complete the search is
\[S(n,K) = \frac{1}{K!} \sum_{k=0}^{K} (-1)^{K-k} \binom{K}{k} k^n\]
(the Stirling number of the second kind; for \(n>0\) the \(k=0\) term vanishes). This counts the number of ways to partition \(n\) observations into \(K\) nonempty unlabeled clusters.
It is clear that this is not feasible for large \(n\) and \(K\), since the number of distinct assignments can be extremely large. So, we need to develop more efficient algorithms that may not be optimal but they could be a reasonably good sub-optimal partition.