Участник: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 Математическое описание алгоритма

1.2.1 (???) Введение

Пусть в кластере имеются [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]D_2[/math], среднее внутрикластерное расстояние [math]D_3[/math] и дисперсия [math]D_4[/math] между двумя кластерами определяются следующим образом:

[math]D_2 = (\frac{\sum_{i=1}^{N_1}\sum_{j=N_1+1}^{N_1+N_2}{(\vec{X_i} - \vec{X_j})}^2}{N_1N_2})^{1/2}[/math]

[math]D_3 = (\frac{\sum_{i=1}^{N_1+N_2}\sum_{j=1}^{N_1+N_2}{(\vec{X_i} - \vec{X_j})}^2}{(N_1+N_2)(N_1+N_2-1)})^{1/2}[/math]

[math]D_4 = \sum_{k=1}^{N_1+N_2}(\vec{X_k} - \frac{\sum_{i=1}^{N_1+N_2}\vec{X_i}}{N_1+N_2})^2 - \sum_{i=1}^{N_1}(\vec{X_i} - \frac{\sum_{i=1}^{N_1}\vec{X_i}}{N_1})^2 - \sum_{j=N_1+1}^{N_1+N_2}(\vec{X_j} - \frac{\sum_{i=N_1+1}^{N_1+N_2}\vec{X_i}}{N_2})^2[/math]

[math]D_3[/math] - это по сути [math]D[/math] для объединённого кластера.

Таким образом, величины [math]\vec{X_0}[/math], [math]R[/math] и [math]D[/math] относятся к отдельным кластерам, а [math]D_0[/math], [math]D_1[/math], [math]D_2[/math], [math]D_3[/math] и [math]D_4[/math] - к объединению двух кластеров.

1.2.2 Кластерные элементы и кластерное дерево

В основе концепции алгоритмы BIRCH лежат понятия кластерного элемента кластерного дерева (CF Tree).

1.2.2.1 Кластерный элемент

Определение. Пусть в кластере содержатся [math]N[/math] точек размерности [math]d[/math]:[math]\vec{X_i}[/math], где [math]i=1,2,...,N[/math]. Кластерный элемент (CF) - следующая тройка чисел, характеризующая информацию о кластере: [math]'''CF''' = (N, \vec{LS}, SS)[/math], где [math]N[/math] - количество элементов входнях данных, входящих в кластер, [math]\vec{LS}[/math] - линейная сумма входных данных (т.е. [math]\sum_{i=1}^{N}\vec{X_i}[/math]), [math]SS[/math] - сумма квадратов элементов входных данных (т.е. [math]\sum_{i=1}^{N}{\vec{X_i}}^2[/math])

Теорема Пусть [math]CF_1 = (N_1, \vec{LS_1}, SS_1)[/math] и [math]CF_2 = (N_1, \vec{LS_2}, SS_2)[/math] - CF векторы двух непересекающихся кластеров. Тогда при их объединении образуется кластер со следующим CF вектором:

[math]CF = CF_1 + CF_2 = (N_1+N_2, \vec{LS_1}+\vec{LS_2}, SS_1+SS_2)[/math].

Из указанных выше определения и теоремы вытекает тот факт, что при объединении кластеров CF вектор может вычисляться инкрементно и точно. Легко показать, что величины [math]\vec{X_0}[/math], [math]R[/math], [math]D[/math], [math]D_0[/math], [math]D_1[/math], [math]D_2[/math], [math]D_3[/math], [math]D_4[/math], как и обычные метрики, также могут вычисляться без труда.

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

1.2.2.2 Кластерное дерево

Определение. Кластерное дерево (CF Tree) - это взвешенно сбалансированное дерево с двумя параметрами: [math]B[/math] - коэффициент разветвления, [math]T[/math] - пороговая величина. Каждый нелистьевой узел дерева имеет не более чем [math]B[/math] вхождений узлов следующей формы: [math][CF_i,child_i][/math], где [math]i=1,2,...,B[/math], "child" - указатель на i-й дочерний узел, [math]CF_i[/math] - CF вектор соответствующего подкластера.

Каждый листьевой узел имеет ссылку на два соседних узла ("prev" и "next") для того чтобы связать все узлы для эффективного сканирования.

Все листьевые узлы должны удовлетворять пороговому ограничению [math]T[/math], т.е. диаметр (радиус) не должен превосходить [math]T[/math].

Размер дерева является функцией [math]T[/math]: чем больше [math]T[/math], тем меньше дерево. (???) Что-то там про Р.

После задания размерности данных [math]d[/math], а также размерности нелистьевых и листьевых узлов, величины [math]B[/math] и [math]L[/math] определяются при помощи [math]P[/math]. Поэтому мы можем изменять [math]P[/math] для (???)

В процессе вставки новых данных подобное [math]CF[/math] дерево строится динамически. Оно использует вставку данных для кластеризации точно также как [math]B+[/math] дерево использует её для поиска. CF очень компактно, поскольку каждый листьевой узел - это не просто точка, а подкластер (который объединяет множество точек с учётом ограничения [math]T[/math]).

1.2.2.3 Операция вставки в CF дерево

[math][/math]

3 Литература

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