Clustering very small datasets

I am looking for methods to cluster very small datasets. Almost all methods I have seen talk about how well they work on very large datasets.

By small I am talking 5 elements, 20elements, maybe 50 elements. Particularly focused on 20 elements.

Are there some standard methods I am not seeing?

20 elements is just about small enough that it would be viable to brute force it. It seems like it is certain to be able to use some method based on mixed integer programming.

To give specifics about my particular problem

I have, what I will call "models", and each set of models is about 20 elements. The models are what I want to cluster. I have about 3000 sets of models to cluster, each with about 20 elements. Each model is made up of two things: An ID (which links to other useful information), and a probability function. That probability function takes in some data and tells me how likely, according to this model, that data is.

When using the collection of models, I assess the data with each of the models, and then chose the model that gives the highest probability as one that best fits this particular price of data.

I initially start with a lot of models which are more or less random in their quality, but which are improved by a separate system to get better and better at modeling particular types of data (the type of data which they currently model best). Often the two (or more) models may become good at modelling the same data. So I want to use clustering to throw out duplicated.

So I evaluated over a dataset all the models, and then use the results to determine my distence function between the models.

I am currently investigating measures including Correlation between the sets of probabilities output for same point, and also the "Cost to replace", that is how much the total probability of all the data sets with this model being the best would go down if one of the other models was used instead. If when model $i$ is best, I could instead use model $j$ and not loose much probability, then $i$ and $j$ must be generally pretty similar (I have to make this symmetric by adding the transpose).

I do not have (or rather do not want to use) an a priori data about the likely number of clusters? But given the maximum number of clusers is one per element, with K-* type clustering it really doesn't take too long to evaluate all values of K.

I've been playing around a lot with affinity propagation and k-meniods. Just starting to play with hierarchical clustering now.

• Hierarchical clustering is what performs well for small datsets. Also, plot your data (scatterplots), to see. With few data point it is easy to "cluster" visually without cluster analysis (if euclidean distance is what will suit you). – ttnphns Jun 8 '16 at 9:27
• The clustering problem is NP-hard, which in practice means that no optimal solutions can be found other than by brute force. Hence, all clustering algorithms use heuristics to find a clustering that minimizes the mean square error (MSE). You could use mixed integer linear programming (MILP) to find the clustering that minimizes the MSE (acutally I have found that in some cases MILP solvers are quite fast, i.e., lpsolver). However, in general you want to find a clustering that generalizes your data, not just one the minimizes the MSE. – PolBM Jun 8 '16 at 9:42
• manual clustering won't workout for me. while i only have 20 points in each dataset, I need to cluster like 3000 datasets. (Also I really only know point to point distances, not actual points in a space,) – Lyndon White Jun 8 '16 at 9:44
• Could you give some more information? How large is the feature space? Where do your data come from? Do you have any a priori idea about the likely number of clusters? I personally very much like DBSCAN (available in the fpc R package), which requires some tuning of parameters - but this might be quite feasible for small datasets. – Stephan Kolassa Jun 8 '16 at 9:44
• If you only know pairwise distances, not actual points, then you may want to look at multidimensional scaling (MDS), if only for display purposes. – Stephan Kolassa Jun 8 '16 at 9:46