Согласно Википедии:
Береза — тонколиственное листопадное лиственное дерево рода Betula семейства Betulaceae, к которому также относятся ольха, лещина и грабы. Он тесно связан с буково-дубовым семейством Fagaceae. Род Betula включает от 30 до 60 известных таксонов, 11 из которых занесены в Красный список исчезающих видов МСОП 2011 года.
Береза, которую мы собираемся здесь обсудить, неэта береза.
Извините, ботаники, вы можете отправиться в другие места, чтобы узнать об этом. Теперь давайте обсудим нашу основную тему. Чтобы изучить алгоритм березы, во-первых, мы должны знать, что такое кластеризация.
Что такое кластеризация?
Алгоритмы кластеризации — это тип алгоритма машинного обучения, который используется для разделения набора данных на группы или кластеры похожих точек данных. Цель алгоритмов кластеризации состоит в том, чтобы найти шаблоны и структуры в данных, которые не очевидны, и сгруппировать точки данных таким образом, чтобы они отражали эти шаблоны и структуры.
Существует множество различных алгоритмов кластеризации, каждый из которых имеет свои сильные и слабые стороны. Существуют различные типы методов кластеризации. В основном они основаны либо на расстоянии, либо на вероятности. Некоторые из них :
- Подход с разделением – это алгоритм, который делит набор данных на заданное количество кластеров путем многократного присвоения каждой точки данных кластеру с ближайшим средним значением. Это быстро и эффективно, но может быть чувствительно к начальному размещению кластеров.
- Иерархическая кластеризация – это алгоритм, который строит иерархию кластеров, при этом каждый кластер делится на более мелкие кластеры, пока все точки данных не окажутся в своем собственном кластере. Это более медленный алгоритм, чем алгоритм k-средних, но он более надежен и может обрабатывать большие наборы данных.
- Кластеризация на основе плотности – это алгоритм, который идентифицирует кластеры, находя области набора данных с высокой плотностью точек данных. Он эффективен при поиске кластеров произвольной формы и устойчив к шуму и выбросам.
- Подход с добавочной кластеризацией — это способ обработки динамически растущего набора данных. Он пытается свести к минимуму усилия по сканированию и вычислению вновь добавленных точек данных. Очень важно эффективно хранить и использовать знания о существующих результатах кластеризации для добавочной кластеризации.
Из них метод Берча представляет собой неконтролируемый алгоритм кластеризации, основанный на подходе иерархической кластеризации, который используется для поиска естественных кластеров в наборе данных. Это быстрый и эффективный алгоритм, который легко реализовать и который может обрабатывать большие наборы данных. В случае большинства методов кластеризации они усложняются, когда мы используем большие наборы данных. Birch — одно из решений, которое мы можем использовать для кластеризации точек данных в больших наборах данных.
ЧТО НЕОБХОДИМО ПОМНИТЬ
- Дерево CF (дерево функций кластеризации)
Метод Birch работает путем построения древовидной структуры, называемой деревом CF (дерево кластерных признаков). Дерево CF строится путем итеративного добавления точек данных в дерево, начиная с одного узла, представляющего кластер. Когда в дерево добавляется новая точка данных, она сравнивается с существующими узлами в дереве. Если точка данных достаточно похожа на существующий узел, она добавляется в кластер, представленный этим узлом. Если точка данных недостаточно похожа ни на один из существующих узлов, она добавляется в дерево как новый кластер.
Алгоритм Берча состоит из четырех фаз:
- Этап 1 включает в себя создание начального дерева CF (функция кластеризации) в памяти.
- Этап 2 (необязательный) включает перестроение меньшего дерева CF с конечными элементами исходного дерева.
- Этап 3 включает использование глобального или полуглобального алгоритма кластеризации для кластеризации листовых записей дерева CF.
- Этап 4 (необязательно) включает в себя дальнейшее уточнение кластеров путем повторного сканирования данных.
Параметры алгоритма BIRCH
- Порог. Порог – это максимальное количество точек данных, которое может содержать подкластер в листовом узле дерева CF.
- Коэффициент ветвления. Этот параметр указывает максимальное количество подкластеров CF в каждом узле (внутреннем узле).
- n кластеров: количество кластеров, которое будет возвращено после завершения всего алгоритма BIRCH, т. е. количество кластеров после последнего шага кластеризации. Если установлено значение None, последний этап кластеризации не выполняется и возвращаются промежуточные кластеры.
2. Функция кластеризации
Функция кластеризации — это тройное обобщение информации, которую мы храним о кластере. Дерево CF представляет собой сбалансированное по высоте дерево, которое собирает и управляет функциями кластеризации и содержит необходимую информацию о заданных данных для дальнейшей иерархической кластеризации. Это избавляет от необходимости работать со всеми входными данными. Функция кластеризации (CF) кластера представляет собой трехмерный вектор, обобщающий информацию о кластерах объектов. Это как,
Где,
n = количество элементов в подкластерах
LS = векторная сумма точек данных
SS = сумма квадратов точек данных
Например, если у нас есть кластер,
c = {1,2,3,4}
Тогда соответствующая функция кластеризации будет:
Здесь n (количество элементов в подкластерах) = 4
LS (векторная сумма точек данных) = 1+2+3+4 = 10
SS (сумма квадратов точек данных) = 1²+2²+3²+4² = 30
Мы можем сделать то же самое для поиска функции кластеризации для двумерных объектов. Мы также можем получить статистику кластера, такую как центр тяжести, радиус и диаметр соответствующего кластера.
Для N-мерной точки данных в кластере: {Xi}, где i = 1,2, …. N, то центр тяжести соответствующего кластера будет Xo,
Здесь числитель — это сумма точек данных в кластере, равная LS. Таким образом, мы можем записать это как:
Точно так же радиус кластера ( R ), среднее расстояние от точек-членов до центроида, можно определить по формуле:
и диаметр (D) кластера, среднее попарное расстояние внутри кластера будет:
Точно так же, если есть центроиды двух кластеров, то центроидное евклидово расстояние и центроидное манхэттенское расстояние двух кластеров будут следующими:
Функции кластеризации также подчиняются «теореме аддитивности». Предположим, что CF₁= (N₁, LS₁ ,SS₁) и CF₂ = (N₂, LS₂ ,SS₂) являются векторами CF двух непересекающихся кластеров. Тогда вектор CF кластера, образованного слиянием двух непересекающихся кластеров, равен:
3. Работа алгоритма Берча
Вот шаги, связанные с работой алгоритма Берча:
- Предварительная обработка. Первый шаг алгоритма Birch — предварительная обработка данных. Это включает в себя очистку и форматирование данных, чтобы обеспечить их готовность к анализу.
- Построение дерева CF. Следующим шагом является построение дерева CF (функции кластеризации), которое представляет собой древовидную структуру данных, используемую для представления набора данных. Дерево CF строится путем создания корневого узла и последующего добавления к нему подузлов до тех пор, пока все точки данных не будут представлены в дереве.
- Кластеризация.После построения дерева CF алгоритм Birch использует его для кластеризации данных. Алгоритм начинается с корневого узла и сравнивает расстояние между точками данных и центроидом узла. Если расстояние находится в пределах определенного порога, точка данных добавляется к узлу. Если расстояние больше порога, создается новый подузел и к нему добавляется точка данных. Этот процесс повторяется до тех пор, пока все точки данных не будут назначены узлу.
- Объединение.После кластеризации точек данных алгоритм Birch объединяет похожие узлы для формирования более крупных кластеров. Это делается путем сравнения расстояния между центроидами узлов и проверки того, находится ли оно в пределах определенного порога. Если это так, узлы объединяются в один кластер.
- Уточнение. Последний шаг алгоритма Берча – уточнение кластеров путем удаления выбросов и обеспечения однородности кластеров. Это делается путем сравнения расстояния между точками данных в кластере и центроидом кластера. Точка данных удаляется из кластера, если расстояние слишком велико.
4. Преимущества перед другими алгоритмами кластеризации
Метод Берча имеет ряд преимуществ перед другими алгоритмами кластеризации. 1. Это быстро и эффективно, так как требуется только один проход по данным.
2. Он также обрабатывает большие наборы данных и может обрабатывать зашумленные или неполные данные.
3. Кроме того, он может идентифицировать кластеры разных размеров и форм и устойчив к выбросам.
5. Приложения
- Одним из основных применений метода Берча является интеллектуальный анализ данных и машинное обучение, где он используется для группировки схожих точек данных для дальнейшего анализа.
- Он также использовался в таких областях, как обработка изображений, обработка естественного языка и анализ социальных сетей.
- Создание итеративного и интерактивного инструмента классификации пикселей
- Сжатие изображения.
6. ЗАКЛЮЧЕНИЕ
Таким образом, метод Берча — это мощный и эффективный алгоритм кластеризации, который широко используется в интеллектуальном анализе данных и машинном обучении. Его способность обрабатывать большие наборы данных, обрабатывать зашумленные или неполные данные и идентифицировать кластеры разных размеров и форм делает его ценным инструментом для различных приложений.
ССЫЛКИ
- Чжан Т., Рамакришнан Р. и Ливни М. (1996). БЕРЕЗА. Запись ACM SIGMOD, 25(2), 103–114. https://doi.org/10.1145/235968.233324
- Чжан, Т. (1997, 1 июня). BIRCH: новый алгоритм кластеризации данных и его приложения. СпрингерЛинк. https://link.springer.com/article/10.1023/A:1009783824328?error=cookies_not_supported&code=91832e7f-6009-48a0-93b0-939176788278
- Верма, Ю. (2021, 11 ноября). Руководство по алгоритму кластеризации BIRCH (с кодами Python). Журнал Analytics India. https://analyticsindiamag.com/guide-to-birch-clustering-algorithmwith-python-codes/
- Гикс для гиков. (2022, 20 июня). ML | БЕРЕЗА Кластеризация. https://www.geeksforgeeks.org/ml-birch-clustering/
- Далал, В. (2022, 26 февраля). Алгоритм BIRCH с рабочим примером — Vipul Dalal. Середина. https://medium.com/@vipulddalal/birch-algorithm-with-working-example-a7b8fe047bd4
- Сваруп, К. С. (2022b, 29 декабря). Обзор алгоритма BIRCH — Kottapalli Sai swaroop. Середина. https://medium.com/@kottapalli.cs22/an-overview-of-birch-algorithm-81a0512eeff4
