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

Алгоритмы кластеризации, такие как кластеризация K-средних, неэффективны, а обработка больших наборов данных с ограниченным объемом ресурсов, таких как память или более медленный ЦП, проблематична. По мере роста объема набора данных стандартные алгоритмы кластеризации плохо масштабируются с точки зрения времени выполнения и качества. Здесь в игру вступает кластеризация BIRCH.

Проблема кластеризации данных — это тип задачи интеллектуального анализа данных. Пространство данных редко заполняется равномерно, когда присутствует значительное количество многомерных точек данных. Кластеризация данных определяет разреженные и переполненные области набора данных, раскрывая общие закономерности распределения коллекции. Проблема кластеризации утверждает, что для заданного числа кластеров K и набора данных из N точек и функции измерения на основе расстояния цель состоит в том, чтобы обнаружить раздел набора данных, который минимизирует значение функции измерения.

В BIRCH однократное сканирование набора данных дает хорошую кластеризацию, а его стоимость прямо пропорциональна размеру набора данных. Сравнивая временную и пространственную сложность BIRCH и качество кластеризации, становится очевидным, что BIRCH — лучший доступный метод кластеризации для очень больших баз данных. BIRCH помогает преодолеть две трудности методов агломеративной кластеризации: 1. масштабируемость и 2. невозможность отменить то, что было сделано на предыдущем шаге.

В BIRCH мы начинаем с определения центроида, радиуса и диаметра кластера, используя следующие уравнения:

R — среднее расстояние от точек-членов до центроида, а D — среднее попарное расстояние внутри кластера, и оба они отражают плотность кластера вокруг центроида.

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

Функция кластеризации

BIRCH имеет две основные концепции: функция кластеризации и дерево функций кластеризации. Эти концепции используются для обобщения кластера и отображения иерархии кластеров. Функция кластеризации (CF) представляет собой трехмерный вектор, содержащий информацию о кластере. CF кластера определяется как:

Согласно теореме об аддитивности CF, если у нас есть два непересекающихся кластера, векторы CF которых равны CF1 = (N1, LS1, SS1) и CF2 = (N2, LS2, SS2), то вектор CF для кластера, образованного после слияния двух кластеров, будет быть:

CF-дерево

CF-дерево — это сбалансированное по высоте дерево, в котором хранятся функции кластеризации для иерархической кластеризации. Каждый листовой узел в дереве функций кластеризации соответствует кластеру. После создания этого компактного представления набора данных выполняется выбор признаков. Он имеет два параметра: коэффициент ветвления B и порог T. Коэффициент ветвления определяет, сколько дочерних элементов может иметь каждый нелистовой узел, а максимальный диаметр подкластеров, хранящихся в конечных узлах дерева, определяется пороговым параметром. Эти два параметра влияют на размер результирующего дерева. Листовой узел представляет собой кластер, состоящий из всех подкластеров, представленных его записями. Но все записи в листовом узле должны удовлетворять пороговому требованию, что означает, что диаметр и радиус должны быть меньше T. Следовательно, размер дерева является функцией T и обратно пропорционален размеру дерева. Есть еще один параметр, называемый Размер страницы P, каждый из узлов должен соответствовать странице размера P. Для набора данных в определенном измерении, в котором известен размер конечных и неконечных узлов, тогда B и L определяются P. Таким образом, мы можем сказать, что P можно варьировать для настройки производительности.

Вставка в дерево CF

Алгоритм кластеризации BIRCH

Ссылка

· BIRCH: эффективный метод кластеризации данных для очень больших баз данных, Тим Чжан, Рагху Рамакришнан, Мирон Ливни, кафедра компьютерных наук Висконсинского университета в Мэдисоне