Уровень алгоритма

Участник:Dadrik/Плотностный алгоритм кластеризации: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 85 промежуточных версий 6 участников)
Строка 1: Строка 1:
 +
{{Assignment|Sleo|Dexter}}
 +
 
{{algorithm
 
{{algorithm
 
| name              = Плотностный алгоритм кластеризации DBSCAN
 
| name              = Плотностный алгоритм кластеризации DBSCAN
−
| serial_complexity = <math>-</math>
+
| serial_complexity = <math>O(n \log n)</math>
−
| pf_height        = <math>-</math>
+
| input_data        = <math>n</math>
−
| pf_width          = <math>-</math>
+
| output_data      = <math>n</math>
−
| input_data        = <math>-</math>
 
−
| output_data      = <math>-</math>
 
 
}}
 
}}
 +
  
 
Авторы описания: [[Участник:Dadrik | Вашуров И.М.]], [[Участник:ramon93i7 | Шемякин Р.О.]]
 
Авторы описания: [[Участник:Dadrik | Вашуров И.М.]], [[Участник:ramon93i7 | Шемякин Р.О.]]
Строка 16: Строка 17:
 
Задача кластеризации - это задача разбиения заданной входной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались.
 
Задача кластеризации - это задача разбиения заданной входной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались.
  
−
Алгоритм DBSCAN (Density-based spatial clustering of applications with noise) был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в 1996 году как решение задачи кластеризации с кластерами произвольной формы. DBSCAN является непараметрическим плотностным алгоритмом кластеризации: для заданного набора точек в некотором пространстве, алгоритм группирует те точки, которые расположены достаточно близко друг к другу (точки с большим количеством соседей), и помечает как выбросы те, что располагаются далеко от ближайших соседей.
+
Алгоритм DBSCAN (Density-based spatial clustering of applications with noise)<ref>Ester, Martin, et al. "A density-based algorithm for discovering clusters in large spatial databases with noise." Kdd. Vol. 96. No. 34. 1996.</ref> был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в 1996 году как решение задачи кластеризации с кластерами произвольной формы. DBSCAN является непараметрическим плотностным алгоритмом кластеризации: для заданного набора точек в некотором пространстве, алгоритм группирует те точки, которые расположены достаточно близко друг к другу (точки с большим количеством соседей), и помечает как выбросы те, что располагаются далеко от ближайших соседей.
  
−
Близость в алгоритме определяется заданной в пространстве метрикой. Наиболее часто в качестве метрики используются Евклидово расстояние, квадрат Евклидова расстояния, манхэттенская метрика, расстояние Чебышева или степенное расстояние.
+
Близость в алгоритме определяется заданной в пространстве метрикой. Наиболее часто в качестве метрики используют Евклидово расстояние, квадрат Евклидова расстояния, манхэттенскую метрику, расстояние Чебышева или степенное расстояние.
 +
 
 +
Данный алгоритм кластеризации отличается от остальных тем, что не требует знаний о количестве кластеров, может определять кластеры произвольной формы, а также устойчив к шуму и выбросам.
  
 
== Математическое описание алгоритма ==
 
== Математическое описание алгоритма ==
−
=== Определения ===
 
 
Вход алгоритма: множество точек <math>X</math> из <math>n</math>-мерного пространства, на котором определена функция расстояния <math>D</math>.  
 
Вход алгоритма: множество точек <math>X</math> из <math>n</math>-мерного пространства, на котором определена функция расстояния <math>D</math>.  
  
Строка 30: Строка 32:
 
* <math>MinPts</math> - минимальное количество соседей для создания области связности.
 
* <math>MinPts</math> - минимальное количество соседей для создания области связности.
  
 +
 +
=== Определения ===
 +
 +
