Evaluating Clustering Performance

After partitioning your data into clusters using algorithms like K-Means or DBSCAN, a natural and important question arises: How good is this clustering? Unlike supervised learning, where we have ground truth labels to compare against, unsupervised clustering often lacks such direct benchmarks. Therefore, evaluating clustering performance requires a different set of tools and perspectives. The goal is to assess the quality of the resulting clusters based on certain intrinsic properties of the data or, if available, external benchmarks.

There are generally two families of measures for evaluating clustering quality: internal and external.

Internal Evaluation Measures

Internal evaluation measures assess the quality of a clustering structure without reference to any external information. They use only the information present in the dataset itself, focusing on characteristics like cluster compactness (how close together points in the same cluster are) and cluster separation (how distinct different clusters are from each other).

A good clustering algorithm should produce clusters where:

• Points within the same cluster are similar to each other (high intra-cluster similarity).
• Points in different clusters are dissimilar from each other (low inter-cluster similarity).

Let's look at some popular internal evaluation metrics.

Silhouette Coefficient (or Silhouette Score)

The Silhouette Coefficient is a popular metric that quantifies how well-defined your clusters are. For each data point $i$, its silhouette value $s(i)$ is calculated as:

$$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}$$

Where:

• $a(i)$: The average distance from point $i$ to all other points within the same cluster. This measures cohesion.
• $b(i)$: The average distance from point $i$ to all points in the nearest neighboring cluster (the cluster to which $i$ does not belong that has the smallest average distance to $i$). This measures separation.

The Silhouette Coefficient ranges from -1 to +1:

• +1: Indicates that the point is far away from the neighboring clusters and very close to points in its own cluster. This is the ideal.
• 0: Indicates that the point is on or very close to the decision boundary between two neighboring clusters.
• -1: Indicates that the point is probably assigned to the wrong cluster.

The average Silhouette Coefficient over all data points provides an overall measure of clustering quality. A higher average Silhouette Score generally indicates better clustering.

In Julia, you can compute silhouette scores using the Clustering.jl package.

using Clustering, Distances, Statistics

# Assume X is your data matrix (features by observations)
# e.g., X = rand(2, 100) for 100 2D points
# Assume 'assignments' is an array of cluster labels for each point
# e.g., assignments = kmeans(X, 3).assignments

# Sample data and assignments for illustration
X = hcat(randn(2, 30), randn(2,40) .+ 5, randn(2,30) .- 3)
assignments = vcat(fill(1, 30), fill(2, 40), fill(3, 30))

if size(X, 2) != length(assignments)
    error("Data points and assignments count mismatch.")
end

# Calculate pairwise distances (e.g., Euclidean)
# Ensure X is features as rows, observations as columns for pairwise
dist_matrix = pairwise(Euclidean(), X, dims=2)

# Calculate silhouette scores for each point
sils = silhouettes(assignments, dist_matrix)

# Average silhouette score for the entire clustering
avg_silhouette_score = mean(sils)
println("Average Silhouette Score: ", avg_silhouette_score)

# You can also inspect individual silhouette scores
# For example, to find points with low silhouette scores:
# low_silhouette_points_indices = findall(s -> s < 0.1, sils)

The following diagram illustrates how Silhouette Coefficients relate to cluster structure:

The diagram shows three points. Point A, with a high Silhouette value, is well-separated from its neighboring cluster and cohesive with its own. Point B is close to the boundary. Point C might be in the wrong cluster as it's closer to the neighboring cluster than its assigned one.

One common use of the Silhouette Score is to help determine an appropriate number of clusters, $k$. You can run your clustering algorithm (e.g., K-Means) for different values of $k$ and choose the $k$ that yields the highest average Silhouette Score.

Davies-Bouldin Index (DBI)

The Davies-Bouldin Index (DBI) is another internal evaluation metric. It is defined as the average similarity measure of each cluster with its most similar cluster. Similarity is the ratio of within-cluster distances to between-cluster distances. Lower values of the DBI indicate better clustering, as clusters are more compact and well-separated.

For each cluster $C_i$, we calculate $R_i$:

$$R_i = \max_{j \neq i} \left( \frac{\sigma_i + \sigma_j}{d(c_i, c_j)} \right)$$

Where:

• $\sigma_i$ is the average distance of all points in cluster $C_i$ to their cluster centroid $c_i$ (a measure of scatter within cluster $i$).
• $d(c_i, c_j)$ is the distance between the centroids of clusters $C_i$ and $C_j$.

The Davies-Bouldin Index is then the average of these $R_i$ values for all clusters:

$$\text{DBI} = \frac{1}{k} \sum_{i=1}^{k} R_i$$

A lower DBI score corresponds to a model with better separation between the clusters. Unlike the Silhouette Score, there isn't a direct function for DBI in Clustering.jl, so its computation might require a custom implementation or leveraging functionalities within broader frameworks like MLJ.jl if available for specific model types.

Calinski-Harabasz Index (Variance Ratio Criterion)

