4

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.

  • Have you tried filtering the file through gpsvisualizer.com and using the "Discard Outliers" option? I know that's an online tool, not really what you're after. – Chenmunka Sep 30 '14 at 11:38
  • @Chenmunka: I would have to split the filefor each city (tens of thousands) and submit them individualy, not very convenient :-/ They don't seem to have an API and would probably ban me if I tried... – Nicolas Raoul Oct 1 '14 at 5:59
2

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:

ELKI parameters

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

ELKI graph

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.