Давайте сделаем: пространственная кластеризация с DBSCAN

Демонстрация того, как объединить пользовательскую метрику и байесовскую оптимизацию для настройки алгоритма пространственной кластеризации на основе плотности.

Предыстория и введение

В прошлые годы я жил через дорогу от довольно оживленного паба в жилом районе. Будучи новичком в этом районе (и в стране!) Я подумал, что это будет довольно интересный способ познакомиться как с местными жителями, так и с районом немного больше.

Что ж, точно так же, как «через дорогу» не точно описывает, насколько близко это было к дому — я мог сидеть в пабе и по-прежнему подключаться к домашнему Wi-Fi — «живой» на самом деле не соответствует количеству дежурные посещения паба полицией.

Объективно визиты полиции имели несколько общих характеристик:

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

Если бы мы сменили шляпы обеспокоенных соседей на очки науки о данных, мы, вероятно, начали бы думать обо всей этой деятельности по-другому: у нас есть ряд похожих событий, происходящих в небольшом географическом районе. Или, другими словами, кластер! А поскольку в стране, скорее всего, есть более одного небольшого паба по соседству, вероятно, вокруг разбросано больше проблемных мест.

И это плавно подводит нас к сегодняшней теме — пространственной кластеризации.

Наша миссия, если мы решим ее принять (мы делаем): можем ли мы выявить из большого общедоступного журнала событий концентрированные кластеры преступной деятельности?

Во-первых, нам нужны некоторые данные.

Данные

Мы будем использовать данные о преступности в Великобритании, полученные с общедоступного портала¹; и, конечно же, прямо напоминаем себе, что он содержит информацию государственного сектора, лицензированную в соответствии с лицензией Open Government License v3.0., как того требуют условия лицензии².

Я загрузил и агрегировал все данные полиции за период с января 2019 года по декабрь 2019 года отдельно — вот фрагмент набора данных из ~ 6 миллионов строк:

Мое внимание привлекают три переменные — широта, долгота и тип преступления.

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

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

Давайте быстро проверим пропущенные значения:

Что касается переменных, которыми мы занимаемся, похоже, мы находимся в хорошем положении, поскольку только небольшая часть широты и долготы имеет пропущенные значения. Мы просто отбросим эти наблюдения из данных и продолжим.

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

Давайте посмотрим на распределение преступности:

Мы видим, что:

Насилие и сексуальные преступления — самые распространенные преступления в 2019 году; владение оружием наименее распространено.
Существуют разные виды краж: кража у человека, кража велосипеда, другие кражи.
Несмотря на то, что предположительно есть некоторый элемент кражи, грабеж и кража со взломом рассматриваются отдельно от кражи.
Интересно, что входит в автомобильное преступление. Могут ли это быть преступления, совершенные с использованием транспортного средства, например. инсценировать аварию обманным путем? Или, возможно, преступление, затрагивающее само транспортное средство — например. кража из автомобиля или, возможно, вандализм в отношении автомобиля? Я уверен, что немного поиска в Google может помочь, но я оставлю это для будущего Брэда, чтобы узнать.

Я упомянул, что в этом упражнении мы собираемся сосредоточиться только на одном типе преступлений — я выберу кража со взломом, так как он находится где-то посередине по объему.

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

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

Мы не будем делать ничего подобного, но об этом позже.

Мотивация и подход

Мотивация

Теперь, когда у нас есть данные о кражах со взломом за 2019 год, можем ли мы сразу увидеть какие-либо горячие точки?

Давайте создадим тепловую карту Великобритании — спасибо folium — помня, что центры городов по умолчанию будут горячими точками, поскольку мы используем необработанные данные:

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

Так что довольно резкий разрыв! Тепловые карты используют некоторую форму сглаживания — можем ли мы увидеть несколько примеров небольших кластеров?

folium отлично помогает визуализировать группы краж со взломом, но эти «кластеры», как правило, охватывают значительные области, а не узкие окрестности.

Некоторые наблюдения:

