Основанная на плотности пространственная кластеризация приложений с шумом (DBSCAN)
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, соответственно.
Кластеризируйте 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-средних значений, кластеризирующие сбои, чтобы правильно идентифицировать эти два кластера в наборе данных.
Выполните 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,:);
Визуализируйте данные как 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 для более обширного примера.
Для улучшенной скорости при итерации по многим значениям 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.