p36

Prévia do material em texto

8-36
Because of this behavior of the 
algorithm, we can dramatically reduce its 
execution time by relaxing our criteria of “no 
points are shifting from one cluster to 
another” to “fewer than 1% of the points are 
shifting from one cluster to another.”
This is a common approach!
N K-means is simple! 
For you computer science geeks:
K-means is an instance of the Expectation 
Maximization (EM) Algorithm, which is an 
iterative method that alternates between 
two phases. We start with an initial 
estimate of some parameter. In the K-
means case we start with an estimate of the 
centroids. In the expectation (E) phase, we 
use this estimate to place points into their 
expected cluster. In the Maximization (M) 
phase we use these expected values to 
adjust the estimate of the centroids. If you 
are interested in learning more about the 
EM algorithm the wikipedia page http://
en.wikipedia.org/wiki/Expectation
%E2%80%93maximization_algorithm is a 
good place to start.
http://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm
http://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm
http://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm
http://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm
http://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm
http://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm