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

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

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

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

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

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

Если имеется очень большой набор данных, то в пространстве он распределен, как правило, неравномерно. Кластерный анализ определяет места наибольшего и наименьшего скоплений, чтобы таким образом понять всю картину целиком. Кроме того, полученные кластеры визуализируются гораздо нагляднее, чем начальные "сырые" данные. Задачей алгоритмов кластеризации является не только простое разбиение данных на кластеры, но и работа в рамках ограниченного объёма доступной памяти (как правило, её объём гораздо меньше, чем размер исходного набора данных) и минимизация времени, требуемого на операции ввода-вывода.

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

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

1.2.1 Теоретическая основа

Пусть в кластере имеются [math]N[/math] точек размерности [math]d[/math]: [math]\{\vec{X_i}\}, 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] - это среднее расстояние между парами в кластере. Данные величины являются альтернативными метриками плотности кластера относительно центроида.

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

пусть даны центроиды двух кластеров [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]N_2[/math] точек размерности [math]d[/math]: [math]\{\vec{X_i}\}[/math], где [math]i= 1,2, ...,N_1[/math] и [math]\{\vec{X_j}\}[/math], где [math]j= N_1+1,N_1+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]\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]. В процессе вставки новых данных CF дерево строится динамически. Оно использует вставку данных для кластеризации точно также как [math]B+[/math] дерево использует её для поиска. CF дерево очень компактно, поскольку каждый листьевой узел - это не просто точка, а подкластер (который объединяет множество точек с учётом ограничения [math]T[/math]).

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

Опишем алгоритм вставки элемнта [math]Ent[/math] в CF дерево:

1) Определение подходящего листа: Начиная с корня, алгоритм рекурсивно спускается по CF дереву, выбирая ближайший дочерний узел в соответствии с выбранной метрикой [math]D0[/math], [math]D1[/math], [math]D2[/math], [math]D3[/math] или [math]D4[/math].

2) Преобразование листа: Когда алгоритм доходит до листа, он находит ближайшую листьевой элемент, скажем, [math]L_1[/math], а затем проверяет, можно ли добавить Ent к [math]L_1[/math] без нарушения порогового условия. Если да, то с учётом этого изменяется CF вектор для [math]L_1[/math]; если нет, то Ent становится новым элементом листа. Если в листе для этого достаточно места, то шаг окончен, иначе он должен "расщепиться". Расщепление узла производится при помощи выбора за основу наиболее удалённой друг от друга пары элементов и перераспределение оставшихся элементов в соответствии с выбранным критерием близости.

3) Преобразование пути к листу: После вставки Ent в лист мы должны обновить информацию о CF для каждого нелистьевого элемента на пути к листу. При отсутствии расщепления это означает простое сложение CF векторов для отражения факта добавления Ent. Расщепление листа же требует вставки нового нелистьевого элемента в родительский узел для задания только что созданного листа. Если у родителя есть место для этого элемента, то необходимо просто преобразовать CF векторы на всех более высоких уровнях. В общем случае, однако, нам также придётся расщепить родительский узел, и так далее до корня. Если расщеплён корень, то высота дерева увеличивается на единицу.

4) Улучшение слияния: Расщепление вызвано ограничением на размер узла, который не зависит от кластеризационных свойств данных. Если во входящем потоке присутствуют "искажённые" (из областей с низкой плотностью) данные, это может повлиять на качество кластеризации, а также уменьшить эффективность использования памяти. Дополнительный шаг алгоритма помогает решить эти проблемы: предположим, что произошло расщепление листа, и распространение этого процесса остановилось на некотором нелистьевом узле [math]N_j[/math], то есть [math]N_j[/math] может вместить дополнительный элемент, полученный после расщепления. Теперь мы сканируем узел [math]N_j[/math] для нахождения двух наиболее близких элементов. Если это не пара, отвечающая расщеплению, мы пытаемся объединить их и поставить в соответствие два дочерних узла. Если количество элементов в дочерних узлах больше B, мы снова расщепляем результат объединения. В процессе повторного расщепления, в случае, если один источник собирает достаточно элементов для того, чтобы полностью заполнить узел, оставшиеся элементы передаются другом источнику. В итоге, если объединённые элементы помещаются в одном узле, в нём освобождается место для ещё одного элемента. Тем самым увеличивается степень использования свободного пространства и откладывается дальнейшее расщепление. В ином случае мы улучшаем распределение элементов в двух ближайших подкластерах.