Похоже, у нас мало данных по Шотландии по сравнению с Англией, Уэльсом и Северной Ирландией.
Существует резкое разделение между сельскими и городскими районами, возможно, преувеличенное сглаживанием визуализации тепловой карты. В этом нет ничего удивительного, так как городские районы, как правило, имеют большее население, и мы смотрим на количество краж со взломом (а не на количество).
Внутри скоплений, предложенных folium, мы, возможно, можем получить более концентрированные скопления внутри.

Желаемый результат

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

В идеале наше упражнение по кластеризации будет доставлять нам небольшие, плотные кластеры краж со взломом. Эти кластеры должны быть как можно более отчетливыми (т. е. отдельными), а это означает, что вокруг каждого кластера и между ним есть четкое «пространство».

Мы также хотим, чтобы наш подход определял «оптимальное» количество кластеров, к которому мы пришли. Обоснование здесь простое: указание количества кластеров заранее не только вносит смещение, но также может привести к неправильному распределению наблюдений по кластерам.

Мы также должны позволить алгоритму рассматривать некоторые наблюдения как шум. То есть мы принимаем, что не каждая кража со взломом будет частью кластера, и, «отбрасывая» некоторые наблюдения, мы можем получить более чистые кластеры.

Наконец, мы хотим иметь возможность объяснить, как создавались кластеры и как они настраивались; то есть метрика, которую мы используем в любом потоке оптимизации, должна быть понятной и понятной.

Подход

Кластеризация будет выполняться с использованием sklearn реализации пространственной кластеризации приложений с шумом на основе плотности (DBSCAN). Этот алгоритм рассматривает кластеры как области с высокой плотностью, разделенные областями с низкой плотностью³, и требует указания двух параметров, определяющих «плотность».

Поскольку эти параметры потребуют некоторого ввода, а я не эксперт по кластеризации, я собираюсь использовать подход оптимизации для определения «оптимальной» пары параметров.

Процесс оптимизации требует выходных данных или метрики для оптимизации. Найдем параметры, минимизирующие среднее расстояние от «границы» до «центра» образующихся кластеров.

Схематично это так:

Конечно, там есть немного больше деталей.

Мы будем измерять «расстояние» между точками в облаке точек (широта, долгота). Как правило, гаверсинус расстояния используется для определения расстояния в километрах между парами координат. Это просто использовать в sklearn реализации DBSCAN, но нам понадобится собственная реализация, с которой мы будем работать, когда будем вычислять расстояния напрямую.

Мы хотим измерить расстояние от «границы» кластера до его «центра». Сначала мы определим границу кластера, используя выпуклую оболочку (подробнее об этом позже), и используем вершины оболочки в нашем среднем вычислении границы к центроиду.

Кроме того, использование только вершин выпуклой оболочки в расчете расстояния полезно в двух отношениях. (1) его легче понять и реализовать в качестве первого шага и (2) он сэкономит нам вычислительные ресурсы (мой бедный маленький ноутбук!), поскольку нам не придется вычислять расстояние до центра тяжести для всех. пограничные точки.

Пока мы этим занимаемся, мы упростим вычисление центроида кластера, чтобы он был просто средним значением всех пар координат (широта, долгота) в кластере. Обратите внимание, что это может привести к центроиду, которого на самом деле нет в данных!

Итак, с помощью наглядности:

Мы выбираем входные параметры и используем DBSCAN для кластеризации данных.
Один из полученных кластеров показан выше, синие точки представляют наблюдения в указанном кластере (кластер № 189).
Мы используем операцию выпуклой оболочки, чтобы найти выпуклую границу или границу кластера. Это показано пунктирной красной линией.
Мы вычисляем центроид как среднее значение пар (широта, долгота) в кластере. В этом случае все выглядит так, как будто мы пришли к центроиду, которого нет в данных.
Используя вершины выпуклой оболочки (то есть граничные точки), мы вычисляем среднее расстояние от вершины до центра тяжести. Мы передаем это значение в оптимизатор и проходим через обновленный выбор параметра обратно в (1).

Дьявол в деталях (алгоритма)

