mireabulletinRussian Technological JournalRussian Technological Journal2782-32102500-316XRTU MIREA10.32362/2500-316X-2019-7-6-134-150mireabulletin-187Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGГенетический алгоритм кластеризацииGenetic clustering algorithmАнфёровМ. А.AnfyorovM. A.

Анфёров Михаил Анисимович, доктор технических наук, профессор, профессор кафедры «Прикладная и бизнес-информатика»

119454, Россия, Москва, пр-т Вернадского, д. 78

Mikhail A. Аnfyorov, Dr. of Sci. (Engineering), Professor of the Chair “Applied and Business Informatics,”

78, Vernadskogo pr., Moscow 119454, Russia

anfyorov@inbox.ruМИРЭА – Российский технологический университетРоссияMIREA – Russian Technological UniversityRussian Federation20191001202076134150Copyright © Анфёров М.А., 20202020Анфёров М.А.Anfyorov M.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.rtj-mirea.ru/jour/article/view/187

В рамках гибридного подхода построения информационных интеллектуальных технологий поддержки принятия решений предложен генетический алгоритм кластеризации объектов анализа в различных предметных областях. Алгоритм позволяет учитывать при кластеризации различные предпочтения аналитика, отражаемые в расчетной формуле фитнес-функции. Показано место данного алгоритма среди используемых для кластерного анализа. Алгоритм является простым в его программной реализации, что повышает его надежность в использовании. Используемая технология эволюционного моделирования несколько расширена в рассматриваемом алгоритме. Во-первых, используется десятичная система счисления для кодирования хромосом в отличие от традиционной двоичной. Это вызвано множественным, а не бинарным, состоянием генов хромосомы. С этим связано отсутствие в данном алгоритме генетического оператора инверсии. Во-вторых, введен новый генетический оператор фильтрации, который отсеивает хромосомы, не удовлетворяющие условию требуемого количества кластеров в поставленной задаче. Такие хромосомы могут появляться в стохастическом процессе их эволюции. Представленный алгоритм был исследован в серии вычислительных экспериментов. В результате было выявлено, что стабилизация разбиения на кластеры достигается при числе реализованных поколений эволюции от 200 и более при сравнительно небольшом размере популяции от 150 хромосом, не требующем значительного выделения оперативной памяти компьютера. Проведенные вычисления на реальных данных показали для данного алгоритма хорошее качество кластеризации и вполне приемлемую производительность одного порядка с производительностью алгоритмов SOM и “k-means”.

The genetic algorithm of clustering of analysis objects in different data domains has been offered within the hybrid concept of intelligent information technologies development aimed to support decision-making. The algorithm makes it possible to account for different preferences of the analyst in clustering reflected in a calculation formula of fitness function. The place of this algorithm among those used for cluster analysis has been shown. The algorithm is simple in its program implementation, which increases its usage reliability. The used technology of evolutionary modeling is rather expanded in the mentioned algorithm. Firstly, the decimal chromosomes coding is used instead of the traditional binary coding. This has resulted from the fact that the chromosome genes condition is multiple and not binary. Moreover, this is due to the absence of the genetic operator of inversion in this algorithm. Secondly, a new genetic operator used for filtering has been implemented. This operator eliminates chromosomes that do not meet the required clusters quantity condition in a task. Such chromosomes can appear in the stochastic process of their evolution. The presented algorithm has been studied in a series of simulation experiments. As a result, it has been found that stabilization of splitting into clusters is reached when the number of completed generations of evolution is 200 and more, and the population size is rather small: from 150 chromosomes (in this case no considerable amount of random-access store is required). The calculations carried out on real data showed for this algorithm the high quality of clustering and the acceptable computing speed of the same order with the computing speed of SOM and “k-means” algorithms.

