BIRCH

Сбалансированное итеративное сокращение и кластеризация с помощью иерархий (BIRCH, англ. balanced iterative reducing and clustering using hierarchies) — это алгоритм интеллектуального анализа данных без учителя, используемый для осуществления иерархической кластеризации на наборах данных большого размера. Преимуществом BIRCH является возможность метода динамически кластеризовать по мере поступления многомерных метрических точек данных в попытке получить кластеризацию лучшего качества для имеющегося набора ресурсов (памяти и временных рамок). В большинстве случаев алгоритм BIRCH требует одного прохода по базе данных.

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

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

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

Преимущества BIRCH

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

Алгоритм

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

Первая фаза строит CF дерево точек данных, высоко сбалансированную древесную структуру, определённую следующим образом:

• Если дан набор N d-мерных точек данных, признак кластеризации (англ. Clustering Feature) $CF$ набора определяется как тройка $CF=(N,LS,SS)$, где ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ является линейной суммой, а ${\overrightarrow {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. Требуется, чтобы узел A вмещался на страницу размера P. B и L определяются значением P. Таким образом, P может меняться для настройки производительности. Это очень компактное представление набора данных, поскольку каждый лист не является отдельной точкой данных, а является подкластером.

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

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

Вычисление признаков кластеров

Если дано только $CF=[N,{\overrightarrow {LS}},{\overrightarrow {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}+{\overrightarrow {SS}}-2\cdot {\overrightarrow {C}}\cdot {\overrightarrow {LS}}}{N}}}$

• Среднее расстояние между кластерами $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},{\overrightarrow {SS_{1}}}]$ и $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},{\overrightarrow {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 {\overrightarrow {SS_{2}}}+N_{2}\cdot {\overrightarrow {SS_{1}}}-2\cdot {\overrightarrow {LS_{1}}}\cdot {\overrightarrow {LS_{2}}}}{N_{1}\cdot N_{2}}}}$

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