Compact Clustering with Hierarchical Linkage Methods in Python

Hierarchical Clustering Linkage Methods

Hierarchical clustering is a popular unsupervised learning technique used to group similar data points into clusters. The choice of linkage method in hierarchical clustering significantly impacts the shape and compactness of the resulting clusters. This presentation explores various linkage methods, with a focus on identifying which method produces more compact clusters using Python.

import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.datasets import make_blobs

# Generate sample data
X, _ = make_blobs(n_samples=50, centers=3, random_state=42)

# Perform hierarchical clustering with different linkage methods
methods = ['single', 'complete', 'average', 'ward']
plt.figure(figsize=(20, 5))

for i, method in enumerate(methods):
    Z = linkage(X, method=method)
    plt.subplot(1, 4, i+1)
    dendrogram(Z)
    plt.title(f'{method.capitalize()} Linkage')

plt.tight_layout()
plt.show()

Single Linkage Method

The single linkage method, also known as the nearest neighbor approach, defines the distance between clusters as the minimum distance between any two points in different clusters. This method tends to produce elongated, chain-like clusters.

from scipy.cluster.hierarchy import single

# Generate sample data
X, _ = make_blobs(n_samples=100, centers=3, random_state=42)

# Perform single linkage clustering
Z = single(X)

# Plot the dendrogram
plt.figure(figsize=(10, 5))
dendrogram(Z)
plt.title('Single Linkage Dendrogram')
plt.xlabel('Sample Index')
plt.ylabel('Distance')
plt.show()

# Plot the clusters
from scipy.cluster.hierarchy import fcluster

clusters = fcluster(Z, t=3, criterion='maxclust')
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
plt.title('Single Linkage Clusters')
plt.show()

Complete Linkage Method

The complete linkage method, also called the farthest neighbor approach, defines the distance between clusters as the maximum distance between any two points in different clusters. This method tends to produce more compact, spherical clusters compared to single linkage.

from scipy.cluster.hierarchy import complete

# Perform complete linkage clustering
Z = complete(X)

# Plot the dendrogram
plt.figure(figsize=(10, 5))
dendrogram(Z)
plt.title('Complete Linkage Dendrogram')
plt.xlabel('Sample Index')
plt.ylabel('Distance')
plt.show()

# Plot the clusters
clusters = fcluster(Z, t=3, criterion='maxclust')
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
plt.title('Complete Linkage Clusters')
plt.show()

Average Linkage Method

The average linkage method calculates the distance between clusters as the average distance between all pairs of points in different clusters. This method often produces clusters with characteristics between those of single and complete linkage.

from scipy.cluster.hierarchy import average

# Perform average linkage clustering
Z = average(X)

# Plot the dendrogram
plt.figure(figsize=(10, 5))
dendrogram(Z)
plt.title('Average Linkage Dendrogram')
plt.xlabel('Sample Index')
plt.ylabel('Distance')
plt.show()

# Plot the clusters
clusters = fcluster(Z, t=3, criterion='maxclust')
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
plt.title('Average Linkage Clusters')
plt.show()

Ward Linkage Method

The Ward linkage method aims to minimize the variance within clusters. It tends to create compact, spherical clusters and is often considered the most effective method for producing tight, well-separated clusters.

from scipy.cluster.hierarchy import ward

# Perform Ward linkage clustering
Z = ward(X)

# Plot the dendrogram
plt.figure(figsize=(10, 5))
dendrogram(Z)
plt.title('Ward Linkage Dendrogram')
plt.xlabel('Sample Index')
plt.ylabel('Distance')
plt.show()

# Plot the clusters
clusters = fcluster(Z, t=3, criterion='maxclust')
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
plt.title('Ward Linkage Clusters')
plt.show()

Comparing Cluster Compactness

To compare the compactness of clusters produced by different linkage methods, we can use metrics such as silhouette score or inertia. The silhouette score measures how similar an object is to its own cluster compared to other clusters, with higher values indicating more compact and well-separated clusters.

from sklearn.metrics import silhouette_score

methods = ['single', 'complete', 'average', 'ward']
silhouette_scores = []

for method in methods:
    Z = linkage(X, method=method)
    clusters = fcluster(Z, t=3, criterion='maxclust')
    score = silhouette_score(X, clusters)
    silhouette_scores.append(score)

