Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,916

МЕТОД ОЦЕНКИ ЭФФЕКТИВНОСТИ ФИЛЬТРАЦИИ ГЕОКООРДИНАТ

Головков А.А. 1 Иванова Г.С. 1
1 Московский государственный технический университет имени Н.Э. Баумана
Мобильные устройства в настоящее время активно используются в областях логистики, технического обслуживания и производства. Ключевые возможности геоинформационных систем (ГИС) в данных сферах позволяют выполнять мониторинг перемещений и координировать действия полевых сотрудников, что тесно связано со сбором, обработкой, хранением, передачей и визуализацией геоданных. Модели и методы фильтрации данных местоположения, ориентированные на мобильные операционные системы, зачастую основаны на обработке информации в реальном времени. Их проектирование и разработка, а также экспериментальная оценка эффективности представляют собой нетривиальную задачу. Данная статья посвящена разработке метода оценки эффективности фильтрации геокоординат. В работе рассмотрены траектории движения, построенные по геоданным перемещаемых мобильных устройств, и предложен метод оценки качества фильтрации, основанный на определении значения функции ошибки, которая сравнивает временную и пространственную идентичность реального маршрута и траектории движения после фильтрации. Одной из особенностей метода является линейное время вычисления функции ошибки, что позволяет применять ее в качестве целевой функции при тренировке моделей машинного обучения в задачах фильтрации геокоординат в том числе в переносимых мобильных устройствах.
геоданные
функция ошибки
фильтрация
ГИС
траектория движения
оценка эффективности
1. Головков А.А. Источники геоданных в мобильных устройствах / А.А. Головков // Динамика сложных систем – XXI век. – 2017. – № 4. – С. 94–101.
2. Головков А.А., Иванова Г.С. Адаптивная фильтрация потока геолокационных данных в реальном времени // Наука и Образование. МГТУ им. Н.Э. Баумана. Электрон. журн. – 2016. – № 4 [Электронный ресурс]. URL: http://technomag.edu.ru/jour/article/download/10/12 (дата обращения: 30.03.2018).
3. Макаренко Г.К. Исследование алгоритма фильтрации при определении координат объекта по сигналам спутниковых радионавигационных систем / Г.К. Макаренко, А.М. Алешечкин // Доклады Томского государственного университета систем управления и радиоэлектроники. – 2012. – № 2–2 (26). – С. 15–18.
4. Прохорцов А.В. Методы определения координат и скорости подвижных объектов с помощью спутниковых радионавигационных систем / В.В. Савельев, А.В. Прохорцов // Известия Тульского государственного университета. Технические науки. – 2011. – № 2. – С. 264–274.
5. Jaime Gomez-Gil, Ruben Ruiz-Gonzalez, Sergio Alonso-Garcia, Francisco Javier Gomez-Gil. A Kalman Filter Implementation for Precision Improvement in Low-Cost GPS Positioning of Tractors // Sensors. – 2013. – no. 13. – Р. 15307–15323.
6. Салычев О.С. MEMS/GPS – малогабаритная интегрированная навигационная система / О.С. Салычев // Геопрофи. – 2013. – № 3. – С. 16–17.
7. Weiliang Zeng, Tomio Miwa, Takayuki Morikawa. Exploring Trip Fuel Consumption by machine Learning from GPS and CAN Bus Data // Journal of the Eastern Asia Society for Transportation Studies. – 2015. – vol. 11. – Р. 906–921.
8. Huiqin Li, Gang Wu. Map Matching for Taxi GPS Data with Extreme Learning Machine // Advanced Data Mining and Applications: 10th International Conference proceedings. – 2014. – Р. 447–460.
9. Katherine Ellis, Suneeta Godbole, Simon Marshall, Gert Lanckriet, John Staudenmayer, Jacqueline Kerr. Identifying active travel behaviours in challenging environments using GPS, accelerometers, and machine learning algorithms // Frontiers in Public Health. – 2014. – vol. 2. – Р. 1–8.
10. Christian Manasseh, Raja Sengupta. Predicting driver destination using machine learning techniques // 16th International IEEE Conference on Intelligent Transportation Systems. – 2013. – Р. 142–147.
11. Abhishek Goswami, Luis E. Ortiz, Samir R. Das. WiGEM: a learning-based approach for indoor localization // CoNEXT ‘11 Proceedings of the Seventh COnference on emerging Networking EXperiments and Technologies, 2011.

