CODEWITHSUNDEEP
algorithmcluster-analysisoutliersminimum-spanning-tree
user2961927
user2961927

Reputation: 1728

Fast way of detecting outliers in 2D space

I have hundreds of millions of point clouds like the following: enter image description here

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?

Upvotes: 3

Views: 163

Answers (3)

TheGoat
TheGoat

Reputation: 2877

Have you looked at the isolation forest algorithm, this should work perfectly in the 2D space but also in a milti-dimensional space

Upvotes: 1

Matt Timmermans
Matt Timmermans

Reputation: 59303

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.

Upvotes: 1

Naman Agrawal
Naman Agrawal

Reputation: 76

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.

Upvotes: 3

Related Questions