Efficient clustering of sparse binary vectors

I'm trying to perform clustering of the data to improve the efficiency of brute-force kNN . The dataset consists of objects described by a large set of binary features, each identified by a 32-bit hash code. Data point can be understood as a 2^32 elements long very sparse binary vector, with bits set to 1 on the positions denoted by hash code of feature. To simplify, each of the data points is being represented as an array of hashes - if we know which of the bits are set to 1, we know which of them are set to 0.

I have a working distance function (mentioned in here) but have difficulties to cluster the dataset in reasonable time. Because of the binary nature of the data it is impossible to create any kind of mean value based on a collection of datapoints, so k-Centroids is not an option. I tried k-Clustroids but it doesn't converge, hierarchical approaches are too inefficient. Do you happen to know any clustering algorithm that would efficiently handle fixed size dataset, with custom metric calculation method without the need to create any temporary, centroid datapoints?

Many thanks.

• Perhaps you could find a lower-dimensionality continuous embedding approximation. – Emre Mar 2 '17 at 0:31

You can efficiently implement e.g. Euclidean distance or Cosine on sparse data (iterate over nonzero values only!). Then you can use e.g. Hierarchical clustering.

But also consider frequent itemset mining. Usually, on sparse binary data, frequent itemsets are better than clusters.

I'm a neuroscientist, and I encountered what I think is a similar issue. Just to give a little background: the brain is divided in ~ 200k voxels. Using a technique known as DTI, fibers are sought. Either a fiber passes through a certain voxels (1), or it doesn't (0). Therefore, given a certain voxel, the connections pattern with the rest of the brain is a 200k vector; its components being mostly 0s, sometimes 1.

a) either calculate the cross-correlation matrix between all vectors of your dataset, or the distance matrix; in both cases, you'll get a square matrix. Which distance to choose: I would suggest the Jaccard distance, eminently suitable for binary, sparse feature vectors.

b1) use the spectral reordering algorithm, as described in http://www.pnas.org/content/suppl/2004/08/20/0403743101.DC1/03743SuppText.pdf (read the paper too, it is wonderful) to separate your data into clusters (each square is going to be one), or at least to get an idea about the number of your clusters. Optionally,

b2) apply k-means to cluster the rows (or columns; it doesn't matter, being the aforementioned cc/distance matrices symmetrical) of your matrix of choice.

HTH, kind regards, Luca