DBSCAN

Введение в DBSCAN

Основанная на плотности пространственная кластеризация приложений с шумом (DBSCAN) идентифицирует произвольно сформированные кластеры и шум (выбросы) в данных. Функция Statistics and Machine Learning Toolbox™ dbscan выполняет кластеризацию на входные данные матрице или на парных расстояниях между наблюдениями. dbscan возвращает индексы кластера и вектор, указывающий наблюдения, являющиеся основными точками (точки внутри кластеров). В отличие от кластеризации k-means, алгоритм DBSCAN не требует предварительного знания количества кластеров, и кластеры не обязательно являются сфероидальными. DBSCAN также полезен для определения выбросов на основе плотности, поскольку он идентифицирует точки, которые не относятся ни к одному кластеру.

Чтобы точка была назначена кластеру, она должна удовлетворять условию, что ее эпсилоновая окрестность (epsilon) содержит по крайней мере минимальное количество соседей (minpts). Или точка может лежать в районе эпсилона другой точки, которая удовлетворяет epsilon и minpts условия. Алгоритм DBSCAN идентифицирует три типа точек:

  • Основная точка - точка в кластере, которая имеет по крайней мере minpts соседи в его районе эпсилона

  • Пограничная точка - точка в кластере, которая имеет меньше minpts соседи в его районе эпсилона

  • Шумовая точка - выбросы, который не принадлежит ни одному кластеру

DBSCAN работает с широкой областью значений метрик расстояния, и вы можете задать пользовательскую метрику расстояния для вашего конкретного приложения. Выбор метрики расстояния определяет форму окрестности.

Описание алгоритма

Для заданных значений окружности эпсилона epsilon и минимальное количество соседей minpts необходимый для точки ядра, dbscan функция реализует 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 маркируются.

Определите значения параметров DBSCAN

В этом примере показано, как выбрать значения для 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')

Figure contains an axes. The axes contains an object of type scatter.

Центр набора точек (обведён красным цветом) содержит крышу и капот транспортного средства. Все остальные точки являются препятствиями.

Выберите значение для 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, найдите расстояние до 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

Figure contains an axes. The axes with title k-distance graph contains an object of type line.

Колено, по-видимому, около 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')

Figure contains an axes. The axes with title epsilon = 2 and minpts = 50 contains 12 objects of type line. These objects represent -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.

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')

Figure contains an axes. The axes with title epsilon = 1 and minpts = 50 contains 17 objects of type line. These objects represent -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16.

При помощи меньшего значения эпсилона 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')

Figure contains an axes. The axes with title epsilon = 1.55 and minpts = 50 contains 16 objects of type line. These objects represent -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

dbscan делает лучшую работу по идентификации кластеров при epsilon установлено в 1.55. Например, функция идентифицирует отдельные кластеры, окруженные красным, черным и синим цветом (с центрами вокруг (3,–4), (-6,18), и (2.5,18), соответственно).

Ссылки

[1] Эстер, М., H.-P. Кригель, Дж. Сандер, и X. Сяовэй. «Основанный на плотности алгоритм для обнаружения кластеров в больших пространственных базах данных с шумом». В материалах второй Международной конференции по открытию знаний в базах данных и майнингу данных, 226-231. Portland, OR: AAAI Press, 1996.

Похожие темы