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

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

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

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

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

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

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

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

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

1.6 Последовательная сложность алгоритма

Для начала проанализируем вычислительную сложность фазы 1. Максимальный размер дерева [math]\frac{M}{P}[/math]. Для того чтобы вставить элемент, мы должны пройти путь от корня до листа (это около [math]1+log_B\frac{M}{P}[/math] узлов). В каждом узле в поисках "ближайшего" нам необходимо просмотреть B элементов; сложность для каждого элемента пропорциональна размерности d.

Поэтому сложность вставки всех входных точек [math]O(d*N*B(1+log_B\frac{M}{P}))[/math].

В случае, когда необходимо перестроить дерево, предположим, что ES - это размер CF элемента. Существует максимум [math]\frac{M}{ES}[/math] листьевых элементов для вставки, поэтому сложность повторной вставки листьевых элементов [math]O(d*\frac{M}{ES}*B(1+log_B\frac{M}{P}))[/math].

Количество итераций перестройки дерева зависит от пороговой величины. На самом деле, это около [math]log_2\frac{N}{N_0}[/math] (двоичное основание появилось из-за того, что мы не можем провести оценку более чем в 2 раза отличающуюся от текущего размера). [math]N_0[/math] - это число входных точек, загруженных в память с пороговым ограничением [math]T_0[/math].

Соответственно, итоговая сложность фазы 1 [math]O(d*N*B(1+log_B\frac{M}{P})+log_2\frac{N}{N_0}*d*\frac{M}{ES}*B(1+log_B\frac{M}{P}))[/math].

Анализ фазы 2 проводится аналогично.

Что касается операций ввода-вывода, то в фазе 1 данные сканируются один раз, а в фазе 2 не сканируются вовсе. Некоторое количество вычислений связано с удалением точек из областей с низкой плотностью. Если количество доступной для этой операции памяти не больше M и проведено порядка [math]log_2{N}{N_0}[/math] перестроек дерева, то сложность ввода-вывода для фазы 1 не отличается существенно от сложности чтения из файла. Основываясь рассуждениях выше, сложность фаз 1 и 2 будет линейно увеличиваться с ростом N.

В фазе 3 нет операций ввода-вывода. Сложность фазы 3 ограничена константой, которая зависит от максимального размера входных данных и варианта выбранного алгоритма для кластеризации.

Фаза 4 снова сканирует данные и зписывает каждую точку в подходящий кластер; время работы пропорционально [math]N*K[/math].

[math][/math]

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

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

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

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

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

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

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

3 Литература

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