How to specify K cluster in Hierarchical clustering with noisy data?

Question

I'm new in Mining and Clustering and I wonder how to cut off the hierarchical clustering Dendrogram to obtain a specific number of clusters. The problem is here that the data is noisy and the SLINK algorithm consider these noises as a cluster and when I cut off the Dendrogram to obtain exactly K cluster, it gives me some noisy cluster and so ignores all or some of K expected clusters. So I think there should be some techniques to cut the Dendrogram without considering the noisy clusters.

Note that I know the number of K and it's not a problem how to specify this number!

Thanks.

Answer 1

You do not specify what a "noisy cluster" is, but it seems that your problem is to partition the data into $K$ clusters plus another cluster consisting of noise, which is randoomly distributed and thus not correctly detected by any clustering algorithm looking for dense and coherent clusters.

I can think of two different approaches that you can try:

1. As you have a distance measure for your data points, you can try to remove the noise before clustering by an outlier detection algorithm. A simple method would by to set a threshold on the average kNN distance and remove points above it. See, e.g., section 5 (distance rejection) in

Dalitz: "Reject Options and Confidence Measures for kNN Classifiers." In "Document Image Analysis with the Gamera Framework." Schriftenreihe des Fachbereichs Elektrotechnik und Informatik, Hochschule Niederrhein, vol. 8, pp. 16-38, Shaker Verlag (2009)

2. Incidentally, I had a very similar problem a few years ago. The only difference was that the number of clusters was not known beforehand, but noise was a problem too, resulting in many meaningless cluster. We have solved the problem by simply removing clusters with a size below some threshold (the size was not merely the number of data points, which made the method somewaht more robust, but this should not be a principal problem). In your case, you would need to try it iteratively by increasing the number $K$, removing noise clusters, inclreasing $K$ again, until you arrive at the remaining predefined number of clusters. The entire algorithm based on single link hierarchical clustering is described in the following article (the URL also points to a reference implementation and online demo):

Dalitz, Wilberg, Aymans: "TriplClust: An Algorithm for Curve Detection in 3D Point Clouds." Image Processing On Line 9, pp. 26-46 (2019)

Answer 2

Choose the height h such that there are k non-trivial (non noise) clusters.

Then cut the tree at this height.

Note that this may not be satisfiable. If your data is a single gaussian, it may not be possible to find k non-trivial clusters.