2
$\begingroup$

I'm working on a project that requires some clustering analysis. In performing the analysis, I noticed something that seemed odd to me. I understand that in k-means the total sum of squares (total distance of all observations from the global center) equals the between sum of squares (distance between the centroids) plus the total within sum of squares (sum of the distances of each observation to its centroid). But I also see that total sum of squares is not exactly equal to the total variance of the distribution, which I don't understand. What I've noticed is that the two numbers (total sum of squares from k-means analysis vs. total variance) get closer to each other as the sample sizes get larger. Here's a quick simulation in R that shows what I'm talking about:

require(dplyr)
compare_sd_km <- function(numObs){
    set.seed(3)
    x <- rnorm(numObs, 0, 1)
    y <- rnorm(numObs, 0, 1)

    km <- kmeans(data.frame(x,y), centers = 5)

    kmeansMeasure <- (km$betweenss + km$tot.withinss) / numObs
    varianceMeasure <- var(x) + var(y)
    return(c(kmeansMeasure, varianceMeasure))
}

numObsMultipliers <- c(1:5)
numObsMultipliers <- sapply(numObsMultipliers, function(x) 10^x)
comparisons <- lapply(numObsMultipliers, function(x)  compare_sd_km(x))
comparisons <- as.data.frame(do.call(rbind, comparisons))
comparisons$observations <- numObsMultipliers
colnames(comparisons) <- c('kmeansMeasure', 'varianceMeasure', 'observations')
comparisons <- mutate(comparisons, difference = kmeansMeasure - varianceMeasure)
comparisons <- comparisons[, c(3,1,2,4)]

#### RESULT ####
  observations kmeansMeasure varianceMeasure     difference
1           10      1.142764        1.269738 -0.12697379740
2          100      1.920365        1.939762 -0.01939762318
3         1000      1.988562        1.990553 -0.00199055288
4        10000      2.031035        2.031238 -0.00020312381
5       100000      2.007437        2.007457 -0.00002007457

Any ideas what's going on here? Rounding issues? Something having to do with how the algorithms are implemented? Am I calculating something incorrectly? Or do total sum of squares and total variance actually mean something substantively different? Thanks for any help anyone can provide.

$\endgroup$
4
$\begingroup$

I believe the issue here is the var function in R computes the unbiased estimator of the variance, i.e.

$s^2 = \displaystyle \frac{\sum_{i = 1}^n (x_i - \bar x)^2 }{ (n-1)}$

I think what you are getting from k-means will be equivalent to the MLE of $\sigma^2$, i.e.

$\hat \sigma^2 = \displaystyle \frac{\sum_{i = 1}^n (x_i - \bar x)^2 }{ n}$

$\endgroup$
  • 1
    $\begingroup$ Thanks, @Cliff AB! You're 100% correct. When I change the line of code that says kmeansMeasure <- (kmbetweenss+kmbetweenss+kmtot.withinss) / numObs to kmeansMeasure <- (kmbetweenss+kmbetweenss+kmtot.withinss) / (numObs - 1) the numbers match exactly. Very much appreciated. $\endgroup$ – oneyellowlion Jun 6 '16 at 3:26

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.