9
$\begingroup$

I'm working on some software which should determine real world locations (f.e. speed cams) from several GPS-based reports. An user will be driving when reporting a location, thus the reports a very inaccurate. To solve that problem I have to cluster reports about the same location and calculate an average.

My question is about how to cluster those reports. I read about Expectation-maximation algorithms and k-means clustering, but as I understood I would need to determine the number of real locations in advance.

Are there any other algorithms, which don't need the exact number of real locations, but instead use some edge conditions (f.e. minimal distance) ?

A report contains longitude, latitude and accuracy (in meters). There is no name or anything else which could be used to identify duplicates.

Another obstacle could be that it will be common, that there is only one report for a real world location. That makes it difficult to distinguish outliers from good data.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I'm not sure what you mean when you say "...as I understood I would need to determine the number of real locations in advance..." Assuming I've understood you correctly, there's nothing in the algorithms which inherently requires this. Are you perhaps planning to increase the number of cluster components based on the number of reports? $\endgroup$
    – Pat
    Commented May 23, 2013 at 8:20
  • 1
    $\begingroup$ 2nd question :) . If your reports are coming from someone who is driving, then there's possibly going to be significant changes in position between them. Do the reports come with a timestamp telling you when they were taken? $\endgroup$
    – Pat
    Commented May 23, 2013 at 8:23
  • 2
    $\begingroup$ Hi Pat. I'm talking about traffic jams or speed cams to make it more clear. 1. The "k" in k-means clustering stands for the number of clusters. In my case I would have one cluster for each location, whereas I don't know how many different locations there are. 2. Yes, they also include a timestamp. But I don't understand why that should be important, because I only care about the position. $\endgroup$
    – Christian Strempfer
    Commented May 23, 2013 at 8:36
  • 1
    $\begingroup$ 1. Ahh, I see. So you have an unknown number of locations, and each location generates one or more reports. However, all you see are a stream of reports. You want to infer how many locations there are, and their position, based on the observed reports. Have I got it? 2. I worry about timestamps because you say the user will be driving when they give a report. As such, unless the reports come in very quick succession, or the speed is very low (possible, if it's a traffic jam) then a single location will look like a ragged line of reports following the road. Timestamps may be able to help here $\endgroup$
    – Pat
    Commented May 23, 2013 at 9:05
  • 1
    $\begingroup$ 1. Yes, you've got it. 2. It's a manual task, so a location should only be reported once per user during one trip. But you're right, I have to handle duplicates, when a user accidently clicks twice, and reports will be inaccurate when driving fast. That's why I mentioned the edge condition of a minimal distance between locations. Let's ignore traffic jams, which might spread some miles, and assume that a location is very small. $\endgroup$
    – Christian Strempfer
    Commented May 23, 2013 at 9:15

1 Answer 1

Reset to default
1
+50
$\begingroup$

I have found a software that maybe can help you. It looks like somebody had the same problem that you and they gave him a solution in this forum, so you will need to use ArcGIS, but if you are looking for an algorithm they suggest this paper. I think the paper is detailed enough to be a good start fro your algorithm.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Because all the information is this answer resides in its links, and links do eventually rot, please at least summarize what the forum posts and the paper recommend. $\endgroup$
    – whuber ♦
    Commented Jan 1, 2016 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.