ИЕРАРХИЧЕСКИЕ МЕТОДЫ КЛАСТЕРИЗАЦИИ В ЗАДАЧЕ ПОИСКА АНОМАЛЬНЫХ НАБЛЮДЕНИЙ НА ОСНОВЕ ГРУПП С НАРУШЕННОЙ СИММЕТРИЕЙ

з DOI 10.22394/1726-1139-2020-5-116-127

§ Иерархические методы кластеризации

Кисляков А. Н., Поляков С. В.*

° Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации (Владимирский филиал), г. Владимир, Российская Федерация; *svp2206@yandex.ru

РЕФЕРАТ

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

Для цитирования: Кисляков А. Н., Поляков С. В. Иерархические методы кластеризации в задаче поиска аномальных наблюдений на основе групп с нарушенной симметрией // Управленческое консультирование. 2020. № 5. С. 116-127.

Hierarchical clustering methods in a task to find abnormal observations based on groups with broken symmetry

Aleksey N. Kislyakov, Sergey V. Polyakov*

Russian Presidential Academy of National Economy and Public Administration (Vladimir Branch), Vladimir, Russian Federation; *svp2206@yandex.ru

ABSTRACT

The work is aimed at solving the actual problem of identification and interpretation of anomalous observations in the study of socio-economic processes. The proposed method is based on the use of a cluster approach to detecting anomalous observations. Clustering is performed using hierarchical methods, which are a set of data ordering algorithms aimed at creating dendrograms consisting of groups of observed points. In the case of mixed data consisting of numeric and categorical variables, it is proposed to use the Gower

distance as a metric for distances between elements. Clustering quality is evaluated based 3 on the sum of squares of metric distances between objects within the cluster and the J average width of the silhouette. These indicators allow you to select the optimal number o of clusters and evaluate the quality of the split results. The dendrogram can be used to ® study the symmetry groups of cluster systems and the causes of symmetry breaking. CL Anomaly detection is performed by analyzing the results of hierarchical clustering and ^ identifying branches of the dendrogram that are located at the initial levels of tree con- m struction and do not have branches. The implemented method makes it possible to more o accurately interpret the results of clustering with respect to determining errors of the first ^ and second kind in the form of anomalous observations

method, it is possible to effectively investigate socio-economic systems and manage their 0 development.

For citing: Kislyakov A. N., Polyakov S. V. Hierarchical clustering methods in a task to find abnormal observations based on groups with broken symmetry // Administrative consulting. 2020. No. 5. P. 116-127.

Введение

Круг задач, решаемых на основе перспективного анализа данных и прогнозного моделирования постоянно расширяется. На основе математических моделей возможна выработка рекомендаций и составление прогнозов показателей социально-экономического развития. Сам подход к использованию данных для принятия решений становится ключевым фактором экономического роста [6; 7]. Данные являются основой для построения прогнозных моделей и от их качества зависит результат принятия решений.

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

В этой связи на первый план выходит задача не только поиска, идентификации, но и интерпретации аномальных наблюдений. Так, например, визуальная оценка наличия таких наблюдений на диаграмме рассеяния не всегда дает однозначный ответ на вопрос является ли аномальным наблюдением данная точка. Еще сложнее обстоят дела, когда изучается поведение человека как составляющей социально-экономической системы на основе вектора признаков (факторов) на основе групп с нарушением симметрии [8; 10].

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

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

^ В этом понимании кластерные методы схожи с метрическими и статистически° ми методами [1; 15] поиска аномальных наблюдений, однако при более детальном о рассмотрении кластерные методы позволяют решить более широкий круг задач, д связанных с интерпретацией выявленных аномалий.

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

При исследовании реальных систем, объектов и их структур, изменяющихся в процессе развития, чаще, где это возможно, обращаются к математическим моделям, относящимся к алгебраическим структурам. Классификацию алгебраических структур можно построить на основе визуализаторов. Визуализатор — тип программного обеспечения, предназначенный для преобразования различной информации в зрительные образы. В качестве одного из результатов работы визуа-лизатора является дендрограмма [17], которая используется для представления результатов иерархической кластеризации. Дендрограмма может быть использована для исследования групп симметрии кластерных систем и причин нарушения симметрии [8; 9] (наличии, появлении аномальных наблюдений).

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

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

Исходными данными для проведения кластерного анализа служит матрица расстояний между объектами, сформированная с использованием той или иной метрики. Распространенная мера удаленности объектов друг от друга, используемая чаще всего — евклидово расстояние [11; 12].

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

Результат иерархической кластеризации представляется в виде дендрограм-мы [13; 14]. Для разбиения на кластеры также необходимо определить метод объединения, т. е. метод, который позволит выявить наиболее сильные связи между группами объектов и метрики разбиения.

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

В этом смысле методы иерархической кластеризации весьма схожи с методом з Isolation Forest («изолированный лес») [1], но не являются полностью идентичными. cl Суть алгоритма Isolation Forest состоит в том, что аномалию можно изолировать § с помощью меньшего количества случайных разделений по сравнению с образцом £ обычного класса, поскольку отклонения встречаются реже и не укладываются в об- s щую статистику имеющегося набора данных. °