plt.bar(methods, silhouette_scores)
plt.title('Silhouette Scores for Different Linkage Methods')
plt.xlabel('Linkage Method')
plt.ylabel('Silhouette Score')
plt.show()

Interpreting Silhouette Scores

The silhouette score ranges from -1 to 1, where higher values indicate better-defined clusters. From the previous slide's results, we can observe that the Ward linkage method typically produces the highest silhouette score, indicating more compact and well-separated clusters.

# Print silhouette scores
for method, score in zip(methods, silhouette_scores):
    print(f"{method.capitalize()} linkage silhouette score: {score:.3f}")

# Find the method with the highest score
best_method = methods[np.argmax(silhouette_scores)]
print(f"\nThe method producing the most compact clusters is: {best_method.capitalize()} linkage")

Visualizing Cluster Compactness

To better understand the compactness of clusters, we can visualize them in 2D space. This helps us see how different linkage methods affect the shape and separation of clusters.

from sklearn.decomposition import PCA

# Reduce data to 2D for visualization
pca = PCA(n_components=2)
X_2d = pca.fit_transform(X)

# Plot clusters for each linkage method
fig, axs = plt.subplots(2, 2, figsize=(12, 12))
axs = axs.ravel()

for i, method in enumerate(methods):
    Z = linkage(X, method=method)
    clusters = fcluster(Z, t=3, criterion='maxclust')
    axs[i].scatter(X_2d[:, 0], X_2d[:, 1], c=clusters, cmap='viridis')
    axs[i].set_title(f'{method.capitalize()} Linkage')

plt.tight_layout()
plt.show()

Real-Life Example: Customer Segmentation

Hierarchical clustering can be used for customer segmentation in marketing. Let's consider a dataset of customers with features like age, spending score, and loyalty points.

import pandas as pd

# Create sample customer data
np.random.seed(42)
n_customers = 200
age = np.random.randint(18, 70, n_customers)
spending_score = np.random.randint(1, 100, n_customers)
loyalty_points = np.random.randint(0, 1000, n_customers)

customer_data = pd.DataFrame({
    'Age': age,
    'SpendingScore': spending_score,
    'LoyaltyPoints': loyalty_points
})

# Normalize the data
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
customer_data_scaled = scaler.fit_transform(customer_data)

# Perform Ward linkage clustering
Z = ward(customer_data_scaled)

# Determine the number of clusters
from scipy.cluster.hierarchy import fcluster
n_clusters = 4
clusters = fcluster(Z, t=n_clusters, criterion='maxclust')

# Add cluster labels to the dataframe
customer_data['Cluster'] = clusters

# Visualize the clusters
fig = plt.figure(figsize=(10, 8))
ax = fig.add_subplot(111, projection='3d')
scatter = ax.scatter(customer_data['Age'], customer_data['SpendingScore'], 
                     customer_data['LoyaltyPoints'], c=clusters, cmap='viridis')
ax.set_xlabel('Age')
ax.set_ylabel('Spending Score')
ax.set_zlabel('Loyalty Points')
plt.colorbar(scatter)
plt.title('Customer Segments')
plt.show()

Analyzing Customer Segments

After clustering the customers, we can analyze the characteristics of each segment to develop targeted marketing strategies.

# Calculate mean values for each cluster
cluster_means = customer_data.groupby('Cluster').mean()
print(cluster_means)

# Visualize cluster characteristics
cluster_means.plot(kind='bar', figsize=(12, 6))
plt.title('Mean Values of Customer Segments')
plt.xlabel('Cluster')
plt.ylabel('Mean Value')
plt.legend(loc='upper left', bbox_to_anchor=(1, 1))
plt.tight_layout()
plt.show()

Real-Life Example: Document Clustering

Hierarchical clustering can be applied to group similar documents based on their content. This is useful in information retrieval and text analysis.

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity

# Sample documents
documents = [
    "Machine learning is a subset of artificial intelligence",
    "Deep learning is a type of machine learning",
    "Neural networks are used in deep learning",
    "Artificial intelligence includes expert systems",
    "Expert systems use rule-based reasoning"
]

# Convert documents to TF-IDF vectors
vectorizer = TfidfVectorizer(stop_words='english')
tfidf_matrix = vectorizer.fit_transform(documents)

# Calculate cosine similarity between documents
cosine_sim = cosine_similarity(tfidf_matrix)

