Участник:Dmitry/Плотностный алгоритм кластеризации
Авторы описания: Титов Д.Е.
Свойства и структура алгоритма
Общее описание алгоритма
Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.
Математическое описание алгоритма
Плотность точек для данной точки [math]\displaystyle{ X }[/math] определяется двумя параметрами. Первым из них является [math]\displaystyle{ \varepsilon }[/math] – радиус «соседства» (приближенности) точки [math]\displaystyle{ X }[/math]. Тогда множество [math]\displaystyle{ M_\varepsilon(X) }[/math] будет включать в себя такие точки [math]\displaystyle{ f_i }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math], для которых следующее неравенство будет истинно:
[math]\displaystyle{ dist(X,f_i) \le \varepsilon }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math]
Функция [math]\displaystyle{ dist(var1, var2) }[/math] определяет расстояние между объектами выборки [math]\displaystyle{ D }[/math]. Это расстояние может вычисляться различными способами, например, как евклидово расстояние или с помощью метрики Минковского.
Вторым параметром определения плотности точек является [math]\displaystyle{ MCP }[/math] – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу [math]\displaystyle{ \varepsilon }[/math].
Точка [math]\displaystyle{ f_i }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math] будет являться окруженной точкой (согласно [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]) если:
[math]\displaystyle{ M_\varepsilon(X) \le MPC }[/math]
Это значит, что точка [math]\displaystyle{ f_i }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math] окруженная, если количество «соседствующих» точек выборки [math]\displaystyle{ D }[/math] окажется большим, либо равным значению параметра [math]\displaystyle{ MCP }[/math] (рис. 1).
Точка [math]\displaystyle{ X }[/math] является прямо достижимой по плотности от точки [math]\displaystyle{ f }[/math] (при соответствующих [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MPC }[/math]), если точка [math]\displaystyle{ X \in M(X) }[/math], т.е. точка [math]\displaystyle{ X }[/math] – это одна из точек [math]\displaystyle{ f }[/math] для другого окружения (соседства), где [math]\displaystyle{ f }[/math] – окруженная точка (рис. 2).
Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка [math]\displaystyle{ f }[/math] достижима по плотности из точки [math]\displaystyle{ X }[/math], но точка [math]\displaystyle{ X }[/math] не достижима по плотности из точки [math]\displaystyle{ f }[/math] (рис. 3).
Точка [math]\displaystyle{ X }[/math] соединена (связана) по плотности с точкой [math]\displaystyle{ f }[/math] (согласно [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]) если существует точка [math]\displaystyle{ e }[/math] такая, что обе точки [math]\displaystyle{ X }[/math] и [math]\displaystyle{ f }[/math] являются достижимыми от точки [math]\displaystyle{ e }[/math] (согласно [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]) (рис. 4).
Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.
В этом случае, под кластером понимается непустое подмножество точек [math]\displaystyle{ G }[/math] из набора данных [math]\displaystyle{ D }[/math], которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если [math]\displaystyle{ X \in G }[/math] и [math]\displaystyle{ f }[/math] достижима по плотности от точки [math]\displaystyle{ X }[/math], тогда и [math]\displaystyle{ f \in G }[/math], это значит, что обе точки принадлежат одному кластеру.
Свойство связности гласит, что каждый объект в подмножестве [math]\displaystyle{ G }[/math] соединен по плотности со всеми объектами кластера (при заданных [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]).
Все объекты из набора данных [math]\displaystyle{ D }[/math] представляют собой совокупность подмножеств:
[math]\displaystyle{ D= \{ G_1, G_2,..., G_n, N \} }[/math],
где [math]\displaystyle{ G_1, G_2,..., G_n }[/math] – кластеры, образованные по плотности; [math]\displaystyle{ N }[/math] – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств [math]\displaystyle{ G_1, G_2,..., G_n }[/math].
Вычислительное ядро алгоритма
Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки [math]\displaystyle{ X }[/math] входного множества [math]\displaystyle{ D }[/math]. Основное время работы алгоритма используется на функцию [math]\displaystyle{ dist(var1, var2) }[/math], определяющую расстояние между объектами выборки [math]\displaystyle{ D }[/math] и сравнение расстояния с заданной [math]\displaystyle{ \varepsilon }[/math] для того, чтобы определить "соседствующие" точки.