k-means and Gaussian mixtures

Warm-up

One question before the lesson. Choose an answer and check it.

Try it yourself

Run k-means one step at a time: assign every student to the nearest centre, move the centres, and watch the error fall until nothing changes. Try new starts and other values of k. Then fit a Gaussian mixture by EM, a round at a time, and see each student’s shares.

Practice problems

Work each problem out on paper, then type your answer and press Check. Every problem has hints and a full solution.

Programming exercise

Write k-means, the normal density and a round of EM in plain Python. Save clusters.py and test_clusters.py in the same folder, fill in each function in clusters.py, and run the tests:

python test_clusters.py

"""k-means and Gaussian mixtures: programming exercise. Write k-means in plain Python, then the normal distribution's density and around of the EM algorithm for a mixture in one input. Run the tests fromthis folder:     python test_clusters.py A point is a list of two numbers, such as [hours studied, hours slept]. Acentre is a point too. labels[i] is the number of the centre point i belongsto: 0 for the first centre, 1 for the second, and so on.""" import math  # noqa: F401  (you will need math.exp, math.sqrt and math.pi)  def dist2(a, b):    """Return the squared distance between points a and b: (a[0] - b[0])**2 + (a[1] - b[1])**2."""    raise NotImplementedError  def assign(points, centres):    """Return each point's label: the number of its nearest centre by squared distance. If two centres are equally near, use the first."""    raise NotImplementedError  def update(points, labels, centres):    """Return the new centres: each one moved to the mean of its points. A centre with no points stays where it is."""    raise NotImplementedError  def inertia(points, labels, centres):    """Return the error: the total squared distance from each point to its own centre."""    raise NotImplementedError  def kmeans(points, centres):    """Run k-means from the given centres and return (centres, labels).     Assign every point, then move every centre, and repeat. Stop as soon as an    assignment is the same as the one before it, and return the centres that    assignment was made with, and the assignment.    """    raise NotImplementedError  def normal_pdf(x, mu, sigma):    """Return the normal distribution's density at x: e^(-(x - mu)**2 / (2 * sigma**2)) / (sigma * sqrt(2 * pi))."""    raise NotImplementedError  def shares(x, weights, mus, sigmas):    """Return the shares of a value x in each cluster of a mixture in one input: each weight times its cluster's density at x, divided by their total."""    raise NotImplementedError  def em_step(xs, weights, mus, sigmas):    """Do one round of EM for a mixture in one input, and return (weights, mus, sigmas).     E step: work out every value's shares. M step: for each cluster, the new    weight is its total share divided by the number of values, the new mu is    the share-weighted mean of the values, and the new sigma is the square    root of the share-weighted mean of (x - new mu)**2.    """    raise NotImplementedError 

Stuck? Write dist2 first, then assign and update, which kmeans repeats until no point changes centre. em_step works in one input: shares first, then each cluster’s weight, mean and spread from the shares. The Solution tab has one way to write each function.

In practice: clustering in real projects

Scale the inputs. k-means and Gaussian mixtures measure distances, so an input in large units drowns out the others. Standardise the inputs first, as in Lesson 6.

scikit-learn. KMeans(n_clusters=k) picks its first centres by k-means++, which spreads them apart, and n_init sets how many times the whole run is repeated, keeping the lowest error. GaussianMixture(n_components=k) is fitted by EM from a k-means start. Its covariance_type="diag" gives each cluster a spread per input, as in this lesson; its default, "full", lets each ellipse tilt as well.

Checking clusters. Clusters always come out, even from data with no groups in it. Check that they mean something: look at them, compare them with labels held back, as this lesson does, or see whether the same clusters come out of new data.

Test your knowledge

1. 01How does k-means work?Show answer

   Pick k starting centres. Give every point to its nearest centre, then move each centre to the mean of its points. Repeat until no point changes centre. Neither step can raise the total squared distance, so it always stops.

2. 02Why run k-means from several starts?Show answer

   It stops at a local minimum that depends on where it started, so some starts end with a much higher error. Running it several times and keeping the lowest error, or starting from spread-out centres with k-means++, avoids most bad endings.

3. 03How do you choose k?Show answer

   Plot the lowest error against k. It always falls as k grows, so look for the elbow, where one more cluster stops helping much. The silhouette score, or a mixture’s likelihood with a penalty for extra clusters (BIC), are other ways.

4. 04How is a Gaussian mixture different from k-means?Show answer

   Each cluster is a normal distribution with its own centre, spread and weight, and each point gets a share in every cluster instead of one label. k-means is close to the special case where every cluster is the same round bell and every share is 0 or 1.

5. 05What do the E and M steps of EM do?Show answer

   The E step works out each point’s share in each cluster from the current fit. The M step refits each cluster’s weight, centre and spread from all the points, each counted by its share. No round lowers the likelihood, so it converges, though possibly to a local best.

Exit ticket

One last question on the main idea of the lesson.