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

Практический курс по ML: https://stepik.org/course/209247/

Продолжаем рассматривать типовые алгоритмы кластеризации и на этом занятии речь пойдет о довольно популярном алгоритме DBSCAN:

(Density-Based Spatial Clustering of Application with Noise)

Его преимуществом перед алгоритмом K-means (Ллойда), о котором мы говорили на предыдущем занятии, в том, что он позволяет выделять кластеры произвольной формы и, кроме того, сам определяет число кластеров в данных.

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

Все начинается с понятия эпсилон-окрестности объекта. Для любого вектора  в метрическом признаковом пространстве эпсилон-окрестность определяется как множество точек, отстоящих от  не более чем на :

,

где  - выбранная метрика пространства признаков (например, евклидовое расстояние).

Разумеется, параметр  мы задаем сами, как параметр работы алгоритма DBSCAN. Далее, в алгоритме на основе эпсилон-окрестности объекты делятся на три типа:

• корневой: содержащий не менее m объектов в своей эпсилон-окрестности, ;
• граничный: не корневой, но в окрестности корневого;
• шумовой (выброс): не корневой и не граничный.

Все это может показаться каким-то странным и запутанным. Какие то типы объектов? Почему именно такие? Зачем это вообще нужно? Вот поэтому данный алгоритм и основан на эвристиках, а не математике, где все строже и четче. Типы объектов – это одна из эвристик. Сейчас вы поймете, как они используются в алгоритме и зачем нужны.

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

Далее, процесс повторяется с самого начала, исключая ранее обработанные образы. Также случайно отбирается объект и формируется еще один кластер, либо шумовые образы. В итоге, после прохождения по всем объектам выборки, на выходе мы получаем разбиение данных на кластеры и шумовые образы, не вошедшие ни в один из кластеров. Причем, число кластеров было определено автоматически, исходя из заданных параметров ε и m.

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

Вход: выборка , параметры ε и m

Выход: разбиение выборки на кластеры и шумовые выбросы N

1:  - непомеченные;

2: пока в выборке есть непомеченные точки, :

3:         выбирается случайный образ

4:         если  то

5:                 образ  помечается как возможный шумовой

6:         иначе

7:                 создается новый кластер

8:                 для всех , не помеченных или шумовых

9:                       если  то

10:                       иначе пометить  как граничный кластера

11:                   для всех

12:                 

Реализацию этого алгоритма на Python можно посмотреть по ссылке:

machine_learning_34.py

В свою очередь, я его взял с сайта:

https://habr.com/ru/post/322034/

чтобы не изобретать велосипед. Конечно, если вам понадобиться использовать алгоритм DBSCAN на языке Python, то лучше воспользоваться библиотекой Scikit-Learn, в которой уже реализован этот алгоритм на уровне языка С++, а потому работает гораздо быстрее:

https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html

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

Преимущества алгоритма DBSCAN

• быстрая (по объему вычислений) реализация для больших выборок:

   - для эффективных реализаций алгоритма;

• выделяет кластеры произвольной формы;
• разделяет объекты на корневые, граничные и шумовые.

Такое деление играет важную роль, когда нам по набору данных нужно определить не только кластеры, но и объекты с нетиповым поведением (шумовые, выбросы). Например, они могут соответствовать СПАМ-рассылкам, или неестественному поведению пользователей в online-сервисах (отслеживание ботов и злоумышленников), определение неестественности текстов, например, сгенерированных компьютером и т.п. Во всех этих задачах алгоритм кластеризации нам может очень помочь как с группировкой данных по некоторым признакам, так и выделению странных, нетипичных объектов.

Чтобы все это было понятнее, приведу еще один пример из реальной жизни. В середине 90-х новосибирские социологи изучали причины массовой миграции сельского населения в города. При опросах местных жителей Алтайского края, они задавали около сотни вопросов. В результате образовался массив данных из 7000 анкет и в каждой по 100 вопросов. Перед учеными встал вопрос, как анализировать полученные данные? И, конечно же, единственно разумным решением было выполнить группировку (кластеризацию) наблюдений с помощью компьютера. Все данные были переведены в цифровой вид, поданы на вход алгоритма кластеризации и на выходе получили весьма интересные и закономерные результаты в виде семи основных групп (таксонов). Например, была выделена группа женщин в возрасте более 60 лет, дети которых живут в городах. Понятно, что эти женщины (под условным наименованием «бабушки») уезжали в город, чтобы нянчить внуков. Были группы «демобилизованные солдаты», «невесты» и некоторые другие. Вот пример того, как алгоритм кластеризации позволяет существенно упростить анализ данных, которые выполнить вручную было бы очень непростым занятием.

Практический курс по ML: https://stepik.org/course/209247/

Видео по теме

Машинное обучение. Начало

#1. Что такое машинное обучение? Обучающая выборка и признаковое пространство

#2. Постановка задачи машинного обучения

#3. Линейная модель. Понятие переобучения

#4. Способы оценивания степени переобучения моделей

#5. Уравнение гиперплоскости в задачах бинарной классификации

#6. Решение простой задачи бинарной классификации

#7. Функции потерь в задачах линейной бинарной классификации

#8. Стохастический градиентный спуск SGD и алгоритм SAG

#9. Пример использования SGD при бинарной классификации образов

#10. Оптимизаторы градиентных алгоритмов: RMSProp, AdaDelta, Adam, Nadam

#11. L2-регуляризатор. Математическое обоснование и пример работы

#12. L1-регуляризатор. Отличия между L1- и L2-регуляризаторами

#13. Логистическая регрессия. Вероятностный взгляд на машинное обучение

#14. Вероятностный взгляд на L1 и L2-регуляризаторы

#15. Формула Байеса при решении конкретных задач

#16. Байесовский вывод. Наивная байесовская классификация

#17. Гауссовский байесовский классификатор

#18. Линейный дискриминант Фишера

#19. Введение в метод опорных векторов (SVM)

#20. Реализация метода опорных векторов (SVM)

#21. Метод опорных векторов (SVM) с нелинейными ядрами

#22. Вероятностная оценка качества моделей

#23. Показатели precision и recall. F-мера

#24. Метрики качества ранжирования. ROC-кривая

#25. Метод главных компонент (Principal Component Analysis)

#26. Сокращение размерности признакового пространства с помощью PCA

#27. Сингулярное разложение и его связь с PCA

#28. Многоклассовая классификация. Методы one-vs-all и all-vs-all

#29. Метрические методы классификации. Метод k ближайших соседей

#30. Методы парзеновского окна и потенциальных функций

#31. Метрические регрессионные методы. Формула Надарая-Ватсона

#32. Задачи кластеризации. Постановка задачи

#33. Алгоритм кластеризации Ллойда (K-средних, K-means)

#34. Алгоритм кластеризации DBSCAN

#35. Агломеративная иерархическая кластеризация. Дендограмма

#36. Логические методы классификации

#37. Критерии качества для построения решающих деревьев

#38. Построение решающих деревьев жадным алгоритмом ID3

#39. Усечение (prunning) дерева, обработка пропусков и категориальных признаков

#40. Решающие деревья в задачах регрессии. Алгоритм CART

#41. Случайные деревья и случайный лес. Бутстрэп и бэггинг

#42. Введение в бустинг (boosting). Алгоритм AdaBoost при классификации

#43. Алгоритм AdaBoost в задачах регрессии

#44. Градиентный бустинг и стохастический градиентный бустинг

#45. Нейронные сети. Краткое введение в теорию

#46. Обучение нейронной сети. Алгоритм back propagation