# Solve tough clustering problem with overlapping clusters

I'm having some trouble to solve a hard clustering problem.

I have a 2D dataset characterized by non spherical and partially overlaping clusters with different densities. I've read a lot about clustering methods and for this type of data DBSCAN, Optics and other stuff wouldn't work very well. I think fuzzy clustering with mahalanobis inducing norm is a good choice.

I've coded fuzzy c-means, k-means++ initialization, gustafson-kessel and gath-geva clustering methods but none of then can really separate the data. They are working really well for non overlapping clusters. I also know that the problem is not the initialization, because even if I manually initialize the prototypes where I want, the algorithms converge to points that are not well separating the data.

Typically I'm running kmeans++ and fcm to initialize the fuzzy partition and than I run gustafson-kessel or gath-geva

Also, tried different data normalization, like normalization by variance, by range, zscore, pca. None of this helps.

Here is the data:

Here is the typical result of gustafson-kessel and gath-geva

The desired result would be some thing like this: ( i know that because these groups represent different physical processes and we can realize that by eye)

Can someone help me with this please? The data is attached here data.

The Problem is that many clustering algorithms focus on distances (between points, clusters and so on). Especially at the connection between the two desired clusters, distances between points are small. There is little to know clue from these distances that there should be a change in clusters.

But we why can see the two clusters?

1. There is a change in density at the connection point between the desired clusters.
2. The clusters resemble comets with their tails and the human eye focuses on such patterns.

Based on this, I see 3 promissing approaches:

##### 1. Classification

Why do you need to use an unsupervised method? You seem to know - at least for some points - that they come from different processes. You could annotate the data with this information and train a classifier.

##### 2. Segmentation

Transform the data into a density map or image. This could then be considered a grayscale image where segmentation algorithms could be used to separate areas of different densities. Especially the boarder between the two clusters should be detected by such segmentation.

Possible approaches might be graph cut our watershed algorithms, to start with some basic ones.

##### 3. Customized density-based clustering

Gaussian Mixture Models are made to detect Gaussian Distributions even if they are partially overlapping. These would be of elliptic shape with the high-dense region in the center. You could try these but probably the asymmetry of your clusters could cause some problems.

So you could find a distribution with a one-sided tail that describes the shape of your data in a better way. Using this distribution you would have to modify the mixtrue models likelihood function to create a variant especially suitable for your case.

Note: I put this option intentionally at the end, because it is no off-the-shelf algorithm. It is up to you whether this would be worth the work.

• Hi @Broele thank you for your comments. I totally agree with you but my application involves some variability that makes options 1 and 2 not so suitable. In fact, this data come from field measurements and I can get very different behaviors like well spaced and defined clusters and some times this kind of overlapping clusters. This case is problematic. Sometimes the densities are almost the same, sometimes they are very different. I think the third option you gave is promising. Maybe I could modify the data scale to make densities comparable and then perform the clustering. Sep 13, 2023 at 14:39
• I hope it works - it sounds like a challenging task. Since I don't know the other cases, I can just guess a bit. If the two clusters are of similar shape like in this case, a mixture of distributions might possible work. Note that it will not be able to map a point in an overlapping area to exactly one cluster, but it will give you probabilities for the clusters. Sep 14, 2023 at 20:43