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

Введение в кластеризацию и алгоритм K-средних (K-Means)

Добро пожаловать на курс «Алгоритмы кластеризации: теория и применение». Мы начинаем наше путешествие в мир машинного обучения с одной из самых интуитивно понятных и визуально красивых задач — задачи кластеризации. В этой первой статье мы разберем фундаментальные понятия и детально изучим самый популярный алгоритм в этой области — K-Means (K-средних).

Что такое кластеризация?

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

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

В терминах машинного обучения кластеризация относится к классу задач обучения без учителя (Unsupervised Learning). Это означает, что у наших данных нет правильных ответов или меток (labels). Алгоритм должен сам найти закономерности и сгруппировать объекты так, чтобы:

Объекты внутри одной группы (кластера) были максимально похожи друг на друга.

Объекты из разных групп были максимально различны.

!Визуализация процесса кластеризации: переход от неразмеченных данных к выделенным группам.

Где это применяется?

Кластеризация окружает нас повсюду:

* Маркетинг: Сегментация клиентской базы. Магазин может выделить группы покупателей: «экономные студенты», «родители с детьми», «любители техники», чтобы предлагать им релевантные товары. * Геолокация: Определение оптимальных мест для строительства складов или вышек сотовой связи на основе плотности населения. * Обработка изображений: Сжатие цветов (уменьшение палитры изображения) или выделение объектов на фото. * Биология: Классификация растений и животных на основе их генетических признаков.

Алгоритм K-средних (K-Means)

Алгоритм K-Means — это «рабочая лошадка» кластеризации. Он прост в реализации, работает быстро и часто дает отличные результаты. Название алгоритма раскрывает его суть: мы ищем кластеров, каждый из которых определяется своим средним значением (центром).

Основные понятия

Прежде чем разобрать шаги алгоритма, определим ключевые термины:

(количество кластеров): Число групп, которые мы хотим найти. Это гиперпараметр*, то есть мы должны задать его заранее. * Центроид (Centroid): Центр кластера. Это воображаемая точка, координаты которой являются средним арифметическим координат всех точек, принадлежащих этому кластеру.

Как работает алгоритм: пошаговая инструкция

Алгоритм работает итеративно, то есть повторяет одни и те же действия, пока результат не перестанет меняться. Вот как это происходит:

Инициализация: Мы выбираем число (например, 3). Затем случайным образом выбираем 3 точки в пространстве наших данных и объявляем их начальными центроидами.

Присвоение (Assignment): Для каждой точки данных мы считаем расстояние до всех центроидов. Точка «приписывается» к тому кластеру, чей центроид находится ближе всего.

Обновление (Update): После того как все точки распределены, мы пересчитываем положение центроидов. Новый центроид кластера становится в центр масс всех точек, попавших в этот кластер.

Повторение: Мы повторяем шаги 2 и 3 до тех пор, пока центроиды не перестанут двигаться (или изменения станут ничтожно малы). Это называется сходимостью алгоритма.

!Этапы работы алгоритма K-Means: от инициализации до сходимости.

Математика расстояний

Как алгоритм понимает, что одна точка «ближе» другой? Ему нужна метрика расстояния. Чаще всего в K-Means используется классическое Евклидово расстояние.

Для двух точек на плоскости (или в многомерном пространстве) расстояние рассчитывается так:

Где: * — расстояние между точкой и точкой . * — операция извлечения квадратного корня. * — знак суммы, означающий сложение значений для всех измерений от 1 до (например, для плоскости : ось X и ось Y). * — координата точки в измерении . * — координата точки в измерении .

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

Целевая функция

Алгоритм K-Means стремится минимизировать так называемую инерцию или внутрикластерную сумму квадратов (WCSS — Within-Cluster Sum of Squares). Формально это выглядит так:

Где: * — значение целевой функции (ошибка, которую мы хотим уменьшить). * — количество кластеров. * — сумма по всем кластерам. * — сумма по всем точкам , которые попали в кластер . * — квадрат расстояния от точки до центроида этого кластера.

Суть формулы проста: мы хотим, чтобы все точки сидели как можно плотнее вокруг своих центроидов.

Проблема выбора K: Метод локтя

Самый частый вопрос новичков: «А как узнать, сколько кластеров искать?». Ведь в реальных данных мы не видим картинку глазами.

Для этого существует эвристический метод, называемый Методом локтя (Elbow Method).

Идея заключается в следующем:

Запускаем K-Means для разного количества кластеров (например, от 1 до 10).

Для каждого считаем значение инерции (WCSS).

Строим график: по оси X — количество кластеров , по оси Y — ошибка WCSS.

С увеличением ошибка всегда будет падать (если каждый объект станет отдельным кластером, ошибка будет равна 0). Но нам нужно найти баланс.

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

!График метода локтя, помогающий определить оптимальное число кластеров.

Преимущества и недостатки K-Means

Как и любой инструмент, K-Means не идеален. Важно знать его сильные и слабые стороны.

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

* Простота: Легко понять и реализовать. * Скорость: Работает очень быстро даже на больших данных. * Интерпретируемость: Результаты (центроиды) легко объяснить бизнесу.

Недостатки

* Нужно знать K: Алгоритм не умеет сам определять число кластеров. Чувствительность к инициализации: Если неудачно выбрать начальные центроиды, результат может быть плохим. (Эту проблему решает улучшенная версия K-Means++*, о которой мы поговорим в следующих статьях). * Форма кластеров: K-Means хорошо находит только сферические (круглые) кластеры. Если данные вытянуты в длинную линию или образуют «бублик», алгоритм не справится. * Выбросы: Одна точка, отлетевшая далеко от всех, может сильно сместить центроид и испортить кластеризацию.

Заключение

Сегодня мы познакомились с концепцией кластеризации и алгоритмом K-Means. Это фундамент, на котором строится понимание более сложных методов. Мы узнали, что кластеризация ищет структуру в хаосе, а K-Means делает это, перемещая центроиды к центрам масс групп точек.

В следующей статье мы углубимся в методы оценки качества кластеризации и разберем, как бороться с недостатками K-Means на практике.

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

В предыдущей статье мы познакомились с алгоритмом K-Means. Вы наверняка заметили его главный недостаток: нам приходилось заранее угадывать количество кластеров . Но что делать, если мы ничего не знаем о структуре данных? Или если данные имеют сложную вложенную структуру, напоминающую матрёшку или генеалогическое древо?

Сегодня мы разберем иерархическую кластеризацию — метод, который не требует заранее задавать число кластеров и позволяет визуализировать структуру данных в виде красивого дерева, называемого дендрограммой.

Что такое иерархическая кластеризация?

В отличие от K-Means, который пытается сразу разбить данные на плоские группы, иерархическая кластеризация строит систему вложенных разбиений. Представьте, что вы организуете файлы на компьютере. Сначала вы объединяете файлы в папки, затем эти папки — в папки более высокого уровня, и так до тех пор, пока всё не окажется на одном диске.

Существует два основных подхода к иерархической кластеризации:

Агломеративная (Agglomerative): Подход «снизу-вверх». В начале каждая точка считается отдельным кластером. На каждом шаге мы объединяем два самых близких кластера, пока все точки не сольются в один большой кластер.

Дивизивная (Divisive): Подход «сверху-вниз». В начале все точки находятся в одном гигантском кластере. На каждом шаге мы разделяем кластеры на части, пока каждая точка не станет отдельным кластером.

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

!Визуальное различие между подходами «снизу-вверх» и «сверху-вниз».

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

Давайте разберем, как работает алгоритм, шаг за шагом. Представьте, что у нас есть 5 точек на плоскости: A, B, C, D, E.

Инициализация: Каждая точка — это отдельный кластер. У нас есть 5 кластеров: .

Поиск ближайших: Мы вычисляем расстояния между всеми парами кластеров и находим самую близкую пару. Допустим, точки A и B находятся ближе всего друг к другу.

Объединение: Мы сливаем A и B в новый кластер . Теперь у нас 4 кластера: .

Повторение: Снова ищем ближайшие кластеры. Теперь нам нужно знать расстояние не просто между точками, а между кластером и точкой . Допустим, ближайшими оказываются и . Объединяем их. Теперь кластеры: .

Завершение: Продолжаем процесс, пока все точки не окажутся в одном кластере .

Дендрограмма: карта наших данных

Главное преимущество иерархической кластеризации — результат можно изобразить графически. Такой график называется дендрограммой (от греч. dendron — дерево).

Дендрограмма показывает историю объединений: * По оси X расположены наши исходные объекты (точки). * По оси Y отложено расстояние (или схожесть), на котором произошло объединение.

Чем выше перекладина, соединяющая две линии, тем больше различие между объединяемыми объектами. Если перекладина находится низко, значит, объекты очень похожи.

!Пример дендрограммы с линией отсечения, определяющей количество кластеров.

Как выбрать количество кластеров?

В K-Means мы использовали метод локтя. Здесь всё проще и нагляднее. Мы смотрим на дендрограмму и проводим воображаемую (или реальную) горизонтальную линию. Количество вертикальных линий, которые пересечет наша горизонтальная черта, и будет количеством кластеров.

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

Как измерить расстояние между кластерами?

В алгоритме мы упомянули важный момент: «найти расстояние между кластерами». Если расстояние между двумя точками понятно (обычная линейка, евклидово расстояние), то как измерить расстояние между «облаком точек А» и «облаком точек Б»?

Существует несколько методов связи (Linkage Methods), и выбор метода сильно влияет на форму получаемых кластеров.

1. Одиночная связь (Single Linkage)

Расстояние между двумя кластерами определяется как расстояние между двумя самыми близкими точками этих кластеров.

Где: * — расстояние между кластерами и . * — поиск минимального значения. * — точка , принадлежащая кластеру . * — точка , принадлежащая кластеру . * — расстояние между точками и .

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

2. Полная связь (Complete Linkage)

Здесь мы берем противоположность: расстояние между кластерами — это расстояние между двумя самыми далекими точками.

Где: * — поиск максимального значения. * Остальные обозначения те же, что и выше.

Особенность: Этот метод избегает цепочек и стремится создавать компактные кластеры примерно одинакового диаметра. Однако он чувствителен к выбросам (одна далекая точка может «оттолкнуть» кластер).

3. Средняя связь (Average Linkage)

Мы вычисляем среднее арифметическое всех попарных расстояний между точками одного кластера и точками другого.

Где: * и — количество точек в кластерах и соответственно. * — знак суммирования по всем точкам.

Особенность: Компромиссный вариант, часто дающий хорошие результаты. Менее чувствителен к шуму, чем Single Linkage.

