6
$\begingroup$

I am learning about evaluating clustering outcome and am confused about the scatter matrices. Hoping to get some help here.

The within-cluster scatter matrix $S_W$is defined as: $$ S_W=\sum _{ k=1 }^{ K }{ \sum _{ x\in { C }_{ k } }^{ }{ \left( x-{ \mu }_{ k } \right) { \left( x-{ \mu }_{ k } \right) }^{ T } } } $$ The between-cluster matrix $S_B$ is defined as: $$ S_B=\sum _{ k=1 }^{ K }{ N_k }{ \left( { \mu }_{ k }-{ \mu } \right) { \left( { \mu }_{ k }-{ \mu } \right) }^{ T } } $$ where $K$ is number of clusters, $x$ is a member in cluster $C_k$, $\mu_k$ is centroids of cluster $C_k$, $N_k$ is number of members in cluster $C_k$, $\mu$ is the mean of the whole dataset.

My dataset has the form of $m$ by $d$, i.e. $m$ data points of $d$ dimensions (features). After clustering, each cluster $C_k$ has the form of $N_k$ by $d$. So, a point $x$ has the dimension of $1\times d$, likewise $\mu_k$ has the dimension of $1\times d$. And, $S_W$ and $S_B$ are scalar. Why are they not matrices? What exactly should I expect in the elements of the matrices? With that result, the use of $trace \left( S_W \right)$ and $trace \left( S_B \right)$ become irrelevant.

I sure has not understood the subject correctly. I will appreciate any help here.

Update 1:

The scatter matrix for each cluster is given as: $$ S_k=\sum _{ x\in { C }_{ k } }^{ }{ \left( x-{ \mu }_{ k } \right) { \left( x-{ \mu }_{ k } \right) }^{ T } } $$ which gives me a scalar quantity for $x$ and $\mu_k$ of size $1 \times d$. What should $S_{ k(i,j) }$ be? Given a dataset of $n$ observations with $d$ variables/features (i.e. $n \times d$), what should be the size of $S_k$?

To further clarify my problem, suppose one of the clusters has 2 members (rows) with 3 variables/features (columns): $$ C_k = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} $$ Then $$ { x }_{ 1 }=\left[ \begin{matrix} 1 & 2 & 3 \end{matrix} \right] \\ { x }_{ 2 }=\left[ \begin{matrix} 4 & 5 & 6 \end{matrix} \right] \\ { \mu }_{ k }=mean\left( { x }_{ 1 },{ x }_{ 2 } \right) =\left[ \begin{matrix} 2.5 & 3.5 & 4.5 \end{matrix} \right] \\ \left( { x }_{ 1 }-{ \mu }_{ k } \right) { \left( { x }_{ 1 }-{ \mu }_{ k } \right) }^{ T }=\left[ \begin{matrix} -1.5 & -1.5 & -1.5 \end{matrix} \right] \left[ \begin{matrix} -1.5 \\ -1.5 \\ -1.5 \end{matrix} \right] =6.75\\ \left( { x }_{ 2 }-{ \mu }_{ k } \right) { \left( { x }_{ 2 }-{ \mu }_{ k } \right) }^{ T }=\left[ \begin{matrix} 1.5 & 1.5 & 1.5 \end{matrix} \right] \left[ \begin{matrix} 1.5 \\ 1.5 \\ 1.5 \end{matrix} \right] =6.75\\ { S }_{ k }=\sum _{ x\in { C }_{ k } }^{ }{ \left( x-{ \mu }_{ k } \right) { \left( x-{ \mu }_{ k } \right) }^{ T } } =6.75+6.75=13.5 $$ So, $S_k$ is scalar and consequently $S_W$ will be scalar. Where did I go wrong in the above computation of scatter matrix for one cluster?

Update 2:

