# Sparse hyperspace clustering

I have a dataset of M elements where every item is represented by a feature vector of length N where N is very large and only a small subset of N is bigger then zero for every item. So I have a sparse MxN matrix and I want to cluster these M items.

What tools and algorithms do you advise to use? Any script or library in R or in other programming languages would be very useful.

• It is important to hear why you see such data problematic for you. Something made you to post the question. What was that? – ttnphns Mar 19 '13 at 17:02
• @ttnphns I want to learn best practices in this area, so I will not need to invent wheel again. – metdos Mar 19 '13 at 18:48

Your data is quite likely best modeled as a network. I suggest using a similarity (note, not a distance) between vectors. This could for example be the cosine similarity, or, if weights are not important, the Tanimoto coefficient. Cosine similarity is often used in document clustering (which has similar dimensionality characteristics), and Tanimoto is often used in what is called 'fingerprint' analysis (e.g. when analysing databases of chemical compounds), again with similar dimensionality characteristics. You can subsequently cluster such a network with one of the algorithms that do not require the number of clusters as input parameter; I recommend either RNSC (restricted neighbour search clustering), the Louvain method, or MCL (Markov cluster algorithm; disclaimer - I wrote this). Another (well-known) algorithm is APC (Affinity Propagation Clustering), which is based on similar principles as MCL but differs quite a bit in how these principles are modeled.

• Is there any efficient way to calculate cosine similarity for sparse matrices? Complexity of naive solution is Constant * M^2. – metdos Mar 20 '13 at 10:30
• I use the program 'mcxarray' (which is part of MCL). It is threaded and can do job parallelisation (use multiple machines, then combine results). It uses sparse encodings, so N does not figure. I've used mcxarray with M values upwards of 1,000,000. What is your M (and hardware)? I have looked into speeding up computation using the metric properties of alpha (the angle associated with the cosine), but this is really hard - 2-fold reduction of the number of comparisons is the best so far, which is far too little compared to the benefits of simplistic brute-force. – micans Mar 20 '13 at 10:40

The Matrix package is standard in R and comes installed by default.

Example:

library(Matrix)
N <- 1e6
M <- 1e4
x <- Matrix(0, nrow=N, ncol=M)
x[1, 2] <- 1
x[1:10, 1:10]


Most commands are nearly the same as matrix. There are a couple things that are slightly different that you need to make sure to use so that you stay in sparse matrix format instead of standard matrix format (e.g., cBind instead of cbind).

You might also check the packages sparcl and bibmemory and see what they do in their examples.