Введение:

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

Регулировка невозможна при традиционной иерархической кластеризации. После принятия решения о слиянии или разделении оно не отменяет того, что уже было сделано, и не выполняет перестановку объектов между кластерами. В результате, если в какой-то момент будет принято неправильное решение о слиянии или разделении, это может привести к низкокачественным кластерам. Большинство существующих алгоритмов иерархической кластеризации не учитывают случай, когда набор данных может быть слишком большим, чтобы поместиться в основную память. и они не концентрируются на минимизации количества сканирований набора данных.

Интеграция иерархической кластеризации с другими методами многофазной кластеризации является одним из способов повышения качества кластеризации иерархических алгоритмов. BIRCH — один из таких алгоритмов, разработанный Тянь Чжаном, Рагху Рамакришнаном и Мироном Ливни. BIRCH расшифровывается как Balanced Iterative Reduction and Clustering using Hierarchies.

Пояснение:

BIRCH (Balanced iterative Reduction and Clustering Hierarchies) — это неконтролируемый алгоритм интеллектуального анализа данных, который кластеризует большие объемы числовых данных с использованием агломеративного подхода. Агломеративная иерархическая кластеризация — это восходящий метод кластеризации, при котором кластеры делятся на подкластеры, которые далее делятся на подкластеры. Однако BIRCH преодолевает проблему масштабируемости предыдущей кластеризации, он может обрабатывать только метрические атрибуты (любой атрибут, значения которого могут быть представлены в евклидовом пространстве, называется метрическим атрибутом). Это один из недостатков алгоритма BIRCH.

Алгоритм кластеризации BIRCH вводит две концепции. Функция кластеризации и Дерево функций кластеризации (дерево CF). Дерево CF — это сбалансированное по высоте дерево, в котором хранятся функции кластеризации для иерархической кластеризации.

Признак кластеризации (CF) представляет собой трехмерный вектор, обобщающий информацию о кластерах объектов. Это упорядоченная тройка (N, LS, SS). где «N» — количество точек данных в кластере, «LS» — линейная сумма точек данных, а «SS» — квадрат суммы точек данных в кластере.

Например, предположим, что в кластере C есть три точки (2,5), (3,2) и (4,3). Признак кластеризации C: CF = (3, (2+3+4,5+2+3), (2² +3² +4²,5² +2² +3²)) = (3,(9,10), (29,38)).

Дерево CF:

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

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

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

Фаза 1: Загрузка данных в память - Сканирование БД и загрузка данных в память путем построения дерева CF. Восстановите дерево из листового узла, если память исчерпана.

Фаза 2: Уплотнение данных (необязательно) — измените размер набора данных, построив меньшее дерево CF. Удалите больше выбросов.

Фаза 3: Глобальная кластеризация. Используйте существующий алгоритм кластеризации (например, KMEANS) для записей CF.

Фаза 4: Уточнение кластера (необязательно) — устраняет проблему с деревьями CF, где точки данных с одинаковыми значениями могут быть назначены разным листовым записям.

Построение дерева CF

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

→Если точку можно разместить в кластере, обновите запись.

→ Если Радиус (R) выбранного узла пересекает пороговое значение T, разделите запись; если он пересекает предел L, разделите лист. Разделите родительский узел, если он также заполнен, и так далее.

  • Обновите записи CF от корня до листа, чтобы учесть эту точку.

X0 — это центр тяжести кластера, а Xi — точки данных в кластере.

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

Расстояние между листовыми узлами вычисляется с помощью D0 и D1.

Преимущества:

  • Всего за одно сканирование он находит хорошую кластеризацию и повышает качество еще несколькими сканированиями.
  • Работает с очень большими наборами данных.
  • Превосходит другие алгоритмы с точки зрения стабильности и масштабируемости.

Недостатки:

  • Обрабатывает только числовые данные.

Приложения:

  • Классификация пикселей в изображениях.
  • Сжатие изображения.

Ссылки: