Why choosing proper initial centroids is very important for K-means? I don't fully understand why choosing proper initial centroids is very important for K-means. Demos or simple explanations will be very grateful. Thank you !
 A: The algorithm may find a suboptimal solution when the centers are chosen badly. Google for "k-means local minimum example" and you will likely find some examples.
There is no feasible way to guarantee finding the optimal solution (NP hard, too expensive), so you need heuristics.
But one of the most effective heuristics is to simply choose random points initially, but retry this several times and keep the best only. k-means++ may or may not help (and you still need to run it multiple times for best results).
A: There's a terrific visualization of k-means at http://www.naftaliharris.com/blog/visualizing-k-means-clustering/.  You can select the number of centroids and their initial placement, and see how the initial placement impacts the ultimate cluster assignments (that is, how the solution resolves to local minima).
A: There are many different algorithms for solving the K-means problem. The most common one is called Lloyd's algorithm. The K-means problem itself is NP-hard, so any algorithm with a runtime that's practically usable will only give a locally optimal solution. The fact that we'll converge to a local minimum is what makes the procedure sensitive to initialization conditions. Methods like Lloyd's algorithm start with the parameters at some initial point. They iteratively adjust parameters to reduce the loss function at each step, then halt when no local step can give further improvements. Because the loss function is, in general, nonconvex, each local minimum will have a basin of attraction that surrounds it. The basin of attraction is a region of parameter space where--if initial parameters lie within it--the algorithm will converge to that local minimum. So, the initial parameters determine which solution is ultimately obtained. But, some local minima are better than others. This is why initialization matters. It's also worth mentioning that the difficulty of solving the K-means problem and the sensitivity to initial conditions can vary with the dataset.
A: Choosing adequate initial seeds affects both the speed and quality when using the Lloyd heuristic algorithm, an algorithm for solving K-means problem. It is because the algorithm works by iteratingly improving the centroids position, from previous centroids.
I would suggest you to use an algorithm for choosing the initial values if you don't know how to choose your seeds. Randomly selected ones is not always a good option. The k-means++ algorithm garantees to find a solution that is O(log k) competitive to the optimal k-means solution.
See here.
