Метод кластеризации на основе плотности, который обрабатывает шум и представляет кластеры несферической формы.

DBSCAN: приложение пространственной кластеризации на основе плотности с шумом.

Иерархическая кластеризация и кластеризация K-средних не могут идентифицировать выбросы. DBScan может идентифицировать выбросы.

Терминология:

  1. Эпсилон — Радиус круга
  2. min_sample
  3. основная точка
  4. Пограничный пункт
  5. Точка шума

  1. Epsilon — Радиус круга вокруг точки данных, значение эпсилон определяется пользователем
  2. min_sample — нам нужно указать, сколько точек данных будет в круге
  3. Основная точка — основная точка — это эта точка данных, если вокруг этой точки данных нарисован круг, он должен удовлетворять критериям минимальной выборки. Он должен иметь минимум точек данных, которых в данном случае 3. точка данных, вокруг которой нарисован круг, также учитывается в критериях минимальной выборки.
  4. Точка границы — точка границы является точкой данных, если вокруг этой точки данных нарисован круг. если он не нарисован вокруг этой точки данных. если он не удовлетворяет критериям минимальной выборки, это означает, что в круге меньше точек данных, чем критерии минимальной выборки, в этом случае точка B имеет только две точки внутри круга. но точка, вокруг которой рисуется круг, должна находиться в круге другой точки данных, только тогда мы можем сказать, что это граничная точка. Есть два условия для пограничного пункта. во-первых, в круге должно быть меньше точек данных, чем указано в критериях минимальной выборки. а во-вторых, одна и та же точка данных должна находиться в кругу другой точки данных.
  5. Точка шума — эта точка не является частью какого-либо другого кластера и не удовлетворяет критериям минимальной выборки, в этом случае точка C не удовлетворяет критериям минимальной выборки, и точка не находится в круге или кластере любой другой точки данных. Точка шума называется выбросом.
  • Каждая точка данных будет иметь тот же радиус, который прошел для значения эпсилон.

Недостатки K-средних и иерархической кластеризации

Недостатки кластеризации K-средних:-

  • Метод разделения: - Разделение набора данных на k Количество групп. разделение представляет собой итеративный процесс, в ходе которого каждая точка данных набора данных распределяется по группе, к которой она принадлежит. После распределения баллов среднее значение группы рассчитывается путем взятия среднего значения для всех баллов в группе. Самый известный метод разбиения — k-средних.
  • Существенные недостатки метода разделов:
  1. Алгоритм k-средних требует указания количества кластеров
  2. k-средние плохо работают при поиске выпуклых/несферических форм кластеров.
  3. K-средние чувствительны к шумовым данным.
  4. DBScan-Везде, где есть плотность, будет рассматривать это как кластер.

Недостатки иерархической кластеризации:-

  1. он не подходит для больших наборов данных, которые имеют высокую вычислительную сложность.
  2. Нужна метрика объединения кластера (Linkage), влияющая на результаты кластеризации.
  3. Чувствителен к шуму.

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

DBSCAN:-

DBSCAN — это метод кластеризации на основе плотности, который обнаруживает кластеры данных несферической формы. Метод кластеризации DBScan может представлять кластеры произвольной формы и обрабатывать шум.

Если нет линейно разделимых данных, k-средние и иерархическая кластеризация не будут работать. В этом случае DBSCAN преуспеет.

Параметры DBSCAN: ε (или eps или epsilon)

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

точка x и ее соседи будут в одной окрестности, а y и ее соседи в конце концов будут в другой, однако точки x и y и ее соседи, вероятно, будут в одном кластере, тогда как точка y и ее соседи будут считаться выбросами или шум.

Это связано с тем, что окрестность y недостаточно плотна, поскольку окрестность содержит больше точек, чем плотнее она становится.

Как определить, что окрестности достаточно плотные? Для этого DBSCAN использует параметр minpts.

Minpts:- Окрестность считается плотной, если она включает по крайней мере точки Minpts в своей ε-окрестности, где Minpts — порог плотности. В пределах такой окрестности точки, соответствующие этому критерию, считаются опорными точками.

Давайте проверим изображения. Если параметры Minpts равны 3. Точка x будет основной точкой, потому что размер ее окрестности ε равен 9, а ее точка y больше 3 не будет основной точкой, потому что ее окрестности ε содержат две точки

Количество точек в ε окрестности точки x содержит само себя.

Пограничная точка: - окрестность пограничной точки ε, которая содержит меньше точек Minpts (поэтому это не основная точка). но он принадлежит окрестности ε другой центральной точки. Если точка не является основной точкой и не является граничной точкой, это точка шума или выброс.

Мы можем видеть, что x является центральной точкой. У нее более 11 точек в ее окрестности ε.

Точка y не является центральной точкой, потому что в ее окрестности ε меньше 11 точек, но поскольку она принадлежит окрестности ε точки x, а точка x является центральной точкой, точка y является граничной точкой. мы можем легко увидеть, что точка z не является основной точкой y, а точка y не является основной точкой, поэтому точка z является точкой шума.

Плотность связана:-

Точка x является плотностью, связанной с точкой y, если существует точка o, плотность которой и x, и y достижима таким образом, что DBScan соединяет основные объекты и их соседей в плотном регионе.

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

Как выбрать Эпсилон?

  • Оценка параметров: - Если эпсилон имеет небольшое значение, многие точки могут считаться выбросами. Они не будут основными точками (окрестность ε будет очень маленькой). Большое значение ε может привести к тому, что огромное количество точек окажется в одном кластере.

Как оценивать модели кластеризации?

  1. Оценка силуэта
  2. Индекс Рэнда
  3. Индекс Жаккорда

Оценка Силхотта более точна, чем индекс Рэнда и оценка Жаккорда.

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

Оценка силуэта варьируется от -1 до 1, где -1 — наихудшая возможная оценка, а 1 — наилучшая оценка. Оценка силуэта 0 предполагает перекрывающиеся кластеры

Эту оценку силуэта можно использовать также для оценки любых других моделей кластеризации.

Параметры

Алгоритм DBScan требует передачи двух параметров:

  1. eps: — Один из способов найти значение Eps основан на графике k-расстояний.
  2. Minpts: - Минимальное количество соседей (точек данных) в радиусе eps. Чем больше наборы данных, тем больше значение minpts должно быть выбрано. Как правило, минимальные minpts могут быть получены из количества измерений D в наборе данных как Minpts≥D+1. Минимальное значение minpts должно быть не менее 3. Это всего лишь основное эмпирическое правило. Минимальное значение minpt 3 будет хорошим. Размер D означает функции или столбцы.