Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2014:journals:fred:4.7_clustering [2014/03/04 23:08] – created gisaf
+++ courses:cs211:winter2014:journals:fred:4.7_clustering [2014/03/04 23:20] (current) – gisaf
@@ Line 7: / Line 7: @@
 Minmum Spanning trees play a role in cases where we are given a set of n objects whose distance between any two objects is positive and symmetric. How possible is it to divide the objects into k groups, where k is the minimum distance between any pair of points?? Our goal is to seek k clusters or groups of objects with the **maximum possible spacing**. Our next question involves finding a most efficient k-clustering  with the maximum spacing.
 **Designing the Algorithm**.
-We start by considering growing a
+We start by considering growing a graph on vertex set U. Then draw an edge between the closets pair of points. Then draw another edge between the next closest pair in increasing order. If we are about to add an edge between two nodes that already belong to the same cluster, we will refrain from adding the edge because it wont change the set of components. In this way we wont have a cycle; thus giving us a union of trees.
+What is the connection to MST's? Our procedure is precisely applying Kruskal's MST Algorithm. We stop when we obtain k connected components. This is similar to taking a full MST , and deleting k-1 most expensive edges, and defining the k-clustering to be the resulting connected components.
+**Analyzing the Algorithm**.
+We claim that the components formed by deleting k-1 most expensive edges of the MST constitute a k-clustering of maximum spacing, proof on //page 160-161//. What is the running time of finding k-clusters?? It will take the running time Kruskal's Algorithm would take.
+This section was easy to read through but required some attention, its scale is 8.5/10.