Clustering with custom criterion (minimum cluster weight)

Edit: following comment from @anony-mousse, I'm changing the question to search for a general clustering approach that matches this criterion (minimum weight per cluster).

I am to use a clustering method on a set of $$n$$ weighted points:

---------------------------------------------
| id  | weight | feature_1| feature_2 | ... |
---------------------------------------------
| 1   | 4      | 0.2345   | -0.2345   | ... |
| 2   | 2      | 0.675    | 0.7433    | ... |
| 3   | 15     | -0.45    | 0.123     | ... |
| ... | ...    | ...      | ...       | ... |
---------------------------------------------


I have a custom criterion: some algorithms make sure there is a minimum number of points $$n_{min}$$ per cluster ; here I would like to make sure each cluster has a minimum weight (sum of point weights) $$\sum w_i > s_{min}$$.

Is there such a clustering method already implemented in Python?

• It looks a bit like a kind of optimization problem. Maybe a genetic algorithm would work? Commented Jun 19, 2019 at 14:34
• Do you want "a" set of such clusters, or do you want a "best" set of clusters? If you want a best set, what is best? As close to $s$ as possible?
– knb
Commented Jun 19, 2019 at 19:54
• @knb I would like a "best" set of clusters, that minimizes the variance in each cluster (or minimizes the intra-cluster distance), given that constraint (minimum weight per cluster). Whether or not the cluster weight is closest to $s$ is secondary (but might be achieved by the "minimize variance" objective, as "as close as $s$ as possible" ~ "smallest clusters" ~ "more granular" --> possibly lower variance). Commented Jun 20, 2019 at 8:56
• Please update your Q once more with that response, also: what distance measure, how big could n be typically. Maybe post to SE sites puzzles, mathoverflow?
– knb
Commented Jun 20, 2019 at 9:25
• @knb minimizing the variance in each cluster (or minimizing the intra-cluster distance) is not really specific to this question, it's a pretty general objective for clustering methods, so I probably should keep the question around the specific (additional) constraint. Commented Jun 20, 2019 at 9:42

1 Answer

This does not work, and it's not how hierarchical clustering works.

If you stop at $$n_\min$$, no cluster will be larger than $$2n_\min-2$$ but there will either be plenty of badly clustered points, or unclustered points.

Consider the data set 0 2 3 5 with nmin=2. The first merge is (2,3) and fulfills the stopping criterion. So either you cluster this as (0), (2,3), (5) or as (0,5), (2,3) neither of which is convincing: either nmin is not a minimum size, or the clusters can be arbitrarily bad (and still may be below the minimum size).

The same concern applies to a weighted version.

• Thanks for your point. Your example indeed highlights the problem of unclustered points. I thought this could be added as a criterion a each node of the dendrogram (I possibly had also hDBSCAN -- hierarchical DBSCAN -- in mind for the minPoints criterion). So instead, I'm looking for a clustering approach to enforce a minimum weight per cluster. Commented Jun 19, 2019 at 14:11
• Well, that suffers from the same problem, doesn't it? Commented Jun 20, 2019 at 1:56
• Well, tackling outliers/noise is a general trade-off for clustering: as you said, clusters can be arbitrarily bad (if we try to cluster all points, even if they don't really belong to a cluster), or some points may not get associated to a cluster. [...] Commented Jun 20, 2019 at 9:36
• [...] An example of a clustering method that enforces a minimum number of points per cluster (minimal cluster size) is DBSCAN (and the modified HDBSCAN): hdbscan.readthedocs.io/en/latest/… ; they indeed leave the outliers alone (grey points in the exemples in this link). They can still be associated to a cluster with an additional step (associating each lone point to the nearest cluster). Commented Jun 20, 2019 at 9:37
• The HDBSCAN authors have proposed a number of ways to extract clusters, you may want to read their papers. If you are okay with having outliers, enforcing a nmin is possible. But if you do this bottom up an stop when reaching nmin, you will not find much larger clusters either. Using a minimum size as stopping criterion in a bottom up process doesn't work well. Commented Jun 20, 2019 at 14:14