12.3 Clustering Evaluation

Clustering evaluation is a crucial yet challenging aspect of unsupervised learning. Without ground truth labels, assessing cluster quality becomes subjective, relying on internal metrics like silhouette scores and external measures when labels are available.

Visualization techniques like t-SNE and PCA help interpret clustering results by reducing dimensionality. These tools, along with scatter plots and heatmaps, provide insights into cluster structures and relationships, aiding in the evaluation and refinement of clustering algorithms.

Clustering Evaluation Challenges and Metrics

Challenges in unsupervised model evaluation

• Lack of ground truth labels hampers direct comparison, no predefined classes or categories to benchmark against
• Difficulty determining optimal number of clusters due to subjective nature of cluster quality
• Different applications require varying criteria for good clusters (compactness, separation)
• Sensitivity to initial conditions, random initialization leads to inconsistent results
• High-dimensional data visualization limitations obscure cluster relationships
• Varying cluster shapes and densities complicate uniform evaluation methods
• Presence of noise and outliers distorts cluster boundaries and quality metrics

Internal metrics for clustering quality

• Silhouette score quantifies how well objects fit within their assigned clusters
  • Range from -1 to 1, higher values indicate better-defined clusters
  • Calculated as $(b - a) / max(a, b)$, $a$ = intra-cluster distance, $b$ = nearest-cluster distance
• Davies-Bouldin index evaluates average similarity between clusters and their most similar counterparts
  • Lower values suggest improved clustering
  • Computed as $\frac{1}{n} \sum_{i=1}^n \max_{j \neq i} (\frac{\sigma_i + \sigma_j}{d(c_i, c_j)})$
• Calinski-Harabasz index measures ratio of between-cluster to within-cluster dispersion
  • Higher values indicate better-defined clusters
• Dunn index identifies compact and well-separated clusters
  • Larger values signify improved clustering quality

External metrics with ground truth

• Purity measures extent of single-class dominance within clusters
  • Assign each cluster to most frequent class, compute accuracy
  • Range 0 to 1, 1 indicates perfect clustering
• Rand index calculates percentage of correct clustering decisions
  • Considers point pairs, evaluates correct grouping or separation
  • Calculated as $(TP + TN) / (TP + FP + TN + FN)$, TP/TN/FP/FN = true/false positives/negatives
• Adjusted Rand index corrects Rand index for chance
  • Range -1 to 1, 1 signifies perfect agreement
• F1 score computes harmonic mean of precision and recall
  • Particularly useful for imbalanced datasets

Visualization of clustering results

• t-SNE reduces dimensionality non-linearly, preserves local structure
  • Projects high-dimensional data to 2D or 3D space
  • Perplexity parameter balances local and global structure preservation
• PCA performs linear dimensionality reduction, projects data onto orthogonal axes
  • Identifies main features and overall data structure
• Scatter plots display data points in reduced dimensional space
  • Color-code points based on cluster assignments
• Heatmaps visualize pairwise distances or similarities between data points
  • Reveal block structures within data
• Silhouette plots display individual data point and cluster silhouette scores
  • Identify well-formed clusters and potential outliers
• Dendrograms illustrate hierarchical relationships between clusters
  • Useful for visualizing results of hierarchical clustering methods