BIRCH

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

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

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

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

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

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

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

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

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

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

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

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