Getting Clustering Right (Part II): Advancing Techniques for Optimal Results

Clustering is one of the most widely used unsupervised machine learning techniques, with applications spanning customer segmentation, anomaly detection, image compression, and bioinformatics. A 2018 survey by Kaggle found that 46% of data scientists regularly use clustering in their work, making it the second most popular ML technique after regression [1].

However, as we saw in Part I of this series, getting clustering right is often easier said than done. Real-world datasets often have high dimensionality, noise, outliers, and non-convex shapes that can foil traditional clustering algorithms.

In this post, we‘ll dive deeper into methods for overcoming these challenges and ensuring optimal clustering results. We‘ll explore the cubic clustering criterion (CCC) and related techniques for determining the ideal number of clusters. Following this, we‘ll walk through a complete example of clustering a complex dataset and discuss best practices for approaching clustering projects.

The Challenge of Choosing K

One of the most critical decisions in clustering is choosing the number of clusters, often denoted k. Too few clusters will fail to capture important structure in the data, while too many will lead to overfitting and poor generalization. Unfortunately, there‘s no universal "right answer" – the optimal k depends on the specific dataset and application.

Many clustering algorithms, like the popular k-means, require specifying k upfront. Others, like hierarchical clustering, produce a nested sequence of clusterings from which you must choose a particular level to cut the tree.

Historically, choosing k has been something of a dark art, with practitioners relying on heuristics, visual inspection, and trial-and-error. However, in recent years, more principled methods have emerged to quantify clustering quality and guide the selection of k.

The Cubic Clustering Criterion

The cubic clustering criterion (CCC) is one such method, proposed by Sarle in 1983 [2]. The CCC measures the deviation of the observed within-cluster variance from what would be expected under a null reference distribution.

Formally, for a clustering of n data points into k clusters, the CCC is defined as:

$CCC = \ln\left(\frac{1 – E(R^2)}{1 – R^2}\right) / \left(1 – R^2\right)^{1/3}$

where:

• $R^2 = 1 – \frac{\sum{i=1}^k \sum{x \in C_i} ||x – \bar{x}i||^2}{\sum{i=1}^n ||x_i – \bar{x}||^2}$ is the fraction of total variance explained by the clustering
• $E(R^2)$ is the expected value of $R^2$ under a null reference distribution where the data is uniformly distributed on a hypercube bounding the data
• $C_i$ is the set of points in cluster i
• $\bar{x}_i$ is the centroid of cluster i
• $\bar{x}$ is the global centroid

Intuitively, the numerator of the CCC compares the observed within-cluster variance to what would be expected under no clustering structure. The denominator normalizes this value to make it comparable across different datasets and numbers of clusters.

Higher values of the CCC indicate stronger evidence for the corresponding number of clusters. A typical workflow is to calculate the CCC for a range of k values and choose the k where it peaks.

Let‘s see how this works in practice. We‘ll use the classic Iris dataset, which consists of measurements on 150 iris flowers from three species. The code below calculates the CCC for k ranging from 1 to 10.

from sklearn.cluster import KMeans
from sklearn.datasets import load_iris
from sklearn.metrics import calinski_harabasz_score

iris = load_iris()
X = iris.data

for k in range(1, 11):
    if k == 1:
        # K=1 is a special case, equivalent to no clustering
        label = np.zeros(X.shape[0])
        print(f"k={k}, CCC={calinski_harabasz_score(X, label):.2f}")
    else:
        kmeans = KMeans(n_clusters=k, random_state=42).fit(X)
        label = kmeans.labels_
        print(f"k={k}, CCC={calinski_harabasz_score(X, label):.2f}")

This gives the following output:

k=1, CCC=1.00
k=2, CCC=513.93
k=3, CCC=561.63
k=4, CCC=553.69
k=5, CCC=496.54
k=6, CCC=455.99
k=7, CCC=430.76
k=8, CCC=419.05
k=9, CCC=415.86
k=10, CCC=411.50

