ИССЛЕДОВАНИЕ КЛАСТЕРНО-ОРИЕНТИРОВАННЫХ ПОДХОДОВ К ОБНАРУЖЕНИЮ ОСТАНОВОК ТРАЕКТОРИЙ В УСЛОВИЯХ ЗАШУМЛЕННОСТИ ДАННЫХ, И РАЗРАБОТКА АЛГОРИТМА ПО ЭФФЕКТИВНОМУ ОБНАРУЖЕНИЮ И СЖАТИЮ КЛАСТЕРОВ ОСТАНОВОК
Оглавление 2
Введение 3
Существующие решения 5
Траектории 5
Остановки и Движения (Stops and Moves) 5
Кластеризация 6
Примеры эффективных алгоритмов 8
Шумные точки 11
Предлагаемый алгоритм 14
Реализация, псевдокод 18
Создание кластеров 20
Объединение кластеров 21
Удаление лишних точек 22
Корректировка границ 23
Визуальная демонстрация работы алгоритма 25
Математическая оценка работы алгоритма 30
1. Определение типа точек 32
2. Нахождение остановок 32
3. Точность определения точек остановки 33
4. Общий анализ 34
Заключение 35
Список литературы 36
Приложение
В последние годы стали популярны и востребованы мобильные приложения, отслеживающие траекторию движения владельца. Современные технологии используют комбинации различных техник: GPS, сети Wi-Fi, Bluetooth и определение физического положения телефона - вместе они найти наиболее точную информацию о местоположении человека в различные моменты при максимальной экономии энергии.
Однако часто получаемой информации недостаточно или же она имеет неудобный для пользователя формат: может мешать зашумленность, переизбыток точек или может существовать необходимость определить продолжительные остановки.
Благодаря востребованности темы было разработано множество различных техник и алгоритмов для анализа и обработки траекторий, в том числе и обнаружение остановок при различных условиях. Большая часть алгоритмов успешно используют слегка измененные алгоритмы кластеризации точек типа DBSCAN, часто анализируют не только пространственные характеристики точек, но и временные. В результате наиболее последние работы опираются в первую очередь на характеристику скорости передвижения для изначального объединения в кластеры.
Но в реальных условиях главной сложностью нередко оказывается правильная обработка возникающего шума. В частности, изначальная проблема, ставшая основания для создания данной работы, заключается в случаях чрезвычайно высокой зашумленности траектории во время продолжительных остановок пользователя. Например, при перемещении исключительно внутри одного здания может быть создано множество ошибочных точек, находящихся далеко от здания. Это сильно мешает как понимаю данных пользователем, так и обработке траектории для различных целей.
Существующие алгоритмы не готовы к такой степени зашумленности и не способны охватить все шумные точки остановки, а иногда и целые остановки.
Таким образом, существует потребность в создании алгоритма, который способен очистить траекторию от сильно зашумленных точек, появляющихся при продолжительных остановках, и улучшить таким образом ее читаемость и полезность для обработки. Для решения данной задачи может быть необходимо находить остановки траектории и определять, является ли та или иная точка шумом.
Таким образом, эта работа ставит перед собой задачу по решению конкретной проблемы: сильная зашумленность точек на продолжительных остановках, превращающая траекторию в нечитаемый набор точек. Для этого необходимо найти или создать алгоритм, способный:
• Определять продолжительные остановки на траектории передвижения пользователя
• Определять, является ли точка шумом, и использовать эту информацию для создания и дополнения остановок
В первую очередь требуется провести исследование соответствующей литературы и статей на близкую тематику для нахождения нужных или близких алгоритмов и подходов. После чего - использовать лучшие найденные идеи и принципы, дополнить и улучшить их при необходимости, и создать на основе полученных данных полноценный алгоритм, выполняющий поставленную задачу.
Поскольку целевые шумные точки как правило появляются лишь на остановках, главной концепцией алгоритма является именно нахождение этих остановок и определение точек, принадлежащих им. Определение типа точек - вспомогательная концепция алгоритма.
В результате изучения существующих материалов и их дополнения, был разработан алгоритм, успешно справляющийся с поставленной задачей: упрощение траектории для понимания и обработки путем обнаружения и замены точек, принадлежащих остановкам. В первую очередь алгоритм исправляет нечитаемые для человека сильно зашумленные остановки с точками, разбросанными на большие расстояния от действительного местоположения.
При крайне успешной работе с продолжительными и зашумленными остановками, алгоритм способен допустить незначительные ошибки при определении небольших или нетипичных остановок. Поэтому рекомендуется использовать алгоритм не как самостоятельное и окончательное решение для работы над траекториями и остановками, а как эффективную узконаправленную часть более масштабной системы обработки траекторий.
