Outlier detection in latitude/longitude CSV file

Question

I have a huge CSV file containing GPS points of hotels in various cities. Sample:

CITY    | HOTEL     | LATITUDE | LONGITUDE
Chicago | Bellevue  | 41.826   | -87.689
Chicago | SuperMt   | 41.924   | -87.703
Chicago | Starhotel | 44.903   | -93.215
Chicago | BestW     | 41.743   | -87.641
Tokyo   | CityStay  | 30.212   | 128.435

Is there a program that can detect outliers? For instance, Starhotel's latitude/longitude are clearly wrong, putting it hundreds of kilometers away from the other hotels of the same city.

Requirements:

• Outliers should be detected relative to the dispersion of the main cluster, for instance hotels in "California" will be rather far apart, whereas hotels in "East Village" will all be very close to each other. So "outlier" is relative to the dispersion of the whole group.
• Free, ideally open source
• Fast to configure
• Works with 300,000 lines 100 MB CSV file, or its equivalent RDF or OSM file
• Any OS. Ideally command-line. Online tool/API OK if it can handle the load.
• Longitude becomes less significant near the South/North Poles. Calculating distance in a naive way sqrt(latitudeDelta²+longitudeDelta²) is better than nothing, though, as the Poles don't have many hotels.

Final goal: catch probable errors, in order to send them to human reviewers. 100% accuracy not needed.

Answer 1

First of all, you may want to split your data set into cities. This will probably yield better results than keeping everything together.

Then the tool of choice probably is ELKI:

1. It contains lots and lots of algorithms for outlier detection. In particular, it has the Local Outlier Factor (wikipedia), which exactly tries to capture local differences in density
2. It supports Geodetic distance, with different earth models
3. It can use R-tree indexes for acceleration, so 300k is not a problem (but you may still want to split the data set on cities, for better results; and without it, a hotel titled "Chicago" but with coordinates in California will still appear to be normal from the coordinates). I have used 100k multidimensional data sets myself already; and I've seen the author use 23 million tweets in clustering...
4. Open-source, written in Java.

You may also want to check the authors work on customizing outlier detection. This may be required if you want to process all 300k at once, and use the city and hotel columns as well. (Most methods are designed for numerical data!) From my interpretation of this model, you may want to define the context as hotels in the same city, and then compare the densities.

Schubert, E., Zimek, A., & Kriegel, H. P. (2014).
Local outlier detection reconsidered: a generalized view on locality with applications to spatial, video, and network outlier detection.
Data Mining and Knowledge Discovery, 28(1), 190-237.

hmm... thinking of your problem, this one may also be relevant, detecting outliers in car accident and radiactivity measurement data:

Schubert, E., Zimek, A., & Kriegel, H. P. (2014).
Generalized outlier detection with flexible kernel density estimates.
In Proceedings of the 14th SIAM International Conference on Data Mining (SDM), Philadelphia, PA.

I guess both were done using ELKI, since it is the same authors...

---

Here is how to use ELKI to perform outlier detection:

1. Separate your data into one latitude,longitude CSV file per city.
2. Download the ELKI JAR and open it
3. Configure the parameters like this:

4. Push the Run task button and you should get this: