Exponenta Banner
exponenta event banner

dbscan

Основанная на плотности пространственная кластеризация приложений с шумом (DBSCAN)

свернуть все на странице

Синтаксис

idx = dbscan(X,epsilon,minpts)
idx = dbscan(X,epsilon,minpts,Name,Value)
idx = dbscan(D,epsilon,minpts,'Distance','precomputed')
[idx,corepts] = dbscan(___)

Описание

пример

idx = dbscan(X,epsilon,minpts) наблюдения разделов в n-by-p матрица данных X в кластеры с помощью алгоритма DBSCAN (см. Алгоритмы). dbscan кластеризирует наблюдения (или точки) на основе порога для радиуса поиска окружения epsilon и минимальное количество соседей minpts, требуемый идентифицировать базовую точку. Функция возвращает n-by-1 вектор (idx), содержащий кластерные индексы каждого наблюдения.

пример

idx = dbscan(X,epsilon,minpts,Name,Value) задает дополнительные опции с помощью одного или нескольких аргументов пары "имя-значение". Например, можно задать 'Distance','minkowski','P',3, чтобы использовать метрику расстояния Минковскего с экспонентой три в алгоритме DBSCAN.

пример

idx = dbscan(D,epsilon,minpts,'Distance','precomputed') возвращает вектор кластерных индексов для предварительно вычисленных попарных расстояний D между наблюдениями. D может быть вывод pdist или pdist2, или более общего вектора несходства или матрицы, соответствующей выходному формату pdist или pdist2, соответственно.

пример

[idx,corepts] = dbscan(___) также возвращает логический векторный corepts, который содержит базовые точки, идентифицированные dbscan, с помощью любой из комбинаций входных аргументов в предыдущих синтаксисах.

Примеры

свернуть все

Скрипт Open Live Script

Кластеризируйте 2D круговой набор данных с помощью DBSCAN с Евклидовой метрикой расстояния по умолчанию. Кроме того, сравните результаты кластеризации набора данных с помощью DBSCAN и k-средств, кластеризирующихся с Евклидовой метрикой расстояния в квадрате.

Сгенерируйте синтетические данные, которые содержат два шумных круга.

rng('default') % For reproducibility

% Parameters for data generation
N = 300;  % Size of each cluster
r1 = 0.5; % Radius of first circle
r2 = 5;   % Radius of second circle
theta = linspace(0,2*pi,N)';

X1 = r1*[cos(theta),sin(theta)]+ rand(N,1); 
X2 = r2*[cos(theta),sin(theta)]+ rand(N,1);
X = [X1;X2]; % Noisy 2-D circular data set

Визуализируйте набор данных.

scatter(X(:,1),X(:,2))

График показывает, что набор данных содержит два отличных кластера.

Выполните DBSCAN, кластеризирующийся на данных. Задайте значение epsilon 1 и значение minpts 5.

idx = dbscan(X,1,5); % The default distance metric is Euclidean distance

Визуализируйте кластеризацию.

gscatter(X(:,1),X(:,2),idx);
title('DBSCAN Using Euclidean Distance Metric')

Используя Евклидову метрику расстояния, DBSCAN правильно идентифицирует эти два кластера в наборе данных.

Выполните DBSCAN, кластеризирующий использование Евклидовой метрики расстояния в квадрате. Задайте значение epsilon 1 и значение minpts 5.

idx2 = dbscan(X,1,5,'Distance','squaredeuclidean');

Визуализируйте кластеризацию.

gscatter(X(:,1),X(:,2),idx2);
title('DBSCAN Using Squared Euclidean Distance Metric')

Используя Евклидову метрику расстояния в квадрате, DBSCAN правильно идентифицирует эти два кластера в наборе данных.

Выполните кластеризацию k-средств с помощью Евклидовой метрики расстояния в квадрате. Задайте k = 2 кластера.

kidx = kmeans(X,2); % The default distance metric is squared Euclidean distance

Визуализируйте кластеризацию.

gscatter(X(:,1),X(:,2),kidx);
title('K-Means Using Squared Euclidean Distance Metric')

Используя Евклидову метрику расстояния в квадрате, кластеризации k-средств не удается правильно идентифицировать эти два кластера в наборе данных.

Скрипт Open Live Script

Выполните DBSCAN, кластеризирующий использование матрицы попарных расстояний между наблюдениями, как введено к функции dbscan, и найдите количество выбросов и базовых точек. Набор данных является последовательностью сканирований Лазерного дальномера, каждый сохраненный как 3-D облако точек.

Загрузите последовательность облак точек. Выберите последнюю метку времени в последовательности и извлеките x, y, z координаты объектов, окружающих автомобиль.

