Основанная на плотности пространственная кластеризация приложений с шумом (DBSCAN)
наблюдения разделов в n-by-p матрица данных idx
= dbscan(X
,epsilon
,minpts
)X
в кластеры с помощью алгоритма DBSCAN (см. Алгоритмы). dbscan
кластеризирует наблюдения (или точки) на основе порога для радиуса поиска окружения epsilon
и минимальное количество соседей minpts
требуемый идентифицировать базовую точку. Функция возвращает n-by-1 вектор (idx
) содержа кластерные индексы каждого наблюдения.
возвращает вектор кластерных индексов для предварительно вычисленных попарных расстояний idx
= dbscan(D
,epsilon
,minpts
,'Distance'
,'precomputed')D
между наблюдениями. D
может быть выход pdist
или pdist2
, или более общий вектор несходства или матрица, соответствующая выходному формату pdist
или pdist2
, соответственно.
Для улучшенной скорости при итерации по многим значениям epsilon
, рассмотрите передачу в D
как вход к dbscan
. Этот подход препятствует тому, чтобы функция имела, чтобы вычислить расстояния в каждой точке итерации.
Если вы используете pdist2
предварительно вычислить D
, не задавайте 'Smallest'
или 'Largest'
аргументы пары "имя-значение" pdist2
выбрать или отсортировать столбцы D
. Выбор меньше, чем расстояния n приводит к ошибке, потому что dbscan
ожидает D
быть квадратной матрицей. Сортировка расстояний в каждом столбце D
приводит к потере в интерпретации D
и может дать бессмысленные результаты, когда используется в dbscan
функция.
Для эффективного использования памяти рассмотрите передачу в D
как логическая матрица, а не числовая матрица к dbscan
когда D
является большим. По умолчанию MATLAB® хранит каждое значение в числовой матрице с помощью 8 байтов (64 бита) и каждое значение в логической матрице с помощью 1 байта (8 битов).
Выбрать значение для minpts
, считайте значение больше, чем или равный количеству размерностей входных данных плюс один (1). Например, для n-by-p матричный X
, установите 'minpts'
равняйтесь p +1 или больше.
Одна возможная стратегия выбора значения для epsilon
должен сгенерировать k - график расстояния для X
. Для каждой точки в X
, найдите расстояние до k th самой близкой точкой и постройте отсортированные точки против этого расстояния. Обычно график содержит колено. Расстояние, которое соответствует колену, обычно является хорошим выбором для epsilon
, потому что это - область, где точки начинают затихать в выброс (шум) территория [1].
DBSCAN является основанным на плотности алгоритмом кластеризации, который спроектирован, чтобы обнаружить кластеры и шум в данных. Алгоритм идентифицирует три вида точек: базовые точки, пограничные точки и шумовые точки [1]. Для заданных значений epsilon
и minpts
, dbscan
функционируйте реализует алгоритм можно следующим образом:
От входных данных устанавливает X
, выберите первое непомеченное наблюдение x1 как текущая точка и инициализируйте первую кластерную метку C к 1.
Найдите набор точек в окружении эпсилона epsilon
из текущей точки. Эти точки являются соседями.
Если количество соседей меньше minpts
, затем пометьте текущую точку как шумовую точку (или выброс). Перейдите к шагу 4.
dbscan
может повторно присвоить шумовые точки кластерам, если шум указывает, позже удовлетворяют ограничениям, установленным epsilon
и minpts
от некоторой другой точки в X
. Этот процесс переприсвоения точек происходит для пограничных точек кластера.
В противном случае пометьте текущую точку как базовую точку, принадлежащую, чтобы кластеризировать C.
Выполните итерации по каждому соседу (новая текущая точка) и повторный шаг 2, пока никакие новые соседи не найдены, что это может быть помечено как принадлежащий текущему кластерному C.
Выберите следующую непомеченную точку в X
как текущая точка и увеличение кластерное количество 1.
Повторите шаги 2-4 до всех точек в X
помечены.
Если два кластера имеют различную плотность и друг близко к другу, то есть, расстояние между двумя пограничными точками (один от каждого кластера) меньше epsilon
, затем dbscan
может объединить эти два кластера в один.
Каждая допустимая кластерная сила не содержит, по крайней мере, minpts
наблюдения. Например, dbscan
может идентифицировать пограничную точку, принадлежащую двум кластерам, которые являются друг близко к другу. В такой ситуации алгоритм присваивает пограничную точку первому обнаруженному кластеру. В результате второй кластер является все еще допустимым кластером, но он может иметь меньше, чем minpts
наблюдения.
[1] Сложный эфир, M., H.-P. Kriegel, Дж. Сандер и Кс. Ксиэауэи. “Основанный на плотности алгоритм для обнаружения кластеров в больших пространственных базах данных с шумом”. В Продолжениях Второй Международной конференции по вопросам Открытия Знаний в Базах данных и Анализа данных, 226-231. Портленд, OR: Нажатие AAAI, 1996.