COSC345 Assignment 4 — k-Means P

Your name:

Student number:

Suppose we have measured a collection of “cases” that we would like to divide into k groups, so that each group is pretty much the same, and the groups are different. Also suppose that we have measured some numeric “features” for each of thes cases, and that we define two cases to be “similar” if the Euclidean distance between their feature vectors is small.

The k-means algorithm is a famous algorithm for doing this. You have to find your cases and measure them, and choose k, but the algorithm takes it from there.

An outer iteration goes

and we repeat that several times and take the best result.

An inner iteration goes

and we repeat that at most some number of times or until it stops improving.