0

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

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 Jan 13 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? – Nikhil VJ Jan 13 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. – Vince Jan 14 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 :) – Nikhil VJ Jan 14 at 10:43
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.