假设我在过去一年中每天绘制直升机的位置并得出以下 map :
任何看到这个的人都会告诉我这架直升机位于芝加哥以外。
如何在代码中找到相同的结果？
我正在寻找这样的东西:
$geoCodeArray = array([GET=http://pastebin.com/grVsbgL9]);
function findHome($geoCodeArray) {
// magic
return $geoCode;
}
最终生成如下内容:
更新:示例数据集
这是一张带有示例数据集的 map :http://batchgeo.com/map/c3676fe29985f00e1605cd4f86920179
这是一个包含 150 个地理编码的 pastebin:http://pastebin.com/grVsbgL9
以上包含 150 个地理编码。前 50 个位于芝加哥附近的几个集群中。其余分布在全国各地，包括纽约、洛杉矶和旧金山的一些小集群。
我有大约一百万(严重)这样的数据集，我需要遍历并确定最有可能的“家”。非常感谢您的帮助。
更新 2:飞机改用直升机
飞机概念引起了对实体机场的过多关注。坐标可以是世界上的任何地方，而不仅仅是机场。让我们假设它是一架不受物理、燃料或其他任何因素约束的 super 直升机。它可以降落在它想要的地方。 ;)
最佳答案
通过将纬度和经度转换为笛卡尔坐标，即使点散布在地球各处，以下解决方案也适用。它执行一种 KDE(内核密度估计)，但在第一遍中，内核总和仅在数据点处进行评估。应该选择内核来解决问题。在下面的代码中，我可以开玩笑/冒昧地称其为 Trossian，即 d≤h 为 2-d²/h²，d>h 为 h²/d²(其中 d 是欧氏距离，h 是“带宽”$global_kernel_radius)，但它也可以是高斯 (e-d²/2h²)，Epanechnikov 核(1-d²/h² 对于 d
本质上，每个点将它周围的所有点(包括它自己)相加，如果它们更近(通过钟形曲线)，则对它们进行加权，并通过可选的权重数组对它们进行加权$w_arr。获胜者是总和最大的点。一旦找到了赢家，就可以通过在赢家周围重复相同的过程(使用另一条钟形曲线)找到我们要寻找的“家”，或者可以估计它是所有点的“质心”在获胜者的给定半径内，半径可以为零。
算法必须通过选择合适的内核、选择如何在本地优化搜索以及调整参数来适应问题。对于示例数据集，第一遍的 Trossian 内核和第二遍的 Epanechnikov 内核，所有 3 个半径都设置为 30 英里，网格步长为 1 英里可能是一个很好的起点，但前提是两个子芝加哥的集群应该被看作是一个大集群。否则必须选择更小的半径。
function find_home($lat_arr, $lng_arr, $global_kernel_radius,
$local_kernel_radius,
$local_grid_radius, // 0 for no 2nd pass
$local_grid_step, // 0 for centroid
$units='mi',
$w_arr=null)
{
// for lat,lng <-> x,y,z see http://en.wikipedia.org/wiki/Geodetic_datum
// for K and h see http://en.wikipedia.org/wiki/Kernel_density_estimation
switch (strtolower($units)) {
/* */case 'nm' :
/*or*/case 'nmi': $m_divisor = 1852;
break;case 'mi': $m_divisor = 1609.344;
break;case 'km': $m_divisor = 1000;
break;case 'm': $m_divisor = 1;
break;default: return false;
}
$a = 6378137 / $m_divisor; // Earth semi-major axis (WGS84)
$e2 = 6.69437999014E-3; // First eccentricity squared (WGS84)
$lat_lng_count = count($lat_arr);
if ( !$w_arr) {
$w_arr = array_fill(0, $lat_lng_count, 1.0);
}
$x_arr = array();
$y_arr = array();
$z_arr = array();
$rad = M_PI / 180;
$one_e2 = 1 - $e2;
for ($i = 0; $i < $lat_lng_count; $i++) {
$lat = $lat_arr[$i];
$lng = $lng_arr[$i];
$sin_lat = sin($lat * $rad);
$sin_lng = sin($lng * $rad);
$cos_lat = cos($lat * $rad);
$cos_lng = cos($lng * $rad);
// height = 0 (!)
$N = $a / sqrt(1 - $e2 * $sin_lat * $sin_lat);
$x_arr[$i] = $N * $cos_lat * $cos_lng;
$y_arr[$i] = $N * $cos_lat * $sin_lng;
$z_arr[$i] = $N * $one_e2 * $sin_lat;
}
$h = $global_kernel_radius;
$h2 = $h * $h;
$max_K_sum = -1;
$max_K_sum_idx = -1;
for ($i = 0; $i < $lat_lng_count; $i++) {
$xi = $x_arr[$i];
$yi = $y_arr[$i];
$zi = $z_arr[$i];
$K_sum = 0;
for ($j = 0; $j < $lat_lng_count; $j++) {
$dx = $xi - $x_arr[$j];
$dy = $yi - $y_arr[$j];
$dz = $zi - $z_arr[$j];
$d2 = $dx * $dx + $dy * $dy + $dz * $dz;
$K_sum += $w_arr[$j] * ($d2 <= $h2 ? (2 - $d2 / $h2) : $h2 / $d2); // Trossian ;-)
// $K_sum += $w_arr[$j] * exp(-0.5 * $d2 / $h2); // Gaussian
}
if ($max_K_sum < $K_sum) {
$max_K_sum = $K_sum;
$max_K_sum_i = $i;
}
}
$winner_x = $x_arr [$max_K_sum_i];
$winner_y = $y_arr [$max_K_sum_i];
$winner_z = $z_arr [$max_K_sum_i];
$winner_lat = $lat_arr[$max_K_sum_i];
$winner_lng = $lng_arr[$max_K_sum_i];
$sin_winner_lat = sin($winner_lat * $rad);
$cos_winner_lat = cos($winner_lat * $rad);
$sin_winner_lng = sin($winner_lng * $rad);
$cos_winner_lng = cos($winner_lng * $rad);
$east_x = -$local_grid_step * $sin_winner_lng;
$east_y = $local_grid_step * $cos_winner_lng;
$east_z = 0;
$north_x = -$local_grid_step * $sin_winner_lat * $cos_winner_lng;
$north_y = -$local_grid_step * $sin_winner_lat * $sin_winner_lng;
$north_z = $local_grid_step * $cos_winner_lat;
if ($local_grid_radius > 0 && $local_grid_step > 0) {
$r = intval($local_grid_radius / $local_grid_step);
$r2 = $r * $r;
$h = $local_kernel_radius;
$h2 = $h * $h;
$max_L_sum = -1;
$max_L_sum_idx = -1;
for ($i = -$r; $i <= $r; $i++) {
$winner_east_x = $winner_x + $i * $east_x;
$winner_east_y = $winner_y + $i * $east_y;
$winner_east_z = $winner_z + $i * $east_z;
$j_max = intval(sqrt($r2 - $i * $i));
for ($j = -$j_max; $j <= $j_max; $j++) {
$x = $winner_east_x + $j * $north_x;
$y = $winner_east_y + $j * $north_y;
$z = $winner_east_z + $j * $north_z;
$L_sum = 0;
for ($k = 0; $k < $lat_lng_count; $k++) {
$dx = $x - $x_arr[$k];
$dy = $y - $y_arr[$k];
$dz = $z - $z_arr[$k];
$d2 = $dx * $dx + $dy * $dy + $dz * $dz;
if ($d2 < $h2) {
$L_sum += $w_arr[$k] * ($h2 - $d2); // Epanechnikov
}
}
if ($max_L_sum < $L_sum) {
$max_L_sum = $L_sum;
$max_L_sum_i = $i;
$max_L_sum_j = $j;
}
}
}
$x = $winner_x + $max_L_sum_i * $east_x + $max_L_sum_j * $north_x;
$y = $winner_y + $max_L_sum_i * $east_y + $max_L_sum_j * $north_y;
$z = $winner_z + $max_L_sum_i * $east_z + $max_L_sum_j * $north_z;
} else if ($local_grid_radius > 0) {
$r = $local_grid_radius;
$r2 = $r * $r;
$wx_sum = 0;
$wy_sum = 0;
$wz_sum = 0;
$w_sum = 0;
for ($k = 0; $k < $lat_lng_count; $k++) {
$xk = $x_arr[$k];
$yk = $y_arr[$k];
$zk = $z_arr[$k];
$dx = $winner_x - $xk;
$dy = $winner_y - $yk;
$dz = $winner_z - $zk;
$d2 = $dx * $dx + $dy * $dy + $dz * $dz;
if ($d2 <= $r2) {
$wk = $w_arr[$k];
$wx_sum += $wk * $xk;
$wy_sum += $wk * $yk;
$wz_sum += $wk * $zk;
$w_sum += $wk;
}
}
$x = $wx_sum / $w_sum;
$y = $wy_sum / $w_sum;
$z = $wz_sum / $w_sum;
$max_L_sum_i = false;
$max_L_sum_j = false;
} else {
return array($winner_lat, $winner_lng, $max_K_sum_i, false, false);
}
$deg = 180 / M_PI;
$a2 = $a * $a;
$e4 = $e2 * $e2;
$p = sqrt($x * $x + $y * $y);
$zeta = (1 - $e2) * $z * $z / $a2;
$rho = ($p * $p / $a2 + $zeta - $e4) / 6;
$rho3 = $rho * $rho * $rho;
$s = $e4 * $zeta * $p * $p / (4 * $a2);
$t = pow($s + $rho3 + sqrt($s * ($s + 2 * $rho3)), 1 / 3);
$u = $rho + $t + $rho * $rho / $t;
$v = sqrt($u * $u + $e4 * $zeta);
$w = $e2 * ($u + $v - $zeta) / (2 * $v);
$k = 1 + $e2 * (sqrt($u + $v + $w * $w) + $w) / ($u + $v);
$lat = atan($k * $z / $p) * $deg;
$lng = atan2($y, $x) * $deg;
return array($lat, $lng, $max_K_sum_i, $max_L_sum_i, $max_L_sum_j);
}
距离是欧几里德距离而不是大圆距离这一事实对手头的任务的影响可以忽略不计。计算大圆距离会更麻烦，并且只会导致非常远的点的权重显着降低——但这些点的权重已经很低了。原则上，不同的内核可以达到相同的效果。具有超出一定距离的完全截止的内核，如 Epanechnikov 内核，根本没有这个问题(在实践中)。
WGS84 基准面的纬度、经度和 x、y、z 之间的转换是准确给出的(尽管不保证数值稳定性)，更多的是作为引用而不是因为真正的需要。如果要考虑高度，或者需要更快的反向转换，请引用 Wikipedia article .
Epanechnikov 核除了比高斯核和特罗西核“更局部”外，还具有第二个循环最快的优点，即 O(ng)，其中 g 是局部网格的点数, 如果 n 很大，也可以用在第一个循环中，即 O(n²)。
关于algorithm - 如何找到一组数据点的中心？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17112719/