K-Means clustering: optimal clusters for common data sets I use scikit-learn to get IRIS and WINE clusters for evaluating an algorithm for K-means clustering. The K-means algorithm is a heuristic algorithm for solving the "minimum-sum-of-squares-clustering (MSSC)" problem, that is, it does not guarantee to get an optimal solution for the MSSC. Therefore, I was wondering where I can find the optimal solutions of the IRIS and WINE instances of MSSC? Are you aware of any data sets for which the optimal clusters are available?
If such optimal solutions are not available, then I am wondering how different algorithms of K means are currently being compared?
 A: The problem of finding the partitioning that minimizes the trace of the within scatter matrix (this is the target criterion that k-means tries to minimize) has been shown to be NP-hard. For a proof, see

Drineas, Frieze, Kannan, Vempala, Vinay: "Clustering Large
Graphs via the Singular Value Decomposition." Machine Learning 56, pp. 9-33 (1999)

This means that there is no other way than brute force to find the global optimum. The article above, however, also presents an algorithm that finds a solution that is guaranteed to be less than two times the optimum criterion.
From a practical point of view, you should follow the suggestions in the comments to your question and use a primitive Monte Carlo algorithm by trying out different start points for k-means. This is actually what the R function kmeans does (see its argument nstart).
A: The IRIS dataset has labels. These are the ground truth values. 
You could evaluate whether your algorithm defines the same groups as the actual labels when running the algorithm on the features only.
If your algorithm defines three groups and these perfectly coincide with the three labels, you could say that your algorithm is working well.
