3
$\begingroup$

I have to make a quick clustering program but the following formula is gibberish to me:

$\operatorname{Perf}(X,C) = \sum\limits_{i=1}^n\min\{||X_i-C_l||^2 \mid l = 1,...,K\}$

where $X$ is a set of multi-dimensional data and $C$ is a set of centroids for each data cluster.

This formula is a fitness function for an artificial bee colony clustering algorithm as a substitute for k-means clustering algorithm. It is described as a total within-cluster variance or the total mean-square quantization error (MSE).

Can anyone translate it to pseudo-code, normal human English, or at least enlighten me?

$\endgroup$
  • 2
    $\begingroup$ I don't think pseudocode or "human" English would be particularly enlightening. I suggest you learn how to read such formula; that opens up whole troughs of knowledge for you. $\endgroup$ – Raphael May 25 '12 at 9:43
6
$\begingroup$

Just break it down into parts:

$ \{ f(l) \mid l = 1,...,K \} $

This is a simple set construction. The above would simply create a set with all the elements from 1 to K. In your case the f(l) is the function:

$ ||X_i-C_l||^2 $

Given the || means the norm, these are vectors you are subtracting (rows of the X and C matrices). So subtract the vectors, take the norm, and square it. That produces a new set, of which you want to take the minimum.

$ \sum\limits_{i=1}^n $

This part is then just the sum of above min calculation for every index $i$ from $1$ to $n$.

$\endgroup$
3
$\begingroup$

If you remove all short-hands resp. unfold the notation, you get

$\qquad \begin{align} \operatorname{Perf}(X,C) = \quad &\min \{ ||X_1−C_1||^2, ||X_1−C_2||^2, \dots, ||X_1−C_K||^2 \} \\ + &\min \{ ||X_2−C_1||^2, ||X_2−C_2||^2, \dots, ||X_2−C_K||^2 \} \\ &\ \ \vdots \\ + &\min \{ ||X_n−C_1||^2, ||X_n−C_2||^2, \dots, ||X_n−C_K||^2 \} \\ \end{align}$

where

  • $\min$ denotes the minimum value of the operand set,
  • $X_i$ and $C_l$ are rows or columns of the matrices (depends on the source),
  • $u - v$ for vectors $u,v$ is component-wise subtraction and
  • $||u||$ for a vector $u$ is a norm (which one depends on your source; if nothing else is stated, usually the Euclidian norm is meant).

So, $\operatorname{Perf}(X,C)$ finds for every row (column) of $X$ the row (column) of $C$ that is nearest, and sums up all those minimum (squared) distances. It is therefore a measure of closeness: if $\operatorname{Perf}(X,C)=0$ then every row (column) in $X$ has a perfect match in $C$ (because norms are non-negative).

$\endgroup$

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.