В настоящее время мобильные устройства широко используются в различных областях логистики, технического обслуживания и производства. Ключевые возможности геоинформационных систем (ГИС) в данных сферах позволяют выполнять мониторинг перемещений и координировать действия полевых сотрудников, что тесно связано со сбором, обработкой и хранением геоданных, поступающих с мобильных устройств [1–3]. Важность и актуальность задач обработки геолокационной информации обусловлена высокими требованиями к геоинформационным системам в различных областях применения [4–6].

Стратегия разделения ответственности по обработке геоинформации в ГИС, когда приоритет отдается мобильным приложениям, является предпочтительной. В этом случае существенно снижается нагрузка на серверную часть и уменьшается объем передаваемых данных, что в случае плохого соединения с сетью или полного отсутствия связи является ключевым фактором. Такая стратегия позволяет реализовать потоковую обработку данных в реальном времени на мобильном устройстве, что даст возможность получить высокоточные данные местоположения настолько быстро, насколько это возможно. Это, несомненно, важно для ГИС, которые предполагают немедленное реагирование на различные ситуации на основе данных местоположения.

Модели и методы фильтрации геоданных зачастую основаны на обработке информации в реальном времени [1, 2]. Их проектирование и разработка, а также экспериментальная оценка эффективности представляют собой нетривиальную задачу [7, 8]. Для оценки качества фильтрации обычно используют такую характеристику, как функцию ошибки, которую конструируют исходя из оценки идентичности целевой функции (целевого, реального маршрута, Ground Truth) и предсказаний классификатора или траектории движения на выходе фильтрации, учитывая специфику предметной области, таким образом, чтобы ошибка была максимально достоверной для данной конкретной задачи [9–11]. Значение функции ошибки должно уменьшаться с увеличением качества работы модели. При этом решая задачу минимизации функции, возможно найти оптимальные параметры модели. В качестве функции ошибки наряду с евклидовой метрикой часто используют кросс-энтропию или функцию потерь Хьюбера.

Определение функции ошибки

Рассматривая задачу фильтрации геокоординат, целевой маршрут можно представить в виде ломаной линии, заданной вектором кортежей. Каждый кортеж состоит из набора параметров: времени, широты и долготы, которые определяют точку в трехмерном пространстве:

gol01.wmf (1)

Траектория движения, полученная после фильтрации, также представляет собой ломаную:

gol02.wmf (2)

Особенностью такого представления является то, что количество элементов в векторах LgroundTruth и Lpredicted в общем случае может быть разным. Координаты широты lati(latj) и долготы loni(lonj) могут быть также разными в обеих ломаных. Только по параметру ti(tj) возможно однозначно определить две точки, соответствующие одному и тому же времени. По этому параметру существует некая неравномерная дискретизация координат: каждой единице времени tk соответствует не менее одного кортежа gol03.wmf в векторах LgroundTruth и Lpredicted. То есть возможны случаи, когда:

- gol04.wmf

- gol05.wmf

- gol06.wmf

Задача оценки качества фильтрации сводится к сравнению идентичности двух ломаных LgroundTruth и Lpredicted функцией ошибки gol07.wmf как по пространственным координатам lati и loni, так и по временным ti. Чем больше различаются ломаные, тем больше должно быть значение ошибки Eloss и наоборот. В общем случае gol08.wmf. При этом известно, что ломаные изначально так расположены в пространстве, что Eloss = min, так как всегда рассматривается одна и та же реальная траектория движения. Вектор Lpredicted в случае идеальной фильтрации должен совпадать с LgroundTruth, и Eloss = 0.

Идентичность ломаных в данном контексте следует понимать как степень соответствия каждой точки Lpredicted с соответствующей точкой в LgroundTruth. Степень подобия в отличие от идентичности не будет адекватной оценкой, поскольку ломаные могут быть схожи с высоким показателем подобия, однако расположены далеко друг от друга, при этом значение ошибки будет мало, что неверно.

Задача конструирования Eloss усложняется тем, что координаты точек на ломаных lati, loni и latj, lonj – это геокоординаты в замкнутом пространстве, эллипсоиде, а не точки на плоскости. Расстояние от точки до прямой здесь определяется дугой. Перевод геокоординат в прямоугольную систему координат может добавить существенную погрешность определения значения функции ошибки.

Конструирование функции ошибки

Рассмотрим возможные решения задачи нахождения максимально достоверной функции Eloss.

