Участник: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

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

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

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

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

BIRCH.

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

Входные данные:

• Набор из [math]\displaystyle{ N }[/math] точек [math]\displaystyle{ \{X_i\}, i=1,...,N }[/math] размерности [math]\displaystyle{ d }[/math].

Выходные данные:

• Кластерное дерево с не более чем [math]\displaystyle{ \frac{M}{P} }[/math] узлами.

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

Достоинства алгоритма

По сравнению с предыдущими методами BIRCH обладает следующими достоинствами:

1. BIRCH является локальным алгоритмом, то есть каждое решение о каждом элементе кластера принимается без повторного сканирования данных или уже существующих кластеров. Используются только метрики, отражающие близость элементов друг к другу.

2. BIRCH использует факт неравномерного распределения данных в пространстве и поэтому не все данные рассматриваются как одинаково важные для построения кластера. Области с большой плотностью обрабатываются как единый кластер. Данные в более разреженных областях могут удаляться (опционально).

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

4. BIRCH не требует всего набора данных заранее (при этом просматривает его всего один раз).

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

1. Алгоритм позволяет работать только с числовыми данными.

2. BIRCH хорошо выделяет только кластеры сферической формы.

3. Существует необходимость в задании пороговых значений.

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

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

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

• scikit-learn
• NU-MineBench

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

• JBIRCH

Литература

[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