BIRCH

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

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

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

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

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

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

Алгоритм

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

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

• Если дан набор N d-мерных точек данных, признак кластеризации (Шаблон:Lang-en) $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$ входов вида $[C{F}_i,chil{d}_i]$, где $chil{d}_i$ является указателем на его $i$-ого потомка, а $C{F}_i$ является признаком кластеризации, представляющим связанный подкластер. Лист содержит не более $L$ входов, каждый вида $[C{F}_i]$. Он также имеет два указателя, prev и next, которые используются для соединения в цепь все листы. Размер дерева зависит от параметра T. Требуется, чтобы узел A вмещался на страницу размера P. B и L определяются значением P. Таким образом, P может меняться для Шаблон:Не переведено 5. Это очень компактное представление набора данных, поскольку каждый лист не является отдельной точкой данных, а является подкластером.

На втором шаге алгоритм просматривает все листья в начальном 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 \stackrel{2}{\overrightarrow{C}}+\overrightarrow{SS}-2\cdot \overrightarrow{C}\cdot \overrightarrow{LS}}{N}}$

• Среднее расстояние между кластерами $C{F}_1=[N_1,\overrightarrow{L{S}_1},\overrightarrow{S{S}_1}]$ и $C{F}_2=[N_2,\overrightarrow{L{S}_2},\overrightarrow{S{S}_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{S{S}_2}+N_2\cdot \overrightarrow{S{S}_1}-2\cdot \overrightarrow{L{S}_1}\cdot \overrightarrow{L{S}_2}}{N_1\cdot N_2}}$

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

Литература

• Шаблон:Книга