BIRCH

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) — алгоритм, предложенный Т. Чжаном, Р. Рамакришнаном и М. Ливни для кластеризации очень больших наборов данных. **Основная идея:** BIRCH не хранит все объекты как самостоятельные элементы. Он строит CF-дерево — компактную иерархическую структуру, где каждый узел хранит статистики подкластеров. **Clustering Feature:** Для подмножества объектов используется тройка: $CF = (N, LS, SS)$, где $N$ — число объектов, $LS = \sum x_i$ — линейная сумма объектов, $SS = \sum x_i^2$ — сумма квадратов. По этим значениям можно быстро вычислять центр, радиус и диаметр подкластеров без обращения ко всем исходным точкам. **Параметры:** 1. **threshold** ограничивает радиус или диаметр подкластеров; 2. **branching factor** ограничивает число потомков в узле CF-дерева. **Преимущества:** Алгоритм хорошо подходит для предварительного сжатия больших данных и может работать почти в потоковом режиме. **Ограничения:** Качество зависит от порядка поступления объектов и выбора threshold. Метод лучше работает с компактными кластерами, но может хуже описывать сложные невыпуклые формы.