# Clustering of very high dimensional data and large number of examples without losing info in dimensions

I'm trying to get a grasp on scalability of clustering algorithms, and have a toy example in mind. Let's say I have around a million or so songs from $$50$$ genres. Each song has characteristics - some of which are common across all or most genres, some of which are common to only a few genres and some of which are genre-specific.

Common attributes could be something like song duration, artist, label, year, album, key, etc. Genre-specific attributes could be like lead guitarist, trombone player, conductor, movie name (in case of movie soundtracks), etc. Assume that there are, say, $$2000$$ attributes across all possible genres.

The aim is to identify attributes that characterize subgenres of these genres. So of course, let's say for rock I can just collect all the attributes for all rock songs, but even that set of attributes may be too broad to characterize the rock genre - maybe there are some that are specific to subgenres and so I won't have the desired level of granularity.

Note that for the purpose of this example, I'm not assuming that I already know the subgenres a priori. For example, I'm not going to categorize songs into subgenres like post rock, folk rock, etc. and then pick out attributes characterizing them. I want to discover subgenres on the basis of clustering, if that makes sense.

In a nutshell, about a million songs belonging to $$50$$ genres and all songs collectively have $$2000$$ attributes. So for each song I'll make a vector in $$\mathbb{R}^{2000}$$ - each dimension corresponds to an attribute. If that attribute is present for that song, the corresponding element of the vector is $$1$$, otherwise $$0$$ (e.g. a jazz-related attribute will be $$0$$ for a rock song). Now I want to do genre-wise clustering. For each genre, not only do I want to cluster songs of that genre into groups, but I also want to get an idea which attributes are the most important to characterize individual groups.

On the basis of this clustering, I can identify subgenres (e.g. of rock music) that I can characterize using a subset of the $$2000$$ attributes.

My first question is: is there a better way to initialize the problem than forming 2000-dimensional vectors of ones and zeros?

Secondly, given the vast number of dimensions and examples, what clustering methods could be tried? From what I've surveyed, there are graph-based clustering methods, hierarchical, density-based, spectral clustering and so on. Which of these would be best for the toy example? I've heard that one can project the points on to a lower-dimensional subspace, then do clustering. But I also want which attributes define different clusters. Since attributes are encoded in the dimensions, with dimensionality reduction techniques I'll lose information about the attributes. So now what?

• The problem is that you'll either get trivial results - split the data set on the attribute with the highest variance - or pretty much random results. It's not so much a matter of choosing the right algorithm - it is an I'll defined problem on such data. Literally any solution is as good as any other solution. It does not matter. Why is splitting on key better than on the first letter of the lead singers name? What about the second letter? Can you provide a mathematical definition of a "cluster" that proves splitting on the second letter of the name is worse? – Anony-Mousse Sep 16 at 19:18
• @Anony-Mousse : So let's say I intend to use clusters as a proxy for similarity of songs, instead of worrying about which attributes characterize clusters. In other words, songs belonging to the same cluster are deemed similar. Is the paradigm described in the question appropriate for this new objective or is it still an ill defined problem? Does using or not using dimensionality reduction make any difference? – Shirish Kulhari Sep 16 at 19:28
• No, dimensionality reduction completely suffers from the same problem: all these attributes mathematically have no "correct" similarity. Everything is just a big hack, and every different hack to get some similarity score or projection is equally good or bad. There is a chance that songs with more attributes in common are perceived more similar by humans. Or not. Which attributes matter more, which don't? Does the second letter of the artists first name indicate similarity? (Probably yes, as all songs of the same artist tend to be more similar than those of other artists!) – Anony-Mousse Sep 16 at 22:01