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) [math]\displaystyle{ CF }[/math] набора определяется как тройка [math]\displaystyle{ CF = (N,LS,SS) }[/math], где [math]\displaystyle{ \overrightarrow{LS} = \sum_{i=1}^N \overrightarrow{X_i} }[/math] является линейной суммой, а [math]\displaystyle{ \overrightarrow{SS} = \sum_{i=1}^N (\overrightarrow{X_i})^2 }[/math] является суммой квадратов точек данных.
- Признаки кластеризации организуются в CF-дерево, высоко сбалансированное дерево с двумя параметрами: коэффициентом ветвления [math]\displaystyle{ B }[/math] и порогом [math]\displaystyle{ T }[/math]. Каждый нелистовой узел состоит максимум из [math]\displaystyle{ B }[/math] входов вида [math]\displaystyle{ [CF_i,child_i] }[/math], где [math]\displaystyle{ child_i }[/math] является указателем на его [math]\displaystyle{ i }[/math]-ого потомка, а [math]\displaystyle{ CF_i }[/math] является признаком кластеризации, представляющим связанный подкластер. Лист содержит не более [math]\displaystyle{ L }[/math] входов, каждый вида [math]\displaystyle{ [CF_i] }[/math]. Он также имеет два указателя, prev и next, которые используются для соединения в цепь все листы. Размер дерева зависит от параметра T. Требуется, чтобы узел A вмещался на страницу размера P. B и L определяются значением P. Таким образом, P может меняться для настройки производительности . Это очень компактное представление набора данных, поскольку каждый лист не является отдельной точкой данных, а является подкластером.
На втором шаге алгоритм просматривает все листья в начальном CF-дереве, чтобы построить меньшее CF-дерево путём удаления выпадений и группирования переполненных подклассов в бо́льшие подклассы. Этот шаг в исходном представлении BIRCH помечен как необязательный.
На третьем шаге используется существующий алгоритм для кластеризации всех листов. Здесь применяется агломерирующий иерархический алгоритм кластеризации непосредственно к подкластерам, представленным их CF-векторами. Это также обеспечивает гибкость, позволяющую пользователю указать либо желаемое число кластеров, либо желаемый порог диаметра кластеров. После этого шага получаем набор кластеров, которые содержат главные схемы распределения в данных. Однако могут существовать небольшие локальные неточности, которые могут быть обработаны необязательным шагом 4. На шаге 4 центры тяжести кластеров, полученных на шаге 3, используются как зародыши и точки перераспределения точек данных для получения нового набора кластеров. Шаг 4 обеспечивает также возможность отбрасывания выбросов. То есть точка, которая слишком далека от ближайшего зародыша, может считаться выбросом.
Вычисление признаков кластеров
Если дано только [math]\displaystyle{ CF = [N, \overrightarrow{LS}, \overrightarrow{SS}] }[/math], те же измерения могут быть получены без знания истинных значений.
- Центроид: [math]\displaystyle{ \overrightarrow{C} = \frac{\sum_{i=1}^N \overrightarrow{X_i}}{N} = \frac{\overrightarrow{LS}}{N} }[/math]
- Радиус: [math]\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}} }[/math]
- Среднее расстояние между кластерами [math]\displaystyle{ CF_1 = [N_1, \overrightarrow{LS_1}, \overrightarrow{SS_1}] }[/math] и [math]\displaystyle{ CF_2 = [N_2, \overrightarrow{LS_2}, \overrightarrow{SS_2}] }[/math]:[math]\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}} }[/math]
В мультифакторных случаях квадратный корень может быть заменён подходящей нормой.
Примечания
- ↑ 1,0 1,1 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.
Для улучшения этой статьи желательно: |