API Reference / algorithms / clustering /

hierarchical.py

Hierarchical Agglomerative Clustering (HAC) algorithm.

Classes

ClusterNode

class algorithms.clustering.hierarchical.ClusterNode

Node in the hierarchical clustering tree (dendrogram).

Methods

is_leaf (self) -> bool

AgglomerativeClusterer

class algorithms.clustering.hierarchical.AgglomerativeClusterer(Clusterer)

Hierarchical Agglomerative Clustering.

Builds a hierarchy of clusters by progressively merging the most similar clusters. This implementation uses a bottom-up (agglomerative) approach, starting with each point as its own cluster and merging them based on a linkage criterion.
Constructor 
__init__(
    self,
    n_clusters: int = 2,
    linkage: str = 'ward',
    distance: str = 'euclidean',
)

Overview

The algorithm constructs a dendrogram (tree of merges):

  1. Initialize each data point as a singleton cluster
  2. Compute the pairwise distance matrix between all clusters
  3. Find the two closest clusters according to the linkage criterion
  4. Merge them into a single cluster and record the merge distance
  5. Repeat steps 2--4 until only one cluster remains
  6. Cut the dendrogram at the level that yields n_clusters clusters

Theory

The linkage criterion determines the distance between sets of observations as a function of the pairwise distances between observations:

  • Single Linkage:
d(A, B) = \min \{ \text{dist}(a, b) : a \in A, b \in B \}
  • Complete Linkage:
d(A, B) = \max \{ \text{dist}(a, b) : a \in A, b \in B \}
  • Average Linkage (UPGMA):
d(A, B) = \frac{1}{|A| |B|} \sum_{a \in A} \sum_{b \in B} \text{dist}(a, b)
  • Ward Linkage minimizes the increase in total within-cluster variance:
\Delta(A, B) = \sqrt{\frac{|A| \cdot |B|}{|A| + |B|}} \| \bar{A} - \bar{B} \|_2

Parameters

n_clusters
int = 2
The number of clusters to find.
linkage
{"ward", "complete", "average", "single"} = "ward"
Which linkage criterion to use.
distance
{"euclidean", "manhattan"} = "euclidean"
Metric used to compute the linkage. If linkage is "ward", only "euclidean" is accepted.

Attributes

labels_
np.ndarray of shape (n_samples,)
Cluster labels for each point.
children_
np.ndarray of shape (n_samples-1, 2)
The children of each non-leaf node. Each row represents a merge.
distances_
np.ndarray of shape (n_samples-1,)
The distances between nodes which were merged.
n_clusters_
int
The number of clusters found by the algorithm.

Notes

Complexity:

  • Training: O(n^3) time complexity and O(n^2) memory.
This makes it unsuitable for very large datasets.

When to use AgglomerativeClusterer:

  • When you need a full hierarchy or dendrogram of clusters
  • Exploratory analysis to understand data structure at multiple scales
  • Small to medium datasets (quadratic memory limits scalability)
  • When cluster shapes are non-globular and linkage choice matters

References

Mullner2011
Mullner, D. (2011). Modern hierarchical, agglomerative clustering algorithms. arXiv preprint arXiv:1109.2378.
Ward1963
Ward, J. H. (1963). Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58(301), pp. 236-244.

See Also

DBSCANClusterer

Density-based clustering with noise detection.

Agglomerative clustering with Ward linkage:

python 
>>> import numpy as np
>>> from tuiml.algorithms.clustering import AgglomerativeClusterer
>>> X = np.array([[1, 2], [1, 4], [1, 0],
...               [4, 2], [4, 4], [4, 0]])
>>> hc = AgglomerativeClusterer(n_clusters=2, linkage='ward')
>>> hc.fit(X)
>>> hc.labels_
array([0, 0, 0, 1, 1, 1])

Methods

get_parameter_schema (cls) -> Dict[str, Dict[str, Any]]

Return parameter schema.

get_capabilities (cls) -> List[str]

Return algorithm capabilities.

get_complexity (cls) -> str

Return time/space complexity.

fit (self, X: np.ndarray) -> 'AgglomerativeClusterer'

Fit the hierarchical clustering model.

Parameters
X
np.ndarray of shape (n_samples, n_features)
Training data to cluster.
Returns
self
AgglomerativeClusterer
Fitted estimator.
predict (self, X: np.ndarray) -> np.ndarray

Predict cluster labels for new data.

Parameters
X
np.ndarray of shape (n_samples, n_features)
Data to cluster.
Returns
labels
np.ndarray of shape (n_samples,)
Cluster labels.
get_dendrogram_data (self) -> Tuple[np.ndarray, np.ndarray]

Get data for plotting a dendrogram.

Returns
children
np.ndarray of shape (n_samples-1, 2)
Merge history.
distances
np.ndarray of shape (n_samples-1,)
Distances at each merge.
__repr__ (self) -> str

String representation.