Участник:Smirnov.maxim/BIRCH: различия между версиями
| Строка 28: | Строка 28: | ||
Решением этих проблем стал алгоритм, известный как BIRCH. | Решением этих проблем стал алгоритм, известный как BIRCH. | ||
| − | '''BIRCH'''<ref>[http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf | + | '''BIRCH'''<ref>[Нейский И.М. Классификация и сравнение методов кластеризации http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf]</ref><ref>[T Zhang, R Ramakrishnan, M Livny. BIRCH: An Efficient Data Clustering Method for Very Large Databases - 1996. - С.103-114)- алгоритм, применяемый в области [https://ru.wikipedia.org/wiki/Data_mining Data mining] и использующий принципы [https://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F иерархической кластеризации]. |
Если имеется очень большой набор данных, то в пространстве он распределен, как правило, неравномерно. Кластерный анализ определяет места наибольшего и наименьшего скоплений, чтобы таким образом понять всю картину целиком. Кроме того, полученные кластеры визуализируются гораздо нагляднее, чем начальные "сырые" данные. | Если имеется очень большой набор данных, то в пространстве он распределен, как правило, неравномерно. Кластерный анализ определяет места наибольшего и наименьшего скоплений, чтобы таким образом понять всю картину целиком. Кроме того, полученные кластеры визуализируются гораздо нагляднее, чем начальные "сырые" данные. | ||
| Строка 308: | Строка 308: | ||
* Вычисление величин <math>\vec{LS},\vec{X0}, R, D, D_0-D_4</math>, в процессе чего выполняются операции сложения и скалярного произведения векторов. | * Вычисление величин <math>\vec{LS},\vec{X0}, R, D, D_0-D_4</math>, в процессе чего выполняются операции сложения и скалярного произведения векторов. | ||
| − | Другим способом параллелизации алгоритма может служить создание и заполнение сразу множества кластерных деревьев, между которыми будут распределены входные данные. Множество всех подкластеров листьевых узлов полученных таким образом деревьев может быть подвергнуто глобальной кластеризации с помощью какого-либо из известных параллельных алгоритмов, например, k-средних<ref>[ | + | Другим способом параллелизации алгоритма может служить создание и заполнение сразу множества кластерных деревьев, между которыми будут распределены входные данные. Множество всех подкластеров листьевых узлов полученных таким образом деревьев может быть подвергнуто глобальной кластеризации с помощью какого-либо из известных параллельных алгоритмов, например, k-средних<ref>[A Garg, N Gupta PBIRCH: A Scalable Parallel Clustering algorithm for Incremental Data //10th International Database Engineering and Applications Symposium (IDEAS'06), 2006]</ref>. |
== Входные и выходные данные алгоритма == | == Входные и выходные данные алгоритма == | ||
Версия 18:54, 31 октября 2016
Авторы: Морозова Светлана, Смирнов Максим. Вклад авторов:
Смирнов максим:
- п.1.5
- п.1.7
- п.1.8
- п.1.9
- п.2.7
Морозова Светлана
- п.1.1
- п.1.2
- п.1.3
- п.1.4
- п.1.6
- п.1.10
- п.3
Содержание
- 1 Свойства и структура алгоритмов
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Нахождение полезных для анализа закономерностей в больших объёмах данных с недавних пор вызывает значительный интерес. В связи с этим ввелось и стало активно развиваться такое понятие как кластеризация.
Ранние работы и алгоритмы, разработанные в этой области, не уделяли достаточного внимания анализу очень больших наборов данных или минимизации издержек на процессы ввода-вывода. Решением этих проблем стал алгоритм, известный как BIRCH.
BIRCH[1]Ошибка цитирования Отсутствует закрывающий тег </ref>.
1.2 Входные и выходные данные алгоритма
Входные данные:
- Набор из [math]N[/math] точек [math]\{X_i\}, i=1,...,N[/math] размерности [math]d[/math].
Выходные данные:
- Кластерное дерево с не более чем [math]\frac{M}{P}[/math] узлами.
1.3 Свойства алгоритма
1.3.1 Достоинства алгоритма
По сравнению с предыдущими методами BIRCH обладает следующими достоинствами:
1. BIRCH является локальным алгоритмом, то есть каждое решение о каждом элементе кластера принимается без повторного сканирования данных или уже существующих кластеров. Используются только метрики, отражающие близость элементов друг к другу.
2. BIRCH использует факт неравномерного распределения данных в пространстве и поэтому не все данные рассматриваются как одинаково важные для построения кластера. Области с большой плотностью обрабатываются как единый кластер. Данные в более разреженных областях могут удаляться (опционально).
3. BIRCH использует всю доступную память для получения наилучших из возможных подкластеров, в то же время минимизируя затраты на операции ввода/вывода. Оптимизация процесса кластеризации достигается за счет использования взвешенно-сбалансированного дерева. При этом время исполнения линейно.
4. BIRCH не требует всего набора данных заранее (при этом просматривает его всего один раз).
1.3.2 Недостатки алгоритма
1. Алгоритм позволяет работать только с числовыми данными.
2. BIRCH хорошо выделяет только кластеры сферической формы.
3. Существует необходимость в задании пороговых значений.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
В составе пакетов и библиотек:
Пользовательские реализации:
3 Литература
[1] Нейский И.М. Классификация и сравнение методов кластеризации http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf
[2] T Zhang, R Ramakrishnan, M Livny. BIRCH: An Efficient Data Clustering Method for Very Large Databases - 1996. - С.103-114
[3] A Garg, N Gupta PBIRCH: A Scalable Parallel Clustering algorithm for Incremental Data //10th International Database Engineering and Applications Symposium (IDEAS'06), 2006
- ↑ [Нейский И.М. Классификация и сравнение методов кластеризации http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf]