1. Ковариационный анализ. Метод предполагает составление матрицы ковариации между распределенными величинами, которые являются координатами точек на двух ломаных Lpredicted и LgroundTruth. После составления матрицы анализируются коэффициенты корреляции. По их значениям возможно определить степень идентичности двух ломаных, однако метод применим только в случае одинаковой дискретизации точек на ломаных, что в данном случае неверно.

2. Анализ Фурье и сравнение спектров. Проблема здесь аналогична п. 1. Для ее разрешения возможно аппроксимировать дискретные функции gol09.wmf на интервалах времени t + dt непрерывными функциями для каждой ломаной, выполнить передискретизацию по времени и сравнить непрерывные функции ковариационным анализом, анализом Фурье или простым вычислением интеграла разницы функций на интервалах t + dt. Однако определение значения dt для максимально достоверной оценки представляет собой нетривиальную задачу. Дело в том, что ломаные могут описывать окружности на больших интервалах времени, и в таком случае аппроксимация не имеет смысла. На малых интервалах возможна большая погрешность вычисления ошибки Eloss.

Предложим три подхода, основанные на векторном представлении ломаных. Первый определяет Eloss как разницу сумм изменения углов направления по двум ломаным. Второй подход заключается в сдвиге всех векторов в начало координат и подсчете разницы общих площадей под двумя ломаными. Однако в обоих случаях оценка может быть недостоверна, так как возможно построить два различных трека с нулевой ошибкой Eloss. Третий подход предполагает попарное сравнение векторов, но здесь появляется проблема дискретизации.

Все рассмотренные подходы с высокой степенью недостоверности вычисляют ошибку Eloss. Для декомпозиции задачи попробуем выделить частные случаи анализа двух ломаных. Допустим, моменту времени tk соответствуют две точки на обеих ломаных, то есть:

gol10.wmf

gol77a.wmf

и gol78.wmf.

Ошибка здесь очевидно пропорциональна расстоянию между двумя точками gol12.wmf и gol13.wmf в метрах:

gol14.wmf (3)

где D – функция расстояния между точками gol15.wmf и gol16.wmf.

Рассмотрим второй случай, когда

gol17.wmf

или

gol18.wmf

gol19.wmf,

то есть для момента времени tk существует только одна точка на одной из ломаных. Выполнение любого из условий сводится к одной и той же задаче, поэтому далее будем рассматривать точку gol20.wmf на одной ломаной (LgroundTruth или Lpredicted), для которой нет соответствующей точки на другой ломаной (Lpredicted или LgroundTruth). Ошибка здесь пропорциональна расстоянию от точки xk на первой ломаной до точки на второй ломаной gol21.wmf в метрах, которая на самом деле отсутствует:

gol22.wmf (4)

Эту точку целесообразно определить как местоположение на второй ломаной в момент времени tk. За gol23.wmf можно взять существующую точку на второй ломаной, ближайшую к моменту времени tk. Однако данный подход может существенно увеличить погрешность определения итоговой ошибки Eloss, так как ближайшая точка по времени может располагаться на значительном расстоянии от xk. Для нивелирования погрешности следует учитывать разницу во времени, что представляет собой нетривиальную задачу.

Второй способ определения gol24.wmf заключается в нахождении на второй ломаной двух точек gol79.wmf и gol80.wmf, предыдущей и следующей по отношению к моменту времени tk. Такой подход привнесет в определение ошибки Eloss не только оценку пространственной идентичности ломаных, но и временной. Следует учитывать, что в начале и/или в конце трека на одной из ломанных может не быть точек xl и/или xl+1. В этом случае ошибка пропорциональна расстоянию до существующей точки xl или xl+1:

gol26.wmf, (5)

gol27.wmf. (6)

Если обе точки присутствуют на ломаной, имеем треугольник с геокоординатами xl, xl+1 и xk, и ошибка определяется как

gol28.wmf, (7)

где D' – функция расстояния между точкой xk и дугой, составленной из точек xl и xl+1.

Рассмотрим подходы для определения функции D'.

1. Определение D' и gol29.wmf по скорости. В качестве gol30.wmf здесь рассматривается точка, которая находится на отрезке gol31.wmf, на расстоянии dl,k от xl. При этом dl,k – расстояние, которое возможно преодолеть за время gol32.wmf со скоростью spdl. Время tl здесь соответствует кортежу gol33.wmf, spdl – моментальная скорость в точке xl. Итоговая ошибка определяется расстоянием между xk и gol34.wmf:

