I have a large set of data containing the description for 81432 images. These descriptions are generated by an image descriptor which generates a vector (for each image) with 127 positions. So, I have a matrix with 81432 rows and 127 columns.

I'm running kmeans from R, but I just don't know how to interpret the results. I've set a number of clusters, the algorithm runs and so what? I want to plot the Elbow rule, but I don't even know how to do it.

  • $\begingroup$ if it is necessary, i can provide some sample data $\endgroup$ – Victor Leal Oct 13 '15 at 16:23
  • $\begingroup$ Are you asking for a decision rule regarding the number of clusters to retain from k-means or for approaches to understanding what the clusters "mean?" $\endgroup$ – Mike Hunter Oct 27 '15 at 11:36
  • $\begingroup$ I was wondering about the first one (a decision rule regarding the number of clusters). $\endgroup$ – Victor Leal Oct 27 '15 at 11:50

To plot the Elbow Rule, we can use the tot.withinss returned by the kmeans model from R.

According to R documentation, tot.withinss represents the Total within-cluster sum of squares, i.e. sum(withinss).


This ancient pdf by the great Glenn Milligan reviews a range of cluster decision rules and may still be helpful:


There is also this Wikipedia entry on cluster stopping rules: https://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set

Finally, there have been numerous discussions in CV on this topic over the years to which the sidebar (right hand side) of this thread provides pointers.

Having personally done a ton of work with k-means solutions, I've never been able to find or develop a single stopping rule that worked for me. Moreover, having reviewed many papers over the years where such algorithmic solutions were proposed and reviewed, I haven't found a single approach that worked both consistently and well. In this sense, I think of k-means clustering as more an art than a science -- not to mention that I have an aversion to rigidly applied cookbook recipes, rules and prescriptions. But, this requires a lot of hand work which machine learning enthusiasts despise.

What I've found is that the best approach triangulates results from several metrics across a range of possible solutions. The possibilities are determined by adjusting the composition of the input information in incrementing solutions from one to the next, as well as the number and size of the seeds used -- which are random seeds in my case. I'm with the ML enthusiasts in not wanting to take the time to hand curate seeds. While I suppose an "expert system" of some sort could be developed from this protocol, I've never taken the time or trouble to do so.

First, I'm interested in the distribution of the cluster frequencies focused primarily on how "lumpy" they are. This simply involves "eyeballing" the frequencies. In other words, if a few clusters have most of the observations and the remaining clusters are sparsely populated, that suggests tightening up the cutoff for the size of the seeds used. Similarly, if 40% or more of the data is in a single cluster, then I look for ways to unpack that cluster.

Next, I look at the change in the "pseudo-Rsquared" as the results increment from one solution to the next. This may be a similar metric to your "Elbow Rule." Here again, subjective judgement determines what a "reasonable" magnitude for change is.

Finally, I employ the cubic clustering criterion, looking for the first occurrence of a maximal value across all of the possible solutions. The CCC was developed by Warren Sarle at SAS back in the 80s and remains a useful metric. Here's Milligan's description of it:

The cubic clustering criterion is the test statistic provided by the SAS programming package (Ray, 1982; Sarle, 1983). The index is the product of two terms. The first term is the natural logarithm of (1 - E(R2))/(1 R2) where R2 is the proportion of variance accounted for by the clusters and its expected value is determined under the assumption that the data have been sampled from a uniform distribution based on a hyperbox. The second term is ((np/2)’s)/((.O01 E(R2))l-2), where p is an estimate of the dimensionality of the between cluster variation. The constant terms were chosen on the basis of extensive simulation results (Sarle, 1983). The maximum value across the hierarchy levels was used to indicate the optimal number of clusters in the data.

SAS has a document about it here: https://support.sas.com/documentation/onlinedoc/v82/techreport_a108.pdf

This "triangulating" approach has worked well for me across a nontrivial number of k-means solutions. However my audience was, for the most part, nontechnical marketers who were interested in putting a "human face" on otherwise abstract consumer segments. I fully recognize that this is a completely different objective from what the OP is describing wrt the mining of ~80,000+ images. Regardless and even with 100+ predictors, I wouldn't be afraid to leverage this method in arriving at an actionable solution.

I would begin with some sort of factorization or dimension reduction of the inputs.


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.