Кластеризация в машинном обучении: 5 ключевых алгоритмов кластеризации

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

Интуиция, лежащая в основе кластеризации

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

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

Ключевые критерии успеха анализа кластеризации

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

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

Ключевые критерии успеха моделей кластеризации сводятся к следующему:

• Насколько это интерпретируемо?
• Полезен ли результат кластеризации для бизнеса?
• Удалось ли узнать новое или обнаружить ранее неизвестные шаблоны в данных?

Измерение качества кластеризации

Без разметки нельзя посчитать accuracy или AUC. Две метрики помогают количественно оценить, насколько хорошо ваши кластеры разделены. Два распространённых показателя:

• Silhouette Score измеряет, насколько точка похожа на свой кластер по сравнению с ближайшим соседним кластером. Диапазон от -1 до 1; значения выше 0,5 говорят о хорошо разделённых кластерах.
• Индекс Дэвиса—Булдина измеряет среднюю схожесть каждого кластера с наиболее похожим на него кластером — меньше значит лучше.

Обе метрики доступны в scikit-learn: sklearn.metrics.silhouette_score(X, labels) и sklearn.metrics.davies_bouldin_score(X, labels).

1. K-Means

K-Means — самый широко используемый алгоритм для задач кластеризации, во многом потому, что его шаги легко понять, а реализация в scikit-learn проста. Это центроид-ориентированный алгоритм, в котором пользователь должен задать требуемое число кластеров. 

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

K-Means — итеративный алгоритм, создающий непересекающиеся кластеры: каждая запись в наборе данных может принадлежать только одному кластеру. Проще всего понять интуицию K-Means, разобрав шаги по примеру на диаграмме ниже. Подробности есть и в наших руководствах K-Means на Python и K-Means на R. 

1. Пользователь задаёт число кластеров.
2. Инициализируются центроиды случайно по числу кластеров. На схеме ниже на Итерации 1 видно три случайно инициализированных центроида синего, красного и зелёного цветов.
3. Вычисляются расстояния между точками данных и каждым центроидом, и каждая точка назначается ближайшему центроиду.
4. Пересчитывается среднее центроида по всем назначенным точкам, и его положение меняется, как видно на Итерациях 2–9, пока алгоритм не сойдётся.
5. Итерации продолжаются, пока среднее центроида не перестанет меняться, либо пока не будет достигнут параметр max_iter — максимум итераций, заданный пользователем при обучении. По умолчанию в scikit-learn max_iter равен 300.

Источник изображения: Learnbymarketing.com

2. MeanShift

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

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

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

Поэтому MeanShift также называют алгоритмом поиска мод. Шаги MeanShift следующие:

• Выберите случайную точку и создайте вокруг неё окно.
• Вычислите среднее всех точек внутри окна.
• Сместите окно в направлении моды. 
• Повторяйте до сходимости.

Источник изображения: ResearchGate

Пошаговую практику работы с MeanShift смотрите в нашем руководстве по Mean Shift Clustering.

3. DBSCAN

DBSCAN, или Density-Based Spatial Clustering of Applications with Noise, — алгоритм кластеризации без учителя, основанный на предпосылке, что кластеры — это области с высокой плотностью, разделённые областями с меньшей плотностью. 

Главное преимущество алгоритма перед K-Means и MeanShift — устойчивость к выбросам: он не включает выбросы ни в один кластер. 

Алгоритм DBSCAN требует от пользователя лишь два параметра: 

• Радиус окружности вокруг каждой точки данных, также называемый epsilon

• minPoints — минимальное число точек внутри этой окружности, чтобы точка была признана ядровой (Core).

Каждую точку окружают окружностью радиуса epsilon, и DBSCAN классифицирует точки как ядровые (Core), граничные (Border) или шум (Noise). Точка считается ядровой, если окружность вокруг неё содержит не менее minPoints. 

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

Распространённые кейсы применения DBSCAN:

• Отлично разделяет кластеры высокой и низкой плотности;
• Хорошо работает на нелинейных наборах данных;
• Подходит для обнаружения аномалий, поскольку отделяет шумовые точки и не относит их к кластерам.

DBSCAN vs K-Means

Сравнивая DBSCAN с K-Means, основные различия таковы: 

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

Подробнее — в нашем руководстве по алгоритму DBSCAN с настройкой параметров и примерами. 

Источник изображения: Medium

4. Иерархическая кластеризация

Иерархическая кластеризация — это метод, который строит иерархию кластеров. Различают два типа. 

