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

Введение. В современной инженерной и научно-технической практике многокритериальная оптимизация часто обеспечивает поиск компромиссных решений без задания весовых коэффициентов и границ, формируя Парето-фронт посредством эвристической аппроксимации на основе генетических алгоритмов. Однако даже аппроксимированный Парето-фронт представляет собой множество точек, что затрудняет анализ и отбор решений. Для упорядочения и структурирования полученных решений возможным решением становится кластеризация, позволяющая выделить репрезентативные группы компромиссов. Научная новизна предлагаемого метода кластеризации заключается в комбинации алгоритмов Ordering Points to Identify the Clustering Structure и k-means с выделением медоидов, обеспечивающей автоматическое удаление шума и компактное представление репрезентативных стратегий. 
Метод. Предложен метод двухэтапной кластеризации. На первом этапе применен алгоритм Ordering Points to Identify the Clustering Structure, с помощью которого строится упорядоченный профиль плотности и автоматически фильтруются шумовые точки по порогу досягаемости. На втором этапе использован алгоритм k-means, выполнено разбиение отфильтрованного ядра Парето-фронта на кластеры и вычислены центроиды, а затем медоиды — реальные представители данных. 
Основные результаты. Проведены два эксперимента на трехмерных множествах точек Парето-фронта (1226 и 2514 ядровых точек после фильтрации). В результате применения предложенной методики получено разбиение на 10 кластеров. Установлено, что после фильтрации доля шумовых точек составила менее 1 % от общего числа решений. Фильтрация позволяет существенно снизить значения метрики, оценивающей качество центров кластеров, при умеренном увеличении суммарного времени выполнения кластеризации. Показано, что малая рассогласованность центроидов и соответствующих медоидов свидетельствует о высокой репрезентативности полученных кластеров. 
Обсуждение. Предложенный комбинированный метод, сочетающий применение алгоритмов Ordering Points to Identify the Clustering Structure и k-means, требует настройки двух параметров, автоматически адаптируется к нелинейным плотностям и размерам входных данных. Область применения метода может быть расширена для любых задач многокритериальной оптимизации, решаемых посредством построения и анализа Парето-фронта, включая инженерную оптимизацию, логистику, энергетику и финансовое моделирование. В перспективе возможно внедрение адаптивных методов для автоматического определения оптимальных параметров используемых алгоритмов, а также обеспечения адаптации к динамическим изменениям многокритериальных задач.

1. Зак Ю.А. Множество Парето для критериев эффективности, представленных стохастическими и нечеткими данными // Искусственный интеллект и принятие решений. 2014. № 2. С. 89–101.

2. Ногин В.Д. Множество и принцип Парето: Учебное пособие. СПб: Издательско-полиграфическая ассоциация высших учебных заведений. 2022. 110 с.

3. Брестер К.Ю., Становов В.В., Семенкина О.Э., Семенкин Е.С. О применении эволюционных алгоритмов при анализе больших данных // Искусственный интеллект и принятие решений. 2017. № 3. С. 82–93.

4. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. 340 p.

5. Zitzler E., Deb K., Thiele L. Comparison of multiobjective evolutionary algorithms: empirical results // Evolutionary Computation. 2000. V. 8. N 2. P. 173–195. https://doi.org/10.1162/106365600568202

6. Ватутин Э.И. Решение дискретных комбинаторных оптимизационных задач с использованием эвристических методов: методические указания по выполнению лабораторных и практических работ по дисциплине «Основы комбинаторной оптимизации». Курск: Юго-Западный государственный университет, 2016. 30 с.

7. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: ФИЗМАТЛИТ, 2010. 368 с.

8. Вирсански Э. Генетические алгоритмы на Python. М.: ДМК Пресс, 2020. 286 с.

9. Everitt B.S., Landau S., Leese M., Stahl D. Cluster Analysis. John Wiley & Sons, 2011. 346 p.

10. Клинов Д.А., Григорян К.А. Разработка методики сегментации пользователей с помощью алгоритмов кластеризации и расширенной аналитики // Электронные библиотеки. 2022. Т. 25. № 2. С. 137–147. https://doi.org/10.26907/1562-5419-2022-25-2-137-147

11. Бондаренко И.Б., Гатчин Ю.А., Гераничев В.Н. Синтез оптимальных искусственных нейронных сетей с помощью модифицированного генетического алгоритма // Научно-технический вестник информационных технологий, механики и оптики. 2012. № 2 (78). С. 51–55.

12. Барсегян А.А. Анализ данных и процессов. СПб: БХВ-Петербург, 2009. 512 с.

13. Семериков А.В., Глазырин М.А. Кластеризация студентов университета иерархическим и KMeans методами // ИТ Арктика. 2021. № 3. С. 41–58.

14. Кисляков А.Н., Поляков С.В. Иерархические методы кластеризации в задаче поиска аномальных наблюдений на основе групп с нарушенной симметрией // Управленческое консультирование. 2020. № 5 (137). С. 116–127. https://doi.org/10.22394/1726-1139-2020-5-116-127

15. Иванов А.А. Кластеризация данных на основе марковской цепи с помощью алгоритма DBSCAN // Новые информационные технологии в автоматизированных системах. 2018. № 21. С. 315–319.

16. Трушкова К.Н., Калайда В.Т. Кластеризация спутниковых изображений облачных полей на основе алгоритма DBSCAN // Известия вузов. Физика. 2013. Т. 56. № 8-3. С. 356–358.

17. Murphy K.P. Machine Learning: A Probabilistic Perspective. The MIT Press, 2012. 1104 p.

18. Гарафиев И.З., Гарафиева Г.И. Кластеризация вакансий инженеров: методы K-средних и модель гауссовой смеси // Управленческий учет. 2024. № 9. С. 234–240.

19. Chung F.R.K. Spectral Graph Theory. American Mathematical Society, 1997. 207 p.

20. Баринов А.Е., Захаров А.А., Жизняков А.Л. Алгоритм спектральной кластеризации с ограничениями для выделения лица человека на изображениях // Динамика систем, механизмов и машин. 2016. № 4. С. 222–228.

21. Пылов П.А., Протодьяконов А.В. Спектральная кластеризация для сегментации изображения // Инновации. Наука. Образование. 2020. № 23. С. 274–277.

22. Han J., Kamber M., Pei J. Data Mining: Concepts and Techniques. Morgan Kaufmann, 2011. 744 p.

23. Ankerst M., Breunig M.M., Kriegel H.P., Sander J. OPTICS: ordering points to identify the clustering structure // Proc. of the 1999 ACM SIGMOD International Conference on Management of Data. 1999. P. 49–60. https://doi.org/10.1145/304182.304187

24. Попова О.А. Анализ и выбор метода кластеризации для текстовых документов короткой длины с целью реализации в модуле рекомендательной системы вуза // XXI век: итоги прошлого и проблемы настоящего плюс. 2023. Т. 12. № 4 (64). С. 89–102.

25. Юртаев А.Г., Степанов М.Ф. Решение задачи выбора компонентной базы при проектировании электронных блоков авионики // Математические методы в технологиях и технике. 2025. № 2. С. 170–174.