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.
$\begingroup$
$\endgroup$
asked Oct 20, 2016 at 13:51
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
10
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:
- Partitioning algorithms (like k-means and it's progeny)
- Hierarchical clustering (as @Tim describes)
- Density based clustering (such as DBSCAN)
- 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)
answered Oct 20, 2016 at 14:17
-
$\begingroup$ 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? $\endgroup$– amoebaOct 23, 2016 at 23:54
-
$\begingroup$ @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. $\endgroup$ Oct 24, 2016 at 0:02
-
$\begingroup$ 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. $\endgroup$– amoebaOct 24, 2016 at 13:14
-
$\begingroup$ 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. $\endgroup$ Oct 24, 2016 at 14:55
-
1$\begingroup$ @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
Mclustuses 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. $\endgroup$ Oct 24, 2016 at 16:50
$\begingroup$
$\endgroup$
3
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.
(source: https://en.wikipedia.org/wiki/Hierarchical_clustering)
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.
-
$\begingroup$ Isn't pruning somehow means that you are deciding on cluster number? $\endgroup$ Oct 20, 2016 at 16:34
-
1$\begingroup$ @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. $\endgroup$– Tim ♦Oct 20, 2016 at 16:39
-
1$\begingroup$ 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. $\endgroup$ Oct 20, 2016 at 21:00
$\begingroup$
$\endgroup$
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.
answered Oct 21, 2016 at 6:36
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ Dirichlet processes (and their generalization Pitman-Yor processes) are reasonable approaches to clustering that don't require specifying the number of clusters in advance. However, keep in mind that Dirichlet and Pitman-Yor processes are not consistent estimators of the number of clusters: jmlr.org/papers/volume15/miller14a/miller14a.pdf $\endgroup$– jkpateSep 15, 2020 at 8:44
$\begingroup$
$\endgroup$
1
If you want to compute the number of clusters only from the input data, for numerical variables you may look at MCG, a hierarchical clustering method with an automatic stop criterion: see the free seminar paper at https://hal.archives-ouvertes.fr/hal-02124947/document (contains bibliographic references); the input data is either the array of coordinates of the N data points, or an N by N array of distances between the N items (the distances are not required to be Euclidean ones).
If you are working on categorical variables, you may look at POP (optimal partitioning); the method is presented in the same seminar paper; it operates either on categorical variables or on an N by N array of signed dissimilarities (the main cited paper was published in 2002: free copy at https://hal.archives-ouvertes.fr/hal-02123085/document).
There are free binaries for MCG and POP (at least for linux). Indeed the two methods are explained (with examples) in English in the seminar paper.
-
$\begingroup$ Thanks for the answer. It would help if you described the methods a bit further, because the first document you linked is just a presentation and the second is in French. $\endgroup$– Fato39Sep 15, 2020 at 9:37