0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It looks a bit like a kind of optimization problem. Maybe a genetic algorithm would work? $\endgroup$ – Erwan Jun 19 '19 at 14:34
  • $\begingroup$ 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? $\endgroup$ – knb Jun 19 '19 at 19:54
  • $\begingroup$ @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). $\endgroup$ – couturierc Jun 20 '19 at 8:56
  • $\begingroup$ 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? $\endgroup$ – knb Jun 20 '19 at 9:25
  • $\begingroup$ @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. $\endgroup$ – couturierc Jun 20 '19 at 9:42
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – couturierc Jun 19 '19 at 14:11
  • $\begingroup$ Well, that suffers from the same problem, doesn't it? $\endgroup$ – Has QUIT--Anony-Mousse Jun 20 '19 at 1:56
  • $\begingroup$ 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. [...] $\endgroup$ – couturierc Jun 20 '19 at 9:36
  • $\begingroup$ [...] 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). $\endgroup$ – couturierc Jun 20 '19 at 9:37
  • $\begingroup$ 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. $\endgroup$ – Has QUIT--Anony-Mousse Jun 20 '19 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.