Hierarchical Clustering

šŸ“– Introduction

Hierarchical Clustering is an unsupervised machine learning algorithm used to group similar observations into clusters by creating a hierarchy of nested clusters. Unlike K-Means, it does not require specifying the number of clusters in advance. The clustering process is represented using a dendrogram, a tree-like diagram that illustrates how clusters are formed or divided.

Information

Hierarchical Clustering is particularly useful when the number of clusters is unknown or when understanding the hierarchical relationships among data points is important.

šŸŽÆ Learning Objectives

  • Understand hierarchical clustering.
  • Learn the difference between Agglomerative and Divisive clustering.
  • Understand linkage methods and distance metrics.
  • Interpret dendrograms for cluster selection.

šŸŒŸ What is Hierarchical Clustering?

Hierarchical Clustering builds a hierarchy of clusters rather than producing a single partition of the dataset. The resulting hierarchy can be visualized using a dendrogram, allowing users to choose the desired number of clusters by cutting the tree at an appropriate level.

CharacteristicHierarchical Clustering
Learning TypeUnsupervised
OutputHierarchy of clusters
Requires K in AdvanceNo
VisualizationDendrogram

šŸŒ³ Types of Hierarchical Clustering

Agglomerative Clustering (Bottom-Up)

Starts with each observation as its own cluster. At each step, the two closest clusters are merged until only one cluster remains or a stopping criterion is reached.

Individual Data Points
Merge Closest Clusters
Merge Again
Repeat
Single Cluster
Divisive Clustering (Top-Down)

Begins with all observations in one cluster and recursively splits clusters into smaller groups until each observation forms its own cluster or another stopping condition is met.

Single Cluster
Split Cluster
Split Again
Continue Splitting
Individual Data Points

āš™ļø Agglomerative Clustering Algorithm

šŸ“Š Linkage Methods

Linkage methods determine how the distance between two clusters is calculated during the merging process.

Linkage MethodDescription
Single LinkageMinimum distance between two clusters.
Complete LinkageMaximum distance between two clusters.
Average LinkageAverage pairwise distance between clusters.
Ward LinkageMinimizes the increase in within-cluster variance.

šŸ“ Distance Metrics

Euclidean Distance

Most commonly used for continuous numerical data.

Manhattan Distance

Suitable for grid-based or high-dimensional data.

Cosine Distance

Measures the angle between vectors rather than their absolute distance. Commonly used for text and document clustering.

šŸŒ² Dendrogram

A dendrogram is a tree-like diagram that illustrates the sequence of cluster merges. The height at which two branches merge represents the distance between the corresponding clusters.

Remember

The number of clusters can be determined by drawing a horizontal cut across the dendrogram. Each disconnected branch below the cut represents one cluster.

šŸ“Š Hierarchical Clustering vs K-Means

FeatureHierarchical ClusteringK-Means
Requires Number of ClustersNoYes
OutputDendrogramCluster Centroids
Cluster ShapeFlexiblePrefers Spherical Clusters
ScalabilityLess ScalableHighly Scalable
Centroid RequiredNoYes

šŸŽ›ļø Important Hyperparameters

HyperparameterDescription
n_clustersDesired number of output clusters.
linkageCluster linkage method.
metricDistance metric used to measure similarity.
distance_thresholdMaximum linkage distance for cluster formation.

šŸ“Š Evaluation Metrics

  • Silhouette Score
  • Davies-Bouldin Index
  • Calinski-Harabasz Index
  • Cophenetic Correlation Coefficient

āš–ļø Advantages and Limitations

  • No need to specify the number of clusters beforehand.
  • Produces an intuitive dendrogram.
  • Can discover clusters of different shapes and sizes.
  • Works well for small and medium-sized datasets.
  • Supports multiple linkage and distance methods.
  • Computationally expensive for large datasets.
  • Once clusters are merged or split, they cannot be undone.
  • Sensitive to noise and outliers.
  • Performance depends on the choice of linkage method and distance metric.

šŸŒ Real-World Applications

ApplicationPurpose
šŸ§¬ Gene Expression AnalysisGroup genes with similar expression patterns.
šŸ›’ Customer SegmentationIdentify groups of customers with similar behavior.
šŸ“„ Document ClusteringOrganize related documents.
šŸŒ Social Network AnalysisDiscover communities within networks.
šŸ–¼ļø Image SegmentationPartition images into meaningful regions.
šŸ„ Medical ResearchIdentify patient groups with similar characteristics.

šŸ’» Practical Example

Agglomerative Hierarchical Clustering Using Scikit-learn

from sklearn.cluster import AgglomerativeClustering
import numpy as np

# Sample data
X = np.array([
    [1, 2], [1, 3], [2, 2],
    [8, 8], [9, 8], [8, 9]
])

# Create model
model = AgglomerativeClustering(
    n_clusters=2,
    linkage="ward"
)

# Train and predict clusters
labels = model.fit_predict(X)

print("Cluster Labels:")
print(labels)

āš ļø Common Mistakes

  • Using Hierarchical Clustering on extremely large datasets.
  • Ignoring feature scaling before computing distances.
  • Selecting an inappropriate linkage method.
  • Misinterpreting the dendrogram when choosing clusters.
  • Ignoring the influence of outliers.

Best Practice

Standardize numerical features before clustering, experiment with multiple linkage methods, visualize the dendrogram to determine an appropriate number of clusters, and use Ward linkage with Euclidean distance as a strong starting point for numerical datasets.

šŸ“š Summary

Summary

Hierarchical Clustering is an unsupervised learning algorithm that constructs a hierarchy of clusters represented by a dendrogram. It is especially useful when the number of clusters is unknown and when understanding relationships among clusters is important. Agglomerative Clustering builds clusters from the bottom up, while Divisive Clustering splits clusters from the top down. With flexible linkage methods and distance metrics, Hierarchical Clustering is widely used in bioinformatics, customer segmentation, document analysis, and many other exploratory data analysis tasks.

šŸ”— Further Reading