Куда поехать в пятницу вечером, если ты в Питере. Сравнение алгоритмов геокластеризации
Всем привет, меня зовут Максим Шаланкин, в Ситимобил я занимаюсь машинным обучением. Мы постоянно принимаем решения на основе больших данных. Даже в пятницу вечером мы доверяем алгоритмам выбор места отдыха. А кто же, если не наши клиенты, лучше всего знают, где в Санкт-Петербурге можно хорошо отдохнуть?
Мы хотим найти зоны, куда чаще всего приезжают наши клиенты в пятницу вечером (точка «Б» маршрута). Для этого мы будем изучать реальные поездки в промежутке с 17 до 24 часов. В качестве примера данных возьмём небольшой фрагмент из n поездок. И при помощи алгоритмов кластеризации проанализируем точки «Б» (широта и долгота) и характер их группирования.
Выбор алгоритмов
Кластеризация — задача машинного обучения без учителя, когда метки истинных классов заранее не определены. Цель кластеризации — разбить множество объектов на плотные подгруппы (определить структуру в данных). Ожидается, что объекты внутри каждой подгруппы будут схожи между собой. Существует много алгоритмов кластеризации. Их можно разделить по ключевому способу обнаружения кластеров:
кластеризация на основе центров масс (centroid-based);
иерархическая кластеризация (hierarchical-based);
кластеризация на основе плотности распределения данных (density-based);
кластеризация по виду распределения данных (distribution-based).
а также:
графовая кластеризация (graph-based);
кластеризация на основе сетки (grid-based);
фрактальная кластеризация (fractal-based);
квантовая кластеризация (quantum-based).
и другие.
Мы попробуем решить нашу задачу первыми четырьмя алгоритмами, так как тестировать все виды будет слишком трудозатратно, и наверняка нашу проблему решит один из первых четырёх алгоритмов.
Как понять, что выбраны правильные кластеры?
Самое трудное в кластеризации — не построить кластеры, а понять, что они означают. Оценивают чаще всего экспертно, в зависимости от задачи. Смотрят на характеристики тех объектов, которые попали в один кластер и делают выводы.
Но есть несколько метрик, которые также помогут с интерпретацией кластеров. Поскольку мы заранее не знаем ни количество кластеров, ни истинных меток для каждой точки, выбор метрик качества кластеризации сильно ограничен. Мы будем пользоваться следующими четырьмя метриками:
Average within cluster sum of squares
Оценка расстояния от точек до центра кластера. Чем больше значение метрики, тем выше дисперсия точек в рамках одного кластера (и тем хуже для нас). Мы будем усреднять эти величины для финальной метрики. Она может работать хуже, когда в данных есть выбросы.
# python реализация
import numpy as np
def wcss_score(X, labels):
"""
Parameters
----------
X : array-like of shape (n_samples, n_features)
A list of ``n_features``-dimensional data points. Each row corresponds
to a single data point.
labels : array-like of shape (n_samples,)
Predicted labels for each sample.
Returns
-------
score: float
The resulting average within cluster sum of Squares
"""
total_wcss = 0
unique_labels = np.unique(labels)
for cluster_label in unique_labels:
cluster_indexes = np.where(labels == cluster_label)[0]
total_wcss += np.sum(np.linalg.norm(np.mean(X[cluster_indexes], axis=0) - X[cluster_indexes], axis=1))
return total_wcss / len(unique_labels)Average silhouette score
Показывает, насколько объекты внутри одного кластера похожи друг на друга в сравнении с объектами других кластеров. Если значение близко к единице, то наши точки явно разделимы. Значение около нуля означает, что полученные кластеры могут пересекаться, а значение -1 означает, что мы ошиблись в выборе меток кластеров.
В библиотеке sklearn есть реализация этой метрики: from sklearn.metrics import silhouette_score.
Calinski-Harabasz index
Представляет собой отношение суммы дисперсии между кластерами и межкластерной дисперсии для всех кластеров. Чем выше значение, тем лучше произведена кластеризация.
В библиотеке sklearn есть реализация этой метрики: from sklearn.metrics import calinski_harabasz_score.
Davies-Bouldin index
Показывает среднее «сходство» кластеров: расстояние между ними сравнивается с их размером. Чем меньше значение, тем лучше произведено разделение на кластеры.
В библиотеке sklearn есть реализация этой метрики: from sklearn.metrics import davies_bouldin_score.
Все описанные метрики работают лучше всего, когда кластеры имеют выпуклую форму и отделены друг от друга. Но в реальности мы имеем совершенно иное распределение точек «Б», и поэтому ещё интереснее посмотреть на значения метрик и результаты работы каждого алгоритма.
Критерий финальной оценки звучит так: смотрим на две компоненты — метрики и интерпретируемость — и выбираем алгоритм, который максимизирует качество в каждом случае. Да, интерпретируемость — это субъективная оценка, но как иначе оценивать качество кластеризации, если не с точки зрения вашей оценки бизнес-ценности?
Пройдём последовательно по четырём группам алгоритмов и посмотрим на результат работы одного из них.
Алгоритм k-means
Кластеризация на основе центра масс данных (centroid-based).
Пожалуй, это самый известный алгоритм кластеризации. Его задача — нахождение k центров и определение их линейной разделимости. Граница кластера всегда будет идти по прямой или плоскости, что может не дать нам того результата, которого мы ожидаем от гео-кластеризации. Главный параметр алгоритма — число кластеров k. Есть много рекомендаций по его настройке, но мы воспользуемся нашими метриками для поиска оптимального значения.
Метрики Average within cluster sum of squares и Calinski-Harabasz index.Метрики Average silhouette score и Davies-Bouldin index.
По этим двум графикам можно сделать вывод, что стоит попробовать задать количество кластеров равным 10, 13 и 16. Когда мы это сделаем, получим наилучшую интерпретируемость для 16 кластеров. Рассмотрим их подробнее.
16 кластеров, полученных алгоритмом k-means.
Почему в результате работы алгоритма получились такие кластеры? Дело в том, что основные предположения о форме кластеров не соответствуют действительности. K-means работает лучше всего, когда кластеры округлой формы и одинакового размера, с одинаковой плотностью и без выбросов. Поэтому проблемы очевидны: наши предполагаемые области имеют произвольный размер с разной плотностью.
Алгоритм Agglomerative Clustering
Иерархическая кластеризация (hierarchical-based).
Алгоритмы иерархической кластеризации отличаются от предыдущего вида тем, что в первой итерации у нас будет столько же кластеров, сколько наблюдений. То есть центроидов намного больше, чем нужно. В каждой итерации мы должны пересчитывать расстояние между центроидами и объединять кластеры. Получается определённая древовидная структура, в которой мы укрупняем агрегацию от листьев к корню и получаем заданное количество кластеров k. Из-за такого итеративного пересчёта расстояний алгоритм имеет сложность O (n2) и трудно применим к очень большому набору данных.
В этом алгоритме мы также можем настраивать количество кластеров. Посчитаем итеративно наши метрики для поиска оптимального значения k.
Метрики Average within cluster sum of squares и Calinski-Harabasz index.Метрики Average silhouette score и Davies-Bouldin index.
Как и в предыдущем примере, попробуем различные варианты количества кластеров, а именно 11, 14, 17, и выберем лучший из них.
17 кластеров, полученных алгоритмом Agglomerative Clustering.
Здесь мы уже не видим таких ровных границ, как как в случае с k-means. Более того, этому алгоритму удалось разделить точки с разных берегов, хоть и не везде. Но так как алгоритм не умеет работать с выбросами в данных, мы видим особо крупные и совершенно нелогичные кластеры на западе и востоке. Возможно, следующий алгоритм справится с задачей лучше.
Алгоритм DBSCAN
Кластеризация на основе плотности распределения данных (density-based).
Этот алгоритм чаще остальных применяется для кластеризации геоданных, и не просто так. Он способен «правильно» определять области сложной формы, потому что в его основе лежит алгоритм объединения групп точек, которые являются вершинами одного связного графа. Алгоритм ищет такие группы точек, у которых расстояние между парой соседних точек не больше epsilon (первый параметр алгоритма), а самих таких точек не менее min_samples (второй параметр алгоритма). В отличие от двух предыдущих алгоритмов, DBSCAN способен обрабатывать выбросы в данных и не включать их ни в один из кластеров.
Вот такими могут получиться кластера при определенных значениях epsilon и min_samples.
Кластеры, полученные алгоритмом DBSCAN.
Некоторые выводы по полученным результатам:
Кластеры отлично повторяют границы рек и крупных каналов.
Мы не контролируем количество кластеров и максимальный размер полигона.
Результаты получились намного лучше, чем в двух предыдущих случаях. Но точно ответить на вопрос, который мы поставили в начале публикации, не получится. Мы можем сильно понизить параметр epsilon и получить 1000+ кластеров, но они всё-равно никак нам не помогут. Нам нужен ранжированный список кластеров. Конечно, можно проверить вхождение каждой точки в полученный полигон, но к чему такие сложности, если есть другой, схожий алгоритм, который может самостоятельно выдать ранжированный список.
Алгоритм KDE
Кластеризация на основе вида распределения данных (distribution-based).
(с некоторыми дополнениями)
Алгоритм ядерной оценки плотности мы уже разбирали ранее. Он способен выдавать линию уровня (определенная доля данных), форма которой зависит от используемого ядра. По умолчанию он выдаёт один полигон (наш условный кластер) за раз. Но что нам мешает выполнить k итераций получения кластеров плотности, итеративно удаляя области, которые мы выделяем? Если написать такой цикл, то мы получим следующую картину:
16 кластеров, полученных алгоритмом KDE.
Давайте сравним все алгоритмы между собой по правилам, которые написаны в начале.
Выводы по алгоритмам
Будем сравнивать по двум критериям: метрики кластеризации и экспертная оценка.
Сравнение работы всех четырёх алгоритмов.
В результате ранжирования алгоритмов по нашим ключевым метрикам они разместились в следующем порядке: DBSCAN, KDE, Agglomerative clustering, k-means. По интерпретируемости DBSCAN и KDE находятся примерно на одном уровне, но всё же DBSCAN оказался лучше, потому что в его кластеры не включена река.
Чтобы оценить наше будущее место отдыха в пятницу вечером, нам нужно получить топовые места (самая высокая плотность) с небольшим радиусом полигона (малый размер обводимой области). При построении кластеров KDE мы можем явно задавать долю наблюдений от их общего количества, а итеративность построения кластеров за нас ранжирует их в порядке частотности.
Теперь мы можем разобраться, где же лучше всего провести вечер пятницы, потому что по ранжированному списку гораздо проще сделать полезные выводы.
Как же я люблю интересные места в Питере, вот они, слева направо: Набережная реки Смоленки, кафе и рестораны Васильевского острова, Никольские ряды, Александринский театр, Невский проспект
Отлично! Алгоритм определил наше место отдыха, как значительную часть центра Санкт-Петербурга с историческими постройками, достопримечательностям и интересными заведениями. На выбор есть сразу три района: Василеостровский, Адмиралтейский и Центральный.
Мы можем прогуляться по набережной реки Смоленки, перекусить в одном из кафе Васильевского острова, заглянуть в Никольские ряды, насладиться архитектурой Александрийского театра, а потом сделать селфи на Невском проспекте.
Теперь-то мы не ошибёмся с выбором.
