Clustering methods that do not require pre-specifying the number of clusters

Are there any "non-parametric" clustering methods for which we don't need to specify the number of clusters? And other parameters like the number of points per cluster, etc.

Clustering algorithms that require you to pre-specify the number of clusters are a small minority. There are a huge number of algorithms that don't. They are hard to summarize; it's a bit like asking for a description of any organisms that aren't cats.

Clustering algorithms are often categorized into broad kingdoms:

1. Partitioning algorithms (like k-means and it's progeny)
2. Hierarchical clustering (as @Tim describes)
3. Density based clustering (such as DBSCAN)
4. Model based clustering (e.g., finite Gaussian mixture models, or Latent Class Analysis)

There can be additional categories, and people can disagree with these categories and which algorithms go in which category, because this is heuristic. Nevertheless, something like this scheme is common. Working from this, it is primarily only the partitioning methods (1) that require pre-specification of the number of clusters to find. What other information needs to be pre-specified (e.g., the number of points per cluster), and whether it seems reasonable to call various algorithms 'nonparametric', is likewise highly variable and hard to summarize.

Hierarchical clustering does not require you to pre-specify the number of clusters, the way that k-means does, but you do select a number of clusters from your output. On the other hand, DBSCAN doesn't require either (but it does require specification of a minimum number of points for a 'neighborhood'—although there are defaults, so in some sense you could skip specifying that—which does put a floor on the number of patterns in a cluster). GMM doesn't even require any of those three, but does require parametric assumptions about the data generating process. As far as I know, there is no clustering algorithm that never requires you to specify a number of clusters, a minimum number of data per cluster, or any pattern / arrangement of data within clusters. I don't see how there could be.

It might help you to read an overview of different types of clustering algorithms. The following might be a place to start:

• Berkhin, P. "Survey of Clustering Data Mining Techniques" (pdf)
• I am confused by your #4: I thought if one fits a Gaussian mixture model to the data then one needs to choose the number of Gaussians to fit, i.e. the number of clusters has to be specified in advance. If so, why do you say that "primarily only" #1 requires this? – amoeba Oct 23 '16 at 23:54
• @amoeba, it depends on the model based method & how it's implemented. GMMs are often fit to minimize some criterion (as, eg, OLS regression is, cf here). If so, you do not pre-specify the number of clusters. Even if you do according to some other implementation, it isn't a typical feature for model based methods. – gung Oct 24 '16 at 0:02
• What you did in the linked answer (or perhaps what the corresponding R function did for you) is probably to fit GMMs with 1, 2, 3, 4, etc. clusters, to compare the resulting BICs, and to choose the "optimal" one, yielding $k=3$. I would still describe it as pre-specifying the number of clusters and using some additional general heuristic to choose the best fitting model, but I can see that an argument can be made in favour of saying that, overall, $k$ does not need to be pre-specified. However, can't one use BIC with k-means too? If so, then k-means and GMM appear to be in the same boat. – amoeba Oct 24 '16 at 13:14
• I don't really follow your argument here, @amoeba. When you fit a simple regression model w/ the OLS algorithm, would you say that you are pre-specifying the slope & intercept, or that the algorithm specifies them by optimizing a criterion? If the latter, I don't see what's different here. It is certainly true that you could create a new meta-algorithm that uses k-means as one of its steps to find a partition w/o pre-specifying k, but that meta-algorithm would not be k-means. – gung Oct 24 '16 at 14:55
• @amoeba, this does seem to be a semantic issue, but the standard algorithms used to fit a GMM typically optimize a criterion. Eg, the one Mclust uses is designed to optimize the BIC, but the AIC could be used or a sequence of likelihood ratio tests. I guess you could call it a meta-algorithm, b/c it has constituent steps (eg, EM), but that is the algorithm you use, & at any rate it does not require you to pre-specify k. You can clearly see in my linked example that I did not pre-specify k there. – gung Oct 24 '16 at 16:50

The most simple example is hierarchical clustering, where you compare each point with each other point using some distance measure, and then join together the pair that has the smallest distance to create joined pseudo-point (e.g. b and c makes bc as on the image below). Next you repeat the procedure by joining the points, and pseudo-points, based their pairwise distances until each point is joined with the graph. The procedure is non-parametric and the only thing that you need for it is the distance measure. In the end you need to decide how to prune the tree-graph created using this procedure, so a decision about expected number of clusters needs to be made.

• Isn't pruning somehow means that you are deciding on cluster number? – Learn_and_Share Oct 20 '16 at 16:34
• @MedNait that is what I said. In cluster analysis you always have to make such decision, the only question is how is it made -- e.g. it could be arbitrary, or it could be based on some reasonable criterion like likelihood-based model fit etc. – Tim Oct 20 '16 at 16:39
• It depends on what exactly you are after, @MedNait. Hierarchical clustering does not require you to pre-specify the number of clusters, the way that k-means does, but you are selecting a number of clusters from your output. On the other hand, DBSCAN doesn't require either (but it does require specification of a minimum number of points for a 'neighborhood'--although there are defaults--which does put a floor on the number of patterns in a cluster). GMM doesn't even require that, but does require parametric assumptions about the data generating process. Etc. – gung Oct 20 '16 at 21:00

Parameters are good!

A "parameter-free" method means that you only get a single shot (except for maybe randomness), with no customization possibilities.

Now clustering is a explorative technique. You must not assume there is a single "true" clustering. You should rather be interested in exploring different clusterings of the same data to learn more about it. Treating clustering as a black box never works well.

For example, you want to be able to customize the distance function used depending on your data (this is also a parameter!) If the result is too coarse, you want to be able to get a finer result, or if it is too fine, get a coarser version of it.

The best methods often are those that let you navigate the result well, such as the dendrogram in hierarchical clustering. You can then explore substructures easily.

Check out Dirichlet mixture models. They're provide a good way of making sense of the data if you don't know the number of clusters beforehand. However, they do make assumptions about the shapes of clusters, which your data might violate.