Clustering 200k+ observations w/ 100+ dimensions where K clusters is unknown

Question

I have a dataset with over 100 features and 200k observations. My objective is to try and group these observations into clusters as a more meaningful way to understand the interaction between my feature set. Specifically I'm interested in how one specific feature behaves across the different clusters. I don't know how many clusters exist [eliminating a lot of different methods such as K-means, SOM, etc.), therefore it would be preferable to use unsupervised clustering methods but would be open to really any options

I have been playing around with dbscan() from both the ftp and dbscan packages, but am having issues with optimizing the EPS and MinPts parameters [the documentation for both packages only covers 2d data as well]. Are there any other methodologies that have proven successful for handling datasets of this size (which understandably is small by Big Data standards, but seems to overwhelm numerous clustering algorithms)?

Answer 1

There is no free lunch. Yes, with DBSCAN, you do not have to pick the number of clusters, but you must pick EPS and MinPts. Another choice that does not require picking the number of clusters is Mean Shift (either MeanShift or LPCM packages in R). But instead you have to pick the bandwidth parameter. The comments seem to focus on the size of your data, but I read your question as more about selecting a method and setting its parameters.

You started out mentioning K-means. There is lots of help about how to pick the number of clusters. Two good ones are the Wikipedia article on Determining the number of clusters in a data set and an earlier Cross Validated post on How to decide on the correct number of clusters

Another choice that (sort of) needs the number of clusters is hierarchical clustering. For this method, you don't need to choose the number of clusters up front. You build the hierarchy and then can explore it to see where to cut the tree. In the end, you still need to decide how many clusters, but you can get some idea of what that means as you do it. This method may not work so well with a large number of points. It is $O(n^3)$, although you could sample your data to deal with this problem.
References: Wikipedia on Hierarchical Clustering and Stack Overflow Documentation on Hierarchical Clustering in R

As you noted, with DBSCAN, you do not need to choose the number of clusters, but you do need to choose EPS and MinPts. The choices of EPS and MinPts are not independent. They interact. I like to think of MinPts as depending on the problem and then there is a way to pick an appropriate EPS. Whatever value you use for MinPts, any micro-cluster of size less than MinPts will be treated as noise. If you had a small but distinct cluster of 5 points, would you be willing to write it off as noise? You get stuck making the hard choice on MinPts, but once you make that choice, there is some help choosing EPS. At each point, DBSCAN will look at whether or not there are MinPts points within a radius of EPS. You can create the distance matrix for your data and look at the distribution of distances to the $MinPts^{th}$ nearest neighbor. Often there will be good choices that make most points be core points and leave only the most extreme as noise. But DBSCAN has a downside. By picking MinPts and EPS, you are picking a single density for clusters that applies across your data. If you think that your data might have varying density between clusters, this may not work out for you.
DBSCAN References: Wikipedia on DBSCAN and DBSCAN Package in R

Another algorithm for which you do not specify the number of clusters is Mean Shift. You need to pick the bandwidth (the radius away from each point that will be used to estimate density). This does not tie you to a single density for all of the clusters, but you still need to decide the bandwidth - essentially a statement of how far away you need to look to get a decent local density estimate.
Mean Shift References: Wikipedia on Mean Shift and MeanShift package in R

In summary, you always have to specify something that will determine what is a cluster. It might be the number of clusters, some parameters that choose a density, or others, but you end up making choices. Since what you are trying to do is understand your data, I would recommend that you try several methods with various parameter settings and see if they help you converge on an understanding of your data set.

Answer 2

One alternative, if your data is not discrete and reasonably "normally" distributed is to fit a Gaussian Mixture model. In that case, because it is a generative model it will be possible to either do cross-validation or compute things like AIC to determine the optimal number of clusters. Obviously 100 dimensions is quite a bit for GMM, but it may work.