13
$\begingroup$

I was using the kmeans instruction of R for performing the k-means algorithm on Anderson's iris dataset. I have a question about some parameters that I got. The results are:

Cluster means:
  Sepal.Length Sepal.Width Petal.Length Petal.Width
1     5.006000    3.428000     1.462000    0.246000

In this case, what does "Cluster means" stands for? It is the mean of the distances of all the objects within the cluster?

Also in the last part I have:

Within cluster sum of squares by cluster:
[1] 15.15100 39.82097 23.87947
 (between_SS / total_SS =  88.4 %)

That value of 88.4%, what it could be its interpretation?

$\endgroup$
4
  • 4
    $\begingroup$ Please don't cross post! stackoverflow.com/q/14524818/429846 $\endgroup$ – Gavin Simpson Jan 25 '13 at 16:27
  • $\begingroup$ No it's just the mean of all the objects inside the first cluster(3 in total). You can get 88.4% by iris.km\$betweenss/iris.km\$totss $\endgroup$ – dfhgfh Jan 25 '13 at 17:44
  • $\begingroup$ Read any article on k-means. Then it should be obvious what the clsuter means are... K-means is not distance based. It minimizes variances aka: "sum of squared deviations". $\endgroup$ – Has QUIT--Anony-Mousse Jan 25 '13 at 18:08
  • $\begingroup$ Assume that your mean is 0. Do the math. Check if above assumtion makes a difference. Live happily thereafter. Profit! $\endgroup$ – mia Mar 2 '17 at 9:47
26
$\begingroup$

If you compute the sum of squared distances of each data point to the global sample mean, you get total_SS. If, instead of computing a global sample mean (or 'centroid'), you compute one per group (here, there are three groups) and then compute the sum of squared distances of these three means to the global mean, you get between_SS. (When computing this, you multiply the squared distance of each mean to the global mean by the number of data points it represents.)

If there were no discernible pattern of clustering, the three means of the three groups would be close to the global mean, and between_SS would be a very small fraction of total_SS. The opposite is true here, which shows that data points cluster quite neatly in four dimensional space according to species.

$\endgroup$
14
$\begingroup$

K-means is not a distance based clustering algorithm.

K-means searches for the minimum sum of squares assignment, i.e. it minimizes unnormalized variance (=total_SS) by assigning points to cluster centers.

In order for k-means to converge, you need two conditions:

  • reassigning points reduces the sum of squares
  • recomputing the mean reduces the sum of squares

As there is only finite number of combinations, you cannot infinitely reduce this value and the algorithm must converge at some point to a local optimum.

Whenever you intend to change the assignment functions, you have the risk of making the algorithm not terminate anymore, like a dog chasing its own tail. Essentially both steps have to agree on the objective function. We do know that the arithmetic mean is the optimum choice with respect to sum of squares. And for the first step, we can just compute $\sum_i (x_i-\mu_{ji})^2$ for each mean $j$ and choose whichever is minimal. Technically, there is no distance computation here. Mathematically, assigning by least sum of squares is equal to assigning by closes squared Euclidean distance, which (if you waste the CPU cycles for computing sqrt) equals minimal Euclidean distance assignment. So the intuition of assigning each point to the closest mean is correct, but not what the optimization problem does.

between_SS probably is the weighted sum of squares between two means, to measure how well cluster centers are separated (note: cluster centers, it does not compare the actual clusters - technically, the cluster Voronoi cell touches the neighbor clusters Voronoi cell).

Note that with k-means you can improve the naive clustering quality by increasing k. The quality measured here is a mathematical value, which may not match the users requirements. Iris is actually a quite good example, where k-means often converges to less than satisfactory results, even given the external information that there should be exactly 3 clusters.

If you want a distance-based variation of k-means, look at k-medoids. Here convergence is ensured by replacing the mean with the medoid:

  • Each object is assigned to the nearest cluster (by an arbitrary distance measure)
  • The cluster center is updated to the most central object of the cluster, i.e. with the smallest average distance to all others.

In each step, the sum of distances reduces; there is a finite number of combinations, therefore the algorithm must terminate at some local minimum.

$\endgroup$
3
  • $\begingroup$ interesting point +1 $\endgroup$ – Cam.Davidson.Pilon Jan 26 '13 at 13:19
  • 1
    $\begingroup$ Why is there no distance computation here (in kmeans)? In order to calculate variance it is necessary to calculate the distance of each element to the mean, so there clearly is distance calculation involved, isn't it? $\endgroup$ – Funkwecker Sep 14 '17 at 11:30
  • $\begingroup$ Variance is usually not defined in terms of distance, but as "expected value of the squared deviation from the mean". $\endgroup$ – Has QUIT--Anony-Mousse Sep 15 '17 at 1:34

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.