xbe.at

Miscellany / Statistics and analysis

Limitations of Silhouette Score for Arbitrary-Shaped Clusters

6 min read, 13 sections

Contents
  1. Understanding Silhouette Score Limitations
  2. DBCV Introduction and Core Concepts
  3. Computing Intra-cluster Density
  4. Computing Inter-cluster Density
  5. DBCV Implementation
  6. Comparing Silhouette and DBCV on Synthetic Data
  7. Real-world Example - Customer Segmentation
  8. Density Visualization Implementation
  9. Mathematical Foundation of DBCV
  10. Handling High-Dimensional Data
  11. Performance Optimization Techniques
  12. Real-world Example - Image Segmentation
  13. Additional Resources

Understanding Silhouette Score Limitations

The Silhouette score is a widely used metric that measures cluster cohesion and separation, ranging from -1 to 1. While effective for evaluating convex-shaped clusters, it struggles with arbitrary shapes due to its reliance on mean-based distances and assumption of spherical cluster geometry.

import numpy as np
from sklearn.metrics import silhouette_score
from sklearn.cluster import KMeans
from sklearn.datasets import make_moons

# Generate non-spherical data (two moons)
X, y = make_moons(n_samples=200, noise=0.05, random_state=42)

# Apply K-means clustering
kmeans = KMeans(n_clusters=2, random_state=42)
kmeans_labels = kmeans.fit_predict(X)

# Calculate Silhouette score
sil_score = silhouette_score(X, kmeans_labels)
print(f"Silhouette Score for non-spherical clusters: {sil_score:.3f}")

DBCV Introduction and Core Concepts

Density-Based Clustering Validation (DBCV) addresses the limitations of traditional metrics by focusing on density-based cluster characteristics. It evaluates clustering quality by measuring both intra-cluster density and inter-cluster separation through density-connected paths.

import numpy as np
from scipy.spatial.distance import pdist, squareform
from scipy.sparse.csgraph import minimum_spanning_tree

def calculate_density(X, dist_matrix):
    """Calculate core density for each point"""
    k = int(np.log(len(X)))  # Rule of thumb for k
    nn_distances = np.partition(dist_matrix, k, axis=1)[:, :k]
    return 1 / np.mean(nn_distances, axis=1)

Computing Intra-cluster Density

The intra-cluster density measurement in DBCV focuses on the density distribution within each cluster. It uses the concept of density-sparseness to identify the weakest density-connected paths between points in the same cluster.

def intra_cluster_density(X, labels, dist_matrix):
    densities = {}
    for label in np.unique(labels):
        mask = labels == label
        cluster_points = X[mask]
        cluster_dist = dist_matrix[mask][:, mask]
        
        # Calculate density for cluster points
        point_densities = calculate_density(cluster_points, cluster_dist)
        densities[label] = np.mean(point_densities)
    
    return densities

Computing Inter-cluster Density

To evaluate cluster separation, DBCV examines the density characteristics of paths connecting different clusters. Lower density values between clusters indicate better separation, contributing to a higher overall DBCV score.

def inter_cluster_density(X, labels, dist_matrix):
    separations = {}
    unique_labels = np.unique(labels)
    
    for i in range(len(unique_labels)):
        for j in range(i + 1, len(unique_labels)):
            label1, label2 = unique_labels[i], unique_labels[j]
            mask1 = labels == label1
            mask2 = labels == label2
            
            # Calculate minimum density path between clusters
            between_dist = dist_matrix[mask1][:, mask2]
            separations[(label1, label2)] = np.min(between_dist)
            
    return separations

DBCV Implementation

A complete implementation of the DBCV metric requires combining intra-cluster density and inter-cluster separation measurements into a single score. The implementation uses density-reachability concepts from DBSCAN.

def dbcv_score(X, labels):
    """Calculate DBCV score for clustering results"""
    # Calculate distance matrix
    dist_matrix = squareform(pdist(X))
    
    # Get intra-cluster densities
    internal_density = intra_cluster_density(X, labels, dist_matrix)
    
    # Get inter-cluster densities
    external_density = inter_cluster_density(X, labels, dist_matrix)
    
    # Calculate DBCV score
    validity = np.mean([
        min(internal_density[label] / max(external_density.get((label, other), 0) 
            for other in np.unique(labels) if other != label))
        for label in np.unique(labels)
    ])
    
    return validity

