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

Участник:Igor.orpanen/Плотностный алгоритм кластеризации (DBSCAN): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
← Предыдущая правкаСледующая правка →
Нет описания правки
Нет описания правки
Строка 41: Строка 41:


== Масштабируемость алгоритма и его реализации ==
== Масштабируемость алгоритма и его реализации ==
*
 
== Динамические характеристики и эффективность реализации алгоритма ==
== Динамические характеристики и эффективность реализации алгоритма ==


Строка 47: Строка 47:


== Существующие реализации алгоритма ==
== Существующие реализации алгоритма ==
*
{| class="wikitable"
|-
! Реализация
! Технологии
! Лицензия
! Посдедовательная сложность
! Структуры данных
! Метрики
! Параллельность
|-
| [http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html Scikit learn]
| Python
| BSD 3
| <math>O(n \log n)</math>
| k-d tree, ball tree
| Любые
| style="background: #9F9;" | Есть
|-
| [https://github.com/alitouka/spark_dbscan alitouka/spark_dbscan]
| Scala, Spark
| GPLv2
| <math>O(n \log n)</math>
| r-tree
| Euclidean
| style="background: #9F9;" | Есть
|-
| [https://github.com/irvingc/dbscan-on-spark irvingc/dbscan-on-spark]
| Scala, Spark
| GPLv2
| <math>O(n \log n)</math>
| r-tree
| Euclidean
| style="background: #9F9;" | Есть
|-
| [https://github.com/propanoid/DBSCAN propanoid/DBSCAN]
| C++, Boost, OpenMP
| ABRMS
| <math>O(n \log n)</math>
| vantage-point tree
| Euclidean
| style="background: #9F9;" | Есть
|-
| [https://cran.r-project.org/web/packages/dbscan/index.html CRAN]
| R, C++
| GPLv3
| <math>O(n \log n)</math>
| k-d tree
| Euclidean
| style="background: #F99;" | Нет
|-
| [http://weka.sourceforge.net/doc.packages/optics_dbScan/weka/clusterers/DBScan.html Weka]
| Java
| GPLv3
| <math>O(n^2)</math>
| -
| Euclidean, Manhattan
| style="background: #F99;" | Нет
|-
| [https://commons.apache.org/proper/commons-math/javadocs/api-3.1/org/apache/commons/math3/stat/clustering/DBSCANClusterer.html Apache Commons]
| Java
| Apache 2.0
| <math>O(n^2)</math>
| -
| Euclidean
| style="background: #F99;" | Нет
|-
| [https://github.com/choffstein/dbscan choffstein/dbscan]
| Python
| -
| <math>O(n^2)</math>
| -
| Euclidean
| style="background: #F99;" | Нет
|}


= Литература =
= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

Версия от 21:48, 15 октября 2016


Плотностный алгоритм кластеризации (DBScan)
Последовательный алгоритм
Последовательная сложность [math]\displaystyle{ O(n \log n) }[/math]
Объём входных данных [math]\displaystyle{ - }[/math]
Объём выходных данных [math]\displaystyle{ - }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]\displaystyle{ - }[/math]
Ширина ярусно-параллельной формы [math]\displaystyle{ - }[/math]

Автор описания: Орпанен И.С.

ЧАСТЬ. Свойства и структура алгоритмов

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

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

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

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

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

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

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

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

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

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

ЧАСТЬ. Программная реализация алгоритма

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

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

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

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

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

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

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

Реализация Технологии Лицензия Посдедовательная сложность Структуры данных Метрики Параллельность
Scikit learn Python BSD 3 [math]\displaystyle{ O(n \log n) }[/math] k-d tree, ball tree Любые Есть
alitouka/spark_dbscan Scala, Spark GPLv2 [math]\displaystyle{ O(n \log n) }[/math] r-tree Euclidean Есть
irvingc/dbscan-on-spark Scala, Spark GPLv2 [math]\displaystyle{ O(n \log n) }[/math] r-tree Euclidean Есть
propanoid/DBSCAN C++, Boost, OpenMP ABRMS [math]\displaystyle{ O(n \log n) }[/math] vantage-point tree Euclidean Есть
CRAN R, C++ GPLv3 [math]\displaystyle{ O(n \log n) }[/math] k-d tree Euclidean Нет
Weka Java GPLv3 [math]\displaystyle{ O(n^2) }[/math] - Euclidean, Manhattan Нет
Apache Commons Java Apache 2.0 [math]\displaystyle{ O(n^2) }[/math] - Euclidean Нет
choffstein/dbscan Python - [math]\displaystyle{ O(n^2) }[/math] - Euclidean Нет

Литература

Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Участник:Igor.orpanen/Плотностный_алгоритм_кластеризации_(DBSCAN)&oldid=12208