БЕРЕЗА

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

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

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

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

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

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

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

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

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

This section is missing information about BIRCH equations for Diameter D, Distances D0, D1, D3 and D4. Please expand the section to include this information. Further details may exist on the talk page. (July 2023)

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

• Центроид:${\displaystyle {\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow {LS}}{N}}}$
• Радиус:${\displaystyle 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}}}}$
• Среднее расстояние связи между кластерами и :${\displaystyle CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]}$${\displaystyle CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]}$${\displaystyle 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. При вычитании или подобном в других расстояниях, таких как , может произойти катастрофическое сокращение и привести к плохой точности, и что в некоторых случаях может даже привести к отрицательному результату (и квадратный корень тогда станет неопределенным). ^[2] Это можно решить, используя вместо этого кластерные признаки BETULA, которые хранят количество , среднее значение и сумму квадратов отклонений вместо этого на основе численно более надежных онлайн-алгоритмов для вычисления дисперсии . Для этих признаков справедлива аналогичная теорема аддитивности. При хранении вектора соответственно матрицы для квадратов отклонений результирующее дерево BIRCH CF также можно использовать для ускорения моделирования гауссовой смеси с алгоритмом ожидания-максимизации , помимо кластеризации k-средних и иерархической агломеративной кластеризации .${\displaystyle SS}$${\displaystyle {\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}}$${\displaystyle D_{2}}$${\displaystyle CF=(N,\mu ,S)}$${\displaystyle N}$${\displaystyle \mu }$

Вместо того чтобы хранить линейную сумму и сумму квадратов, мы можем хранить среднее значение и квадрат отклонения от среднего значения в каждом кластерном признаке , ^[4] где${\displaystyle CF'=(N,\mu ,S)}$

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

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

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

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

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

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

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

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

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

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

• В состав ELKI входят БЕРЕЗА и БЕТУЛА.
• scikit-learn содержит ограниченную версию BIRCH, которая поддерживает только расстояние D0, статические пороги и использует только центроиды листьев на этапе кластеризации. ^[6]