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:
- 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)
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.
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.
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.