Benchmarking a clustering algorithm

Question

Intro

I built a clustering algorithm for a specific problem I have. The clustering algorithm wasn't my main goal, I just had to be able to separate the data into clusters prior to further processing, and I wanted to see if I could cluster the data so that I can later run my further processing on unlabeled data.

Some Details

It turns out that it worked great. However, my dataset might be too small an I might just overfit. So my question is can you point me toward standard benchmark datasets to compare my algorithm against?

Some more details: My algorithm is designed to cluster data of the following form:

• Each sample is a block (or sequence) of binary values.
• All samples are of the same size (same number of bits).
• Samples can be quite long (up to about a thousand bits each).

I presume that each sample originates from some (unknown) distribution and that each cluster originates from a different distribution. In a sense, my problem is very similar to a GMM model with a maximum likelihood of classification. The main differences are that the distribution isn't gaussian (variables are discrete), and the GMM would perform very poorly for distributions with a dimension of 1000 due to the curse of dimensionality. Somehow (I'm not sure yet exactly how), my algorithm circumferences this problem, and I wonder if it is because of the dataset.

My Questions

1. Are there standard algorithms that try to accomplish the same goal or at least try to cluster binary sequences of relevant lengths that I can benchmark my algorithm against?
2. Are there any datasets that I could use (binary sequences) in order to test my algorithm against further data?

Answer 1

Alternative methods: Any distance-based method - such as Single, Complete, Average Linkage of Hierarchical clustering or Partitioning Around Medoids clustering - can be used with an appropriate distance on binary sequences, such as Simple Matching or Jaccard. There is also a standard mixture model for such data that is usually called latent class model, see https://en.wikipedia.org/wiki/Latent_class_model. Clusters are modelled as subsets within which variables are independent ("local independence"). The R-package poLCA can do this. One could also use distances, run multidimensional scaling on them, and then run a GMM on the MDS output as is done in our R-package prabclus, function prabclust. There's also BayesLCA for Bayesian latent class analysis.

I add that somebody once told me that despite originally being designed for continuous data, k-means can work well with binary sequences (if the dimension is not very low - not sure about very big). I think I've never tried it, but this person may be right and it could be worth a try.

The prabclus-package has example data sets veronica and kykladspecreg, although both come without ground truth in the package. (I have something of a ground truth vector for veronica, and you can contact me off site about it, however these "true species" are not necessarily reliable.) poLCA also has example data sets, but I don't know whether these have ground truth information.

Some general considerations regarding cluster benchmarking are here: https://arxiv.org/abs/1809.10496 You may also think about generating artificial data with known truth for benchmarking.