# Divide-and-conquer approach for hierarchical clustering

I have a huge data set (33K), each represented as a bit-vector of 275-dimensions. basically my data set can be represented as a 33000 x 275 matrix. I want to cluster these bit-vectors. I have tried single link hierarchical clustering on a small data set, 3000 x 275, the result is promising.

I know that single link hierarchical clustering algorithm is not scalable as the time complexity is $O(n^2)$. I am planning to apply divide-and-conquer approach, i.e., divide the dataset into chunks of equal size and cluster each chunks individually and finally merge the clustered chunks based on distance (if: $d(C1,C2)< t$; then: merge $C1$ and $C2$).

The time complexity for my new approach is $O(p)O(1) + O(pq)$, where $p$ is number of chunks and $q$ is the average number of clusters in each chunk.
Note: I assume that when hierarchical clustering is applied, each chunck will take same amount of time and its constant for all chunks, thus $O(n^2)$ will become $O(1)$.

I want to know, whether the above mentioned clustering approach is feasible and efficient. or is there any logic flaws in applying divide-and-conquer approach for clustering

-
This question seems to belong to the Computer Science forum rather than the statistics forum. –  Andrew Apr 17 '12 at 12:34

## migrated from stackoverflow.comMar 26 '12 at 18:14

This question came from our site for professional and enthusiast programmers.

I found a few problems in your approach, namely:

Single Link (SLINK) is a hierarchical clustering technique. When you cluster individual chunks of data (subsets) you will get a dendrogram (similar to a tree) of data, where the items that are closer to each other are clustered first and the branches near the top indicate sub-families that are more unlike each other.

With your approach, if you merge these dendrogram at the top, you will lose this relationship and you are automatically stating that items within each subset of your data are more similar (there is less distance) to each other compared to items in another sub-tree. Of course, this is OK if you first select the subsets of your data in an intelligent manner.

If you were to use SLINK or brute force to organise the subsets of data into partitions that are most similar to each other, you would take $O(n^2)$ time, although you might be happy with using a heuristic approach if you can accept a sub-optimal solution.

The second flaw that I notice is that you assume that using SLINK to merge $P$ items takes $O(1)$ time when it should take $O(P)$ time.

For large n, if you divide the n items into a small constant number of groups, $\frac{n}{p}$ where $p$ is constant, $O(\frac{n}{p})$ is still $O(n)$.

-
(+1) For the care you took to comment the approach proposed in the OP. –  gui11aume Jun 17 '12 at 15:59

A common approach to cluster large datasets is to use a k-d tree, which is similar to divide and conquer. k-d trees work well in low dimension, but their performance is reported to be not as good as dimensionality increases.

k-d trees are not suitable for efficiently finding the nearest neighbour in high dimensional spaces. As a general rule, if the dimensionality is k, the number of points in the data, N, should be N >> 2k.

In your case, the condition is not met, but you can still have a look at this article which shows a pseudo-code for fast clustering using k-d trees.

-