Как мы создали алгоритм, который мог идентифицировать и различать кластеры так же интуитивно, как человеческий глаз

Заявление о проблеме

POI или Достопримечательность в нашем контексте определяется как место, где происходит большое количество посадки. Это может быть любое популярное место, такое как торговый центр, вокзал или даже большой жилой комплекс. В более ранних версиях нашего приложения, когда пользователь заказывал GO-RIDE или GO-CAR в POI, ему приходилось согласовывать с водителем точную точку посадки: опыт, который мы предлагали водителям и клиентам, был меньше чем адекватный.

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

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

Команда инженеров GO-JEK также не может вручную делать то, что можно легко автоматизировать. 😉

Наше решение

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

Для этого мы воспользовались историческими данными, которые у нас были о том, где именно клиенты выбирались из таких точек интереса. Ниже приведен пример пунктов вывоза клиентов в районе Blok M Square, торгового центра в Джакарте.

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

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

Алгоритмы кластеризации

Мы экспериментировали с различными алгоритмами кластеризации, из которых мы обсудим DBSCAN и KMeans. Хотя оба алгоритма являются неконтролируемыми, первый - это алгоритм кластеризации на основе плотности, который эффективно удаляет шум, а второй - на основе расстояния, который не учитывает шум в наборе данных.

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

DBSCAN

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

Данные геопространственного пикапа, с которыми мы имели дело, содержали обе следующие крайности:

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

Как видно из данных, реальные условия были далеки от идеальных, когда дело касалось требований к DBSCAN. Плотность перехвата почти всегда будет разной для разных точек интереса и, вероятно, будет разной для кластеров посадки в пределах одной точки интереса. Имея это в виду, обобщение алгоритма DBSCAN для всех точек интереса будет затруднительным.

В приведенном ниже примере Blok M Square алгоритм (после некоторой настройки гиперпараметров) смог идентифицировать кластеры и выбросы (точки, отмеченные серым цветом), поскольку плотность наводок во всех 5 воротах несколько униформа.

Однако, поскольку пункты выдачи для некоторых ворот более разбросаны, DBSCAN не удалось хорошо обобщить на другой торговый центр, Ciputra World, как это видно на изображении ниже.

KMeans

KMeans - это алгоритм кластеризации на основе расстояния, в котором каждая точка назначается ближайшему центру кластера. Хотя алгоритм не учитывает выбросы, он оказался гораздо более эффективным в правильной идентификации кластеров, которые DBSCAN не смог определить, как видно из изображений ниже. Для Ciputra World он правильно идентифицировал три кластера, в то время как DBSCAN не смог идентифицировать два из кластеров, поскольку датчики в этой области были относительно разбросаны.

Однако у KMeans есть один серьезный недостаток: k, или количество кластеров, должно быть входом в модель. Затем нам нужно было автоматизировать процесс точного определения значения k для каждого POI.

Подход 1: бронирование дайвинга по s2 Cell

Первоначальный подход, который был использован, заключался в разделении всех бронирований для одного POI на ячейки S2 уровня 17 (каждая из которых имеет ширину примерно 70 метров) и предполагает два кластера (т. Е. Возьмем k = 2) в каждой ячейке. Поскольку граница ячейки S2 может существовать в середине кластера, это равносильно алгоритму, рассматривающему кластер как два отдельных; по одному в каждой из соседних ячеек. Таким образом, потребуется последующий этап дедупликации, чтобы объединить любые два кластера, центры кластеров которых находятся ближе, чем на 25 метров друг от друга.

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

Подход 2: аналитическое вычисление «k»

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

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

Из графиков выше мы можем с уверенностью предположить, что значение k = 5 или k = 6 будет оптимальное значение. На этом этапе алгоритм выберет k = 6, поскольку он имеет более низкое значение WSS для аналогичного Silhouette Оценка по сравнению с k = 5. Но если посмотреть на силуэтный график для n_clusters = 6 ниже, становится очевидным, что красный кластер (пронумерованный 5) не имеет значительного количества точки данных.

Таким образом, после определения наилучшего значения k мы использовали метод Stupid Backoff, чтобы убедиться, что количество определенных кластеров действительно было оптимальным. , на основе значимости каждого кластера по отношению ко всем перехватам, соответствующим этому POI. Используя этот подход, оптимальное количество кластеров, которое было окончательно определено для Blok M Square, составило 5.

Заключение

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

Если вам это показалось интересным и вы хотите решить интересные задачи в области Data Science, присоединяйтесь к нам! Посетите gojek.jobs, чтобы узнать больше, и воспользуйтесь возможностью поработать с первым и самым быстрорастущим единорогом в Юго-Восточной Азии.