Генетический алгоритм кластеризации
https://doi.org/10.32362/2500-316X-2019-7-6-134-150
Аннотация
В рамках гибридного подхода построения информационных интеллектуальных технологий поддержки принятия решений предложен генетический алгоритм кластеризации объектов анализа в различных предметных областях. Алгоритм позволяет учитывать при кластеризации различные предпочтения аналитика, отражаемые в расчетной формуле фитнес-функции. Показано место данного алгоритма среди используемых для кластерного анализа. Алгоритм является простым в его программной реализации, что повышает его надежность в использовании. Используемая технология эволюционного моделирования несколько расширена в рассматриваемом алгоритме. Во-первых, используется десятичная система счисления для кодирования хромосом в отличие от традиционной двоичной. Это вызвано множественным, а не бинарным, состоянием генов хромосомы. С этим связано отсутствие в данном алгоритме генетического оператора инверсии. Во-вторых, введен новый генетический оператор фильтрации, который отсеивает хромосомы, не удовлетворяющие условию требуемого количества кластеров в поставленной задаче. Такие хромосомы могут появляться в стохастическом процессе их эволюции. Представленный алгоритм был исследован в серии вычислительных экспериментов. В результате было выявлено, что стабилизация разбиения на кластеры достигается при числе реализованных поколений эволюции от 200 и более при сравнительно небольшом размере популяции от 150 хромосом, не требующем значительного выделения оперативной памяти компьютера. Проведенные вычисления на реальных данных показали для данного алгоритма хорошее качество кластеризации и вполне приемлемую производительность одного порядка с производительностью алгоритмов SOM и “k-means”.
Об авторе
М. А. Анфёров
МИРЭА – Российский технологический университет
Россия
Россия
Анфёров Михаил Анисимович, доктор технических наук, профессор, профессор кафедры «Прикладная и бизнес-информатика»
119454, Россия, Москва, пр-т Вернадского, д. 78
Список литературы
1. Нечеткие системы, мягкие вычисления и интеллектуальные технологии: Труды VII Всероссийской научно-практической конференции. Санкт-Петербург, 03–07 июля 2017 г. Т. 2. СПб.: Политехника-сервис, 2017. 210 с.
2. Юдин В.Н., Карпов Л.Е. Неполностью описанные объекты в системах поддержки принятия решений // Программирование. 2017. № 5. С. 24–31.
3. Анфёров М.А. Системная оптимизация наукоемких технологий // Известия вузов. Авиационная техника. 2002. № 2. С. 57–60.
4. Батыршин И.З., Недосекин А.А., Стецко А.А., Тарасов В.Б., Язенин А.В., Ярушкина Г.Г. Нечеткие гибридные системы: теория и практика / Под ред. Н.Г. Ярушкиной. М.: Физматлит, 2007. 207 с.
5. Аджемов С.С., Кленов Н.В., Терешонок М.В., Чиров Д.С. Использование искусственных нейронных сетей для классификации источников сигналов в системах когнитивного радио // Программирование. 2016. № 3. С. 3–11.
6. Hu 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_49
7. Анфёров М.А., Ханнанов М.Г. Кластерный подход к проектированию в САПР ТП // Проведение научных исследований в области обработки, хранения, передачи и защиты информации. Сб. науч. тр. в 4 т. Т. 3. Ульяновск: УлГТУ, 2009. С. 60–65.
8. Бороздина Н.А. Применение иерархического кластерного анализа для сегментации потребителей рынка сотовой связи // Молодой ученый. 2016. № 29. С. 365–367. URL: https://moluch.ru/archive/133/37358/ (дата обращения: 13.11.2019).
9. Дударин П.В., Ярушкина Н.Г. Подходы к нечеткой и иерархической кластеризации и классифиации ключевых показателей эффективности системы стратегического планирования российской федерации // Труды VII Всероссийской научно-практической конференции «Нечеткие системы, мягкие вычисления и интеллектуальные технологии». Санкт-Петербург, 03–07 июля, 2017г. Т. 2. СПб.: Политехника-сервис, 2017. С. 65–73.
10. Петухова. М.В. Кластеризация заемщиков – физических лиц по уровню дефолтов: рейтинговый подход (на примере регионов Сибирского федерального округа) // Журнал Новой экономической ассоциации. 2012. № 4 (16). С. 71–102.
11. Анфёров М.А. Сети Кохонена в задаче выявления экономически нестабильных региональных структур // Труды XV Всероссийской научно-технической конференции «Нейроинформатика 13». Москва, 21–25 января, 2013 г. Т. 3. М: НИЯУ МИФИ, 2013. С. 177–184.
12. Анфёров М.А., Рашитова О.Б. SADT моделирование системы налогообложения в Российской Федерации // Экономика и управление: научно-практический журнал. 2015. № 2(124). С. 94–101.
13. 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_13
14. Хвостиков А.В., Крылов А.С., Камалов Ю.Р. Текстурный анализ ультразвуковых изображений для диагностирования фиброза печени // Программирование. 2015. № 5. С. 39–46.
15. Kumar 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_64
16. Abadi 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.11491
17. Hussain 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_21
18. Харинов М.В. Кластеризация пикселей для сегментации цветового изображения // Программирование. 2015. № 5. С. 20–30.
19. Астраханцев Н.А., Федоренко Д.Г. Турдаков Д.Ю. Методы автоматического извлечения терминов из коллекции текстов предметной области // Программирование. 2015. № 6. С. 33–52.
20. Lakhno 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_66
21. 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. V. 28. № 1. P. 100–108.
22. Kohonen T. Self-Organizing Maps: 3rd edition. Berlin - New York: Springer-Verlag, 2001. 521 p.
23. 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.233324
24. Pä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.039
25. Sudipto 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-4
26. Sudipto 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-3
27. Bodyanskiy 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_40
28. Иванова Е.В., Соколинский Л.Б. Методы параллельной обработки сверхбольших баз данных с использованием распределенных колоночных индексов // Программирование. 2017. № 3. С. 3–21.
29. Shao 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/2934688
30. Songlei 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.2848902
31. Sheikholeslami 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/s007780050009
32. Gionis 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.1217303
33. Wang 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/3230967
34. Zhang 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/2747879
35. Abasi 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.7101
36. Горбатков С.А., Рашитова О.Б. Моделирование налоговых управленческих решений на основе нейронных сетей Кохонена // Информационные технологии. 2013. № 5. С. 60–65.
Дополнительные файлы
|
|
1. Рис. 4. Работа алгоритма на переходных режимах (сильно выраженная кластеризация) | |
| Тема | ||
| Тип | Исследовательские инструменты | |
Посмотреть
(2MB)
|
Метаданные ▾ | |
Рецензия
Для цитирования:
Анфёров М.А. Генетический алгоритм кластеризации. Russian Technological Journal. 2019;7(6):134-150. https://doi.org/10.32362/2500-316X-2019-7-6-134-150
For citation:
Anfyorov M.A. Genetic clustering algorithm. Russian Technological Journal. 2019;7(6):134-150. (In Russ.) https://doi.org/10.32362/2500-316X-2019-7-6-134-150
Просмотров:
1743
Послать статью по эл. почте 