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

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)?

• How much RAM do you have on your machine? – Jon Jan 19 '17 at 18:57
• I'm working on a distributed Hadoop Cluster. We've got about 450GB available for processing. – Travis Gaddie Jan 19 '17 at 18:59
• For a data set that small, it sounds like over kill. It'd be more efficient to move your data to a laptop/desktop. Given the overhead of hadoop, you'd be more efficient by working on a small data set on a local machine. – Jon Jan 19 '17 at 19:08
• I'm voting to leave open. It isn't clear that this question is asking for code. It asks for "other methodologies ... for handling datasets of this size". It is generally known that many clustering algorithms are too slow as N or p gets large. – gung - Reinstate Monica Jan 19 '17 at 21:34
• You might try various ways to reduce the size of your dataset to make it more manageable, play w/ the possibilities you have in mind, & try scaling it up when you've settled on what you like. You could start by making some random partitions & set all but 1 aside. Then you could try variable reduction w/ something like PCA. Etc. You don't want to pare it down to the point where it is no longer representative, but you might succeed in making it manageable. – gung - Reinstate Monica Jan 19 '17 at 21:53

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.

• +1. I generally prefer DBSCAN to $k$-something approaches because it really forces people to think about their data and the data's internal structure. The basic advantage with $k$-something is that you want (or even more strongly, know that exist) $k$ clusters in your data and you want to retrieve them. – usεr11852 Jan 19 '17 at 22:11
• Let's see what MeanShift has in store for me! – Travis Gaddie Jan 20 '17 at 15:44

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.