Давайте рассмотрим каждый компонент алгоритма немного подробнее.

Гаверсинус расстояние

Как упоминалось выше, мы можем использовать расчет расстояния по гаверсинусу для количественного определения расстояния в километрах между двумя парами координат.

Более формально:

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

Теперь, используя формулу гаверсинуса с точками на поверхности Земли, можно скрыть небольшое упрощение, которое мы сделаем: Земля не сферическая (нет, она и не плоская).

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

Математически формула гаверсинуса выглядит следующим образом:

… и благодаря отличному сообщению StackOverflow⁵ у нас есть быстрая — и векторизованная — реализация Python:

ДБСКАН

… или пространственная кластеризация приложений с шумом на основе плотности — это…

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

От sklearn :

Алгоритм DBSCAN рассматривает кластеры как области высокой плотности, разделенные областями низкой плотности. Из-за этого довольно общего представления кластеры, обнаруженные с помощью DBSCAN, могут иметь любую форму, в отличие от k-средних, которые предполагают, что кластеры имеют выпуклую форму.³

Еще одно ключевое отличие заключается в том, что DBSCAN не требует от пользователя указывать количество используемых кластеров, что становится все труднее сделать по мере того, как кластеризуемые данные становятся больше и/или сложнее.

DBSCAN принимает два параметра: epsilon и min_points, которые вместе определяют «плотность»⁷:

epsilon — это мера расстояния, которая будет использоваться для определения местоположения точек в окрестностях любой точки.
min_points — это минимальное количество точек (порог), сгруппированных вместе, чтобы область считалась плотной.

Ключевыми понятиями в DBSCAN являются основные точки и достижимость, и эти понятия объединяются для создания кластеров и фильтрации «шумовых» точек.

Опять же, в основном из Википедии⁶:

Точка P является основной точкой, если по крайней мере min_points находятся на расстоянии epsilon от P (включая саму точку P ).

Точка Q является непосредственно достижимой из точки P, если точка Q находится в пределах epsilon расстояния от точки P . До точек можно напрямую добраться только из базовых точек.

Точка R достижима из точки P, если существует путь P → Q → … → R, где каждый промежуточная точка достижима напрямую из предыдущей точки (например, Q напрямую достижима из P). Это означает, что P и все остальные точки на пути являются базовыми точками, за возможным исключением R.

Все точки, недостижимые из любой другой точки, называются «шумами» или «выбросами».

Если P является базовой точкой, она образует кластер со всеми точками (основными или неосновными), доступными из P. Каждый кластер содержит как минимум одну основную точку.

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

Достижимость не является симметричным отношением: по определению только основные точки могут достигать неосновных точек. Обратное неверно, поэтому неосновная точка может быть достижима, но из нее ничего не может быть достигнуто. Следовательно, необходимо дополнительное понятие связности, чтобы формально определить размер кластеров, найденных DBSCAN. Две точки Pи Q связаны по плотности, если существует точка Oтакая, что обе точки Pи >Qдоступны из O. Плотность связности является симметричной.

Тогда кластер удовлетворяет двум свойствам:

1. Все точки внутри кластера плотно связаны друг с другом.

2. Если точка достижима по плотности из некоторой точки кластера, она также является частью кластера⁶.

Ну, это немного нагло. Посмотрим, сможем ли мы нарисовать что-нибудь из этого!

Диаграмма слева визуально исследует концепцию «основной точки»; тот, что справа, визуализирует концепцию достижимости.

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

На что обратить внимание:

Мы можем напрямую использовать гаверсинусное расстояние в качестве меры — metric = "haversine" .
Расчет гаверсинуса требует, чтобы пары координат были указаны в радианах, а не в градусах. Мы делаем это с помощью быстрого вызова одного из моих любимых пакетов — numpy. Нам нужно убедиться, что порядок пар координат правильный, так как sklearn сначала ожидает широту.
Поскольку мы сейчас говорим в радианах, нам нужно преобразовать ввод epsilon в радианы.
Алгоритм шарового дерева используется для ускорения времени выполнения алгоритма.
Мы возвращаем метки кластера, так как это все, что нас интересует.

