Введение

Исследовательский характер анализа данных и интеллектуального анализа данных делает кластеризацию одной из самых обычных задач в подобных проектах. Чаще эти проекты исходят из разных областей применения, таких как биология, анализ текста, анализ сигналов и т. Д., Которые включают все большие и большие наборы данных по количеству примеров и количеству атрибутов. Самая большая проблема с кластеризацией в реальных сценариях - это объем данных и, как следствие, увеличение сложности и потребность в большей вычислительной мощности.
Эти проблемы открыли область для поиска алгоритмов, способных уменьшить эту перегрузку данными. Некоторые решения приходят со стороны предварительной обработки данных путем преобразования данных в многообразие более низкой размерности, которое представляет структуру данных, или путем обобщения набора данных путем получения меньшего подмножества примеров, представляющих эквивалентную информацию. Другая перспектива - изменить классические алгоритмы кластеризации или получить другие, способные кластеризовать более крупные наборы данных. Эта точка зрения опирается на множество различных стратегий. Такие методы, как выборка, оперативная обработка, суммирование, распределение данных и эффективные структуры данных, были применены к проблеме масштабирования алгоритмов кластеризации.
В этой статье мы обсудим один из таких алгоритмов - BIRCH, что означает сбалансированный итерационный Редукция и кластеризация с использованием иерархий, разработанная в 1996 году Тиан Чжан, Рагху Рамакришнаном и Мироном Ливни.

Объяснение

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

Алгоритм кластеризации БЕРЕЗА состоит из двух этапов:

  1. Построение дерева CF: BIRCH объединяет большие наборы данных в более мелкие и плотные области, называемые записями функции кластеризации (CF). Формально запись Clustering Feature определяется как упорядоченная тройка (N, LS, SS), где N - количество точек данных в кластере, LS - линейная сумма точек данных, а SS - квадрат суммы точек данных в кластере. Запись CF может состоять из других записей CF. При желании мы можем сжать это исходное дерево CF в меньший CF.
  2. Глобальная кластеризация: применяет существующий алгоритм кластеризации к листьям дерева CF. Дерево CF - это дерево, в котором каждый листовой узел содержит подкластер. Каждая запись в дереве CF содержит указатель на дочерний узел и запись CF, состоящую из суммы записей CF в дочерних узлах. При желании мы можем уточнить эти кластеры.

Из-за этого двухэтапного процесса BIRCH также называется двухэтапной кластеризацией. Давайте теперь углубимся в эти шаги, чтобы получить целостное понимание.

Особенности кластера

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

★ Счетчик [количество значений данных в кластере.]

★ Линейная сумма [сумма отдельных координат. Это мера местоположения кластера.]

★ Квадратная сумма [Сумма квадратов координат. Это мера распространения кластера.]

Вместе линейная сумма и сумма в квадрате эквивалентны среднему значению и дисперсии точки данных.

CF дерево

Процесс построения Дерева CF можно резюмировать следующим образом:

  1. Для каждой данной записи BIRCH сравнивает расположение этой записи с положением каждого CF в корневом узле, используя либо линейную сумму, либо среднее значение CF. БЕРЕЗА передает входящую запись корневому узлу CF, ближайшему к входящей записи.
  2. Затем запись спускается вниз к нелистовым дочерним узлам корневого узла CF, выбранного на шаге 1. БЕРЕЗА сравнивает расположение записи с расположением каждого нелистового узла CF. BIRCH передает входящую запись на нелистовой узел CF, ближайший к входящей записи.
  3. Затем запись спускается вниз к конечным дочерним узлам нелистового узла CF, выбранного на шаге 2. БЕРЕЗА сравнивает расположение записи с положением каждого листа. BIRCH предварительно передает входящую запись листу, ближайшему к входящей записи.
  4. Выполните одно из (а) или (б):

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

(b) Если радиус выбранного листа, включающего новую запись, действительно превышает порог T, то формируется новый лист, состоящий только из входящей записи. Родительские CF обновляются с учетом новой точки данных.

Если выполняется шаг 4 (b), и в листовом узле уже есть максимум L листьев, то листовой узел разделяется на два листовых узла. CF наиболее удаленных листовых узлов используются в качестве начальных значений листовых узлов, а оставшиеся CF назначаются тому, какой листовой узел находится ближе. Если родительский узел заполнен, разделите родительский узел и так далее. Обратите внимание, что радиус кластера может быть вычислен даже без знания точек данных, если у нас есть счет n, линейная сумма LS и сумма в квадрате SS. Это позволяет BIRCH оценить, принадлежит ли данная точка данных к определенному подкластеру, без необходимости сканировать исходный набор данных.

Кластеризация субкластеров

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

Параметры БЕРЕЗЫ

В этом алгоритме есть три параметра, которые необходимо настроить. В отличие от K-средних, здесь оптимальное количество кластеров (k) не нужно вводить пользователем, поскольку они определяются алгоритмом.

✓ порог: порог - это максимальное количество точек данных, которое может содержать подкластер в листовом узле дерева CF.

✓ branching_factor: этот параметр указывает максимальное количество подкластеров CF в каждом узле (внутреннем узле).

✓ n_clusters: количество кластеров, которые должны быть возвращены после завершения всего алгоритма BIRCH, то есть количество кластеров после последнего шага кластеризации. Если установлено значение None, последний этап кластеризации не выполняется и возвращаются промежуточные кластеры.
Scikit-learn предлагает надежную реализацию для Python.

Вывод

Недостаток кластеризации БЕРЕЗЫ заключается в следующем. Из-за древовидной структуры, присущей дереву CF, решение кластеризации может зависеть от входного порядка записей данных. Чтобы избежать этого, аналитик данных может пожелать применить кластеризацию BIRCH к нескольким различным случайным сортировкам данных и найти консенсус среди результатов. Однако преимущество кластеризации BIRCH состоит в том, что аналитику не требуется выбирать лучший выбор k, количества кластеров, как в случае с некоторыми другими методами кластеризации. Скорее, количество кластеров в решении для кластеризации BIRCH является результатом процесса построения дерева.

Пожалуйста, не стесняйтесь делиться своими предложениями.
Спасибо за чтение! Оставайтесь в безопасности!

Ссылки