d = load('01_city_c2s_fcw_10s_Lidar.mat'); 
pcloud = d.LidarPointCloud; 
loc = pcloud(end).ptCloud.Location;

Чтобы подсветить среду вокруг автомобиля, установите видимую область охватывать 20 метров налево и право на автомобиль, 20 метров впереди и заднюю часть автомобиля и область выше поверхности дороги.

xBound = 20; % in meters
yBound = 20; % in meters
zLowerBound = 0; % in meters

Обрежьте облако точек, чтобы содержать только точки в заданной области.

indices = loc(:,1) <= xBound & loc(:,1) >= -xBound ...
    & loc(:,2) <= yBound & loc(:,2) >= -yBound ...
    & loc(:,3) > zLowerBound;
loc = loc(indices,:);

Визуализируйте данные как 2D график рассеивания. Аннотируйте график подсветить автомобиль.

scatter(loc(:,1),loc(:,2),'.');
annotation('ellipse',[0.48 0.48 .1 .1],'Color','red')

Центр облака точек (кружился в красном) содержит крышу и капот автомобиля. Все другие точки являются препятствиями.

Предварительно вычислите матрицу попарных расстояний D между наблюдениями при помощи функции pdist2.

D = pdist2(loc,loc);

Кластеризируйте данные при помощи dbscan с попарными расстояниями. Задайте значение epsilon 2 и значение minpts 50.

[idx, corepts] = dbscan(D,2,50,'Distance','precomputed');

Визуализируйте результаты и аннотируйте фигуру, чтобы подсветить определенный кластер.

gscatter(loc(:,1),loc(:,2),idx);
annotation('ellipse',[0.54 0.41 .07 .07],'Color','red')
grid

Как показано в графике рассеивания, dbscan идентифицирует 11 кластеров и помещает автомобиль в отдельный кластер.

dbscan присваивает группу точек, окруженных в красном (и сосредоточенный вокруг (3,–4)) к тому же кластеру (группа 7) как группа точек в юго-восточном квадранте графика. Ожидание состоит в том, что эти группы должны быть в отдельных кластерах. Можно попытаться использовать меньшее значение epsilon, чтобы разделить большие кластеры и дальнейший раздел облако точек.

Функция также идентифицирует некоторые выбросы (значение idx –1) в данных. Найдите число точек, которое dbscan идентифицирует как выбросы.

sum(idx == -1)
ans = 412

dbscan идентифицирует 412 выбросов из 19 070 наблюдений.

Найдите число точек, которое идентифицирует dbscan, когда ядро указывает. Значение corepts 1 указывает на базовую точку.

sum(corepts == 1)
ans = 18446

dbscan идентифицирует 18 446 наблюдений, когда ядро указывает.

Смотрите Определяют Значения для Параметров DBSCAN для более обширного примера.

Входные параметры

свернуть все

Входные данные, заданные как n-by-p числовая матрица. Строки X соответствуют наблюдениям (или точки), и столбцы соответствуют переменным.

Типы данных: single | double

Попарные расстояния между наблюдениями, заданными как числовой вектор - строка, который является выводом pdist, числовая квадратная матрица, которая является выводом pdist2, логического вектора - строки или логической квадратной матрицы. D может также быть более общим вектором несходства или матрицей, которая соответствует выходному формату pdist или pdist2, соответственно.

Для вышеупомянутых спецификаций следующая таблица описывает форматы, которые D может взять, учитывая входную матрицу X, который имеет наблюдения n (строки) и размерности p (столбцы).

СпецификацияФормат
Числовой вектор - строка (вывод pdist(X))

  • Вектор - строка из длины n (n – 1)/2, соответствуя парам наблюдений в X

  • Расстояния располагаются в порядке (2,1), (3,1)..., (n, 1), (3,2)..., (n, 2)..., (n, n – 1)),

Числовая квадратная матрица (вывод pdist2(X,X))

  • n-by-n матрица, где D(i,j) является расстоянием между наблюдениями i и j в X

  • Симметрическая матрица, имеющая диагональные равные нулю элементы

Логический вектор - строка

  • Вектор - строка из длины n (n – 1)/2, соответствуя парам наблюдений в X

  • Логический вектор - строка с элементами, указывающими на расстояния, которые меньше чем или равны epsilon

  • Элементы D располагаются в порядке (2,1), (3,1)..., (n, 1), (3,2)..., (n, 2)..., (n, n – 1)),

Логическая квадратная матрица

  • n-by-n матрица, где D(i,j) указывает на расстояние между наблюдениями i и j в X, которые меньше чем или равны epsilon