кластеризациягенетический алгоритминтеллектуальная технологияпринятие решенийвычислительный экспериментclusteringgenetic algorithmintellectual technologydecision-makingcomputing experimentReferencesНечеткие системы, мягкие вычисления и интеллектуальные технологии: Труды VII Всероссийской научно-практической конференции. Санкт-Петербург, 03–07 июля 2017 г. Т. 2. СПб.: Политехника-сервис, 2017. 210 с.Fuzzy systems, soft calculations and intellectual technologies: Proceedings of the VII All-Russian Scientific and Practical Conference. St. Petersburg, July 03-07, 2017. V. 2. St. Petersburg: Politekhnika-servis Publ., 2017. 210 p. (in Russ.).Юдин В.Н., Карпов Л.Е. Неполностью описанные объекты в системах поддержки принятия решений // Программирование. 2017. № 5. С. 24–31.Yudin V.N., Karpov L.E. Incompletely described objects in decision support. Programming and Computer Software. 2017;43(5):294-299.Анфёров М.А. Системная оптимизация наукоемких технологий // Известия вузов. Авиационная техника. 2002. № 2. С. 57–60.Аnfyorov M.А. System optimization of high technologies. Izv. VUZ. Аviatsionnaya tekhnika = Russian Aeronautics. 2002;2:57-60 (in Russ.).Батыршин И.З., Недосекин А.А., Стецко А.А., Тарасов В.Б., Язенин А.В., Ярушкина Г.Г. Нечеткие гибридные системы: теория и практика / Под ред. Н.Г. Ярушкиной. М.: Физматлит, 2007. 207 с.Batyrshin I.Z., Nedosekin А.А., Stetsko А.А., Tarasov V.B., Yazenin A.V., Yarushkina N.G. Fuzzy hybrid systems: theory and practice. Ed. N.G. Yarushkina. Moscow: Fizmatlit Publ., 2007. 207 p. (in Russ.).Аджемов С.С., Кленов Н.В., Терешонок М.В., Чиров Д.С. Использование искусственных нейронных сетей для классификации источников сигналов в системах когнитивного радио // Программирование. 2016. № 3. С. 3–11.Аdzhemov S.S., Klenov N.V., Tereshonok M.V., Chirov D.S. The use of artificial neural networks for classification of signal sources in cognitive radio systems. Programming and Computer Software. 2016;42(3):121-128. 10.1134/S0361768816030026Hu Z., Bodyanskiy Y., Tyshchenko O.K. Self-learning procedures for a kernel fuzzy clustering system // Advances in Computing Science for Engineering and Education. 2019. V. 754. P. 487–497. http://dx.doi.org/10.1007/978-3-319-91008-6_49Hu Z., Bodyanskiy Y., Tyshchenko O.K. Self-learning procedures for a kernel fuzzy clustering system. Advances in Computing Science for Engineering and Education. 2019;754:487-497. http://dx.doi.org/10.1007/978-3-319-91008-6_49Анфёров М.А., Ханнанов М.Г. Кластерный подход к проектированию в САПР ТП // Проведение научных исследований в области обработки, хранения, передачи и защиты информации. Сб. науч. тр. в 4 т. Т. 3. Ульяновск: УлГТУ, 2009. С. 60–65.Аnfyorov M.А., Khannanov M.G. Cluster approach to design in CAM. In: Provedeniye nauchnykh issledovaniy v oblasti obrabotki, khraneniya, peredachi i zashchity informatsii = Conducting scientific research in the field of processing, storage, transmission and protection of information. Collection of scientific papers in 4 v. V. 3. Ul’yanovsk: UlGTU Publ., 2009; pp. 60-65 (in Russ.).Бороздина Н.А. Применение иерархического кластерного анализа для сегментации потребителей рынка сотовой связи // Молодой ученый. 2016. № 29. С. 365–367. URL: https://moluch.ru/archive/133/37358/ (дата обращения: 13.11.2019).Borozdina N.А. The use of hierarchical cluster analysis for segmentation of consumers of the market of cellular communication. Molodoi uchenyi = Young scientist. 2016;29:365-367. (in Russ.). URL: https://moluch.ru/archive/133/37358/ (accessed November 13, 2019).Дударин П.В., Ярушкина Н.Г. Подходы к нечеткой и иерархической кластеризации и классифиации ключевых показателей эффективности системы стратегического планирования российской федерации // Труды VII Всероссийской научно-практической конференции «Нечеткие системы, мягкие вычисления и интеллектуальные технологии». Санкт-Петербург, 03–07 июля, 2017г. Т. 2. СПб.: Политехника-сервис, 2017. С. 65–73.Dudarin P.V., Yarushkina N.G. Approaches to fuzzy and hierarchical clustering and classification of key process indicators of the strategic planning system of the Russian Federation. In: Proceedings of the VII All-Russian Scientific and Practical Conference “Fuzzy Systems, Soft Computing and Intelligent Technology”. St. Petersburg, July 03–07, 2017. V. 2. SPb.: Polytekhnik servis Publ., 2017; pp. 65-73 (in Russ.).Петухова. М.В. Кластеризация заемщиков – физических лиц по уровню дефолтов: рейтинговый подход (на примере регионов Сибирского федерального округа) // Журнал Новой экономической ассоциации. 2012. № 4 (16). С. 71–102.Petukhova M.V. Clustering of borrowers at the level of defaults: Rating approach (regions of Siberian Federal District). Zhurnal Novoi ekonomicheskoi assotsiatsii = J. New Economic Association. 2012;4(16):71-102 (in Russ.).Анфёров М.А. Сети Кохонена в задаче выявления экономически нестабильных региональных структур // Труды XV Всероссийской научно-технической конференции «Нейроинформатика 13». Москва, 21–25 января, 2013 г. Т. 3. М: НИЯУ МИФИ, 2013. С. 177–184.Аnfyorov M.А. Kohonen networks in a problem of identification of economically unstable regional structures. Proceedings of the XV All-Russian Scientific and Practical Conference “Nejroinformatika 13” [Neuroinformatics-2013]. Moscow, 21–25 January, 2013. V. 3. М.: NIYaU MIFI, 2013; pp. 177-184 (in Russ.).Анфёров М.А., Рашитова О.Б. SADT моделирование системы налогообложения в Российской Федерации // Экономика и управление: научно-практический журнал. 2015. № 2(124). С. 94–101.Аnfyorov M.А., Rashitova O.B. SADT modeling of the Russian Federation tax system. Ekonomika i upravlenie: nauchno-prakticheskii zhurnal = Economics and Management: Research and Practice Journal. 2015;2(124):94-101 (in Russ.).González del Pozo R., García-Lapresta J.L., Pérez-Román D. Clustering U.S. 2016 presidential candidates through linguistic appraisals // Advances in Intelligent Systems and Computing. 2018. V. 642. P. 143–153. https://doi.org/10.1007/978-3-319-66824-6_13González del Pozo R., García-Lapresta J.L., Pérez-Román D. Clustering U.S. 2016 presidential candidates through linguistic appraisals. Advances in Intelligent Systems and Computing. 2018;642:143-153. https://doi.org/10.1007/978-3-319-66824-6_13Хвостиков А.В., Крылов А.С., Камалов Ю.Р. Текстурный анализ ультразвуковых изображений для диагностирования фиброза печени // Программирование. 2015. № 5. С. 39–46.Kvostikov А.V., Krylov А.S., Kamalov U.R. Ultrasound image texture analysis for liver fibrosis stage diagnostics. Programming and Computer Software. 2015;41(5):273-278. https://doi.org/10.1134/S0361768815050059Kumar S., Mishra S., Asthana P. Automated detection of acute leukemia using k-mean clustering algorithm // Advances in Intelligent Systems and Computing. 2018. V. 554. P. 655–670. https://doi.org/10.1007/978-981-10-3773-3_64Kumar S., Mishra S., Asthana P. Automated detection of acute leukemia using k-mean clustering algorithm. Advances in Intelligent Systems and Computing. 2018;554:655-670. https://doi.org/10.1007/978-981-10-3773-3_64Abadi S., Sari T.I., Maseleno A., Muslihudin M., Mat The K.S., Nasir B.M., Huda M., Ivanova N.L., Satria F. Application model of k-means clustering: insights into promotion strategy of vocational high school // International Journal of Engineering and Technology. 2018. V. 7. № 2.27. P. 182–187. http://dx.doi.org/10.14419/ijet.v7i2.11491Abadi S., Sari T.I., Maseleno A., Muslihudin M., Mat The K.S., Nasir B.M., Huda M., Ivanova N.L., Satria F. Application model of k-means clustering: insights into promotion strategy of vocational high school. International Journal of Engineering and Technology. 2018;7(2.27):182-187. http://dx.doi.org/10.14419/ijet.v7i2.11491Hussain S., Atallah R., Kamsin A., Hazarika J. Classification, сlustering and association rule mining in educational datasets using data mining tools: A case study // Advances in Intelligent Systems and Computing. 2019. V. 765. P. 196–211. https://doi.org/10.1007/978-3-319-91192-2_21Hussain S., Atallah R., Kamsin A., Hazarika J. Classification, Clustering and Association Rule Mining in Educational Datasets Using Data Mining Tools: A Case Study. Advances in Intelligent Systems and Computing. 2019;765:196-211. https://doi.org/10.1007/978-3-319-91192-2_21Харинов М.В. Кластеризация пикселей для сегментации цветового изображения // Программирование. 2015. № 5. С. 20–30.Kharinov M.V. Pixel clustering for color image segmentation. Programming and Computer Software. 2015:41(5):258-266. https://doi.org/10.1134/S0361768815050047Астраханцев Н.А., Федоренко Д.Г. Турдаков Д.Ю. Методы автоматического извлечения терминов из коллекции текстов предметной области // Программирование. 2015. № 6. С. 33–52.Аstrakhantsev N.А., Fedorenko D.G. Turdakov D.YU. Methods for automatic term recognition in domainspecific text collections: A survey. Programming and Computer Software. 2015;41(6):336-349. https://doi.org/10.1134/S036176881506002XLakhno V., Zaitsev S., Tkach Y., Petrenko T. Adaptive expert systems development for cyber attacks recognition in information educational systems on the basis of signs’ clustering // Advances in Intelligent Systems and Computing. 2019. V. 754. P. 673–682. https://doi.org/10.1007/978-3-319-91008-6_66Lakhno V., Zaitsev S., Tkach Y., Petrenko T. Adaptive expert systems development for cyber attacks recognition in information educational systems on the basis of signs’ clustering. Advances in Intelligent Systems and Computing. 2019;754:673-682. https://doi.org/10.1007/978-3-319-91008-6_66Hartigan, J.A., Wong, M.A. Algorithm AS 136: A k-means clustering algorithm // Journal of the Royal Statistical Society, Series C (Applied Statistics). 1979. V. 28. № 1. P. 100–108.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.Kohonen T. Self-Organizing Maps: 3rd edition. Berlin - New York: Springer-Verlag, 2001. 521 p.Kohonen T. Self-Organizing Maps: 3rd edition. Berlin - New York: Springer-Verlag, 2001. 521 p.Zhang T., Ramakrishnan R., Livny M. BIRCH: an efficient data clustering method for very large databases // Proceedings of the ACM SIGMOD international conference on Management of data (SIGMOD '96). 1996. P. 103–114. https://doi.org/10.1145/235968.233324Zhang T., Ramakrishnan R., Livny M. BIRCH: an efficient data clustering method for very large databases. In: Proceedings of the ACM SIGMOD international conference on Management of data (SIGMOD ’96). 1996; pp. 103-114. https://doi.org/10.1145/235968.233324Päivinen N. Clustering with a minimum spanning tree of scale-free-like structure // Pattern Recognition Letters. 2005. V. 26. Iss. 7. P. 921–930. https://doi.org/10.1016/j.patrec.2004.09.039Päivinen N. Clustering with a minimum spanning tree of scale-free-like structure. Pattern Recognition Letters. 2005;26(7):921-930. https://doi.org/10.1016/j.patrec.2004.09.039Sudipto Guha, Rajeev Rastogi, Kyuseok Shim. CURE: An Efficient Clustering Algorithm for Large Databases // Information Systems. 1998. V. 26. № 1. P. 35–58. https://doi.org/10.1016/S0306-4379(01)00008-4Sudipto Guha, Rajeev Rastogi, Kyuseok Shim. CURE: An Efficient Clustering Algorithm for Large Databases. Information Systems. 1998;26(1):35-58. https://doi.org/10.1016/S0306-4379(01)00008-4Sudipto Guha, Rajeev Rastogi, Kyuseok Shim. ROCK: a robust clustering algorithm for categorical attributes // Information Systems. 2000. V. 25. № 5. P. 345–366. https://doi.org/10.1016/S0306-4379(00)00022-3Sudipto Guha, Rajeev Rastogi, Kyuseok Shim. ROCK: a robust clustering algorithm for categorical attributes. Information Systems. 2000;25(5):345-366. https://doi.org/10.1016/S0306-4379(00)00022-3Bodyanskiy Y., Didyk O. On-line robust fuzzy clustering for anomalies detection // Advances in Intelligent Systems and Computing. 2019. V. 754. P. 402–409. https://doi.org/10.1007/978-3-319-91008-6_40Bodyanskiy Y., Didyk O. On-line robust fuzzy clustering for anomalies detection. Advances in Intelligent Systems and Computing. 2019;754:402-409. https://doi.org/10.1007/978-3-319-91008-6_40Иванова Е.В., Соколинский Л.Б. Методы параллельной обработки сверхбольших баз данных с использованием распределенных колоночных индексов // Программирование. 2017. № 3. С. 3–21.Ivanova E.V., Sokolinsky L.B. Parallel processing of very large databases with using distributed columnar indexes. Programming and Computer Software. 2017;43(3):131-144. https://doi.org/10.1134/S0361768817030069Shao J., Yang Q., Schmidt B., Dang H-V., Kramer S. Scalable Clustering by Iterative Partitioning and Point Attractor Representation // ACM Transactions on Knowledge Discovery from Data. 2016. V. 11. № 1. P. 5:1–5:23. https://doi.org/10.1145/2934688Shao J., Yang Q., Schmidt B., Dang H-V., Kramer S. Scalable Clustering by Iterative Partitioning and Point Attractor Representation. ACM Transactions on Knowledge Discovery from Data. 2016;11(1):5:1-5:23. https://doi.org/10.1145/2934688Songlei J.https://orcid.org/0000-0001-5760-6431, Guansong P., Longbing C., Kai L., Hang G. CURE: Flexible Categorical Data Representation by Hierarchical Coupling Learning // IEEE Transactions on Knowledge and Data Engineering. 2019. V. 31. Iss. 5. P. 853–866. https://doi.org/10.1109/TKDE.2018.2848902Songlei J.https://orcid.org/0000-0001-5760-6431, Guansong P., Longbing C., Kai L., Hang G. CURE: Flexible Categorical Data Representation by Hierarchical Coupling Learning. IEEE Transactions on Knowledge and Data Engineering. 2019;31(5):853-866. https://doi.org/10.1109/TKDE.2018.2848902Sheikholeslami G., Chatterjee S., Zhang A. WaveCluster: A Wavelet-Based Clustering Approach for Spatial Data // VLDB Journal. 2000. № 8(3-4). P. 289–304. http://dx.doi.org/10.1007/s007780050009Sheikholeslami G., Chatterjee S., Zhang A. WaveCluster: A Wavelet-Based Clustering Approach for Spatial Data. VLDB Journal. 2000;8(2-4):289-304. http://dx.doi.org/10.1007/s007780050009Gionis A., Mannila H., Tsaparas P. Clustering Aggregation // ACM Transactions on Knowledge Discovery from Data. 2007. V. 1. № 1. Article 4. 30 p. https://doi.org/10.1145/1217299.1217303Gionis A., Mannila H., Tsaparas P. Clustering Aggregation. ACM Transactions on Knowledge Discovery from Data. 2007;1(1):Article 4. 30 p. https://doi.org/10.1145/1217299.1217303Wang C., She Z., Stantic B., Chi C.H., Cao L. Coupled Clustering Ensemble by Exploring Data Interdependence // ACM Transactions on Knowledge Discovery from Data. 2018. V. 12. № 6. P. 63:1-63:38. http://dx.doi.org/10.1145/3230967Wang C., She Z., Stantic B., Chi C.H., Cao L. Coupled Clustering Ensemble by Exploring Data Interdependence. ACM Transactions on Knowledge Discovery from Data. 2018;12(6):63:1-63:38. https://doi.org/10.1145/3230967Zhang X., Zhang X., Liu H. Smart Multitask Bregman Clustering and Multitask Kernel Clustering // ACM Transactions on Knowledge Discovery from Data. 2015. V. 10. № 1. P. 8:1-8: p. https://doi.org/10.1145/2747879Zhang X., Zhang X., Liu H. Smart Multitask Bregman Clustering and Multitask Kernel Clustering. ACM Transactions on Knowledge Discovery from Data. 2015;10(1):8:1-8:29. https://doi.org/10.1145/2747879Abasi A., Sajedi H. Fuzzy-clustering based data gathering in wireless sensor network // International Journal on Soft Computing (IJSC). 2016. V.7. № 1. P.1–15. https://doi.org/10.5121/ijsc.2016.7101Abasi A., Sajedi H. Fuzzy-clustering based data gathering in wireless sensor network. International Journal on Soft Computing (IJSC). 2016:7(1):1-15. https://doi.org/10.5121/ijsc.2016.7101Горбатков С.А., Рашитова О.Б. Моделирование налоговых управленческих решений на основе нейронных сетей Кохонена // Информационные технологии. 2013. № 5. С. 60–65.Gorbatkov S.А., Rashitova O.B. Modeling of tax administrative decisions on the basis of Kohonen’s neural networks. Informatsionnye tekhnologii = Information Technology. 2013;5:60-65 (in Russ.).

The authors declare that there are no conflicts of interest present.