Comparing Silhouette and DBCV on Synthetic Data

Using synthetic datasets with different cluster shapes demonstrates the superiority of DBCV over Silhouette score for non-spherical cluster validation.

from sklearn.datasets import make_moons, make_blobs
import matplotlib.pyplot as plt

# Generate datasets
n_samples = 300
datasets = {
    'moons': make_moons(n_samples=n_samples, noise=0.05, random_state=42),
    'blobs': make_blobs(n_samples=n_samples, centers=2, random_state=42)
}

# Compare metrics
for name, (X, y) in datasets.items():
    kmeans = KMeans(n_clusters=2, random_state=42)
    labels = kmeans.fit_predict(X)
    
    sil = silhouette_score(X, labels)
    dbcv = dbcv_score(X, labels)
    
    print(f"\nDataset: {name}")
    print(f"Silhouette Score: {sil:.3f}")
    print(f"DBCV Score: {dbcv:.3f}")

Real-world Example - Customer Segmentation

Customer segmentation often involves clusters with irregular shapes based on behavioral patterns. This example demonstrates how DBCV provides more reliable evaluation than Silhouette score for such real-world scenarios.

import pandas as pd
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import DBSCAN

# Sample customer data
data = {
    'recency': [2, 45, 10, 30, 15, 180, 5, 90],
    'frequency': [100, 5, 80, 10, 50, 2, 95, 3],
    'monetary': [1000, 100, 800, 250, 500, 50, 950, 75]
}
df = pd.DataFrame(data)

# Preprocessing
scaler = StandardScaler()
X_scaled = scaler.fit_transform(df)

# Apply DBSCAN clustering
dbscan = DBSCAN(eps=0.5, min_samples=2)
labels = dbscan.fit_predict(X_scaled)

# Calculate both metrics
sil_score = silhouette_score(X_scaled, labels)
dbcv_val = dbcv_score(X_scaled, labels)

print(f"Silhouette Score: {sil_score:.3f}")
print(f"DBCV Score: {dbcv_val:.3f}")

Density Visualization Implementation

Understanding density distribution is crucial for DBCV calculation. This implementation provides a visual representation of density variations across clusters using kernel density estimation.

from scipy.stats import gaussian_kde

def plot_density_distribution(X, labels):
    """Visualize density distribution for each cluster"""
    plt.figure(figsize=(12, 6))
    
    for label in np.unique(labels):
        if label == -1:  # Skip noise points
            continue
            
        mask = labels == label
        cluster_points = X[mask]
        
        # Calculate kernel density estimation
        kde = gaussian_kde(cluster_points.T)
        density = kde(cluster_points.T)
        
        plt.scatter(cluster_points[:, 0], 
                   cluster_points[:, 1],
                   c=density,
                   cmap='viridis',
                   label=f'Cluster {label}')
    
    plt.colorbar(label='Density')
    plt.legend()
    plt.title('Cluster Density Distribution')
    plt.show()

Mathematical Foundation of DBCV

The mathematical basis of DBCV involves density-connectivity and core-distance concepts. The metric combines these elements to provide a comprehensive cluster validation score.

def density_connectivity(X, dist_matrix, k=5):
    """
    Calculate density connectivity between points
    Mathematical representation:
    ```
    $$DC(p,q) = \min_{path(p,q)} \max_{x \in path(p,q)} \frac{1}{core\_dist(x)}$$
    ```
    """
    n_samples = len(X)
    connectivity = np.zeros((n_samples, n_samples))
    
    # Calculate core distances
    nn_dist = np.partition(dist_matrix, k, axis=1)[:, :k]
    core_dist = np.mean(nn_dist, axis=1)
    
    # Build density connectivity matrix
    for i in range(n_samples):
        for j in range(i+1, n_samples):
            path_density = min(1/core_dist[i], 1/core_dist[j])
            connectivity[i,j] = connectivity[j,i] = path_density
            
    return connectivity

