Then this, blue one actually is also moved, okay.

Once we recompute the centroid, we may need to

go back to reassign these point to its closest centroid.

In this case you probably can see, the closest centroid, like this,

blue points assigned to the red ones, and

these red, this red one assigned to the blue side of the cluster.

Okay? Then we can calculate the centroid again.

Okay?

So this repeat the loop here until it becomes stable or

until the, the difference the different assignment becomes really, really small.

Now the first important thing we should know is,

this actually is a pretty efficient algorithm for clustering.

Because if we're told we'll have n objects,

we will want to find a K clusters.

Suppose we get a t iteration it becomes stable.

You probably can see the computational complexity is, every time every

object that you need to see which cluster is it belongs to, so this time,

you're assigning to the corresponding K centroid, so that's why it's n times K.

In total, you have t iterations,

that's why the computational complexity is big O of t times K times n.

usually K and t, number of cluster and

number of iterations, is far smaller than number of objects.

That's why if you give me n, supposed quite big number of objects,

this complexity essentially is a linear to the size of n.

The number of objects, that's efficient algorithms.

However, K-means clustering often may terminate at a local optimal.