Chapter 17 of Zaki & Meira (2020): Clustering Validation

Clustering Validation Metrics¶

Introduction to Clustering Validation¶

Clustering validation helps assess the quality of clustering results. There are three main types of validation measures:

1. External measures: Use external information like ground truth labels

2. Internal measures: Use only the data and clustering results

3. Relative measures: Compare different clusterings

External Measures¶

External measures assume that the correct or ground-truth clustering is known a priori, which is used to evaluate a given clustering.

Let $\mathbf{D} = \{\mathbf{x}_i\}_{i=1}^n$ be a dataset consisting of $n$ points in a $d$-dimensional space, partitioned into $k$ clusters. Let $y_i \in \left\{ 1, 2,\ldots , k \right\}$ denote the ground-truth cluster membership or label information for each point.

The ground-truth clustering is given as:

where the cluster $T_{j}$ consists of all the points with label $j$, i.e.,

We refer to $\mathbf{T}$ as the ground-truth partitioning, and to each $T_i$ as a partition (class).

Let $\mathbf{C} = \{C_1, \ldots, C_r\}$ denote a clustering of the same dataset into $r$ clusters, obtained via some clustering algorithm, and let $\hat{y}_i \in \left\{ 1, 2, \ldots, r \right\}$ denote the cluster label for $\mathbf{x}_i$.

External evaluation measures try to capture the extent to which points from the same partition appear in the same cluster, and the extent to which points from different partitions are grouped in different clusters.

All of the external measures rely on the $r \times k$ contingency table $\mathbf{N}$ that is induced by a clustering $\mathbf{C}$ and the ground-truth partitioning $\mathbf{T}$, defined as follows:

The count $n_{ij}$ denotes the number of points that are common to cluster $C_i$ and ground-truth partition $T_{j}$.

Let $n_{i} = |C_i|$ denote the number of points in cluster $C_i$, and let $m_{j} = |T_{j}|$ denote the number of points in partition $T_{j}$. The contingency table can be computed from $\mathbf{T}$ and $\mathbf{C}$ in $O(n)$ time by examining the partition and cluster labels, $y_i$ and $\hat{y}_i$, for each point $\mathbf{x}_i \in \mathbf{D}$ and incrementing the corresponding count $n_{y_i\hat{y}_i}$.

Contingency Table can be computed as follows:

Efficient Contingency Table Computation with np.add.at¶

When implementing clustering validation metrics, constructing a contingency table is a key step. One efficient way to do this in NumPy is using np.add.at. This method ensures correct accumulation of counts when duplicate indices are present.

Why np.add.at?¶

Unlike simple indexed incrementation, such as:

contingency_table[cluster_map, class_map] += 1

NumPy’s fancy indexing creates a temporary copy, meaning updates to repeated indices may not accumulate correctly. Instead, np.add.at ensures in-place modifications:

np.add.at(contingency_table, (cluster_map, class_map), 1)

Example: Difference Between Direct Indexing and np.add.at¶

Here’s an example illustrating how np.add.at correctly handles duplicate indices while direct indexing may fail:

1. Purity¶

Purity measures how “pure” each cluster is by the fraction of points from the majority class:

Where:

• $n$ = total number of points

• $r$ = number of clusters

• $k$ = number of true classes

• $n_{ij}$ = number of points in cluster $i$ from class $j$

Let’s consider an example where we achieve high purity, ensuring our clustering is well-aligned with the ground-truth partitioning.

Example Data¶

Suppose we have the following clustering and ground-truth labels:

true_labels    = np.array([0, 0, 1, 1, 1, 2])
cluster_labels = np.array([0, 0, 1, 1, 2, 2])

Here, each cluster aligns better with a single true class.

Compute Contingency Table¶

Using the compute_contingency_table function, we obtain:

Middle Computations¶

Step 1: Find the max of each row:

• max(C₀) = 2

• max(C₁) = 2

• max(C₂) = 1

Step 2: Sum the max values: $\sum \max(n_{ij}) = 2 + 2 + 1 = 5$

Step 3: Compute purity: $\text{Purity} = \frac{\sum \max(n_{ij})}{\sum n_{ij}} = \frac{5}{6} \approx 0.833$

purity is invariant to cluster labels, meaning that relabeling clusters doesn’t change the score as long as the assignment itself remains consistent.

Let’s take the previous clustering but shift the cluster labels (e.g., renaming clusters C₀ $\rightarrow$ C₂, C₁ $\rightarrow$ C₀, C₂ $\rightarrow$ C₁):

Why Does Purity Stay the Same?

• The mapping between clusters and ground-truth partitions hasn’t changed, only their labels.

• Since purity only depends on how well clusters match ground-truth partitions, renaming clusters doesn’t affect purity calculations.

Precision and Recall¶

For each cluster $C_i$:

• Precision: Fraction of points in cluster from majority class

