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.
Please help.
You are asking the wrong question.
Instead of asking "what algorithm", you should be asking "what is a meaningful category/cluster in your application".
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.
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:
Online clustering (data can arrive as a stream)
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.
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.
Maybe I'm little bit late with the answer, but probably it would be useful for some body in the future.
Adaptive Resonance Theory is a good algorithm for binary classification problems. You can read more about ART 1 (i.e. Neural Network Design book in chapter 19). The algorithm is quite easy to implement and, in the book, you can also find step-by-step instruction on how to build the classifier.
You can certainly use kmeans as it was mentioned by Shlomo Geva, but kmeans does not give best answers for some datasets. I recommend you look at these publications:
'Powered Outer Probabilistic Clustering' (http://www.iaeng.org/publication/WCECS2017/WCECS2017_pp394-398.pdf)
'Clustering for Binary Featured Datasets' (https://link.springer.com/chapter/10.1007/978-981-13-2191-7_10)
You can also look at Principal Component Analysis - PCA (https://en.wikipedia.org/wiki/Principal_component_analysis), but in my experience with some examples, that might not provide great answers either, similarly to kmeans.
