Exponenta 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 имя аргумента и 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 = nanstdX. Используйте Scale задавать другое значение для S.

'mahalanobis'

Расстояние Mahalanobis с помощью выборочной ковариации X, C = nancovX. Используйте 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- n вектор, содержащий одно наблюдение.

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

  • D2 m2- 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
Поддержка