Maximize K-Clustering Spacing: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 15: | Line 15: | ||
initially each point is a separate cluster | initially each point is a separate cluster | ||
repeat until only k clusters: | repeat until only k clusters: | ||
let p,q = closest pair of separated points <font color=teal># determines the current spacing | let p,q = closest pair of separated points <font color=teal># determines the current spacing</font> | ||
merge the clusters containing p and q into a single cluster | merge the clusters containing p and q into a single cluster | ||
</font> | </font> | ||
This algorithm is very similar in structure to the [[Kruskal's Algorithm|Kruskal's algorithm]]. | |||
=Correctness Proof= | =Correctness Proof= | ||
{{External|https://www.coursera.org/learn/algorithms-greedy/lecture/7lWTf/correctness-of-clustering-algorithm}} | {{External|https://www.coursera.org/learn/algorithms-greedy/lecture/7lWTf/correctness-of-clustering-algorithm}} | ||
Revision as of 21:07, 23 October 2021
External
Internal
Overview
This is a greedy algorithm that aims to maximize spacing between any two clusters. By spacing between two clusters we mean the minimum distance between any two separated points, which belong to two distinct clusters:
minseparated p, qd(p,q)
"Good" clustering means that all of the separated points should be as far apart as possible.
Algorithm
initially each point is a separate cluster repeat until only k clusters: let p,q = closest pair of separated points # determines the current spacing merge the clusters containing p and q into a single cluster
This algorithm is very similar in structure to the Kruskal's algorithm.