Determining the optimal number of clusters when identifying neighborhood models

Full Text

Введение

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

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

Для оценки качества и компактности кластеров используются четыре индекса качества кластеризации: индексы Xie-Beni, Fuzzy Simplified Silhouette, Kwon, Tang-Sun-Sun [4-5].

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

Все расчеты были выполнены в программе, реализованной на языке программирования Python.

Исходные данные

Рассмотрим окрестностную модель (ОМ) вида «вход-выход», которую можно описать как  где:

 – это структура окрестностной модели, где  – множество узлов,  – множество окрестностных связей;

 – векторы входов и выходов ОМ в текущий момент времени;

− функция пересчета выходов.

Общий вид функции  для узла  окрестностной модели описывается формулой:

 

где  – количество окрестностных связей по выходам,  – количество окрестностных связей по входам для узла , .

Общий вид системы представлен формулой:

 

В работе рассматривается квадратичная окрестностная модель с одним узлом (рис. 1).

 

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

Частный случай системы (2) общего вида для рассматриваемой модели представлен формулой: 

 

 В квадратичном случае формула (3) имеет вид:

 

 

где  – параметры модели.

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

 

Таблица 1. Фрагмент выборки исходных данных

0,598	9,292	3,568
3,092	4,317	0,516
1,839	7,348	8,554
3,235	4,906	0,560
2,545	5,088	2,727
5,179	8,268	7,818
8,311	2,487	3,686
2,145	8,680	7,115
6,795	1,304	0,777
…

 

Данные были разделены на обучающую и тестовую выборки, в отношении 80 % на 20 % соответственно.

Определение оптимального количества кластеров

В работе использовался один из наиболее известных методов кластеризации – метод нечетких C-средних [6]. К недостаткам метода можно отнести необходимость задания количества кластеров . На практике не всегда известно, на какое оптимальное количество кластеров нужно разделить данные [7]. Задание неправильного  может привести к перекрывающим кластерам или к случаю, когда точки слишком удалены от центров кластеров [8-10]. Часто используемым подходом к выбору оптимального  является перебор различного количества кластеров и последующий выбор конкретного количества, которое обеспечивает наилучший результат в соответствии с определенным критерием качества.

В статье рассмотрены четыре индекса оценки качества кластеризации: Xie-Beni, Fuzzy Simplified Silhouette, Kwon, Tang-Sun-Sun.

В индексе Xie-Beni компактность и обособленность кластеров измеряются с использованием внутрикластерных отклонений и межкластерного расстояния [11]:

 

Меньшие значения индекса указывают на компактные и хорошо разделенные кластеры [12].

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

 

где  — расстояние между объектом  и ближайшим кластером-прототипом , к которому  принадлежит наибольшей степенью принадлежности, а  — расстояние между объектом  и вторым ближайшим кластером-прототипом.

Индекс Fuzzy Simplified Silhouette представляет собой нечеткую версию упрощенного силуэта [13]:

 

 

где  и  — первый и второй по величине элементы i-ой строки матрицы нечеткого разбиения, соответственно,

       — весовой коэффициент, определяемый пользователем.

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

Индекс Kwon представляет собой модификацию Xie-Beni и определяется как [14]:

 

 

где

Аналогично индексу Kwon, индекс Tang-Sun-Sun является модификацией индекса Xie-Beni [15]:

 

 

где  — это показатель минимизации.

 

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

 

Таблица 2. Результаты оценки качества кластеризации

Кол-во кластеров	Xie-Beni	Fuzzy Simplified Silhouette	Kwon	Tang-Sun-Sun
2	0,276	0,577	2767,073	2701,334
3	0,119	0,623	1196,173	1180,915
4	0,083	0,646	829,503	820,234
5	0,145	0,610	1454,343	1425,661
6	0,107	0,634	1071,278	1054,032
7	0,118	0,630	1191,861	1169,682
8	0,085	0,632	861,326	847,827
9	0,074	0,641	741,679	730,504
10	0,102	0,637	1029,890	1009,102

Как видно из табл. 2, в случае девяти кластеров получены оптимальные значения для индексов минимизации, то есть получаются компактные и хорошо разделенные кластеры. Самый неудовлетворительный результат получен при двух кластерах. В случае с индексом Fuzzy Simplified Silhouette наилучший результат получен при разделении выборки на четыре кластера.

 

Сравнение результатов кластеризации

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

 

Таблица 3. Центры кластеров

Количество кластеров
2		4		9
3,163	3,600	2,568	7,514	4,955
6,870	6,304	7,590	7,595	8,483	8,473
		2,396	2,451	1,685	8,296
		7,533	2,492	5,134	8,482
				8,457	1,714
				5,217	1,616
				1,676	4,563
				1,634	1,395
				8,338	4,955

На рис. 2-4 представлены результаты кластеризации тестовой выборки с разным количеством кластеров.

Рис. 2. Результаты кластеризации с

Рис. 3. Результаты кластеризации с

Рис. 4. Результаты кластеризации с

Идентификация окрестностной модели

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

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

 

   – объем выборки.

Матрицу параметров  находим по формуле

 

 

где  – псевдообратная матрица .

Для поиска ошибок идентификации необходимо получить модельные значения функции пересчета состояния  по формуле (7) для найденных параметров  и сравнить с исходными данным  Для нахождения среднеквадратичной ошибки (MSE) используется формула (8).

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

В табл. 4 приведены ошибки прогноза до и после кластеризации при разном количестве кластеров.

 

Таблица 4. Ошибки прогноза

Наименование ошибки	До кластеризации	После кластеризации
		2 кластера	4 кластера	9 кластеров
MSE	6,661	6,346	5,881	2,308

Ниже представлены графики значений  и  для тестовой выборки до и после кластеризации (рис. 5-8), а также графики ошибок прогноза до и после кластеризации (рис. 9).

Рис. 5. График  и  для тестовой выборки до кластеризации

Рис. 6. График  и для тестовой выборки при двух кластерах

Рис. 7. График  и  для тестовой выборки при четырех кластерах

Рис. 8. График  и  для тестовой выборки при девяти кластерах

Рис. 9. График MSE прогноза при разном количестве кластеров

Из рис. 5-9 видно, что для рассматриваемой выборки оптимальным является четыре кластера, что и было получено в результате исследования качества кластеризации по индексу Fuzzy Simplified Silhouette. Ошибка MSE прогноза при этом составила 5,881. Время выполнения расчетов 28,04 секунды.

Конечно, можно выбрать для построения модели и девять кластеров, как показывают индексы минимизации. При этом ошибка MSE прогноза уменьшается приблизительно в 2,5 раза и составила 2,308, что является существенным в некоторых исследованиях. Однако разбиение на большее количество кластеров требует дополнительных вычислительных и временных ресурсов. Здесь время выполнения расчетов составило 285,38 секунд. Поэтому при определении оптимального количества кластеров при решении задачи идентификации следует учитывать допустимую точность прогноза и времени вычислений.

Заключение

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

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

___________________________

© Седых И.А., Макаров К.Н., 2025

About the authors

Irina A. Sedykh

Lipetsk State Technical University

Author for correspondence.
Email: kirik0-1@yandex.ru
ORCID iD: 0000-0003-0012-8103

Dr. Sc. (Technical), Associate Professor

Russian Federation, 30 Moskovskaya St., Lipetsk, 398055, Russia

Kirill N. Makarov

Lipetsk State Technical University

Email: kirik0-1@yandex.ru
ORCID iD: 0009-0008-9556-7910

graduate student

Russian Federation, 30 Moskovskaya St., Lipetsk, 398055, Russia

References

Supplementary files