Статья

Название статьи КОМБИНИРОВАННЫЙ БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КЛАСТЕРИЗАЦИИ ДАННЫХ
Автор А. Н. Нацкевич, И. О. Курситыс
Рубрика РАЗДЕЛ IV. АНАЛИЗ ДАННЫХ И УПРАВЛЕНИЕ ЗНАНИЯМИ
Месяц, год 04, 2018
Индекс УДК 002.53:004.89
DOI
Аннотация Статья посвящена решению одной из популярнейших задач интеллектуального анализа данных – задачи кластеризации. Кластеризация – объединение в группы схожих объектов – является одной из фундаментальных задач в области анализа данных и Data Mining. Список прикладных областей, где она применяется, широк: сегментация изображений, маркетинг, борьба с мошенничеством, прогнозирование, анализ текстов и многие другие. Решение данной задачи приобретает особую актуальность в условиях постоянно растущего объема генерируемых, передаваемых и обрабатываемых данных. Авторами исследована задача кластеризации, приведены постановка задачи, основные формулы для ее решения, а так же целевая функция. Проведен аналитический обзор существующих алгоритмов, таких как: алгоритмы иерархической кластеризации, квадратичной ошибки, алгоритмы k-means и c-means, алгоритмы, основанные на теории графов. Отмечены основные достоинства и недостатки рассмотренных алгоритмов. Предложено использовать методы биоинспирированного поиска для решения задачи кластеризации, обоснована актуальность применения биоинспирированных моделей и методов для решения NP-полных задач, к классу которых относится и исследуемая задача. Отмечен вклад ученых в решение данной проблемы – биоинспирированные алгоритмы, такие как метод роя частиц, муравьиный алгоритм, пчелиный алгоритм, алгоритм бактериальной оптимизации, алгоритм кукушки и многие другие подобные методы успешно применяются для решения задачи кластеризации. Предложен комбинированный биоинспирированный алгоритм, применяющий последовательно муравьиный алгоритм и алгоритм летучих мышей. Раскрыты основные идеи алгоритмов, приведены схемы решения задачи, кодирования решений. Реализован метод локального поиска для алгоритма летучих мышей. Проведены экспериментальные исследования на тестовых примерах (бенчмарках), которые доказывают эффективность разработанного алгоритма по сравнению с алгоритмами k-средних и генетическим алгоритмом. В ходе проведения экспериментов определена временная сложность разработанного комбинированного биоинспирированного алгоритма. Предложенную модель комбинированого решения задачи планируется в дальнейшем использовать для работы ранее разработанного бустинга алгоритмов, который работает с несколькими алгоритмами и позволяет найти лучшее решение из решений, полученных разными биоинспирированными алгоритмами.

Скачать в PDF

Ключевые слова Кластеризация; биоинспирированный алгоритм; муравьиный алгоритм; алгоритм летучих мышей; роевый алгоритмы; роевой интеллект; искуственный интеллект.
Библиографический список 1. Ka-Chun Wong. A Short Survey on Data Clustering Algorithms // IEEE Second International Conference on Soft Computing and Machine Intelligence, 2015.
2. Кравченко Ю.А., Нацкевич А.Н. Модель решения задачи кластеризации данных на основе использования бустинга алгоритмов адаптивного поведения муравьиной колонии и
k-средних // Известия ЮФУ. Технические науки. – 2017. – № 7 (192). – С. 90-102.
3. Ершов К.С., Романова Т.Н. Анализ и классификация алгоритмов кластеризации // Новые информационные технологии в автоматизированных системах. – 2016. – Вып. 19.
– С. 274-279.
4. Van D.M. and Engelbrecht A.P. Data clustering using particle swarm optimization // Proceedings of The Congress on Evolutionary Computation. – 2003. – P. 215-220.
5. Shelokar P.S., Jayaraman V.K. and Kulkarni B.D. An Ant Colony Approach for Clustering // Analytica Chimica Acta. – 2004. – Vol. 509, No. 2. – P. 187-195.
6. Yi-Tung Kao, Erwie Zahara and I-Wei Kao. A hybridized approach to data clustering // Expert Systems with Applications. – 2008. – Vol. 34, No. 3. – P. 1754-1762.
7. Changsheng Zhang, Dantong Ouyang and Jiaxu Ning. An artificial bee colony approach for clustering // Expert Systems with Applications. – 2010. – Vol. 37, No. 7. – P. 4761-4767,
8. Miao Wan, Lixiang Li, Jinghua Xiao, Cong Wang and Yixian Yang, Data clustering using bacterial foraging optimization // Journal of Intelligent Information Systems. – 2012. – Vol. 38, No. 2. – P. 321-341.
9. Senthilnath J., Vipul Das, Omkar S.N. and Mani V. Clustering using Levy Flight Cuckoo Search // Proceedings of Seventh International Conference on Bio-Inspired Computing: Theories and Applications, Advances in Intelligent Systems and Computing. – 2012. – Vol. 202.
– P. 65-75.
10. Jensi R., Wiselin Jiji G. MBA-LF: a new data clustering method using modified bat algorithm and Levy flight // ICTACT J. Soft Comput. – 2015. – No. 6. – P. 1093-1101.
11. Кулиев Э.В., Лежебоков А.А., Кравченко Ю.А. Роевой алгоритм поисковой оптимизации на основе моделирования поведения летучих мышей // Известия ЮФУ. Технические науки. – 2016. – № 7 (180). – С. 53-62.
12. Частикова В.А., Новикова Е.Ф. Алгоритм летучих мышей для решения задачи глобальной оптимизации // Научные труды КубГТУ (электронный сетевой политематический журнал). – 2015. – № 2. – URL: http://ntk.kubstu.ru/file/348 (дата обращения: 15.12.2017).
13. Красношлык Н.А. Решение задачи глобальной оптимизации модифицированным алгоритмом летучих мышей // Радіоелектроніка, інформатика, управління. – 2015. – № 4 (35). – С. 96-103.
14. Кравченко Ю.А., Нацкевич А.Н., Курситыс И.О. Бустинг биоинспирированных алгоритмов для решения задачи кластеризации // Международная конференция по мягким вычислениям и измерениям. – 2018. – Т. 1. – С. 777-780.
15. Bova V.V., Kravchenko Y.A., Kureichik V.V. Development of distributed information systems: ontological approach // Advances in Intelligent Systems and Computing. – 2015. – Vol. 349.
– P. 113-122.
16. Кравченко Ю.А. Технология анализа надежности адаптивных информационных сред // Известия ЮФУ. Технические науки. – 2010. – № 12 (113). – С. 103-108.
17. Кравченко Ю.А. Оценка когнитивной активности пользователя в системах поддержки принятия решений // Известия ЮФУ. Технические науки. – 2009. – № 4 (93). – С. 113-117.
18. Родзин С.И., Курейчик В.В. Теоретические вопросы и современные проблемы развития когнитивных биоинспирированных алгоритмов оптимизации // Кибернетика и программирование. – 2017. – № 3. – С. 51-79.
19. Donkuan X. Yingjie T.A. comprehensive survey of clustering algorithms // Annals of Data Science. – 2015. – Vol. 2, Issue 2. – P. 165-193.
20. Kravchenko Y.A., Kuliev E.V., Kursitys I.O.: Information's semantic search, classification, structuring and integration objectives in the knowledge management context problems // In: 8th IEEE International Conference on Application of Information and Communication Technologies (AICT 2016). – IEEE Press, Baku, Azerbaijan, 2016. – P. 136-141.

Comments are closed.