What algorithm should I use to cluster a huge binary dataset into few categories?

I have a large (650K rows * 62 columns) matrix of binary data (0-1 entries only). The matrix is mostly sparse: about 8% is filled.

I would like to cluster it into 5 groups - say named from 1 to 5. I have tried hierarchical clustering and it was not able to handle the size. I have also used hamming distance based k-means clustering algorithm, considering the 650K bit vectors of length 62. I did not get proper results with any of these.

• I can't comment b/c of my 1 rep so I had to type this as an answer. You might look into Jaccard Similarity. I think python scipy has implementations of it. Jaccard... Mar 11 '14 at 6:10
• Is there any reason to assume the data naturally falls into five groups, at least to some extent? Are you really interested in the row clustering, or are you also interested in relationships between the 62 traits encoded in the bit vectors? If the latter, then other techniques are more suitable. Mar 11 '14 at 11:31

You are asking the wrong question.

I'm not surprised that above algorithms did not work - they are designed for very different use cases. k-means does not work with arbitrary other distances. Don't use it with Hamming distance. There is a reason why it is called k-means, it only makes sense to use when the arithmetic mean is meaningful (which it isn't for binary data).

You may want to try k-modes instead, IIRC this is a variant that is actually meant to be used with categorial data, and binary data is somewhat categorial (but sparsity may still kill you).

But first of all, have you removed duplicates to simplify your data, and removed unique/empty columns for example?

Maybe APRIORI or similar approaches are also more meaningful for your problem.

Either way, first figure out what you need, then which algorithm can solve this challenge. Work data-driven, not by trying out random algorithms.

• Can you please explain why "Don't use with Hamming distance"? It might make sense, after all it is available in Matlab.I don't mind opening a new question, if it make sense. Apr 20 '15 at 12:05
• Because of the mean. Arithmetic mean is meaningless with hamming distance or binary data. Use the mode or medoid instead. Apr 21 '15 at 9:14
• Just to make sure I'm getting it right: matlab uses the arithmetic mean when updating the centroids when using the k-means together with the hamming metric. Is that right? What's the right way to use this metric in matlab? Apr 21 '15 at 10:18
• k-means is called k-means because it uses the mean. Otherwise, it's called k-medoids, k-modes, etc. The mean is good for L2 - sum of squared deviations. Apr 21 '15 at 14:17
• So, matlab uses k-means together with the hamming metric; this doesn't make much sense. Apr 22 '15 at 9:51

A classic algorithm for binary data clustering is Bernoulli Mixture model. The model can be fit using Bayesian methods and can be fit also using EM (Expectation Maximization). You can find sample python code all over the GitHub while the former is more powerful but also more difficult. I have a C# implementation of the model on GitHub (uses Infer.NET which has a restrictive license!).

The model is fairly simple. First sample the cluster to which a data point belongs to. Then independently sample from as many Bernoullis as you have dimensions in your dataset. Note that this implies conditional independence of the binary values given the cluster!

In Bayesian setting, the prior over cluster assignments is a Dirichlet distribution. This is the place to put priors if you believe some clusters are larger than others. For each cluster you must specify prior, a Beta distribution, for each Bernoulli distribution. Typically this prior is Beta(1,1) or uniform. Finally, don't forget to randomly initialize cluster assignments when data is given. This will break symmetry and the sampler won't get stuck.

There are several cool features of the BMM model in Bayesian setting:

1. Online clustering (data can arrive as a stream)

2. Model can be used to infer the missing dimensions

The first is very handy when the dataset is very large and won't fit in RAM of a machine. The second can be used in all sorts of missing data imputation tasks eg. imputing the missing half of binary MNIST image.

Maybe I'm little bit late with answer, but probably it would be useful for some body in future.

Adaptive Resonance Theory is a good algorithm for binary classification problems. Check about ART 1. More information you can see at free Neural Network Design book in chapter 19.

This network combine great biological idea and good math implementation. Also this algorithm is easy to implement and, in this book, you can also find step-by-step instruction on how to build this classifier.

You are asking the right question. And you can use kmeans!!! Despite what you may be told by some, you absolutely can cluster with kmeans. There is nothing about binary data that will cause kmeans to fail. However, you might want to consider the following:

1 - Zero-mean your matrix by column. This means that you compute the mean row vector, which now becomes a real valued vector, and then subtract that vector from each of the original binary vectors. Your 0/1 binary matrix of 650K row vectors now becomes a real valued matrix of 650K vectors. Note that this DOES NOT change the mutual distance (or similarity) between vectors. It is just a translation operation, applied identically to each vector.

2 - Apply the sign function to the matrix. The sign function forces each matrix element to -1 if it is negative, or to +1 otherwise. The result of this transformation, in steps 1 and 2, is that the new matrix is no longer sparse.

3 - Now apply kmeans. you can use the Euclidean metric, or experiment with other metrics that you kmeans implementation supports. No need to use a specific binary clustering algorithm. kmeans is simple and clustering 650K vectors should be easily feasible on a decent desktop.

4 - If you wish to have binary cluster vectors as the result, then apply the sign function to the final k clusters. You may also convert the final cluster vectors from +1/-1 representation to 0/1 representation (but only after applying the sign function).

Things to note:

Because you only have 62 dimensional vectors the range of 'similarity' values that are possible between vectors in the binary representation is 62 (corresponding to a Hamming distance between 0 and 62.) Since the range of distances between binary vectors is thus limited, any ranking by hamming distances will necessarily result in numerous ties. As you try to squeeze 650K vectors into only 62 possible distance buckets, the number of vectors per bucket will depend on the number of clusters, but will generally be large and you may need to resolve ties by going back to the original data from which you derived the initial binary matrix.