Есть вот такой набор точек, каждая точка представляет собой gps координату автобуса (x,y), у каждой точки есть timestamp. На построенном графике видны явные ошибки измерения. Как их можно убрать? Решение должно быть простым, так как всего координат около 100 тысяч. Интересует идея, но желательно, чтобы ее можно было без особых проблем реализовать средствами Java
Пример исходных данных:
1447037729
Первое поле - UNIX-время, второе и третье - (x,y) соответственно, четвертое - идентификатор автобуса (автобусов около 50ти) .
Исходные данные : https://drive.google.com/file/d/0B4bA9d5B_O_BcVpPUXpYTmZBUFE/view
Ответ
Приведённый набор точек - это две зависимости: x(t) и y(t), и по каждой идёт импульсный шум. К таким данным идеально подходит алгоритм медианной обработки в скользящем окне на 7-9 элементов, когда i-тый во времени элемент заменяется на медианное значение элементов с номерами (i-h,i+h) при h=3...4.
Обработку для x(t) и y(t) следует проводить независимо, после чего подменить ими исходные массивы.
Обработка эффективна при высоком уровне импульсной помехи (в тестовом примере искажена третья часть данных). Дополнительный плюс - что сохраняется формат исходных данных. Обработка краёв ведётся на окнах меньшего размера.
Минусы обработки в скользящем окне проявляются при разворотах последовательности, поскольку выступы и провалы шириной меньше h выполаживаются.
В демо-программе представлена рекуррентная сортировка массива в окне. Для этого точки, лежащие между старым (удаляемым) и новым (добавляемым) элементами, сдвигаются в сторону старого элемента, после чего на место крайнего из возникших дубликатов записывается новый элемент. Это резко снижает вычислительные затраты.
Демо-программа (PHP):
function print_a($a, $name){
print("$name: ");
foreach($a as $item){
printf("%2d, ",$item);
}
}
function slide_median($h, $a){
$size = count($a);
$result = [];
$slide = [];
array_push($slide, reset($a));
array_push($result,$slide[0]);
print_a($slide, " Сортировка в окне");
print_a($result, "
Массив результата");
for($i=1; $i<=$h; $i++){
array_push($slide, next($a), next($a));
sort($slide);
array_push($result, $slide[$i]);
print_a($slide, " Сортировка в окне");
print_a($result, "
Массив результата");
}
for($i=0; $i < $size-2*$h-1; $i++){
$old = $a[$i];
$new = $a[$i+2*$h+1];
if($old < $new){
for($key = 0; $key <= 2*$h; $key++){
if($new < $slide[$key]){
break;
}
if(($old <= $slide[$key])&&($slide[$key] < $new)) $slide[$key] = $slide[$key+1];
}
$slide[$key-1] = $new;
}
if($old > $new){
for($key = 2*$h; $key >= 0; $key--){
if($new > $slide[$key]){
break;
}
if(($old >= $slide[$key])&&($slide[$key] > $new)) $slide[$key] = $slide[$key-1];
}
$slide[$key+1] = $new;
}
array_push($result, $slide[$h]);
print(" old = $old, new =$new");
print_a($slide, " Сортировка в окне");
print_a($result, "
Массив результата");
}
for($i = $h-1; $i > 0; $i--){
$slide = array_slice($a, $size-2*$i-1, 2*$i+1);
sort($slide);
array_push($result, $slide[$i]);
print_a($slide, " Сортировка в окне");
print_a($result, "
Массив результата");
}
$slide = [$a[$size-1]];
array_push($result, $slide[0]);
print_a([end($a)], " Сортировка в окне");
print_a($a, "
Исходный массив: ");
print_a($result, "
Массив результата");
return $result;
};
$a = range(20, 40);
foreach($a as &$item){
$item += 5*mt_rand(-1,1)*(int)(mt_rand(0,199)/100);
}
print_a($a, "Исходный массив: ");
slide_median(3, $a);
Результаты (импульсный шум, амплитуда 5):
Исходный массив: : 20, 21, 22, 23, 19, 20, 21, 27, 28, 29, 30, 31, 32, 28, 29, 35, 36, 42, 43, 39, 35, Сортировка в окне: 20,
Массив результата: 20, Сортировка в окне: 20, 21, 22,
Массив результата: 20, 21, Сортировка в окне: 19, 20, 21, 22, 23,
Массив результата: 20, 21, 21, Сортировка в окне: 19, 20, 20, 21, 21, 22, 23,
Массив результата: 20, 21, 21, 21, old = 20, new =27 Сортировка в окне: 19, 20, 21, 21, 22, 23, 27,
Массив результата: 20, 21, 21, 21, 21, old = 21, new =28 Сортировка в окне: 19, 20, 21, 22, 23, 27, 28,
Массив результата: 20, 21, 21, 21, 21, 22, old = 22, new =29 Сортировка в окне: 19, 20, 21, 23, 27, 28, 29,
Массив результата: 20, 21, 21, 21, 21, 22, 23, old = 23, new =30 Сортировка в окне: 19, 20, 21, 27, 28, 29, 30,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, old = 19, new =31 Сортировка в окне: 20, 21, 27, 28, 29, 30, 31,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, old = 20, new =32 Сортировка в окне: 21, 27, 28, 29, 30, 31, 32,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, old = 21, new =28 Сортировка в окне: 27, 28, 28, 29, 30, 31, 32,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, old = 27, new =29 Сортировка в окне: 28, 28, 29, 29, 30, 31, 32,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, old = 28, new =35 Сортировка в окне: 28, 29, 29, 30, 31, 32, 35,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, old = 29, new =36 Сортировка в окне: 28, 29, 30, 31, 32, 35, 36,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, old = 30, new =42 Сортировка в окне: 28, 29, 31, 32, 35, 36, 42,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, old = 31, new =43 Сортировка в окне: 28, 29, 32, 35, 36, 42, 43,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, old = 32, new =39 Сортировка в окне: 28, 29, 35, 36, 39, 42, 43,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, old = 28, new =35 Сортировка в окне: 29, 35, 35, 36, 39, 42, 43,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36, Сортировка в окне: 35, 36, 39, 42, 43,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36, 39, Сортировка в окне: 35, 39, 43,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36, 39, 39, Сортировка в окне: 35,
Исходный массив: : 20, 21, 22, 23, 19, 20, 21, 27, 28, 29, 30, 31, 32, 28, 29, 35, 36, 42, 43, 39, 35,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36, 39, 39, 35,
Сравнение скользящей медианы и скользящего среднего на интенсивной импульсной помехе проведено с помощью следующей программы:
function print_a($a, $name){
print("$name: ");
foreach($a as $item){
printf("%3d, ",$item);
}
}
function slide_median($h, $a){
$size = count($a);
$result = [];
$slide = [];
array_push($slide, reset($a));
array_push($result,$slide[0]);
for($i=1; $i<=$h; $i++){
array_push($slide, next($a), next($a));
sort($slide);
array_push($result, $slide[$i]);
}
for($i=0; $i < $size-2*$h-1; $i++){
$old = $a[$i];
$new = $a[$i+2*$h+1];
if($old < $new){
for($key = 0; $key <= 2*$h; $key++){
if($new < $slide[$key]){
break;
}
if(($old <= $slide[$key])&&($slide[$key] < $new)) $slide[$key] = $slide[$key+1];
}
$slide[$key-1] = $new;
}
if($old > $new){
for($key = 2*$h; $key >= 0; $key--){
if($new > $slide[$key]){
break;
}
if(($old >= $slide[$key])&&($slide[$key] > $new)) $slide[$key] = $slide[$key-1];
}
$slide[$key+1] = $new;
}
array_push($result, $slide[$h]);
}
for($i = $h-1; $i > 0; $i--){
$slide = array_slice($a, $size-2*$i-1, 2*$i+1);
sort($slide);
array_push($result, $slide[$i]);
}
$slide = [$a[$size-1]];
array_push($result, $slide[0]);
print_a($a, "
Исходный массив ");
print_a($result, "
Массив медиан ");
return $result;
};
function slide_average($h, $a){
$size = count($a);
$b = array_merge([0], $a);
$sum = reset($a);
$result = [$sum];
for($i=1; $i<=$h; $i++){
$sum += next($a)+next($a);
$average = (int)($sum/(2*$i+1)+.5);
array_push($result, $average);
}
reset($b);
for($i=0; $i < $size-2*$h-1; $i++){
$sum += next($a) - next($b);
$average = (int)($sum/(2*$h+1)+.5);
array_push($result, $average);
}
for($i = $h-1; $i >=0; $i--){
$sum -= (next($b) + next($b));
$average = (int)($sum/(2*$i+1)+.5);
array_push($result, $average);
}
print_a($a, "
Исходный массив ");
print_a($result, "
Массив средних ");
return $result;
};
$a = range(200, 240);
foreach($a as &$item){
$item += 50*mt_rand(-1,1)*(int)(mt_rand(0,149)/100);
}
slide_median(3, $a);
slide_average(3, $a);
Результаты:
Исходный массив : 200, 201, 202, 203, 204, 155, 206, 207, 208, 209, 210, 211, 212, 213, 264, 265, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 183, 234, 235, 236, 287, 238, 239, 240,
Массив медиан : 200, 201, 202, 202, 203, 204, 206, 207, 208, 209, 210, 211, 212, 213, 216, 217, 218, 219, 219, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 229, 230, 231, 232, 234, 235, 236, 238, 239, 239, 240,
Исходный массив : 200, 201, 202, 203, 204, 155, 206, 207, 208, 209, 210, 211, 212, 213, 264, 265, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 183, 234, 235, 236, 287, 238, 239, 240,
Массив средних : 200, 201, 202, 196, 197, 198, 199, 200, 201, 209, 210, 218, 226, 227, 228, 229, 230, 231, 225, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 223, 224, 225, 226, 234, 235, 236, 244, 248, 239, 240,
Видно, что скользящая медиана лучше сглаживает интенсивные случайные выбросы данных.
Для данных из реального массива (x,y округлялись до целых):
Обработка массива x80c48
Исходный массив : 10790, 10728, 10565, 10228, 10148, 9911, 9861, 9880, 9887, 9894, 9907, 9910, 9917, 9932, 9937, 9925, 9900, 9684, 9579, 9446, 9040, 8912, 8703, 8457, 8350, 8338, 8129, 8040, 7900, 7836, 7731, 7490, 7271, 7250, 7165, 7013, 6912, 6848, 6823, 6857, 6868, 6894, 6902, 6903, 6904, 7114, 7067, 7047, 6994, 6883, 6848, 6787, 6722, 6412, 6236, 6136, 6012, 5991, 5659, 5648, 5595, 5327, 5079, 5015, 4678, 4639, 4569, 4294, 4241, 4164, 4137, 3948, 3905, 3771, 3731, 3664, 3577, 3422, 3304, 3086, 3053, 2977, 2967, 3248, 3257, 3202, 2954, 2834, 2594, 2574, 2611, 2730, 2766, 2514, 2387, 2368, 2365, 2344, 2312, 2098, 1905, 1722, 1579, 1233, 1206, 963, 815, 825,
Массив медиан : 10790, 10728, 10565, 10228, 10148, 9911, 9894, 9894, 9894, 9894, 9907, 9910, 9917, 9917, 9917, 9917, 9900, 9684, 9579, 9446, 9040, 8912, 8703, 8457, 8350, 8338, 8129, 8040, 7900, 7836, 7731, 7490, 7271, 7250, 7165, 7013, 6912, 6868, 6868, 6868, 6868, 6894, 6902, 6903, 6904, 6994, 6994, 6994, 6994, 6883, 6848, 6787, 6722, 6412, 6236, 6136, 6012, 5991, 5659, 5648, 5595, 5327, 5079, 5015, 4678, 4639, 4569, 4294, 4241, 4164, 4137, 3948, 3905, 3771, 3731, 3664, 3577, 3422, 3304, 3086, 3086, 3086, 3086, 3053, 2977, 2967, 2954, 2834, 2730, 2730, 2611, 2594, 2574, 2514, 2387, 2368, 2365, 2344, 2312, 2098, 1905, 1722, 1579, 1233, 1206, 963, 825, 825,
Исходный массив : 10790, 10728, 10565, 10228, 10148, 9911, 9861, 9880, 9887, 9894, 9907, 9910, 9917, 9932, 9937, 9925, 9900, 9684, 9579, 9446, 9040, 8912, 8703, 8457, 8350, 8338, 8129, 8040, 7900, 7836, 7731, 7490, 7271, 7250, 7165, 7013, 6912, 6848, 6823, 6857, 6868, 6894, 6902, 6903, 6904, 7114, 7067, 7047, 6994, 6883, 6848, 6787, 6722, 6412, 6236, 6136, 6012, 5991, 5659, 5648, 5595, 5327, 5079, 5015, 4678, 4639, 4569, 4294, 4241, 4164, 4137, 3948, 3905, 3771, 3731, 3664, 3577, 3422, 3304, 3086, 3053, 2977, 2967, 3248, 3257, 3202, 2954, 2834, 2594, 2574, 2611, 2730, 2766, 2514, 2387, 2368, 2365, 2344, 2312, 2098, 1905, 1722, 1579, 1233, 1206, 963, 815, 825,
Массив средних : 10790, 10694, 10492, 10319, 10189, 10069, 9973, 9927, 9893, 9894, 9904, 9912, 9917, 9918, 9886, 9839, 9772, 9644, 9498, 9323, 9117, 8927, 8749, 8561, 8418, 8274, 8150, 8046, 7923, 7771, 7645, 7520, 7394, 7262, 7136, 7040, 6981, 6927, 6888, 6872, 6871, 6879, 6920, 6950, 6976, 6990, 6987, 6980, 6963, 6907, 6813, 6697, 6575, 6450, 6328, 6167, 6013, 5897, 5767, 5616, 5473, 5286, 5140, 4986, 4800, 4645, 4514, 4389, 4285, 4180, 4066, 3985, 3903, 3819, 3717, 3625, 3508, 3405, 3298, 3198, 3151, 3127, 3113, 3094, 3063, 3008, 2952, 2861, 2786, 2723, 2660, 2597, 2564, 2534, 2496, 2437, 2341, 2254, 2159, 2046, 1885, 1722, 1529, 1346, 1192, 1008, 868, 825,
Обработка массива y80c48
Исходный массив : 7289, 7275, 7243, 7178, 7163, 7119, 7109, 6903, 6785, 6680, 6448, 6379, 6264, 5869, 5709, 5448, 5353, 5083, 5081, 5083, 5063, 5062, 5042, 5166, 5186, 5172, 4916, 4925, 4982, 5009, 5025, 5007, 4993, 4991, 4986, 4976, 4968, 4964, 4962, 4636, 4488, 4148, 4038, 4029, 4010, 3960, 3798, 3709, 3462, 3475, 3480, 3489, 3498, 3542, 3567, 3581, 3598, 3586, 3647, 3649, 3656, 3693, 3727, 3736, 3782, 3788, 3797, 3831, 3837, 3743, 3710, 3550, 3511, 3406, 3379, 3435, 3520, 3455, 3367, 3204, 3179, 3123, 3115, 2534, 2519, 2472, 2351, 2281, 2141, 2129, 2066, 1862, 1801, 1522, 1302, 1218, 1200, 1038, 851, 812, 778, 746, 721, 621, 529, 420, 386, 279,
Массив медиан : 7289, 7275, 7243, 7178, 7163, 7119, 7109, 6903, 6785, 6680, 6448, 6379, 6264, 5869, 5709, 5448, 5353, 5083, 5083, 5081, 5081, 5081, 5083, 5063, 5062, 5042, 5009, 5009, 5007, 4993, 4993, 4993, 4993, 4991, 4986, 4976, 4968, 4964, 4962, 4636, 4488, 4148, 4038, 4029, 4010, 3960, 3798, 3709, 3489, 3489, 3489, 3489, 3498, 3542, 3567, 3581, 3586, 3598, 3647, 3649, 3656, 3693, 3727, 3736, 3782, 3788, 3788, 3788, 3788, 3743, 3710, 3550, 3511, 3511, 3455, 3435, 3406, 3379, 3367, 3204, 3179, 3123, 3115, 2534, 2519, 2472, 2351, 2281, 2141, 2129, 2066, 1862, 1801, 1522, 1302, 1218, 1200, 1038, 851, 812, 778, 746, 721, 621, 529, 420, 386, 279,
Исходный массив : 7289, 7275, 7243, 7178, 7163, 7119, 7109, 6903, 6785, 6680, 6448, 6379, 6264, 5869, 5709, 5448, 5353, 5083, 5081, 5083, 5063, 5062, 5042, 5166, 5186, 5172, 4916, 4925, 4982, 5009, 5025, 5007, 4993, 4991, 4986, 4976, 4968, 4964, 4962, 4636, 4488, 4148, 4038, 4029, 4010, 3960, 3798, 3709, 3462, 3475, 3480, 3489, 3498, 3542, 3567, 3581, 3598, 3586, 3647, 3649, 3656, 3693, 3727, 3736, 3782, 3788, 3797, 3831, 3837, 3743, 3710, 3550, 3511, 3406, 3379, 3435, 3520, 3455, 3367, 3204, 3179, 3123, 3115, 2534, 2519, 2472, 2351, 2281, 2141, 2129, 2066, 1862, 1801, 1522, 1302, 1218, 1200, 1038, 851, 812, 778, 746, 721, 621, 529, 420, 386, 279,
Массив средних : 7289, 7269, 7230, 7197, 7141, 7071, 6991, 6887, 6775, 6653, 6475, 6305, 6114, 5924, 5729, 5544, 5375, 5260, 5168, 5110, 5083, 5098, 5111, 5087, 5067, 5056, 5051, 5031, 5005, 4980, 4990, 4999, 4998, 4992, 4984, 4977, 4926, 4854, 4735, 4601, 4466, 4330, 4187, 4067, 3956, 3858, 3778, 3699, 3625, 3559, 3522, 3502, 3519, 3536, 3552, 3574, 3596, 3612, 3630, 3651, 3671, 3699, 3719, 3740, 3765, 3785, 3788, 3784, 3751, 3711, 3655, 3591, 3533, 3502, 3465, 3439, 3395, 3363, 3326, 3280, 3140, 3006, 2878, 2756, 2628, 2488, 2347, 2280, 2186, 2090, 1972, 1832, 1700, 1567, 1420, 1276, 1135, 1028, 949, 878, 795, 723, 661, 600, 529, 447, 362, 279,
По сравнению с алгоритмом скользящего среднего, скользящая медиана намного аккуратнее обращается с данными.
Есть перевод статьи на английский язык
Комментариев нет:
Отправить комментарий