The paper for BIRCH (a clustering algorithm) contains definitions of a Clustering Feature (CF) where the notation is unclear (cf. PDF page 3 / section 4).

A cluster contains N d-dimensional entries $ \{ \vec{X}_1, \vec{X}_2, \dots, \vec{X}_N \} $ and its CF is composed of three values.

  1. N the number of elements (straight forward)
  2. $ \vec{LS} $ "linear sum of the elements" $ \sum_{i=1}^N \vec{X}_i $
  3. $ SS $ "square sum of the N data points" $ \sum_{i=1}^N \vec{X}_i^2 $

The third value seems to cause confusion and is throwing me off. Let's start with the paper's definition.

I am parsing the notation as $ \sum_{i=1}^N \vec{X}_i^2 = \vec{X}_1^2 + \vec{X}_2^2 + \dots + \vec{X}_N^2 $. Now I am left with $ \vec{X}^2 $ and to my current understanding a dot/scalar product has to be applied, e.g. $ \vec{X}^2 = \vec{X} \cdot \vec{X} = \sum_{j=1}^d x_j^2 $ where $x_j$ is an Element in $ \vec{X} = ( x_1, x_2, \dots , x_d ) $.

On the other hand, there are plenty of lectures/slides providing examples in which the value is not a scalar, but the element-wise squared sum, while the notation in the respective definition does not reflect this. The German Wikipedia article even states $ SS $ is a "d-dimensional vector".

Basically they are doing it like this, using the earlier notation: $ \vec{X}_i = ( x_{i,1}, x_{i,2}, \dots , x_{i,d} ) $ $ \vec{SS} = (\sum_{i=1}^N x_{i,1}, \sum_{i=1}^N x_{i,2}, \dots, \sum_{i=1}^N x_{i,d}) = (x_{1,1}^2 + x_{2,1}^2 + \dots + x_{N,1}^2, ... ) $.

In the end the sum of the components would be the same.

Why is are those examples doing it differently? Am I missing something?

Examples describing SS as a scalar

Examples describing SS as a d-dimensional vector

Edit: Added links to paper and examples, fixed typos.

  • $\begingroup$ You should probably provide links to the various references. Presumably the actual algorithm comes out the same, but there might be several ways to present it. $\endgroup$ – Yuval Filmus Jun 11 '18 at 14:02
  • $\begingroup$ Do you have a link a freely available copy of the paper you're referring to? Providing a full citation and a link to a copy of the paper might help. I can see multiple things that notation might be referring to; and the best way to figure out what is intended might be to look at the context. $\endgroup$ – D.W. Jun 11 '18 at 15:45
  • $\begingroup$ I added links to the some example sources, I added a link to the paper in question, which can be found online, all other source are paywalled, I hope this is unproblematic. I might elaborate on the purpose of those values (context), which might give additional insight. $\endgroup$ – c11o Jun 11 '18 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.