Week 6

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.

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.

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.

Problem 4

Complete the notebook Choosing k (live).