k-Means

k-Means Clustering

Say we have $n$ points $x_1,x_2,\dots ,x_n$. We want to partition them into $k$ sets $S_1,S_2,\dots ,S_k$ such that the cost of the partition is minimised, $c(S_1,S_2,\dots ,S_k)$:

$$c(S_1,S_2,\dots ,S_k)=\sum _{i=1}^n\underset{j\in [k]}{\min }\left[\begin{array}{c}||x_i-{\mu }_j|{|}_2^2\end{array}\right]$$

Where ${\mu }_i$ is the mid-point of each cluster, i.e. ${\mu }_i=\frac{1}{|S_i|}{\sum }_{j\in S_i}{x}_j$.

Where $||\cdot |{|}_2^2$ is the squared L2 norm (squared Euclidian distance).

Link to original

k-Means (Algorithm)

To perform k-Means Clustering:

1. Select $K$ points as initial cluster means (cluster centroids)
2. Assign each point in the data to the cluster with the closest centroid.
3. When all points have been assigned, recalculate the positions of the centroids.
4. Repeat steps $2$ and $3$ until centroids no longer change.

Link to original

Example of lucky initialisation (optimal cluster)

Example of arbitrarily bad cluster (sub-optimal clusters)

We can solve this issue by using k-Means++.

k-Means++

k-Means++ Algorithm

We can solve arbitrarily bad initialisations of clusters and generally find a solution much faster by using k-Means++. It can be shown that the approximation factor is at most $O(\log k)$.

1. Set the first centre to be one of the input points chosen uniformly at random. ${\mu }_1=\text{uniform}(x_1,x_2,\dots ,x_n)$
2. For cluster $i=2$ to $k$:
   1. For each point $x_j$, compute the distance to the nearest centre, i.e. calculate $d_j={\text{min}}_l\{||x_j-{\mu }_l|{|}_2\}$
   2. Open a new centre at a point using the weighted probability distribution that is proportional to $d_j$, that is: $\text{Pr}(\text{new centre in }{x}_j)=\frac{d_j^2}{{\sum }_l{d}_l^2}$
3. Continue with k-Means.

Link to original

k-Median

k-Median Clustering

Say we have $n$ points $x_1,x_2,\dots ,x_n$. We want to partition them into $k$ sets $S_1,S_2,\dots ,S_k$ such that the cost of the partition is minimised, $c(S_1,S_2,\dots ,S_k)$:

$$c(S_1,S_2,\dots ,S_k)=\sum _{i=1}^n\underset{j\in [k]}{\min }\left[\begin{array}{c}||x_i-{\mu }_j|{|}_1\end{array}\right]$$

Where ${\mu }_i$ is the mid-point of each cluster, i.e. ${\mu }_i=\frac{1}{|S_i|}{\sum }_{j\in S_i}{x}_j$. Where $||\cdot |{|}_1$ is the L1 norm (Manhattan distance).

Link to original

Elbow method

Elbow method (clustering)

The elbow method is a heuristic in determining the number of clusters in a data set. We plot the K-mean score (% of variance explained) against the number of clusters and picking the “elbow of the curve” as the number to use.

Pick the $k\in \{2,3,\dots ,n-1\}$ that maximises ${\text{cost}}_{k-1}/{\text{cost}}_k$ where ${\text{cost}}_j$ is the cost of clustering with $j$ clusters. $k=1,n$ are ruled out as they result in trivial clusters.

Link to original

Hierarchical Clustering

Hierarchical Clustering

Hierarchical clustering results in a series of clustering results:

• the results start off with each object in their own cluster and end with all of the objects in the same cluster
• the intermediate clusters are created by a series of merges
• the resultant tree-like structure is called a dendrogram

You build a binary tree of the data that successively merges similar groups of points, visualising this tree provides a useful summary of the data.

This resolves an issue with flat clustering (k-Means) where structure is lost.

Link to original

Agglomerative clustering (bottom up)

Agglomerative Clustering

Initially place each data point in its own clusters, repeatedly merge most similar clusters.

We create a graph, an edge can mean similarity or dissimilarity (we only look at similarities). A high similarity value means that the corresponding two nodes are very similar and should be in the same cluster.

Link to original

Similarity (Agglomerative Clustering)

The similarity between two clusters $C_1=\{a,b\}$ and $C_2=\{c,d\}$ is

Link to original

[animate slides 5-7]

The obtained merges can be represented in a dendogram:

Divisive clustering (top down)

Divisive Clustering

In divisive clustering, we split using bisection $k$-means (or sparsest cut), recursing on each part. In effect, working our way from the top down through the graph.

Link to original

Divisive Clustering Algorithm

1. Find a partition of the input similarity graph (or set of points) and:
   • Split using bisection $k$-means
   • Split using sparsest cut
2. Recurse on each part
3. Builds cluster-tree top-down

Link to original

Sparsest Cut

Sparsity of a cut

Given a graph with nodes $V$ and edges in $E\subset V\times V$. The sparsity of a cut $\varphi (S)$ is given by:

$$\varphi (S)=\frac{E(S,\bar{S})}{\text{min}(|S|,|\bar{S}|)}$$

Where $E(S,\bar{S})$ is the sum of weights of edges crossing the cut. Here $\bar{S}=VS$, so $\min (\cdot )$ is the min. number of elements of both sets.

Link to original

Sparsest cut

The sparsest cut of a graph is given by $S^{\ast }$ that minimises $\varphi (S^{\ast })$, i.e. $$ \phi(S^*) = \underset{S}{\text{min}} \phi(S)

Link to original