1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Is it that you want a surely optimal (in the SSwithin=min sense) solution of these datasets? $\endgroup$
    – ttnphns
    Aug 27, 2019 at 8:47
  • $\begingroup$ K-means iterations always monotonically decreese SSwithin and converge on the optimum. The problem is that this found optimum is true for a specific set of initial centroids and not necessarily for any possible set of initial centroids. The key, therefore, is in coming across the best initial centroids. $\endgroup$
    – ttnphns
    Aug 27, 2019 at 8:59
  • $\begingroup$ Try various methods of initializing stats.stackexchange.com/q/317493/3277. If many of them lead to the same final centroids (i.e., same solution), the solution is surely (though not sure) the globally optimal. $\endgroup$
    – ttnphns
    Aug 27, 2019 at 9:06
  • $\begingroup$ @ttnphns Yes, I am looking for a global optimum. So, if the starting point is chosen properly, K-means will always converge to a global optimum? For example, if we happen to use an optimal solution as the initial point then the algorithm stops immediately. Is that right? I was wondering if you have a reference for some conditions for the initial solution that guarantee convergence to an optimum? $\endgroup$
    – rasul
    Aug 27, 2019 at 11:57
  • 2
    $\begingroup$ The trivial case is when the initial centres = the final centroids of the global optimal solution; then 0 iterations are needed. Apart from that case, nobody can tell for sure that the solution will be global optimal. But with not big datasets you can experiment with various initial seeds and finally come to a solution almost 100% sure to be the global optimum. $\endgroup$
    – ttnphns
    Aug 27, 2019 at 14:01

2 Answers 2

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Expanding on that answer: If your clustering does not perfectly coincide with the correct clustering, there are similarity measures such as Jaccard coefficient, Fowlkes & Mallows Index or Rand Index you could use to compare them. $\endgroup$
    – nope
    Aug 27, 2019 at 8:16
  • 1
    $\begingroup$ Looks to me this doesn't answer the question. Iris classes need not to be the optimal clusters in the SSwithin=min sense. $\endgroup$
    – ttnphns
    Aug 27, 2019 at 8:35
  • $\begingroup$ I see what you mean. I guess I was referring to the classical way in which clustering on those sets is generally evaluated (the second question). If the question is whether there is a distribution of centroids for which the MSSC is minimal (and it of course matters then how distance is calculated and how many centroids are introduced), I wonder if someone ever grid searched this.. $\endgroup$
    – Mark Verhagen
    Aug 27, 2019 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.