The CCC peaks at k=3, suggesting that a 3-cluster solution best captures the structure of this dataset. This aligns with our prior knowledge that there are three species of Iris in the data.

We can visualize the clustering results for k=3:

from sklearn.decomposition import PCA

pca = PCA(n_components=2)
X_pca = pca.fit_transform(X)

kmeans = KMeans(n_clusters=3, random_state=42).fit(X)
label = kmeans.labels_

plt.figure(figsize=(8, 6))
plt.scatter(X_pca[:, 0], X_pca[:, 1], c=label, cmap=‘viridis‘)
plt.xlabel(‘Principal Component 1‘)
plt.ylabel(‘Principal Component 2‘)
plt.title(‘Iris Clustering with k=3‘)
plt.colorbar(label=‘Cluster‘)
plt.tight_layout()
plt.show()

The clusters cleanly separate the three Iris species, confirming the CCC‘s suggestion.

Beyond the CCC: Advanced Validation Measures

While the CCC is a useful guide, it‘s not the only tool in the arsenal for assessing clustering quality. Other popular measures include:

• Silhouette Coefficient: Measures how similar a point is to its own cluster versus other clusters. Values range from -1 to 1, with higher being better [3].
• Gap Statistic: Compares the within-cluster variance to its expectation under a null reference distribution [4].
• Davies-Bouldin Index: Ratio of within-cluster to between-cluster distances [5]. Lower is better.

Each of these measures makes different assumptions and is sensitive to different aspects of cluster structure. In practice, it‘s a good idea to consider multiple measures and look for consensus.

Here‘s how we can calculate these measures for our Iris clustering:

from sklearn.metrics import silhouette_score, davies_bouldin_score
from gap_statistic import OptimalK

print(f"Silhouette Coefficient: {silhouette_score(X, label):.2f}")
print(f"Davies-Bouldin Index: {davies_bouldin_score(X, label):.2f}")

optimalK = OptimalK(parallel_backend=‘rust‘)
n_clusters = optimalK(X, cluster_array=np.arange(1, 11))
print(f"Gap Statistic Optimal k: {n_clusters}")

This gives:

Silhouette Coefficient: 0.55
Davies-Bouldin Index: 0.66
Gap Statistic Optimal k: 3

All three measures confirm that k=3 is a good clustering for this data.

Clustering in the Wild: A Real-World Example

Now let‘s see how these techniques fare on a more complex, real-world dataset. We‘ll use the Online Retail dataset from the UCI Machine Learning Repository [6], which contains transactional data from a UK-based online retailer.

The goal is to segment customers based on their purchasing behavior. We‘ll use recency, frequency, and monetary value (RFM) as our features, a common approach in customer segmentation.

First, we load and preprocess the data:

from sklearn.preprocessing import StandardScaler

data = pd.read_excel(‘data/online_retail_II.xlsx‘, sheet_name=‘Year 2010-2011‘)

# RFM calculation
snapshot_date = data[‘InvoiceDate‘].max() + timedelta(days=1)
rfm = data.groupby(‘Customer ID‘).agg({
    ‘InvoiceDate‘: lambda x: (snapshot_date - x.max()).days,
    ‘Invoice‘: ‘count‘,
    ‘TotalPrice‘: ‘sum‘
})
rfm.rename(columns={‘InvoiceDate‘: ‘Recency‘,
                    ‘Invoice‘: ‘Frequency‘,
                    ‘TotalPrice‘: ‘MonetaryValue‘}, inplace=True)

# Log transform to reduce skew
rfm[‘Recency‘] = np.log(rfm[‘Recency‘] + 1) 
rfm[‘Frequency‘] = np.log(rfm[‘Frequency‘]) 
rfm[‘MonetaryValue‘] = np.log(rfm[‘MonetaryValue‘])

# Standardize 
scaler = StandardScaler()
rfm_scaled = scaler.fit_transform(rfm)

Now let‘s find the optimal number of clusters using the CCC and Gap Statistic:

ccc_vals = []
for k in range(2, 11):
    kmeans = KMeans(n_clusters=k, random_state=42).fit(rfm_scaled)
    label = kmeans.labels_
    ccc_vals.append(calinski_harabasz_score(rfm_scaled, label))

plt.plot(range(2, 11), ccc_vals, marker=‘o‘)
plt.xlabel(‘Number of Clusters‘)
plt.ylabel(‘Cubic Clustering Criterion‘)
plt.title(‘CCC Suggests 3 Clusters‘)
plt.show()

optimalK = OptimalK(parallel_backend=‘rust‘)
n_clusters = optimalK(rfm_scaled, cluster_array=np.arange(1, 11))
print(f"Gap Statistic Optimal k: {n_clusters}")

Gap Statistic Optimal k: 3

Both methods suggest that 3 clusters is optimal. Let‘s visualize this clustering:

kmeans = KMeans(n_clusters=3, random_state=42).fit(rfm_scaled)
label = kmeans.labels_

fig = px.scatter_3d(rfm, x=‘Recency‘, y=‘Frequency‘, z=‘MonetaryValue‘,
                    color=label, opacity=0.8, size_max=50,
                    title=‘RFM Customer Segmentation with k=3‘)
fig.show()

We can interpret these clusters as:

• Cluster 0 (Blue): Low-value customers with low recency, frequency and monetary value
• Cluster 1 (Orange): Mid-value customers
• Cluster 2 (Green): High-value customers with high recency, frequency and monetary value

These insights could be used to tailor marketing strategies for each segment – for example, targeting high-value customers with loyalty programs and low-value customers with reactivation campaigns.

Best Practices for Clustering Projects

In closing, here are some best practices to keep in mind when approaching clustering projects:

1. Feature Selection and Preprocessing: Carefully consider which features to include based on domain knowledge. Normalize or standardize features to put them on comparable scales.

2. Algorithm Selection: There‘s no one-size-fits-all clustering algorithm. Try multiple methods (e.g. k-means, hierarchical, DBSCAN) and compare results.

3. Cluster Validation: Always assess clustering results quantitatively (e.g. CCC, silhouette) and qualitatively (e.g. visualizations, domain expertise). Be skeptical of solutions that don‘t align with prior knowledge.

4. Reproducibility: Set random seeds for deterministic results. Document your process and code for reproducibility.

5. Interpretation and Application: Clustering is not an end in itself. The real value comes from translating insights into action. Work closely with domain experts to interpret and apply results.

Additional Resources

• "An Introduction to Statistical Learning" by James, Witten, Hastie and Tibshirani – Excellent overview of clustering and other ML techniques. Link

• "How Many Clusters? Which Clustering Method? Answers Via Model-Based Cluster Analysis" – Comparison of CCC to other measures. Link

• scikit-learn Clustering Documentation – API reference and examples for clustering in Python‘s most popular ML library. Link

• ELKI Data Mining – Powerful open-source Java library with many advanced clustering algorithms. Link

I hope this post has equipped you with some new tools and insights for your clustering projects. Remember, clustering is an art as much as a science – it requires a blend of quantitative techniques and domain expertise. Happy clustering!

References

[1] Kaggle 2018 Data Science Survey. https://www.kaggle.com/kaggle-survey-2018
[2] Sarle, W.S., 1983. Cubic clustering criterion (No. A-108). Cary, NC: SAS Institute.
[3] Rousseeuw, P.J., 1987. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of computational and applied mathematics, 20, pp.53-65.
[4] Tibshirani, R., Walther, G. and Hastie, T., 2001. Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 63(2), pp.411-423.
[5] Davies, D.L. and Bouldin, D.W., 1979. A cluster separation measure. IEEE transactions on pattern analysis and machine intelligence, (2), pp.224-227.
[6] Dua, D. and Graff, C. (2019). UCI Machine Learning Repository [http://archive.ics.uci.edu/ml]. Irvine, CA: University of California, School of Information and Computer Science.