4.1 Minimizing mean square distance to a set of vectors. Let 1,.. , xL be a collection of n-vectors. In this exercise you will fill in the missing parts of the argument to show that the vector z which minimizes the sum-square distance to the vectors, L2, J(z) is the average or centroid of the vectors, (1/L) (x L). (This result is used in one of the steps in the k-means algorithm. But here we have simplified the notation.) (a) Explain why, for any z, we have L L z-) (|-|22( r - ) (z-))L|-2 J(z) i=1 (-) (z - ) 0. Hint. Write the left-hand side as (b) Explain why T ) L (xi -) and argue that the left-hand vector is 0 Lz -2. we have J(z) > J(E). This shows that the choice z (c) Combine the results of (a) and (b) to get J(z) Explain why for any z , minimizes J(z) 1l- 4.3 Linear separation in 2-way partitioning. Clustering groups is called 2-way partitioning, since we are with index sets Gi and G2. Suppose 1,, XN. Show that there is a nonzero vector w and a scalar v that satisfy a collection of vectors into k 2 partitioning the vectors into 2 groups, 2, on the n-vectors we run k-means, with k w xiv0 for i E G1 w i 0 for i E G2. w is greater than or In other words, the affine function f(x) the first group, and less than or equal to zero on the second group. This is called linear separation of the two groups (although affine separation would be more accurate) Hint representatives equal to zero on Consider the function ||x - 21| | -21||,where z and z2 are the group