1.3 Вычислительное ядро алгоритма

Вычислительное ядро алгоритма заключается в многократном выполнении операции вставки нового элемента в дерево, в процессе чего требуется вычисление следующих величин:

• радиуса [math]R[/math] или диаметра [math]D[/math] кластерного элемента. Выполняется при попытке вставить новый элемент в один из подкластеров листьевого узла дерева.

• расстояния между двумя элементами. Выполняется при поиске ближайшего по отношению к новому элементу подкластера в узле дерева по одной из рассмотренных в разд. 1.2.1 метрик [math]D_0[/math], [math]D_1[/math], [math]D_2[/math], [math]D_3[/math] или [math]D_4[/math].

Зная характеристики кластерных элементов [math]N[/math], [math]\vec{LS}[/math] и [math]S[/math], в результате алгебраических преобразований можно получить следующие упрощенные формулы вычисления необходимых значений:

[math]\vec{X_0} = \frac{\vec{LS}}{N}[/math]

[math]R = (\frac{SS - 2\vec{X_0}\vec{LS} + N(\vec{X_0})^2}{N})^{1/2}[/math]

[math]D = (\frac{2(N*SS - (\vec{LS})^2)}{N(N-1)})^{1/2}[/math]

[math]D_2 = (\frac{N_1*SS_2 + N_2*SS_1 - 2\vec{LS_1}\vec{LS_2}}{N_1*N_2})^{1/2}[/math]

[math]D_3 = (\frac{2((N_1+N_2)(SS_1+SS_2)-(\vec{LS_1}+\vec{LS_2})^2)}{(N_1+N_2)(N_1+N_2-1)})^{1/2}[/math]

Рисунок 1 представляет обзор алгоритма BIRCH. Главной задачей фазы 1 является сканирование всех данных и построение в памяти исходного CF дерева, используя заданное количество памяти. Это дерево старается отразить информацию о кластеризации данных настолько хорошо, насколько это позволяют ограничения по памяти. Тогда как плотно распределённые данные хорошо группируются в подкластеры, более разрозненные данные удаляются. После Фазы 1 вспомогательные вычисления в дальнейших фазах будут:

1) быстрее, потому что (а) больше не нужны операции ввода-вывода, (b) проблема кластеризации начальных данных упрощается до проблемы кластеризации подкластеров в листьевых записях;

2) точнее, потому что (а) большинство данных с низкой плотностью удалены, (b) оставшиеся данные распределены оптимально в соответствии с доступным количеством памяти

3) менее чувствительны к порядку, потому что листьевые записи исходного дерева

1.3.1 Фаза 1

Рисунок 2 детализирует Фазу 1. Она начинается с определения порогового значения, сканирования данных и добавления данных в дерево. Если память заканчивается до окончания сканирования данных, увеличивается пороговое значение и строится новое, меньшее CF дерево при помощи повторной вставки листьевых записей в старое дерево. После того как старые листьевые записи добавлены повторно, сканирование данных (и вставка в новое дерево) продолжается с той точки, где процесс был приостановлен.

1.3.2 Уменьшаемость

Пусть [math]t_i[/math] - это CF дерево с пороговым значением [math]T_i[/math]. Его высота равна [math]h[/math], а размер (количество узлов) равен [math]S_i[/math]. Задавая [math]T_{i+1}\geq T_i[/math], мы хотим использовать все листьевые записи [math]t_i[/math] для построения нового CF дерева [math]t_{i+1}[/math] с пороговым значением [math]T_{i+1}[/math] так, чтобы размер [math]t_{i+1}[/math] был не больше чем [math]S_i[/math]. Далее описан алгоритм повторного построения, а также последовательность теорем уменьшаемости.

