0
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 4
    $\begingroup$ 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 ? $\endgroup$ – Suresh Venkat Mar 19 '12 at 19:37
  • $\begingroup$ What does the data represent? (see also cs.joensuu.fi/franti/papers/GraphPnn-TPAMI.pdf) $\endgroup$ – Marzio De Biasi Mar 19 '12 at 20:15
  • $\begingroup$ @suresh: I am using Euclidean distance, Is it preferable to use Hamming distance over Euclidean distance? Thank you :) $\endgroup$ – Maggie Mar 19 '12 at 20:31
  • $\begingroup$ @Vor: each row represent an executable(software) and the dimensions represent the extracted features of that executable. $\endgroup$ – Maggie Mar 19 '12 at 20:31
  • $\begingroup$ @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. $\endgroup$ – Suresh Venkat Mar 19 '12 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.