How to assign existing cluster numbers for future data, using hierarchical clustering algorithms?

Question

Assume we have some good clusters from some clustering algorithm and we want to assign the cluster numbers (labels) to future data (= to enrol new data points into the existing clusters, if to word it other way).

In K-means, we can assign future data into clusters based on cluster center. Cluster center is the summary statistic of the cluster and its localization in space. But how to do that for some hierarchical clustering algorithms? Hierarchical clustering may not tie oneself up with something like cluster center.

Hierarchical clustering algorithms I am thinking about can be top-down or bottom up. And assume we have some threshold to cut the Dendrogram into clusters.

Answer 1

My answer is about agglomerative (i.e. bottom-up) hierarchical cluster analysis, HAC, which methods are overviewed here. (I'm not quite sure if the answer can be extended to divisive, top-down hierarchical algorithms which I know less.)

Every linkage method defines, its characteristic way, the distance between two clusters - or between cluster and point as a particular case. Therefore it is possible to compute the distance between a point and a cluster according to the selected linkage method - even if the cluster already exists as a descendant from past HAC or other clustering method session. I mean - it is possible to assign a point to a cluster without doing the assemblage of that cluster hierarchically by steps within HAC. Few methods (namely, WPGMA, WPGMC) is the exclusion in that they demand the stepwise assemblage to be repeated in order to assign some next point to the cluster.

The computations are quite straightforward, different for different methods, and are accomplishable by matrix algebra operations.

I've implemented this task of assignment of new objects to existent clusters according to the different HAC linkage rules as a program for SPSS. Also, I've implemented the HAC program with the option to do the assignment and stop (not to cluster up to the end), among other options. (The link for the page is in my profile, and the download is called "Clustering".)

The first program !assclu is faster because it doesn't perform the stepwise agglomerative assemblage before the assignment, but the second program !hieclu is more general. Program 1 requires you to have the matrix of distances between all the old points (that are partitioned into the clusters) plus the new points-to-enrol, added to that matrix. Program 2 will accept the same input but can also allow you to have just the matrix of distances between the clusters, plus the new points-to-enrol added to that matrix.

The being discussed task of assignment of new objects to old clusters is in-between (or a hybrid of) the clustering and the classification tasks. Like classification, it uses data already labelled (clustered). But it does not derive classification rules by exploring the classes. Instead, it applies the clustering rule preformulated by the chosen linkage method, coming from the domain of clustering; in other words, the step of discrimination (learning) between the classes is skipped, and just the classification by the rule is performed. See a recent question about the topic.

Answer 2

Don't do this.

It's not even a good idea for k-means.

Do not assume the clustering is perfect, and also do not assume that it never changes. And you won't be able to react appropriately.

For example, consider the data set

-5    -2     +2    +5

This will cluster at height 3 into the two clusters $\{-5,-2\}$ and $\{+2,+5\}$. But now a new data point arrives:

-5    -2  0  +2    +5

and now the best solution is three clusters, $\{-5\}$, $\{-2,0,+2\}$ and $\{+5\}$. The result has changed completely!

Clustering algorithms are fragile, use them with care.

Don't even assume they got everything labeled correctly - because they won't. The proper way to use clustering is to study the resulting clusters, derive a hypothesis from that then test and verify this hypothesis. You can then of course check if new data is in accordance with this hypothesis etc., but you really should spell out this pattern.

A viable, but also questionable because of above reasons, approach is to train a classifier. You want a robust classifier, because your clustering wasn't perfect; so you really want to avoid overfitting. If you just need something, but quality is not very important, then this is feasible (e.g. when you map image snippets to visual words, you don't need to get every single visual word correct, but you only want to get a sufficiently similar histogram in the end; then such approaches work well enough.)