1
$\begingroup$

Context --

Unlike, Partitional clustering algorithms like K-Means, Spectral or Hierarchal Methods, Incomplete clustering techniques like DBSCAN, HDBSCAN and many others have the notion of noise (outliers).

Common cluster validation (Internal and External) indices - Silhouette Index, C-Index, Dunn Index, Entropy, Within-cluster scatter ... don't explicitly accommodate noise.

Questions --

  1. Do there exist special Cluster Validation indices that accommodate noise?
  2. What would be the appropriate treatment of noise, so that they fit well into all cluster indices ?

The cluster validation should reflect the loss of cluster-ability due to excessive noise.

Some thoughts --

  1. Treat the noise as a new (k+1 th) partition.
  2. Remove all noises from the picture (Not recommended)
  3. Re-assign noises into one of the existing clusters (by nearest neighbor technique or using some cluster indices)

Please feel free to put forward your suggestions and links to related research materials and posts.

Edit : Let's assume a two class problem.

$\endgroup$
  • 1
    $\begingroup$ DBSCAN explicitly computes outliers clusterwise. Therefore (1) treat noise as a new partition is not a good idea. Further if you (3) reassign the noise into the existing (nearest) cluster, you can directly use clustering algorithms which do not detect/consider outliers. Finally (2) remove outliers before evaluation sounds most reasonable. Who does not recommend it and why? If possible, provide a reference. $\endgroup$ – Nikolas Rieble Jul 14 '17 at 13:17
  • 1
    $\begingroup$ @NikolasRieble -- Noise (Outlier) are inevitably a part of all real datasets. Removing noise (esp. in large number) from the picture, give a false sense of clusterability. $\endgroup$ – R Mukesh Jul 15 '17 at 10:47
  • $\begingroup$ @NikolasRieble -- Our guide, demands that the effect of noise be evident in the cluster indices (Even if the indices be goofed up - indicating poor clusterability due to excessive noise). Even sklearn's default API calls of Silhouette Score and Adjusted Rand Index treat noise (indicated by a label '-1') as a separate partition -- not sure if it was a conscious decision or an unintended mistake. $\endgroup$ – R Mukesh Jul 15 '17 at 10:58
  • $\begingroup$ I think Nikolas' suggestions are quite reasonable (+1). It does not make sense to compute a "goodness-of-fit" metric on points you explicitly categorise as noise. Think about it: eg. in a regression setting we predict people's height and there is a corrupted/noise data-point of someone being 4.5m tall. We would not take into account that point when saying how good our predictions are, it s nonsensical, nobody is 4.5m! $\endgroup$ – usεr11852 Jul 15 '17 at 12:20
  • $\begingroup$ Actually Silhouette does specify how to handle noise: it has a silhouette of 0 for "singleton" objects. In many cases that will be the proper approach: treat these points as one-element clusters each. $\endgroup$ – Anony-Mousse Jul 16 '17 at 8:07
1
$\begingroup$

There exist different ways of handling noise. If I recall correctly, this is discussed in the DBCV paper (density-based cluster validation). The ELKI clustering toolkit has an option of how to handle noise clusters during evaluation.

I am not convinced by these measures. I believe that with a trivial postprocessing you can "optimize" your clustering for most metrics (e.g. assigning noise to their nearest cluster will improve silhouette) without theoretical support or any practical usefulness.

In my opinion,clustering needs to be treated as an explorative technique: it does not matter if it can improve some useless statistical score. The only thing that matters is, if it allows a human to better understand data.

$\endgroup$

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.