# Perform hierarchical clustering
Z = ward(1 - cosine_sim)

# Plot dendrogram
plt.figure(figsize=(10, 5))
dendrogram(Z, labels=documents, leaf_rotation=90, leaf_font_size=8)
plt.title('Document Clustering Dendrogram')
plt.xlabel('Document')
plt.ylabel('Distance')
plt.tight_layout()
plt.show()

# Cluster the documents
n_clusters = 2
clusters = fcluster(Z, t=n_clusters, criterion='maxclust')

# Print clusters
for cluster in range(1, n_clusters + 1):
    print(f"\nCluster {cluster}:")
    for i, doc in enumerate(documents):
        if clusters[i] == cluster:
            print(f"- {doc}")

Advantages and Disadvantages of Ward's Method

Ward's method often produces the most compact clusters, but it's important to consider its pros and cons:

Advantages:

1. Creates compact, spherical clusters
2. Minimizes within-cluster variance
3. Often produces intuitive and visually appealing results

Disadvantages:

1. Sensitive to outliers
2. May not perform well with non-spherical or unequally sized clusters
3. Computationally expensive for large datasets

Advantages and Disadvantages of Ward's Method

# Demonstrate Ward's method sensitivity to outliers
np.random.seed(42)
X_with_outlier = np.vstack([X, np.array([10, 10])])  # Add an outlier

# Perform Ward linkage clustering
Z_with_outlier = ward(X_with_outlier)

# Plot the clusters
plt.figure(figsize=(12, 5))

plt.subplot(121)
clusters = fcluster(Z, t=3, criterion='maxclust')
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
plt.title('Ward Linkage Clusters (Without Outlier)')

plt.subplot(122)
clusters_with_outlier = fcluster(Z_with_outlier, t=3, criterion='maxclust')
plt.scatter(X_with_outlier[:, 0], X_with_outlier[:, 1], c=clusters_with_outlier, cmap='viridis')
plt.title('Ward Linkage Clusters (With Outlier)')

plt.tight_layout()
plt.show()

Choosing the Right Linkage Method

Selecting the appropriate linkage method depends on the nature of your data and the desired cluster characteristics:

1. Single Linkage: Useful for detecting elongated clusters or chaining patterns
2. Complete Linkage: Suitable when compact, evenly sized clusters are expected
3. Average Linkage: A balanced approach that works well in many scenarios
4. Ward Linkage: Ideal for creating compact, spherical clusters with minimal variance

To choose the best method, consider:

• The shape and distribution of your data
• The presence of outliers
• The desired cluster characteristics
• Computational resources available

Experiment with different methods and use evaluation metrics like silhouette score to determine the most suitable approach for your specific use case.

Choosing the Right Linkage Method

# Function to evaluate linkage methods
def evaluate_linkage_methods(X, methods, n_clusters):
    results = []
    for method in methods:
        Z = linkage(X, method=method)
        clusters = fcluster(Z, t=n_clusters, criterion='maxclust')
        score = silhouette_score(X, clusters)
        results.append((method, score))
    return sorted(results, key=lambda x: x[1], reverse=True)

# Evaluate linkage methods
methods = ['single', 'complete', 'average', 'ward']
results = evaluate_linkage_methods(X, methods, n_clusters=3)

# Print results
for method, score in results:
    print(f"{method.capitalize()} linkage silhouette score: {score:.3f}")

print(f"\nBest method: {results[0][0].capitalize()} linkage")

Additional Resources

For further exploration of hierarchical clustering and linkage methods, consider the following resources:

1. Xu, D., & Tian, Y. (2015). A Comprehensive Survey of Clustering Algorithms. Annals of Data Science, 2(2), 165-193. ArXiv: https://arxiv.org/abs/1506.04337
2. Murtagh, F., & Contreras, P. (2012). Algorithms for hierarchical clustering: an overview. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2(1), 86-97. ArXiv: https://arxiv.org/abs/1105.0121
3. Scikit-learn documentation on hierarchical clustering: https://scikit-learn.org/stable/modules/clustering.html#hierarchical-clustering
4. SciPy documentation on hierarchical clustering: https://docs.scipy.org/doc/scipy/reference/cluster.hierarchy.html

These resources provide in-depth explanations of hierarchical clustering algorithms, their implementations, and applications in various domains.