Identify lat long points falling out of cluster

Question

Problem Statement

I have a set of lat-long locations, say 30 in number. Ideally they should be just a few meters from each other on ground. But sometimes there's that odd junk data point that's 20kms away or so, which messes up the whole cluster. I want to programmatically identify these "odd ones out". What would be a good way of going about this? Will mention here: I have to repeat this thousands of times, so seeking a programmed way.

Strategies coming to mind

• Use Sklearn package's AgglomerativeClustering as done in the Kaggle example below.
• Draw distance buffers and dissolve, then find largest polygon and all points outside of it, based on PyQGIS answer linked below.
• Convert lat-longs to OpenLocationCode / plus.code, and find the most frequent one. This is simplistic and crude as the plus code grid is predefined (what if two points are right next to each other? what if one grid size resolution is too large and next level one that's 400x smaller is too small?)

Specifics

• Max cluster area : 2 sq km
• Or, max distance between any two points: 0.5 km.
• Input would be one dataframe having one point per row
• Output would be two dataframes or lists telling which is 'Out' and which is 'In'.

Good leads to pursue

• Kaggle - Basic Visualization and Clustering in Python
• Filtering out spatial-outliers from cluster of points using PyQGIS? - answer is promising but I can't use it directly : Will have find largest polygon and then find all the points in that. If would be great to adapt this to work directly with pandas/lists instead of having to convert into a shapefile layer and all.
• How to cluster points and plot - It's in R so a python adaptation would make for a good answer here.

I'll update here if I find more leads.

Clarification notes

• No weighing, scoring business etc. They're just lat-long points.
• The data is ok enough that we can trust the majority; most points are near the right place and there may be just 1 to 3 outlaws in each set.
• Preferred programming language is python3, but I'm open to seeing other solutions; will adapt.
• I'm not too concerned about lat-long contorting (the work area is in the tropics so a lat-long grid is pretty squarish), so it's possible to boil this down to a simple x-y scatterplot, and finding the odd one out.
• I'm aware that the algorithms can even generate multiple clusters. In that scenario I'll just take the most populated cluster and all the other points will be branded outlaws. In case of 50-50, I'll flip a coin :)
• No need of visualising! This has to be a sub-routine at back end.

Related questions on this forum

• Creat clusters using long and lat - basic question, could be great as a starting point, unfortunately no answers yet.
• How to calculate/measure the spread of coordinates in an area using python - no solid answer
• Clustering geographical data based on point location and associated point values - went into more complicated territory
• Clustering of Spatial Data in R or Python - closed for being unclear

Answer 1

If what you are looking at is simply filtering out points that are outliers (e.g. distance bigger than x), then a good solution that I used successfully in the past is to run a nearest neighbour algorithm and filter by maximum distance.

In python this can be achieved very efficiently and fast by using the sklearn package. An example code could be:

from sklearn.neighbors import NearestNeighbors
nn = NearestNeighbors(n_neighbors=2)
nn.fit(samples)
# for each point, the first match is the point itself, the second match is the actual nearest neighbour
indices, distances = nn.kneighbors(samples)
# you can now sort through the "distances" dataset to find values higher than you threshold and delete those entries

You may want to reproject your dataset to a projected coordinate reference system having meters as units. A simple way you can do it is by using geopandas (you mentioned dataframes, so I guess you are familiar with pandas)

samples.to_crs(epsg=3111)

However that can be achieved in many other ways.

NOTE: this method assumes that the outlier is an outlier of any cluster (e.g. away from ANY other point). If this is not the case the method will not work unless you repeat this step iteratively selecting one cluster at the time

Answer 2

I think DBSCAN clustering algorithm is what you are looking for. If you have PostGIS at your fingertips, then you can simply use st_clusterdbscan function as described here. If you really want python, then you can probably use scikit-learn implementation of that algorithm which is described here.