Статья

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

Скачать в PDF

Ключевые слова Кластеризация; эволюционное моделирование; роевые алгоритмы; алгоритм роя му-равьев; бустинг; k-means.
Библиографический список 1. Donkuan X. Yingjie T. A comprehensive survey of clastering algorithms // Annals of Data Science. – 2015. – Vol. 2, Issue 2. – P. 165-193.
2. Müller K., Mika S., Rätsch G. An introduction to kernel-based learning algorithms // IEEE Trans Neural Netw. – 2001. – No. 12. – P. 181-201.
3. Filippone M., Camastra F., Masulli F. A survey of kernel and spectral methods for clustering // Pattern Recognit. – 2008. – Vol. 41. – P. 176-190.
4. Schölkopf B., Smola A., Müller K. Nonlinear component analysis as a kernel eigenvalue problem // Neural Comput. – 1998. – Vol. 10. – P. 1299-1319.
5. Radha C., Rong J., Timothy C.H., Anil K.J. Scalable Kernel Clustering: Approximate Kernel k-means // Computer Vision and Pattern Recognition. – 2014.
6. Yoon H., Ahn S., Lee S., Cho S., Kim J. Heterogeneous clustering ensemble method for combin-ing different cluster results // In: Data mining for biomedical applications. – 2006. – P. 82-92.
7. Punera K., Ghosh J. Consensus-based ensembles of soft clusterings // ApplArtifIntell. – 2008. – Vol. 22. – P. 780-810.
8. Бустинг. Применение в области машинного обучения. – URL: http://www.machinelearning.ru/ wiki/index.php?title=%D0%91%D1%83%D1%81%D1%82%D0%B8%D0%BD%D0%B3 (дата обращения 28.4.2017).
9. Лебедев Б.К., Лебедев О.Б. Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 27-34.
10. Лебедев Б.К., Нацкевич А.Н. Решение однородной распределительной задачи методом моделирования поведения муравьиной колонии // Информатика, вычислительная техника и инженерное образование. – 2015. − № 4 (24). – С. 7-15.
11. Gladkov L.A., Kravchenko Y.A., Kureichik V.V. Evolutionary Algorithm for Extremal Subsets Comprehension in Graphs // World Applied Sciences Journal. – 2013. – Vol. 27 (9). – P. 1212-1217.
12. Курейчик В.М., Кажаров А.А. Использование шаблонных решений в муравьиных алго-ритмах // Известия ЮФУ. Технические науки. – 2013. – № 7 (144) – С. 11-17.
13. Курейчик В.М. Особенности построения систем поддержки принятия решений // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 92-98.
14. Курейчик В.В., Родзин С.И. О правилах представления решений в эволюционных алго-ритмах // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 13-21.
15. Bova V.V., Kravchenko Y.A., Kureichik V.V. Decision Support Systems for Knowledge Man-agement // Software Engineering in Intelligent Systems. Proceedings of the 4th Computer Sci-ence On-line Conference 2015 (CSOC2015). Springer International Publishing AG Switzerland. – Vol. 3. – P. 123-130.
16. Гладков Л.А., Курейчик В.М., Курейчик В.В. Генетические алгоритмы. – М.: Физматлит, 2006. – 320 с.
17. Курейчик В.В., Бова В.В., Курейчик Вл.Вл. Комбинированный поиск при проектировании // Образовательные ресурсы и технологии. – 2014. – № 2 (5). – С. 90-94.
18. Курейчик В.В., Курейчик Вл.Вл. Бионический поиск при проектировании и управлении // Известия ЮФУ. Технические науки. – 2012. – № 11 (136). – С. 178-183.
19. Zaporozhets D.Yu., Zaruba D.V., Kureichik V.V. Hybrid bionic algorithms for solving prob-lems of parametric optimization // World Applied Sciences Journal. – 2013. – No. 23 (8).
– P. 1032-1036.
20. Курейчик В.В., Запорожец Д.Ю. Роевой алгоритм в задачах оптимизации // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 28-32.
21. Sandro V.P., Jyrko C.M., José R.S. Weighted Partition Consensus via Kernels // Pattern Recognition. – 2010. – Vol. 43(8). – P. 2712-2724.
22. Карпов В.Е. Введение в распараллеливание алгоритмов и программ // Компьютерные исследование и моделирование. – 2010. – Т. 2, № 3. – С. 231-272.

Comments are closed.