Scaling Agglomerative Clustering for Big Data | by Daniel Frees | Aug, 2023

Agglomerative clustering is likely one of the finest clustering instruments in knowledge science, however conventional implementations fail to scale to giant datasets.

On this article, I’ll take you thru some background on agglomerative clustering, an introduction to reciprocal agglomerative clustering (RAC) based mostly on 2021 research from Google, a runtime comparability between RAC++ and scikit-learn’s AgglomerativeClustering, and at last a short clarification of the speculation behind RAC.

Background on Agglomerative Clustering

In knowledge science, it’s incessantly helpful to cluster unlabeled knowledge. With purposes starting from grouping of search engine outcomes, to genotype classification, to banking anomaly detection, clustering is an important piece of an information scientist’s toolkit.

Agglomerative clustering is likely one of the hottest clustering approaches in data-science and for good cause, it:

✅ Is simple to make use of with little to no parameter tuning
✅ Creates significant taxonomies
✅ Works nicely with high-dimensional knowledge
✅ Doesn’t have to know the variety of clusters beforehand
✅ Creates the identical clusters each time

Compared, partitioning strategies like Okay-Means require the info scientist to guess on the variety of clusters, the very fashionable density-based technique DBSCAN requires some parameters round density calculation radius (epsilon) and min neighborhood dimension, and Gaussian combination fashions make robust assumptions in regards to the underlying cluster knowledge distribution.

With agglomerative clustering, all that you must specify is a distance metric.

At a high-level, agglomerative clustering follows the under algorithm:

1. Determine cluster distances between all pairs of clusters (every cluster begins as a single level)
2. Merge the 2 clusters that are closest to at least one one other
3. Repeat

The outcome: a ravishing dendrogram that may then be partitioned based mostly on area experience.

In fields like biology and pure language processing, clusters (of cells, genes, or phrases) naturally comply with a hierarchical relationship. Agglomerative clustering due to this fact allows a extra pure and data-driven choice of the ultimate clustering cutoff.

Pictured under is a pattern agglomerative clustering of the well-known Iris Dataset.

So why not use agglomerative clustering for each unsupervised classification drawback?

❌ Agglomerative clustering has a horrible runtime as datasets enhance in dimension.

Sadly, conventional agglomerative clustering doesn’t scale. The runtime is O(n³) or O(n²log(n)) if applied with a min-heap. Even worse, agglomerative clustering runs sequentially on a single-core and can’t be scaled up with compute.

Within the subject of NLP, agglomerative clustering is a high performer… for small datasets.

Reciprocal Agglomerative Clustering (RAC)

Reciprocal Agglomerative Clustering (RAC) is a method proposed by Google to scale the advantages of conventional Agglomerative clustering to bigger datasets.

RAC decreases the runtime complexity whereas additionally parallelizing the operations to make the most of a multi-core structure. Regardless of these optimizations, RAC produces the very same outcomes as conventional Agglomerative clustering when the info is absolutely linked (see under).

Word: Totally linked knowledge signifies that a distance metric will be calculated between any pair of factors. Non-fully linked datasets have connectivity constraints (often supplied within the type of a linkage matrix) whereby some factors are thought of disconnected.

Even with connectivity constraints (knowledge which isn’t absolutely linked), RAC and Agglomerative clustering are nonetheless usually similar, as seen within the second Swiss Roll dataset instance above.

Nevertheless, giant discrepancies can emerge when there are only a few attainable clusters. The Noisy Moons dataset is an effective instance of this:

RAC++ scales to bigger datasets than scikit-learn

We will examine RAC++ (an implementation of reciprocal agglomerative clustering) to its counterpart, AgglomerativeClustering, in scikit-learn.

Let’s generate some instance knowledge with 25 dimensions, and check how lengthy agglomerative clustering takes utilizing racplusplus.rac vs. sklearn.cluster.AgglomerativeClustering for datasets ranging in dimension from 1,000 to 64,000 factors.

Word: I’m utilizing a connectivity matrix to restrict reminiscence consumption.

import numpy as np
import racplusplus
from sklearn.cluster import AgglomerativeClustering
import time
factors = [1000, 2000, 4000, 6000, 10000, 14000, 18000, 22000, 26000, 32000, 64000]
for point_no in factors:
X = np.random.random((point_no, 25))
distance_threshold = .17
knn = kneighbors_graph(X, 30, include_self=False)
# Matrix have to be symmetric - carried out internally in scikit-learn
symmetric = knn + knn.T
begin = time.time()
mannequin = AgglomerativeClustering(
linkage="common",
connectivity=knn,
n_clusters=None,
distance_threshold=distance_threshold,
metric='cosine'
)
sklearn_times.append(time.time() - begin)
begin = time.time()
rac_labels = racplusplus.rac(
X, distance_threshold, symmetric,
batch_size=1000, no_cores=8, metric="cosine"
)
rac_times.append(time.time() - begin)

Here’s a graph of the runtime outcomes for every dimension dataset:

As we will see, there are drastic distinction in runtime between RAC++ and conventional Agglomerative clustering.

At simply over 30k factors, RAC++ is round 100x quicker! Much more improtantly, scikit-learn’s Agglomerative clustering hits a time restrict at ~35 thousand factors, whereas RAC++ might scale to a whole lot of 1000’s of factors by the point it hits an affordable time restrict.

RAC++ can scale to high-dimensions

