В данном проекте рассматривается применение алгоритма Label Spreading для разделения города на отдельные районы на основе дорожного графа. Реализация алгоритма выполнена без использования готовой библиотеки, с опорой на описание подхода, представленное в статье от Ozon на Хабре: Как алгоритмы на графах помогают собирать группы
Алгоритм берет начальные данные о некоторых узлах графа с заранее известными метками (то есть эти узлы принадлежит к определённым классам) и стремится распространить эту информацию на все остальные узлы. Для этого он:
- Из структуры графа формирует матрицу смежности, отражающую связи между узлами.
A = nx.adjacency_matrix(G).todense() - Затем вычисляется степень каждого узла (количество связанных с ним рёбер):
d = np.array(A.sum(axis=1)).flatten()- На основе степеней узлов создаётся диагональная матрица для нормализации:
D = np.diagflat(1 / np.sqrt(d))- В итоге матрица смежности нормализуется с учётом степеней узлов, формируя матрицу похожести S:
S = D @ A @ D # @ - умножение матриц- Инициализация матрицы начальных меток Y0:
Y0 = np.zeros((len(G.nodes), 2))
Y0[node_to_index[fixed_labels[0]], 0] = 1
Y0[node_to_index[fixed_labels[1]], 1] = 1 Здесь Y0 — матрица размера (число_узлов x 2), где 2 соответствует количеству классов. В примере обозначено два узла с известными метками: одному присваивается метка класса 0, другому — класса 1. Остальные узлы изначально не имеют меток (нули).
- Копируем начальные метки в переменную Y для последующей итеративной обработки, а Y_history будет хранить историю изменений меток на каждом шаге:
Y = np.array(Y0)
Y_history = [Y.copy()]- Основной цикл распространения меток:
for _ in range(num_iterations):
Y = alpha * S @ Y + (1 - alpha) * Y0
Y_history.append(np.array(Y)) На каждом шаге используем формулу распространения меток.
- S @ Y — умножение нормализованной матрицы похожести S на текущие метки Y, которое перераспределяет информацию о классовой принадлежности по графу.
- alpha * S @ Y — весомое влияние меток с предыдущего шага.
- (1 - alpha) * Y0 — возвращение к исходным «якорным» меткам, чтобы алгоритм не "уходил" слишком далеко от начальных данных. Каждая итерация приближает итоговое распределение меток к устойчивому состоянию, а Y_history фиксирует эти изменения для дальнейшего анализа. В конце возвращается Y_history, чтобы можно было проследить процесс эволюции меток.
В функции create_graph_osm введите название города, который вы хотите кластеризовать. Например:
def create_graph_osm(place_name="Murom, Russia"):- Запустите файл main.py.
- Программа предложит выбрать две точки на графе, которые будут начальной основой для кластеризации.
- После запуска на экране отобразится граф дорожной сети города.
- Выберите две точки, кликнув по ним мышью. Красным цветом будут выделены выбранные точки.
После выбора точек программа предложит выбрать один из двух режимов работы:
- Кластеризация по итерациям:
Этот режим позволяет наблюдать процесс работы алгоритма шаг за шагом. Введите количество итераций для кластеризации. Укажите интервал (в миллисекундах) между кадрами анимации. После ввода параметров запустится анимация, где будет отображаться изменение меток на каждом шаге.
- Готовая кластеризация:
Этот режим сразу выведет итоговый результат после 100 итераций работы алгоритма. Итоговая визуализация покажет результат кластеризации с учетом выбранных начальных точек.
Граф может не полностью кластеризоваться если вы указали малое кол-во итераций. Красные точки указывают на первую группу точек. Синие на другую группу. Черные - это точки без меток, тобеж не кластеризированные. Фиолетовые - это те точки, которые могут войти и в красную и в синюю группу.
Альтернативная визуализация
В коде есть закомментированный альтернативный метод plot_graph_live, который показывает процесс кластеризации с более точной визуализацией. В этом варианте точки изменяют свой размер в зависимости от их меток.
Если вы хотите использовать его вместо текущего метода, замените plot_graph_live в коде на закомментированную версию.
Алгоритм может доработаться путём увеличения кол-во точек.
