Просмотр кода страницы BIRCH

'''Сбалансированное итеративное сокращение и кластеризация с помощью иерархий''' ('''BIRCH''', {{lang-en|balanced iterative reducing and clustering using hierarchies}}) — это алгоритм [[data mining|интеллектуального анализа данных]] [[Обучение без учителя|без учителя]], используемый для осуществления [[Кластерный анализ|иерархической кластеризации]] на наборах данных большого размера{{sfn|Zhang, Ramakrishnan, Livny|1996|с=103–114}}. Преимуществом BIRCH является возможность метода динамически кластеризовать по мере поступления многомерных метрических {{не переведено 5|Единица наблюдения|точек данных||data point}} в попытке получить кластеризацию лучшего качества для имеющегося набора ресурсов (памяти и {{не переведено 5|Временные ограничения|временных рамок||time constraint}}). В большинстве случаев алгоритм BIRCH требует одного прохода по [[База данных|базе данных]].

Разработчики BIRCH утверждали, что это был «первым алгоритмом кластеризации, предлагающим в базах данных эффективно обрабатывать 'шум' (точки данных, которые не являются частью схемы)»{{sfn|Zhang, Ramakrishnan, Livny|1996|с=103–114}} побивший [[DBSCAN]] за два месяца. Алгоритм получил в 2006 году приз [[SIGMOD]] после 10 лет тестирования<ref>{{cite web
 |url=http://www.sigmod.org/sigmod-awards/citations/2006-sigmod-test-of-time-award-1 
 |title=2006 SIGMOD Test of Time Award 
 |deadurl=yes 
 |archiveurl=https://web.archive.org/web/20100523062258/http://www.sigmod.org/sigmod-awards/citations/2006-sigmod-test-of-time-award-1 
 |archivedate=2010-05-23 
}}</ref>.

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

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

== Алгоритм ==

Алгоритм BIRCH берёт в качестве входа набор из {{mvar|N}} точек данных, представленный как [[Признак (машинное обучение)|вещественные вектора]], и желаемое число кластеров {{mvar|K}}. Алгоритм разбит на четыре фазы, вторая из которых не обязательна.

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

* Если дан набор N d-мерных точек данных, ''признак кластеризации'' ({{lang-en|Clustering Feature}}) <math>CF</math> набора определяется как тройка <math>CF = (N,LS,SS)</math>, где <math>\overrightarrow{LS} = \sum_{i=1}^N \overrightarrow{X_i}</math> является линейной суммой, а <math>\overrightarrow{SS} = \sum_{i=1}^N (\overrightarrow{X_i})^2</math> является суммой квадратов точек данных.
* Признаки кластеризации организуются в ''CF-дерево'', высоко сбалансированное дерево с двумя параметрами: [[Коэффициент ветвления|коэффициентом ветвления]] <math>B</math> и порогом <math>T</math>. Каждый нелистовой узел состоит максимум из <math>B</math> входов вида <math>[CF_i,child_i]</math>, где <math>child_i</math> является указателем на его <math>i</math>-ого [[Дерево (теория графов)|потомка]], а <math>CF_i</math> является признаком кластеризации, представляющим связанный подкластер. [[Дерево (теория графов)|Лист]] содержит не более <math>L</math> входов, каждый вида <math>[CF_i]</math>. Он также имеет два указателя, prev и next, которые используются для соединения в цепь все листы. Размер дерева зависит от параметра T. Требуется, чтобы узел A вмещался на страницу размера P. B и L определяются значением P. Таким образом, P может меняться для {{не переведено 5|Настройка производительности|настройки производительности||performance tuning}}. Это очень компактное представление набора данных, поскольку каждый лист не является отдельной точкой данных, а является подкластером.

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

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

== Вычисление признаков кластеров ==
Если дано только <math>CF = [N, \overrightarrow{LS}, \overrightarrow{SS}]</math>, те же измерения могут быть получены без знания истинных значений.

* Центроид: <math> \overrightarrow{C} = \frac{\sum_{i=1}^N \overrightarrow{X_i}}{N} = \frac{\overrightarrow{LS}}{N} </math>

* [[Радиус]]: <math> 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}} </math>

* Среднее расстояние между кластерами <math> CF_1 = [N_1, \overrightarrow{LS_1}, \overrightarrow{SS_1}] </math> и <math> CF_2 = [N_2, \overrightarrow{LS_2}, \overrightarrow{SS_2}] </math>:<math> 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}} </math>

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

== Примечания ==
{{примечания|2}}

== Литература ==
{{refbegin|colwidth=30em}}
* {{книга
|doi=10.1145/233269.233324
|часть=BIRCH: an efficient data clustering method for very large databases
|заглавие=Proceedings of the 1996 ACM SIGMOD international conference on Management of data  - SIGMOD '96
|год=1996
|автор=Zhang T., Ramakrishnan R., Livny M. 
|ref=Zhang, Ramakrishnan, Livny 
}}
{{refend}}
{{Машинное обучение}}

[[Категория:Алгоритмы кластерного анализа]]
{{rq|checktranslate|style}}