Cluster evaluation metrics in SciPy - Time & Space Complexity

Time Complexity: Cluster evaluation metrics

O(n²)

Understanding Time Complexity

When we evaluate clusters, we use metrics to check how good the grouping is.

We want to know how the time to calculate these metrics grows as data size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.spatial.distance import pdist
from scipy.cluster.hierarchy import linkage, fcluster

# data is a 2D array with n samples
D = pdist(data, metric='euclidean')  # pairwise distances
Z = linkage(D, method='ward')       # hierarchical clustering
labels = fcluster(Z, t=3, criterion='maxclust')  # cluster labels

# Calculate silhouette score
from scipy.spatial.distance import cdist

# silhouette calculation
silhouette_vals = []
for i in range(len(data)):
    same_cluster = data[labels == labels[i]]
    other_clusters = data[labels != labels[i]]
    a = cdist(data[i:i+1], same_cluster).mean()  # mean intra-cluster distance
    b = cdist(data[i:i+1], other_clusters).min()  # nearest-cluster distance
    silhouette_vals.append((b - a) / max(a, b))

silhouette_score = sum(silhouette_vals) / len(silhouette_vals)

This code computes clusters and then calculates the silhouette score to evaluate clustering quality.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each data point to compute silhouette values.
• How many times: Once per data point, so n times.
• Inside the loop, distance calculations happen over subsets of data, which can be up to size n.

How Execution Grows With Input

As the number of data points grows, the number of distance calculations grows quickly.

Input Size (n)	Approx. Operations
10	About 100 distance calculations
100	About 10,000 distance calculations
1000	About 1,000,000 distance calculations

Pattern observation: The operations grow roughly with the square of the input size.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the data points, the time to compute the silhouette score roughly quadruples.

Common Mistake

[X] Wrong: "Calculating cluster evaluation metrics like silhouette score is fast and scales linearly with data size."

[OK] Correct: Because silhouette score requires comparing each point to many others, the number of comparisons grows much faster than the number of points.

Interview Connect

Understanding how cluster evaluation metrics scale helps you explain trade-offs when working with big data and choosing the right methods.

Self-Check

What if we used a sampling method to calculate silhouette score on only a subset of points? How would the time complexity change?

Practice

1. Which cluster evaluation metric is best used when you do NOT have true labels for your data?

easy

A. Adjusted Rand Index

B. Silhouette Score

C. Accuracy Score

D. Mean Squared Error

Solution

1. Step 1: Understand the role of true labels

   Adjusted Rand Index requires true labels to compare clusters, so it is not suitable without labels.

2. Step 2: Identify metrics for unknown labels

   Silhouette Score measures how well clusters are separated without needing true labels.

3. Final Answer:

   Silhouette Score -> Option B

4. Quick Check:

   Unknown labels = Silhouette Score [OK]

Hint: Use silhouette score when labels are unknown [OK]

Common Mistakes:

• Confusing Adjusted Rand Index as label-free
• Choosing accuracy score which needs labels
• Using mean squared error for clustering

2. Which of the following is the correct way to import the silhouette_score function for cluster evaluation?

easy

A. from scipy.cluster import silhouette_score

B. from scipy.spatial.distance import silhouette_score

C. from scipy.cluster.hierarchy import silhouette_score

D. from sklearn.metrics import silhouette_score

Solution

1. Step 1: Check common library modules

   Silhouette score is available in sklearn.metrics module, not in scipy.cluster or spatial.distance.

2. Step 2: Verify import syntax

   The correct import is from sklearn.metrics import silhouette_score.

3. Final Answer:

   from sklearn.metrics import silhouette_score -> Option D

4. Quick Check:

   Correct import = sklearn.metrics [OK]

Hint: Silhouette score is in sklearn.metrics module [OK]

Common Mistakes:

• Importing from scipy.cluster directly
• Using scipy.spatial.distance for silhouette_score
• Confusing hierarchy module with vq

3. What is the output of the following code snippet?

from scipy.cluster.vq import kmeans, vq, whiten
import numpy as np

data = np.array([[1, 2], [1, 4], [1, 0], [10, 2], [10, 4], [10, 0]])
whitened = whiten(data)
centroids, _ = kmeans(whitened, 2)
cluster_labels, _ = vq(whitened, centroids)
from sklearn.metrics import silhouette_score
score = silhouette_score(whitened, cluster_labels)
print(round(score, 2))

medium

A. 0.75

B. 1.00

C. 0.35

D. 0.55

Solution

1. Step 1: Understand the code flow

   The code whitens data, runs kmeans for 2 clusters, assigns labels, then calculates silhouette score.

2. Step 2: Interpret silhouette score meaning

   Data clearly forms two groups; silhouette score is around 0.75 indicating good cluster separation.

3. Final Answer:

   0.75 -> Option A

4. Quick Check:

   Well-separated clusters ≈ 0.75 silhouette [OK]

Hint: Silhouette near 0.75 means good cluster separation [OK]

Common Mistakes:

• Expecting silhouette score of 1.0 always
• Confusing whitened data with original scale
• Misreading cluster labels

4. Identify the error in this code snippet for calculating Davies-Bouldin score:

from scipy.spatial.distance import davies_bouldin_score

labels = [0, 0, 1, 1]
data = [[1, 2], [1, 4], [10, 2], [10, 4]]
score = davies_bouldin_score(data, labels)
print(score)

medium

A. Data must be a numpy array, not list

B. Labels and data length mismatch

C. Importing davies_bouldin_score from wrong module

D. Davies-Bouldin score requires true labels

Solution

1. Step 1: Check import source

   Davies-Bouldin score is in sklearn.metrics, not scipy.spatial.distance.

2. Step 2: Validate data and labels

   Data and labels lengths match and data as list works with sklearn, so no error there.

3. Final Answer:

   Importing davies_bouldin_score from wrong module -> Option C

4. Quick Check:

   Correct import is sklearn.metrics [OK]

Hint: Davies-Bouldin score is in sklearn.metrics, not scipy [OK]

Common Mistakes:

• Importing from scipy.spatial.distance
• Assuming data must be numpy array
• Thinking Davies-Bouldin needs true labels

5. You have true labels and predicted cluster labels for a dataset. Which metric from scipy or sklearn should you use to evaluate clustering quality by comparing these labels?

hard

A. Adjusted Rand Index

B. Davies-Bouldin Score

C. Silhouette Score

D. Calinski-Harabasz Index

Solution

1. Step 1: Identify metrics needing true labels

   Adjusted Rand Index compares predicted clusters with true labels to measure similarity.

2. Step 2: Exclude label-free metrics

   Silhouette, Davies-Bouldin, and Calinski-Harabasz do not use true labels for evaluation.

3. Final Answer:

   Adjusted Rand Index -> Option A

4. Quick Check:

   True vs predicted labels = Adjusted Rand Index [OK]

Hint: Use Adjusted Rand Index to compare true and predicted labels [OK]

Common Mistakes:

• Using silhouette score with true labels
• Confusing Davies-Bouldin as label-based
• Choosing Calinski-Harabasz for label comparison