Кластерный анализ - это метод машинного обучения без учителя, который разделяет точки данных на кластеры или группы, так что все точки данных в одном кластере / группе имеют схожие атрибуты или характеристики. Существует четыре основных категории кластерного анализа: методы разделения (K-средних), иерархические методы (BIRCH), методы на основе плотности (DBSCAN) и методы на основе сетки.

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

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

Алгоритм DBSCAN использует два основных параметра:

  • minPts: минимальное количество точек (порог), сгруппированных вместе, чтобы регион считался плотным, то есть минимальное количество точек данных, которые могут образовывать кластер.
  • eps (ε): мера расстояния, которая будет использоваться для определения точек в окрестности любой точки.

Алгоритм заботится о двух концепциях, называемых Density Reachability и Density Connectivity.

  • Плотность достижимости: точка, которую нужно достичь из другой точки, если она находится на определенном расстоянии (eps) от нее, что указывает на степень доступности кластера.
  • Связность по плотности: DBSCAN использует подход цепочки на основе транзитивности для определения того, находятся ли точки в определенном кластере. Например, точки a и d могут быть соединены, если a- ›b-› c- ›d, где p-› q означает, что q находится в окрестности p.

В этом методе есть три разных типа точек данных:

  1. Основная точка данных: точка данных, имеющая как минимум «minPts» в пределах расстояния «ε».
  2. Граничная точка данных: точка данных, которая находится на расстоянии в пределах «ε» от основной точки данных, но не является основной точкой.
  3. Точка данных шума: точка данных, которая не является ни основной, ни пограничной точкой данных.

Алгоритмические шаги для кластеризации DBSCAN

  1. Первоначально он начинается со случайной непосещенной начальной точки данных. Все точки на расстоянии «» классифицируются как точки соседства.
  2. Для запуска процесса кластеризации требуется минимальное количество точек minPts в соседстве. В противном случае точка помечается как «Шум».
  3. Все точки на расстоянии ‘’ становятся частью одного кластера. Повторите процедуру для всех новых точек, добавленных в группу кластера. Продолжайте, пока он не посетит и не пометит каждую точку в окрестности «» кластера.
  4. По завершении процесса он снова начинается с новой непосещенной точки, что приводит к обнаружению большего количества кластеров или шума. В конце процесса вы должны отметить каждую точку как кластер или шум.

Теперь давайте реализуем то же самое, используя образец набора данных из sklearn.datasets и модуля DBSCAN с ε равным 0,3 и minPts равным 10.

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

Теперь возникает вопрос: «А как же DBSCAN, когда у нас есть более простые алгоритмы в качестве k-средних?»
Алгоритмы K-средних имеют тенденцию формировать только сферические кластеры. Это не удается, когда данные не являются сферическими по своей природе, то есть одинаково изменчивы во всех направлениях. Наряду с этим K-средство чувствительно к выбросам, поэтому в основном небольшое изменение в точках данных может повлиять на результат кластеризации. Кроме того, DBSCAN определяет количество кластеров самостоятельно, никаких предварительных знаний не требуется. В то время как это не относится к K-средним, нам необходимо определить количество кластеров «k» до моделирования.

Вы можете сослаться на код GitHub здесь: https://github.com/kavyagajjar/Clustering/blob/main/DBSCAN/Cluster_Analysis_with_DBSCAN.ipynb

Также обратитесь к этой ссылке, чтобы узнать больше о различиях между различными методами кластеризации.