Hierarchical Clustering, Why Always Agglomerative?

Question

I'm working on clustering for 6 month right now and there is question that bothers me lately, and that is why in every single resource about hierarchical clustering someone introduced two types of it (Agglomerative and Divisive) and then said "Hey, We only focus on Agglomerative"!

In my project I have to use hierarchical clustering and for now I'm using K-Means to divide the observations and in each new cluster I run K-means again till I reached the criteria.

There is a problem here; as long as number of observation are quit large (26000 for now) and each observation has 344 feature (output of PCA), I cannot follow agglomerative method and I prefer divisive method. For now I choose number of cluster as a constant (equal to 7) and clustering till I have 3 levels. Because of these constraints my model is not quit well. So I decided to use Elbow Method to determine number of clusters in each step.

Now after this long introduction, I came up with some problems:

1. Using elbow method is too expensive. From here I'm choosing optimized k in each set of data. But as elbow method wants inertia (intra cluster distance) for every single k, I have to calculate this statistics for each set of data. This is a very time consuming task and choosing maximum number of k is, let's say, risky.
2. An important issue besides number of clusters is stopping criteria. For now I said "If number of observation in a node is under 100, Stop!". But you know this doesn't work very well. So, what is the best stopping criteria for divisive method?

After all of these, is there any methods that implemented divisive hierarchical clustering ?

If you need a clarification, just simply ask for it. Thank You.

Answer 1

The main reason divisive clustering is not used is that it is much more computationally intensive than agglomerative. If your problem runs slowly with agglomerative, it will run much more slowly with divisive.

With agglomerative, we start by computing distances among the N objects. There are $\frac{N(N-1)}{2}$ calculations, but each is very fast (and may even be in the data). Each step "up" requires fewer calculations and each is very fast.

With divisive, we start with $2^N$ comparisons (because each object can be in one of two clusters) and each is more time consuming. And the costs stay high because, while each cluster gets smaller there are more of them.

If you have 100 objects, then agglomerative starts with 4950 comparisons while divisive starts with $1.26*10^{30}$. But you have $26,000$ objects. That's $2^{26000}$ comparisons. That's (very roughly) $10^{8000}$ calculations. The universe will end before you finish.

Answer 2

To choose the optimal split in divisive clustering, one would need to check O(2^n) possible splits unless you use some heuristics.

Several such methods exist:

• DIANA for "divisive analysis"
• bisecting k-means
• x-means
• g-means

Most of these are k-means based heuristics, because of performance. So in particular, they only work for the least-squares objective of k-means and cannot support the entire range of HAC linkages.