# Looking for sparse and high-dimensional clustering implementation

I'm looking for a clustering implementation with the following features:

• Support for high-dimensional data. Now I have approximately 160.000 dimensions/features.
• Be able to manage sparse matrix. That is, not only to read sparse matrices, but also capable of making operations in this format.
• Properly shows the centroid for each cluster.

I've tested some packages:

• Rapidminer, which seems to be a memory eater, I suppose because although capable of reading a sparse matrix, it is not capable of working with them as they are.
• Cluto, which is very fast and low-memory consumption, but it is not able of show properly the centroid elements (source code not available). It shows descriptive features together with a percentage of how that feature contributes to the average similarity, but there is no clear info (here is a question about that, with no clear answer) about how is calculated that, and also I have clusters where there is 0.0% but it is not clear for me if this means the program is unable to show an upper precision or if that feature has nothing to do tho the average similarity.

• Centroids aren't very meaningful for sparse vectors IMHO. – Has QUIT--Anony-Mousse Mar 6 '12 at 11:38
• How many data points, how many classes, what data format ? Do you need centroids (agree w Anony-Mousse), or data points near centres, or a good classifier ? I can recommend scikit-learn linear_model.sparse.SGDClassifier, also their RFE. – denis May 5 '12 at 16:49

I recommend you to see the answer that JCWong gave in this question about a method called 'sparse clustering' developed by Robert Tibshirani & Daniela Witten. This method is able to select the only features that are really determining the differences between groups in the data. It is available as an R library called 'sparcl'

The article is:

Witten DM and R Tibshirani (2010) A framework for feature selection in clustering. Journal of the American Statistical Association 105(490): 713-726.

• You and the OP are using the term sparse in two very different ways. The paper you reference is not at all geared towards handling sparse matrices. It is concerned with taking a dense $n \times p$ matrix and finding a smaller $q < p$ set of features (columns) to cluster the $n$ data points. The penalization approach uses $\ell_1$ and $\ell_2$ ball constraints as well as nonnegativity constraints and, as far as I know, appears to have only been tried on problems up to a couple orders of magnitude smaller than the the OP's. – cardinal Mar 6 '12 at 12:08
• @cardinal: Are there any good terms for differentiating between sparse clustering and clustering on sparse matrices? I've encountered similar confusion when looking for information on "sparse PCA." – Zach Oct 2 '12 at 12:32

I've had success with the CLARA function in R, from the Cluster package on a matrix with ~45,000 rows.

I believe you can find Matlab very useful for your needs.
Here you can find a video tutorial that explains how to handle large data sets AND explains the new features for the x64 versions regarding memory allocation etc.
Also Matlab is very well suited for handling sparse matrices (and any type of matrices), contains several built-in functions and user provided functions for handling centroids, and so on.
Just my 2 cents.