2 ms·

Thanks! This now mentions and links Lloyd's algorithm. What happens when a cluster has no points assigned? I'm not sure, do you know? Is there much reasoning

by tmcw 14y ago

Thanks! This now mentions and links Lloyd's algorithm. What happens when a cluster has no points assigned? I'm not sure, do you know? Is there much reasoning for choosing other initial cluster means? Just better approximation? I'd rather not talk about optimizations to the algorithm too much; highly optimized algorithms aren't the best way to learn, and this is not an article about implementation.

tzs 14y ago
What you do when a cluster has no points depends on the details of the problem you are trying to apply clustering to. If you don't actually care how many clusters you have, you could just drop such cluster centers from the final output. If, on the other hand, you really want the number of clusters you asked for, one common approach is to abort the run if a cluster becomes entry and start over, with a new set of initial clusters. I'm not sure if it really matters much how you pick the initial clusters. Random within the space, rather than random from among the points, can simply be easier. Suppose you've got 100 points and are trying to split into 10 clusters. If you pick from the points, you need to pick without replacement so that you won't pick the same point twice. This can complicate things a little, depending on what data structures you are using and what's in your language's library. If, on the other hand, you are just picking 10 random points in the space, the chance of picking the same point twice is so low you can get away with not worrying about it. If you are curious, another place K-means clustering is used is in choosing points to serve as the centers for modeling a dataset with radial basis functions. There is an excellent set of lectures and slides on this in the Caltech machine learning video library here: http://work.caltech.edu/library/ http://work.caltech.edu/library/

by tmcw 14y ago

tzs 14y ago

What you do when a cluster has no points depends on the details of the problem you are trying to apply clustering to. If you don't actually care how many clusters you have, you could just drop such cluster centers from the final output. If, on the other hand, you really want the number of clusters you asked for, one common approach is to abort the run if a cluster becomes entry and start over, with a new set of initial clusters. I'm not sure if it really matters much how you pick the initial clusters. Random within the space, rather than random from among the points, can simply be easier. Suppose you've got 100 points and are trying to split into 10 clusters. If you pick from the points, you need to pick without replacement so that you won't pick the same point twice. This can complicate things a little, depending on what data structures you are using and what's in your language's library. If, on the other hand, you are just picking 10 random points in the space, the chance of picking the same point twice is so low you can get away with not worrying about it. If you are curious, another place K-means clustering is used is in choosing points to serve as the centers for modeling a dataset with radial basis functions. There is an excellent set of lectures and slides on this in the Caltech machine learning video library here: http://work.caltech.edu/library/ http://work.caltech.edu/library/