Основанная на плотности Пространственная Кластеризация Приложений с Шумом (DBSCAN) идентифицирует кластеры произвольной формы и шум (выбросы) в данных. Функция Statistics and Machine Learning Toolbox™ dbscan выполняет кластеризацию на матрице входных данных или на попарных расстояниях между наблюдениями. dbscan возвращает кластерные индексы и вектор, указывающий на наблюдения, которые являются базовыми точками (точки в кластерах). В отличие от k - означает кластеризироваться, алгоритм DBSCAN не требует предварительных знаний количества кластеров, и кластеры являются не обязательно сфероидальными. DBSCAN также полезен для основанного на плотности определения выбросов, потому что это идентифицирует точки, которые не принадлежат никакому кластеру.
Для точки, которая будет присвоена кластеру, условие должно удовлетворить, что его окружение эпсилона (epsilon) содержит, по крайней мере, минимальное количество соседей (minpts). Или, точка может лечь в окружении эпсилона другой точки, которая удовлетворяет условия minpts и epsilon. Алгоритм 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-by-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.