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

  • K-means clustering - итеративный алгоритм кластеризации, в котором заданный набор точек данных сгруппирован в k кластеров. число k должно быть указано нами (т.е. мы должны иметь представление о количестве кластеров).
  • Иерархическая кластеризация - каждая точка данных назначается отдельным собственным кластерам. Затем две самые близкие точки берутся вместе и образуют кластер. Этот процесс продолжается до тех пор, пока все точки не будут сгруппированы в 1 кластер. Во время этого процесса мы можем решить, какое количество кластеров нам нужно.

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

Как работает алгоритм DBSCAN?

Основные гиперпараметры:

Есть 2 основных гиперпараметра.

  1. epsilon (eps) - максимальный радиус окрестности определяется epsilon. Это максимальное расстояние между двумя точками данных, при котором они могут считаться соседями друг друга.
  2. минимальные точки - минимальное количество точек данных, которые должны существовать в эпсилон-окрестности для определения кластера. то есть, если количество точек данных, которые существуют на расстоянии не более eps от конкретной точки данных, больше, чем это число, то эти точки данных могут образовывать кластер или плотную область.

минимальные точки = 3, eps = 2. Как видно, плотность (количество точек данных в окрестности эпсилон) = 5. Поскольку плотность ›минимальные точки, это кластер.

Каждая точка данных классифицируется по одному из 3 типов алгоритма, как описано ниже.

Основные моменты:

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

Пограничные пункты:

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

Выброс:

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

На следующей диаграмме показаны три типа точек данных. считайте минимальные точки = 3, eps = 2.

Достигаемая плотность:

точка данных y считается достижимой по плотности из другой точки данных x, если существует путь P1,… .Pn с P1 = x и Pn = y, где каждое Pi включено путь является основной точкой с возможным исключением для Pn. Например, на приведенной выше диаграмме a - это достижимая плотность от d. путь равно d, c, b, a.

Непосредственно достижимая плотность:

точка данных y считается непосредственно достижимой плотностью из другой точки данных x, если x - это основная точка, а y находится в эпсилон-окрестности x. y не обязательно основная точка. Например, на приведенной выше диаграмме b непосредственно достижимая плотность из c и a непосредственно достижимая плотность из b.

Шаги алгоритма:

  1. Выберите случайную точку, которая еще не была назначена кластеру или обозначена как выброс. Затем определите его как ключевой момент или выброс.
  2. После определения базовой точки добавьте все точки, непосредственно достижимые по плотности из этой точки в ее кластер. Затем перейдите к каждой точке в окрестности эпсилона и добавьте их в кластер.
  3. Повторяйте эти шаги, пока все точки не будут назначены кластеру или помечены как выбросы.

Простая реализация DBSCAN доступна здесь: Реализация DBSCAN