• Recall: Fraction of points from class found in cluster

Precision¶

Given cluster $C_i$, let $j_i$ denote the partition that contains the maximum number of points from $C_i$, that is, $j_i = \max_{j=1}^k \{ n_{ij} \}$. The precision of a cluster $C_i$ is the same as its purity:

Recall¶

The recall of cluster $C_i$ is defined as:

where $m_{j_i} = |\mathbf{T}_{j_i}|$.

F-Measure¶

The F-measure is the harmonic mean of the precision and recall values for each $C_i$:

The F-measure for the clustering $\mathbf{C}$ is the mean of clusterwise F-measure values:

2. Maximum Matching¶

Finds the best matching between clusters and true classes to maximize overlap:

Where $M$ is a matching between clusters and classes.

Maximum Weight Matching based on Zaki & Meira (2020)

Let $G$ be a bipartite graph over the vertex set $V = \mathbf{C} \cup \mathbf{T}$, and let the edge set be $E = \{ (C_i, T_{j}) \}$ with edge weights $w(C_i,T_{j}) = n_{ij}$. A matching $M$ in $G$ is a subset of $E$, such that the edges in $M$ are pairwise nonadjacent, meaning they do not have a common vertex.

The maximum weight matching in $G$ is given as:

where $w(M)$ is the sum of all edge weights in matching $M$, given as $w(M) = \sum_{e \in M} w(e)$.

Maximum Matching Example (Bipartite Graph Interpretation)¶

Scenario: Imagine we have clustered 10 fruits into 3 clusters, and we know their true categories (ground truth):

True Categories (T₁=apples, T₂=oranges, T₃=bananas):
T₁: apple1, apple2, apple3, apple4
T₂: orange1, orange2, orange3
T₃: banana1, banana2, banana3

Cluster Assignments (C₁, C₂, C₃):
C₁: [apple1, apple2, banana1]
C₂: [orange1, orange2, apple3] 
C₃: [banana2, banana3, orange3, apple4]

Contingency Table¶

Step 1: Build the Bipartite Graph

We create edges between clusters and categories with weights equal to their overlap:

Clusters       Categories
   C₁ ------------- T₁ (weight=2: apple1,apple2)
      \------------ T₃ (weight=1: banana1)
   C₂ ------------- T₁ (weight=1: apple3)
      \------------ T₂ (weight=2: orange1,orange2)
   C₃ ------------- T₁ (weight=1: apple4)
      \------------ T₂ (weight=1: orange3)
      \------------ T₃ (weight=2: banana2,banana3)

Step 2: Find Maximum Weight Matching

We want to match each cluster to at most one category (and vice versa) to maximize total weight:

Possible matching options:

1. Match C₁-T₁ (2), C₂-T₂ (2), C₃-T₃ (2) $\rightarrow$ Total weight = 6

2. Match C₁-T₃ (1), C₂-T₂ (2), C₃-T₁ (1) $\rightarrow$ Total weight = 4

The first option gives us the maximum weight matching.

Step 3: Calculate Maximum Matching Score

Example 17.1: Good vs Bad Clustering on Iris Data¶

Let’s examine two different clusterings of the Iris dataset using principal components:

Good Clustering Results:¶

Contingency Table¶

Purity: 0.887
Match: 0.887
F: 0.885

Bad Clustering Results:¶

Contingency Table¶

Purity: 0.667
Match: 0.560
F: 0.658

4. Pairwise Measures¶

First, let’s define some key quantities used in external measures:

• TP (True Positives): Pairs in same cluster and same true partition

• FP (False Positives): Pairs in same cluster but different partitions

• TN (True Negatives): Pairs in different clusters and different partitions

• FN (False Negatives): Pairs in different clusters but same partition

Given clustering $\mathbf{C}$ and ground-truth partitioning $\mathbf{T}$, let $\mathbf{x}_i, \mathbf{x}_{j} \in \mathbf{D}$ be any two points, with $i \ne j$. Let $y_i$ denote the true partition label and let $\hat{y}_i$ denote the cluster label for point $\mathbf{x}_i$.

If both $\mathbf{x}_i$ and $\mathbf{x}_{j}$ belong to the same cluster, that is, $\hat{y}_i = \hat{y}_{j}$, we call it a positive event, and if they do not belong to the same cluster, that is, $\hat{y}_i \ne \hat{y}_{j}$, we call that a negative event. Depending on whether there is agreement between the cluster labels and partition labels, there are four possibilities to consider:

True Positives (TP)
$\mathbf{x}_i$ and $\mathbf{x}_{j}$ belong to the same partition in $\mathbf{T}$, and they are also in the same cluster in $\mathbf{C}$. The number of true positive pairs is given as:

