DevGang
Авторизоваться

Кластеризация траектории GPS с помощью Python 

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

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

В этой статье я приведу краткое введение в быструю кластеризацию траекторий GPS. В этом решении используются библиотеки Python с открытым исходным кодом. Как правило, при кластеризации траекторий может возникнуть несколько проблем.

  1. Траектории GPS часто содержат много точек данных. Кластеризация может занять много времени.
  2. Соответствующие меры сходства необходимы для сравнения различных траекторий.
  3. Кластерный подход и настройка
  4. Визуализация траекторий и их скоплений

На эту тему есть ряд интересных статей. Однако решены не все вышеперечисленные проблемы. В этой статье я проиллюстрирую решение Python, охватывающее все эти области. Используемые здесь данные взяты из набора данных по энергии транспортного средства. Сначала к исходным данным был применен процесс кластеризации всех точек GPS. Затем я выбрал траектории для нескольких начально-конечных групп. Для простоты данные, представленные в этой статье, относятся к этим группам траекторий, как показано ниже:

Уменьшение точек данных траектории

Алгоритм Рамера-Дугласа-Пекера (RDP) - один из самых популярных методов уменьшения количества точек в ломаной линии. Цель этого алгоритма - найти подмножество точек для представления всей ломаной линии.

def rdp_with_index(points, indices, epsilon):
    """rdp with returned point indices
    """
    dmax, index = 0.0, 0
    for i in range(1, len(points) - 1):
        d = point_line_distance(points[i], points[0], points[-1])
        if d > dmax:
            dmax, index = d, i
    if dmax >= epsilon:
        first_points, first_indices = rdp_with_index(points[:index+1], indices[:index+1], epsilon)
        second_points, second_indices = rdp_with_index(points[index:], indices[index:], epsilon)
        results = first_points[:-1] + second_points
        results_indices = first_indices[:-1] + second_indices
    else:
        results, results_indices = [points[0], points[-1]], [indices[0], indices[-1]]
    return results, results_indices

Параметр epsilon здесь установлен равным 10 (метрам). После RDP количество точек данных на траекториях значительно уменьшается по сравнению с исходными точками данных.

traj #    data points original       after RDP
0         266                        21
1         276                        36
2         239                        34
...

Это способствует резкому сокращению времени вычисления матрицы расстояний.

distance matrix without RDP: 	 61.0960 seconds
distance matrix with RDP: 	 0.4899 seconds

Меры сходства траекторий и матрица расстояний

Существуют различные методы измерения сходства двух траекторий, например, расстояние Фреше, метод площади, как показано на следующем рисунке. Они могут быть рассчитаны с использованием пакета similaritymeasures.

В примерах в этой статье расстояние Фреше используется для вычисления матрицы расстояний, как показано ниже. Также поддерживается мера сходства по площади.

def compute_distance_matrix(trajectories, method="Frechet"):
    """
    :param method: "Frechet" or "Area"
    """
    n = len(trajectories)
    dist_m = np.zeros((n, n))
    for i in range(n - 1):
        p = trajectories[i]
        for j in range(i + 1, n):
            q = trajectories[j]
            if method == "Frechet":
                dist_m[i, j] = similaritymeasures.frechet_dist(p, q)
            else:
                dist_m[i, j] = similaritymeasures.area_between_two_curves(p, q)
            dist_m[j, i] = dist_m[i, j]
    return dist_m

DBSCAN кластеризация

Scikit-learn предоставляет несколько методов кластеризации. В этой статье я представляю DBSCAN с предварительно вычисленной матрицей. Параметры устанавливаются следующим образом:

  1. eps: 1000 (м) для расстояния Фреше, 300000 (м²) для измерения площади.
  2. min_samples: 1, чтобы убедиться, что все траектории будут сгруппированы в кластер.

Код приведен ниже.

def clustering_by_dbscan(distance_matrix, eps=1000):
    """
    :param eps: unit m for Frechet distance, m^2 for Area
    """
    cl = DBSCAN(eps=eps, min_samples=1, metric='precomputed')
    cl.fit(distance_matrix)
    return cl.labels_

Результаты и визуализация траектории

Matplotlib - это комплексная библиотека для визуализации на Python. Он предоставляет гибкие решения как для статической, так и для анимированной визуализации.

Результаты кластеризации для шести групп визуализируются с помощью подзаголовков в Matplotlib. Как показано ниже, большинство групп траекторий состоит из нескольких кластеров. Только две последние группы имеют один кластер по той причине, что сходство этих траекторий велико (расстояния Фреше меньше eps, т.е. 1000).

#Python
Комментарии
Чтобы оставить комментарий, необходимо авторизоваться

Присоединяйся в тусовку

Поделитесь своим опытом, расскажите о новом инструменте, библиотеке или фреймворке. Для этого не обязательно становится постоянным автором.

Попробовать

Оплатив хостинг 25$ в подарок вы получите 100$ на счет

Получить