Так, при «случайном» способе построения деревьев выбросы будут попадать о в «листья» (вершины ветвей дерева), т. е. выбросы проще «изолировать». Вы- g деление аномальных значений происходит на первых итерациях работы алго- ш ритма на небольшой глубине построения дерева — когда относительное расстояние между кластерами больше 0,5 [1; 16], потому как именно при этих значениях наблюдается выделение аномалий в отдельную ветвь. Вторым признаком аномалии является отсутствие дальнейшего разветвления этой ветви дерева.

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

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

Результаты

Рассмотрим в качестве примера возможность кластеризации тестовой базы данных, содержащей признаки поведенческой активности клиентов сети ресторанов быстрого питания. Тестовая выборка состояла из 100 клиентов (п = 100) и нескольких признаков. Пример выборки показан на рис. 1. Для программной реализации кластерных методов использовались пакетные функции: с1а^у(), сНапа(), с!ивр!о!() из библиотеки кластеризации на языке Я.

По сути данная выборка состоит из идентификатора сделки и нескольких показателей по каждому из признаков, характеризующих эти сделки [2; 3]. Каждая из сделок является вершиной сетевого графа («листья» дерева), а связи между этими вершинами характеризуются мерами схожести каждой пары сделок.

Идентификатор Q Доход с клиента □ Город □ Способ заказа □ День недели □ Тип продукта д

Рис. 1. Пример тестовой выборки Fig. 1. Example of test selection

В качестве метрики расстояний между элементами в случае смешанных данных, состоящих из числовых и категориальных переменных предлагается использовать расстояние Гауэра [11], которое при оценке сходства (различия) допускает, одновременное использование смешанных переменных (качественных и количественных), измеренных по различным шкалам

где — весовой коэффициент, принимающий значение 1, если сравнение объектов по признаку следует учитывать, и 0 — в противном случае; — вклад в сходство объектов, зависящий от того, учитывается ли признак при сравнении объектов I и ]. В случае бинарных признаков = 0, если признак отсутствует у одного или обоих сопоставляемых объектов. В итоге чем меньше расстояние Гауэра, тем лучше классификация отражает структуру данных. Эта метрика позволяет выстроить структуру дендрограммы.

На основе расстояния Гауэра вычисляется матрица отличий [4; 5], — таблица, заполненная в идеальном случае 0 и 1. Значение «0» означает отсутствие связи между признаками, значение «1» говорит об однозначной связи. Использование такой матрицы отличий позволяет реализовать основной принцип кластеризации: объединить в группы вершины, которые находятся ближе всего друг к другу, или разделить наиболее удаленные друг от друга. На рис. 2 приведены результаты такого разбиения и построены дендрограммы на основе агломеративного и дивизионного подхода.

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

о. >

CD ш О

О. >

Рис. 2. Результат дивизионной (а) и агломеративной (Ь) кластеризации Fig. 2. Result of divisional (a) and agglomerative (b) clustering

Для реализации высокого качества кластеризации необходимо, чтобы расстояние между точками внутри кластера (или компактность) было минимальным, а расстояние между группами (отделимость) — максимально возможным. Для этого необходимо выполнить расчет основных характеристик качества кластеризации: суммы квадратов метрических расстояний между объектами внутри кластера и среднюю ширину силуэта [12]. Особого пояснения требует показатель ширины силуэта, который для i-го объекта (вх) определяется соотношением

(bi > ai) ,

где ах — среднее расстояние между г-м объектом и всеми членами кластера, которому он принадлежит (если объект в кластере один, то ах = 0), Ьх — среднее расстояние между г-м объектом и членами другого ближайшего кластера (на практике рассчитывается среднее расстояние до членов всех остальных кластеров и выбирается минимум).

Ширина силуэта характеризует степень разброса принадлежности объектов к кластеру и может варьироваться от -1 до 1. Если она близка к единице, объект находится фактически в центре кластера и его принадлежность к нему не вызывает сомнений. Если ё% близко к нулю, объект лежит между двумя кластерами. Отрицательные значения вх свидетельствуют о, вероятно, неверной классификации объекта.

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

В данном случае (рис. 3) сумма квадратов расстояний между объектами внутри кластера не дает однозначных выводов о выборе количества кластеров. И в том и в другом случае логично предположить, что в данном наборе присутствует 8-10 кластеров.

Количество кластеров

Количество кластеров

Рис. 3. Сумма квадратов метрических расстояний между объектами внутри кластера для дивизионной (а) и агломеративной (b) кластеризации Fig. 3. Sum of squares of metric distances between objects within the cluster for divisional (a)

and agglomerative (b) clustering

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

" 0,24 — (0 I S Q. S

| 0,22-О

о 0,205 0,18 —