So, the data points should be column vectors. $$ { x }_{ 1 }=\left[ \begin{matrix} 1 \\ 2 \\ 3 \end{matrix} \right] \\ { x }_{ 2 }=\left[ \begin{matrix} 4 \\ 5 \\ 6 \end{matrix} \right] \\ { \mu }_{ k }=mean\left( { x }_{ 1 },{ x }_{ 2 } \right) =\left[ \begin{matrix} 2.5 \\ 3.5 \\ 4.5 \end{matrix} \right] \\ \left( { x }_{ 1 }-{ \mu }_{ k } \right) { \left( { x }_{ 1 }-{ \mu }_{ k } \right) }^{ T }=\left[ \begin{matrix} -1.5 \\ -1.5 \\ -1.5 \end{matrix} \right] \left[ \begin{matrix} -1.5 & -1.5 & -1.5 \end{matrix} \right] =\left[ \begin{matrix} 2.25 & 2.25 & 2.25 \\ 2.25 & 2.25 & 2.25 \\ 2.25 & 2.25 & 2.25 \end{matrix} \right]\\ \left( { x }_{ 2 }-{ \mu }_{ k } \right) { \left( { x }_{ 2 }-{ \mu }_{ k } \right) }^{ T }=\left[ \begin{matrix} 1.5 \\ 1.5 \\ 1.5 \end{matrix} \right] \left[ \begin{matrix} 1.5 & 1.5 & 1.5 \end{matrix} \right] =\left[ \begin{matrix} 2.25 & 2.25 & 2.25 \\ 2.25 & 2.25 & 2.25 \\ 2.25 & 2.25 & 2.25 \end{matrix} \right]\\ { S }_{ k }=\sum _{ x\in { C }_{ k } }^{ }{ \left( x-{ \mu }_{ k } \right) { \left( x-{ \mu }_{ k } \right) }^{ T } } =\left[ \begin{matrix} 2.25 & 2.25 & 2.25 \\ 2.25 & 2.25 & 2.25 \\ 2.25 & 2.25 & 2.25 \end{matrix} \right]+\left[ \begin{matrix} 2.25 & 2.25 & 2.25 \\ 2.25 & 2.25 & 2.25 \\ 2.25 & 2.25 & 2.25 \end{matrix} \right]=\left[ \begin{matrix} 4.5 & 4.5 & 4.5 \\ 4.5 & 4.5 & 4.5 \\ 4.5 & 4.5 & 4.5 \end{matrix} \right] $$ And finally, $S_W=\sum _{ k=1 }^{ K } S_k$. Yes, this is matrix! Do I get it right this time?

The size of $S_W$ is $d \times d$ ($d$ being dimension/no. of features of the data points). $trace(S_W)$ is then the sum-of-squared-error.

Update 3:

Using the approach given by @ttnphns, the data matrix for cluster k can be arranged in rows (while the equations above have data in columns): $$ X_k = \begin{bmatrix} x_1^T \\ x_2^T \end{bmatrix} = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} $$

Each columns has 2 elements, hence to center the matrix columns, the required center matrix is $$ C_2 = I(2) - \frac{1}{n}O(2) = \begin{bmatrix} 0.5 & -0.5 \\ -0.5 & 0.5 \end{bmatrix} $$ where $I(2)$ is identify matrix of size 2, $O(2)$ is 2-by-2 matrix of all 1's.

Center columns of matrix $X_k$, $$ X_k^c = C_2X_k = \begin{bmatrix} 0.5 & -0.5 \\ -0.5 & 0.5 \end{bmatrix}\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}\\=\begin{bmatrix} -1.5 & -1.5 & -1.5 \\ 1.5 & 1.5 & 1.5 \end{bmatrix} $$ Do $X_k^{c~T}X_k^c$ gives $S_k$ $$ S_k=X_k^{c~T}X_k^c = \begin{bmatrix} -1.5 & 1.5 \\ -1.5 & 1.5 \\ -1.5 & 1.5 \end{bmatrix}\begin{bmatrix} -1.5 & -1.5 & -1.5 \\ 1.5 & 1.5 & 1.5 \end{bmatrix}\\=\begin{bmatrix} 4.5 & 4.5 & 4.5 \\ 4.5 & 4.5 & 4.5 \\ 4.5 & 4.5 & 4.5 \end{bmatrix} $$ This is the same as in Update 2.

