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 f1, f2, ... fn, 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?