Применение метаэвристических алгоритмов к решению задач кластеризации методом k-средних
Лисин А.В, Файзуллин Р.Т.

Омский государственный технический университет, Омск, Россия

Аннотация:
В статье рассматривается подход к сегментации изображений методом k-средних путём сведения задачи кластеризации к задаче непрерывной оптимизации и её решения с помощью метаэвристических алгоритмов на примере алгоритма гравитационного поиска. Обосновывается применимость данного подхода, приводятся результаты численного эксперимента.

Ключевые слова :
кластеризация, метод k-средних, обработка изображений, непрерывная оптимизация.

Цитирование:
Лисин, А.В. Применение метаэвристических алгоритмов к решению задач кластеризации методом k-средних / А.В. Лисин, Р.Т. Файзуллин // Компьютерная оптика. – 2015. – Т. 39, №3. – С. 406-412. – DOI: 10.18287/0134-2452-2015-39-3-406-412.

Литература:

  1. Сегаран, Т. Программируем коллективный разум / Т. Сегаран; пер. c англ. – Символ-Плюс, 2008. – 368 с. (T. Segaran. Programming Collective Intelligence. – O’Reilly Media, 2007.)
  2. Inaba, M. Applications of Weighted Voronoi Diagrams and Randomization to Variance-based K-clustering: (Extended Abstract) / M. Inaba, N. Katoh, H. Imai // Proceedings of the Tenth Annual Symposium on Computational Geometry. – 1994. – Vol. 10 – P. 332–339.
  3. Lloyd, S. Least squares quantization in PCM / S. Lloyd // Information Theory, IEEE Transactions on. – 1982. – Vol. 28(2) – P. 129-137.
  4. Лисин, А.В. Эвристический алгоритм поиска приближенного решения задачи Штейнера, основанный на физических аналогиях / А.В. Лисин, Р.Т. Файзуллин // Компьютерная оптика. – 2013. – Т. 37, № 4. – С. 503-510.
  5. Дулькейт, В.И. Приближенное решение задачи коммивояжера методом рекурсивного построения вспомогательной кривой / В.И. Дулькейт, Р.Т. Файзуллин // Прикладная дискретная математика. – 2009. – Т. 1, № 3. – С. 72-78.
  6. Sundaram, R.K. A First Course in Optimization Theory / R.K. Sundaram. – Cambridge University Press, 1996. – 376 p.
  7. Avriel, M. Nonlinear Programming: Analysis and Methods / M. Avriel – Dover Publishing, 2003. – 544 p.
  8. Duman, S. Gravitational Search Algorithm for Economic Dispatch with Valve-Point Effects / S. Duman, U. Güvenç, N. Yörükeren // International Review of Electrical Engineering. – 2010. – Vol. 5. – P. 2890-2895.
  9. Rashedi, E. GSA: A Gravitational Search Algorithm / E. Rashedi, H. Nezamabadi-pour, S. Saryazdi // Information Science. – 2009. – Vol. 179. – P. 2232–2248.
  10. Зиновьев, А.Ю. Визуализация многомерных данных / А.Ю. Зиновьев. – Красноярск: Изд-во Красноярского государственного технического университета, 2000. – 180 с.
  11. Кормен, Т. Алгоритмы. Построение и анализ / Т. Кор- мен, Ч. Лейзерсон, Р. Ривест, К. Штайн; пер. с англ. – М.: Издательский дом «Вильямс», 2012. – 1296 с. (T. Cormen, R. Rivest, C. Leiserson. Introduction to algorithms. – McGraw-Hill Science/Engineering/Math, 2001).
© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; E-mail: ko@smr.ru; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20