Теперь давайте завершим наш краткий обзор DBSCAN, вспомнив, на что следует обратить внимание, опять же с помощью Википедии⁶ (хотя акцент сделан мной).

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

Качество DBSCAN зависит от меры расстояния... Наиболее распространенной метрикой расстояния является евклидово расстояние. Особенно для многомерных данных эта метрика может оказаться почти бесполезной из-за так называемого «проклятия размерности», затрудняющего поиск подходящего значения для ε. Однако этот эффект присутствует и в любом другом алгоритме, основанном на евклидовом расстоянии.

DBSCAN не может хорошо кластеризовать наборы данных с большими различиями в плотности, поскольку комбинация min_points — epsilon не может быть выбрана надлежащим образом для всех кластеров.

Если данные и масштаб не совсем понятны, выбор осмысленного порога расстояния ε может быть затруднен.

Мы оставим здесь DBSCAN и перейдем к выпуклым оболочкам — то есть к тому, как мы строим границы нашего кластера.

Выпуклая оболочка

Как мне нравится думать об этом, двумерная выпуклая оболочка — это наименьший выпуклый многоугольник, который окружает двумерное облако точек. «Выпуклость» в данном случае просто означает, что многоугольник не имеет внутренних углов больше 180 градусов (если бы это было так, то корпус «повернулся бы» сам в себя и стал бы «вогнутым»).

В Википедии⁸ есть отличная аналогия для представления о том, как создается выпуклая оболочка: если мы хотим построить выпуклую оболочку вокруг облака точек C, мы можем представить эластичную ленту, которая растягивается вокруг C, а затем натягивается; тогда форма натянутой ленты представляет собой выпуклую оболочку. Визуально это:

Здесь мы видим, как эластичная лента сначала натягивается вокруг облака точек (фиолетовый), а затем натягивается, создавая выпуклую оболочку (красный).

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

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

Наконец, мы используем реализацию выпуклой оболочки, доступную в scipy ⁹. Эта реализация позволяет нам добраться до вершин выпуклой оболочки, а также вычислить площади и объемы оболочки.

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

Метрика: средняя вершина — расстояние до центра тяжести

Несколько слов о метрике, которую мы будем использовать для оптимизации espilon и min_points.

Подход довольно прост:

Для каждого кластера рассчитаем выпуклую оболочку.
Используя эту оболочку, мы можем идентифицировать вершины кластера; мы будем использовать нашу функцию расстояния гаверсинуса для вычисления расстояния от каждой вершины до центроида кластера.
Затем мы возьмем среднее значение расстояний между вершинами и центроидами, чтобы получить значение для каждого кластера.

Затем мы можем усреднить по всем кластерам, чтобы получить представление о том, как в целом прошла работа по кластеризации.

В идеале нам нужны небольшие и плотные кластеры. Я надеюсь, что с помощью этой метрики мы сможем выбрать оптимальную пару epsilon и min_points (то есть значений, определяющих «плотность») для достижения обеих целей. Я вполне могу ошибаться — есть один способ узнать это!

С точки зрения кода это довольно просто реализовать:

Внимательные читатели заметят, что подход к кластерам с менее чем тремя точками немного отличается — это связано с тем, что ConvexHull требует трех или более точек для построения выпуклой оболочки.

Оптимизация

И последнее, но не менее важное слово об оптимизации или о том, как мы будем выбирать epsilon и min_points.

Мы собираемся использовать мой любимый алгоритм оптимизации — байесовскую оптимизацию¹⁰. Это действительно мощная структура, которая позволяет нам оптимизировать любую функцию черного ящика и не ограничивается оптимизацией моделей машинного обучения.

Ранее я рассказывал, как работает оптимизация здесь, но схематически мы можем представить это следующим образом:

Некоторые результаты

Хватит болтовни — пора подводить итоги, не так ли? Верно!

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