Предположим, что внутри каждого CF дерева [math]t_i[/math] все соседние записи пронумерованы от [math]0[/math] до [math]n_k-1[/math], где [math]n_k[/math] - это число записей в данном узле. Тогда путь из корневой записи (уровень 1) до листьевого узла (уровень h) уникально представляется вектором [math](i_1, i_2, ..., i_{h-1})[/math], где [math]i_j, j=1,...,h-1[/math] - это номера записей j-го уровня. Поэтому естественно принять, что путь [math]({i_1}^(1), {i_2}^(1), ..., {i_{h-1}}^(1))[/math] меньше пути [math]({i_1}^(2), {i_2}^(2), ..., {i_{h-1}}^(2))[/math], если [math]{i_1}^{(1)}={i_1}^{(2)}, ..., {i_{j-1}}^{(1)}={i_{j-1}}^{(2)}[/math] и [math]{i_j}^{(1)}\lt {i_j}^{(2)}[/math] [math](0 \leq j \leq h-1) [/math]. Очевидно, что между понятиями листа и пути существует точное соответствие, поэтому в дальнейшем мы будет использовать эти понятия взаимозаменяемо.

Алгоритм показан на рмсунке 3. Имея определение пути, указанное выше, он сканирует и освобождает старое дерево путь за путём и в то же время путь за путём создаёт новое дерево. Новое дерево начинается с NULL, а "OldCurrentPath" начинается с крайнего левого пути старого дерева. Для "OldCurrentPath" алгоритм работает следующим образом:

1) Создание соответствующей "NewCurrentPath" в новом дереве: узлы добавляются в новое дерево точно так же как и в старое, так что новое дерево никак не может стать больше старого

2) Вставка листьевых записей "OldCurrentPath" в новое дерево: каждый лист в "OldCurrentPath" проверяется заново в соответствием с новым пороговым значением (???? АААА НАДОЕЛО)

3) Освобождение места в "OldCurrentPath" и "NewCurrentPath": после обработки всех листьев в "OldCurrentPath", неиспользуемые узлы могут быть освобождены. Также может оказаться, что некоторые узлы "NewCurrentPath" пусты из-за того, что листьевые записи, которые изначально соответствовали этому пути, теперь "продвинуты вперёд" (???). В этом случае пустые узлы также необходимо удалить.

4) "OldCurrentPath" устанавливается на следующий путь старого дерева (если такой существует), и шаги выше повторяются.

Теорема (уменьшаемости): Пусть по указанному выше алгоритму CF дерево [math]t_{i+1}[/math] с пороговым значением [math]T_{i+1}[/math] построено из CF дерева [math]t_i[/math] с пороговым значением [math]T_i[/math] и пусть [math]S_i[/math] и [math]S_{i+1}[/math] - их соответствующие размеры. Если [math]T_{i+1} \geq T_i[/math], то [math]S_{i+1} \leq S_i[/math] и преобразованию [math]t_i[/math] в [math]t_{i+1}[/math] необходимы как минимум h дополнительных страниц памяти, где h - это высота [math]t_i[/math].

1.3.3 Пороговые значения

Правильный выбор порогового значения может значительно уменьшить количество перепостроений дерева. Так как начальное пороговое значение [math]T_0[/math] увеличивается динамически, мы можем установить его значение слишком маленьким. Но если начальное значение [math]T_0[/math] слишком большое, мы получим менее детализированное CF дерево, чем это возможно при доступной памяти. BIRCH по умолчанию устанавливает значение, равное 0. Пользователь может его менять.

Пусть значение [math]T_i[/math] оказалось слишком маленьким, и мы вышли за пределы памяти после сканирования [math]N_i[/math] точек и формирования [math]C_i[/math] листьевых записей (каждая из которых удовлетворяет пороговому значению [math]T_i[/math]). Основываясь на части данных, которые мы просканировали и той части дерева, которое мы уже построили, необходимо оценить следующее пороговое значение [math]T_{i+1}[/math]. Эта оценка является сложной проблемой, а её решение выходит за пределы данной статьи.

В настоящее время используется следующий подход:

1) Мы пытаемся выбрать [math]T_{i+1}[/math] так, чтобы [math]N_{i+1}=Min(2N_i,N)[/math]. (????)

