Exponenta Banner
exponenta event banner

dbscan

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

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

Синтаксис

idx = dbscan (X, epsilon, minpts)
idx = dbscan (X, epsilon, minpts, имя, значение)
idx = dbscan (D, epsilon, minpts, 'Расстояние', 'предварительно вычисленное')
[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, используя любую из комбинаций входных аргументов в предыдущих синтаксисах.

Примеры

свернуть все

Открыть сценарий в реальном времени

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

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

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 и a 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 и a 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-Means с использованием квадратной евклидовой метрики расстояния. Укажите 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-Means не может правильно идентифицировать два кластера в наборе данных.

Открыть сценарий в реальном времени

Выполнение кластеризации 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 и a 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 для разделения больших кластеров и дальнейшего разделения точек.

Функция также идентифицирует некоторые отклонения ( 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-на-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-на-n, где D(i,j) указывает расстояние между наблюдениями i и j в X которые меньше или равны epsilon

Примечание

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

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

Окрестность точки Epsilon, заданная как числовой скаляр, определяющий радиус поиска окрестности вокруг точки. Если эпсилоновая окрестность точки содержит по крайней мере 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'

Один минус коэффициент 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

Ковариационная матрица для метрики расстояния Махаланобиса, заданная как разделенная запятыми пара, состоящая из '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-расстояний для 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. Кригель, Дж. Сандер и Х. Сяовэй. «Алгоритм на основе плотности для обнаружения кластеров в больших пространственных базах данных с шумом». В материалах второй Международной конференции по открытию знаний в области баз данных и интеллектуального анализа данных, 226-231. Портленд, ИЛИ: AAAI Press, 1996.

См. также

| | | | |

Темы

Представлен в R2019a

Документация по инструментам для статистического и машинного обучения

Поддержка