<p>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 \times 275$ matrix. I want to cluster these bit-vectors. I have tried single link hierarchical clustering on a small data set, $3000 \times 275$, and the result is promising.</p>

<p>I know that single link hierarchical clustering algorithm is not scalable as the time complexity is $O(n^2)$. I am planning to apply a 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(C_1,C_2)&lt; t$; then: merge $C_1$ and $C_2$).</p>

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

<p>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.</p>

CC BY-SA 3.0
2012-03-19T19:37:24.017Z
it's feasible, and it will probably be more efficient. Whether it gives you a GOOD answer is another matter altogether. I assume the distance you're using is the Hamming distance ?
Suresh Venkat
CC BY-SA 3.0
2012-03-19T20:15:46.027Z
What does the data represent? (see also ftp://cs.joensuu.fi/franti/papers/GraphPnn-TPAMI.pdf)
Marzio De Biasi
CC BY-SA 3.0
2012-03-19T20:31:45.063Z
@suresh: I am using Euclidean distance, Is it preferable to use Hamming distance over Euclidean distance? Thank you :)
Maggie
CC BY-SA 3.0
2012-03-19T20:31:50.383Z
@Vor: each row represent an executable(software) and the dimensions represent the extracted features of that executable.
Maggie
CC BY-SA 3.0
2012-03-19T20:43:21.610Z
@Mahin I was merely wondering. it really depends on the problem whether you use Euclidean or Hamming. But if you're using Euclidean, then $k$-means is another possibility.
Suresh Venkat
CC BY-SA 3.0
2012-03-19T20:46:09.267Z
@Mahin: ok, so every dimension is a weight between 0 and 1? Do you know in advance what a "cluster" should represent and/or how many clusters should be found?
Marzio De Biasi
CC BY-SA 3.0
2012-03-19T21:03:08.660Z
@SureshVenkat:My research area is purely software security and now I am gradually entering the world of machine learning :). yes, I have considered using k-means, but its mentioned that it has several serious weaknesses like determining 'K' is a problem and highly dependent on initialization. I am going through few good papers to fully understand k-means/k-medoid.
Maggie
CC BY-SA 3.0
2012-03-19T21:05:12.963Z
@Vor: yes its between 0-1, but I am unaware of optimal number of clusters. thats why thought to start with hierarchical clustering.
Maggie
<ds.algorithms><machine-learning><clustering>
Divide-and-conquer approach for hierarchical clustering
Maggie
# Divide-and-conquer approach for hierarchical clustering

(Asked by: username_0 on 2012-03-19)

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 \times 275$ matrix. I want to cluster these bit-vectors. I have tried single link hierarchical clustering on a small data set, $3000 \times 275$, and 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 a 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(C\_1,C\_2)< t$; then: merge $C\_1$ and $C\_2$).

The time complexity for my new approach is $O(p) + O(pq)$, where $p$ is the number of chunks and $q$ the average number of clusters in each chunk. Note: I assume that when hierarchical clustering is applied, each chuck 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.

**Tags:** ds.algorithms, machine-learning, clustering
> **Comments:**
> **username_1**: it's feasible, and it will probably be more efficient. Whether it gives you a GOOD answer is another matter altogether. I assume the distance you're using is the Hamming distance ?  
> **username_2**: What does the data represent? (see also ftp://cs.joensuu.fi/franti/papers/GraphPnn-TPAMI.pdf)  
> **username_0**: @suresh: I am using Euclidean distance, Is it preferable to use Hamming distance over Euclidean distance? Thank you :)  
> **username_0**: @Vor: each row represent an executable(software) and the dimensions represent the extracted features of that executable.  
> **username_1**: @Mahin I was merely wondering. it really depends on the problem whether you use Euclidean or Hamming. But if you're using Euclidean, then $k$-means is another possibility.  
> **username_2**: @Mahin: ok, so every dimension is a weight between 0 and 1? Do you know in advance what a "cluster" should represent and/or how many clusters should be found?  
> **username_0**: @SureshVenkat:My research area is purely software security and now I am gradually entering the world of machine learning :). yes, I have considered using k-means, but its mentioned that it has several serious weaknesses like determining 'K' is a problem and highly dependent on initialization. I am going through few good papers to fully understand k-means/k-medoid.  
> **username_0**: @Vor: yes its between 0-1, but I am unaware of optimal number of clusters. thats why thought to start with hierarchical clustering.  

---

## 0 answers

