В DBSCAN, как определить пограничные точки?
В DBSCAN основные точки определены как имеющие больше чем MinPts в пределах Eps.
Так что, если MinPts = 4, очки с 5 очками в Eps, безусловно, являются ключевыми. Как насчет точки с 4 точками (включая себя) в Eps? Это ключевой пункт или пограничный пункт?
3 ответа
Граничные точки - это точки, которые (в DBSCAN) являются частью кластера, но сами по себе не являются плотными (т. Е. Каждый элемент кластера, который не является базовой точкой).
В алгоритме отслеживания HDBSCAN понятие пограничных точек было отброшено.
Кампелло, RJGB; Мулави, D.; Сандер, Дж. (2013).
Кластеризация на основе плотности на основе оценок иерархической плотности.
Материалы 17-й Тихоокеанской конференции по открытию знаний в базах данных, PAKDD 2013. Конспект лекций в области компьютерных наук 7819. p. 160. doi:10.1007/978-3-642-37456-2_14
в котором говорится:
Наши новые определения более соответствуют статистической интерпретации кластеров, поскольку связанные компоненты набора уровней объектов границы [...] плотности технически не относятся к набору уровней (их оценочная плотность ниже порогового значения).
На самом деле, я просто перечитал оригинальную статью, и из определения 1 видно, что основная точка принадлежит его собственной окрестности eps. Таким образом, если minPts равно 4, то точке нужно как минимум 3 других в окрестности eps.
Обратите внимание, что в определении 1 говорится, что NEps(p) = {q ∈D | dist(p,q) ≤ Eps}. Если бы точка была исключена из ее окрестности eps, то она бы сказала NEps (p) = {q ∈D | dist (p, q) ≤ Eps и p!= q}. Где! = "Не равно".
Это также подтверждается авторами DBSCAN в их документе OPTICS на рисунке 4. http://fogo.dbs.ifi.lmu.de/Publikationen/Papers/OPTICS.pdf
Поэтому я думаю, что интерпретация SciKit верна, а иллюстрация из Википедии вводит в заблуждение на http://en.wikipedia.org/wiki/DBSCAN
Это во многом зависит от реализации. Лучший способ - просто поиграть с реализацией самостоятельно.
В исходной статье DBSCAN1 условие точки ядра задается как N_Eps>=MinPts, где N_Eps - окрестность Эпсилона определенной точки данных, которая исключена из ее собственных N_Eps.
Следуя вашему примеру, если MinPts = 4 и N_Eps = 3 (или 4, включая себя, как вы говорите), они не образуют кластер в соответствии с оригинальной статьей. С другой стороны, реализация DBSCAN scikit-learn2 работает иначе, то есть она сама считает точку для формирования группы. Таким образом, для MinPts=4, для формирования кластера необходимо всего четыре точки.
[1] Эстер, Мартин; Кригель, Ханс-Петер; Сандер, Йорг; Сюй, Xiaowei (1996). "Алгоритм на основе плотности для обнаружения кластеров в больших пространственных базах данных с шумом".