Клюковкин Г.К. Кластеризация пользователей с помощью K-Means и DBSCAN // Вестник Науки и Творчества. 2018. № 5(29). С. 36-42.

Статья: Клюковкин Г.К. 2018-05.pdf

Полный выпуск: Вестник Науки и Творчества. Выпуск №5 (2018).pdf

КЛАСТЕРИЗАЦИЯ ПОЛЬЗОВАТЕЛЕЙ

С ПОМОЩЬЮ K-MEANS И DBSCAN

Клюковкин Георгий Константинович,

специалист по актуарным расчётам и аналитике рисков,

Страховая компания «Капитал-Полис», г. Санкт-Петербург

E-mail: kliukovkin@gmail.com

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

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

Актуальность исследования

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

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

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

Таким образом, сравнение этих двух алгоритмов в контексте кластеризации пользователей – это актуальная задача, направленная на улучшение качества аналитики и принятия решений в цифровой среде.

Цель исследования

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

Материалы и методы исследования

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

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

Результаты исследования

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

Существует несколько основных типов алгоритмов кластеризации. К ним относятся иерархические методы, формирующие древовидную структуру (агломеративные и дивизивные), разделяющие методы (centroid-based), среди которых наиболее известен K‑Means, и плотностные методы, представленные DBSCAN. Кроме того, существуют фаззи‑кластеризация и модельно-ориентированные методы, такие как GMM [1].

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

Разделяющие методы (например, K‑Means) требуют предварительно известного числа кластеров, стремясь минимизировать внутрикластерную дисперсию.

Плотностные методы (DBSCAN) рассматривают плотные области как кластеры, отделённые низкоплотными пространствами, что позволяет обнаруживать произвольные формы кластеров и выявлять шум.

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

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

Таблица 1

Сравнительная характеристика метрик

внутренней и внешней оценки кластеризации

Алгоритм K‑Means – это один из классических методов кластеризации, относящийся к группе centroid‑based, где цель заключается в оптимальном делении наблюдений на K кластеров путём минимизации внутрикластерной дисперсии, выраженной как сумма квадратов расстояний точек до центроидов [3].

Формально задача записывается как:

, где ?_? – центр ?‑го кластера.

Алгоритм итеративный (разработан Ллойдом 1957-1962 гг., опубликован 1982 г.) и состоит из двух циклических шагов: сначала данные назначаются к ближайшему центроиду, затем центроиды пересчитываются как среднее внутри каждого кластера; процесс повторяется до сходимости (стабильность центрoидов или WCSS).

Главным преимуществом K‑Means является простота реализации и высокая скорость работы: сложность O (n · K · d · i), где n – число объектов, d – размерность, i – количество итераций. При этом общая задача NP‑трудна, но практические данные обычно приводят к быстрому сжатию WCSS.

Среди ограничений:

– Алгоритм чувствителен к выбору K, невозможность его заранее определить без эвристик. Часто используют метод локтя – визуальный анализ резкого перегиба кривой WCSS vs K (рисунок 1).

Рис. 1 Метод локтя для определения оптимального

количества кластеров в алгоритме K-Means

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

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

– Алгоритм плохо справляется с выбросами – они могут сильно смещать центроиды.

Алгоритм DBSCAN (Density‑Based Spatial Clustering of Applications with Noise) разработан в 1996 году Мартином Эстером, Хансом-Питером Кригелем, Йёргом Сандером и Сюй Сяовэй для кластеризации пространственных данных, содержащих шум [4]. В отличие от K‑Means, DBSCAN не требует заранее задавать число кластеров и позволяет вычленять структуры произвольной формы.

В основе алгоритма лежат два гиперпараметра: ε – радиус окрестности, и minPts – минимальное число точек, которое делает точку плотной. Точка классифицируется как «core», если в её ε‑соседстве находится по меньшей мере minPts точек; иначе она может стать «border»-точкой, если принадлежит ε‑соседству core‑точки. Все остальные – шум. Визуализация на рисунке 2 показывает core-, border- и noise‑точки в кластеризации.

Рис. 2 Иллюстрация работы алгоритма DBSCAN

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

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

Среди ограничений – необходимость подбора ε и minPts, чувствительность к масштабу и метрике, ограниченная способность при сильно различной плотности кластеров, и амбигуитет при распределении border‑точек.

Для выбора ε используют график k‑расстояний (k = minPts−1), где точка «локтя» служит ориентиром, как показано на примере в R-пакете dbscan. minPts обычно рассчитывается как minPts ≥ dim + 1, и часто miPts = 2·dim, чтобы обеспечить устойчивость при шуме

На практике DBSCAN часто превосходит K‑Means в задачах с данными произвольной формы, особенно при наличии плотностных сгустков и выбросов. Пример кластеризации «noisy moons» или «aggregation» демонстрирует устойчивость DBSCAN к шуму и сложной геометрии, о чём свидетельствуют результаты в R-библиотеке: кластеризация eps = 0.075, minPts = 10 успешно отделяет две формы даже при шуме.

Наконец, расширения алгоритма, такие как OPTICS и HDBSCAN*, призваны устранить ограничения гиперпараметров и неопределённости в border‑точках, а также создавать иерархические кластеры вместо «плоской» сегментации.

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

Таблица 2

Сравнительный анализ алгоритмов K-Means и DBSCAN

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

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

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

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

Одним из важных преимуществ DBSCAN является возможность выделения «аномальных» пользователей – тех, чьё поведение не вписывается в основные поведенческие паттерны. В контексте анализа оттока это может быть ключевым для раннего предупреждения потери клиента. При этом, в отличие от K-Means, DBSCAN хорошо работает с данными, где поведение неоднородно по плотности, например, с группами пользователей, отличающимися как по количеству действий, так и по глубине вовлечённости.

Выводы

Таким образом, выбор алгоритма кластеризации зависит от природы пользовательских данных. Если поведение пользователей достаточно однородно и хорошо аппроксимируется евклидовыми расстояниями, то K-Means может быть эффективен. В случаях же с разреженными, сложными и неструктурированными поведенческими данными, особенно в event-based системах, преимущество будет на стороне DBSCAN.

Анализ поведенческих данных с помощью этих алгоритмов требует обязательной подготовки: нормализация признаков, устранение мультиколлинеарности, а в случае DBSCAN – использование графиков k-distance для определения оптимального порога ε. Кластеризация в этой области становится всё более интегрированной с системами рекомендательных моделей, ML-сервисами персонализации и A/B‑тестированием пользовательского опыта.

Литература:

1. Кластеризация – scikit-learn 1.4.2 documentation [Электронный ресурс]. – Режим доступа: https://scikit-learn.ru/stable/modules/clustering.html.

2. Кластеризация [Электронный ресурс]. – Режим доступа: https://education.yandex.ru/handbook/ml/article/klasterizaciya.

3. K-Means Clustering Explained [Электронный ресурс]. – Режим доступа: https://neptune.ai/blog/k-means-clustering.

4. DBSCAN – scikit-learn 1.7.0 documentation [Электронный ресурс]. – Режим доступа: https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html.