Пространственная кластеризация приложений с шумом на основе плотности (DBSCAN) идентифицирует произвольно сформированные кластеры и помехи (отклонения) в данных. Функция 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 объектов.
load('lidar_subset.mat')
X = lidar_subset;Чтобы выделить окружающую среду вокруг транспортного средства, задайте область, представляющую интерес, которая будет охватывать 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,:);
Визуализация данных в виде графика рассеяния 2-D. Аннотирование графика для выделения транспортного средства.
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найдите расстояние до k-ой ближайшей точки и постройте график отсортированных точек относительно этого расстояния. График содержит колено. Расстояние, которое соответствует колену, как правило, хороший выбор для 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] Эфир, М., H.P. Кригель, Дж. Сандер и Х. Сяовэй. «Алгоритм на основе плотности для обнаружения кластеров в больших пространственных базах данных с шумом». В материалах второй Международной конференции по открытию знаний в области баз данных и интеллектуального анализа данных, 226-231. Портленд, ИЛИ: AAAI Press, 1996.