УДК 004

Быстрое автоматизированное определение субоптимальной кластеризации на основе метрики WCSS и алгоритма UIK

Тараторин Никита Сергеевич – магистрант Уфимского университета науки и технологий.

Прокудина Елена Ивановна – кандидат физико-математических наук, доцент Уфимского университета науки и технологий.

Аннотация: В эпоху больших данных кластеризация стала важным методом анализа данных, но ее эффективное применение часто ограничивается субъективностью в выборе оптимального разбиения. В данной работе продемонстрирован автоматизированный подход к определению оптимальной кластеризации методом k-means на основе метрики WCSS с помощью алгоритма UIK. На базе подхода представлен разработанный модифицированный алгоритм определения оптимального числа кластеров алгоритма k-means на основе тернарного поиска.

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

1. Введение

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

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

Создание эффективных моделей автоматической кластеризации, однако, остается сложной задачей. Это, в частности, связано с тем, что некоторые модели оцениваются нестрогими математическими критериями, как, например, квадрат внутриклассового расстояния (Within-Cluster Sum of Squares, WCSS). Согласно данной метрике, оптимальное разделение кластеров достигается в точке «локтя» графика функции оценки. В данной статье рассмотрен подход к автоматизации процесса кластеризации на примере алгоритма k-means с использованием метрики суммы квадратов внутрикластерных расстояний и алгоритма Unit Invariant Knee (UIK) для определения оптимального числа кластеров.

2. Постановка задачи

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

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

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

Таким образом задача разбиения множества точек  на группы в контексте данной работы сводится к определению точки «локтя» на графике WCSS. Сделать это можно за счёт специализированного алгоритма UIK.

Для более глубокого понимания изложенной далее информации приведем описание метрики WCSS.

Метрика WCSS – это метрика оценки качества кластеризации, основанная на сумме квадратов расстояний между точками кластеров и их центроидами [1].

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

где  ‒ множество точек, входящих в i-ый кластер.

(1)

Тогда метрика WCSS оценки данного разбиения принимает вид:

(2)

где  – евклидово расстояние между двумя точками.

В некоторых случаях на основе графика данной метрики можно эмпирически найти точку «локтя», однако это не всегда так. Ниже на рисунке 1 приведён пример графика метрики WCSS, рассчитанного для различных разбиений некоторых геномных данных на кластеры. По оси  отложено значение метрики WCSS, а по оси X – количество кластеров. Красным на графике помечено место предполагаемого нахождения точки «локтя».

Рисунок 1. Пример графика WCSS анализа качества разбиения групп клеток при транскриптомном анализе.

На эмпирическое восприятие графиков подобного рода влияет выбранный масштаб осей. В некоторых других задачах, где необходимо найти точку «локтя», важную роль может играть выбор единиц измерения. К тому же выбранные визуально разбиения вовсе могут не включать в себя оптимальное. Применительно к представленному выше графику оптимальное разбиение может содержать в себе 50, 100, и даже 1000 кластеров, а оценка таких разбиений не была проведена.

3. Алгоритм UIK

Для устранения субъективизма при выборе точки локтя предлагается использовать алгоритм UIK.

UIK – эвристический алгоритм поиска точки «локтя» или «колена» для дискретных данных. Первая работа, описывающая данный подход, опубликована в 2016 году [2].

Описание алгоритма приведено ниже.

1. Пусть задано облако  точек .
2. Проведём прямую от точки  до точки . Пусть функция прямой обозначается как .
3. Пусть  – множество точек, таких что:  и .
4. Точка «локтя»/«колена» определяется как точка глобального экстремума ломанной, проведённой через облако точек . В этом случае точка «локтя» – это глобальный минимум, точка «колена» – глобальный максимум.

Данный алгоритм на примере поиска «колена» может быть проиллюстрирован следующим образом (рисунок 2). На рисунке чёрным обозначена ломанная, проходящая через исходное множество точек; красным – прямая, проведённая через две крайние точки исходной ломанной; синим – функция, полученная посредством “вычитания” красной прямой из чёрной ломанной.