Рис. 4. Средняя ширина силуэта для дивизионной (а) и агломеративной (b) кластеризации Fig. 4. Average silhouette width for divisional (a) and agglomerative (b) clustering

Именно это количество и будет использоваться в дальнейшем при построении дендрограмм с разбиением на кластеры (рис. 5).

Дендрограмма (дивизионная), к= 8

номер элемента

Дендрограмма (агломеративная), к= 8

номер элемента

Рис. 5. Результаты иерархической кластеризации Fig. 5. Results of a hierarchical clustering

Обсуждение

Как видно из рис. 5, наиболее отличными от остальных ветвей дендрограммы являются ветви с наблюдением № 48 и № 68, которые начинаются на уровне большем и равном 0,5 и далее не разветвляются, тем не менее алгоритмы их определили к одному из кластеров. Также можно наблюдать, что оба метода кластеризации показывают различные результаты объединения, однако данные аномалии выделяются бесспорно в каждом их этих методов. Кроме того, при дивизионной кластеризации мы можем наблюдать ветвь, состоящую всего из четырех точек. Эти точки также можно считать аномальными второго рода, однако три из них имеют больше общих признаков.

Теперь для того чтобы оценить, как будет работать алгоритм, умышленно попытаемся внести изменения двух видов в исходный набор данных: сначала необоснованно увеличим показатель дохода от одной сделки при покупке одного из видов продукции — пусть, к примеру, это будет наблюдение № 15, затем заметено увеличим доходы с продаж напитков по субботам (таких наблюдений было немного, их номера: № 52, 53, 62, 63, 79, 89 и 91). Построим теперь дендрограммы и сравним результаты.

Рисунок 6 показывает, что при дивизионной кластеризации наблюдение № 68 уже не является аномальным, зато наблюдение № 48 выделено даже в отдельный кластер в виде одной точки. Кроме того, ожидаемо отнесено к аномалиям наблюдение и № 15. Следует также обратить внимание на наблюдение № 44, которое тоже отнесено к аномалиям. В свою очередь аномалии продаж напитков по субботам даже не выделены в отдельный кластер.

Дендрограмма (дивизионная), к= 8

номер элемента

Дендрограмма (агломеративная), к= 8

г| L jl Дп ГГ1 1

ГШ р. 1 j: п Гп "1 "Vi JL Гп

Ii ш all ¡1Д пяЛ №13 ш1Ш S=8" 4 Je* ssss ¡ssaesss

О 25 50 75 100

номер элемента

Рис. 6. Результаты кластеризации с аномальными наблюдениями Fig. 6. Results of clustering with abnormal observations

Если рассматривать результат агломеративной кластеризации, то легко заметить, что здесь даже наблюдение № 48 уже не является аномальным, как, впрочем, и наблюдение № 68. Однако наблюдение № 15 по-прежнему относится к аномальным, кроме этого наблюдения больше не существует ветвей без дальнейшего деления на уровне построения дерева более или равном 0,5. Часть аномальных наблюдений (продажи напитков по субботам — ошибки второго рода) с номерами 52, 62, 91 отнесены к одному кластеру, но не определены как аномалии.

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

Выводы

Результаты анализ дендрограмм позволяет сделать выводы.

Литература

-О зоопланктона реки Линда Нижегородской области) // Биология внутренних вод. 2016.

g № 2. С. 94-103.

о 12. Alboukadel K. Practical Guide to Cluster Analysis in R. Unsupervised Machine Learning 2 (Multivariate Analysis). Vol. 1. 1st ed. / Publisher: CreateSpace Independent Publishing Platform,

T* 13. Murtagh F., Contreras P. Methods of Hierarchical Clustering // Computing Research Repository — 2 CORR, 2011.

о 14. Nielsen F. Introduction to HPC with MPI for Data Science // Springer International Publishing, ^ 2016.

ш 15. Gareth J., Witten D., Hastie T., Tibshirani R. An Introduction to Statistical Learning with ° Applications in R / Publisher: Springer, 2013.

Об авторах:

Кисляков Алексей Николаевич, доцент кафедры информационных технологий Владимирского филиала РАНХиГС (г. Владимир, Российская Федерация), кандидат технических наук; ankislyakov@mail.ru

Поляков Сергей Владимирович, доцент кафедры информационных технологий Владимирского филиала РАНХиГС (г. Владимир, Российская Федерация), кандидат технических наук; svp2206@yandex.ru

References

under general ed. of A. I. Novikov and A. E. Illarionov. Vladimir : RANEPA Vladimir branch, 2018. _o P. 236-244. (In rus) J

About the authors:

Aleksey N. Kislyakov, Associate Professor of the Chair of Information Technology of Vladimir Branch of RANEPA (Vladimir, Russian Federation), PhD in Technical Science; ankislyakov@mail.ru

Sergey V. Polyakov, Associate Professor of the Chair of Information Technology of Vladimir Branch of RANEPA (Vladimir, Russian Federation), PhD in Technical Science; svp2206@yandex.ru