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.

• 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. Apr 8 '13 at 14:15
• @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.
– hong
Apr 9 '13 at 2:59
• 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.
– whuber
Apr 9 '13 at 5:54
• @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.) Apr 9 '13 at 7:35
• @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!
– hong
Apr 9 '13 at 11:45

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

• @ 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.
– hong
Apr 9 '13 at 12:57