Handling High-Dimensional Data

DBCV's effectiveness extends to high-dimensional spaces where traditional metrics often fail. This implementation includes dimensionality considerations and distance metric adaptations.

def high_dim_dbcv(X, labels, metric='cosine'):
    """DBCV implementation optimized for high-dimensional data"""
    from sklearn.metrics.pairwise import pairwise_distances
    
    # Calculate distance matrix with appropriate metric
    dist_matrix = pairwise_distances(X, metric=metric)
    
    # Adjust density calculation for high dimensions
    def density_factor(dim):
        return np.log(dim + 1)
    
    dim_factor = density_factor(X.shape[1])
    
    # Modified density calculation
    densities = calculate_density(X, dist_matrix) * dim_factor
    
    # Calculate adjusted DBCV score
    validity = np.mean([
        densities[labels == label].mean() / 
        densities[labels != label].mean()
        for label in np.unique(labels) if label != -1
    ])
    
    return validity

Performance Optimization Techniques

For large datasets, computational efficiency becomes crucial. This implementation includes optimized versions of DBCV calculation using vectorization and sparse matrix operations.

def optimized_dbcv(X, labels, batch_size=1000):
    """Memory-efficient DBCV implementation for large datasets"""
    from scipy.sparse import csr_matrix
    
    n_samples = len(X)
    n_batches = (n_samples + batch_size - 1) // batch_size
    
    density_scores = np.zeros(n_samples)
    
    # Process in batches
    for i in range(n_batches):
        start_idx = i * batch_size
        end_idx = min((i + 1) * batch_size, n_samples)
        
        batch_X = X[start_idx:end_idx]
        batch_dist = squareform(pdist(batch_X))
        
        # Calculate batch densities
        batch_density = calculate_density(batch_X, batch_dist)
        density_scores[start_idx:end_idx] = batch_density
    
    return density_scores.mean()

Real-world Example - Image Segmentation

Image segmentation presents a challenging case for cluster validation due to irregular shapes and varying densities. This example demonstrates DBCV's effectiveness in evaluating image segmentation results.

from skimage import io
from skimage.segmentation import slic
from sklearn.preprocessing import StandardScaler

def evaluate_image_segmentation(image_path):
    # Load and preprocess image
    image = io.imread(image_path)
    features = np.reshape(image, (-1, 3))
    
    # Apply SLIC segmentation
    segments = slic(image, n_segments=50, compactness=10)
    segment_labels = segments.reshape(-1)
    
    # Scale features
    scaler = StandardScaler()
    features_scaled = scaler.fit_transform(features)
    
    # Calculate validation scores
    sil_score = silhouette_score(features_scaled, segment_labels)
    dbcv_score_val = dbcv_score(features_scaled, segment_labels)
    
    return sil_score, dbcv_score_val

Additional Resources

More in Statistics and analysis

  1. Mastering Feature Discretization for Non-Linear Modeling14 min

    Feature discretization transforms continuous variables into categorical ones through binning. This process enables linear models to capture non-linear...

  2. Limitations of Binary Classifiers for Face Unlock7 min

    A binary classifier is inadequate for a face unlock application due to several inherent limitations. This approach oversimplifies the complex task of facial...

  3. Mastering ML Pipelines Common Mistakes to Avoid19 min

    Data validation serves as the critical first line of defense in machine learning pipelines, ensuring data quality, consistency, and reliability. Implementing...

  4. Independent and Dependent Variables in Predictive Modeling8 min

    Independent variables are features used as input to predict an outcome. They are the factors that we manipulate or control in an experiment or analysis to...

  5. Maximizing Power in Small-Sample Experiments11 min

    Small-sample experiments present unique challenges in statistical analysis. This slideshow explores the importance of controlling between-individual...

  6. Feature Scaling Techniques for Outlier-Robust Data6 min

    Feature scaling is crucial when dealing with datasets containing outliers. This presentation explores various techniques to scale features effectively...