K-mean clustering, why different initial positions of the clusters influence on the final clustering result?

I am not sure whether this question is suitable here. Anyway, it seems like people here are helpful. So here is my question.

In case of k-mean clustering, it is necessary to give the initial positions of the clusters. why different initial positions of the clusters influence on the fina开发者_StackOverflowl clustering result?

When you use k-means, the problem you really want to solve is to minimize the within cluster sum of squares (WCSS). There is no efficient way to solve this problem exactly (even for 2-d points). In more technical terms WCSS is an NP-hard problem.

k-means is an iterative method that finds an approximate solution to the WCSS problem, this general scheme k-means uses is an expectation-maximization method. Most iterative methods require a starting point, and in general the quality of the solution will depend on the starting point.