Примечание

Если D является логическим вектором или матрицей, то значение epsilon должно быть пустым; например, dbscan(D,[],5,'Distance','precomputed').

Типы данных: single | double | logical

Окружение эпсилона точки, заданной в виде числа, которое задает радиус поиска окружения вокруг точки. Если окружение эпсилона точки содержит, по крайней мере, соседей minpts, то dbscan идентифицирует точку как базовую точку.

Значение epsilon должно быть пустым ([]), когда D является логическим вектором или матрицей.

Пример: dbscan(X,2.5,10)

Пример: dbscan(D,[],5,'Distance','precomputed'), для логического матричного или векторного D

Типы данных: single | double

Минимальное количество соседей требуется для базовой точки, заданной как положительное целое число. Окружение эпсилона базовой точки в кластере должно содержать, по крайней мере, соседей minpts, тогда как окружение эпсилона пограничной точки может содержать меньше соседей, чем minpts.

Пример: dbscan(X,2.5,5)

Типы данных: single | double

Аргументы в виде пар имя-значение

Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми. Имя (Name) — это имя аргумента, а значение (Value) — соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

Пример: dbscan(D,2.5,5,'Distance','precomputed') задает DBSCAN, кластеризирующий использование предварительно вычисленной матрицы попарных расстояний D между наблюдениями, окружением эпсилона 2.5 и минимумом соседей 5.

Метрика расстояния, заданная как пара, разделенная запятой, состоящая из 'Distance' и вектора символов, представляет в виде строки скаляр или указатель на функцию, как описано в этой таблице.

ЗначениеОписание
'precomputed'

Предварительно вычисленные расстояния. Необходимо задать эту опцию, если первый вход к dbscan является вектором или матрицей попарных расстояний D.

'euclidean'

Евклидово расстояние (значение по умолчанию)

'squaredeuclidean'

Придал Евклидову расстоянию квадратную форму. (Эта возможность предоставляется для эффективности только. Это не удовлетворяет треугольное неравенство.)

'seuclidean'

Стандартизированное Евклидово расстояние. Каждое координатное различие между наблюдениями масштабируется путем деления на соответствующий элемент стандартного отклонения, S = nanstd(X). Используйте Scale, чтобы задать другое значение для S.

'mahalanobis'

Расстояние Mahalanobis с помощью выборочной ковариации X, C = nancov(X). Используйте Cov, чтобы задать другое значение для C, где матричный C симметричен и положительный определенный.

'cityblock'

Расстояние городского квартала

'minkowski'

Расстояние Минковскего. Экспонента по умолчанию равняется 2. Используйте P, чтобы задать различную экспоненту, где P является значением положительной скалярной величины.

'chebychev'

Расстояние Чебычева (максимум координируют различие),

'cosine'

Один минус косинус включенного угла между точками (обработанный как векторы)

'correlation'

Один минус корреляция выборки между точками (обработанный как последовательности значений)

'hamming'

Расстояние Хемминга, которое является процентом координат, которые отличаются

'jaccard'

Один минус коэффициент Jaccard, который является процентом ненулевых координат, которые отличаются

'spearman'

Один минус порядковая корреляция демонстрационного Копьеносца между наблюдениями (обработанный как последовательности значений)

@distfun

Пользовательский указатель на функцию расстояния. Функция расстояния имеет форму

function D2 = distfun(ZI,ZJ)
% calculation of distance
...
где

  • ZI является 1-by-n вектор, содержащий одно наблюдение.

  • ZJ является m2-by-n матрица, содержащая несколько наблюдений. distfun должен принять матричный ZJ с произвольным числом наблюдений.

  • D2 является m2-by-1 вектор расстояний, и D2(k) является расстоянием между наблюдениями ZI и ZJ(k,:).

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

Для определений смотрите Метрики Расстояния.

Когда вы используете 'seuclidean', 'minkowski' или метрику расстояния 'mahalanobis', можно задать дополнительный аргумент пары "имя-значение" 'Scale', 'P', или 'Cov', соответственно, чтобы управлять метриками расстояния.

Пример: dbscan(X,2.5,5,'Distance','minkowski','P',3) задает окружение эпсилона 2.5, минимум соседей 5, чтобы вырастить кластер и использование метрики расстояния Минковскего с экспонентой 3 при выполнении кластеризирующегося алгоритма.

Экспонента для метрики расстояния Минковскего, заданной как пара, разделенная запятой, состоящая из 'P' и положительной скалярной величины.

Этот аргумент допустим, только если 'Distance' является 'minkowski'.

Пример: 'P',3

