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).
So, here are the questions:
- Is there an unsupervised (and possibly paramterless) algorithm that I can use to solve this task?
- If yes, is there any implementation ready somewhere?
- 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:
- 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
- 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.