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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть в кластере имеются [math]N[/math] точек размерности [math]d[/math]: [math]{\vec{{X_i}}}[/math], где [math]i= 1,2, ...,N[/math]. Тогда центроид [math]{\vec{{X_0}}}[/math], радиус [math]R[/math] и диаметр [math]D[/math] кластера определяются следующим образом:

[math]{\vec{X_0}}=\frac{\sum_{i=1}^N\vec{X_i}}{N}[/math]

[math]R = (\frac{\sum_{i=1}^N{(\vec{X_i} - \vec{X_0})}^2}{N})^{1/2}[/math]

[math]D = (\frac{\sum_{i=1}^N\sum_{j=1}^N{(\vec{X_i} - \vec{X_j})}^2}{N(N-1)})^{1/2}[/math]

[math]R[/math] - это среднее расстояние от каждой точки до центроида. [math]D[/math] - это среднее расстояние между парами в кластере. Это две альтернативные метрики плотности кластера вокруг центроида.

Для измерения близости друг к другу двух кластеров мы введём следующие 5 метрик.

Пусть даны центроиды двух кластеров [math]\vec{X_{01}}[/math] и [math]\vec{X_{02}}[/math]. Евклидова метрика [math]D_0[/math] и метрика Манхэттена [math]D1[/math] между двумя кластерами определяются следующим образом:

[math]D_0 = ((\vec{X_{01}}-\vec{X_{02}})^2)^{1/2}[/math]

[math]D_1 = |\vec{X_{01}}-\vec{X_{02}}| = \sum_{i=1}^d |{\vec{X_{01}}}^{(i)}-{\vec{X_{02}}}^{(i)}| [/math]

Пусть в одном кластере имеются [math]N_1[/math] точек размерности [math]d[/math]: [math]{\vec{{X_i}}}[/math], где [math]i= 1,2, ...,N_1[/math], а в другом кластере

Пусть имеются два кластера, содержащих соответственно [math]N_1[/math] и [math]N_2[/math] точек размерности [math]d[/math]: [math]{{\vec{X_i}}}[/math], где [math]i= 1,2, ...,N_1[/math] и [math]{{\vec{X_j}}}[/math], где [math]i= N_1+1,N1+2, ...,N_1+N_2[/math].

[math][/math]

3 Литература

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