3
$\begingroup$

I have a huge dataset (50,000 2000-dimensional sparse feature vectors). I want to cluster them in to k (unknown)clusters. As hierarchical clustering is very expensive in terms of time complexity (though it provides better result), I have designed my clustering framework as follows:

  1. do K-means clustering to partition the data into several bins (k is unknown so I make it reasonably large. eg. k=500)
  2. get centroids of all 500 partitions
  3. do hierarchical clustering on those 500 centroids(kind of merging based on some threshold value t)
  4. assign the datapoints to the nearest centroid(centroids emerged from hierarchical clustering)

I would like to know, whether my approach is efficient and if possible any other good solution to this problem.

Thank you.

Improve this question
$\endgroup$
3
  • $\begingroup$ are the features binary, tf-idf ... ? how sparse, % zeros ? How will the clusters be used ? What toolset ? Why 500 ? (100M is not huge). Try flat k-means e.g. scikit-learn but k-means may be weak for your data. $\endgroup$
    – denis
    Jul 29, 2012 at 11:08
  • $\begingroup$ they are software behavioral features, similar to binary tf-idf. feature vectors are very sparse, around 95% of the coordinates are zeros. I randomly choose 500 (based on the domain knowledge, there is no strong backing for that). I don't want to use PCA or SVD to reduce the dimensionality as I want consider all the features for clustering. yes, K-means is not suitable for spare dataset. Do you recommend any state-of-the-art clustering algorithm for this kind of problem. $\endgroup$
    – Maggie
    Jul 29, 2012 at 12:27
  • $\begingroup$ 1) the scikit-learn link does k-means with scipy sparse arrays (although I agree with Anony-Mousse, "k-means is bound to fail"); 2) start with 10 or 20 clusters, small enough to understand on paper / plot; 3) can you hand-classify say 100 points ? Then look at semi-supervised SVMs. $\endgroup$
    – denis
    Jul 29, 2012 at 13:29

2 Answers 2

Reset to default
4
$\begingroup$

Why don't just first look at other clustering algorithms? For example DBSCAN does not need to know the number of clusters, and it can work with any distance function (assuming that you want to go with something like cosine distance for your sparse vectors).

Given the characteristics of your data, k-means is just bound to fail. The problem is that the means will most likely be no longer sparse, so they are actually outliers, and by no means central objects. Don't use k-means with sparse vectors or non-euclidean distances! (k-means may not converge for other distance functions, as the mean might not minimize the objective function anymore!)

Seriously, there are at least 100 more modern clustering algorithms. Try these first.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thank you @Anony-Mousse, I'll look into DBSCAN algorithm. I am quite new to large-scale clustering and familiar with only k-means and hierarchical clustering algorithms. Can you suggest me some related modern clustering algorithms for spare vectors to start with. $\endgroup$
    – Maggie
    Jul 27, 2012 at 22:09
0
$\begingroup$

I don't have any detailed experience with it, but a common approach is to use Canopy Clustering, which is similar to what you are describing. In fact, it's often used as a precursor to k-means. Unfortunately the only implementations I know of are in Hadoop/Mahout, so you might have to do some searching to find something usable. However, as your approach seems fairly similar, if you have access/familiarity with the algorithms, it might be easy to do it the way you've described.

Anyway, here are some descriptions:

http://en.wikipedia.org/wiki/Canopy_clustering_algorithm

https://cwiki.apache.org/MAHOUT/canopy-clustering.html

I think there's an implementation listed under the second link.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Canopies are more of a pre-clustering. An aggregation step that helps speed up a later operation. $\endgroup$
    – Has QUIT--Anony-Mousse
    Jul 27, 2012 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.