Основанная на плотности Пространственная Кластеризация Приложений с Шумом (DBSCAN) идентифицирует кластеры произвольной формы и шум (выбросы) в данных. Функция Statistics and Machine Learning Toolbox™ dbscan выполняет кластеризацию на матрице входных данных или на попарных расстояниях между наблюдениями. dbscan возвращает кластерные индексы и вектор, указывающий на наблюдения, которые являются базовыми точками (точки в кластерах). В отличие от k - означает кластеризироваться, алгоритм DBSCAN не требует предварительных знаний количества кластеров, и кластеры являются не обязательно сфероидальными. DBSCAN также полезен для основанного на плотности определения выбросов, потому что это идентифицирует точки, которые не принадлежат никакому кластеру.
Для точки, которая будет присвоена кластеру, условию что его окружение эпсилона должно удовлетворить (epsilon) содержит, по крайней мере, минимальное количество соседей (minpts). Или, точка может лечь в окружении эпсилона другой точки, которая удовлетворяет epsilon и minpts условия. Алгоритм DBSCAN идентифицирует три вида точек:
Базовая точка — точка в кластере, который имеет, по крайней мере, minpts соседи в его окружении эпсилона
Пограничная точка — точка в кластере, который имеет меньше, чем minpts соседи в его окружении эпсилона
Шумовая точка — выброс, который не принадлежит никакому кластеру
DBSCAN работает с широким спектром метрик расстояния, и можно задать пользовательскую метрику расстояния для конкретного приложения. Выбор метрики расстояния определяет форму окружения.
Для заданных значений окружения эпсилона epsilon и минимальное количество соседей minpts требуемый для базовой точки, dbscan функционируйте реализует DBSCAN можно следующим образом:
От входных данных устанавливает X, выберите первое непомеченное наблюдение x1 как текущая точка и инициализируйте первую кластерную метку C к 1.
Найдите набор точек в окружении эпсилона epsilon из текущей точки. Эти точки являются соседями.
Если количество соседей меньше minpts, затем пометьте текущую точку как шумовую точку (или выброс). Перейдите к шагу 4.
dbscan может повторно присвоить шумовые точки кластерам, если шум указывает, позже удовлетворяют ограничениям, установленным epsilon и minpts от некоторой другой точки в X. Этот процесс переприсвоения точек происходит для пограничных точек кластера.
В противном случае пометьте текущую точку как базовую точку, принадлежащую, чтобы кластеризировать C.
Выполните итерации по каждому соседу (новая текущая точка) и повторный шаг 2, пока никакие новые соседи не найдены, что это может быть помечено как принадлежащий текущему кластерному C.
Выберите следующую непомеченную точку в X как текущая точка и увеличение кластерное количество 1.
Повторите шаги 2-4 до всех точек в X помечены.
В этом примере показано, как выбрать значения для epsilon и minpts параметры dbscan. Набор данных является последовательностью сканирований Лидара, каждый сохраненный как 3-D облако точек.
Загрузите, предварительно обработайте и визуализируйте набор данных.
Загрузите последовательность облаков точек. Выберите последнюю метку времени в последовательности и извлеките x, y, z координаты объектов, окружающих транспортное средство.
d = load('01_city_c2s_fcw_10s_Lidar.mat');
pcloud = d.LidarPointCloud;
X = pcloud(end).ptCloud.Location;Чтобы подсветить среду вокруг транспортного средства, установите необходимую область охватывать 20 метров налево и право на транспортное средство, 20 метров впереди и заднюю часть транспортного средства и область выше поверхности дороги.
xBound = 20; % in meters yBound = 20; % in meters zLowerBound = 0; % in meters
Обрежьте облако точек, чтобы содержать только точки в заданной области.
indices = X(:,1) <= xBound & X(:,1) >= -xBound ... & X(:,2) <= yBound & X(:,2) >= -yBound ... & X(:,3) > zLowerBound; X = X(indices,:);
Визуализируйте данные как 2D график рассеивания. Аннотируйте график подсветить транспортное средство.
scatter(X(:,1),X(:,2),'.'); annotation('ellipse',[0.48 0.48 .1 .1],'Color','red')
Центр облака точек (кружился в красном) содержит крышу и капот транспортного средства. Все другие точки являются препятствиями.
Выберите значение для minpts.
Выбрать значение для minpts, считайте значение больше, чем или равный одному плюс количество размерностей входных данных [1]. Например, для n- p матричный X, установите значение 'minpts' больше, чем или равный p+1.
Для набора определенных данных задайте minpts значение, больше, чем или равный 4, в частности значение 50.
minpts = 50; % Minimum number of neighbors for a core pointВыберите значение для epsilon.
Одна стратегия оценки значения для epsilon должен сгенерировать график k-расстояния для входных данных X. Для каждой точки в X, найдите расстояние до kth самой близкой точки и постройте отсортированные точки против этого расстояния. График содержит колено. Расстояние, которое соответствует колену, обычно является хорошим выбором для epsilon, потому что это - область, где точки начинают затихать в выброс (шум) территория [1].
Прежде, чем построить график k-расстояния, сначала найдите minpts наименьшие попарные расстояния для наблюдений в X, в порядке возрастания.
kD = pdist2(X,X,'euc','Smallest',minpts); % The minpts smallest pairwise distances
Постройте график k-расстояния.
plot(sort(kD(end,:))); title('k-distance graph') xlabel('Points sorted with 50th nearest distances') ylabel('50th nearest distances') grid
Колено, кажется, приблизительно 2; поэтому, установите значение epsilon к 2.
epsilon = 2;
Кластер с помощью dbscan.
Используйте dbscan со значениями minpts и epsilon это было определено на предыдущих шагах.
labels = dbscan(X,epsilon,minpts);
Визуализируйте кластеризацию и аннотируйте фигуру, чтобы подсветить определенные кластеры.
gscatter(X(:,1),X(:,2),labels); title('epsilon = 2 and minpts = 50') grid annotation('ellipse',[0.54 0.41 .07 .07],'Color','red') annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue') annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')
dbscan идентифицирует 11 кластеров и набор шумовых точек. Алгоритм также идентифицирует транспортное средство в центре облака точек как отличный кластер.
dbscan идентифицирует некоторые отличные кластеры, такие как кластер, окруженный в черном цвете (и сосредоточенный (приблизительно-6,18)) и кластер, окруженный в синем (и сосредоточенный (приблизительно 2.5,18)). Функция также присваивает группу точек, окруженных в красном (и сосредоточенный вокруг (3,–4)) к тому же кластеру (группа 7) как группа точек в юго-восточном квадранте графика. Ожидание состоит в том, что эти группы должны быть в отдельных кластерах.
Используйте меньшее значение в epsilon разделять большие кластеры и дальнейший раздел облако точек.
epsilon2 = 1; labels2 = dbscan(X,epsilon2,minpts);
Визуализируйте кластеризацию и аннотируйте фигуру, чтобы подсветить определенные кластеры.
gscatter(X(:,1),X(:,2),labels2); title('epsilon = 1 and minpts = 50') grid annotation('ellipse',[0.54 0.41 .07 .07],'Color','red') annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue') annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')
При помощи меньшего значения эпсилона, dbscan может присвоить группу точек, окруженных в красном к отличному кластеру (группа 13). Однако некоторые кластеры, что dbscan правильно идентифицированный прежде теперь разделены между точками накопления и выбросами. Например, смотрите, кластерная группа 2 (кружился в черном цвете), и кластерная группа 3 (кружился в синем). Правильный epsilon значение где-нибудь между 1 и 2.
Используйте epsilon значение 1.55 кластеризировать данные.
epsilon3 = 1.55; labels3 = dbscan(X,epsilon3,minpts);
Визуализируйте кластеризацию и аннотируйте фигуру, чтобы подсветить определенные кластеры.
gscatter(X(:,1),X(:,2),labels3); title('epsilon = 1.55 and minpts = 50') grid annotation('ellipse',[0.54 0.41 .07 .07],'Color','red') annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue') annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')
dbscan делает лучшее задание идентификации кластеров когда epsilon установлен в 1.55. Например, функция идентифицирует отличные кластеры, окруженные в красном, черном цвете цвете, и синий (с центрами вокруг (3,–4), (–6,18), и (2.5,18), соответственно).
[1] Сложный эфир, M., H.-P. Kriegel, Дж. Сандер и Кс. Ксиэауэи. “Основанный на плотности алгоритм для обнаружения кластеров в больших пространственных базах данных с шумом”. В Продолжениях Второй Международной конференции по вопросам Открытия Знаний в Базах данных и Анализа данных, 226-231. Портленд, OR: Нажатие AAAI, 1996.