How to approach a clustering problem with high cardinality, high number of expected clusters, and high sparsity without dimensionality reduction?

Question

I need to to group n widgets into a unknown number of groups k based on their propensity towards a large number of features.

Here's some things I know:

---

I haven't settled on the sample yet, but n is likely under 50K.

The features being used are large (possibly up to 5K) and represent unique attributes of the widgets. They will have int values of varying magnitudes, but are extremely sparse. That is, if my features are f₁, f₂, ... f_n, it's likely that only a few of them are nonzero (though many may be "approximately" zero). The unfortunate thing is I can't (and I mean really can't) do cardinality reduction on the features. This is because I need to capture those fine differences in groups. Said another way, every group is known to be fairly cleanly separable as it should have its own unique subset of features that are nonzero, and all other features are approximately zero.

I also know (by nature of the problem and previous experience) that k is large (between 100 and 300 likely).

---

On one hand this feels like a clustering problem, but on the other hand, the way in which one would group these could more or less be done by hand if the cardinality wasn't so large. Also the high sparsity makes me think maybe it should be approached differently.

Is using standard clustering algorithms (like k-means) the right approach to this, or is there an even simpler heuristic I can use? And if clustering is right, I know the cardinality and sparsity is a pain, so what are some considerations I can use given that dimensionality reduction won't work for me here?

Answer 1

Note: this is a vague untested idea!

Given your description that each group is very likely to have its own set of features with all the other features close to zero, I would be tempted to try to cluster the features instead of the instances. I'm not sure how, but I would probably start by calculating some kind of association measure between every pair of features, for instance the overlap coefficient or Pointwise Mutual Information, based on how often the two features co-occur (i.e. are both non-zero) across the instances.

Then this association matrix could be used to group features using some simple clustering method, e.g. hierarchical clustering. If the assumption about the sets of features is satisfied, this should directly lead to a clustering of instances, simply by grouping them based on which features are non-zero. This is very likely much more efficient than applying regular clustering on the instances, but how well it would works depends on the data.

Answer 2

Have you considered an SVD-based method? SVD is often associated with dimensionality reduction, which you are trying to avoid, but can also be used as the base of clustering algorithms.

SVD is nice in your case because calculating the SVD of a sparse matrix is a well studied problem and there should be some fairly mature and efficient code in some standard library to help you.

You say "I know the cardinality and sparsity is a pain" but I would suggest that cardinality is the pain and sparsity is a partial salve.

There is a nice paper that looks at relaxing the K-mean clustering problem into something that admits a polynomial-time algorithm (and a good linear approximation algorithm). From the introduction:

There are many notions of similarity and many notions of what a “good” clustering is in the literature. In general, clustering problems turn out to be NP-hard; in some cases, there are polynomial-time approximation algorithms. Our aim here is to deal with very large matrices (with more than 10^5 rows and columns and more than 10^6 non-zero entries), where a polynomial time bound on the algorithm is not useful in practice. Formally, we deal with the case where m and n vary and k (the number of clusters) is fixed; we seek linear time algorithms (with small constants) to cluster such data sets. We will argue that the basic Singular Value Decomposition (SVD) of matrices provides us with an excellent tool.

As with most clustering problems, this assumes that the number of clusters, k, is fixed. Your question mentions "unknown number of groups". You will probably have to fit a model for each value of k and have some way to picking the right number of clusters. Again, SVD might be helpful here because the clusters will be related to the singular values and you might be able to figure something out from the spectrum (list of singular values) of the matrix.

Answer 3

Just wanted to follow up on this with what worked. While I liked Erwan's answers, I couldn't find a good way to truly implement it. Jamie's suggestion of SVD was helpful, but it did smear over groups as I was worried and ultimately more afforded me some computational complexity reduction for early runs, but not the final answer.

Ultimately just using a standard clustering algorithm was effective, but more specifically:

• Aglomerative Clustering - It can reasonably handle a large number of samples as well as a large number of resulting clusters. Additionally it turns out there was a hierarchical structure in my data, which this indeed works well with.
• Cosine Distance - Cosine similarities and distances are well-suited to sparse datasets (after all they're often used on OH-encoded word tokens in NLP problems), so this was versatile to my needs.

So ultimately this did end up being a fairly standard clustering problem and my dimensionality/sparsity wasn't too terrible, though I did have less cardinality than I originally supposed (30K rows, 800 columns).