Участник:Dmitry/Плотностный алгоритм кластеризации
Плотностный алгоритм кластеризации DBSCAN | |
Последовательный алгоритм | |
Последовательная сложность | [math]O(n \log n)[/math] |
Объём входных данных | [math]n[/math] |
Объём выходных данных | [math]n[/math] |
Авторы описания: Титов Д.Е.
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.
1.2 Математическое описание алгоритма
Плотность точек для данной точки [math]X[/math] определяется двумя параметрами. Первым из них является [math]\varepsilon[/math] – радиус «соседства» (приближенности) точки [math]X[/math]. Тогда множество [math]M_\varepsilon(X)[/math] будет включать в себя такие точки [math]f_i[/math], [math](i=\overline{1,n})[/math], для которых следующее неравенство будет истинно:
[math]dist(X,f_i) \le \varepsilon[/math], [math](i=\overline{1,n})[/math]
Функция [math]dist(var1, var2)[/math] определяет расстояние между объектами выборки [math]D[/math][1]. Это расстояние может вычисляться различными способами, например, как евклидово расстояние или с помощью метрики Минковского.
Вторым параметром определения плотности точек является [math]MCP[/math] – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу [math]\varepsilon[/math].
Точка [math]f_i[/math], [math](i=\overline{1,n})[/math] будет являться окруженной точкой (согласно [math]\varepsilon[/math] и [math]MCP[/math]) если:
[math]M_\varepsilon(X) \ge MPC[/math]
Это значит, что точка [math]f_i[/math], [math](i=\overline{1,n})[/math] окруженная, если количество «соседствующих» точек выборки [math]D[/math] окажется большим, либо равным значению параметра [math]MCP[/math] (рис. 1).
Точка [math]X[/math] является прямо достижимой по плотности от точки [math]f[/math] (при соответствующих [math]\varepsilon[/math] и [math]MPC[/math]), если точка [math]X \in M(X)[/math], т.е. точка [math]X[/math] – это одна из точек [math]f[/math] для другого окружения (соседства), где [math]f[/math] – окруженная точка (рис. 2).
Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка [math]f[/math] достижима по плотности из точки [math]X[/math], но точка [math]X[/math] не достижима по плотности из точки [math]f[/math] (рис. 3).
Точка [math]X[/math] соединена (связана) по плотности с точкой [math]f[/math] (согласно [math]\varepsilon[/math] и [math]MCP[/math]) если существует точка [math]e[/math] такая, что обе точки [math]X[/math] и [math]f[/math] являются достижимыми от точки [math]e[/math] (согласно [math]\varepsilon[/math] и [math]MCP[/math]) (рис. 4).
Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.
В этом случае, под кластером понимается непустое подмножество точек [math]G[/math] из набора данных [math]D[/math], которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если [math]X \in G[/math] и [math]f[/math] достижима по плотности от точки [math]X[/math], тогда и [math]f \in G[/math], это значит, что обе точки принадлежат одному кластеру.
Свойство связности гласит, что каждый объект в подмножестве [math]G[/math] соединен по плотности со всеми объектами кластера (при заданных [math]\varepsilon[/math] и [math]MCP[/math]).
Все объекты из набора данных [math]D[/math] представляют собой совокупность подмножеств:
[math]D= \{ G_1, G_2,..., G_m, N \}[/math],
где [math]G_1, G_2,..., G_m[/math] – кластеры, образованные по плотности; [math]N[/math] – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств [math]G_1, G_2,..., G_m[/math].
1.3 Вычислительное ядро алгоритма
Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки [math]X[/math] входного множества [math]D[/math]. Основное время работы алгоритма используется на функцию [math]dist(var1, var2)[/math], определяющую расстояние между объектами выборки [math]D[/math] и сравнение расстояния с заданной [math]\varepsilon[/math] для того, чтобы определить "соседствующие" точки.
1.4 Макроструктура алгоритма
Вычисление расстояния между двумя объектами из выборки [math]D[/math] осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: [math]dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.[/math]
Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:
[math]dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}[/math].
1.5 Схема реализации последовательного алгоритма
Реализация алгоритма DBSCAN может быть разделена на два этапа[2]. В первую очередь из всего набора данных [math]D[/math] необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта [math]X[/math] из набора данных [math]D[/math] определить:
1) принадлежит ли текущий объект к какому-нибудь из кластеров;
2) является ли текущий объект окруженной точкой.
Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:
for [math]\forall X \in D[/math] [math]\{[/math] if [math] (X \in G_i, i= \overline{1,n})[/math] [math]\{[/math] if [math] (X_i \in M_\varepsilon(X))[/math] [math]\{[/math] find [math]X_i \in D[/math] достижимы по плотности from [math]X_i \in M_\varepsilon(X)[/math] [math]\}[/math] else if [math] (X_i \notin M_\varepsilon(X)[/math] and [math]X[/math] не достижим от любого другого объекта [math])[/math] [math]\{[/math] [math]X \in N[/math] [math]\}[/math] [math]\}[/math]
параметры [math]\varepsilon[/math] и [math]MCP[/math] задаются пользователем.
1.6 Последовательная сложность алгоритма
Сложность алгоритма зависит от поиска всех точек в [math]\varepsilon[/math]-окрестности конкретной точки [math]X[/math] из выборки [math]D[/math]. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность [math]O(n^2)[/math] (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до [math]O(\text{n log n})[/math].
1.7 Информационный граф
Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.
- Задаются параметры [math]\varepsilon[/math] и [math]MCP[/math].
- На входе алгоритма набор данных [math]D[/math] разбивается на множество точек [math]X_n[/math], где [math]n[/math] - количество точек.
- Для каждой точки [math]X_n[/math] из выборки [math]D[/math] с помощью функции [math]dist(var1, var2)[/math] определяется расстояние между остальными точками.
- Далее алгоритм объединяет точки [math]X_n[/math], образуя подмножества [math]M_\varepsilon(X_n)[/math], объекты которого удовлетворяют условию: [math]dist(X,f_i) \le \varepsilon[/math], [math](i=\overline{1,n})[/math].
- Если подмножество [math]M_\varepsilon(X_n)[/math] состоит из [math]MCP[/math] и больше объектов (т. е. [math]M_\varepsilon(X_n) \ge MPC[/math]), то подмножество [math]M_\varepsilon(X_n)[/math] образует кластер [math]G_m[/math].
- Подмножество [math]N[/math] включает в себя все объекты, которые не принадлежат ни одному из подмножеств [math]G_1, G_2,..., G_m[/math].
1.8 Ресурс параллелизма алгоритма
Ширина ярусно-параллельной формы алгоритма [math]O(m)[/math][3], где m - количество частей, на которые разбиваются все объекты из набора данных [math]D[/math]. Высотой ярусно-параллельной формы алгоритма является [math]O(|X| \log |X|)[/math], где [math]\mid X \mid[/math] - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.
1.9 Входные и выходные данные алгоритма
Входные данные: множество объектов из набора данных [math]D[/math], для которых задана метрическая функция расстояния [math]dist(var1, var2)[/math]. Объём входных данных: [math]n[/math].
Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: [math]n[/math].
Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра [math]MCP[/math], большие значения параметра [math]\varepsilon[/math] ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.
1.10 Свойства алгоритма
- Число настраиваемых параметров равно двум: [math]\varepsilon[/math] и [math]MPC[/math].
- Вычислительная сложность алгоритма [math]O(\text{n log n})[/math].
- Возможность обрабатывать большой объем данных.
- Результат не зависит от порядка ввода данных.
- Не требуется указывать количество кластеров.
- Возможность выделять кластеры в присутствии выбросов.
- Число итераций определено заранее[4].
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
Scikit-Learn включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.
SPMF предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).
Apache Commons Мath содержит java-реализацию алгоритма выполняющегося за квадратичное время.
ELKI предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.
Weka содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.
GNU R содержит DBSCAN в fpc пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R dbscan.
3 Литература
- ↑ Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.
- ↑ Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.
- ↑ https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)
- ↑ http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy