Week 6

ImportantNotes for the exam

Problem 1

Suppose the data consists of well-separated groups. Precisely, \([n]\) is split into disjoint groups \(G_1,\ldots,G_K\), and there are numbers \(\delta,\Delta>0\) such that

  • (tight groups) \(\|\bfx_i-\bfx_j\|_2\leq\delta\) whenever \(i\) and \(j\) are in the same group, and
  • (separated groups) \(\|\bfx_i-\bfx_j\|_2\geq\Delta\) whenever \(i\) and \(j\) are in different groups.

Think of \(\delta\) as small and \(\Delta\) as large.

Suppose further that \(\Delta>2\delta\), and that Lloyd’s algorithm with \(k=K\) starts from \(K\) data points as centers, one from each group. In this problem you will show that Lloyd’s algorithm then finds the groups exactly.

  1. Show that every point of a group is within distance \(\delta\) of the mean of that group.
  2. Show that the first assignment step makes the clusters exactly the groups.
  3. Show that the second assignment step changes nothing, so the algorithm stops with the groups as its clusters.

Hint: For this problem, remember the triangle inequality, \(\|\bfx+\bfy\|_2\leq\|\bfx\|_2+\|\bfy\|_2\).

NoteSolution sketch
  1. Let \(i\in G_a\) and let \(m=|G_a|\). Since \(\bar{\bfx}_{G_a}-\bfx_i=\frac1m\sum_{j\in G_a}(\bfx_j-\bfx_i)\), the triangle inequality gives \[ \|\bar{\bfx}_{G_a}-\bfx_i\|_2\leq\frac1m\sum_{j\in G_a}\|\bfx_j-\bfx_i\|_2\leq\frac1m\cdot m\delta=\delta. \]
  2. Let \(\bfs_a\) be the starting center in \(G_a\), and let \(i\in G_a\). Then \(\|\bfx_i-\bfs_a\|_2\leq\delta<\Delta\leq\|\bfx_i-\bfs_b\|_2\) for every \(b\neq a\), so \(\bfx_i\) is assigned to the cluster of \(\bfs_a\), with no ties. The clusters are therefore exactly the groups, and the update step moves each center to its group mean \(\bar{\bfx}_{G_a}\).
  3. Let \(i\in G_a\). By part 1, \(\bfx_i\) is within \(\delta\) of its own group mean. For \(b\neq a\), pick any \(j\in G_b\). The triangle inequality and part 1 again give \[ \Delta\leq\|\bfx_i-\bfx_j\|_2\leq\|\bfx_i-\bar{\bfx}_{G_b}\|_2+\|\bar{\bfx}_{G_b}-\bfx_j\|_2\leq\|\bfx_i-\bar{\bfx}_{G_b}\|_2+\delta, \] so \(\|\bfx_i-\bar{\bfx}_{G_b}\|_2\geq\Delta-\delta>\delta\), using \(\Delta>2\delta\). Every point is therefore still assigned to its own group, the assignment does not change, and the algorithm stops.

Problem 2

In this problem you will prove that more clusters never hurt the cost.

  1. Show that \(\operatorname{opt}_n=0\).
  2. Let \(1\leq k<n\). Starting from an optimal \(k\)-partition with its means as centers, build a \((k+1)\)-partition and centers whose cost is at most \(\operatorname{opt}_k\). Conclude that \(\operatorname{opt}_{k+1}\leq\operatorname{opt}_k\). Hint: since \(k<n\), some cluster has at least two points.
NoteSolution sketch
  1. The only \(n\)-partition puts every point in its own cluster. With each point as its own center, the cost is \(0\), and the cost is never negative.
  2. Take an optimal \(k\)-partition with means \(\bfmu_1,\ldots,\bfmu_k\). Since \(k<n\), some cluster \(S_\ell\) has at least two points. Move one of them, \(\bfx_i\), into a new singleton cluster with center \(\bfx_i\), keeping every other center. Both \(S_\ell\setminus\{i\}\) and \(\{i\}\) are non-empty, so this is a valid \((k+1)\)-partition, and the cost drops by \(\|\bfx_i-\bfmu_\ell\|_2^2\geq0\). So \(\operatorname{opt}_{k+1}\leq\operatorname{opt}_k\).

Problem 3

