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, использование любой комбинации входных аргументов в предыдущих синтаксисах.

Примеры

свернуть все

Открыть Live Script

Скопируйте 2-D набор круговых данных с помощью 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))

Figure contains an axes. The axes contains an object of type scatter.

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

Выполните кластеризацию данных 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')

Figure contains an axes. The axes with title DBSCAN Using Euclidean Distance Metric contains 2 objects of type line. These objects represent 1, 2.

Используя метрику Евклидова расстояния, 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')

Figure contains an axes. The axes with title DBSCAN Using Squared Euclidean Distance Metric contains 2 objects of type line. These objects represent 1, 2.

Используя квадратную метрику Евклидова расстояния, 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')

Figure contains an axes. The axes with title K-Means Using Squared Euclidean Distance Metric contains 2 objects of type line. These objects represent 1, 2.

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

Открыть Live Script

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

Загружает координаты x, y, z объектов.

load('lidar_subset.mat') 
loc = lidar_subset;

Чтобы выделить окружение вокруг транспортного средства, установите необходимую область размах 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,:);

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

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

Figure contains an axes. The axes contains an object of type scatter.

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

Предварительно вычислите матрицу парных расстояний 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

Figure contains an axes. The axes contains 12 objects of type line. These objects represent -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.

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

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

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

sum(idx == -1)
ans = 412

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

Найдите число точек, которые dbscan определяет как основные точки. A 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 = std(X,'omitnan'). Использование Scale чтобы задать другое значение для S.

'mahalanobis'

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

'cityblock'

Расстояние между блоками

'minkowski'

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

'chebychev'

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

'cosine'

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

'correlation'

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

'hamming'

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

'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' distance metric, можно задать дополнительный аргумент пары "имя-значение" 'Scale', 'P', или 'Cov', соответственно, для управления метриками расстояния.

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

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

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

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

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

Ковариационная матрица для метрики расстояния Махаланобиса, заданная как разделенная разделенными запятой парами, состоящая из '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 для строк, соответствующих наблюдениям, которые не являются центральными точками.

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

Подробнее о

свернуть все

Основные точки

Основные точки в кластере являются точками, которые имеют по крайней мере минимальное количество соседей (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 -distance графиков для X. Для каждой точки в Xнайдите расстояние до k-й ближайшей точки и постройте график отсортированных точек относительно этого расстояния. Обычно график содержит колено. Расстояние, которое соответствует колену, обычно является хорошим выбором для 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] Эстер, М., H.-P. Кригель, Дж. Сандер, и X. Сяовэй. «Основанный на плотности алгоритм для обнаружения кластеров в больших пространственных базах данных с шумом». В материалах второй Международной конференции по открытию знаний в базах данных и майнингу данных, 226-231. Portland, OR: AAAI Press, 1996.

См. также

| | | | |

Темы

Введенный в R2019a

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

Поддержка

Для просмотра документации необходимо авторизоваться на сайте