Due: In class, Thursday November 30

**K-Means:**(20 points) Recall that the K-means algorithm minimizes the squared Euclidean distance from each point to its cluster mean (the objective function is given on (8.1) on p.500 of the book). Assume you are given a clustering with k clusters. In this problem, you will construct an algorithm that will extend the given clustering to a clustering with (k+1) clusters from this clustering.- One way to create a mean for the cluster (k+1) is to choose a vector at random as the mean. Show that if you choose such a vector and perform a half step of k-means (the assignment step - step (3) from Algorithm 8.1 in the book), then the k-means objective function will not increase (i.e. it will either decrease or stay the same).
- If you continue running the algorithm over the (k+1) clusters, the final objective function will be smaller than for that of the original clustering over k points. Argue why this is true.
- Give high level pseudo-code for an algorithm that starts with k = 1 clusters and iteratively increases the number of clusters, using the scheme given above.
- Do you think your algorithm will work well in practice? Why or why not? Can you suggest any improvements?

- Problem 2, p. 404 (10 points)
- Problem 11, p. 406 (10 points)