• Агломеративная: нисходящий подход снизу вверх, где поначалу каждое наблюдение — это свой кластер, а по мере подъёма от низа к верху наблюдения объединяются попарно, а пары — в кластеры. 
• Делящая: «сверху вниз»: все наблюдения начинают в одном кластере, и по мере движения сверху вниз выполняются рекурсивные разбиения.

При анализе данных социальных сетей иерархическая кластеризация — один из самых распространённых и популярных методов. Узлы (ветви) графа сравниваются друг с другом по степени сходства. Объединяя более мелкие связанные группы узлов, формируют более крупные группировки.

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

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

Источник изображения: ResearchGate

5. BIRCH

BIRCH расшифровывается как Balanced Iterative Hierarchical Based Clustering. Его используют на очень больших наборах данных, где K-Means практически не масштабируется. Алгоритм BIRCH делит большие данные на небольшие кластеры и старается сохранить максимум информации. Затем небольшие группы кластеризуются для получения финального результата вместо прямой кластеризации всего большого набора. 

BIRCH часто используют в связке с другими алгоритмами кластеризации, формируя сводку информации, которую те могут использовать. Пользователь должен задать число кластеров для обучения BIRCH так же, как в K-Means.

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

Самый частый кейс для BIRCH — это экономичная по памяти альтернатива K-Means для кластеризации больших наборов, которые нельзя обработать K-Means из-за ограничений памяти или вычислений.

Бизнес-применения кластеризации

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

Сегментация клиентов

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

Представьте, что у вас 10 млн клиентов, и вы хотите создать персонализированные или сфокусированные кампании. Вряд ли вы будете делать 10 млн кампаний — что тогда? Можно применить кластеризацию, сгруппировать 10 млн клиентов в 25 кластеров и разработать 25 кампаний вместо 10 млн.

Источник изображения: Medium

Ритейловая кластеризация

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

Другой пример — кластеризация на уровне категорий. На диаграмме ниже восемь магазинов. Разные цвета — разные кластеры. В этом примере их четыре. 

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

Источник изображения: dotactiv.com

Кластеризация в клинической практике / управлении заболеваниями

В здравоохранении и клинической науке особенно много применений кластеризации. Один из примеров — исследование Komaru & Yoshida et al., 2020: были собраны демографические и лабораторные данные для 101 пациента и выполнена сегментация на 3 кластера. 

Каждый кластер характеризовался разными состояниями. Например, кластер 1 — пациенты с низкими WBC и CRP. Кластер 2 — пациенты с высокими BMP и сывороткой, кластер 3 — с низкой сывороткой. Каждый кластер имеет свою траекторию выживаемости при годичной смертности после гемодиализа.

Источник изображения: elsevierhealth.com

Сегментация изображений

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

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

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

В библиотеке scikit-learn, популярной библиотеке машинного обучения на Python, реализовано 10 алгоритмов кластеризации без учителя. Между ними есть фундаментальные различия в том, как они определяют и назначают кластеры в наборе данных. 

Различия в математической природе этих алгоритмов сводятся к четырём аспектам, по которым их можно сравнивать:

• Требуемые параметры модели 
• Масштабируемость 
• Сценарии использования 
• Геометрия, то есть метрика расчёта расстояний. 

На схеме ниже каждый столбец — это результат разного алгоритма кластеризации: K-Means, Affinity Propagation, MeanShift и т. д. Всего 10 алгоритмов, обученных на одном наборе данных.

Некоторые алгоритмы дали одинаковые результаты. Обратите внимание: Agglomerative Clustering, DBSCAN, OPTICS и Spectral Clustering выделили одинаковые кластеры. 

Однако, сравнив результаты K-Means и MeanShift, видно, что они различаются. В случае K-Means — только две группы (синяя и оранжевая), тогда как у MeanShift — три: синяя, зелёная и оранжевая. 

Источник изображения: scikit-learn

К сожалению (или к счастью), в кластеризации нет однозначно верных или неверных ответов. Было бы просто заявить: «Алгоритм X показывает здесь лучший результат». 

Это невозможно, и именно поэтому кластеризация — очень нетривиальная задача. 

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

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

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

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

Заключение

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

Кластеризация — ценный навык для разных ролей: дата-сайентистов, ML-инженеров и аналитиков, — все они сталкиваются с задачами, которые она помогает решать. 

Если вы хотите глубже изучить кластеризацию и обучение без учителя и научиться реализовывать их на Python и R, эти курсы помогут вам продвинуться: 

• Cluster Analysis in Python
• Cluster Analysis in R
• Unsupervised Learning in Python
• Unsupervised Learning in R