$\endgroup$
  • 1
    $\begingroup$ No, Sw and Sb aren't scalars. Don't you look at fancy formulas. Wording is better. A scatter matrix is just a covariance matrix without dividedness by "n-1" (i.e. a cov. matrix multiplied back by n-1). Compute scatter matrix for each cluster; sum all these matrices: this is Sw, pooled within-cluster scatter matrix. Compute scatter matrix St for the whole sample. Sb=St-Sw. $\endgroup$ – ttnphns Apr 8 '13 at 14:15
  • $\begingroup$ @ttnphns, many thanks for the help. My scatter matrix for each cluster, however, is a scalar given that both x and mu are of size 1xd. I have updated my question to clarify this doubt. $\endgroup$ – hong Apr 9 '13 at 2:59
  • $\begingroup$ Hong, @ttnphns is correct: your $x$ and $\mu$ should be considered column vectors, not row vectors. E.g., in Clustering Methods, the formulas in section 3 make it clear the $x_i$ are column vectors and the scatter matrix formulas in section 4 are identical to those you quote here. If you still think otherwise, then please let us know what the source of your formulas is so we can check it out. $\endgroup$ – whuber Apr 9 '13 at 5:54
  • $\begingroup$ @hong, Once again in words. For each cluster you have a data matrix A (or a row vector) point(s) X variables. Center columns of A and compute A'A. This is what called scatter matrix (see). (So, if A is a vector [?,?,?,?] then column-centered it is [0,0,0,0] and A'A is 4 X 4 matrix of zeros.) $\endgroup$ – ttnphns Apr 9 '13 at 7:35
  • $\begingroup$ @whuber, thank you very much! You hit my problem right on spot. I have been assuming the data points are row vectors. Indeed, I obtained the formula from the document you referred. However, embarrassingly, I did not and still cannot capture the fact that $x_i$ are column vectors. I will appreciate if you can point out the specific sentence in Section 3 of the referred document that clearly indicate $x_i$ are column vectors. This will greatly help me in reading future materials in this subject matter. Thanks a lot! $\endgroup$ – hong Apr 9 '13 at 11:45
4
$\begingroup$

What @whuber and I were saying to you in the comments are equivalent things. @whuber pointed out that the text you were reading makes points column vectors. I stuck to your own original notation where points are row vectors (this way of presenting is more common). When points are columns, thansposed ("T", or just ' in my notation) multiplier is the right one; when they are rows, it is the left one. Instead of multiplying separate vectors, it's more convenient to multiply whole matrices. See it with your data (matrix A = your "Ck"):

****** Points are rows, variables are columns [more common] ******
A
  1  2  3
  4  5  6

Column-centered A
  -1.500000000  -1.500000000  -1.500000000
   1.500000000   1.500000000   1.500000000

A'A, the scatter matrix
   4.500000000   4.500000000   4.500000000
   4.500000000   4.500000000   4.500000000
   4.500000000   4.500000000   4.500000000

****** Points are columns, variables are rows [that's how in your book] ******    
A
  1  4
  2  5
  3  6

Row-centered A
  -1.500000000   1.500000000
  -1.500000000   1.500000000
  -1.500000000   1.500000000

AA', the scatter matrix
   4.500000000   4.500000000   4.500000000
   4.500000000   4.500000000   4.500000000
   4.500000000   4.500000000   4.500000000
$\endgroup$
  • 1
    $\begingroup$ @ ttnphns, thanks! I got it! I was reading up on centering matrix (ya, I am weak in this subject) and updating the question and then only see your answer after edit. Many thanks! I have learned a lot from you and @whuber. Very much appreciate the time and kindness from both of you. $\endgroup$ – hong Apr 9 '13 at 12:57

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.