2) Интуитивно мы хотим увеличить пороговое значение, основываясь на некоторой мере объёма. Существует два различных обозначений объём, которые мы используем, оценивая пороговую величину. Первое - средний объём, который определяется как [math]V_\alpha=r^d[/math], где r - это средний радиус корневого кластера в CF дереве, а d - размерность пространства. Интуитивно понятно, что это мера места, занятого данными, проссканироанными до этого момента. Следующее обозначение - упакованный объём, который определяется как [math]V_p = C_i*{T_i}^d[/math], где [math]C_i[/math] - это количество листьевых записей, а [math]{T_i}^d[/math] - максимальный объём листьевой записи. Интуитивно понятно, что это текущий объём, занятый листьевыми кластерами. Так как [math]C_i[/math] остаётся прежней, даже если мы выходим за пределы памяти (так как мы работаем с фиксированным объёмом памяти), то мы можем приблизить [math]V_p[/math] при помощи [math]{T_i}^d[/math].

Мы делаем предположение, что [math]r[/math] растёт с числом точек [math]N_i[/math]. Зная [math]r[/math] и [math]N_i[/math], мы можем оценить [math]r_{i+1}[/math], используя метод наименьших квадратов (что за линейная регрессия??).

Определим коэффициент расширения [math]f = Max(1.0, \frac{r_{i+1}}{r_i}[/math], и используем это как эвристическую меру

[math][/math]

1.4 Макроструктура алгоритма

Реализация алгоритма BIRCH состояит из следующих четырёх фаз:

1) Фаза 1. Главной задачей фазы 1 является сканирование всех данных и построение в памяти исходного CF дерева, используя заданное количество памяти. Это дерево стремится отразить информацию о кластеризации данных настолько хорошо, насколько это позволяют ограничения по памяти. При этом плотно распределённые данные группируются в подкластеры, а более разрозненные данные удаляются. После завершения фазы 1 вспомогательные вычисления в дальнейших фазах будут:

  1) быстрее, потому что (а) больше не нужны операции ввода-вывода, (b) проблема кластеризации начальных данных упрощается до проблемы кластеризации подкластеров в листьях;

  2) точнее, потому что (а) большинство данных с низкой плотностью удалены, (b) оставшиеся данные распределены оптимально (в соответствии с доступным количеством памяти);

2) Фаза 2. Данная фаза является опциональной. Подмечено, что существующие методы глобальной кластеризации, используемые в рамках фазы 3, имеют различные диапазоны входных значений, при которых они работают эффективно (в терминах скорости и качества). Поэтому потенциально существует пробел между размером фазы 1 и входными значениями фазы 3. И фаза 2 как раз является недостающим связующим звеном: так же как и фаза 1, она сканирует листьевые элементы начального CF дерева для того, чтобы построить меньшее дерево, удаляя ещё больше элементов с низкой плотностью и группируя переполненные подкластеры в большие класетры.

3) Фаза 3. В данной фазе для листьевых элементов используются алгоритмы глобальной кластеризации. Существующие алгоритмы кластеризации наборов точек могут также работать с наборами подкластеров, каждый из которых представлен своим CF вектором. Например, зная CF вектор, мы можем просто посчитать центроид (заменяя всю информацию о кластере этим значением) и рассматривать каждый подкластер как отдельную точку. (при этом существующий алгоритм используется без модификации). Либо если быть более точными, мы можем рассматривать каждый подкластер из n точек как его центроид, повторённый n раз (и с учётом этого модифицировать соответствующий алгоритм). Либо чтобы быть совсем точными, мы можем применить существующий алгоритм непосредственно с подкластерам, потому что информации об их CF векторах, как правило, достаточно для вычисления большинства местрик.

После фазы 3 мы получаем набор кластеров, который отражает основные характеристики распределяемых данных. Однако, всё ещё могут оставаться некоторые неточности, для устранения которых существует фаза 4.

4) Фаза 4. Данная фаза является опциональной и влечёт за собой затраты на дополнительное сканирование данных для корректировки неточностей и дальнейшего улучшения кластеризации. Фаза 4 использует центроиды кластеров, полученные в фазе 3 для как основы и перераспределяет точки входных данных в ближайшие для них основы для получения нового списка кластеров. Фаза 4, если это необходимо пользователю, может быть расширена дополнительными проходами для уверенности в том, что результат приближается к оптимальному. (также во время этих проходов можно пометить каждую точку в кластере).

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

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

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

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

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

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

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

3 Литература

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