Informacionnye TehnologiiInformacionnye TehnologiiИнформационные технологии1684-6400New Technologies Publishing House70211610.17587/it.31.235-242Modeling and optimizationМоделирование и оптимизацияResearch ArticleSimulation modeling of the clustering problem solution using the Mean Shift methodИмитационное моделирование решения задачи кластеризации методом сдвига среднего значенияSalibekyanS. M.СалибекянС. М.
Russian Federation

Cand. Sc., Assistant Professor

канд. техн. наук, доц.

ssalibekyan@hse.ruNational Research University Higher School of EconomicsНациональный исследовательский университет Высшая школа экономики150520253152352420302202603022026Copyright ©; 2025, Informacionnye TehnologiiCopyright ©; 2025, Информационные технологии2025Informacionnye TehnologiiИнформационные технологииhttps://journals.eco-vector.com/1684-6400/article/view/702116

The article describes the implementation of the Mean Shift data clustering algorithm based on the data flow computing system, which provides maximum parallelization of calculations. The description of an algorithm adapted for execution on a dataflow computing system, an algorithm for generating a computational grid, is given. the architecture of the computer system, the implementation of its simulation model, the results of simulation modeling, evaluation of the main parameters of the computer system.

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

computing system with data flow controldata clusteringMean Shift algorithmDelaunay triangulationcomputational gridвычислительная система с управлением потоком данныхкластеризация данныхсдвиг среднего значенияMean Shiftтриангуляция Делоневычислительная сеткаMilutinovic V., Salom J., Veljovic D., Korolija N., Markovic D., Petrovic L. DataFlow Supercomputing Essentials, Research, Development and Education, Springer, 2017, 150 p.Milutinovic V., Salom J., Veljovic D., Korolija N., Markovic D., Petrovic L. DataFlow Supercomputing Essentials // Research, Development and Education. Springer, 2017. 150 p.Milutinovic V., Trifunovic N., Salom J., Giorgi R. The guide to dataflow supercomputing, USA, Springer, 2015, available at: https://proxylibrary.hse.ru:2084/content/pdf/10.1007%2F978-3-319-16229-4.pdf.Milutinovic V., Trifunovic N., Salom J., Giorgi R. The guide to dataflow supercomputing. USA: Springer, 2015. URL: https://proxylibrary.hse.ru:2084/content/pdf/10.1007%2F978-3-319-16229-4.pdfSalibekyan S. M., Panfilov P. B. Issues in automata network modeling of dataflow computing systems, Informacionnye tekhnologii i vychislitel’nye sistemy, 2015, no. 1, pp. 3—9 (in Russian).Салибекян С. М., Панфилов П. Б. Вопросы автоматно-сетевого моделирования вычислительных систем с управлением потоком данных // Информационные технологии и вычислительные системы. 2015. № 1. С. 3—9.Panfilov P. B., Salibekyan S. M. A New Approach for Distributed Computing in Embedded Systems, Procedia Engineering , 2015, vol. 100, pp. 977—986. available at: http://www.scien-cedirect.com/science/article/pii/S187770581500484.Panfilow P. B., Salibekyan S. M. A New Approach for Distributed Computing in Embedded Systems // Procedia Engineering. 2015. Vol. 100. P.977—986. URL: http://www.sciencedirect.com/science/article/pii/S187770581500484.Panfilov P. B., Salibekyan S. M. Modeling of a supercomputer computing system of object-attribute architecture with data flow control, Informacionnye tekhnologii i vychislitel’nye sistemy, 2013, no. 1, pp. 3—10 (in Russian).Салибекян С. М., Панфилов П. Б. Моделирование суперкомпьютерной вычислительной системы объектно-атрибутной архитектуры с управлением потоком данных // Информационные технологии и вычислительные системы. 2013. № 1. С. 3—10.Tyurin A. G., Zuyev I. O. Cluster analysis, methods and algorithms of the clustering, Vestnik MGTU MIREA, 2014, no. 2, pp. 86—97 (in Russian).Тюрин А. Г., Зуев И. О. Кластерный анализ, методы и алгоритмы кластеризации // Вестник МГТУ МИРЭА. 2014. № 2 (3). С. 86—97.Comaniciu D., Meer P. Mean Shift: A Robust Approach Toward Feature Space Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, pp. 603—619.Comaniciu D., Meer P. Mean Shift: A Robust Approach Toward Feature Space Analysis // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2002. P. 603—619.Kim E., Wang W., Li H., Huang X. A parallel annealing methods for automatic color cervigram image segmentation, available at: http://edwardkim.net/publications/edkim_miccaigpu2009.pdf.Kim E., Wang W., Li H., Huang X. A parallel annealing methods for automatic color cervigram image segmentation. URL: http://edwardkim.net/publications/edkim_miccaigpu2009.pdf.Klaus A., Sormann M., Karner K. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure, ICPR 2006, available at: http://old.vrvis.at/2d3d/technology/stereomatching/images/segment-based-stereomatching.pdf.Klaus A., Sormann M., Karner K. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure // ICPR. 2006. URL: http://old.vrvis.at/2d3d/technology/stereomatching/images/segment-based-stereomatching.pdf.Wang Z., Zheng Z. A region based stereo matching algorithm using cooperative optimization, CVPR, 2008, available at: http://vision.middlebury.edu/stereo/eval/papers/CORegion.pdf.Wang Z., Zheng Z. A region based stereo matching algorithm using cooperative optimization // CVPR. 2008. URL: http://vision.middlebury.edu/stereo/eval/papers/CORegion.pdf.Medvedev M. Y., Lazarev V. S. A path planning method for a moving object group using clustering in a two-dimensional environment, Nauchnyj vestnik Novosibirskogo gosudarstvennogo tekhnicheskogo universiteta, 2019, no. 4(77). pp. 45—54, doi 10.17212/1814-1196-2019-4-45-54, EDN FVNLJV (in Russian).Медведев М. Ю., Лазарев В. С. Метод формирования траектории для группы подвижных объектов с помощью кластеризации в двумерной среде // Научный вестник Новосибирского государственного технического университета. 2019. № 4(77). С. 45—54. DOI 10.17212/1814-1196-2019-4-45-54. EDN FVNLJV.Skvorcov A. V. Delaunay triangulation and its application, Tomsk, Publishing house of Tomsk university, 2002, 128 p. (in Russian).Скворцов А. В. Триангуляция Делоне и ее применение. Томск: Изд-во Том. ун-та, 2002. 128 с.Levin B. A., Rosenberg I. N., Tsvetkov V. Y. Modeling of the basic relief based on Delaunay triangulation, Railway Science and Technology, 2018, vol. 2, no. 1 (5), pp. 3—15.Левин Б. А., Розенберг И. Н., Цветков В. Я. Моделирование рельефа на основе триангуляции Делоне // Наука и технологии железных дорог. 2018. Т. 2. № 1 (5). С. 3—15.Zheleznyakova A. L., Surzhikov S. T. A Molecular dynamics-based triangulation of multiple nurbs-surfaces for complex products of the aviation and space-rocket industry, Fiziko-himicheskaya kinetika v gazovoj dinamike, 2014, vol. 15, no 1, pp. 6, EDN UAHFHZ (in Russian).Железнякова А. Л., Суржиков С. Т. Построение пространственных неструктурированных сеток на NURBS-поверхностях сложных изделий авиационной и ракетно-космической техники методом молекулярной динамики // Физико-химическая кинетика в газовой динамике. 2014. Т. 15, № 1. С. 6. EDN UAHFHZ.Rebay S. Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm, Journal of Computational Physics, May 1993, vol. 106, iss. 1, p. 127.Rebay S. Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm // Journal of Computational Physics. May 1993. Vol. 106, Iss. 1. P. 127.Skvorcov A. V., Mirza N. S. Algorithms for constructing and analyzing triangulation, Tomsk, Publishing house of Tomsk university, 2006, 168 p., EDN SBVWBL (in Russian).Скворцов А. В., Мирза Н. С. Алгоритмы построения и анализа триангуляции. Томск: Изд. Нац. иссл. Томского гос. университета, 2006. 168 с. EDN SBVWBL.Batenkov A. A., Man’yakov Yu. A., Gasilov A. V., Yakovlev O. A. Mathematical model of optimal triangulation, Informatika i ee primeneniya, 2018, vol. 12, no. 2, pp. 69—74, doi: 10.14357/19922264180210, EDN USPXIK (in Russian).Батенков А. А., Маньяков Ю. А., Гасилов А. В., Яковлев О. А. Математическая модель оптимальной триангуляции // Информатика и ее применения. 2018. Т. 12, № 2. С. 69—74. DOI 10.14357/19922264180210. EDN USPXIK.Salibekyan S. M., Panfilov P. B. Object-attribute architecture is a new approach to object systems developing, Informacionnye Tehnologii, 2012, no. 2, pp. 8—14 (in Russian).Салибекян С. М., Панфилов П. Б. Объектно-атрибутная архитектура — новый подход к созданию объектных систем // Информационные технологии. 2012. № 2. С. 8—14.Salibekyan S. M., Vishnekov A., Ivanova E. Methodology of Mean Shift Clustering Algorithm Implementation Based on Dataflow Computer, Proceedings of 2019 XVI International Symposium "Problems of Redundancy in Information and Control Systems" (REDUNDANCY)б IEEE, 2019б pp. 177—180, doi: 10.1109/REDUNDANCY48165.2019.9003312.Salibekyan S. M., Vishnekov A., Ivanova E. Methodology of Mean Shift Clustering Algorithm Implementation Based on Dataflow Computer // Proceedings of 2019 XVI International Symposium "Problems of Redundancy in Information and Control Systems" (REDUNDANCY). IEEE, 2019. P. 177—180. DOI: 10.1109/REDUNDANCY48165.2019.9003312Salibekyan S. M. High-level Language Translation Controlled by Dataflow, Informacionnye Tehnologii, 2024, vol. 30, no. 4, pp. 261—268 (in Russian).Салибекян С. М. Трансляция языков высокого уровня, управляемая потоком данных // Информационные технологии. 2024. Т. 30, № 5. С. 261—268. DOI 10.17587/it.30.261-268. EDN TMXWJX.Cormen T., Leiserson Ch., Rivest R., Klifford Sh. Introduction to Algorithms, Moscow, Sankt-Peterburg, Dialektika, 2019, 1323 p. (in Russian).Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. М.; СПб.: Диалектика, 2019. 1323 с.