BIRCH Clustering: Эффективность и универсальность

Понимание BIRCH: полное руководство по эффективной кластеризации

Сбалансированное итеративное сокращение и кластеризация с использованием иерархий (BIRCH) — это алгоритм, используемый для кластеризации больших наборов данных в машинном обучении и интеллектуальном анализе данных. Ее предложили Тянь Чжан, Тянь Чжан, Рагу Рамакришнан и Мирон Ливни в 1996 году. Вы можете добраться до статьи здесь.

Иерархическая кластеризация

Это тип алгоритма кластеризации для группировки похожих точек данных в кластеры на основе их попарного сходства или различия.

Частичная кластеризация направлена на разделение данных на заранее определенное количество непересекающихся кластеров путем итеративного назначения точек данных кластерам на основе определенных критериев, таких как минимизация (или максимизация) расстояний внутри кластера, требующих, чтобы количество кластеров было предварительно определено.

С другой стороны, иерархическая кластеризация создает иерархию кластеров. Он организует точки данных в иерархическую структуру или древовидное представление, часто называемое дендрограммой.

Иерархическая кластеризация может быть выполнена двумя основными способами:

Агломеративное: оно начинается с каждой точки как отдельного кластера и постепенно объединяет наиболее похожие кластеры на основе выбранной меры сходства. На каждом шаге алгоритм идентифицирует два ближайших кластера и объединяет их в новый кластер. Этот процесс продолжается до тех пор, пока все точки данных не будут объединены в один кластер или пока не будет выполнен критерий остановки. (Подход «снизу вверх)
Разделительный: используется противоположный подход, начиная с одного кластера, представляющего все точки данных, и рекурсивно делящего его на более мелкие кластеры на основе различий. На каждом шаге алгоритм выбирает кластер и разбивает его на два или более подкластера до тех пор, пока не будет достигнут желаемый уровень или степень детализации или критерии остановки. (Нисходящий подход)

Дерево признаков кластеризации (Дерево CF)

CF Tree — это иерархическая структура данных, используемая в алгоритме BIRCH для эффективной кластеризации больших наборов данных. Он компактно и иерархически представляет информацию о кластеризации. Он состоит из набора узлов, где каждый узел представляет либо кластер, либо подкластер.

Дерево CF строится восходящим образом на начальном этапе BIRCH. Вначале каждая точка данных рассматривается как отдельный кластер. По мере добавления дополнительных точек данных алгоритм итеративно объединяет кластеры на основе определенных критериев, таких как близость точек данных и заданные пользователем пороговые значения. Этот процесс слияния продолжается до тех пор, пока не будет сформировано дерево CF.

Каждый узел в Дереве CF содержит важную информацию о соответствующем кластере, такую как количество точек данных в кластере, центроид или репрезентативная точка кластера, а также радиус или диаметр кластера. Эти атрибуты помогают в эффективной идентификации и извлечении кластера в процессе кластеризации.

Он обеспечивает иерархическую структуру, позволяющую эффективно хранить и извлекать информацию о кластеризации. Он обеспечивает быстрый доступ к различным уровням детализации кластеризации и упрощает различные операции, такие как слияние, разделение и уточнение кластеров, которые необходимы BIRCH для достижения масштабируемой кластеризации больших наборов данных с эффективным использованием памяти.

БЕРЕЗА Алгоритм

BIRCH постепенно строит дерево признаков кластеризации (CF) посредством двухэтапного процесса. На первом этапе он последовательно исследует базу данных и строит начальное дерево CF, хранящееся в памяти. На втором этапе BIRCH применяет произвольный алгоритм кластеризации для кластеризации листовых узлов, присутствующих в дереве CF.

Функция кластеризации (CF) в BIRCH представляет собой компактное представление статистики подкластеров, выраженное в виде вектора с тремя компонентами. Эти компоненты собирают важную статистическую информацию о подкластере, в частности, о 0-м, 1-м и 2-м моментах. Суммируя эти измерения, CF эффективно сохраняет важные данные для кластерных вычислений. Он служит сжатым представлением, которое оптимизирует хранение, сохраняя при этом важные статистические данные.