False Negatives (FN)
$\mathbf{x}_i$ and $\mathbf{x}_{j}$ belong to the same partition in $\mathbf{T}$, but they do not belong to the same cluster in $\mathbf{C}$. The number of false negative pairs is given as:

False Positives (FP)
$\mathbf{x}_i$ and $\mathbf{x}_{j}$ do not belong to the same partition in $\mathbf{T}$, but they do belong to the same cluster in $\mathbf{C}$. The number of false positive pairs is given as:

True Negatives (TN)
$\mathbf{x}_i$ and $\mathbf{x}_{j}$ neither belong to the same partition in $\mathbf{T}$, nor do they belong to the same cluster in $\mathbf{C}$. The number of such true negative pairs is given as:

Jaccard Coefficient¶

Rand Index¶

Internal Validation Measures¶

Silhouette Coefficient¶

Measures how similar a point is to its own cluster compared to other clusters:

For each point $x_i$:

Where:

• $a_i$ = average distance to other points in same cluster

• $b_i$ = min average distance to points in another cluster

Overall score is average of all $s_i$.

Python Example on Iris Dataset¶

Interpretation of Results¶

• Purity: Higher is better (max 1.0)

• Rand Index: Higher is better (max 1.0)

• Silhouette: Ranges from -1 to 1, higher is better

• Jaccard: Higher is better (max 1.0)

Wiki of Silhouette

Choosing the Right Metric¶

1. Use external measures when ground truth is available

2. Use internal measures when no labels exist

3. Consider multiple metrics together for robust evaluation

Remember that no single metric tells the whole story - different metrics may be more appropriate for different clustering goals.

Further Reading¶

Here are several real-world examples of bipartite matching problems that help explain the concept of maximum matching in clustering validation, along with relevant links for further reading:

1. Stable Marriage Problem¶

Scenario: Matching medical students to hospital residency programs based on mutual preferences
Visualization:

Students   Hospitals
  A ──────── X (1st choice)
  B ──┬───── Y 
     └───── Z (tie)
  C ──────── Y (only option)

Key Insight: The Gale-Shapley algorithm finds stable pairings where no unmatched pair prefers each other over their current matches
Resource: Wikipedia - Stable Marriage Problem

2. Roommate Assignment¶

Scenario: Matching college students as roommates based on compatibility scores
Example Matrix:

       Clean | Social | Studious
Alice    5   |   3    |    2
Bob      2   |   4    |    1
Carol    4   |   1    |    5

Optimal Matching: Alice-Clean (5), Bob-Social (4), Carol-Studious (5) $\rightarrow$ Total=14
Resource: Roommate Assignment Algorithms

3. Thesis Advisor Matching¶

Scenario: Assigning graduate students to faculty advisors based on research interests
Connection: Similar to ensuring each cluster (advisor group) best represents one true category (research area)
Process Flow:

1. Students rank advisors

2. Advisors rank students

3. Solve using maximum weight matching
   Visualization:

Students     Research Areas
  Sara ────┐
           ├── ML (Prof. Smith)
  John ────┘
  Emma ────── NLP (Prof. Lee)

Resource:

• Match Day 101: How does the medical residency match work?

• Dr. Amin Saberi

4. Image Feature Matching¶

Scenario: Matching keypoints between two images of the same object
Example:

Image A Features   Image B Features
   Corner X ─────────── Edge P (distance=1.2)
   Blob Y ──┬────────── Corner Q (distance=0.8)
           └────────── Blob R (distance=1.5)

Optimal Matching: X-P (1.2), Y-Q (0.8) $\rightarrow$ Total=2.0
Algorithm: Hungarian algorithm on distance matrix
Resource: OpenCV Feature Matching

5. Job Applicant Matching¶

Scenario: Assigning applicants to job openings based on skill fit
Matching Table:

Applicants  Jobs       Fit Score
  Amy ───── Data Sci ─── 0.9
  Sam ──┬── Engineer ── 0.7
        └── Analyst ── 0.8
  Zoe ───── Engineer ── 0.6

Maximum Matching: Amy-Data Sci (0.9), Sam-Analyst (0.8), Zoe-Engineer (0.6) $\rightarrow$ Total=2.3
Resource: LinkedIn Matching Algorithm

Comparative Summary Table¶

These examples demonstrate how maximum matching principles apply across domains while maintaining the core idea of optimal constrained assignments - exactly what we do when evaluating clustering quality against ground truth.

Maximum Cardinality Matching in Bipartite Graphs¶

Overview¶

This implementation finds the maximum cardinality matching in a bipartite graph using NetworkX. A bipartite graph is a graph whose nodes can be split into two disjoint sets such that no two nodes within the same set are adjacent.

Key Components:¶

• bipartite.sets(G): Extracts the two partitions (left and right nodes).

• max_weight_matching(G): Finds the optimal matching where each node is paired with at most one other node.

Code Implementation¶

Contingency Table

Purity: 0.667
Match: 0.560