4. Метод Уорда (Ward's Method)

Этот метод наиболее близок к идеологии K-Means. Мы объединяем те два кластера, слияние которых приведет к минимальному увеличению дисперсии (суммы квадратов расстояний) внутри объединенного кластера.

Особенность: Метод Уорда обычно работает лучше всего для поиска сферических кластеров и является стандартным выбором во многих библиотеках (например, Scikit-learn).

!Сравнение того, как разные методы связи группируют одни и те же данные.

Плюсы и минусы иерархической кластеризации

Чтобы понять, когда использовать этот метод, давайте сравним его с уже известным нам K-Means.

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

Не нужно знать K: Мы можем построить дерево и уже потом решить, на сколько кластеров делить данные, глядя на дендрограмму.

Интерпретируемость: Иерархическая структура часто соответствует естественной природе данных (таксономия в биологии, категории товаров).

Детерминированность: Если не считать случаев с одинаковыми расстояниями, алгоритм всегда выдает один и тот же результат при каждом запуске (в отличие от K-Means, где результат зависит от случайной инициализации центроидов).

Недостатки

Вычислительная сложность: Это главный минус. Алгоритм очень медленный для больших данных. Его сложность составляет порядка или даже , где — число объектов. Для сравнения, K-Means имеет линейную сложность . Если у вас миллион строк данных, иерархическая кластеризация может считаться годами.

Необратимость: Если на раннем этапе алгоритм ошибочно объединил две точки, их уже нельзя разъединить на следующих шагах. K-Means же может перебрасывать точки между кластерами в процессе обучения.

Заключение

Иерархическая кластеризация — мощный инструмент для разведочного анализа данных (EDA), когда набор данных относительно невелик (до нескольких тысяч объектов). Она позволяет увидеть структуру данных «с высоты птичьего полета» благодаря дендрограммам.

Мы разобрали: * Разницу между агломеративным и дивизивным подходами. * Как строить и читать дендрограммы. * Как выбор метрики расстояния (Single, Complete, Ward) меняет результат.

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

Методы, основанные на плотности: алгоритм DBSCAN и работа с шумом

Мы продолжаем наш курс «Алгоритмы кластеризации: теория и применение». В предыдущих статьях мы изучили K-Means, который разбивает данные на сферические группы, и иерархическую кластеризацию, строящую деревья связей. Однако оба этих метода имеют свои ограничения. K-Means плохо справляется с кластерами сложной формы (например, в виде полумесяцев или вложенных колец) и чувствителен к выбросам. Иерархическая кластеризация, хоть и наглядна, требует огромных вычислительных ресурсов.

Сегодня мы познакомимся с принципиально иным подходом — кластеризацией, основанной на плотности. Мы разберем алгоритм DBSCAN, который умеет находить кластеры любой формы, автоматически определять их количество и, что самое важное, игнорировать мусорные данные (шум).

Интуиция плотности: острова в океане

Представьте, что вы смотрите на карту архипелага сверху. Вы видите группы островов, расположенных близко друг к другу. Где-то острова образуют плотную кучу, где-то вытянуты в цепочку, а где-то есть одинокие скалы, удаленные от всех.

Для алгоритмов, основанных на плотности, кластер — это область пространства, где точек (островов) много, окруженная областями, где точек мало (океан).

В отличие от K-Means, который пытается найти центр и собрать точки вокруг него, плотностные методы ищут соседей. Если у точки достаточно много соседей, она становится частью кластера. Если соседей нет — это шум.

!Слева: ошибка K-Means на сложных формах. Справа: корректная работа DBSCAN.

Алгоритм DBSCAN

Название алгоритма расшифровывается как Density-Based Spatial Clustering of Applications with Noise (Пространственная кластеризация, основанная на плотности, для приложений с шумом). Он был предложен в 1996 году и до сих пор остается одним из самых цитируемых методов в Data Science.

Два главных параметра

Чтобы запустить DBSCAN, нам не нужно указывать количество кластеров . Вместо этого нам нужно определить, что такое «близко» и что такое «много». Для этого используются два параметра:

(Epsilon): Радиус окрестности. Это максимальное расстояние между двумя точками, при котором они считаются соседями.

(Minimum Points): Минимальное количество точек (включая саму точку), которое должно находиться внутри радиуса , чтобы область считалась плотной.

Классификация точек

На основе этих параметров DBSCAN делит все точки датасета на три типа:

Ядровые точки (Core Points): Это точки, в радиусе у которых находится не менее соседей. Это «сердце» кластера.

Граничные точки (Border Points): Это точки, у которых соседей меньше, чем , но они находятся в радиусе от ядровой точки. Они являются частью кластера, но находятся на его краю.

Шумовые точки (Noise / Outliers): Это точки, которые не являются ни ядровыми, ни граничными. У них мало соседей, и рядом нет ни одной ядровой точки. Алгоритм помечает их как «-1» и не относит ни к одному кластеру.

!Визуализация различий между ядровыми, граничными и шумовыми точками.

Математическое определение окрестности

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

Где: * — множество точек-соседей для точки в радиусе . * — любая точка , принадлежащая нашему набору данных . * — расстояние между точкой и точкой (обычно Евклидово). * — условие, что расстояние должно быть меньше или равно заданному радиусу .

Условие для ядровой точки выглядит так:

Где: * — количество точек в окрестности (мощность множества соседей). * — знак «больше или равно». * — пороговое значение минимального количества точек.

Как работает алгоритм: пошагово

Процесс кластеризации напоминает заражение в эпидемиологической модели или распространение огня:

Выбор точки: Алгоритм выбирает случайную точку , которую он еще не посещал.

Проверка окрестности: Он считает, сколько точек находится в радиусе от .

Решение:

* Если соседей , точка помечается как Ядровая, и создается новый кластер. Все соседи добавляются в этот кластер. * Если соседей , точка временно помечается как Шум. (Позже она может стать Граничной, если до нее дотянется другой кластер).

Расширение кластера: Если создан новый кластер, алгоритм смотрит на всех соседей точки . Если сосед тоже оказывается Ядровой точкой, то его соседи также добавляются в кластер. Так «пятно» кластера расползается по плотной области до тех пор, пока не упрется в разреженное пространство.

Повторение: Когда текущий кластер полностью обнаружен (расширяться больше некуда), алгоритм выбирает новую непосещенную точку и повторяет процесс с шага 1.

В итоге все точки будут либо приписаны к какому-то кластеру, либо останутся помеченными как Шум.

Как выбрать параметры Epsilon и MinPts?

Это самый сложный момент в работе с DBSCAN. Если выбрать слишком маленьким, большая часть данных станет шумом. Если слишком большим — все кластеры сольются в один.

Выбор MinPts

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

Выбор Epsilon: Метод k-расстояний

Для выбора радиуса используют график k-расстояний (k-distance graph):

Для каждой точки вычисляем расстояние до ее -го ближайшего соседа (где ).

Сортируем эти расстояния по возрастанию.

Строим график: по оси X — индекс точки, по оси Y — расстояние.

Ищем точку «излома» (колено) графика. Значение по оси Y в этой точке и будет оптимальным .

!График для определения оптимального радиуса Epsilon.

Преимущества и недостатки DBSCAN

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

Произвольная форма: Алгоритм легко находит кластеры в виде спиралей, дуг, букв и любых других геометрических фигур, недоступных для K-Means.

Устойчивость к шуму: Выбросы не искажают центры кластеров (как в K-Means), а просто игнорируются и помечаются отдельной меткой (-1).

Не нужно знать K: Количество кластеров определяется автоматически исходя из плотности данных.

Недостатки

Разная плотность: DBSCAN плохо работает, если в данных есть кластеры с разной плотностью. Например, один кластер очень тугой и компактный, а второй — рыхлый. Невозможно подобрать одно значение , которое подходило бы для обоих: для тугого оно будет слишком большим (объединит с другими), а для рыхлого — слишком маленьким (разорвет его на части или посчитает шумом).

Проклятие размерности: В пространствах высокой размерности (когда признаков очень много) понятие «расстояния» теряет смысл, и найти плотные участки становится крайне сложно.

Чувствительность к параметрам: Небольшое изменение может кардинально изменить результат кластеризации.

Заключение

DBSCAN — это мощный инструмент в арсенале специалиста по данным. Он переопределяет понятие кластера с «группы точек вокруг центра» на «область высокой плотности». Это делает его незаменимым для задач геоаналитики (поиск районов города), астрономии и обработки изображений.

Однако он не универсален. Если ваши данные имеют переменную плотность, вам могут понадобиться более продвинутые алгоритмы, такие как OPTICS или HDBSCAN, которые являются развитием идей DBSCAN.

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

Вероятностный подход: модели гауссовых смесей (GMM)

Мы продолжаем наш курс «Алгоритмы кластеризации: теория и применение». В предыдущих статьях мы рассмотрели два принципиально разных подхода. K-Means (K-средних) — это строгий геометрический алгоритм, который делит данные на сферы. DBSCAN — это алгоритм, основанный на плотности, который ищет сгустки произвольной формы и отсеивает шум.

Но что, если наши данные не являются ни идеальными сферами, ни четко очерченными плотными островами? Что, если границы между кластерами размыты, и мы не уверены на 100%, к какой группе относится конкретная точка? Здесь на сцену выходит вероятностная кластеризация и её самый яркий представитель — модель гауссовых смесей (Gaussian Mixture Model, GMM).

Жесткая и мягкая кластеризация

Давайте вспомним K-Means. Когда этот алгоритм завершает работу, каждая точка получает метку: «Ты принадлежишь кластеру А». Без вариантов. Даже если точка лежит ровно посередине между центрами двух кластеров, алгоритм принудительно припишет её к одному из них. Это называется жесткой кластеризацией (Hard Clustering).

Однако в реальном мире всё не так однозначно. Представьте, что мы классифицируем новости. Статья про «Финансирование футбольного клуба» — это «Спорт» или «Экономика»? Скорее всего, это 70% экономики и 30% спорта.

GMM предлагает подход мягкой кластеризации (Soft Clustering). Вместо жесткой метки алгоритм выдает вероятность принадлежности точки к каждому из кластеров. Например: «Точка X принадлежит кластеру 1 с вероятностью 0.8 и кластеру 2 с вероятностью 0.2».

Что такое нормальное распределение?

Чтобы понять GMM, нужно вспомнить школьную или университетскую статистику, а именно — нормальное (гауссово) распределение.

Это знаменитая «колоколообразная кривая». В природе многие величины распределены именно так: рост людей, ошибки измерений, IQ, размер обуви. Большинство значений группируется вокруг среднего, а чем дальше от центра, тем реже встречаются значения.

Одномерное распределение Гаусса описывается двумя параметрами:

Среднее значение (, мю): Центр колокола (пик).

Стандартное отклонение (, сигма): Ширина колокола. Чем больше , тем более пологим и широким будет распределение.

Формула плотности вероятности для одной точки выглядит так:

Где: * — плотность вероятности (высота кривой) в точке . * — среднее значение (центр распределения). * — стандартное отклонение (разброс данных). * — число Пи (примерно 3.14159). * — число Эйлера (основание натурального логарифма, примерно 2.718).

!Визуализация того, как параметры среднего и отклонения влияют на форму колокола Гаусса.

Идея GMM: Смесь колоколов

Модель гауссовых смесей предполагает, что все наши данные были сгенерированы из смеси нескольких нормальных распределений.

Представьте, что у нас есть данные о росте людей в школе. Если мы построим график, мы увидим сложную форму с двумя горбами. Почему? Потому что это смесь двух распределений: роста учеников младших классов и роста старшеклассников. GMM пытается найти эти скрытые распределения и восстановить их параметры.

В многомерном пространстве (когда у нас много признаков) «колокол» превращается в «холм» или эллипсоид. Форма и ориентация этого эллипсоида определяются ковариационной матрицей (обозначается ).

Таким образом, каждый кластер в GMM описывается тремя параметрами:

Среднее (): Где находится центр кластера.

Ковариация (): Какова форма, размер и наклон кластера (круглый, вытянутый, сплюснутый).

Вес (): Насколько этот кластер большой по сравнению с другими (какую долю всех данных он содержит).

Как обучается GMM: Алгоритм EM

В K-Means мы двигали центроиды. В GMM мы должны подобрать параметры () для каждого из распределений так, чтобы они максимально точно описывали наши данные.

Для этого используется мощный метод, называемый EM-алгоритмом (Expectation-Maximization). Он очень похож на работу K-Means, но работает с вероятностями.

Шаг 1: Инициализация

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

Шаг 2: E-step (Ожидание / Expectation)

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

Это называется «ответственностью» (responsibility). Если точка находится близко к центру первого кластера, его ответственность за эту точку будет высокой (например, 0.9). Если точка далеко — низкой.

Шаг 3: M-step (Максимизация / Maximization)

Теперь мы обновляем параметры кластеров, используя вероятности, полученные на предыдущем шаге.

* Новое среднее (): Это взвешенный центр всех точек. Если точка имеет вероятность 0.9 принадлежности к кластеру, она сильно тянет центр на себя. Если 0.01 — почти не влияет. * Новая ковариация (): Мы пересчитываем ширину и наклон эллипса, опять же, учитывая веса точек. * Новый вес (): Мы смотрим, сколько «суммарной вероятности» пришлось на этот кластер.

Шаг 4: Повторение

Мы повторяем шаги E и M до тех пор, пока параметры не перестанут меняться (алгоритм сойдется).

!Пошаговая иллюстрация того, как EM-алгоритм подгоняет гауссовы распределения под данные.

Гибкость формы: Типы ковариации

Одно из главных преимуществ GMM перед K-Means — это способность принимать форму эллипсов. K-Means всегда ищет круги. GMM может адаптироваться.

В библиотеках машинного обучения (например, Scikit-learn) можно выбрать тип ковариации, что ограничивает свободу формы кластеров:

Spherical (Сферическая): Кластеры могут быть разного размера, но всегда остаются круглыми (сферическими). Это делает GMM похожим на K-Means.

Diagonal (Диагональная): Кластеры могут вытягиваться, но их оси должны быть параллельны осям координат. Эллипс нельзя поворачивать под углом.

Full (Полная): Полная свобода. Кластеры могут быть любой формы (эллипсы) и повернуты под любым углом. Это самый гибкий, но и самый вычислительно сложный вариант.

Tied (Связанная): Все кластеры имеют одинаковую форму и размер, но могут быть повернуты. (Используется редко).

Как выбрать количество кластеров?

В K-Means мы использовали метод локтя и инерцию. В GMM понятие инерции неприменимо, так как мы максимизируем правдоподобие (Likelihood).

Для выбора в GMM используют информационные критерии, которые штрафуют модель за излишнюю сложность:

* AIC (Akaike Information Criterion) * BIC (Bayesian Information Criterion)

Формула BIC выглядит так:

Где: * — количество параметров в модели (чем больше кластеров, тем больше параметров). * — натуральный логарифм от количества точек данных . * — максимальное значение функции правдоподобия модели (насколько хорошо модель описывает данные).

Суть проста: чем меньше значение BIC (или AIC), тем лучше. Мы ищем баланс: модель должна хорошо описывать данные (высокое правдоподобие ), но не должна быть слишком сложной (малое ). Обычно строят график BIC от количества кластеров и выбирают минимум.

Преимущества и недостатки GMM

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

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

Гибкость формы: В отличие от K-Means, GMM отлично справляется с вытянутыми кластерами.

Генеративная модель: Поскольку GMM описывает распределение данных, мы можем использовать обученную модель, чтобы генерировать новые данные, похожие на исходные.

Недостатки

Сложность вычислений: GMM работает медленнее, чем K-Means, особенно на больших данных.

Локальные минимумы: Как и K-Means, EM-алгоритм может застрять в локальном оптимуме. Результат зависит от начальной инициализации.

Нужно угадать распределение: GMM предполагает, что данные состоят из нормальных распределений. Если ваши кластеры имеют форму полумесяцев (как в примере с DBSCAN), GMM не сможет их корректно описать.

Заключение

Модели гауссовых смесей — это мост между простой геометрической кластеризацией и сложным вероятностным моделированием. Они позволяют увидеть структуру данных там, где K-Means видит лишь круги, и дают нам понимание уверенности в наших предсказаниях.

Теперь в нашем арсенале есть: * K-Means: Быстрый, простой, для сферических кластеров. * Hierarchical: Для построения таксономий и визуализации структуры. * DBSCAN: Для поиска кластеров сложной формы и борьбы с шумом. * GMM: Для мягкой кластеризации и работы с эллиптическими данными.

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

Метрики оценки качества кластеризации и реальные кейсы

Мы подошли к финальной части нашего курса «Алгоритмы кластеризации: теория и применение». В предыдущих статьях мы разобрали, как работают K-Means, иерархическая кластеризация, DBSCAN и GMM. Мы научились находить структуры в данных, будь то сферы, спирали или вероятностные облака.

Но остался один критически важный вопрос, который часто ставит в тупик даже опытных специалистов: «А насколько хорош полученный результат?».

В задачах обучения с учителем (классификация, регрессия) всё просто: у нас есть правильные ответы. Мы можем посчитать точность (Accuracy) или среднеквадратичную ошибку (MSE). Но в кластеризации правильных ответов нет. Мы не знаем, сколько на самом деле должно быть групп и какие они.

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

Проблема оценки качества

Оценка кластеризации всегда субъективна. Хорошее разбиение для маркетолога (сегментация клиентов по чеку) может быть плохим для инженера (сегментация по техническим логам).

Глобально все метрики делятся на два типа:

Внешние метрики (External): Используются, если у нас есть истинная разметка (ground truth). Это редкость в реальной жизни, но полезно для тестирования алгоритмов на эталонных датасетах.

Внутренние метрики (Internal): Используются, когда правильных ответов нет. Они оценивают качество, основываясь только на свойствах самих кластеров (компактность и отделимость).

Мы сосредоточимся на внутренних метриках, так как именно с ними вы будете работать в 99% случаев.

Внутренние метрики качества

Идеальная кластеризация должна удовлетворять двум критериям:

Компактность (Cohesion): Объекты внутри одного кластера должны быть максимально похожи друг на друга (находиться близко).

Отделимость (Separation): Кластеры должны находиться как можно дальше друг от друга.

!Сравнение компактных и хорошо разделенных кластеров с рыхлыми и пересекающимися.

Коэффициент Силуэта (Silhouette Coefficient)

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

Для каждой точки данных значение силуэта рассчитывается так:

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

Как интерпретировать результат: Значение метрики лежит в диапазоне от -1 до 1. * Близко к 1: Идеально. Точка находится далеко от соседних кластеров и близко к своему. * 0: Точка находится на границе двух кластеров (неопределенность). * Близко к -1: Ошибка. Точка была отнесена не к тому кластеру (она ближе к соседям, чем к «своим»).

Чтобы оценить качество всей кластеризации, мы берем среднее значение по всем точкам датасета.

Индекс Дэвиса-Болдина (Davies-Bouldin Index)

Эта метрика оценивает сходство кластеров друг с другом. Мы хотим, чтобы кластеры были как можно менее похожи (то есть индекс должен быть минимальным).

Формула выглядит устрашающе, но суть её проста:

Где: * — итоговый индекс Дэвиса-Болдина. * — количество кластеров. * — сумма значений для каждого кластера. * — поиск «худшего» (самого близкого) соседа для текущего кластера. * и — средний разброс (диаметр) внутри кластеров и (мы хотим, чтобы он был маленьким). * — расстояние между центроидами кластеров и (мы хотим, чтобы оно было большим).

Простыми словами: мы берем сумму размеров двух кластеров и делим на расстояние между ними. Чем меньше результат, тем лучше разделение.

Индекс Калински-Харабаса (Calinski-Harabasz Index)

Также известен как критерий отношения дисперсий (Variance Ratio Criterion). Он сравнивает дисперсию (разброс) между кластерами с дисперсией внутри кластеров.

В отличие от Дэвиса-Болдина, здесь чем выше значение, тем лучше.

Внешние метрики (если есть разметка)

Иногда мы проводим кластеризацию на данных, где метки уже известны, чтобы проверить, способен ли алгоритм восстановить структуру. Например, мы берем размеченный датасет ирисов Фишера, прячем метки, запускаем K-Means и сравниваем результат с реальностью.

* Adjusted Rand Index (ARI): Считает долю пар точек, которые были правильно разбиты (либо вместе в одном кластере и в реальности, и в предсказании, либо в разных и там, и там). Диапазон от -1 до 1. * Normalized Mutual Information (NMI): Измеряет количество информации, которую одно разбиение дает о другом. Диапазон от 0 до 1.

Реальные кейсы применения кластеризации

Теория и формулы — это хорошо, но где это применяется на практике? Рассмотрим три классических сценария.

Кейс 1: Сегментация клиентов в ритейле (RFM-анализ)

Проблема: У интернет-магазина миллион покупателей. Делать всем одну рассылку неэффективно. Нужно разделить их на группы для персонализированного маркетинга.

Решение: Используется подход RFM (Recency, Frequency, Monetary). Для каждого клиента рассчитываются три числа:

Давность последней покупки.

Частота покупок.

Сумма покупок.

Затем применяется алгоритм K-Means или иерархическая кластеризация.

Результат: Алгоритм выделяет группы: «Чемпионы»:* Покупают часто, много и недавно. «Лояльные»:* Покупают часто, но средний чек невысокий. «В зоне риска»:* Покупали много, но давно не заходили.

Бизнес может отправить «Чемпионам» эксклюзивное предложение, а тем, кто «В зоне риска» — скидку для возвращения.

!Визуализация сегментации клиентов по трем параметрам RFM.

Кейс 2: Детекция аномалий в кибербезопасности

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

Решение: Используется алгоритм DBSCAN или Isolation Forest. Логика проста: нормальные транзакции похожи друг на друга и образуют плотные кластеры. Аномалии — это одинокие точки в разреженном пространстве (шум).

Результат: Система помечает транзакции, которые не попали ни в один плотный кластер, как подозрительные. Служба безопасности проверяет только их, экономя тысячи часов.

Кейс 3: Сжатие цветов изображения

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

Решение: Каждый пиксель изображения имеет три координаты цвета (Red, Green, Blue). Если на картинке миллион цветов, мы можем запустить K-Means с . Алгоритм найдет 16 «средних» цветов, которые лучше всего описывают всё изображение.

Результат: Каждый пиксель заменяется на ближайший центроид. Размер файла уменьшается, а изображение приобретает стилизованный «постеризованный» вид.

Заключение курса

Мы прошли путь от интуитивного понимания группировки объектов до сложных вероятностных моделей и метрик оценки.

Что мы узнали: * K-Means — ваш первый выбор для простых задач и сферических кластеров. * Иерархическая кластеризация — идеальна для анализа структуры небольших данных. * DBSCAN — незаменим, когда данные имеют сложную форму и содержат шум. * GMM — помогает, когда границы размыты и нужна мягкая классификация. * Метрики (Силуэт, DB Index) — позволяют не гадать, а измерять качество работы.

Кластеризация — это искусство поиска порядка в хаосе. Теперь у вас есть полный набор инструментов, чтобы стать художником данных. Удачи в ваших исследованиях!