Identify lat long points falling out of cluster

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'.

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

• Check this out: stackoverflow.com/a/26544427/1446289
– Aaron
Commented Jan 13, 2019 at 16:02
• @Aaron thanks I'll add it to the references. It's in R and I currently can't see how to adapt it to python. Can you share which libraries to import etc? Commented Jan 13, 2019 at 16:15
• There's a ton of information here, but very little in the way of focused question. You appear to want to start a discussion, but GIS SE doesn't really do discussions. We do have Geographic Information Systems Chat, but it is underutilized, so you might need to seek advice elsewhere. Commented Jan 14, 2019 at 0:09
• Actually I want one sound technical answer, found leads in multiple directions but don't know which will lead to a solution first (or a more efficient one) and didn't want to create a new question here for each one. Had to share prior done research so I don't have a dozen comments / answers simply pointing to the same things. I've provided the exact inputs, outputs, parameters. If the one provided works out I'll mark it as answer. Also : am one point short of being able to use that chat system :) Commented Jan 14, 2019 at 10:43

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
distances, indicies = 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

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.