# Determine if a cluster has to be divided to 2 mini-clusters

I have a dataset containing clusters of points (x,y). Those clusters are given and I can't change them.
Some of those clusters have 2 "mini clusters" in them - so I need to do some clustering on the large cluster, in order to receive fixed 2 mini clusters.
How can I know which clusters should I keep as-is and which clusters to split?

• Ultimately the data can't decide themselves whether clusters should be split or not, and no automatic method can do that. This depends on what the clusters are used for and what meaning a "clustering" is supposed to have in the application at hand, particularly how much within-cluster heterogeneity can be tolerated. The data can't know that on their own. The answer of cdalitz correctly points to some existing methods, but often different methods give different results (sometimes dependent on tuning), and the issue can't be settled by just trusting the one somebody likes best. – Lewian Feb 1 at 13:54
• Can you explain what the background is and what these clusters will be used for? – Lewian Feb 1 at 13:55

There are two possible approaches:

1. Use a clustering algorithm that automatically figures out the number of clusters, like removing inconsistent edges in the Euclidean Minimum Spanning Tree. An edge $$e$$ is "inconsistent", if its weight $$w_e$$ is greater than $$\mu_e + q\cdot\sigma_e$$, where $$\mu_e$$ and $$\sigma_e$$ are mean and standard deviation, respectively, of the edges that are at most $$k$$ steps afar from $$e$$. $$q$$ and $$k$$ are tweakable parameters.

2. Try out a clustering algorithm that requires a fixed number of clusters (like K-Means) and test the result with some "internal" clustering index. If you are looking for approximate circular clusters, the Calinski-Harabasz index might be a good choice.

To find review articles about cluster indices that address this problem, do a literature search for "internal cluster validation". Here are some starting points:

Overview over different internal indices:
Arbelaitz, Olatz, et al.: "An extensive comparative study of cluster validity indices." Pattern Recognition 46.1 (2013): 243-256.

An older study based on Monte Carlo simulations:
Milligan, Cooper: "An examination of procedures for determining the number of clusters in a data set." Psychometrika 50 (1985): 159-179

A recent suggestion, specifically suited for non-circular clusters:
Rojas-Thomas, et al.: "New internal index for clustering validation based on graphs." Expert Systems with Applications 86 (2017): 334-349.

• Thank you for your answer. Can you elaborate more on the first method? and for the second - if I'm not mistaken, Calinski-Harabasz index values are received for 2+ clusters only. So I can not create 2 mini clusters and test it against the large single cluster. – Dave Jan 30 at 13:15
• I have edited the answer to include the precise rule for identifying inconsistent edges (I cannot remember where I read it,, presumably the textbooks by Theodoridis or Webb). Concerning Calinski-Harabasz: yes you are right, due to the division by $K-1$ you can only identify clusters that are to be split up into three or more parts, but there are many other internal indices. – cdalitz Jan 30 at 13:41
• Thank you for the clarification at #1, well understood. #2 - Can you maybe point out some internal indices that fit the problem (circular clusters, only 1 or 2 clusters, and no GT)? I've searched a bit and couldn't found such who answer with 1 cluster only. For example, [scikit-learn.org/stable/modules/… doesn't contain any methods that will fit. – Dave Jan 30 at 13:46
• @Dave I have just added some literature suggestions. Note that cluster validation is a difficult subject, worth many doctoral theses.... – cdalitz Feb 1 at 10:25