I'm studying performance analysis and in the summarizing data methods there's the clustering. I understood what clustering is and the various algorithms to clusterize data, however in my book (The art of computer systems performance analysis, Raj Jain) there's written (according to clustering techniques) the following:
What I really don't understand is that statistic formula about variance underlined in red. How can we talk about intragroup and intergroup variance in clustering? My professor said that this formula is correct just for SDM(squared deviation from the mean) but not variances since you can't divide by n-1 each cluster as they are not populated of n elements. So we should talk about intragroup SDM and intergroup SDM. Furthermore let's suppose I computed a PCA before clustering and that I selected just 2 principal components that explains the 93% of variance (here it's clear we can talk about variances). Then I compute clustering (Ward method), and dendogram shows me the intragroup distance according to the number of the cluster I choose. How do I extimate the total variance lost after doing PCA+ clustering? How could it be done if I have to extimate SDM and not variance after clustering? Why on my book that formula refers to variances? Thanks
P.S. I used jmp tool
-
$\begingroup$ In statistics be deviance we rather understand the -2 times log-likelihood, are you sure you mean deviance..? How do you define it? $\endgroup$– Tim ♦Dec 12, 2016 at 23:20
-
$\begingroup$ oh sorry you are right. That was a translation error. It's the squared deviation from the mean not deviance $\endgroup$– MazzolaDec 12, 2016 at 23:29
-
$\begingroup$ just to be clear it's the variance multiplied by (n-1) $\endgroup$– MazzolaDec 12, 2016 at 23:35
-
$\begingroup$ You are right with the terminology grievance. The book probably meant to say variability, or scatter, not variance, where "Sum of squares [of deviations]" stand for variability. In clustering, as in ANOVA or MANOVA, there is true that SStotal=SSwithin+SSbetween. Note that this is related to the combined distance between clusters (their centroids). $\endgroup$– ttnphnsDec 13, 2016 at 1:10
-
$\begingroup$ As in ANOVA/MANOVA, variance or Mean square (MS) = SS/df. Df for "total" is N-1, for "between" is k-1, k being the number of classes (clusters). And pooled (i.e. weighted averaged) "within" variance has df=N-k. $\endgroup$– ttnphnsDec 13, 2016 at 1:26
2 Answers
Forget of PCA for now. You don't need PCA here.
k-means clustering (and Ward) are based on the idea of minimizing the sum-of-squares; and that value is related to variance.
There are different kinds of variance. Here you need the simple one, although it supposedly is biased. For large data, the difference doesn't matter. To understand that statement, assume variance is the simple $$1/N \sum_{x_i\in S} ||x_i - \mu_S||^2$$ And not N-1.
But now when looking at clusters, you want a cluster with many objects to have more influence. So for N objects, you take N times the variance. I.e., you take simply the sum of squares.
The proper version of the equation is
total-SSQ = within-cluster-SSQ + inbetween-clusters-SSQ = constant
It says that minimizing the SSQ (and equivalent, minimizing variance of a cluster) increases the separation of clusters; and conversely.
Intragroup variance is determining the variance within each cluster and combining them. Intergroup variance is determined by the distance between the cluster centers. I think something similar to Cochran's theorem applies to allow these variance estimates to be summed.
