Clustering data with covariance for each point

Question

I am looking to cluster data points that each have a covariance around itself (based on some function of its neighbourhood, but how I got it is not important). I would like to use the covariance to achieve these properties:

• points with relatively high covariances should be "weighted" less for partitioning based algorithms like kmeans because it represents the point's unreliability
• distance to other points should be closer if their difference is along the direction of high variance for both points

Most clustering algorithms need a metric on the points, so I am considering these:

• Wasserstein/earth mover distance
• Bhattacharyya distance
• Hellinger distance

In all cases to compute the distance in closed form, I'm assuming each data point is a Gaussian (the mean is the point value, and the Gaussian covariance is the covariance for that point).

Unfortunately I lack a statistics background, so I would appreciate an analysis of the differences between them and which one might be best suited for my use!

Some properties of the data that I'm clustering:

• N = number of data points ranges up to 10000
• d = dimension of each point ranges up to 100 (working for more would be desirable)
• may have significant noise
• is somewhat globularly distributed
• clusters may have very different sizes (# elements)

I only have 32GB RAM, and to scale to higher dimensions I think I would have to use the variance rather than covariance (assume axis aligned variation to cut down parameters from $O(d^2)$ to just $O(d)$).

A simplified example of what I'm clustering projected down to 2 dimensions:

The blue dots are the data points and the red ellipses are the covariances for each data point. This data is projected down from some higher dimension, and the hatched region represents where the data points would have very different values along the other dimensions.

We see that the covariances tend to stretch tangentially to the donut, so given the same euclidean distance between two points, they should be considered closer if they lie tangentially to the donut than if they lie radially.

I am currently clustering with a modified kmeans such that I'm measuring the distance to each mean as $$d(x_i,\mu_j)^2 = (x_i-\mu_j)^T\Sigma_i^{-1}(x_i-\mu_j)$$ This is working out somewhat well so far because of the globular nature of the data, but it doesn't handle imbalanced clusters and I would like to shift the hyperparameter from the number of clusters k to something more intuitive.

I think HDBSCAN is the best clustering algorithm for my needs. The built-in metrics are:

==============  ====================  ========  ===============================
identifier      class name            args      distance function
--------------  --------------------  --------  -------------------------------
"euclidean"     EuclideanDistance     -         ``sqrt(sum((x - y)^2))``
"manhattan"     ManhattanDistance     -         ``sum(|x - y|)``
"chebyshev"     ChebyshevDistance     -         ``sum(max(|x - y|))``
"minkowski"     MinkowskiDistance     p         ``sum(|x - y|^p)^(1/p)``
"wminkowski"    WMinkowskiDistance    p, w      ``sum(w * |x - y|^p)^(1/p)``
"seuclidean"    SEuclideanDistance    V         ``sqrt(sum((x - y)^2 / V))``
"mahalanobis"   MahalanobisDistance   V or VI   ``sqrt((x - y)' V^-1 (x - y))``
==============  ====================  ========  ===============================

It also allows for a custom function taking in 2 1-D vectors. My current idea is to squash the covariance into a 1-D vector with the data, then unsquash and calculate the metric using one of the metrics above. Is there a better way of doing this?

TL;DR summary:

• I have data points that each have a covariance
• I want a metric over the points that uses this covariance to achieve certain properties
• what's the best metric to achieve those properties?
• how do I perform HDBSCAN using that metric?
• is there a more suitable clustering algorithm for my data than HDBSCAN?

Answer 1

1. There are special clustering algorithms for uncertain data, where some information on this uncertainty is known. But if I recall correctly it has been shown that usually, using the mean of this uncertainty region is as good as more complex models. So I found that rather disappointing.

2. There are DBSCAN based algorithms (maybe it was "FourC"? Check the DBSCAN authors later research!) That employ covariance-based contexts around data points to cluster in an "oriented" fashion. I think they used the covariance of the neighborhood, but you can probably just use your covariance instead.