Иерархический кластерный анализ

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

Иерархическая кластеризация поможет в создании кластеров в правильном порядке / иерархии. Пример: самый распространенный повседневный пример, который мы видим, – это то, как мы упорядочиваем наши файлы и папки на нашем компьютере по правильной иерархии.

Типы иерархической кластеризации

Иерархическая кластеризация подразделяется на два типа: агломерационная кластеризация и дивизионная кластеризация (DIANA)

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

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

AGNES (AGglomerative NESting) – это тип агломерационной кластеризации, который объединяет объекты данных в кластер на основе сходства. Результатом этого алгоритма является древовидная структура, называемая дендрограммой. Здесь он использует метрики расстояния, чтобы решить, какие точки данных следует объединить с каким кластером. По сути, он строит матрицу расстояний и проверяет пару кластеров с наименьшим расстоянием и объединяет их.

На приведенном выше рисунке показана агломерационная и разделительная кластеризация.

Исходя из того, как измеряется расстояние между кластерами, мы можем использовать 3 разных метода.

• Одиночная связь : где кратчайшее расстояние между двумя точками в каждом кластере определяется как расстояние между кластерами.
• Полная связь : в этом случае мы будем рассматривать самое длинное расстояние между точками в каждом кластере как расстояние между кластерами.
• Средняя связь: здесь мы возьмем среднее между каждой точкой в ​​одном кластере для каждой другой точки в другом кластере.

Теперь давайте поговорим о сильных и слабых сторонах AGNES; этот алгоритм имеет временную сложность, по крайней мере, O (n 2 ), следовательно, он не очень хорошо масштабируется, и еще одним существенным недостатком является то, что все, что было сделано, никогда не может быть отменено, т.е. если мы неправильно сгруппируем любой кластер на более ранней стадии алгоритм тогда мы не сможем изменить результат / изменить его. Но у этого алгоритма есть и яркая сторона, так как формируется множество более мелких кластеров, это может быть полезно в процессе обнаружения и обеспечивает упорядочение объектов, что очень полезно при визуализации.

Дивизионная кластеризация (ДИАНА)

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

На рисунке выше показан пошаговый процесс деления кластеров

Многофазная иерархическая кластеризация

Чтобы улучшить качество кластеров, генерируемых вышеупомянутыми методами иерархической кластеризации, мы интегрируем наши методы иерархической кластеризации с другими методами кластеризации; это называется многофазной кластеризацией. Существуют следующие типы многофазной кластеризации:

• BIRCH (Сбалансированное итеративное сокращение и кластеризация с использованием иерархий)
• ROCK (кластеризация RObust с использованием ссылок)
• ХАМЕЛЕОН

1. Сбалансированное итеративное сокращение и кластеризация с использованием иерархий

Этот метод в основном используется для кластеризации огромного количества числовых данных путем интеграции нашей иерархической / микрокластеризации на начальной стадии и макрокластеризации / итеративного разделения на более поздней фазе. Этот метод помогает преодолеть проблему масштабируемости, с которой мы столкнулись в AGNES, и невозможность отменить то, что было сделано до шага. BIRCH использует два важных понятия в своем алгоритме

а. Функция кластеризации (помогает в суммировании кластера)

CF определяется как (n- количество точек данных в кластере, линейная сумма n точек, квадратная сумма n точек). Хранение свойства кластера таким способом помогает избежать хранения подробной информации о нем, а CF имеет аддитивный характер для разных кластеров.

б. Дерево объектов кластеризации (помогает представить кластер в виде иерархии)

CF-дерево – это сбалансированное дерево с коэффициентом ветвления B (максимальное количество дочерних элементов) и порогом T (максимальное количество субкластеров, которые могут храниться в конечных узлах).

Алгоритм в основном работает в 2 этапа; на этапе 1 он сканирует базу данных и создает дерево CF в памяти, а на этапе 2 он использует алгоритм кластеризации, который помогает в кластеризации конечных узлов путем удаления выбросов (разреженных кластеров) и группирует кластер с максимальной плотностью. Единственный недостаток этого алгоритма заключается в том, что он обрабатывает только числовой тип данных.

2. Надежная кластеризация с использованием ссылок

Ссылка определяется как количество общих соседей между двумя объектами. Алгоритм ROCK – это тип алгоритма кластеризации, который использует эту концепцию связи с категориальным набором данных. Поскольку мы знаем, что алгоритмы кластеризации с измерением расстояния не обеспечивают высококачественные кластеры для категориального набора данных, но в случае ROCK он также учитывает окрестности точек данных, т. Е. Если две точки данных имеют одинаковую окрестность, то они скорее всего, принадлежат к одному кластеру. Алгоритм построит разреженный граф на первом этапе с учетом матрицы подобия с понятием соседства и порога подобия. На втором этапе используется метод агломерационной иерархической кластеризации на разреженном графе.

3. Хамелеон

Этот тип алгоритма иерархической кластеризации использует концепцию динамического моделирования. Хотите знать, почему это называется динамическим? Он называется динамическим, поскольку обладает способностью автоматически адаптироваться к внутренним характеристикам кластера, оценивая сходство кластера, то есть то, насколько хорошо связаны точки данных в кластере и вблизи кластеров. Одним из недостатков хамелеона является то, что стоимость обработки слишком высока (O (n 2 ) для n объектов – сложность времени в худшем случае).

Источник изображения – Google

Вывод

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

Рекомендуемые статьи

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

1. Иерархическая кластеризация в R
2. Алгоритм кластеризации
3. кластеры
4. Методы кластеризации
5. Кластеризация в машинном обучении
6. Иерархическая кластеризация | Агломерационная и разделительная кластеризация

определение

Кластерный анализ – это совокупность методов, позволяющих классифицировать многомерные наблюдения. Термин кластерный анализ, впервые введенный Трионом (Tryon) в 1939 году, включает в себя более 100 различных алгоритмов.

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

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