Рисунок 2. Графическое представление работы метода UIK.

Данный метод имеет следующие преимущества перед эмпирическим анализом графика:

• объективность и однозначность;
• инвариантность относительно линейных преобразований исходной системы координат облака точек.

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

4. Применение тернарного поиска для нахождения точки «локтя»

Тернарный поиск — это метод поиска экстремума (максимума или минимума) функции на заданном интервале. Предполагается, что функция унимодальна (имеет только один локальный максимум или минимум) на заданном интервале поиска.

Формальное описание шагов алгоритма представлено ниже.

1. Задается интервал поиска  для функции .
2. Определяются две точки  и  так, что . Обычно это делается путем разделения интервала на три равные части.
3. Вычисляются значения функции в точках  и :  и .
4. Если ищется максимум и если , то максимум функции не может находиться в интервале . Тогда интервал поиска обновляется и принимается равным . Если , то максимум функции не может находиться в интервале . В этом случае интервал поиска обновляется и принимается равным . Для поиска минимума рассуждения аналогичны, но отличаются знаком сравнения между значениями функции  в точках  и .
5. Шаги 2-4 повторяются до тех пор, пока длина рассматриваемого интервала не станет меньше заранее заданного .

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

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

Данная композиция подходов позволяет быстро найти достаточно хорошее решение, которое при всём прочем позволяет не запускать алгоритм кластеризации разбиения данных на все возможные количества кластеров (количество кластеров всегда лежит в интервале , где  – количество точек данных).

Если известен результат тернарного поиска  ( в данном контексте – количество классов), то для выбора действительно лучшего решения можно рассчитать метрику WCSS по разбиениям исходного множества точек на количество групп, лежащих в интервале , где  – некоторый радиус исследуемого интервала.

Таким образом асимптотическая сложность данного решения равна , где  – асимптотическая сложность алгоритма k-means,  – количество точек данных.

5. Численный эксперимент

Ниже проведён эксперимент над популярным набором данных mtcars. Решено опробовать вышеизложенный алгоритм кластеризации, разделив данные на группы на основе их параметров disp и qsec. Набор данных содержит 32 строки. Исходное множество точек представлено на рисунке 3.

Рисунок 3. Исходное множество точек.

Поскольку данный набор данных часто используется для экспериментов, существует несколько работ, в которых количество кластеров k-means’а выбирается на основе графика WCSS, приведённого на рисунке 4. Основываясь на этом графике, можно заключить, что количество кластеров равно 2.

Рисунок 4. WCSS для результата k-means при .

Ниже на рисунке 5 приведён график WCSS для .

Рисунок 5. WCSS для результата k-means при .

Как можно видеть, уже эмпирически стоит выбрать количество кластеров равно 3 или 4.

На рисунке 6 приведён результат расчёта ломанной, получаемой при UIK.

Рисунок 6. WCSS и UIK для результата kmeans при .

Точка экстремума достигается при количестве кластеров равному 3. Как можно видеть на графике, значения UIK при кластеризации на 3, 4 и 5 кластеров схожи, но результат однозначно идентифицируем.

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

Реализован прототип, в котором оптимальная кластеризация методом k-means определяется посредством нахождения точки максимума функции UIK тернарным поиском. Алгоритм также сошёлся к 3 кластерам. Однако для решения понадобилось лишь 14 запусков алгоритма k-means. Если ко всему прочему не вычислять k-means при одном и том же количестве кластеров дважды, применяя мемоизацию, то количество запусков k-means сокращается до 10.

Оптимальное разбиение представлено на рисунке 7.

Рисунок 7. Найденное оптимальное разбиение UIK’ом по метрике WCSS.

6. Выводы

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

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

1. Christopoulos D. Introducing Unit Invariant Knee (UIK) as an objective choice for elbow point in multivariate data analysis techniques //Available at SSRN 3043076. – 2016.
2. Hartigan J. A., Wong M. A. Algorithm AS 136: A k-means clustering algorithm //Journal of the royal statistical society. series c (applied statistics). – 1979. – Т. 28. – №. 1. – С. 100-108.