gol35.wmf (8)

Однако скорость spdl может быть определена с большой погрешностью; движение в интервале времени от tl до tk может быть неравномерным, что предполагает учет ненулевого ускорения и/или градиентов ускорения, погрешность вычисления которых может лишь расти по отношению к погрешности определения spdl. В результате накопленная ошибка для gol37.wmf может быть значительна.

2. Определение D' как длины кратчайшего отрезка дуги от точки xk до отрезка дуги gol38.wmf. При этом необходимо рассмотреть случаи, когда:

- точка gol39.wmf на дуге gol40.wmf, которая лежит на кратчайшем отрезке дуги, не лежит на отрезке дуги gol41.wmf. В этом случае в качестве gol42.wmf следует использовать расстояние до ближайшей точки:

gol43.wmf. (9)

- точка gol44.wmf на дуге gol45.wmf, которая лежит на кратчайшем отрезке дуги, лежит на отрезке дуги gol46.wmf. В этом случае ошибка пропорциональна кратчайшему расстоянию:

gol47.wmf. (10)

3. Определение D' как разницы расстояний. Данный подход предполагает расчет D' как разницы суммы расстояний от xl до xk, от xk до xl+1 и от xl до xl+1:

gol48.wmf. (11)

Иллюстрация приведена на рисунке.

golov1.tif

Иллюстрация расчета значения D' как разницы расстояний

Прямые между точками на рисунке эквивалентны дугам. Функция gol49.wmf отражает оценку расстояния между xk и дугой gol50.wmf. Чем меньше gol51.wmf, тем ближе точка xk к дуге gol52.wmf, чем больше – тем дальше. Если gol53.wmf, точка xk лежит на дуге.

Исходя из минимизации погрешности и трудоемкости определения функции Eloss был выбран подход, учитывающий расстояние между точками в случае присутствия обеих точек в определенный момент времени на двух ломаных Lpredicted и LgroundTruth и разницу расстояний между точками (см. п. 3 выше) в противном случае.

Поскольку ошибка может быть неабсолютной величиной и не должна в общем случае отражать какие-либо параметры траектории движения, например сумму отклонений расстояний и др., знаки пропорциональности в формулах (1) и (9) заменим на знаки равенства. Общая ошибка Eloss будет являться квадратным корнем из среднеквадратической ошибки модели – отношения суммы квадратов расстояний gol54.wmf или gol55.wmf в зависимости от наличия или отсутствия обеих точек на двух ломаных соответственно к количеству точек:

gol56.wmf (12)

где gol57.wmf, так как вычисление ошибки должно быть выполнено для каждой точки ломаных Lpredicted и LgroundTruth;

gol58.wmf, при условии, что gol59.wmf и gol60.wmf. В противном случае, когда на одной из ломаных нет точки в момент ti, т.е. gol61.wmf и gol62.wmf или gol63.wmf и gol64.wmf

gol65.wmf:

- gol66.wmf, при gol67.wmf, gol68.wmf, если gol69.wmf;

- gol70.wmf, при gol71.wmf, gol72.wmf, если gol73.wmf;

- gol74.wmf, при gol75.wmf иgol76.wmf.

Стоит отметить, что алгоритм вычисления значения функции ошибки для одной траектории выполнится за линейное время, и его вычислительная сложность

gol77.wmf (11)

Заключение

В работе предложен метод расчета функции ошибки для оценки качества фильтрации геокоординат. Рассмотренный метод учитывает как оценку пространственной идентичности траекторий движения, так и временной, учитывая специфику предметной области задачи. Преимуществом метода является линейное время вычисления функции ошибки, что позволяет использовать его в качестве целевой функции при тренировке моделей машинного обучения в задачах фильтрации геокоординат, в том числе в переносимых мобильных устройствах. В качестве недостатка метода стоит отметить отсутствие учета метрики пространства в случае сравнения близости точки к отрезку дуги. Принимая во внимание скоростные и временные показатели движения, возможно сделать оценку более достоверной.


Библиографическая ссылка

Головков А.А., Иванова Г.С. МЕТОД ОЦЕНКИ ЭФФЕКТИВНОСТИ ФИЛЬТРАЦИИ ГЕОКООРДИНАТ // Современные наукоемкие технологии. – 2018. – № 5. – С. 51-55;
URL: http://top-technologies.ru/ru/article/view?id=36990 (дата обращения: 01.04.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074