11
$\begingroup$

I need to write a program to find the average GPS point from a population of points.

In practice the following happens:

  • Each month a person records a GPS point of the same static asset.
  • Because of the nature of GPS, these points differ slightly each month.
  • Sometimes the person makes a mistake a records the wrong assest at a completely different location.
  • Each GPS point has a certainty weight (HDOP) that indicates how accurate the current GPS data is. GPS points with better HDOP values are preferred over lower ones..

How do I determine the following:

  • Deal with data with 2 values vs. a single value like age. (Find the average age in a population of people)
  • Determine the outliers. In the example below these would be [-28.252, 25.018] and [-28.632, 25.219]
  • After excluding the outliers, find the average GPS point in this it might be [-28.389, 25.245].
  • It would be a bonus if can work the "weight" provided by HDOP value for each point.

alt text

$\endgroup$
  • 1
    $\begingroup$ This answer is similar enough to help you with the averaging of the points, stats.stackexchange.com/questions/2493/…, it is simple to incorporate weights in that framework. I would think you would be able to use some simple heuristics to identify outliers, but that doesn't preclude you from taking a more empirical approach like Stephan suggested. $\endgroup$ – Andy W Oct 19 '10 at 11:52
8
$\begingroup$

One of the problems with multivariate data is deciding on, and then interpreting, a suitable metric for calculating distances, hence clever but somewhat hard-to-explain concepts such as Mahalanobis distance. But in this case surely the choice is obvious - Euclidean distance. I'd suggest a simple heuristic algorithm something like:

  1. Calculate the (unweighted) centroid of the data points, i.e. the (unweighted) means of the 2 coordinates
  2. Calculate the Euclidean distance of all the readings from the centroid
  3. Exclude any readings that are further than a certain distance (to be determined based on your experience and knowledge of the technology, or failing that a bit of trial and error cross-validation - 100m, 1km, 10km??)
  4. Calculate the weighted average of both coords of the remaining points, weighting by the inverse of the HDOP score (or some monotonic function of it - i had a quick look at the wikipedia page linked in the question and think maybe you don't need such a function but i'd need to study it further to be sure)

There are clearly several ways to make this more sophisticated, such as down-weighting outliers or using M-estimators rather than simply excluding them, but I'm not sure whether such sophistication is really necessary here.

$\endgroup$
3
$\begingroup$

Rob Hyndman recently posed a question about detecting outliers in multivariate data. The answers may provide a couple of possible approaches (and otherwise, you may want to put the question of finding 2-d outliers in a separate question).

And you can average your remaining GPS data component by component - add all the first components up and divide by the number of points, that will give you the first component of the average. Same with the second components.

This averaging can be weighted by HDOP. Sum up the products of the first component, multiplied with the corresponding HDOP score, and divide the sum by the sum of the HDOP scores. Same with the second components.

I'll take the liberty of removing the "normal-distribution" tag...

$\endgroup$
  • $\begingroup$ Thanks @Stephan Kolassa, this will already help towards finding a solution. $\endgroup$ – Philip Fourie Oct 19 '10 at 8:39
2
$\begingroup$

Call the HDOP the independent variable. Use this for weighting later on. So you have sets of co-ordinates - call this (x1,y1); (x2,y2), etc... First ignore outliers. Calculate the weighted averages of the x co-ordinates as [(x1*h1)+(x2*h2) +....+ (xn*hn)] / [sum(h1,h2,...,hn)] where h1,h2,... is the HDOP value. Do the same for the y co-ordinates. This will give a fairly accurate average value for each co-ordinate.

Dealing with outliers can be a bit tricky. How do you know if they are outliers or not? Strictly you need to determine a statistical fit to the observations and within a confidence interval determine if they are genuine or not. Looking at the question the Poison Distribution does come to mind. But this is probably a lot of work and I'm sure you don't want to go into this. Maybe use an approximation? Say you assume that the average co-ordinate value is a good mean to use. Then determine a value for the standard deviation. I think the standard dev or the poison distribution is 1/(mean). Then approximate using the normal distribution and a 95% confidence interval. Say if an observation is outside the interval (mean-*1.645*std dev ; mean + 1.645*std dev) then it is an outlier? Give this a go. Maybe go do a bit of reading on the poison distribution and incorporate the HDOP value into this?

$\endgroup$

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.