БЕРЕЗА

Эта статья об алгоритме кластеризации. Чтобы узнать о дереве, см . Береза . Чтобы узнать о других значениях, см. Береза ​​(значения) .

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

Его изобретатели утверждают, что BIRCH является «первым алгоритмом кластеризации, предложенным в области баз данных для эффективной обработки «шума» (точек данных, которые не являются частью основного шаблона)». опередив DBSCAN на два месяца. Алгоритм BIRCH получил награду SIGMOD за 10-летнюю проверку временем в 2006 году.

Проблема с предыдущими методами

Предыдущие алгоритмы кластеризации работали менее эффективно в очень больших базах данных и не учитывали должным образом случай, когда набор данных был слишком большим, чтобы поместиться в основной памяти . В результате требовалось много накладных расходов на поддержание высокого качества кластеризации при минимизации стоимости дополнительных операций ввода-вывода (ввода/вывода). Более того, большинство предшественников BIRCH проверяют все точки данных (или все существующие в настоящее время кластеры) одинаково для каждого «решения о кластеризации» и не выполняют эвристическое взвешивание на основе расстояния между этими точками данных.

Преимущества с БЕРЕЗОЙ

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

Алгоритм

Алгоритм BIRCH принимает на вход набор из N точек данных, представленных в виде действительным знаком , и желаемое количество кластеров K. векторов с Он работает в четыре этапа, второй из которых является необязательным.

На первом этапе создается функция кластеризации ( $CF$) дерево из точек данных, структура данных дерева со сбалансированной высотой , определенная следующим образом:

• Учитывая набор N d-мерных точек данных, функция кластеризации $CF$ множества определяется как тройка $CF=(N,{\overrightarrow {LS}},SS)$, где
  • ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ представляет собой линейную сумму.
  • $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ представляет собой квадратную сумму точек данных.
• Функции кластеризации организованы в виде CF-дерева , сбалансированного по высоте дерева с двумя параметрами: фактор разветвления $B$ и порог $T$. Каждый нелистовой узел содержит не более $B$ записи формы $[CF_{i},child_{i}]$, где $child_{i}$ является указателем на его $i$дочерний узел и $CF_{i}$ функция кластеризации, представляющая связанный подкластер. содержит Листовой узел не более $L$ записи каждой формы $[CF_{i}]$ . Он также имеет два указателя prev и next, которые используются для объединения всех конечных узлов. Размер дерева зависит от параметра $T$. Узел должен поместиться на странице размера $P$. $B$ и $L$ определяются $P$. Так $P$ могут быть изменены для настройки производительности . Это очень компактное представление набора данных, поскольку каждая запись в конечном узле представляет собой не отдельную точку данных, а подкластер.

На втором этапе алгоритм сканирует все листовые записи в исходном $CF$ дерево, чтобы восстановить меньшее $CF$ дерево, удаляя при этом выбросы и группируя переполненные подкластеры в более крупные. В исходной версии BIRCH этот шаг помечен как необязательный.

На третьем этапе используется существующий алгоритм кластеризации для кластеризации всех конечных записей. Здесь алгоритм агломеративной иерархической кластеризации применяется непосредственно к субкластерам, представленным их кластерами. $CF$ векторы. Он также обеспечивает гибкость, позволяя пользователю указать либо желаемое количество кластеров, либо желаемый порог диаметра кластеров. После этого шага получается набор кластеров, который фиксирует основные закономерности распределения данных. Однако могут существовать незначительные и локализованные неточности, которые можно устранить на дополнительном этапе 4. На этапе 4 центроиды кластеров, созданных на этапе 3, используются в качестве начальных значений и перераспределяют точки данных по ближайшим начальным значениям для получения нового набора кластеры. Шаг 4 также дает нам возможность отбросить выбросы. Это точка, которая находится слишком далеко от ближайшего начального значения, может рассматриваться как выброс.

Расчеты с учетом особенностей кластеризации

Учитывая только функцию кластеризации $CF=[N,{\overrightarrow {LS}},SS]$, те же показатели могут быть рассчитаны без знания лежащих в их основе фактических значений.

• Центроид: ${\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow {LS}}{N}}$
• Радиус: $R={\sqrt {\frac {\sum _{i=1}^{N}({\overrightarrow {X_{i}}}-{\overrightarrow {C}})^{2}}{N}}}={\sqrt {\frac {N\cdot {\overrightarrow {C}}^{2}+SS-2\cdot {\overrightarrow {C}}\cdot {\overrightarrow {LS}}}{N}}}={\sqrt {{\frac {SS}{N}}-({\frac {\overrightarrow {LS}}{N}})^{2}}}$
• Среднее расстояние связи между кластерами $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ и $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$: $D_{2}={\sqrt {\frac {\sum _{i=1}^{N_{1}}\sum _{j=1}^{N_{2}}({\overrightarrow {X_{i}}}-{\overrightarrow {Y_{j}}})^{2}}{N_{1}\cdot N_{2}}}}={\sqrt {\frac {N_{1}\cdot SS_{2}+N_{2}\cdot SS_{1}-2\cdot {\overrightarrow {LS_{1}}}\cdot {\overrightarrow {LS_{2}}}}{N_{1}\cdot N_{2}}}}$

В многомерных случаях квадратный корень следует заменить подходящей нормой.

