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

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

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

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

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

BIRCH (balanced iterative reducing and clustering using hierarchies)- самостоятельный алгоритм, применяемый в области Data mining и использующий принципы иерархической кластеризации. Если имеется очень большой набор данных, то в пространстве он распределен, как правило, неравномерно. Кластерный анализ определяет места наибольшего и наименьшего скоплений, чтобы таким образом понять всю картину целиком. Кроме того, полученные кластеры визуализируются гораздо нагляднее, чем первоначальные данные. Задачей алгоритмов кластеризации является не только простое разбиение данных на кластеры, но и использование при этом ограниченной памяти (как правило, размер доступной памяти гораздо меньше, чем размер исходного набора данных)и минимизация времени, требуемого на операции ввода/вывода.

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

3 Литература

[1] Википедия