17.8. Evaluation

There are two possible approaches for evaluation of a clustering algorithm.

1. Full reference

2. No reference

In full reference evaluation, a ground truth about an ideal clustering of the data is given. E.g., suppose our goal is to cluster a set of facial images of different persons. The ground truth in this case is the name/id of each person associated with each image.

17.8.1. Full Reference Evaluation

Let $\mathbf{Y}$ be a given set of data points. Assume that the ideal/reference clustering of $\mathbf{Y}$ is given beforehand.

1. Assume that the dataset $\mathbf{Y}$ can be divided into $K$ clusters.

2. Let these clusters be named ${\mathbf{Y}}_1,\dots ,{\mathbf{Y}}_K$.

3. Assume that it is known which point belongs to which cluster.

In general a clustering $\mathcal{C}$ of a set $\mathbf{Y}$ constructed by a clustering algorithm is a set $\{{\mathcal{C}}_1,\dots ,{\mathcal{C}}_C\}$ of non-empty disjoint subsets of $\mathbf{Y}$ such that their union equals $\mathbf{Y}$. Clearly: $|{\mathcal{C}}_c|>0$.

The clustering process may make a number of mistakes.

1. It may identify incorrect number of clusters and $C$ may not be equal to $K$.

2. More-over even if $K=C$, the data points may be placed in wrong clusters.

Ideally, we want $K=C$ and ${\mathcal{C}}_c=Y_k$ with a bijective mapping between $1\le c\le C$ and $1\le k\le K$. In practice, a clustering algorithm estimates the number of clusters $C$ and assigns a label $l_s$, $1\le s\le S$ to each vector $y_s$ where $1\le l_s\le C$.
All the labels can be put in a label vector $L$ where $L\in \{1,\dots ,C{\}}^S$. The permutation matrix $\mathrm{\Gamma }$ can be easily obtained from $L$.

Following [85], we will quickly establish the commonly used measures for clustering performance.

1. We have a reference clustering of vectors in $\mathbf{Y}$ given by $\mathcal{B}=\{{\mathbf{Y}}_1,\dots ,{\mathbf{Y}}_K\}$ which is known to us in advance (either by construction in synthetic experiments or as ground truth with real life data-sets).

2. The clustering obtained by the algorithm is given by $\mathcal{C}=\{{\mathcal{C}}_1,\dots ,{\mathcal{C}}_C\}$.

For two arbitrary points ${\mathbf{y}}_i,{\mathbf{y}}_j\in \mathbf{Y}$, there are four possibilities:

1. they belong to same cluster in both $\mathcal{B}$ and $\mathcal{C}$ (true positive),

2. they are in same cluster in $\mathcal{B}$ but different cluster in $\mathcal{C}$ (false negative)

3. they are in different clusters in $\mathcal{B}$ but in same cluster in $\mathcal{C}$

4. they are in different clusters in both $\mathcal{B}$ and $\mathcal{C}$ (true negative).

Consider some cluster ${\mathbf{Y}}_i\in \mathcal{B}$ and ${\mathcal{C}}_j\in \mathbb{C}$.

1. The elements common to ${\mathbf{Y}}_i$ and ${\mathcal{C}}_j$ are given by ${\mathbf{Y}}_i\cap {\mathcal{C}}_j$.

2. We define

   $${\text{precision}}_{ij}\triangleq \frac{|{\mathbf{Y}}_i\cap {\mathcal{C}}_j|}{|{\mathcal{C}}_j|}.$$

3. We define the overall precision for ${\mathcal{C}}_j$ as

   $$\text{precision}({\mathcal{C}}_j)\triangleq \underset{i}{max}({\text{precision}}_{ij}).$$

4. We define ${\text{recall}}_{ij}\triangleq \frac{|{\mathbf{Y}}_i\cap {\mathcal{C}}_j|}{|{\mathbf{Y}}_i|}$.

5. We define the overall recall for ${\mathbf{Y}}_i$ as

   $$\text{recall}({\mathbf{Y}}_i)\triangleq \underset{j}{max}({\text{recall}}_{ij}).$$

6. We define the $F$ score as

   $$F_{ij}\triangleq \frac{2{\text{precision}}_{ij}{\text{recall}}_{ij}}{{\text{precision}}_{ij}+{\text{recall}}_{ij}}.$$

7. We define the overall $F$-score for ${\mathbf{Y}}_i$ as

   $$F({\mathbf{Y}}_i)\triangleq \underset{j}{max}(F_{ij}).$$

8. We note that cluster ${\mathcal{C}}_j$ for which the maximum is achieved is best matching cluster for ${\mathbf{Y}}_i$.

9. Finally, we define the overall $F$-score for the clustering

   $$F(\mathcal{B},\mathcal{C})\triangleq \frac{1}{S}\sum _{i=1}^p|{\mathbf{Y}}_i|F({\mathbf{Y}}_i)$$

where $S$ is the total number of vectors in $\mathbf{Y}$.

1. We also define a clustering ratio given by the factor

   $$\eta \triangleq \frac{C}{K}.$$

There are different ways to define clustering error. For the special case where the number of clusters is known in advance, and we ensure that the data-set is divided into exactly those many clusters, it is possible to define subspace clustering error as follows:

$$\text{clustering error}=\frac{\text{\# of misclassified points}}{\text{total \# of points}}.$$

The definition is adopted from [32] for comparing the results in this paper with their results. This definition can be used after a proper one-one mapping between original labels and cluster labels assigned by the clustering algorithms has been identified. We can compute this mapping by comparing $F$-scores.