Лучшие итерации выделены фиолетовым текстом. Здесь мы видим, что среднее расстояние вершина-центроид составляет 40 м и получается, когда epsilon = 100m и min_points = 4 (в фоновом режиме я конвертирую значения с плавающей запятой min_samples в целые числа перед вводом в DBSCAN).

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

Здесь у нас большой кластер — то есть кластер с большим количеством краж со взломом — в центре Лондона (числа в кружках обозначают количество краж со взломом в непосредственной близости от кружка):

… и «меньший» кластер:

Совершенно очевидно, что кластер в центре Лондона не очень маленький (хотя и кажется достаточно плотным). Это может быть связано с конструкцией оптимизации — т. е. из-за того, что мы усредняем по ряду кластеров, несколько выпадающих значений могут быть перетянуты большим количеством меньших значений. Тем не менее, не идеальный результат для этого кластера.

Кроме того, если это распространенная проблема с некоторыми из наиболее густонаселенных кластеров, стоит ли выполнять дополнительные упражнения по кластеризации с целью разбить густонаселенные кластеры на более мелкие кластеры?

Мы не видим этой проблемы с меньшим кластером на юге Англии, так как все пять наблюдений произошли на одной и той же улице (эти бедные жители!).

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

Случаи использования

Ладно, Бред, ну и что? Как мы используем полученные кластеры? Позвольте мне объяснить.

Впервые я столкнулся с DBSCAN и идеей пространственной кластеризации в статье, посвященной навигации в реальном времени — представьте, что Google Maps предоставляет пользователям маршруты. Общая идея заключалась в том, что кластеры в этом контексте представляют собой области с интенсивным движением и замедлят продвижение в пути; в идеале алгоритм определит это и пересчитает этапы пути, чтобы обходить кластер.

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

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

Если в наших данных отсутствует информация, кластеризация может стать неотъемлемой частью процесса вменения. Представьте, что мы пытаемся понять характеристики дома; вполне разумно предположить, что дома в одном и том же (небольшом) районе (или на улице), построенные примерно в одно и то же время, будут иметь схожие характеристики. Поэтому, если мы сможем сгруппировать дома вместе, мы, вероятно, сможем сделать разумные расчеты, основанные на характеристиках домов в кластере.

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

Подведение итогов и обсуждение

Ну, этот был довольно длинным. Подведем итоги.

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

Затем мы составили рецепт алгоритма с несколькими пояснениями по пути. Функционал позволил нам:

Вычислите расстояние между двумя парами координат (широта, долгота).
Выполните кластеризацию с использованием алгоритма DBSCAN.
Рассчитайте среднее расстояние от вершины до центра кластера кластеров, созданных DBSCAN.
Используйте байесовскую оптимизацию, чтобы выбрать входные данные DBSCAN, которые минимизируют среднее среднее расстояние между вершинами и центроидами.

Мы визуализировали некоторые результаты и обсудили возможные варианты использования.

Давайте рассмотрим и обсудим несколько вещей, прежде чем мы закончим.

Общий результат

Я думаю, будет справедливо сказать, что, хотя наш подход к кластеризации работал, он дал несколько неожиданные результаты. На данный момент мы, вероятно, должны относиться к этому подходу не как к руководству «как сделать», а как к примеру «что я сделал».

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

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

Данные и вопросы, связанные с данными

Сначала особые упоминания — если вы поклонник бесплатных, интересных и высококачественных наборов данных, я настоятельно рекомендую ознакомиться с тем, что публикует правительство Великобритании. Хотя мы изучили данные о преступности, есть информация по широкому кругу тем, включая автомобильные аварии¹¹, информацию о дорожном движении¹² и COVID-19¹³.

С такими данными важно понимать, как микро- и макрособытия влияют на данные. Я специально решил использовать данные за 2019 год, так как это был последний полный год информации до COVID; Я ожидаю, что уровень краж со взломом резко упадет во время периодов блокировки COVID 2020 года, когда все оставались дома.

Мы коснулись этого ранее, но также важно понимать, как другие демографические данные (такие как численность населения и его распределение) влияют на данные. Например, при прочих равных условиях мы ожидаем, что количество краж со взломом в густонаселенных районах будет выше, чем в районах с меньшим населением, только за счет численности населения (т. е. в густонаселенных районах будет больше людей). грабить).

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

