КОМБИНАЦИЯ АЛГОРИТМОВ K-СРЕДНИХ И DBSCAN ПРИ АНАЛИЗЕ ПОВЕДЕНИЯ ПОЛЬЗОВАТЕЛЕЙ

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

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

Кластеризация

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

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

Прикладная наука также активно использует кластерный анализ. Например, в вычислительной биологии этот метод машинного обучения активно применяется для обнаружения групп генов, демонстрирующих сходное поведение. Это может служить указанием на то, что они будут одинаково реагировать на лечение или что они образовались на одном пути биологического развития [3].

Классификация алгоритмов кластеризации

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

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

Также имеет место классификация методов по количеству применений алгоритмов кластеризации: одноэтапная или многоэтапная кластеризация; по возможности расширения объема обрабатываемых данных: масштабируемые и немасштабируемые; по времени выполнения кластеризации: потоковые и не потоковые.

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

Метод k-средних

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

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

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

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

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

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

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

Рисунок 1. Пример дендрограммы

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

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

Также необходимо упомянуть про другой метод включении нового объекта – метод Уорда. Этот подход позволяет минимизировать дисперсию внутри всех кластеров. Метод Уорда наиболее уместен для анализа социологических данных [2]. Применение данной методологии оптимально для вычленения кластеров приблизительно равных размеров и имеющих гиперсферическую форму.

Число кластеров, как правило, определяется из предположений, не относящихся к работе алгоритмов, например, по динамике изменения порога слияния кластеров. Поэтому на данный момент в иерархических алгоритмах определение числа кластеров уже не актуальная задача, она замещается построением дендрограммы. При этом, представление результатов в таком виде позволяет получить наиболее полное представление о структуре кластеров [1].

Алгоритм DBSCAN

DBSCAN (Density-based spatial clustering of applications with noise) – молодой алгоритм кластеризации, представленный в 1996 году [4]. В отличие от метода k-средних, этот не требует указания количества кластеров и может находить произвольное их количество. Также от рассмотренных выше алгоритмов этот вариант отличает возможность найти кластеры различного типа – главное, чтобы точки находились рядом. На вход необходимо передать два параметра: радиус окрестности и количество соседей m.

Простое описание алгоритма:

1. Найти во всем множестве элементов такой, у которого в радиусе окрестности находится не менее m других объектов (назовем эти точки соседями). Создать кластер с ним. Добавить в список обхода все элементы в выбранном радиусе окрестности.
2. Для каждого объекта из списка обхода проверить, есть ли у него в радиусе окрестности не менее m элементов. Если требование выполнено, то необходимо добавить этот элемент в кластер, а его соседей в список обхода.
3. Если список обхода пуст, то формирование текущего кластера завершено.

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

Этот алгоритм применяется при необходимости идентифицировать группы необычной формы. Способен хорошо находить шумы и выбросы.

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

Наглядное сравнение алгоритмов кластеризации

На рис. 2 приведены разбиения четырёх типов выборок вышеописанными алгоритмами. По строкам представлены четыре множества объектов с различным взаимным расположение. В столбцах: k-средних, агломеративная группировка с разбиением методом одиночной связи, агломеративная с методом Уорда и DBSCAN. Цифры в углу каждого из квадратов показывает время, затраченное на нахождение результатов.

Рисунок 2. Примеры разбиения различных выборок

Алгоритм k-средних хорошо и быстро делит выборки, состоящие из гиперсферических групп (строки 1-3), у которых точки разбросаны около некоторого центра. Проблемой является работы с выборками необычной формы (строка 4).

Результаты работы агломеративного иерархического алгоритма с методом одиночной связи похожи на результаты выполнения k-средних. При этом иногда допускают серьезные промахи, как, например, в строках 2 и 3. Например, шумы определяются в отдельные единичные группы. Выбросы и другие помехи значительно влияют на результаты работы метода. Также отметим долгое время работы.

Агломеративная кластеризация Уорда показывает более хорошую картину. Влияние шумов не так велико, поэтому выборки в строках 1-3 были успешно разбиты на три сферические группы. В четвертой строке заметно сходство с уже разобранными выше методами.

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

Использование k-средних и DBSCAN для анализа поведения пользователей

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

Для демонстрации работоспособности этого подхода использован сгенерированный набор метрик поведения пользователей в системе управления проектами небольших групп по примеру сайта trello.com. Использование подразумевает регистрацию, вход в аккаунт, открытие главной страницы, досок с карточками, создание карточек и т.д. При генерации этого набора были заданы два типа пользователей: корпоративные и персональные. Первый тип пользуется сервисом активно в будние дни, почти не использует в выходные, создаёт много событий. Второй использует приложение для личных нужд каждый день недели, но в заметно меньшем объеме. Этот набор метрик включает события 546 пользователей в течение нескольких недель.

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

После кластеризации алгоритмом k-средних на исходных данных (рис. 3) получили выборку, разбитую на две группы. Они легко идентифицируемы: большая группа точек слева и маленькая справа.

Кластер номер 1 состоит только из корпоративных пользователей количеством 361. Номер 2 состоит из 185, 37 из которых являются корпоративными, а остальные – персональными. Соответственно, в группе персональных долю в 20% составляют посетители другого типа, что влияет на конечный результат. Эти 37 пользователей – точки на рисунке, находящиеся между кластерами. Такое местоположение этих точек объясняется какими-либо аномалиями.

Рисунок 3. Алгоритм k-средних на исходных данных

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

Рисунок 4. Результаты алгоритма DBSCAN

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

Теперь следует применить k-средних на отфильтрованном наборе. Первый кластер состоит только из корпоративных пользователей – их 288. Второй состоит из 154 посетителей, 11 из которых являются корпоративными, а остальные – персональными. Таким образом, количество выбросов сократилось до 7 %. Результаты можно увидеть на рис. 5.

Рисунок 5. Алгоритм k-средних на отфильтрованных данных

Выводы

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

Проведение анализа поведения пользователей при помощи комбинации алгоритмов k-средних и DBSCAN показало, что совместное их использование помогает эффективно и качественно проводить поведенческий анализ.

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

Список литературы:

1. Барсегян А. А. Анализ данных и процессов: учеб. пособие. / А. А. Барсегян, М. С. Куприянов, И. И. Холод, М. Д. Тесс, С. И. Елизаров. – 3-е изд., перераб. и доп. – СПб.: БХВ-Петербург, 2009. – 167 с.
2. Кластерный анализ [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org/wiki/Кластерный_анализ/. – Дата доступа: 03.05.2019.
3. Сегаран. Т. Программируем коллективный разум. / Сегаран. Т. – Пер. с англ. – СПб: Символ-Плюс, 2008. – 50-51 с.
4. Ester, M., Kriegel, H. P., Sander, J., & Xu, X. A density-based algorithm for discovering clusters in large spatial databases with noise. / Ester, M., Kriegel, H. P., Sander, J., & Xu, X. // KDD. – 1996. – Vol. 96, №34 – P. 226-231.