The \(k\)-means cost is written in terms of the points and their cluster means. In this problem you will rewrite it using only the squared distances \(D_{ij}=\|\bfx_i-\bfx_j\|_2^2\) between pairs of points, never the points themselves. This is useful because sometimes there are no points to begin with. For the vertices of a graph, or for documents, molecules, or survey responses, we can often say how far apart two items are (for a graph, say, the length of the shortest path between two vertices) without having coordinates for them. Given any such table of dissimilarities \(D_{ij}\), the right side of part 2 below still defines a clustering objective, and parts 3 and 4 show that, for Euclidean data, Lloyd’s algorithm itself needs nothing more than the table.

  1. Show that for every non-empty \(S\subseteq[n]\), \[ \sum_{i\in S}\|\bfx_i-\bar{\bfx}_S\|_2^2 =\frac{1}{2|S|}\sum_{i\in S}\sum_{j\in S}\|\bfx_i-\bfx_j\|_2^2. \] Hint: Recall the lemma for the sum of squares around a point.
  2. Deduce that \[ \operatorname{opt}_k=\min_{S_1,\ldots,S_k}\ \sum_{\ell=1}^k\frac{1}{2|S_\ell|}\sum_{i,j\in S_\ell}\|\bfx_i-\bfx_j\|_2^2, \] the minimum over all \(k\)-partitions.
  3. Part 2 lets you compute the cost of any partition from the matrix \(\bfD\) with entries \(D_{ij}\). Lloyd’s algorithm never computes the cost, though. Its assignment step needs the distance from each point to each cluster mean, and a cluster mean is usually not a data point, so these distances are not entries of \(\bfD\). Show that they can still be computed from \(\bfD\): for every non-empty \(S\subseteq[n]\) and every \(i\in[n]\) (in \(S\) or not), \[ \|\bfx_i-\bar{\bfx}_S\|_2^2=\frac{1}{|S|}\sum_{j\in S}D_{ij}-\frac{1}{2|S|^2}\sum_{j,l\in S}D_{jl}. \] Hint: use the same lemma as in part 1, together with part 1 itself.
  4. Suppose you are given only \(\bfD\), not the points. You run Lloyd’s algorithm starting from \(k\) data points as centers, and you keep track of the clusters \(S_1,\ldots,S_k\) instead of the centers. Assume no cluster ever becomes empty. Explain how to carry out each of the following using only \(\bfD\) and the current clusters:
    • the first assignment step;
    • every later assignment step;
    • the update step and the stopping test.
NoteSolution sketch
  1. Fix \(j\in S\). The lemma with \(\bfmu=\bfx_j\) gives \[ \sum_{i\in S}\|\bfx_i-\bfx_j\|_2^2=\sum_{i\in S}\|\bfx_i-\bar{\bfx}_S\|_2^2+|S|\,\|\bar{\bfx}_S-\bfx_j\|_2^2. \] Now sum over \(j\in S\). The first term on the right does not depend on \(j\), so it is counted \(|S|\) times, and the second term sums to \(|S|\) times the same quantity: \[ \sum_{i,j\in S}\|\bfx_i-\bfx_j\|_2^2=2|S|\sum_{i\in S}\|\bfx_i-\bar{\bfx}_S\|_2^2. \] Divide by \(2|S|\).
  2. By optimal centers and optimal assignments, \(\operatorname{opt}_k\) is the minimum of \(\operatorname{WCSS}(S_1,\ldots,S_k)\) over all \(k\)-partitions. Apply part 1 to each \(S_\ell\) in the sum defining \(\operatorname{WCSS}\).
  3. The lemma holds for every \(\bfmu\), so take \(\bfmu=\bfx_i\): \[ \sum_{j\in S}D_{ij}=\sum_{j\in S}\|\bfx_j-\bar{\bfx}_S\|_2^2+|S|\,\|\bar{\bfx}_S-\bfx_i\|_2^2. \] By part 1, the first term on the right is \(\frac{1}{2|S|}\sum_{j,l\in S}D_{jl}\). Move it to the left side and divide by \(|S|\).
  4. Let the starting centers be \(\bfx_{s_1},\ldots,\bfx_{s_k}\).
    • The first assignment step needs \(\|\bfx_i-\bfx_{s_\ell}\|_2^2=D_{is_\ell}\), which is an entry of \(\bfD\).
    • After the first update step, every center is the mean of its cluster, so each later assignment step needs \(\|\bfx_i-\bar{\bfx}_{S_\ell}\|_2^2\), which part 3 computes from \(\bfD\) and \(S_\ell\).
    • The update step replaces each center by its cluster mean. Since we store the clusters instead of the centers, there is nothing to compute: the next assignment step uses part 3 directly. The stopping test compares two assignments, which are just labels.
    By part 2, the cost of the final clustering also comes from \(\bfD\).

Problem 4

Complete the notebook Choosing k (live).

NoteSolution sketch

The four exercises are

return ((X - centers[labels]) ** 2).sum()                     # Exercise 1
a = dist[own].sum() / (own.sum() - 1)                         # Exercise 2
return (b - a) / max(a, b)
return (X - X.mean(axis=0)) / X.std(axis=0)                   # Exercise 3
return np.mean(costs <= 1.01 * best)                          # Exercise 4