Есть вот такой набор точек, каждая точка представляет собой gps координату автобуса (x,y), у каждой точки есть timestamp. На построенном графике видны явные ошибки измерения. Как их можно убрать? Решение должно быть простым, так как всего координат около 100 тысяч. Интересует идея, но желательно, чтобы ее можно было без особых проблем реализовать средствами Java Пример исходных данных: 1447037729 3054.619968 2409.828279 570d8 Первое поле - 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, "&emsp Сортировка в окне") 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, "&emsp Сортировка в окне") print_a($result, "<br>Массив результата") } 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 <br> } 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("&emsp old = $old, new =$new") print_a($slide, "&emsp Сортировка в окне") 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, "&emsp Сортировка в окне") print_a($result, " Массив результата") } $slide = [$a[$size-1]] array_push($result, $slide[0]) print_a([end($a)], "&emsp Сортировка в окне") print_a($a, "