Участник:Smirnov.maxim/BIRCH

Авторы: Морозова Светлана, Смирнов Максим. Вклад авторов:

Смирнов максим:

• п.1.5
• п.1.7
• п.1.8
• п.1.9
• п.2.7

Морозова Светлана

• п.1.1
• п.1.2
• п.1.3
• п.1.4
• п.1.6
• п.1.10
• п.3

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

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

Нахождение полезных для анализа закономерностей в больших объёмах данных с недавних пор вызывает значительный интерес. В связи с этим ввелось и стало активно развиваться такое понятие как кластеризация.

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

BIRCH.

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.7 Существующие реализации алгоритма

В составе пакетов и библиотек:

• scikit-learn
• NU-MineBench

Пользовательские реализации:

• JBIRCH

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