The Calinski-Harabasz Index (also known as the Variance Ratio Criterion) evaluates cluster validity based on the ratio of the sum of between-cluster dispersion to the sum of within-cluster dispersion for all clusters. A higher Calinski-Harabasz Index score generally relates to a model with better-defined clusters. It is calculated as:

$$\text{CH} = \frac{\text{SS}_B / (k-1)}{\text{SS}_W / (N-k)}$$

Where:

• $\text{SS}_B$ is the overall between-cluster variance.
• $\text{SS}_W$ is the overall within-cluster variance.
• $k$ is the number of clusters.
• $N$ is the total number of observations.

Larger values of CH indicate better clustering, meaning clusters are dense and well-separated. Similar to DBI, a direct function for Calinski-Harabasz might not be in basic clustering packages but could be implemented or found in more comprehensive ML frameworks.

External Evaluation Measures

External evaluation measures are used when ground truth class labels are available for the data. This scenario is common when benchmarking clustering algorithms on datasets with known classifications, or when using synthetic data. These metrics compare the clustering result to the true underlying structure.

Adjusted Rand Index (ARI)

The Rand Index (RI) measures the similarity between two data clusterings by considering all pairs of samples and counting pairs that are assigned in the same or different clusters in the predicted and true clusterings. The Adjusted Rand Index (ARI) is a version of the Rand Index that is adjusted for chance. The ARI ranges from -1 to 1:

• 1: Perfect agreement between the true labels and the clustering result.
• 0: The clustering is no better than random.
• Negative values: The clustering is worse than random.

In Julia, Clustering.jl provides randindex to compute RI and ARI.

using Clustering, Statistics

# Assume 'true_labels' are the ground truth class labels
# Assume 'predicted_assignments' are the cluster labels from your algorithm
# Example:
true_labels = vcat(fill(1, 50), fill(2, 50), fill(3,50))
# Let's create some predicted assignments, e.g., from K-Means
# For illustration, some slightly imperfect assignments:
predicted_assignments = vcat(fill(1, 45), fill(2,5), fill(2, 48), fill(3,2), fill(3,40), fill(1,10))
# Ensure lengths match
if length(true_labels) != length(predicted_assignments)
   idx = min(length(true_labels), length(predicted_assignments))
   true_labels = true_labels[1:idx]
   predicted_assignments = predicted_assignments[1:idx]
end


# randindex returns (RI, ARI)
ri, ari = randindex(predicted_assignments, true_labels)
println("Adjusted Rand Index (ARI): ", ari)

Normalized Mutual Information (NMI)

Normalized Mutual Information (NMI) is an information-theoretic measure that quantifies the amount of information shared between the true labels and the predicted cluster assignments. It's normalized to range between 0 and 1:

• 1: Perfect correlation between the true labels and the clustering.
• 0: No mutual information; the clustering is independent of the true labels.

Clustering.jl also provides mutualinfo for this purpose.

using Clustering, Statistics

# Using the same true_labels and predicted_assignments from ARI example
# true_labels = ...
# predicted_assignments = ...

nmi_score = mutualinfo(predicted_assignments, true_labels, norm=true) # norm=true for NMI
println("Normalized Mutual Information (NMI): ", nmi_score)

Other external metrics like Homogeneity, Completeness, and V-measure also offer insights into how well the clustering aligns with true class labels, focusing on whether each cluster contains only members of a single class (homogeneity) and whether all members of a given class are assigned to the same cluster (completeness).

Practical Considerations for Evaluation

Choosing the "right" evaluation metric often depends on the specific goals of your clustering task and the characteristics of your data.

Determining the Number of Clusters ($k$)

For algorithms like K-Means, selecting the number of clusters, $k$, is a significant step. Internal evaluation metrics can guide this choice:

• Elbow Method with WCSS: Plot the Within-Cluster Sum of Squares (WCSS) against different values of $k$. WCSS is the sum of squared distances of samples to their closest cluster center. Look for an "elbow" point where adding more clusters doesn't significantly reduce WCSS.
• Average Silhouette Method: Calculate the average Silhouette Score for different values of $k$. The $k$ that maximizes the average Silhouette Score is often chosen. This is generally preferred over the Elbow method as it considers both cohesion and separation.

Here's a visual example of using Silhouette Scores to help choose $k$:

Example plot showing average Silhouette Scores for different values of $k$. In this case, $k=3$ yields the highest average Silhouette Score, suggesting it might be an optimal number of clusters.

Visual Inspection

When possible (e.g., for 2D or 3D data, or after dimensionality reduction), visually inspecting the clusters can provide valuable qualitative insights that complement quantitative metrics. Are the clusters well-separated? Do they make sense in the context of the problem domain?

Domain Knowledge

Always consider domain knowledge. Sometimes, the "best" clustering from a mathematical standpoint might not be the most meaningful or actionable from a domain perspective. For instance, you might have an external reason to expect a certain number of segments in your customer data.

Evaluating clustering is often an iterative process. You might try different algorithms, vary parameters (like $k$), and use multiple evaluation metrics to build confidence in your results. There's rarely a single perfect answer, so a combination of quantitative measures and qualitative judgment is usually the most effective approach.