3
$\begingroup$

My question is probably elementary, and I apologize for that. I am reading Kogan's "Introduction to Clustering Large and High-Dimensional Data"; I am interested in understanding batch K-means and K-means and use it in $\operatorname{R}$. In the textbook it is stated that both algorithms need an initial choice of

  1. the number of clusters $K$
  2. An initial partition of the given dataset

Using such entries, the algorithms can perform the learning exercise. Kogan states that the initial partition is usually found using a Principal Direction Divisive Partitioning (PDDP) algorithm.

Looking at the K-means function kmeans in $\operatorname{R}$ I have noticed the absence of the initial partition as argument of the function itself. One can specify the number of clusters or a set of initial centers.

Moreover, the default K-mean algorithm used by kmeans is the one by Hartigan and Wong (1979). Unfortunately I have no access to the original paper, and I could not run through the original code, searching for the initial partition.

My questions are:

  • is there an initial partition choice hidden somewhere in kmeans? If yes, how is it chosen?
  • In absence of initial partition choice, how does kmeans begins to run (a high level overview would be great!)?

I thank you all.

Improve this question
$\endgroup$
10
  • $\begingroup$ Many k-means implementations start with k randomly selected points. $\endgroup$ – Marc Claesen Aug 14 '13 at 9:13
  • $\begingroup$ I believe these are the centers: I would like to understand how to produce the initial partition, or modify it in the function kmeans. Maybe I am wrong and no initial partition is used at all... $\endgroup$ – Avitus Aug 14 '13 at 9:22
  • 2
    $\begingroup$ The partition is based completely on the location of the centers, e.g. a point belongs to the cluster with closest center. $\endgroup$ – Marc Claesen Aug 14 '13 at 9:28
  • $\begingroup$ Ok, so the algorithm receives the position of the centers, then minimizes the euclidean function to produce an initial partition and then begins to run? If I select just the number of clusters $k$, then the algorithm picks $k$ random centers from the datasets and does the same as above: am I right? $\endgroup$ – Avitus Aug 14 '13 at 9:36
  • 1
    $\begingroup$ Not sure if you have already seen it, but here is the C code used by R for the Lloyd and MacQueen algorithms fossies.org/linux/misc/R-3.0.1.tar.gz:a/R-3.0.1/src/library/… If centers are not specified they are randomly chosen (from kmeans.R: centers <- x[sample.int(m, k), , drop = FALSE]) $\endgroup$ – nico Aug 16 '13 at 8:03
4
$\begingroup$

Compute the centers of the predefined partitions, and use these to run k-means.

Try to find a library that has the book by Hartigan, his variant should be explained there.

A good article discussing the merits of his variant is this:

  • Hartigan’s Method: k-means Clustering without Voronoi
    Telgarsky, Vattani

And always remember that K-means is just a partitioning heuristic. It does not actually look for structure, and there are tons of toy examples where it just fails badly. Consider it a preprocessing method. In particular, when the Euclidean distance isn't what you really want to use on your data.

Being a good heuristic means it will often give reasonable good results; in particular when used in certain ways. Even when the results (e.g. due to outliers) may appear quite bad in a strict analysis of the clustering result.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Really interesting answer, thank you! My next step is to run K-means with distances different from the euclidean one. Btw...have you any reference containing a good number (let us say >2) of k-means "counterexamples" (=surprisingly bad performance)? $\endgroup$ – Avitus Aug 16 '13 at 9:43
  • $\begingroup$ See the wikipedia article for 3 examples where k-means fails to find the intuitively correct solution. E.g. iris data. As for Euclidean distance, k-means may stop converging if you use it with different distances. The problem is the mean step. If you cannot prove that the mean also reduces distances, it may no longer converge. (Actually, K-means does not try to minimize distances. It minimizes variance, which minimizes squared euclidean, which minimizes euclidean.) $\endgroup$ – Has QUIT--Anony-Mousse Aug 16 '13 at 11:00
  • $\begingroup$ Within-Cluster-Sum-of-Squares is the actual objective function used by k-means, locally minimized by both steps of the Floyd algorithm. $\endgroup$ – Has QUIT--Anony-Mousse Aug 16 '13 at 11:04
  • $\begingroup$ K-medoids is a k-means variation that works with any distance metric. Instead of using the mean, it uses the medoid, the most central element of the cluster. Then you have guaranteed convergence again, because both steps optimize the same quantity, the sum-of-distances-to-cluster-medoid. $\endgroup$ – Has QUIT--Anony-Mousse Aug 16 '13 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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