Метод кластеризации на основе плотности, который обрабатывает шум и представляет кластеры несферической формы.
DBSCAN: приложение пространственной кластеризации на основе плотности с шумом.
Иерархическая кластеризация и кластеризация K-средних не могут идентифицировать выбросы. DBScan может идентифицировать выбросы.
Терминология:
- Эпсилон — Радиус круга
- min_sample
- основная точка
- Пограничный пункт
- Точка шума
- Epsilon — Радиус круга вокруг точки данных, значение эпсилон определяется пользователем
- min_sample — нам нужно указать, сколько точек данных будет в круге
- Основная точка — основная точка — это эта точка данных, если вокруг этой точки данных нарисован круг, он должен удовлетворять критериям минимальной выборки. Он должен иметь минимум точек данных, которых в данном случае 3. точка данных, вокруг которой нарисован круг, также учитывается в критериях минимальной выборки.
- Точка границы — точка границы является точкой данных, если вокруг этой точки данных нарисован круг. если он не нарисован вокруг этой точки данных. если он не удовлетворяет критериям минимальной выборки, это означает, что в круге меньше точек данных, чем критерии минимальной выборки, в этом случае точка B имеет только две точки внутри круга. но точка, вокруг которой рисуется круг, должна находиться в круге другой точки данных, только тогда мы можем сказать, что это граничная точка. Есть два условия для пограничного пункта. во-первых, в круге должно быть меньше точек данных, чем указано в критериях минимальной выборки. а во-вторых, одна и та же точка данных должна находиться в кругу другой точки данных.
- Точка шума — эта точка не является частью какого-либо другого кластера и не удовлетворяет критериям минимальной выборки, в этом случае точка C не удовлетворяет критериям минимальной выборки, и точка не находится в круге или кластере любой другой точки данных. Точка шума называется выбросом.
- Каждая точка данных будет иметь тот же радиус, который прошел для значения эпсилон.
Недостатки K-средних и иерархической кластеризации
Недостатки кластеризации K-средних:-
- Метод разделения: - Разделение набора данных на k Количество групп. разделение представляет собой итеративный процесс, в ходе которого каждая точка данных набора данных распределяется по группе, к которой она принадлежит. После распределения баллов среднее значение группы рассчитывается путем взятия среднего значения для всех баллов в группе. Самый известный метод разбиения — k-средних.
- Существенные недостатки метода разделов:
- Алгоритм k-средних требует указания количества кластеров
- k-средние плохо работают при поиске выпуклых/несферических форм кластеров.
- K-средние чувствительны к шумовым данным.
- DBScan-Везде, где есть плотность, будет рассматривать это как кластер.
Недостатки иерархической кластеризации:-
- он не подходит для больших наборов данных, которые имеют высокую вычислительную сложность.
- Нужна метрика объединения кластера (Linkage), влияющая на результаты кластеризации.
- Чувствителен к шуму.
Как мы видим, основным недостатком метода разбиения и иерархической кластеризации является обработка шума и получение плохих результатов при поиске кластеров несферической формы.
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 в приведенном выше примере.
- Если они перекрываются по кругу, получается один кластер
- Если перекрытия круга не происходит, круг рисуется вокруг других данных для формирования других кластеров.
- Критерий минимальной выборки решит, является ли это плотной областью или нет.
Как выбрать Эпсилон?
- Оценка параметров: - Если эпсилон имеет небольшое значение, многие точки могут считаться выбросами. Они не будут основными точками (окрестность ε будет очень маленькой). Большое значение ε может привести к тому, что огромное количество точек окажется в одном кластере.
Как оценивать модели кластеризации?
- Оценка силуэта
- Индекс Рэнда
- Индекс Жаккорда
Оценка Силхотта более точна, чем индекс Рэнда и оценка Жаккорда.
Оценка Silhotte: - оценка силуэта рассчитывается с использованием среднего расстояния внутри кластера между точками и среднего расстояния до ближайшего кластера, например, кластера с большим количеством точек данных, очень близких друг к другу (высокая плотность) и далеко от следующий ближайший кластер (предполагая, что кластер очень уникален по сравнению со следующим закрытием) будет иметь сильную оценку силуэта.
Оценка силуэта варьируется от -1 до 1, где -1 — наихудшая возможная оценка, а 1 — наилучшая оценка. Оценка силуэта 0 предполагает перекрывающиеся кластеры
Эту оценку силуэта можно использовать также для оценки любых других моделей кластеризации.
Параметры
Алгоритм DBScan требует передачи двух параметров:
- eps: — Один из способов найти значение Eps основан на графике k-расстояний.
- Minpts: - Минимальное количество соседей (точек данных) в радиусе eps. Чем больше наборы данных, тем больше значение minpts должно быть выбрано. Как правило, минимальные minpts могут быть получены из количества измерений D в наборе данных как Minpts≥D+1. Минимальное значение minpts должно быть не менее 3. Это всего лишь основное эмпирическое правило. Минимальное значение minpt 3 будет хорошим. Размер D означает функции или столбцы.