Сбалансированное итеративное сокращение и кластеризация с помощью иерархий (BIRCH, англ. balanced iterative reducing and clustering using hierarchies) — это алгоритм интеллектуального анализа данных без учителя, используемый для осуществления иерархической кластеризации на наборах данных большого размера[1]. Преимуществом BIRCH является возможность метода динамически кластеризовать по мере поступления многомерных метрических точек данных[en] в попытке получить кластеризацию лучшего качества для имеющегося набора ресурсов (памяти и временных рамок[en]). В большинстве случаев алгоритм BIRCH требует одного прохода по базе данных.
Разработчики BIRCH утверждали, что это был «первым алгоритмом кластеризации, предлагающим в базах данных эффективно обрабатывать 'шум' (точки данных, которые не являются частью схемы)»[1] побивший DBSCAN за два месяца. Алгоритм получил в 2006 году приз SIGMOD[en] после 10 лет тестирования[2].
Предыдущие алгоритмы кластеризации работали менее эффективно на больших базах данных и неадекватно вели себя в случае, когда данные были слишком большие, чтобы поместиться в оперативную память. Как результат имелось много затрат для получения высокого качества кластеризации при минимизации цены дополнительных операций ввода/вывода. Более того, большинство предшественников BIRCH просматривали все точки данных (или всех выделенных кластеров на текущий момент) одинаково для каждого 'решения кластеризации' и не делали эвристического взвешивания на базе расстояний между этими точками данных.
Каждое решение кластеризации локально и осуществляется без просмотра всех точек данных и существующих на текущий момент кластеров. Метод работает на наблюдениях, пространство данных которых обычно не однородно заполнено и не каждая точка данных одинаково важна. Метод позволяет использовать всю доступную память для получения наиболее точных возможных подкластеров при минимизации цены ввода/вывода. Метод является инкрементальным и не требует наличия полного набора данных[en] сразу.
Алгоритм BIRCH берёт в качестве входа набор из N точек данных, представленный как вещественные вектора, и желаемое число кластеров K. Алгоритм разбит на четыре фазы, вторая из которых не обязательна.
Первая фаза строит CF дерево точек данных, высоко сбалансированную древесную структуру, определённую следующим образом:
На втором шаге алгоритм просматривает все листья в начальном CF-дереве, чтобы построить меньшее CF-дерево путём удаления выпадений и группирования переполненных подклассов в бо́льшие подклассы. Этот шаг в исходном представлении BIRCH помечен как необязательный.
На третьем шаге используется существующий алгоритм для кластеризации всех листов. Здесь применяется агломерирующий иерархический алгоритм кластеризации непосредственно к подкластерам, представленным их CF-векторами. Это также обеспечивает гибкость, позволяющую пользователю указать либо желаемое число кластеров, либо желаемый порог диаметра кластеров. После этого шага получаем набор кластеров, которые содержат главные схемы распределения в данных. Однако могут существовать небольшие локальные неточности, которые могут быть обработаны необязательным шагом 4. На шаге 4 центры тяжести кластеров, полученных на шаге 3, используются как зародыши и точки перераспределения точек данных для получения нового набора кластеров. Шаг 4 обеспечивает также возможность отбрасывания выбросов. То есть точка, которая слишком далека от ближайшего зародыша, может считаться выбросом.
Если дано только , те же измерения могут быть получены без знания истинных значений.
В мультифакторных случаях квадратный корень может быть заменён подходящей нормой.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .