2

I'm trying to perform a hierarchical Clustering Analysis in a dataset of 40 attributes and +70,000 records, which is mostly composed by categorical variables. I've used Matlab and RapidMiner to execute the analysis but among their poor peformance and the lack of consistent outputs, I still can not get any results.

Is it any constraint to use this clustering method for such a dataset like the one I described?

I need to perform this analysis as part of a data mining research, to apply feature selection algorithms and measure performance gains afterwards.

gung - Reinstate Monica
  • 132,789
  • 81
  • 357
  • 650
formacero10
  • 53
  • 1
  • 5
  • If you are clustering records, 70000 is too much for hierarchical method. First, 70000x70000 distance matrix is huge: will you computer or implementation cope? Another reason why hierarchical clustering is bad with thousands of records is that the [risk/amount of suboptimality](http://stats.stackexchange.com/q/40933/3277) of the greedy algo can apper quite large on such datasets. Consider doing clustering by portions or using methods such as Two-step cluster which are designed for huge datasets. – ttnphns Oct 07 '14 at 07:05

1 Answers1

2

I have used single-link clustering on 100k objects with ELKI. The SLINK implementation there is reasonably fast - it should complete in 10 minutes or so on this size of data. It doesn't keep a 70000x70000 matrix in memory (SLINK is $O(n^2)$ runtime, $O(2n)$ memory - much better than the naive algorithm which is $O(n^3)$ runtime and $O(n^2)$ memory - but also note that SLINK can only do single-linkage clustering). But categorial variable support isn't available in the download package - you would need to implement the parser, data type and the distance function yourself (which isn't hard, because there is a Tutorial that worked for me). Or you encode your categories as numbers, and use one of the included distance functions.

There are also various attempts at making an approximative hierarchical clustering in much less time. Wasn't BIRCH an algorithm like this? But I don't know a good implementation of BIRCH.

But have you validated your distance function? If your distance isn't working well, hierarchical clustering (or any clustering based on distance) will fail. I always suggest that people first understand how to quantify similarity. Then cluster.

Has QUIT--Anony-Mousse
  • 39,639
  • 7
  • 61
  • 96