БЕРЕЗА

Часть серии по
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация  • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Статьи по Теме Глоссарий искусственного интеллекта Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

BIRCH ( сбалансированное итеративное сокращение и кластеризация с использованием иерархий ) - это алгоритм неконтролируемого интеллектуального анализа данных , используемый для выполнения иерархической кластеризации особенно больших наборов данных. ^[1] С изменениями его также можно использовать для ускорения кластеризации k-средних и моделирования смеси Гаусса с помощью алгоритма ожидания-максимизации . ^[2] Преимущество BIRCH заключается в его способности постепенно и динамически кластеризовать входящие многомерные метрические точки данных в попытке произвести кластеризацию наилучшего качества для заданного набора ресурсов (память и временные ограничения). В большинстве случаев BIRCH требует только одного сканирования базы данных.

Его изобретатели утверждают, что BIRCH является «первым алгоритмом кластеризации, предложенным в области базы данных для эффективной обработки« шума »(точек данных, не являющихся частью базового шаблона)» ^[1], опережая DBSCAN на два месяца. Алгоритм BIRCH получил награду SIGMOD 10-летний тест временем в 2006 году. ^[3]

Проблема с предыдущими методами [ править ]

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

Преимущества с БЕРЕЗОЙ [ править ]

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

Алгоритм [ править ]

Алгоритм БЕРЕЗЫ принимает в качестве входных данных набор N точек данных, представленных в качестве вещественных векторов , и желаемое количество кластеров K . Он работает в четыре фазы, вторая из которых является необязательной.

На первом этапе строится дерево функций кластеризации ( ) из точек данных, структура данных дерева со сбалансированной высотой , определяемая следующим образом:${\displaystyle CF}$

• Учитывая набор из N d-мерных точек данных, функция кластеризации набора определяется как тройка , где - линейная сумма, а - квадратная сумма точек данных.${\displaystyle CF}$${\displaystyle CF=(N,{\overrightarrow {LS}},SS)}$${\displaystyle {\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}$${\displaystyle SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}}$
• Функции кластеризации организованы в дерево CF , сбалансированное по высоте дерево с двумя параметрами: ^{[ требуется пояснение ]} коэффициент ветвления и порог . Каждый узел не лист содержит в большинстве записей вида , где является указателем на его го дочернего узла и функции кластеризации , представляющего связанный с ним субкластер. Листовой узел содержит в большинстве записей каждого вида . Он также имеет два указателя prev и next, которые используются для объединения всех листовых узлов. Размер дерева зависит от параметра . Узел необходим, чтобы поместиться на странице такого размера . а также${\displaystyle B}$${\displaystyle T}$${\displaystyle B}$${\displaystyle [CF_{i},child_{i}]}$${\displaystyle child_{i}}$${\displaystyle i}$${\displaystyle CF_{i}}$${\displaystyle L}$${\displaystyle [CF_{i}]}$${\displaystyle T}$${\displaystyle P}$${\displaystyle B}$${\displaystyle L}$определяются . Так может быть изменен для настройки производительности . Это очень компактное представление набора данных, поскольку каждая запись в листовом узле является не отдельной точкой данных, а подкластером.${\displaystyle P}$${\displaystyle P}$

На втором этапе алгоритм просматривает все листовые записи в исходном дереве, чтобы восстановить меньшее дерево, удаляя выбросы и группируя переполненные подкластеры в более крупные. Этот шаг отмечен как необязательный в исходной презентации БЕРЕЗЫ.${\displaystyle CF}$${\displaystyle CF}$

На третьем этапе для кластеризации всех листовых записей используется существующий алгоритм кластеризации. Здесь алгоритм агломеративной иерархической кластеризации применяется непосредственно к подкластерам, представленным их${\displaystyle CF}$векторов. Он также обеспечивает гибкость, позволяя пользователю указать желаемое количество кластеров или желаемый порог диаметра для кластеров. После этого шага получается набор кластеров, отражающий основную схему распределения данных. Однако могут существовать незначительные и локализованные неточности, которые можно обработать на необязательном шаге 4. На шаге 4 центроиды кластеров, созданных на шаге 3, используются в качестве начальных значений и перераспределяют точки данных между ближайшими к ним начальными элементами для получения нового набора кластеры. Шаг 4 также дает нам возможность отбросить выбросы. Это точка, которая находится слишком далеко от ближайшего к ней семени, и ее можно рассматривать как выброс.

Расчеты с функциями кластеризации [ править ]

Учитывая только функцию кластеризации , те же показатели могут быть рассчитаны без знания основных фактических значений.${\displaystyle CF=[N,{\overrightarrow {LS}},SS]}$

• Центроид: ${\displaystyle {\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow {LS}}{N}}}$
• Радиус: ${\displaystyle R={\sqrt {\frac {\sum _{i=1}^{N}({\overrightarrow {X_{i}}}-{\overrightarrow {C}})^{2}}{N}}}={\sqrt {\frac {N\cdot {\overrightarrow {C}}^{2}+SS-2\cdot {\overrightarrow {C}}\cdot {\overrightarrow {LS}}}{N}}}={\sqrt {{\frac {SS}{N}}-({\frac {\overrightarrow {LS}}{N}})^{2}}}}$
• Среднее расстояние связи между кластерами и :${\displaystyle CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]}$${\displaystyle CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]}$${\displaystyle D_{2}={\sqrt {\frac {\sum _{i=1}^{N_{1}}\sum _{j=1}^{N_{2}}({\overrightarrow {X_{i}}}-{\overrightarrow {Y_{j}}})^{2}}{N_{1}\cdot N_{2}}}}={\sqrt {\frac {N_{1}\cdot SS_{2}+N_{2}\cdot SS_{1}-2\cdot {\overrightarrow {LS_{1}}}\cdot {\overrightarrow {LS_{2}}}}{N_{1}\cdot N_{2}}}}}$

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

Числовые проблемы в функциях кластеризации BIRCH [ править ]

К сожалению, есть числовые проблемы, связанные с использованием термина в BIRCH. При вычитании или подобном для других расстояний, таких как , может произойти катастрофическая отмена и дать плохую точность, а в некоторых случаях даже привести к отрицательному результату (и тогда квадратный корень станет неопределенным). ^[2] Эту проблему можно решить, используя вместо этого функции кластера BETULA , которые вместо этого хранят подсчет , среднее значение и сумму квадратов отклонений на основе численно более надежных онлайн-алгоритмов для расчета дисперсии.${\displaystyle SS}$${\displaystyle {\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}}$${\displaystyle D_{2}}$${\displaystyle CF=(N,\mu ,S)}$${\displaystyle N}$${\displaystyle \mu }$. Для этих функций справедлива аналогичная теорема аддитивности. При сохранении вектора или матрицы для квадратов отклонений полученное CF-дерево BIRCH также может использоваться для ускорения моделирования гауссовой смеси с алгоритмом ожидания-максимизации , помимо кластеризации k-средних и иерархической агломеративной кластеризации .

Заметки [ править ]