Участник:Dmitry/Плотностный алгоритм кластеризации

Авторы описания: Титов Д.Е.

1 Свойства и структура алгоритма

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

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

1.2 Математическое описание алгоритма

Плотность точек для данной точки $X$ определяется двумя параметрами. Первым из них является $\varepsilon$ – радиус «соседства» (приближенности) точки $X$. Тогда множество $M_\varepsilon(X)$ будет включать в себя такие точки $f_i$, $(i=\overline{1,n})$, для которых следующее неравенство будет истинно:

[math]dist(X,f_i) \le \varepsilon[/math], [math](i=\overline{1,n})[/math]

Функция $dist(var1, var2)$ определяет расстояние между объектами выборки $D$. Это расстояние может вычисляться различными способами, например, как евклидово расстояние или с помощью метрики Минковского.

Вторым параметром определения плотности точек является $MCP$ – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу $\varepsilon$.

Точка $f_i$, $(i=\overline{1,n})$ будет являться окруженной точкой (согласно $\varepsilon$ и $MCP$) если:

[math]M_\varepsilon(X) \le MPC[/math]

Это значит, что точка $f_i$, $(i=\overline{1,n})$ окруженная, если количество «соседствующих» точек выборки $D$ окажется большим, либо равным значению параметра $MCP$ (рис. 1).

Рис. 1. Окруженная точка при MPC = 5

Точка $X$ является прямо достижимой по плотности от точки $f$ (при соответствующих $\varepsilon$ и $MPC$), если точка $X \in M(X)$, т.е. точка $X$ – это одна из точек $f$ для другого окружения (соседства), где $f$ – окруженная точка (рис. 2).

Рис. 2. Точка X прямо достижима по плотности от точки f

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка $f$ достижима по плотности из точки $X$, но точка $X$ не достижима по плотности из точки $f$ (рис. 3).

Рис. 3. Достижимость по плотности