What does this performance formula mean?

Question

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?

Answer 1

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$.

Answer 2

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).