Функция кластеризации (CF) представлена кортежем (N, LS, SS), где N представляет количество точек данных, LS обозначает линейную сумму, полученную путем суммирования координат всех N точек, а SS представляет полученную квадратную сумму. путем суммирования квадратов координат всех N точек.

Допустим, у нас есть 5 точек: (3,4), (2,6), (4,5), (4,7), (3,8). Тогда КФ = (5, (16,30), (54, 190)).

Измерение кластера также включает три элемента: центр тяжести, радиус и диаметр.

Центроид можно рассматривать как центральную точку внутри кластера.

Радиус — это квадратный корень из среднего расстояния от объектов-членов до центроида.

Диаметр кластера рассчитывается как квадратный корень из среднего квадрата расстояния между всеми возможными парами точек внутри кластера.

Дерево CF имеет сходство с деревом B+ и следует процессу инкрементной вставки. При поступлении новых точек начинается поиск ближайшей листовой записи, начиная с корня. Затем точки добавляются к конечной записи, и CF (функция кластеризации) обновляется соответствующим образом. Если диаметр входа превышает максимально допустимый диаметр, выполняется операция разделения листа. Неконечные узлы дерева CF хранят совокупные суммы CF, принадлежащих их соответствующим дочерним элементам.

Дерево CF включает два параметра: коэффициент ветвления (B) и максимальный диаметр (L) подкластеров, хранящихся в листовых узлах. Коэффициент ветвления определяет максимальное количество потомков, которое может иметь узел в древовидной структуре. С другой стороны, максимальный диаметр определяет наибольший размер, который могут иметь подкластеры при хранении в листовых узлах.

Реализация Python

from sklearn.cluster import Birch

Мы можем применить кластеризацию BIRCH, используя класс Birch из scikit-learn. Он принимает некоторые параметры:

n_clusters указывает количество создаваемых кластеров.
threshold — это радиус, в пределах которого объединяются подкластеры. Когда два подкластера имеют расстояния меньше порога, они объединяются в один кластер. Это важный параметр, влияющий на размер и количество образующихся кластеров.
branching_factor определяет максимальное количество подкластеров в нелистовом узле. Более высокое значение может привести к более быстрой сборке и объединению кластеров, но может потреблять часть памяти.
compute_labels, если установлено значение True, алгоритм будет вычислять и назначать кластерные метки образцам. Если установлено значение False, для онлайн-обучения будет доступен только метод partial_fit, и никакие метки не будут присвоены.
copy: если установлено значение True, будет сделана копия входных данных. Рекомендуется установить его на False, если только это не необходимо для экономии памяти.

Простая реализация:

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import Birch

# Generate sample dataset
X, _ = make_blobs(n_samples=100, centers=3, random_state=42)

# Apply BIRCH clustering
birch = Birch(n_clusters=3)
birch.fit(X)

# Plot the clustering results
labels = birch.labels_
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.title('BIRCH Clustering Results')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Преимущества БЕРЕЗЫ

Масштабируемость: он предназначен для эффективной обработки больших наборов данных. Он особенно подходит для сценариев с ограниченными ресурсами памяти или при работе с потоковыми данными.
Гибкость в количестве кластеров: не требуется заранее определять количество кластеров. Его иерархическая природа позволяет исследовать различные уровни детализации, предоставляя диапазон кластеров без необходимости явного указания номера кластера.
Быстрая начальная кластеризация: начальная кластеризация выполняется за один проход по данным, что является эффективным.
Возможность обработки различных типов данных: он может обрабатывать различные типы данных, включая числовые и категориальные данные.
Возможность онлайн-обучения: он поддерживает поэтапное обучение или онлайн-обучение, позволяя включать новые точки данных в процесс кластеризации без повторной обработки всего набора данных.

Головные боли

Чувствительность к входным параметрам: его производительность может зависеть от выбора его параметров, таких как порог или коэффициент ветвления.
Отсутствие обработки шума: он явно не обрабатывает шум или выбросы в данных.
Ограниченная гибкость формы кластера: предполагается, что кластеры имеют приблизительно сферическую форму и одинаковые размеры из-за использования критерия кластеризации на основе расстояния.
Невозможность захвата перекрывающихся кластеров: его иерархическая структура не охватывает перекрывающиеся кластеры.
Интерпретируемость иерархической структуры.