Question

Please write full justification for (a) and (b). Will uprate/vote!

4. K-means The goal of K-means clustering is to divide a set of n points into k< n subgroups of points that are "close" to each other. Each subgroup (or cluster) is identified by the center of the cluster, the centroid (μι, μ2' ··· ,14k) In class, we have seen a brute force approach to solve this problem exactly. Each of the k clusters is represented by a color, e.g., cluster 1 is red, cluster 2 is yellow and so on. We have k ways to color each point in the dataset. There are a finite number of ways to assign colors to all the points. For each coloring scheme, we can calculate the centroids as the center of all the points associated to each color, and then calculate the cost. Finally, we can choose the coloring scheme that provides the lowest cost (the best solution) Let's review this algorithm here by answering to the following questions (justify your answers) (a) True or False: With n points and k clusters, there are k" unique ways of assigning a color each point (b) For n - 100 points and k -5 clusters, how much time will it take to find the best clustering by naively searching through all possible ways to coloring these points? Assume that selecting and evaluating one particular choice of colors takes 10-2 seconds. Discuss if this is an acceptable time. Keep in mind that the estimated age of our universe is ะ 1017 seconds

Answer 1

a) True. We have k clusters. So each of the n points can belong to any one of the k clusters, thus having k options per item. So , total number of possible clusters for 2 items = k for the first item multiplied by k for the second item=k^2. Likewise for n items, we have k^n ways of assigning colors to each point.

b) Naively searching through all possible ways of coloring a set of n points will take k^n, in this case 5^100 units of time = 25^50 units of time = 25^48 sec. This is greater than 10^17 sec. The naive approach hence will fail in this case. We should remember that only 1 of the 5^100 arrangements is the correct answer.

K means works as follows.

Input : number of clusters we want (k) and number of data-points we have(n)

• initially all points are randomly scattered and unassigned. w
• we randomly assign m points with m distinct colors ( initial centers)
• for all remaining points:
• we calculate distance from the k centers and assign the point the color

of the center closest to it.

• Then we update the value of the centers of every cluster with the average coordinate value and update the center to that point closest to the average center.
• repeat entire process till no point updates its color from the previous setting

TIME COMPLEXITY: O(t*k*n*d) where t is number of iterations, k=number of clusters, n=number of points and d=number of dimensions each point has ( for 2D grid coordinates, its value is 2 ). Thus this approach is way better than the naive approach.