2
$\begingroup$

Imagine this... Batman has just retrieved a tracking device he placed on The Joker 150 days ago. The good news is that it has 150 coordinates — one from each day. The bad news is that all the data is randomly sorted — there's no way to tell when the coordinates were recorded, nor their sequence. Further, all the data was collected at random times during the day so we can't even be sure any of the points were actually taken at the hideout — it might very well be in between some of them. How can we help Batman find the secret hideout?

Here's a map of the dataset: http://batchgeo.com/map/c3676fe29985f00e1605cd4f86920179

Here's a pastebin of raw 150 geocodes: http://pastebin.com/grVsbgL9

In math terms, I'm looking for help identifying the centroid of a complex cluster of data. As you'll notice in this data set, there are several clusters (San Francisco, LA, Chicago and NYC) along with lots of noise throughout the rest. I need to determine which cluster is primary, and identify the centroid of this cluster.

Can you recommend a strategy? Preferably one with some meat I can use to begin analyzing the data for the "secret hideout"? ;)

$\endgroup$
  • $\begingroup$ I don't know anything about statistics, but before hitting the data with math, I would just look at them. You've already got a nice visualization. Why do statistics right away? Looking at the data, it appears as if there's not going to be a single "hideout". I would think that the best you could do is pick the three largest clusters, visually, and try to do something with that. If you had given me this data set and said these were random, daily samples for 150 days, I would think that this was someone travelling across the US and visiting cities, not someone operating out of a hideout! $\endgroup$ – Zach L. Jun 20 '13 at 4:50
  • 1
    $\begingroup$ Also asked at mathoverflow.net/questions/134212/… $\endgroup$ – Joel Reyes Noche Jun 20 '13 at 4:56
  • $\begingroup$ Consider using cluster analysis assuming that you have multiple hideouts. $\endgroup$ – response Jun 20 '13 at 5:12
  • $\begingroup$ @ZachL., Unfortunately I need to do this for all of DC Comic's super villains: en.wikipedia.org/wiki/Category:DC_Comics_supervillains , so looking visually isn't an option. I need a formula to do this for hundreds of data sets. $\endgroup$ – Ryan Jun 20 '13 at 5:18
  • 1
    $\begingroup$ @JoelReyesNoche: update - question since removed from mathoverflow. $\endgroup$ – J W Jan 15 '16 at 7:55
1
$\begingroup$

Here's a heuristic that has no scientific basis whatsoever (as far as I know). It's virtue is that it's easy to program.

Let $d_{ij}$ be the distance from point $P_i$ to point $P_j$, $(1 \le i,j \le n)$.

(1) Compute the average $d$ of all the $n^2$ $d_{ij}$ values.

(2) Choose some factor $k$; I'd suggest around 0.1, but you can experiment.

(3) Let $r=k*d$ be a "threshold" radius.

(4) For each $i$, find the count $c_i$ of other points that are within a distance $r$ from point $P_i$.

(5) Any point $P_i$ that has high value for $c_i$ is a good candidate for the hide-out, because it has lots of other points nearby.

If you think you can guess a good value for $r$, then you can skip steps (1) and (2).

$\endgroup$
  • $\begingroup$ I see, some sort of crude kernel density estimation based on each point's proximity to others within a given radius. Let's say that gets us a cluster, how can we determine the centroid of this cluster, assuming the actual "hideout" is in between the given points? $\endgroup$ – Ryan Jun 20 '13 at 12:25
  • $\begingroup$ Average the points in the cluster? $\endgroup$ – bubba Jun 20 '13 at 12:51
  • $\begingroup$ Are you suggesting Mean(Lat1,Lat2,...Latn),Mean(Lng1,Lng2,...Lngn)? I tried that and it doesn't always lead to center mass. $\endgroup$ – Ryan Jun 20 '13 at 13:04
  • $\begingroup$ Well I was thinking of $\bar x = \text{mean}(x_1, \dots, x_n) $, $\bar y = \text{mean}(y_1, \dots, y_n)$, but this should give roughly the same answer as your suggestion, for points in the USA, anyway. Trying to get the exact center of a cluster of points (whatever that means) seems futile anyway, given that the members of the cluster are defined only by some heuristic. This whole process is just educated guess-work, anyway, isn't it? $\endgroup$ – bubba Jun 21 '13 at 13:08
  • $\begingroup$ Just taking means will not work; see my answer below for an algorithm to compute what (I believe) you want. $\endgroup$ – Benjamin Dickman Jun 23 '13 at 4:06
1
$\begingroup$

If I'm not mistaken, you are looking for the geometric median of a set of points.

One way to approach this is to build a physical model as described in the Background Example here. I believe this technique dates back to Gauss, who described it in an unpublished letter to Schumacher (for the case in which there are only $4$ different points; but it extends naturally to the case with many points).

With regard to tackling the problem computationally, you might try Weiszfeld's algorithm. See, for example, this wikipage section, which includes references to more recent approaches as well.

$\endgroup$
  • $\begingroup$ Now that is fascinating. I can picture the physical model and believe this would yield the correct result (p in the case of the background example). However, for my purposes I require a mathematical or programatic approach to solve this problem with hundreds (or more) data sets. $\endgroup$ – Ryan Jun 20 '13 at 5:27
  • $\begingroup$ I added a link for how to approach this computationally. $\endgroup$ – Benjamin Dickman Jun 20 '13 at 15:37

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.