Techniques for Cluster Analysis of a Very Large (n=140000) Binary Dataset in Python?

Question

In essence: what techniques in Python are possible to find clusters/trends in a very large categorical dataset?

My very large dataset (140000 rows/observations, 80 variables) of categorical data has been re-coded using one-hot encoding, so they are all binary (e.g ethnicity_black, ethnicity_asian). This dataset is for instances of police use of force in the UK.

I was planning on doing agglomerative hierarchical clustering on it to find patterns (via cluster description) in use-of-force events, but I cannot accomplish this as the distance matrices are always too large and keep crashing. I was using Gower's distance since they are all dummy variables, and the gower package.

I have tried doing dimensionality reduction via MCA (like PCA but for categorical variables) but that simply reduces the number of columns, and the distance matrix is still too huge (140000x140000 requires 72.7Gigabytes of RAM).

I then tried reducing to the first 10000 rows, but that takes up 10000x10000=100000000 (100 million cells), and exceeded the recursion depth limit when constructing the dendrogram. Not sure if it is appropriate to simply take a tiny random subset of the 1400000 rows? Since that might be unrepresentative in terms of revealing patterns.

As such, I'm looking for other clustering methods besides hierarchical clustering, since K-means only works for continuous data, as does DBSCAN, since they use Euclidean distances. Was wondering if you guys have encountered similar situations before in your work, and could share about other techniques or possible workarounds in this case?

tldr; K-Means and DBSCAN seem to be for continuous data, and hierarchical clustering isn't very scalable to a large dataset due to the dissimilarity matrix required. I'm exploring K-modes but not sure how to interpret the output as well...

I did this MCA - Hierarchical Clustering technique before but in R, following the methodology used in this paper closely: https://erf.org.eg/wp-content/uploads/2019/11/Fateh-Belaid_Manuscript_FB_10-09-2019_FB.pdf

However, even that workflow doesn't work for my current dataset as it's simply too big.

Any advice would be appreciated...

Thank you very much!

Answer 1

Since you have binary data, you can use hamming distance as your similarity metric for clustering.

Then you have to handle the size of your data. Here are couple of options:

1. Rent a bigger computer or a cluster of computers from cloud computing service.

2. Treat the problem as a streaming data problem. Use "online" techniques to load and fit only a portion of the data at a time.

Answer 2

Disclaimer: I've never had to cluster using this sparse of data before, but it might be worth using a stacked autoencoder to reduce the data into a latent continuous space. Once reduced, you can cluster the data using traditional methods.

Because of the one hot encoding, you'd need a convolutional autoencoder that uses 1d-convolutions for your 2d-inputs.