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

Продолжаем рассматривать типовые алгоритмы кластеризации и на этом занятии речь пойдет о довольно популярном алгоритме 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 лет, дети которых живут в городах. Понятно, что эти женщины (под условным наименованием «бабушки») уезжали в город, чтобы нянчить внуков. Были группы «демобилизованные солдаты», «невесты» и некоторые другие. Вот пример того, как алгоритм кластеризации позволяет существенно упростить анализ данных, которые выполнить вручную было бы очень непростым занятием.

Видео по теме