DBSCAN - это мощный алгоритм кластеризации, используемый в различных приложениях машинного обучения. Широкий спектр исследований был сосредоточен на кластеризации географических точек интереса (POI) без присмотра взрослых. Большинство существующих подходов используют координаты DBSCAN в качестве входных данных, но не включают другие функции в процессе кластеризации.
В этой статье мы представляем многофункциональную модель геокластеризации с помощью DBSCAN, позволяющую использовать больше функций, чем единственное местоположение. Мы представляем пример приложения, предполагающего, что этот подход в некоторых случаях может работать лучше.
Как работает DBSCAN
DBSCAN означает Пространственная кластеризация приложений с шумом на основе плотности. Это алгоритм кластеризации на основе плотности. Другими словами, он группирует вместе области данных, которые плотно входят в пространство функций.
Принцип очень простой. Модель принимает два параметра: epsilon и MinPoints. Точка, вокруг которой есть MinPoints в радиусе эпсилон, будет сгруппирована с ними. Их называют основными точками. Точка, которая находится в диапазоне базовой точки, но не имеет MinPoints точек вокруг нее в диапазоне epsilon, называется пограничной точкой. Граничные точки расположены на краю кластеров. Наконец, точка, которая не находится в пределах диапазона базовой точки, объединяется отдельно и называется точкой с шумом.
В приведенном выше примере рисунка красные точки представляют собой основные точки, желтые точки представляют собой граничные точки, а синяя точка представляет собой точку шума. К концу процесса обучения каждая точка набора данных будет либо базовой точкой, либо пограничной точкой, либо точкой шума.
Плюсы
- Нет необходимости указывать количество кластеров, в отличие от k-средних
- Формы кластеров нет, они могут быть любой формы.
- Благодаря идее точек данных шума, DBSCAN устойчив к выбросам.
Минусы
- epsilon и MinPoints зависят от домена, и их может быть сложно настроить
- Метрику расстояния, используемую для поиска соседей, бывает сложно определить.
- Не подходит для кластеров с различной плотностью, так как эпсилон исправлен (см. ОПТИКА, улучшенная версия DBSCAN, исправляющая эту проблему)
Приложение для геокластеризации
Широко распространенное применение DBSCAN - это географическая кластеризация, цель которой состоит в кластеризации географических точек, имеющих географические координаты широта и долгота. Подход довольно прост и приводит к хорошим визуальным результатам, представленным в этом новаторском сообщении в блоге.
Данные, используемые для обучения, представляют собой набор координат. Они конвертируются в радианы и передаются в DBSCAN. В модели используется формула Хаверсинус для вычисления расстояний между двумя точками. В этой ситуации параметр эпсилон имеет значение, поскольку он представляет собой, например, физическое расстояние в километрах.
Но очень часто наборы данных состоят из большего количества функций, чем широта и долгота. Если они интегрированы и преобразованы в радианы, параметр эпсилон больше не представляет физическое расстояние, и его становится труднее настроить, а также становится трудно интерпретируемым. Однако многие приложения заинтересованы в интеграции дополнительных функций в процесс кластеризации, как мы увидим ниже.
Многофункциональная модель
Матрицы расстояний
В DBSCAN для определения расстояния между точками данных обычно используются такие метрики, как евклидово расстояние или гаверсинус (для данных координат). Но вместо того, чтобы передавать имя расстояния для вычисления расстояния между точками, можно ввести предварительно вычисленную матрицу расстояний в DBSCAN.
В этом контексте можно разработать настраиваемую матрицу расстояний, объединяющую несколько типов объектов с системой взвешивания, отражающей важность каждого объекта на расстоянии между точками.
Модель
Модель вычисляет взвешенную сумму предварительно вычисленных матриц расстояний для каждого объекта X. Индексы i и j представляют пару точек данных. Каждую матрицу функций n следует масштабировать в [0,1], поскольку они могут быть не все изначально в одном диапазоне значений. Веса n, обозначенные как w, представляют вклад пространственных объектов в окончательную матрицу расстояний D. Они должны суммировать до одного. Окончательная матрица расстояний имеет расстояния в [0,1], поэтому в этом интервале также следует выбирать эпсилон.
Эта модель особенно хорошо подходит для интеграции в DBSCAN нескольких функций, которые не все имеют одну общую меру расстояния, такую как евклидово расстояние или гаверсинус. Матрицы расстояний могут быть вычислены индивидуально, затем масштабированы и их вклад в окончательное расстояние может быть взвешен.
Иллюстрация: Explorify
Многофункциональная модель родилась в контексте проекта интеллектуального анализа данных, который мы разработали для автоматического выделения областей интереса (AOI) в городах. Проект под названием Explorify направлен на автоматическое извлечение снимков в городе с использованием неконтролируемого машинного обучения и доступных данных из Flickr open API. Собранные данные состояли из трех характеристик: местоположения (широта, долгота), самого изображения и метаданных, таких как теги с комментариями автора.
DBSCAN был идеальным кандидатом для этой задачи, поскольку он широко использовался для задач AOI в литературе и предлагает отличную производительность для кластеризации на основе местоположения. В нашем контексте мы хотели, чтобы кластеры представляли области хороших фото-пятен, подтверждающих два требования: фотографии в кластере должны быть физически близко друг к другу и должны отображать связанный визуальный и семантический контент. Например, кластер, связанный с Эйфелевой башней, должен содержать фотографии, расположенные вокруг него, с тегами, относящимися к башне и, возможно, к окружающей местности. Ключевое понимание, которое мы получили, заключалось в том, что места было недостаточно для извлечения хороших кластеров.
Explorify имеет открытый исходный код и доступен на Github здесь.
Три объекта в одной матрице расстояний
- Местоположение. Имея координаты фотографий с Flickr, мы использовали метрику Хаверсинуса для вычисления матрицы расстояний между всеми парами фотографий в собранном нами наборе данных.
- Изображение. Характерное представление фотографий было извлечено из промежуточного слоя предварительно обученного VGG16. Мы утверждаем, что он обеспечивает надежное векторизованное встраивание содержимого изображения. Мы вычислили матрицу расстояний, используя косинусную несходство векторной формы фотографий.
- Теги. Они играют решающую роль, поскольку могут фиксировать семантическую информацию. Мы очистили и векторизовали их в пакет слов. Для фотографии мы перевели все ее теги на английский и использовали лемматизатор, чтобы преобразовать их в упрощенную форму слова (например, «коты» на «кошка»). Wordnet Synset использовался для удаления семантически повторяющихся тегов («рогатый скот» и «корова» могли быть объединены). В конце концов, мы использовали знаменитый метод TF-IDF для преобразования последовательности предварительно обработанных тегов в числовой вектор. Наконец, матрица расстояний была вычислена с использованием косинусного различия между векторными представлениями.
Каждая из матриц расстояний была масштабирована с использованием нормализации min-max и суммирована с весами, чтобы получить окончательную матрицу расстояний, которая будет загружена в DBSCAN.
Проверка с аннотациями
Проблема остается незамеченной, поскольку у нас нет информации о том, что представляют собой настоящие кластеры. Тем не менее, для проверки модели и поиска оптимальных гиперпараметров мы разработали инструмент аннотации, показанный ниже.
Мы попросили людей-комментаторов (самих себя) сравнить две фотографии на основе их визуального содержания, их местоположения и метаданных, таких как теги. У них есть два варианта: либо они нажимают тот же кластер, либо другой. При выборе первого варианта создается метка, в которой говорится, что две фотографии должны содержаться в одном кластере, а во втором варианте - нет.
Для проверки кластеров DBSCAN мы вычислили метрику оценки следующим образом. Сначала мы перебираем файлы аннотаций и вычисляем соотношение sA правильно сгруппированных пар. Затем мы перебираем кластеры и вычисляем соотношение sC пар внутри них, которые правильно предсказаны. Первая стратегия действует как отзыв, а вторая - как точность. Итоговая оценка s - это среднее гармоническое значение между отношениями, которое дает окончательную метрику производительности в [0,1].
Эта метрика помогает настраивать гиперпараметры (параметры DBSCAN и веса w вклада функции) с поиском по сетке.
Количественные результаты
Мы выполнили поиск по сетке значений параметров w₁ / w₂ / w₃ и DBSCAN (epsilon и MinPoints). Для каждой комбинации мы оценили нашу настраиваемую метрику оценки кластеризации, определенную выше. Оптимальный баланс грузов показан в следующей таблице. Как мы видим, в нашем случае и с учетом наших аннотаций комбинация всех функций (первая строка, где ни один из w₁ / w₂ / w₃ не равен нулю) работает лучше всего по сравнению с конфигурацией одной функции (остальные строки). Обратите внимание, что сами по себе теги уже работают отлично.
Качественные результаты
Визуально мы замечаем согласованные фотографии внутри кластеров. Модель может кластеризовать один и тот же семантический контент, даже если они визуально различаются.
На рисунке ниже мы обнаружили скопление Эйфелевой башни с фотографиями, обрезанными по-разному, почти закрытыми статуей и в разных цветовых наборах.
Мы также обнаружили скопление, раскинувшееся вдоль берегов Сены, с фотографиями различных зданий.
И, глядя на карту, мы замечаем, что фотографии из одного и того же кластера (представленные булавкой одного цвета) либо близки (как Триумфальная арка), либо более разбросаны, но последовательны (как берега Сены).
Этот эксперимент позволил нам поверить, что на самом деле помогает не только местоположение, но и фотографии и теги.
Заключение
Эта модель усиливает силу DBSCAN, комбинируя местоположение и другие функции, такие как изображение и теги, в качестве входных данных для задачи кластеризации. Но это может быть распространено на многие другие функции, если возможно вычисление матрицы расстояний.
Впервые Explorify был инициирован в 2017 году Тхань Тхао Чыонг и Шарлоттой Ламуш во время хакатона Data Science Hackathon в Шанхае. Позже в 2020 году мы разработали эту многофункциональную модель в Технологическом институте Джорджии с помощью Аниша Хегде, Джорджа Джейкоба, Донгсук Лим, Кристофера Щербана и Шафа-Ат А Шейха. Я хотел бы поблагодарить их всех за их вклад.