Думая с точки зрения сетки Великобритании, нам может потребоваться перейти от пар координат к почтовому индексу или нижней супервыходной области (LSOA), чтобы получить соответствующие данные о населении.

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

Близость пар координат, которые вводятся в систему данных, к реальному месту преступления может варьироваться в зависимости от типа преступления и любого вмешательства полиции, которое может потребоваться. Например, мы можем разумно предположить, что место сообщения об ограблении будет находиться на линии «угол Y-стрит и X-авеню», тогда как о кражах со взломом сообщается с очень определенной степенью точности.

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

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

Метрики оптимизации и альтернативные оптимизации

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

Ранее я упоминал, что пересмотр метрики оптимизации может дать лучшие — или более ожидаемые — результаты.

Хотя я думаю, что среднее среднее расстояние между вершинами и центроидами неплохо для первого шага, мы определенно могли бы его улучшить.

В качестве первого шага мы могли бы поэкспериментировать с использованием максимумов. Как я уже говорил выше, использование среднего значения может позволить замаскировать небольшое количество больших значений большим количеством малых значений (таким образом, распределение значений искажает среднее значение). Переключение на вычисление чего-то вроде среднего максимального расстояния между вершинами и центроидами, возможно, может привести к созданию меньших кластеров.

Конечно, мы могли бы изменить концепцию метрики. Поскольку нас интересует размер и плотность кластеров, может быть разумным переключиться на минимизацию площади кластеров. И если бы мы рассчитали площадь кластера, плотность кластера достижима — каламбур — если, скажем, мы определим плотность как количество точек кластера на единицу площади.

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

Я также должен упомянуть, что существуют более формальные методы выбора epsilon и min_points , некоторые из которых описаны в статьях, ссылки на которые приведены ниже.

Геопанды

Было бы упущением не упомянуть GeoPandas¹⁴. Если вы не знакомы с GeoPandas — я ни в коем случае не мастер в этом — это пакет Python, разработанный для упрощения работы с геопространственными данными.

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

Я должен признать, что специально решил не использовать GeoPandas, потому что я все еще знакомлюсь с такими понятиями, как системы отсчета координат, проекционные системы координат и их отношения друг к другу (или, что более важно, как перейти от одного к другому). ).

Возможно, если я вернусь к этому в будущем — или сделаю что-то подобное — я мог бы бросить себе вызов и использовать GeoPandas.

Производительность

Теперь коротко о производительности.

Я использую ноутбук довольно среднего уровня, купленный в 2017 году… это ни в коем случае не мощная машина, это точно.

Увидев огромный объем данных — ~6 млн строк в полном наборе данных о преступлениях, примерно 370 тыс. строк в наборе данных о краже со взломом — я подумал, что старым верным придется немного потрудиться, особенно с кластерными вычислениями.

Но это было не так (как ни странно!). Даже с довольно ресурсоемкой оптимизацией мое оборудование, казалось, справлялось со всем довольно хорошо — вероятно, это больше свидетельствовало о реализации алгоритмов, чем о том, что я сделал сам.

И наконец…

Если вы зашли так далеко, молодец (и спасибо за чтение!).

Вы, наверное, уже заметили, что я не говорю о нейронных сетях для разнообразия; В этой статье я нарушил недавнюю тенденцию документировать свой путь от изучения до создания нейронной сети. Если это действительно то, что щекочет ваше воображение, не бойтесь, потому что я занят работой над следующей частью (тем временем вам придется довольствоваться моим бэк-каталогом¹⁵).

Если вам нравится читать мои разглагольствования, я написал статьи по другим темам машинного обучения, таким как проектирование признаков¹⁷, оптимизация моделей LightGBM с использованием байесовской оптимизации¹⁶ и вменение пропущенных значений¹⁸.

Как всегда, я надеюсь, вам понравилось читать это так же, как мне понравилось писать. Увидимся в следующий раз!

Ссылки