Типы данных: single | double

Ковариационная матрица для метрики расстояния Mahalanobis, заданной как пара, разделенная запятой, состоящая из 'Cov' и симметричной, положительной определенной, числовой матрицы.

Этот аргумент допустим, только если 'Distance' является 'mahalanobis'.

Типы данных: single | double

Масштабные коэффициенты для стандартизированной Евклидовой метрики расстояния, заданной как пара, разделенная запятой, состоящая из 'Scale' и числовой вектор положительных значений.

Каждая размерность (столбец) X имеет соответствующее значение в 'Scale'; поэтому, 'Scale' имеет длину p (количество столбцов в X). Для каждой размерности X dbscan использует соответствующее значение в 'Scale', чтобы стандартизировать различие между X и точкой запроса.

Этот аргумент допустим, только если 'Distance' является 'seuclidean'.

Типы данных: single | double

Выходные аргументы

свернуть все

Кластерные индексы, возвращенные как числовой вектор-столбец. idx имеет строки n, и каждая строка idx указывает на кластерное присвоение соответствующего наблюдения в X. Индекс, равный –1, указывает на выброс (или шумовая точка).

Примечание

Кластерное присвоение с помощью алгоритма DBSCAN зависит от порядка наблюдений. Поэтому перестановка строк X может привести к различным кластерным присвоениям для наблюдений. Для получения дополнительной информации см. Алгоритмы.

Типы данных: double

Индикатор для базовых точек, возвращенных как n-by-1 логический вектор, указывающий на индексы базовых точек, идентифицирован dbscan. Значение 1 в любой строке corepts указывает, что соответствующее наблюдение в X является базовой точкой. В противном случае corepts имеет значение 0 для строк, соответствующих наблюдениям, которые не являются базовыми точками.

Типы данных: логический

Больше о

свернуть все

Базовые точки

Базовые точки в кластере являются точками, которые имеют, по крайней мере, минимальное количество соседей (minpts) в их окружении эпсилона (epsilon). Каждый кластер должен содержать по крайней мере одну базовую точку.

Пограничные точки

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

Шумовые точки

Шумовые точки являются выбросами, которые не принадлежат никакому кластеру.

Советы

  • Для улучшенной скорости при итерации по многим значениям 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 реализует алгоритм можно следующим образом:

    1. От входных данных устанавливает X, выбирают первое немаркированное наблюдение x1 как текущая точка и инициализируют первую кластерную метку C к 1.

    2. Найдите набор точек в окружении эпсилона epsilon текущей точки. Эти точки являются соседями.

      1. Если количество соседей является меньше, чем minpts, то маркируйте текущую точку как шумовую точку (или выброс). Перейдите к шагу 4.

        Примечание

        dbscan может повторно присвоить шумовые точки кластерам, если шум указывает, позже удовлетворяют ограничения, установленные epsilon и minpts от некоторой другой точки в X. Этот процесс переприсвоения точек происходит для пограничных точек кластера.

      2. В противном случае маркируйте текущую точку как базовую точку, принадлежащую, чтобы кластеризировать C.

    3. Выполните итерации по каждому соседу (новая текущая точка) и повторный шаг 2, пока никакие новые соседи не найдены, что это может быть маркировано как принадлежащий текущему кластерному C.

    4. Выберите следующую немаркированную точку в X как текущая точка и увеличьте кластерное количество на 1.

    5. Повторите шаги 2-4, пока все точки в X не будут маркированы.

  • Если два кластера имеют переменную плотность и друг близко к другу, то есть, расстояние между двумя пограничными точками (один от каждого кластера) является меньше, чем epsilon, то dbscan может объединить эти два кластера в один.

  • Каждая допустимая кластерная сила не содержит, по крайней мере, наблюдения minpts. Например, dbscan может идентифицировать пограничную точку, принадлежащую двум кластерам, которые являются друг близко к другу. В такой ситуации алгоритм присваивает пограничную точку первому обнаруженному кластеру. В результате второй кластер является все еще допустимым кластером, но он может иметь меньше, чем наблюдения minpts.

Ссылки

[1] Сложный эфир, M., H.-P. Kriegel, Дж. Сандер и Кс. Ксиэауэи. “Основанный на плотности алгоритм для обнаружения кластеров в больших пространственных базах данных с шумом”. В Продолжениях Второй Международной конференции по вопросам Открытия Знаний в Базах данных и Анализа данных, 226-231. Портленд, OR: Нажатие AAAI, 1996.

Смотрите также

| | | | |

Темы

Введенный в R2019a

Документация Statistics and Machine Learning Toolbox
Поддержка