Fast way of detecting outliers in 2D space

Question

I have hundreds of millions of point clouds like the following:

I want to remove outliers 1, 2, 4, 5, 6, 7. The safest bet is to build a minimum spanning tree connecting all the points and remove edges with lengths $>2\sigma$ (2 can be adjusted), but MST takes quadrarithmic time and operationally complex to implement. I tried removing points with distance $>2\sigma$ to the centroid, but it failed identifying 2, 4 and erroneously removed some points at the tip of 3. The sum-of-distances-to-all-other-points method has similar problems. Orthogonalization via PCA also didn't help much. Before committing to MST, is there any established, fast approach to tackle such problems especially in 2D space? The problem seems common in geospatial domain. I am wondering if some kernel trick can be done to project the points into 1D or 3D space, where the outliers can be easily separated?

Answer 1

Using MSTs for detecting outliers sounds cool, but as you mentioned, it could be slow with at least a quadratic time complexity. There are a few other alternatives you could explore: Isolation forests, for example, identify anomalies by isolating data points using random binary trees, with anomalies being more susceptible to isolation due to their rarity and differing patterns. It is relatively faster with linear/log linear implementations.

DBSCAN is another alternative: it works by grouping points that are closely packed together and labelling points in low-density regions as outliers. It is also a relatively faster choice, with a log-linear time complexity.

Answer 2

In 2D, using Euclidean distances, the minimum spanning tree is a subgraph of the Delaunay Triangulation.

You can calculate both of these in O(n log n) time.