BIRCH использует расстояния от DO до D3, чтобы найти ближайший лист, затем радиус R или диаметр D, чтобы решить, следует ли поглощать данные существующим листом или добавлять новый лист.

Численные проблемы в функциях кластеризации BIRCH

К сожалению, существуют числовые проблемы, связанные с использованием этого термина. $SS$ в БЕРЕЗЕ. При вычитании ${\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}$ или подобное на других расстояниях, таких как $D_{2}$, может произойти катастрофическая отмена , которая приведет к плохой точности, а в некоторых случаях может даже привести к тому, что результат будет отрицательным (и тогда квадратный корень станет неопределенным). Эту проблему можно решить, используя функции кластера BETULA. $CF=(N,\mu ,S)$ вместо этого они хранят счетчик $N$, иметь в виду $\mu$, а сумма квадратов отклонений вместо этого основана на численно более надежных онлайн-алгоритмах для расчета дисперсии . Для этих особенностей справедлива аналогичная теорема аддитивности. При сохранении вектора или матрицы квадратов отклонений полученное CF-дерево BIRCH также можно использовать для ускорения моделирования гауссовой смеси с помощью алгоритма максимизации ожидания , помимо кластеризации k-средних и иерархической агломеративной кластеризации .

Вместо хранения линейной суммы и суммы квадратов мы можем хранить среднее значение и квадратичное отклонение от среднего значения в каждом кластерном признаке. $CF'=(N,\mu ,S)$, где

• $n$ вес узла (количество точек)
• $\mu$ - вектор центра узла (среднее арифметическое, центроид)
• $S$ представляет собой сумму квадратов отклонений от среднего значения (либо вектор, либо сумма для экономии памяти, в зависимости от приложения)

Основное отличие здесь в том, что S вычисляется относительно центра, а не относительно начала координат.

Одна точка $x$ может быть преобразован в функцию кластера $CF_{x}=(1,x,0)$. Чтобы объединить две функции кластера $CF_{AB}=CF_{A}+CF_{B}$, мы используем

• $N_{AB}=N_{A}+N_{B}$
• $\mu _{AB}=\mu _{A}+{\frac {N_{B}}{N_{AB}}}(\mu _{B}-\mu _{A})$ (дополнительное обновление среднего значения)
• $S_{AB}=S_{A}+S_{B}+N_{B}(\mu _{B}-\mu _{A})\circ (\mu _{B}-\mu _{AB})$ в векторной форме с использованием поэлементного произведения соответственно
• $S_{AB}=S_{A}+S_{B}+N_{B}(\mu _{B}-\mu _{A})^{T}(\mu _{B}-\mu _{AB})$ обновить скалярную сумму квадратов отклонений

В этих вычислениях используются более надежные численные вычисления (см. онлайн-вычисление дисперсии ), которые позволяют избежать вычитания двух одинаковых квадратов значений. Центроид — это просто вектор центра узла. $\mu$и может быть непосредственно использован для расчета расстояний с использованием, например, евклидовых или манхэттенских расстояний. Радиус упрощается до $R={\sqrt {{\frac {1}{N}}S}}$ и диаметр до $D={\sqrt {{\frac {2}{N-1}}S}}$.

Теперь мы можем вычислить различные расстояния от D0 до D4, используемые в алгоритме BIRCH, как:

• Евклидово расстояние $D_{0}=\|\mu _{A}-\mu _{B}\|$ и расстояние до Манхэттена $D_{1}=\|\mu _{A}-\mu _{B}\|_{1}$ вычисляются с использованием центров CF $\mu$
• Межкластерное расстояние $D_{2}={\sqrt {{\frac {1}{N_{A}}}S_{A}+{\frac {1}{N_{B}}}S_{B}+{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}}}$
• Внутрикластерное расстояние $D_{3}={\sqrt {{\frac {2}{N_{AB}(N_{AB}-1)}}\left(N_{AB}(S_{A}+S_{B})+N_{A}N_{B}{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}\right)}}$
• Расстояние увеличения дисперсии $D_{4}={\sqrt {{\frac {N_{A}N_{B}}{N_{AB}}}{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}}}$

Эти расстояния также можно использовать для инициализации матрицы расстояний для иерархической кластеризации, в зависимости от выбранной связи. Для точной иерархической кластеризации и кластеризации k-средних нам также необходимо использовать вес узла. $N$.

Шаг кластеризации

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

1. k-означает кластеризацию , где листья взвешиваются по количеству точек, N.
2. k-means++ путем выборки признаков кластера, пропорциональных $S+N\min _{i}||\mu -c_{i}||$ где $c_{i}$ — ранее выбранные центры, и $(N,\mu ,S)$ — это функция кластера BETULA.
3. Моделирование гауссовой смесью , где также может быть принята во внимание дисперсия S, а если листья хранят ковариации, то и ковариации.
4. Иерархическая агломеративная кластеризация , где связь может быть инициализирована с использованием следующей эквивалентности связей расстояниям BIRCH:

Соответствие между связями HAC и расстояниями BIRCH

Связь HAC	БЕРЕЗОВАЯ дистанция
УПГМА	Д2²
ВПГМА	D0²
Сторожить	2 Д4²

Доступность

• ЭЛКИ содержит БЕРЕЗУ и БЕТУЛУ.
• scikit-learn содержит ограниченную версию BIRCH, которая поддерживает только расстояние D0, статические пороги и использует только центроиды листьев на этапе кластеризации.