[[File:Cluster_scheme.png|thumb|right|400px| Рис. 1. [https://upload.wikimedia.org/wikipedia/commons/a/af/DBSCAN-Illustration.svg] Здесь ''MinPts'' = 4. Точка ''A'' и другие красные точки - ядровые и образуют единый кластер, так как достижимы друг из друга. Точки ''B'' и ''C'' не являются ядровыми, но достижимы из ''A'', а значит также принадлежат кластеру. Точка ''N'' - не достижима из других точек и является шумом.]]
  
 
Все заданные точки классифицируются на три группы:
 
Все заданные точки классифицируются на три группы:
  
−
* ядровые точки: точка <math>p</math> является ядровой, если количество <math>\varepsilon</math>-соседей, включая саму точку <math>p</math>, не меньше <math>MinPts</math>. Под <math>\varepsilon</math>-соседями точки <math>p \in X</math> понимается множество точек, расстояние до которых не превышает <math>\varepsilon</math>, т.е. <math>N_\varepsilon(p) = \{ x \in X | D(p, x) \le \varepsilon \}</math>. Эти точки являются напрямую достижимыми из <math>p</math>;
+
* ''ядровые точки'': точка <math>p</math> является ядровой, если количество <math>\varepsilon</math>-соседей, включая саму точку <math>p</math>, не меньше <math>MinPts</math>. Под ''<math>\varepsilon</math>-соседями'' точки <math>p \in X</math> понимается множество точек, расстояние до которых не превышает <math>\varepsilon</math>, т.е. <math>N_\varepsilon(p) = \{ x \in X | D(p, x) \le \varepsilon \}</math>. Эти точки являются напрямую достижимыми из <math>p</math>;
  
−
* достижимые точки: точка <math>q</math> достижима из <math>p</math>, если  существует путь <math>p_1, \dots, p_n</math>, где <math>p_1 = p</math> и <math>p_n = q</math>, для которого выполнено:  
+
* ''достижимые точки'': точка <math>q</math> достижима из <math>p</math>, если  существует путь <math>p_1, \dots, p_n</math>, где <math>p_1 = p</math> и <math>p_n = q</math>, для которого выполнено:  
 
:<math>\begin{align}
 
:<math>\begin{align}
 
p_{i + 1} \in N_\varepsilon(p_i),  i = 1, \dots, n-1 \\
 
p_{i + 1} \in N_\varepsilon(p_i),  i = 1, \dots, n-1 \\
−
\| N_\varepsilon(p_{i}) \| \ge MinPts, i = 1, \dots, n-1 \\
+
| N_\varepsilon(p_{i}) | \ge MinPts, i = 1, \dots, n-1 \\
 
\end{align}</math>
 
\end{align}</math>
  
−
* шум (выбросы): все точки, недостижимые из какой-либо другой точки считаются шумом (выбросом).
+
* ''шум'' (выбросы): все точки, недостижимые из какой-либо другой точки считаются шумом (выбросом).
  
 +
Так, если <math>p</math> - ядровая точка, то она образует кластер вместе со всеми точками, достижимыми из неё. Каждый кластер содержит по крайней мере одну ядровую точку; неядровые точки могут быть частью кластера, образуя при этом его "границу", так как они не могут быть использованы для достижения других точек.
  
−
Так, если <math>p</math> - ядровая точка, то она образует кластер вместе со всеми точками, достижимыми из неё. Каждый кластер содержит по крайней мере одну ядровую точку; неядровые точки могут быть частью кластера, образуя при этом его "границу", так как они не могут быть использованы для достижения других точек.
 
  
−
Достижимость не является симметричным отношением, так как по определению никакая точка не может быть достижима из неядровой точки, независимо от расстояния. Поэтому в DBSCAN применяется следующий термин связности: две точки <math>p</math> и <math>q</math> связанны, если существует такая точка <math>o</math>, что <math>p</math> и <math>q</math> достижимы из <math>o</math>. Такое отношение связности симметрично.
+
Достижимость не является симметричным отношением, так как по определению никакая точка не может быть достижима из неядровой точки, независимо от расстояния. Поэтому в DBSCAN применяется следующий термин ''связности'': две точки <math>p</math> и <math>q</math> связанны, если существует такая точка <math>o</math>, что <math>p</math> и <math>q</math> достижимы из <math>o</math>. Такое отношение связности симметрично.
 +
 
  
−
Кластер в таком случае определяется двумя свойствами:
+
''Кластер'' в таком случае определяется двумя свойствами:
 
* Все точки внутри кластера взаимно связанны;
 
* Все точки внутри кластера взаимно связанны;
 
* Если точка достижима из любой точки кластера, она также является частью кластера.
 
* Если точка достижима из любой точки кластера, она также является частью кластера.
−
 
  
 
=== Шаги алгоритма ===
 
=== Шаги алгоритма ===
Строка 58: Строка 64:
 
#Точка <math>p</math> помечается как посещенная.  
 
#Точка <math>p</math> помечается как посещенная.  
 
#У точки <math>p</math> определяется множество её <math>\varepsilon</math>-соседей - <math>N_\varepsilon(p)</math>.
 
#У точки <math>p</math> определяется множество её <math>\varepsilon</math>-соседей - <math>N_\varepsilon(p)</math>.
−
#*Если точка <math>p</math> оказалась ядровой - <math>\| N_\varepsilon(p) \| \ \ge MinPts</math>, то:  
+
#*Если точка <math>p</math> оказалась ядровой - <math>| N_\varepsilon(p) | \ \ge MinPts</math>, то:  
 
#**она становится началом нового кластера или сохраняет номер кластера, который был ей присвоен ранее;  
 
#**она становится началом нового кластера или сохраняет номер кластера, который был ей присвоен ранее;  
 
#**все точки из <math>N_\varepsilon(p)</math> добавляются в её кластер;
 
#**все точки из <math>N_\varepsilon(p)</math> добавляются в её кластер;
−
#**процесс продолжается рекурсивно для каждой новой добавленной точки <math>p' \in N_\varepsilon(p)</math> c шага 2 (в качестве новой <math>p</math>).
+
#**процесс продолжается рекурсивно для каждой новой добавленной непосещенной точки <math>p' \in N_\varepsilon(p)</math> c шага 2 (в качестве новой <math>p</math>).
 
#*Если точка <math>p</math> оказалась не ядровой, то <math>p</math> объявляется шумом. Алгоритм продолжается с шага 4.
 
#*Если точка <math>p</math> оказалась не ядровой, то <math>p</math> объявляется шумом. Алгоритм продолжается с шага 4.
 
#Если остались непосещенные точки, то алгоритм продолжается с шага 1.
 
#Если остались непосещенные точки, то алгоритм продолжается с шага 1.
Строка 67: Строка 73:
 
== Вычислительное ядро алгоритма ==
 
== Вычислительное ядро алгоритма ==
  
−
Вычислительным ядром алгоритма является нахождение <math>\varepsilon</math>-соседей для каждой точки входного множества.
+
Вычислительным ядром алгоритма является нахождение <math>\varepsilon</math>-соседей каждой точки входного множества <math>X</math>.  
  
−
>>>В описываемом алгоритме выделяется и описывается [[глоссарий#Вычислительное ядро|''вычислительное ядро'']], т.е. та часть алгоритма, на которую приходится основное время работы алгоритма. Если в алгоритме несколько вычислительных ядер, то отдельно описывается каждое ядро. Описание может быть сделано в достаточно произвольной форме: словесной или с использованием языка математических формул. Вычислительное ядро может полностью совпадать с описываемым алгоритмом.<<<
+
Для решения этой задачи требуется найти расстояния между любыми двумя точками множества <math>X</math> по заданной метрике. Например, если используется расстояние Минковского порядка <math>k</math>, то расстояние между точками <math>p=(p_1,...,p_n) \in X</math> и <math>q=(q_1,...,q_n) \in X</math> вычисляется как <math>D(p, q) = (\sum_{i = 1}^{n}|p_i - q_i|^k)^{1 / k}</math>, частным случаем которой при <math>k = 2</math> является широко распространённая евклидова метрика <math>D(p, q) = \sqrt{\sum_{i = 1}^{n} (p_i - q_i)^2}</math>.
  
 
== Макроструктура алгоритма ==
 
== Макроструктура алгоритма ==
−
Если алгоритм использует в качестве составных частей другие алгоритмы, то это указывается в данном разделе. Если в дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде (т.е. на уровне арифметических операций), а давать только его макроструктуру, то здесь описывается структура и состав макроопераций. Если в других разделах описания данного алгоритма в рамках AlgoWiki используются введенные здесь макрооперации, то здесь даются пояснения, необходимые для однозначной интерпретации материала. Типичные варианты макроопераций, часто встречающиеся на практике: нахождение суммы элементов вектора, скалярное произведение векторов, умножение  матрицы на вектор, решение системы линейных уравнений малого порядка, сортировка, вычисление значения функции в некоторой точке, поиск минимального значения в массиве, транспонирование матрицы, вычисление обратной матрицы и многие другие.
 
  
−
Описание макроструктуры очень полезно на практике. Параллельная структура алгоритмов может быть хорошо видна именно на макроуровне, в то время как максимально детальное отображение всех операций может сильно усложнить картину. Аналогичные аргументы касаются и многих вопросов реализации, и если для алгоритма эффективнее и/или технологичнее оставаться на макроуровне, оформив макровершину, например, в виде отдельной процедуры, то это и нужно отразить в данном разделе.
+
Как записано и в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть метода составляют вызовы функции <math>request\_neighbours</math> получения <math>\varepsilon</math>-соседей и нахождение расстояний между точками множества <math>X</math>.
−
Выбор макроопераций не однозначен, причем, выделяя различные макрооперации, можно делать акценты на различных свойствах алгоритмов. С этой точки зрения, в описании одного алгоритма может быть представлено несколько вариантов его макроструктуры, дающих дополнительную информацию о его структуре. На практике, подобные альтернативные формы представления макроструктуры алгоритма могут оказаться исключительно полезными для его эффективной реализации на различных вычислительных платформах.
 
  
 
== Схема реализации последовательного алгоритма ==
 
== Схема реализации последовательного алгоритма ==
  
−
  <math>DBSCAN(X, \varepsilon, MinPts)</math>
+
 
 +
<math>DBSCAN</math> проходит через все точки множества <math>X</math> и определяет, являются ли они шумом или началом нового кластера.
 +
В последнем случае новому кластеру присваивается уникальный номер и вызывается функция расширения кластера.
 +
 
 +
  <math>DBSCAN(\varepsilon, MinPts)</math>
 
   <math>C = 0</math>
 
   <math>C = 0</math>
 
   for <math>\forall p \in X</math>
 
   for <math>\forall p \in X</math>
Строка 86: Строка 94:
 
       mark <math>p</math> as visited
 
       mark <math>p</math> as visited
 
       <math>neighbours</math> = <math>request\_neighbours(p, \varepsilon)</math>
 
       <math>neighbours</math> = <math>request\_neighbours(p, \varepsilon)</math>
−
       if <math>\| neighbours \| < MinPts</math> then
+
       if <math>| neighbours | < MinPts</math> then
 
         mark <math>p</math> as <math>NOISE</math>
 
         mark <math>p</math> as <math>NOISE</math>
 
       else
 
       else
Строка 92: Строка 100:
 
         <math>expand\_cluster(p, neighbours, C, \varepsilon, MinPts)</math>
 
         <math>expand\_cluster(p, neighbours, C, \varepsilon, MinPts)</math>
  
−
 
+
<math>expand\_cluster</math> рекурсивно проходит через все точки множества <math>neighbours</math> - соседей точки <math>p</math>,
 +
и определяет, принадлежат ли эти точки тому же кластеру <math>C</math>, тем самым расширяя этот кластер.
 +
 
  <math>expand\_cluster(p, neighbours, C, \varepsilon, MinPts)</math>
 
  <math>expand\_cluster(p, neighbours, C, \varepsilon, MinPts)</math>
 
   add <math>p</math> to cluster <math>C</math>
 
   add <math>p</math> to cluster <math>C</math>
Строка 99: Строка 109:
 
         mark <math>p'</math> as visited
 
         mark <math>p'</math> as visited
 
         <math>neighbours'</math> = <math>request\_neighbours(p, \varepsilon)</math>
 
         <math>neighbours'</math> = <math>request\_neighbours(p, \varepsilon)</math>
−
         if <math>\| neighbours' \| \ \ge MinPts</math>
+
         if <math>| neighbours' | \ \ge MinPts</math>
 
             <math>neighbours</math> = <math>neighbours \cup neighbours'</math>   
 
             <math>neighbours</math> = <math>neighbours \cup neighbours'</math>   
 
       if <math>p'</math> is not yet member of any cluster
 
       if <math>p'</math> is not yet member of any cluster
 
         add <math>p'</math> to cluster <math>C</math>
 
         add <math>p'</math> to cluster <math>C</math>
  
 +
<math>request\_neighbours</math> возвращает для точки <math>p</math> множество всех её <math>\varepsilon</math>-соседей,
 +
используя функцию расстояния <math>D</math>
 +
<math>request\_neighbours(p, \varepsilon)</math>
 +
    return <math>\{ p' \ | \ \forall p' \in X: D(p, p') < \varepsilon \}</math>
  
−
<math>request\_neighbours(p, \varepsilon)</math>
+
== Последовательная сложность алгоритма ==
−
  return <math>\{ p' \ | \ \forall p' \in X: D(p, p') < \varepsilon \}</math>
 
  
 +
DBSCAN проходит через каждую точку входного множества, возможно, по несколько раз. Временная сложность зависит в большей степени от вызова функции <math>request\_neighbours</math> (нахождение <math>\varepsilon</math>-соседей для заданной точки). Эта функция вызывается ровно один раз для каждой точки множества <math>X</math>.
  
−
>>> Здесь описываются все шаги, которые нужно выполнить при последовательной реализации данного алгоритма. В некотором смысле, данный раздел является избыточным, поскольку математическое описание уже содержит всю необходимую информацию. Однако он, несомненно, полезен: схема реализации алгоритма выписывается явно, помогая однозначной интерпретации приводимых далее оценок и свойств.
+
Если использовать индексированную структуру данных (например, R-деревья), выполняющую операцию <math>request\_neighbours</math> за <math>O(\log n)</math>, то суммарная сложность алгоритма в среднем составит <math>O(n \log n)</math>, с учётом хорошо подобранного параметра <math>\varepsilon</math>, такого что в среднем <math>request\_neighbours</math> возвращает <math>O(\log n)</math> точек. Без использования ускоряющих структур или на вырожденных данных (таких, что все точки находятся на расстоянии меньшем, чем <math>\varepsilon</math> друг от друга) сложность по времени в худшем случае будет <math>O(n^2)</math>.  
  
−
Описание может быть выполнено в виде блок-схемы, последовательности математических формул, обращений к описанию других алгоритмов, фрагмента кода на Фортране, Си или другом языке программирования, фрагмента кода на псевдокоде и т.п. Главное - это сделать схему реализации последовательного алгоритма полностью понятной. Совершенно не обязательно все шаги детализировать до элементарных операций, отдельные шаги могут соответствовать макрооперациям, отвечающим другим алгоритмам.
 
  
−
Описание схемы реализации вполне может содержать и словесные пояснения, отражающие какие-либо тонкие нюансы самого алгоритма или его реализации. Уже в данном разделе можно сказать про возможный компромисс между объемом требуемой оперативной памяти и временем работы алгоритма, между используемыми структурами данных и степенью доступного параллелизма. В частности, часто возникает ситуация, когда можно ввести дополнительные временные массивы или же отказаться от использования специальных компактных схем хранения данных, увеличивая степень доступного параллелизма. <<<
+
Расстояния между точками можно вычислить заранее за <math>O(\frac {n(n - 1)}{2})</math>, например в виде матрицы расстояний, но это потребует <math>O(n^2)</math> памяти. Иначе, расстояния будут вычисляться при каждом запуске функции <math>request\_neighbours</math> за <math>O(n)</math> и потребуют <math>O(n)</math> памяти. Итоговая сложность вычисления расстояний в таком случае составляет <math>O(n^2)</math>. Сложность рассчета расстояний зависит от природы объектов из <math>X</math> и заданной метрики <math>D</math>. Например, если <math>X\subset\mathbb{R}^m</math>, то сложность равна <math>O(m)</math>, но оценка может быть улучшена при использовании векторных операций.
  
−
== Последовательная сложность алгоритма ==
+
== Информационный граф ==
  
−
DBSCAN проходит через каждую точку входного множества, возможно, по несколько раз. Временная сложность, однако, зависит в большей степени от вызова функции <math>request\_neighbours</math> (нахождение <math>\varepsilon</math>-соседей для заданной точки). Эта функция вызывается ровно один раз для каждой точки.
+
Опишем граф алгоритма<ref>Воеводин В.В.  Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref>.
  
−
Если использовать индексированную структуру данных, выполяющую операцию <math>request\_neighbours</math> за <math>O(\log n)</math>, то суммарная сложность алгоритма в среднем составит <math>O(n \log n)</math>, с учётом хорошо подобранного параметра <math>\varepsilon</math>, такого что в среднем <math>request\_neighbours</math> возвращает <math>O(\log n)</math> точек. Без использования ускоряющих структур или на вырожденных данных (таких, что все точки находятся на расстоянии меньшем, чем <math>\varepsilon</math> друг от друга) сложность по времени в худшем случае будет <math>O(n^2)</math>.
 
  
−
Для расчёта расстояний можно использовать матрицу расстояний размера <math>\frac {n^2 - n}{2}</math> с целью избежать перевычислений, но это потребует <math>O(n^2)</math> памяти, в то время как затраты по памяти реализации без такой матрицы составляют только <math>O(n)</math>.
+
[[File:Dbscan abstract.png |thumb|right|320px| Рис. 2. Внешний цикл алгоритма.]]
  
−
>>> В данном разделе описания свойств алгоритма приводится оценка его [[глоссарий#Последовательная сложность|''последовательной сложности'']], т.е. числа операций, которые нужно выполнить при последовательном исполнении алгоритма (в соответствии с [[#Описание схемы реализации последовательного алгоритма|п.1.5]]). Для разных алгоритмов понятие операции, в терминах которой оценивается его сложность, может существенно различаться. Это могут быть операции для работы с вещественными числами, целыми числами, поразрядные операции, обращения в память, обновления элементов массива, элементарные функции, макрооперации и другие. В LU-разложении преобладают арифметические операции над вещественными числами, а для транспонирования матриц важны лишь обращения к памяти: это и должно найти отражение в описании.
 
  
−
Если выбор конкретного типа операций для оценки сложности алгоритма не очевиден, то нужно привести обоснование возможных вариантов. В некоторых случаях можно приводить оценку не всего алгоритма, а лишь его вычислительного ядра: в таком случае это нужно отметить, сославшись [[#Общее описание алгоритма|на п.1.1]].  
+
На рис. 2 изображен информационный граф внешнего цикла алгоритма, который соответствует коду основной функции <math>DBSCAN</math>:
 +
*Макрооперация ''Init'' заключается в получении множества <math>X</math> и инициирования вспомогательных структур.  
 +
*Макрооперация ''Choose'' производит выбор непосещенной точки из <math>X</math>.
 +
*Макрооперация ''Build cluster'' строит кластер, если точка ядровая, или объявляет ее шумом.
  
−
Например, сложность алгоритма суммирования элементов вектора сдваиванием равна <math>n-1</math>. Сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки – <math>n\log_2n</math> операций комплексного сложения и <math>(n\log_2n)/2</math> операций комплексного умножения. Сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> вычислений квадратного корня, <math>n(n-1)/2</math> операций деления, по <math>(n^3-n)/6</math> операций умножения и сложения (вычитания). <<<
 
  
−
== Информационный граф ==
+
Переход от ''Build cluster'' к ''Choose'' заключает в себе зависимость данных о принадлежности некоторых точек к текущему кластеру или шуму и об их посещенности.
−
Это очень важный раздел описания. Именно здесь можно показать (увидеть) как устроена параллельная структура алгоритма, для чего приводится описание и изображение его информационного графа ([[глоссарий#Граф алгоритма|''графа алгоритма'']] [1]). Для рисунков с изображением графа будут составлены рекомендации по их формированию, чтобы все информационные графы, внесенные в энциклопедию, можно было бы воспринимать и интерпретировать одинаково. Дополнительно можно привести полное параметрическое  описание графа в терминах покрывающих функций [1].
 
  
−
Интересных вариантов для отражения информационной структуры алгоритмов много. Для каких-то алгоритмов нужно показать максимально подробную структуру, а иногда важнее макроструктура. Много информации несут разного рода проекции информационного графа, выделяя его регулярные составляющие и одновременно скрывая несущественные детали. Иногда оказывается полезным показать последовательность в изменении графа при изменении значений внешних переменных  (например, размеров матриц): мы часто ожидаем "подобное" изменение информационного графа, но это изменение не всегда очевидно на практике.
+
[[File:Expand cluster 2.png |thumb|right|600px| Рис. 3. Расширение кластера.]]
  
−
В целом, задача изображения графа алгоритма весьма нетривиальна. Начнем с того, что это потенциально бесконечный граф, число вершин и дуг которого определяется значениями внешних переменных, а они могут быть весьма и весьма велики. В такой ситуации, как правило, спасают упомянутые выше соображения подобия, делающие графы для разных значений внешних переменных "похожими": почти всегда достаточно привести лишь один граф небольшого размера, добавив, что графы для остальных значений будут устроены "точно также". На практике, увы, не всегда все так просто, и здесь нужно быть аккуратным.
 
  
−
Далее, граф алгоритма - это потенциально многомерный объект. Наиболее естественная система координат для размещения вершин и дуг информационного графа опирается на структуру вложенности циклов в реализации алгоритма. Если глубина вложенности циклов не превышает трех, то и граф размещается в привычном трехмерном пространстве, однако для более сложных циклических конструкций с глубиной вложенности 4 и больше необходимы специальные методы представления и изображения графов.  
+
На рис. 3 изображен информационный граф алгоритма расширения кластера из начальной точки кластера:
 +
*Макрооперация ''Init'' заключается в создании кластера из его начальной вершины.
 +
*Макрооперация ''Nε'' вычисляет множество <math>\varepsilon</math>-соседей.
 +
*Желтым цветом обозначены узлы, в которых точки из <math>\varepsilon</math>-соседей классифицируются на ядровые, граничные точки и шум. В рамках операции для конкретного соседа вычисляется множество его <math>\varepsilon</math>-соседей.
 +
*Макрооперации ''Ñε'', ''Ňε'', ... производят объединение входных множеств.
 +
*Макрооперация ''Ø'' выполняется тогда, когда объединение входных множеств является пустым.
  
−
В данном разделе AlgoWiki могут использоваться многие интересные возможности, которые еще подлежат обсуждению: возможность повернуть граф при его отображении на экране компьютера для выбора наиболее удобного угла обзора, разметка вершин по типу соответствующим им операций, отражение [[глоссарий#Ярусно-параллельная форма графа алгоритма|''ярусно-параллельной формы графа'']] и другие. Но в любом случае нужно не забывать главную задачу данного раздела - показать информационную структуру алгоритма так, чтобы стали понятны все его ключевые особенности, особенности параллельной структуры, особенности множеств дуг, участки регулярности и, напротив, участки с недерминированной структурой, зависящей от входных данных.
 
  
−
На рис.1 показана информационная структура алгоритма умножения матриц, на рис.2 - информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей.
+
[[File:N eps 3.png        |thumb|right|320px| Рис. 4. Подсчет <math>\varepsilon</math>-соседей.]]
  
−
[[file:Fig1.svg|thumb|center|300px|Рис.1. Информационная структура алгоритма умножения матриц]]
+
На рис. 4 изображен информационный граф алгоритма вычисления множества <math>\varepsilon</math>-соседей:
−
[[file:Fig2.svg|thumb|center|300px|Рис.2. Информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей]]
+
*Операция ''D'' - вычисление расстояния между точками.
 +
*Операция ''ε'' - сравнение расстояния с ε.
 +
*Операция ''U'' - объединение результатов.
  
 
== Ресурс параллелизма алгоритма ==
 
== Ресурс параллелизма алгоритма ==
−
Здесь приводится оценка [[глоссарий#Параллельная сложность|''параллельной сложности'']] алгоритма: числа шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы [1]. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы и составом операций на ярусах.
 
  
−
Параллелизм в алгоритме часто имеет естественную иерархическую структуру. Этот факт очень полезен на практике, и его необходимо отразить в описании. Как правило, подобная иерархическая структура параллелизма хорошо отражается в последовательной реализации алгоритма через циклический профиль результирующей программы (конечно же, с учетом графа вызовов), поэтому циклический профиль ([[#Описание схемы реализации последовательного алгоритма|п.1.5]]) вполне  может быть использован и для отражения ресурса параллелизма.
+
Поиск <math>\varepsilon</math>-соседей требует вычисления <math>n</math> расстояний (функция <math>D</math>) и выполнения <math>n</math> сравнений с <math>\varepsilon</math>. Эти операции для каждой пары точек независимы и могут быть выполнены параллельно. Таким образом, при наличии неограниченного числа процессоров сложность поиска составит <math>O(1)</math>. Т.к. поиск выполняется для каждой точки ровно один раз, параллельная сложность всего алгоритма составит <math>O(n)</math>.
−
 
 
−
Для описания ресурса параллелизма алгоритма (ресурса параллелизма информационного графа) необходимо указать ключевые параллельные ветви в терминах [[глоссарий#Конечный параллелизм|''конечного'']] и [[глоссарий#Массовый параллелизм|''массового'']] параллелизма. Далеко не всегда ресурс параллелизма выражается просто, например, через [[глоссарий#Кооодинатный параллелизм|''координатный параллелизм'']] или, что то же самое, через независимость итераций некоторых циклов (да-да-да, циклы - это понятие, возникающее лишь на этапе реализации, но здесь все так связано… В данном случае, координатный параллелизм означает, что информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей). С этой точки зрения, не менее важен и ресурс [[глоссарий#Скошенный параллелизм|''скошенного параллелизма'']]. В отличие от координатного параллелизма, скошенный параллелизм намного сложнее использовать на практике, но знать о нем необходимо, поскольку иногда других вариантов и не остается: нужно оценить потенциал алгоритма, и лишь после этого, взвесив все альтернативы, принимать решение о конкретной параллельной реализации. Хорошей иллюстрацией может служить алгоритм, структура которого показана на рис.2: координатного параллелизма нет, но есть параллелизм скошенный, использование которого снижает сложность алгоритма с <math>n\times m</math> в последовательном случае до <math>(n+m-1)</math> в параллельном варианте.
 
−
 
 
−
Рассмотрим алгоритмы, последовательная сложность которых уже оценивалась в [[#Последовательная сложность алгоритма|п.1.6]]. Параллельная сложность алгоритма суммирования элементов вектора сдваиванием равна <math>\log_2n</math>, причем число операций на каждом ярусе убывает с <math>n/2</math> до <math>1</math>. Параллельная сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки - <math>\log_2n</math>. Параллельная сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> шагов для вычислений квадратного корня, <math>(n-1)</math> шагов для операций деления и <math>(n-1)</math> шагов для операций умножения и сложения.
 
  
 
== Входные и выходные данные алгоритма ==
 
== Входные и выходные данные алгоритма ==
−
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.
 
  
−
== Свойства алгоритма ==
 
−
Описываются прочие свойства алгоритма, на которые имеет смысл обратить внимание на этапе реализации. Как и ранее, никакой привязки к конкретной программно-аппаратной платформе не предполагается, однако вопросы реализации в проекте AlgoWiki всегда превалируют, и необходимость обсуждения каких-либо свойств алгоритмов определяется именно этим.
 
  
−
Весьма полезным является ''соотношение последовательной и параллельной сложности'' алгоритма. Оба понятия мы рассматривали ранее, но здесь делается акцент на том выигрыше, который теоретически может дать параллельная реализация алгоритма. Не менее важно описать и те сложности, которые могут возникнуть в процессе получения параллельной версии алгоритма.  
+
Вход алгоритма: множество точек X из n-мерного пространства, на котором определена функция расстояния D. В наиболее распространенном случае пространственной кластеризации используется Евлидово расстояние между векторами из <math>\mathbb{R}^n</math>.
  
−
[[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна отношению числа операций к суммарному объему входных и выходных данных. Она показывает, сколько операций приходится на единицу переданных данных. Несмотря на простоту данного понятия, это значение исключительно полезно на практике: чем выше  вычислительная мощность, тем меньше накладных расходов вызывает перемещение данных для их обработки, например, на сопроцессоре, ускорителе или другом узле кластера. Например, вычислительная мощность скалярного произведения двух векторов равна всего лишь <math>1</math>, а вычислительная мощность алгоритма умножения двух квадратных матриц равна <math>2n/3</math>.
+
Выход алгоритма: размеченное множество точек <math>X</math>, в котором каждой точке соответствует номер ее кластера. Обычно каждой точке из <math>X</math> сопоставляется ее номер, а на выходе алгоритм дает отображение номеров точек в номера соответствующих им кластеров, например в виде вектора размера <math>|X|</math>.
  
−
Вопрос первостепенной важности на последующем этапе реализации - это [[глоссарий#Устойчивость|''устойчивость'']] алгоритма. Все, что касается различных сторон этого понятия, в частности, оценки устойчивости, должно быть описано в данном разделе.
+
== Свойства алгоритма ==
  
−
''Сбалансированность'' вычислительного процесса можно рассматривать с разных сторон. Здесь и сбалансированность типов операций, в частности, арифметических операций между собой (сложение, умножение, деление) или же арифметических операций по отношению к операциям обращения к памяти (чтение/запись). Здесь и сбалансированность операций между параллельными ветвями алгоритма. С одной стороны, балансировка нагрузки является необходимым условием эффективной реализации алгоритма. Вместе с этим, это очень непростая задача, и в описании должно быть отмечено явно, насколько алгоритм обладает этой особенностью. Если обеспечение сбалансированности не очевидно, желательно описать возможные пути решения этой задачи.
+
Соотношение последовательной и параллельной сложностей алгоритма является линейным (отношение квадратичной к линейной).
  
−
На практике важна [[глоссарий#Детерминированность|''детерминированность алгоритмов'']], под которой будем понимать постоянство структуры вычислительного процесса. С этой точки зрения, классическое умножение плотных матриц является детерминированным алгоритмом, поскольку его структура при фиксированном размере матриц никак не зависит от элементов входных матриц. Умножение разреженных матриц, когда матрица хранятся в одном из специальных форматов, свойством детерминированности уже не обладает: его свойства, например, степень локальности данных зависит от структуры разреженности входных матриц. Итерационный алгоритм с выходом по точности также не является детерминированным: число итераций, а значит и число операций, меняется в зависимости от входных данных. В этом же ряду стоит использование датчиков случайных чисел, меняющих вычислительный процесс для различных запусков программы. Причина выделения свойства детерминированности понятна: работать с детерминированным алгоритмом проще, поскольку один раз найденная структура и будет определять качество его реализации. Если детерминированность нарушается, то это должно быть здесь описано вместе с описанием того, как недетерминированность влияет на структуру вычислительного процесса.
+
При этом вычислительная мощность, как отношение числа операций к суммарному объему входных и выходных данных линейна.
  
−
Серьезной причиной недетерминированности работы параллельных программ является изменение порядка выполнения ассоциативных операций. Типичный пример - это использование глобальных MPI-операций на множестве параллельных процессов, например, суммирование элементов распределенного массива. Система времени исполнения MPI сама выбирает порядок выполнения операций, предполагая выполнение свойства ассоциативности, из-за чего ошибки округления меняются от запуска программы к запуску, внося изменения в конечный результат ее работы. Это очень серьезная проблема, которая сегодня встречается часто на системах с массовым параллелизмом и определяет отсутствие повторяемости результатов работы параллельных программ. Данная особенность характерна для [[#ЧАСТЬ. Программная реализация алгоритмов|второй части AlgoWiki]], посвященной реализации алгоритмов, но вопрос очень важный, и соответствующие соображения, по возможности, должны быть отмечены и здесь.
+
=== Преимущества алгоритма ===
  
−
Заметим, что, в некоторых случаях, недетерминированность в структуре алгоритмов можно "убрать" введением соответствующих макроопераций, после чего структура становится не только детерминированной, но и более понятной для восприятия. Подобное действие также следует отразить в данном разделе.
+
# не требует указывать число кластеров;
 +
# может определять кластера произвольной формы;
 +
# может определять шум и устойчив к выбросам;
 +
# требует всего два параметра и по в большинстве случаев не чувствителен к порядку заданных точек;
 +
# параллельная реализация сбалансирована по количеству и виду производимых операций (вычисление расстояния, сравнение с <math>\varepsilon</math>).
  
−
[[глоссарий#Степень исхода|''Степень исхода вершины информационного графа'']] показывает, в скольких операциях ее результат будет использоваться в качестве аргумента. Если степень исхода вершины велика, то на этапе реализации алгоритма нужно позаботиться об эффективном доступе к результату ее работы. В этом смысле, особый интерес представляют рассылки данных, когда результат выполнения одной операции используется во многих других вершинах графа, причем число таких вершин растет с увеличением значения внешних переменных.
+
=== Недостатки алгоритма ===
  
−
''"Длинные" дуги в информационном графе'' [1] говорят о потенциальных сложностях с размещением данных в иерархии памяти компьютера на этапе выполнения программы. С одной стороны, длина дуги зависит от выбора конкретной системы координат, в которой расположены вершины графа, а потому в другой системе координат они попросту могут исчезнуть (но не появится ли одновременно других длинных дуг?). А с другой стороны, вне зависимости от системы координат их присутствие может быть сигналом о необходимости длительного хранения данных на определенном уровне иерархии, что накладывает дополнительные ограничения на эффективность реализации алгоритма. Одной из причин возникновения длинных дуг являются рассылки скалярных величин по всем итерациям какого-либо цикла: в таком виде длинные дуги не вызывают каких-либо серьезных проблем на практике.
+
# не детерминирован: граничные точки, достижимые из более, чем одного кластера, могут быть частью любого из них в зависимости от порядка обрабатываемых данных. Однако такая ситуация возникает редко, а относительно ядровых точек и шума DBSCAN детерминирован. Впрочем, от недетерминизма можно избавиться, если считать все граничные точки шумом (алгоритм DBSCAN*);
−
 
+
# качество алгоритма зависит от используемой функции расстояния <math>D</math>. Наиболее часто используемое Евклидово расстояние в многомерных множествах может оказаться практически бесполезным из-за так называемого "проклятия размерности", значительно затрудняя нахождение подходящего значения <math>\varepsilon</math>;
−
Для проектирования специализированных процессоров или реализации алгоритма на ПЛИС представляют интерес ''компактные укладки информационного графа'' [1], которые также имеет смысл привести в данном разделе.
+
# не может выделять кластеры, имеющие разную плотность, так как параметры алгоритма не могут быть выбранны отдельно для каждого кластера.
  
 
= Программная реализация алгоритма =
 
= Программная реализация алгоритма =
−
Вторая часть описания алгоритмов в рамках AlgoWiki рассматривает все составные части процесса их реализации. Рассматривается как последовательная реализация алгоритма, так и параллельная. Описывается взаимосвязь свойств программ, реализующих алгоритм, и особенностей архитектуры компьютера, на которой они выполняются. Исследуется работа с памятью, локальность данных и вычислений, описывается масштабируемость и эффективность параллельных программ, производительность компьютеров, достигаемая на данной программе. Обсуждаются особенности реализации для разных классов архитектур компьютеров, приводятся ссылки на реализации в существующих библиотеках.
 
  
 
== Особенности реализации последовательного алгоритма ==
 
== Особенности реализации последовательного алгоритма ==
−
Здесь описываются особенности и варианты реализации алгоритма в виде последовательной программы, которые влияют на [[глоссарий#Эффективность реализации|''эффективность ее выполнения'']]. В частности, в данном разделе имеет смысл ''сказать о существовании блочных вариантов реализации алгоритма'', дополнительно описав потенциальные преимущества или недостатки, сопровождающие такую реализацию. Важный вопрос - это ''возможные варианты организации работы с данными'', варианты структур данных, наборов временных массивов и другие подобные вопросы. Для различных вариантов реализации следует оценить доступный ресурс параллелизма и объем требуемой памяти.
 
−
 
−
Важным нюансом является ''описание необходимой разрядности выполнения операций алгоритма'' (точности). На практике часто нет никакой необходимости выполнять все арифметические операции над вещественными числами с двойной точностью, т.к. это не влияет ни на устойчивость алгоритма, ни на точность получаемого результата. В таком случае, если значительную часть операций можно выполнять над типом float, и лишь в некоторых фрагментах необходим переход к типу double, это обязательно нужно отметить. Это прямое указание не только на правильную реализацию с точки зрения устойчивости по отношению к ошибкам округления, но и на более эффективную.
 
−
 
−
Опираясь на информацию из [[#Описание ресурса параллелизма алгоритма|п.1.8]] (описание ресурса параллелизма алгоритма), при описании последовательной версии стоит сказать про возможности [[глоссарий#Эквивалентное преобразование|''эквивалентного преобразования программ'']], реализующих данных алгоритм. В дальнейшем, это даст возможность простого использования доступного параллелизма или же просто покажет, как использовать присущий алгоритму параллелизм на практике. Например, параллелизм на уровне итераций самого внутреннего цикла обычно используется для векторизации. Однако, в некоторых случаях этот параллелизм можно поднять "вверх" по структуре вложенности объемлющих циклов, что делает возможной и эффективную реализацию данного алгоритма на многоядерных SMP-компьютерах.
 
−
 
−
С этой же точки зрения, в данном разделе весьма полезны соображения по реализации алгоритма на различных параллельных вычислительных платформах. Высокопроизводительные кластеры, многоядерные узлы, возможности для векторизации или использования ускорителей - особенности этих архитектур не только опираются на разные свойства алгоритмов, но и по-разному должны быть выражены в программах, что также желательно описать в данном разделе.
 
  
 
== Локальность данных и вычислений ==
 
== Локальность данных и вычислений ==
  
 
== Возможные способы и особенности параллельной реализации алгоритма ==
 
== Возможные способы и особенности параллельной реализации алгоритма ==
−
Раздел довольно обширный, в котором должны быть описаны основные факты и положения, формирующие параллельную программу. К их числу можно отнести:
 
−
* представленный иерархически ресурс параллелизма, опирающийся на структуру циклических конструкций и на граф вызовов программы;
 
−
* комбинацию (иерархию) массового параллелизма и параллелизма конечного;
 
−
* возможные способы распределения операций между процессами/нитями;
 
−
* возможные способы распределения данных;
 
−
* оценку количества операций, объёма и числа пересылок данных (как общего числа, так и в пересчёте на каждый параллельный процесс);
 
−
 
−
и другие.
 
−
 
−
В этом же разделе должны быть даны рекомендации или сделаны комментарии относительно реализации алгоритма с помощью различных технологий параллельного программирования: MPI, OpenMP, CUDA или использования директив векторизации.
 
  
 
== Масштабируемость алгоритма и его реализации ==
 
== Масштабируемость алгоритма и его реализации ==
−
Задача данного раздела - показать пределы [[глоссарий#Масштабируемость|''масштабируемости'']] алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование [[глоссарий#Сильная масштабируемость|''сильной'']] и [[глоссарий#Слабая масштабируемость|''слабой'']] масштабируемости алгоритма и его реализаций.
 
  
−
Масштабируемость алгоритма определяет свойства самого алгоритма безотносительно конкретных особенностей используемого компьютера. Она показывает, насколько параллельные свойства алгоритма позволяют использовать возможности растущего числа процессорных элементов. Масштабируемость параллельных программ определяется как относительно конкретного компьютера, так и относительно используемой технологии программирования, и в этом случае она показывает, насколько может вырасти реальная производительность данного компьютера на данной программе, записанной с помощью данной технологии программирования, при использовании бóльших вычислительных ресурсов (ядер, процессоров, вычислительных узлов).
+
!!! ЭКСПЕРИМЕНТЫ ДО 15 НОЯБРЯ !!!
−
 
 
−
Ключевой момент данного раздела заключается в том, чтобы показать ''реальные параметры масштабируемости программы'' для данного алгоритма на различных вычислительных платформах в зависимости от числа процессоров и размера задачи  [4]. При этом важно подобрать такое соотношение между числом процессоров и размером задачи, чтобы отразить все характерные точки в поведении параллельной программы, в частности, достижение максимальной производительности, а также тонкие эффекты, возникающие, например, из-за блочной структуры алгоритма или иерархии памяти.
 
−
 
 
−
На рис.5. показана масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи. На графике хорошо видны области с большей производительностью, отвечающие уровням кэш-памяти.
 
−
[[file:Масштабируемость перемножения матриц производительность.png|thumb|center|700px|Рис.5 Масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи]]
 
  
 
== Динамические характеристики и эффективность реализации алгоритма ==
 
== Динамические характеристики и эффективность реализации алгоритма ==
Строка 221: Строка 210:
  
 
== Существующие реализации алгоритма ==
 
== Существующие реализации алгоритма ==
−
Для многих пар алгоритм+компьютер уже созданы хорошие реализации, которыми можно и нужно пользоваться на практике. Данный раздел предназначен для того, чтобы дать ссылки на основные существующие последовательные и параллельные реализации алгоритма, доступные для использования уже сейчас. Указывается, является ли реализация коммерческой или свободной, под какой лицензией распространяется, приводится местоположение дистрибутива и имеющихся описаний. Если есть информация об особенностях, достоинствах и/или недостатках различных реализаций, то это также нужно здесь указать. Хорошими примерами реализации многих алгоритмов являются MKL, ScaLAPACK, PETSc, FFTW, ATLAS, Magma и другие подобные библиотеки.
+
 
 +
* [http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html Scikit learn (Python)]
 +
* [https://cran.r-project.org/web/packages/dbscan/dbscan.pdf R-project] ([https://github.com/mhahsler/dbscan github])
 +
* [https://www.mathworks.com/matlabcentral/fileexchange/52905-dbscan-clustering-algorithm Matlab]
 +
* P-DBSCAN (Parallel DBSCAN)<ref>Chen, Min, Xuedong Gao, and HuiFei Li. "Parallel DBSCAN with priority r-tree." Information Management and Engineering (ICIME), 2010 The 2nd IEEE International Conference on. IEEE, 2010.</ref>
 +
* Parallel DBSCAN with MPI<ref>Savvas, Ilias K., and Dimitrios Tselios. "Parallelizing DBSCaN Algorithm Using MPI." Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE), 2016 IEEE 25th International Conference on. IEEE, 2016.</ref>
 +
* PDSDBSCAN (Parallel Disjoint-Set DBSCAN)<ref>Patwary, Md Mostofa Ali, et al. "A new scalable parallel DBSCAN algorithm using the disjoint-set data structure." High Performance Computing, Networking, Storage and Analysis (SC), 2012 International Conference for. IEEE, 2012.</ref>
  
 
= Литература =
 
= Литература =
−
[1] Пестунов, Игорь Алексеевич, and Юрий Николаевич Синявский. "Алгоритмы кластеризации в задачах сегментации спутниковых изображений." Вестник Кемеровского государственного университета 4.2 (2012).
 
−
 
−
[x] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
 
−
 
−
[x] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.
 
−
 
−
[x] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.
 
−
 
−
[x] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.
 
  
−
[[en:Description of algorithm properties and structure]]
+
<references />

Текущая версия на 14:56, 3 декабря 2016

Symbol confirmed.svgЭта работа успешно выполнена
Преподавателю: в основное пространство, в подстраницу
Данное задание было проверено и зачтено.
Проверено Dexter и Sleo.



Плотностный алгоритм кластеризации DBSCAN
Последовательный алгоритм
Последовательная сложность [math]O(n \log n)[/math]
Объём входных данных [math]n[/math]
Объём выходных данных [math]n[/math]


Авторы описания: Вашуров И.М., Шемякин Р.О.

Содержание

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

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

Задача кластеризации - это задача разбиения заданной входной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались.

Алгоритм DBSCAN (Density-based spatial clustering of applications with noise)[1] был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в 1996 году как решение задачи кластеризации с кластерами произвольной формы. DBSCAN является непараметрическим плотностным алгоритмом кластеризации: для заданного набора точек в некотором пространстве, алгоритм группирует те точки, которые расположены достаточно близко друг к другу (точки с большим количеством соседей), и помечает как выбросы те, что располагаются далеко от ближайших соседей.

Близость в алгоритме определяется заданной в пространстве метрикой. Наиболее часто в качестве метрики используют Евклидово расстояние, квадрат Евклидова расстояния, манхэттенскую метрику, расстояние Чебышева или степенное расстояние.

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

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

Вход алгоритма: множество точек [math]X[/math] из [math]n[/math]-мерного пространства, на котором определена функция расстояния [math]D[/math].

Выход алгоритма: размеченное множество точек [math]X[/math], в котором каждой точке соответствует номер ее кластера.

Параметры алгоритма:

  • [math]\varepsilon[/math] - максимальное расстояние между соседями;
  • [math]MinPts[/math] - минимальное количество соседей для создания области связности.


1.2.1 Определения

Рис. 1. [1] Здесь MinPts = 4. Точка A и другие красные точки - ядровые и образуют единый кластер, так как достижимы друг из друга. Точки B и C не являются ядровыми, но достижимы из A, а значит также принадлежат кластеру. Точка N - не достижима из других точек и является шумом.

Все заданные точки классифицируются на три группы:

  • ядровые точки: точка [math]p[/math] является ядровой, если количество [math]\varepsilon[/math]-соседей, включая саму точку [math]p[/math], не меньше [math]MinPts[/math]. Под [math]\varepsilon[/math]-соседями точки [math]p \in X[/math] понимается множество точек, расстояние до которых не превышает [math]\varepsilon[/math], т.е. [math]N_\varepsilon(p) = \{ x \in X | D(p, x) \le \varepsilon \}[/math]. Эти точки являются напрямую достижимыми из [math]p[/math];
  • достижимые точки: точка [math]q[/math] достижима из [math]p[/math], если существует путь [math]p_1, \dots, p_n[/math], где [math]p_1 = p[/math] и [math]p_n = q[/math], для которого выполнено:
[math]\begin{align} p_{i + 1} \in N_\varepsilon(p_i), i = 1, \dots, n-1 \\ | N_\varepsilon(p_{i}) | \ge MinPts, i = 1, \dots, n-1 \\ \end{align}[/math]
  • шум (выбросы): все точки, недостижимые из какой-либо другой точки считаются шумом (выбросом).

Так, если [math]p[/math] - ядровая точка, то она образует кластер вместе со всеми точками, достижимыми из неё. Каждый кластер содержит по крайней мере одну ядровую точку; неядровые точки могут быть частью кластера, образуя при этом его "границу", так как они не могут быть использованы для достижения других точек.


Достижимость не является симметричным отношением, так как по определению никакая точка не может быть достижима из неядровой точки, независимо от расстояния. Поэтому в DBSCAN применяется следующий термин связности: две точки [math]p[/math] и [math]q[/math] связанны, если существует такая точка [math]o[/math], что [math]p[/math] и [math]q[/math] достижимы из [math]o[/math]. Такое отношение связности симметрично.


Кластер в таком случае определяется двумя свойствами:

  • Все точки внутри кластера взаимно связанны;
  • Если точка достижима из любой точки кластера, она также является частью кластера.

1.2.2 Шаги алгоритма

  1. Выбирается произвольная непосещенная точка [math]p[/math].
  2. Точка [math]p[/math] помечается как посещенная.
  3. У точки [math]p[/math] определяется множество её [math]\varepsilon[/math]-соседей - [math]N_\varepsilon(p)[/math].
    • Если точка [math]p[/math] оказалась ядровой - [math]| N_\varepsilon(p) | \ \ge MinPts[/math], то:
      • она становится началом нового кластера или сохраняет номер кластера, который был ей присвоен ранее;
      • все точки из [math]N_\varepsilon(p)[/math] добавляются в её кластер;
      • процесс продолжается рекурсивно для каждой новой добавленной непосещенной точки [math]p' \in N_\varepsilon(p)[/math] c шага 2 (в качестве новой [math]p[/math]).
    • Если точка [math]p[/math] оказалась не ядровой, то [math]p[/math] объявляется шумом. Алгоритм продолжается с шага 4.
  4. Если остались непосещенные точки, то алгоритм продолжается с шага 1.

1.3 Вычислительное ядро алгоритма

Вычислительным ядром алгоритма является нахождение [math]\varepsilon[/math]-соседей каждой точки входного множества [math]X[/math].

Для решения этой задачи требуется найти расстояния между любыми двумя точками множества [math]X[/math] по заданной метрике. Например, если используется расстояние Минковского порядка [math]k[/math], то расстояние между точками [math]p=(p_1,...,p_n) \in X[/math] и [math]q=(q_1,...,q_n) \in X[/math] вычисляется как [math]D(p, q) = (\sum_{i = 1}^{n}|p_i - q_i|^k)^{1 / k}[/math], частным случаем которой при [math]k = 2[/math] является широко распространённая евклидова метрика [math]D(p, q) = \sqrt{\sum_{i = 1}^{n} (p_i - q_i)^2}[/math].

1.4 Макроструктура алгоритма

Как записано и в описании ядра алгоритма, основную часть метода составляют вызовы функции [math]request\_neighbours[/math] получения [math]\varepsilon[/math]-соседей и нахождение расстояний между точками множества [math]X[/math].

1.5 Схема реализации последовательного алгоритма

[math]DBSCAN[/math] проходит через все точки множества [math]X[/math] и определяет, являются ли они шумом или началом нового кластера. В последнем случае новому кластеру присваивается уникальный номер и вызывается функция расширения кластера. 

[math]DBSCAN(\varepsilon, MinPts)[/math]
  [math]C = 0[/math]
  for [math]\forall p \in X[/math]
     if [math]p[/math] is visited then
        continue
     mark [math]p[/math] as visited
     [math]neighbours[/math] = [math]request\_neighbours(p, \varepsilon)[/math]
     if [math]| neighbours | \lt  MinPts[/math] then
        mark [math]p[/math] as [math]NOISE[/math]
     else
        [math]C = next\_cluster[/math]
        [math]expand\_cluster(p, neighbours, C, \varepsilon, MinPts)[/math]

[math]expand\_cluster[/math] рекурсивно проходит через все точки множества [math]neighbours[/math] - соседей точки [math]p[/math], и определяет, принадлежат ли эти точки тому же кластеру [math]C[/math], тем самым расширяя этот кластер. 

[math]expand\_cluster(p, neighbours, C, \varepsilon, MinPts)[/math]
  add [math]p[/math] to cluster [math]C[/math]
  for [math]\forall p' \in neighbours[/math]
     if [math]p'[/math] is not visited 
        mark [math]p'[/math] as visited
        [math]neighbours'[/math] = [math]request\_neighbours(p, \varepsilon)[/math]
        if [math]| neighbours' | \ \ge MinPts[/math]
           [math]neighbours[/math] = [math]neighbours \cup neighbours'[/math]  
     if [math]p'[/math] is not yet member of any cluster
        add [math]p'[/math] to cluster [math]C[/math]

[math]request\_neighbours[/math] возвращает для точки [math]p[/math] множество всех её [math]\varepsilon[/math]-соседей, используя функцию расстояния [math]D[/math] 

[math]request\_neighbours(p, \varepsilon)[/math]
   return [math]\{ p' \ | \ \forall p' \in X: D(p, p') \lt  \varepsilon \}[/math]

1.6 Последовательная сложность алгоритма

DBSCAN проходит через каждую точку входного множества, возможно, по несколько раз. Временная сложность зависит в большей степени от вызова функции [math]request\_neighbours[/math] (нахождение [math]\varepsilon[/math]-соседей для заданной точки). Эта функция вызывается ровно один раз для каждой точки множества [math]X[/math].

Если использовать индексированную структуру данных (например, R-деревья), выполняющую операцию [math]request\_neighbours[/math] за [math]O(\log n)[/math], то суммарная сложность алгоритма в среднем составит [math]O(n \log n)[/math], с учётом хорошо подобранного параметра [math]\varepsilon[/math], такого что в среднем [math]request\_neighbours[/math] возвращает [math]O(\log n)[/math] точек. Без использования ускоряющих структур или на вырожденных данных (таких, что все точки находятся на расстоянии меньшем, чем [math]\varepsilon[/math] друг от друга) сложность по времени в худшем случае будет [math]O(n^2)[/math].


Расстояния между точками можно вычислить заранее за [math]O(\frac {n(n - 1)}{2})[/math], например в виде матрицы расстояний, но это потребует [math]O(n^2)[/math] памяти. Иначе, расстояния будут вычисляться при каждом запуске функции [math]request\_neighbours[/math] за [math]O(n)[/math] и потребуют [math]O(n)[/math] памяти. Итоговая сложность вычисления расстояний в таком случае составляет [math]O(n^2)[/math]. Сложность рассчета расстояний зависит от природы объектов из [math]X[/math] и заданной метрики [math]D[/math]. Например, если [math]X\subset\mathbb{R}^m[/math], то сложность равна [math]O(m)[/math], но оценка может быть улучшена при использовании векторных операций.

1.7 Информационный граф

Опишем граф алгоритма[2][3][4].


Рис. 2. Внешний цикл алгоритма.


На рис. 2 изображен информационный граф внешнего цикла алгоритма, который соответствует коду основной функции [math]DBSCAN[/math]:

  • Макрооперация Init заключается в получении множества [math]X[/math] и инициирования вспомогательных структур.
  • Макрооперация Choose производит выбор непосещенной точки из [math]X[/math].
  • Макрооперация Build cluster строит кластер, если точка ядровая, или объявляет ее шумом.


Переход от Build cluster к Choose заключает в себе зависимость данных о принадлежности некоторых точек к текущему кластеру или шуму и об их посещенности.

Рис. 3. Расширение кластера.


На рис. 3 изображен информационный граф алгоритма расширения кластера из начальной точки кластера:

  • Макрооперация Init заключается в создании кластера из его начальной вершины.
  • Макрооперация Nε вычисляет множество [math]\varepsilon[/math]-соседей.
  • Желтым цветом обозначены узлы, в которых точки из [math]\varepsilon[/math]-соседей классифицируются на ядровые, граничные точки и шум. В рамках операции для конкретного соседа вычисляется множество его [math]\varepsilon[/math]-соседей.
  • Макрооперации Ñε, Ňε, ... производят объединение входных множеств.
  • Макрооперация Ø выполняется тогда, когда объединение входных множеств является пустым.


Рис. 4. Подсчет [math]\varepsilon[/math]-соседей.

На рис. 4 изображен информационный граф алгоритма вычисления множества [math]\varepsilon[/math]-соседей:

  • Операция D - вычисление расстояния между точками.
  • Операция ε - сравнение расстояния с ε.
  • Операция U - объединение результатов.

1.8 Ресурс параллелизма алгоритма

Поиск [math]\varepsilon[/math]-соседей требует вычисления [math]n[/math] расстояний (функция [math]D[/math]) и выполнения [math]n[/math] сравнений с [math]\varepsilon[/math]. Эти операции для каждой пары точек независимы и могут быть выполнены параллельно. Таким образом, при наличии неограниченного числа процессоров сложность поиска составит [math]O(1)[/math]. Т.к. поиск выполняется для каждой точки ровно один раз, параллельная сложность всего алгоритма составит [math]O(n)[/math].

1.9 Входные и выходные данные алгоритма

Вход алгоритма: множество точек X из n-мерного пространства, на котором определена функция расстояния D. В наиболее распространенном случае пространственной кластеризации используется Евлидово расстояние между векторами из [math]\mathbb{R}^n[/math].

Выход алгоритма: размеченное множество точек [math]X[/math], в котором каждой точке соответствует номер ее кластера. Обычно каждой точке из [math]X[/math] сопоставляется ее номер, а на выходе алгоритм дает отображение номеров точек в номера соответствующих им кластеров, например в виде вектора размера [math]|X|[/math].

1.10 Свойства алгоритма

Соотношение последовательной и параллельной сложностей алгоритма является линейным (отношение квадратичной к линейной).

При этом вычислительная мощность, как отношение числа операций к суммарному объему входных и выходных данных линейна.

1.10.1 Преимущества алгоритма

  1. не требует указывать число кластеров;
  2. может определять кластера произвольной формы;
  3. может определять шум и устойчив к выбросам;
  4. требует всего два параметра и по в большинстве случаев не чувствителен к порядку заданных точек;
  5. параллельная реализация сбалансирована по количеству и виду производимых операций (вычисление расстояния, сравнение с [math]\varepsilon[/math]).

1.10.2 Недостатки алгоритма

  1. не детерминирован: граничные точки, достижимые из более, чем одного кластера, могут быть частью любого из них в зависимости от порядка обрабатываемых данных. Однако такая ситуация возникает редко, а относительно ядровых точек и шума DBSCAN детерминирован. Впрочем, от недетерминизма можно избавиться, если считать все граничные точки шумом (алгоритм DBSCAN*);
  2. качество алгоритма зависит от используемой функции расстояния [math]D[/math]. Наиболее часто используемое Евклидово расстояние в многомерных множествах может оказаться практически бесполезным из-за так называемого "проклятия размерности", значительно затрудняя нахождение подходящего значения [math]\varepsilon[/math];
  3. не может выделять кластеры, имеющие разную плотность, так как параметры алгоритма не могут быть выбранны отдельно для каждого кластера.

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

!!! ЭКСПЕРИМЕНТЫ ДО 15 НОЯБРЯ !!!

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. ↑ Ester, Martin, et al. "A density-based algorithm for discovering clusters in large spatial databases with noise." Kdd. Vol. 96. No. 34. 1996.
  2. ↑ Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.
  3. ↑ Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.
  4. ↑ Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.
  5. ↑ Chen, Min, Xuedong Gao, and HuiFei Li. "Parallel DBSCAN with priority r-tree." Information Management and Engineering (ICIME), 2010 The 2nd IEEE International Conference on. IEEE, 2010.
  6. ↑ Savvas, Ilias K., and Dimitrios Tselios. "Parallelizing DBSCaN Algorithm Using MPI." Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE), 2016 IEEE 25th International Conference on. IEEE, 2016.
  7. ↑ Patwary, Md Mostofa Ali, et al. "A new scalable parallel DBSCAN algorithm using the disjoint-set data structure." High Performance Computing, Networking, Storage and Analysis (SC), 2012 International Conference for. IEEE, 2012.
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Dadrik/Плотностный_алгоритм_кластеризации&oldid=19973