# 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 $$\bY$$ be a given set of data points. Assume that the ideal/reference clustering of $$\bY$$ is given beforehand.

1. Assume that the dataset $$\bY$$ can be divided into $$K$$ clusters.

2. Let these clusters be named $$\bY_1, \dots, \bY_K$$.

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

In general a clustering $$\CCC$$ of a set $$\bY$$ constructed by a clustering algorithm is a set $$\{\CCC_1, \dots, \CCC_C\}$$ of non-empty disjoint subsets of $$\bY$$ such that their union equals $$\bY$$. Clearly: $$|\CCC_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 $$\CCC_c = Y_k$$ with a bijective mapping between $$1 \leq c \leq C$$ and $$1 \leq k \leq K$$. In practice, a clustering algorithm estimates the number of clusters $$C$$ and assigns a label $$l_s$$, $$1 \leq s \leq S$$ to each vector $$y_s$$ where $$1\leq l_s \leq C$$.
All the labels can be put in a label vector $$L$$ where $$L \in \{1, \dots, C\}^S$$. The permutation matrix $$\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 $$\bY$$ given by $$\BBB = \{\bY_1, \dots, \bY_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 $$\CCC= \{\CCC_1, \dots, \CCC_C\}$$.

For two arbitrary points $$\by_i, \by_j \in \bY$$, there are four possibilities:

1. they belong to same cluster in both $$\BBB$$ and $$\CCC$$ (true positive),

2. they are in same cluster in $$\BBB$$ but different cluster in $$\CCC$$ (false negative)

3. they are in different clusters in $$\BBB$$ but in same cluster in $$\CCC$$

4. they are in different clusters in both $$\BBB$$ and $$\CCC$$ (true negative).

Consider some cluster $$\bY_i \in \BBB$$ and $$\CCC_j \in \CC$$.

1. The elements common to $$\bY_i$$ and $$\CCC_j$$ are given by $$\bY_i \cap \CCC_j$$.

2. We define

$\text{precision}_{i j} \triangleq \frac{|\bY_i \cap \CCC_j|}{|\CCC_j|}.$
3. We define the overall precision for $$\CCC_j$$ as

$\text{precision}(\CCC_j) \triangleq \underset{i}{\max}(\text{precision}_{i j}).$
4. We define $$\text{recall}_{i j} \triangleq \frac{|\bY_i \cap \CCC_j|}{|\bY_i|}$$.

5. We define the overall recall for $$\bY_i$$ as

$\text{recall}(\bY_i) \triangleq \underset{j}{\max}(\text{recall}_{i j}).$
6. We define the $$F$$ score as

$F_{i j} \triangleq \frac{2 \text{precision}_{i j} \text{recall}_{i j} } {\text{precision}_{i j} + \text{recall}_{i j}}.$
7. We define the overall $$F$$-score for $$\bY_i$$ as

$F(\bY_i) \triangleq \underset{j}{\max}(F_{i j}).$
8. We note that cluster $$\CCC_j$$ for which the maximum is achieved is best matching cluster for $$\bY_i$$.

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

$F(\BBB, \CCC) \triangleq \frac{1}{S}\sum_{i=1}^p |\bY_i | F(\bY_i)$

where $$S$$ is the total number of vectors in $$\bY$$.

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.