Clustering users with very sparse data

Question

I have a dataframe of the form

| user_ID | cat1 | cat2 | ..... |cat 2125 |
   234       1.0    0.0            0.0
   125       0.0    1.0            0.0
   542       0.0    1.0            1.0
...

This dataset represents user votes on 2125 books. Each category column stands for one book. It contains either a 1.0, for a vote given by that user or a 0.0, for no vote.

I want to cluster these users by the books they voted for. I realize I first need to reduce dimensionality. I tried PCA and TruncatedSVD, with k-Means clustering afterwards. In both cases, the clusters I get are irrelevant (users usually have no books in common).

My only constraint here is that i must use k-Means (since I need the coordinates of the centroids). I suspect that my dimensionality reduction is not good though.

Can someone please offer some advice as to what I should do?

Answer 1

My first recommendation would be to compute a Jaccard distance between any two users. The Jaccard distance treats 1 and 0 asymmetrically; a joint 1 is important, a joint 0 is not important, so this will not be dominated by "joint zeroes". Note that the linked Wikipedia page defines a Jaccard similarity, a distance can be obtained by computing one minus the similarity (but clustering methods are normally implemented to operate on distances, not similarities).

Data can then be clustered using the Partitioning Around Medoids method, (pam in R) that also delivers centroids.

This may be computationally problematic if your number of users is large, as then storing all distances requires huge memory. A not necessarily optimal possibility is to cluster a random subset of the users and to assign all the others by distance to their closest centroid.

Note that this approach does not involve dimension reduction, although data can be visualised on low dimensions using Multidimensional Scaling.

Answer 2

I am no expert, but in this situation, I'd might try other dimensionality reduction techniques if those previous ones did not work.

There are methods such as KernelPCA, using different kernels, with which you can even construct your own. There are other dimensionality reduction techniques - this link https://towardsdatascience.com/dimensionality-reduction-for-machine-learning-80a46c2ebb7e might give you a start.

Did you plot them up in 2-3 dimensions? If you plot up several different techniques, you can see which dimensionality reduction technique might be the most suitable for obtaining your clusters - this assumes that your dataset is not too big. You could possibly go up to 4 dimensions by using a colour scheme for the 4th dimension. Although 2-4 dimensions might not capture enough variance, you often do not want to go into a high space of dimensions with k-means as it suffers from Curse of Dimensionality. Check how much variance you capture and pick a suitable number, but I would definitely not try and cluster in 2125 dimensions.