Рубрики

DBSCAN кластеризация в ML | Плотность на основе кластеризации

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

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

Кластеры — это плотные области в пространстве данных, разделенные областями с меньшей плотностью точек. Алгоритм DBSCAN основан на этом интуитивном понятии «кластеры» и «шум». Основная идея заключается в том, что для каждой точки кластера окрестность данного радиуса должна содержать как минимум минимальное количество точек.

Почему DBSCAN?
Методы разбиения (K-средних, PAM-кластеризация) и иерархическая кластеризация работают для поиска сферических или выпуклых кластеров. Другими словами, они подходят только для компактных и хорошо разделенных кластеров. Кроме того, они также сильно пострадали от присутствия шума и выбросов в данных.

Реальные данные могут содержать нарушения, например:
i) Кластеры могут иметь произвольную форму, такую как показаны на рисунке ниже.
ii) Данные могут содержать шум.

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

Алгоритм DBSCAN требует двух параметров —

  1. eps : он определяет окрестность вокруг точки данных, т. е. если расстояние между двумя точками меньше или равно «eps», то они считаются соседями. Если значение eps выбрано слишком маленьким, большая часть данных будет считаться выбросами. Если оно выбрано очень большим, кластеры будут объединены, и большинство точек данных будут находиться в одних и тех же кластерах. Один из способов найти значение eps основан на графике k-расстояния .
  2. MinPts : минимальное количество соседей (точек данных) в радиусе eps. Чем больше набор данных, тем большее значение MinPts должно быть выбрано. Как правило, минимальные значения MinPts могут быть получены из числа измерений D в наборе данных как MinPts >= D+1 . Минимальное значение MinPts должно быть выбрано не менее 3.

    In this algorithm, we have 3 types of data points.

    Core Point: A point is a core point if it has more than MinPts points within eps.
    Border Point: A point which has fewer than MinPts within eps but it is in the neighborhood of a core point.
    Noise or outlier: A point which is not a core point or border point.

Алгоритм DBSCAN можно абстрагировать в следующих шагах —

  1. Найдите все соседние точки в пределах eps и определите основные точки, которые посещали больше чем соседи MinPts.
  2. Для каждой базовой точки, если она еще не назначена кластеру, создайте новый кластер.
  3. Найдите рекурсивно все точки, связанные с его плотностью, и назначьте их тому же кластеру, что и точка ядра.
    Точка а и б , как говорят, плотности связаны , если существуют точку с , который имеет достаточное число точек в своих соседях и обеих точках а и б находятся в пределах расстояния EPS. Это цепочечный процесс. Таким образом, если b является соседом c , c является соседом d , d является соседом e , что, в свою очередь, является соседом a, означает, что b является соседом a .
  4. Выполните итерацию по оставшимся не посещенным точкам в наборе данных. Те точки, которые не принадлежат ни одному кластеру, являются шумом.

Ниже приведен алгоритм кластеризации DBSCAN в псевдокоде:

DBSCAN(dataset, eps, MinPts){
# cluster index
C = 1
for each unvisited point p in dataset {
         mark p as visited
         # find neighbors
         Neighbors N = find the neighboring points of p

         if |N|>=MinPts:
             N = N U N'
             if p' is not a member of any cluster:
                 add p' to cluster C 
}

Реализация вышеуказанного алгоритма в Python:

Здесь мы будем использовать библиотеку Python sklearn для вычисления DBSCAN. Мы также будем использовать библиотеку matplotlib.pyplot для визуализации кластеров.

Используемый набор данных можно найти здесь .

import numpy as np

from sklearn.cluster import DBSCAN

from sklearn import metrics

from sklearn.datasets.samples_generator import make_blobs

from sklearn.preprocessing import StandardScaler

from sklearn import datasets

  
# Загрузить данные в X

db = DBSCAN(eps=0.3, min_samples=10).fit(X)

core_samples_mask = np.zeros_like(db.labels_, dtype=bool)

core_samples_mask[db.core_sample_indices_] = True

labels = db.labels_

  
# Количество кластеров в метках, игнорируя шум, если присутствует.

n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)

  

print(labels)

  
# Результат сюжета

import matplotlib.pyplot as plt

  
# Черный удален и используется вместо шума.

unique_labels = set(labels)

colors = ['y', 'b', 'g', 'r']

print(colors)

for k, col in zip(unique_labels, colors):

    if k == -1:

        # Черный используется для шума.

        col = 'k'

  

    class_member_mask = (labels == k)

  

    xy = X[class_member_mask & core_samples_mask]

    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,

                                      markeredgecolor='k'

                                      markersize=6)

  

    xy = X[class_member_mask & ~core_samples_mask]

    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,

                                      markeredgecolor='k',

                                      markersize=6)

  

plt.title('number of clusters: %d' %n_clusters_)

plt.show()

Выход:

Черные точки представляют выбросы. Изменяя eps и MinPts , мы можем изменить конфигурацию кластера.

Теперь вопрос должен быть поднят:

Недостаток K-MEANS:

  1. K-средства образуют только сферические кластеры. Этот алгоритм дает сбой, когда данные не сферические (то есть одинаковые отклонения во всех направлениях).
  2. Алгоритм K-Means чувствителен к выбросам. Выбросы могут искажать кластеры в K-средних в очень большой степени.
  3. Алгоритм K-Means требует, чтобы один указывал количество кластеров в монастыре и т. Д.

По сути, алгоритм DBSCAN преодолевает все вышеупомянутые недостатки алгоритма K-Means. Алгоритм DBSCAN идентифицирует плотную область, группируя точки данных, которые закрыты друг для друга на основе измерения расстояния.

Реализацию Python вышеупомянутого алгоритма без использования библиотеки sklearn можно найти здесь dbscan_in_python .

Ссылки :
https://en.wikipedia.org/wiki/DBSCAN
https://scikit-learn.org/stable/auto_examples/cluster/plot_dbscan.html

Рекомендуемые посты:

DBSCAN кластеризация в ML | Плотность на основе кластеризации

0.00 (0%) 0 votes