Unsupervised outlier detection in 2D space

Question

Problem

I'm working on a school project in Java and my goal is to detect and remove outliers from a dataset containin geo points.

The final result should be a single cluster, with any shape, containing all the points inside a real area (like a stadium for example). Here's a quick example of what I mean:

The hand-drawn blue line represents the expected cluster, while all the outside points should be considered as outliers (this is just one of the possible clusters that can be ok for my case, not detecting the top part is fine too).

What I tried

While DBSCAN looks like the best choice, I need this to be unsupervised so I can't manually set eps and minPts (the algorithm should run on several datasets). What could work is a function that defines both eps and minPts based on the size of the dataset and the size of the area (maybe in meters, using a geo-based distance function), but defining such function can be quite challenging for a small project.

To avoid dealing with eps I decided to try OPTICS but it still requires minPts and, in my tests using ELKI, it returns a single cluster with all the points.

Finally, since ELKI has a lot of builtin algorithms, I also tried LibSVMOneClassOutlierDetection becauseit should be the best option for binary classification (which is my task basically, classes can be seen as "inside" and "outside" the cluster), but it detects almost any point as outlier (even if they have a score, and all the needed points have score < 0.1 so I may do some post-processing steps later).

Question

So, here are the questions:

1. Is there an unsupervised (and possibly paramterless) algorithm that I can use to solve this task?
2. If yes, is there any implementation ready somewhere?
3. Bonus - Can you suggest an algorithm that's already built in ELKI (or even Weka)? If it's in ELKI, can you suggest an evaluation function for the Evaluator if the automatic one is not good enough?

EDIT: Based on suggestions I've tried OPTICSXi with minPts = 50, here's the result.

As you can see, there are two problems:

1. Red cluster, which is the candidate to be the correct one, contains points that are way far from center, but I suppose that I can deal with them later
2. There are other clusters inside the red one, while they should be part of it

EDIT 2: did some other tests using DBSCAN with an automatic eps estimation and I like the result more than OPTICS' one, but the question now is: how can I extract the purple cluster and remove all the others? I can't seem to find any way to evaluate a DBSCAN cluster based on density.

Answer 1

Your task seems to be rather a clustering than an outlier detection task.

In the following, I use this popular data set of User locations (Joensuu).

Running OPTICS with the parameters

-dbc.in /tmp/MopsiLocations2012-Joensuu.txt
-algorithm clustering.optics.OPTICSXi -opticsxi.xi 0.05
-algorithm.distancefunction geo.LngLatDistanceFunction
-optics.epsilon 5000.0 -optics.minpts 50

yields the following (hierarchical) clustering. You can see there are three larger clusters (corresponding to Joensuu, Lieska, and Savijärvi; note that the plot has latitude and longitude 'the wrong way'), and some noise (violet here) that is not density-reachable with 5km distance and 50 points. These are your outliers.

You can tell there are some subclusters in both cities. For example one corresponding to the Prisma Joensuu shopping mall. To see more detail, it is helpful to further reduce epsilon, maybe to just 500 meters.

Answer 2

To answer Edit 2 of this old question -- one way would be to compute the Mahalanobis distance for each point to the center of the cluster, then delete those above a certain cutoff distance.