BIRCH
Сбалансированное итеративное сокращение и кластеризация с помощью иерархий (BIRCH, англ. balanced iterative reducing and clustering using hierarchies) — это алгоритм интеллектуального анализа данных без учителя, используемый для осуществления иерархической кластеризации на наборах данных большого размера[1]. Преимуществом BIRCH является возможность метода динамически кластеризовать по мере поступления многомерных метрических точек данных в попытке получить кластеризацию лучшего качества для имеющегося набора ресурсов (памяти и временных рамок ). В большинстве случаев алгоритм BIRCH требует одного прохода по базе данных.
Разработчики BIRCH утверждали, что это был «первым алгоритмом кластеризации, предлагающим в базах данных эффективно обрабатывать 'шум' (точки данных, которые не являются частью схемы)»[1] побивший DBSCAN за два месяца. Алгоритм получил в 2006 году приз SIGMOD после 10 лет тестирования[2].
Проблема с предыдущими методами[править | править код]
Предыдущие алгоритмы кластеризации работали менее эффективно на больших базах данных и неадекватно вели себя в случае, когда данные были слишком большие, чтобы поместиться в оперативную память. Как результат имелось много затрат для получения высокого качества кластеризации при минимизации цены дополнительных операций ввода/вывода. Более того, большинство предшественников BIRCH просматривали все точки данных (или всех выделенных кластеров на текущий момент) одинаково для каждого 'решения кластеризации' и не делали эвристического взвешивания на базе расстояний между этими точками данных.
Преимущества BIRCH[править | править код]
Каждое решение кластеризации локально и осуществляется без просмотра всех точек данных и существующих на текущий момент кластеров. Метод работает на наблюдениях, пространство данных которых обычно не однородно заполнено и не каждая точка данных одинаково важна. Метод позволяет использовать всю доступную память для получения наиболее точных возможных подкластеров при минимизации цены ввода/вывода. Метод является инкрементальным и не требует наличия полного набора данных сразу.
Алгоритм[править | править код]
Алгоритм BIRCH берёт в качестве входа набор из N точек данных, представленный как вещественные вектора, и желаемое число кластеров K. Алгоритм разбит на четыре фазы, вторая из которых не обязательна.
Первая фаза строит CF дерево точек данных, высоко сбалансированную древесную структуру, определённую следующим образом:
- Если дан набор N d-мерных точек данных, признак кластеризации (англ. Clustering Feature) набора определяется как тройка , где является линейной суммой, а является суммой квадратов точек данных.
- Признаки кластеризации организуются в CF-дерево, высоко сбалансированное дерево с двумя параметрами: коэффициентом ветвления и порогом . Каждый нелистовой узел состоит максимум из входов вида , где является указателем на его -ого потомка, а является признаком кластеризации, представляющим связанный подкластер. Лист содержит не более входов, каждый вида . Он также имеет два указателя, prev и next, которые используются для соединения в цепь все листы. Размер дерева зависит от параметра T. Требуется, чтобы узел A вмещался на страницу размера P. B и L определяются значением P. Таким образом, P может меняться для настройки производительности . Это очень компактное представление набора данных, поскольку каждый лист не является отдельной точкой данных, а является подкластером.
На втором шаге алгоритм просматривает все листья в начальном CF-дереве, чтобы построить меньшее CF-дерево путём удаления выпадений и группирования переполненных подклассов в бо́льшие подклассы. Этот шаг в исходном представлении BIRCH помечен как необязательный.
На третьем шаге используется существующий алгоритм для кластеризации всех листов. Здесь применяется агломерирующий иерархический алгоритм кластеризации непосредственно к подкластерам, представленным их CF-векторами. Это также обеспечивает гибкость, позволяющую пользователю указать либо желаемое число кластеров, либо желаемый порог диаметра кластеров. После этого шага получаем набор кластеров, которые содержат главные схемы распределения в данных. Однако могут существовать небольшие локальные неточности, которые могут быть обработаны необязательным шагом 4. На шаге 4 центры тяжести кластеров, полученных на шаге 3, используются как зародыши и точки перераспределения точек данных для получения нового набора кластеров. Шаг 4 обеспечивает также возможность отбрасывания выбросов. То есть точка, которая слишком далека от ближайшего зародыша, может считаться выбросом.
Вычисление признаков кластеров[править | править код]
Если дано только , те же измерения могут быть получены без знания истинных значений.
- Центроид:
- Среднее расстояние между кластерами и :
В мультифакторных случаях квадратный корень может быть заменён подходящей нормой.
Примечания[править | править код]
- ↑ 1 2 Zhang, Ramakrishnan, Livny, 1996, с. 103–114.
- ↑ 2006 SIGMOD Test of Time Award . Архивировано из оригинала 23 мая 2010 года.
Литература[править | править код]
- Zhang T., Ramakrishnan R., Livny M. 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. — doi:10.1145/233269.233324.
Для улучшения этой статьи желательно:
|