We will additionally examine how nicely RAC++ scales to high-dimensional knowledge vs its conventional counterpart.

Time taken to generate clusters vs dimensionality for 3,000 factors

For 3,000 factors we will see that conventional agglomerative clustering is quicker however it scales linearly whereas RAC++ is sort of fixed. Working with 768 or 1536 dimensional embeddings has develop into the norm within the subject of NLP, and so scaling dimensionality to fulfill these necessities is necessary.

RAC++ has a greater runtime

Researchers at Google proved that RAC has a runtime of O(nk) where k is the connectivity constraint and nis the number of points— a linear runtime. Nevertheless, that is excluding the preliminary distance matrix calculation which is O(n²) — a quadratic runtime.

Our outcomes, operating a continuing 30-neighbor connectivity constraint do affirm an O(n²) runtime:

+ — — — — — — -+ — — — — — +
| Information factors | Seconds |
+ - - - - - - -+ - - - - - +
| 2000 | 0.051 |
| 4000 | 0.125 |
| 6000 | 0.245 |
| 10000 | 0.560 |
| 14000 | 1.013 |
| 18000 | 1.842 |
| 22000 | 2.800 |
| 26000 | 3.687 |
| 32000 | 5.590 |
| 64000 | 22.499 |
+ - - - - - - -+ - - - - - +

Doubling data-points is a 4x enhance in time.

A quadratic runtime limits how nicely RAC++ will carry out as datasets develop into actually huge, nevertheless, this runtime is already an enormous enchancment over the normal O(n³) or min-heap optimizedO(n²log(n)) runtime.

Word: the builders of RAC++ are engaged on passing the gap matrix as a parameter which might give RAC++ a linear runtime.

How RAC Works

Why is RAC++ so should quicker? We will cut back the underlying algorithm to a couple steps:

1. Pair clusters with reciprocal nearest neighbors
2. Merge the pairs of clusters
3. Replace neighbors

Word that the one distinction between this and the normal agglomerative clustering algorithm is that we ensure that to pair reciprocal nearest neighbors collectively. That is the place the identify Reciprocal Agglomerative Clustering (RAC) comes from. As you’ll see, this reciprocal pairing allows us to parallelize essentially the most computationally costly step of agglomerative clustering.

Pair clusters with reciprocal nearest neighbors

First we loop by way of to seek out clusters with reciprocal nearest neighbors, which means that their closest neighbors are each-other (keep in mind, distance will be directional!).

Merge pairs

RAC is parallelizable as a result of it doesn’t matter what order reciprocal nearest neighbors are merged in, so long as the linkage technique is reducible.

A linkage technique is the perform that determines the gap between two clusters, based mostly on pairwise distances between the factors contained in every cluster. A reducible linkage technique ensures that the brand new merged cluster is just not nearer to some other cluster after the merge.

Thankfully, the 4 hottest linkage strategies are reducible:

• Single linkage — min distance
• Common linkage — common of the distances
• Full linkage — max distance
• Ward linkage — minimizing variance

Since we all know that our recognized reciprocal pairs are one another’s nearest neighbor, and we all know that reducible linkage merges won’t ever make a newly merged cluster nearer to a different cluster, we will safely merge all reciprocal nearest neighbor pairs collectively directly. Every nearest-neighbor pair will be positioned into an accessible thread to be merged in response to the linkage technique.

The truth that we will merge reciprocal nearest neighbors on the identical time is incredible, as a result of merging clusters is essentially the most computationally costly step!

Replace nearest neighbors

With reducible linkage the order wherein nearest neighbors are up to date after merging additionally doesn’t matter. Subsequently, with some intelligent design, we will replace the related neighbors in parallel as nicely.

Conclusion

With a couple of check datasets, we’ve proven that RAC++ produces the very same outcomes as conventional Agglomerative Clustering (ie. sklearn) for absolutely linked datasets at a a lot better runtime. With an understanding of reducible linkage metrics and a primary understanding of parallel programming, we will perceive the logic that makes RAC++ a lot quicker.

For a extra full understanding (and proof) of the algorithm RAC++has adopted into open-source, check out the original Google research it was based mostly on.

The long run

Porter Hunley began constructing RAC++ to create taxonomies for medical time period endpoints produced by way of fine-tuned BERT embeddings. Every of those medical embeddings had 768 dimensions and out of the various clustering algorithms he tried, solely agglomerative clustering gave good outcomes.

All different high-scale clustering strategies required lowering dimensionality to provide any coherent outcomes in any respect. There may be, sadly, no fool-proof technique to cut back dimensionality — you’ll all the time lose data.

After discovering Google’s analysis round RAC, Porter determined to construct a customized open-source clustering implementation to assist his medical time period clustering analysis. Porter lead improvement, and I co-developed parts of RAC, notably wrapping the C++ implementation in python, optimizing runtime, and packaging the software program for distribution.

RAC++ allows tons of clustering purposes that are too gradual utilizing conventional agglomerative clustering, and can ultimately be scalable to tens of millions of datapoints.

Though RAC++ can already be used to cluster giant datasets, there are enhancements to be made… RAC++ remains to be in improvement — please contribute!

Contributing authors:

• Porter Hunley, Senior Software program Engineer at Daceflow.ai: github
• Daniel Frees, MS Stats & Information Science Scholar at Stanford, Information Scientist at IBM: github

GitHub — porterehunley/RACplusplus: A high performance implementation of Reciprocal Agglomerative…