Алгоритм усреднения центроидов для построения кластерного ансамбля
Татарников В.В., Пестунов И.А., Бериков В.Б.

 

Институт математики СО РАН, Новосибирск, Россия,
Институт вычислительных технологий СО РАН, Новосибирск, Россия

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

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

Цитирование:
Татарников, В.В. Алгоритм усреднения центроидов для построения кластерного ансамбля / В.В. Татарников, И.А. Пестунов, В.Б. Бериков // Компьютерная оптика. – 2017. – Т. 41, № 5. – С. 712-718. – DOI: 10.18287/2412-6179-2017-41-5-712-718.

Литература:

  1. Hastie, T. The elements of statistical learning / T. Hastie, R. Tibshirani, J. Friedman. – 2nd ed. – New York: Springer-Verlag, 2009. – 745 p. – ISBN: 978-0-387-84857-0.
  2. Xu, Rui. Clustering / R. Xu, D.C. Wunsch II. – Hoboken, NJ: John Wiley& Sons, Inc., 2009. – 368 p. – ISBN: 978-0-470-27680-8.
  3. Белим, С.В. Выделение контуров на изображениях с помощью алгоритма кластеризации / С.В. Белим, П.Е. Кутлунин // Компьютерная оптика. – 2015. – Т. 39, № 1. – С. 119-124. – DOI: 10.18287/0134-2452-2015-39-1-119-124.
  4. Jain, A.K. Data clustering: 50 years beyond K-means / A.K. Jain // Pattern Recognition Letters. – 2010. – Vol. 31, Issue 8. – P. 651-666. – DOI: 10.1016/j.patrec.2009.09.011.
  5. Ghaemi, R. A survey: Clustering ensembles techniques / R. Ghaemi, M. Sulaiman, H. Ibrahim, N. Mustapha // Proceedings of World Academy of Science, Engineering and Technology. – 2009. – Vol. 38. – P. 644-653.
  6. Hore, P. A scalable framework for cluster ensembles / P. Hore, L.O. Hall, D.B. Goldgof // Pattern Recognition. – 2009. – Vol. 42, Issue 5. – P. 676-688. – DOI: 10.1016/j.patcog.2008.09.027.
  7. Kashef, R. Cooperative clustering / R. Kashef, M.S. Kamel // Pattern Recognition. – 2010. – Vol. 43, Issue 6. – P. 2315-2329. – DOI: 10.1016/j.patcog.2009.12.018.
  8. Jia, J. Soft spectral clustering ensemble applied to image segmentation / J. Jia, B. Liu, L. Jiao // Frontiers of Computer Science in China. – 2011. – Vol. 5, Issue 1. – P. 66-78.
  9. Franek, L. Ensemble clustering by means of clustering embedding in vector spaces / L. Franek, X. Jiang // Pattern Recognition. – 2014. – Vol. 47, Issue 2. – P. 833-842. – DOI: 10.1016/j.patcog.2013.08.019.
  10. Berikov, V. Ensemble clustering based on weighted co-association matrices: Error bound and convergence properties / V. Berikov, I. Pestunov // Pattern Recognition. – 2017. – Vol. 63. – P. 427-436. – DOI: 10.1016/j.patcog.2016.10.017.
  11. Ghosh, J. Cluster ensembles / J.  Ghosh, A. Acharya // WIREs Data Mining Knowledge Discovery. – 2011. – Vol. 1. – P. 305-315. – DOI: 10.1002/widm.32.
  12. Пестунов, И.А. Ансамблевый алгоритм кластеризации больших массивов данных / И.А. Пестунов, В.Б. Бериков, Е.А. Куликова, С.А. Рылов // Автометрия. – 2011. – Т. 47, № 3. – С. 49-58.
  13. Пестунов, И.А. Иерархические алгоритмы кластеризации для сегментации мультиспектральных изображений / И.А. Пестунов, С.А. Рылов, В.Б. Бериков // Автометрия. – 2015. – Т. 51, № 4. – С. 12-22.
  14. Пестунов, И.А. Сегментация многоспектральных изображений на основе ансамбля непараметрических алгоритмов кластеризации / И.А. Пестунов, В.Б. Бериков, Ю.Н. Синявский // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. – 2010. – Т. 5(31). – С. 56-64.
  15. Hubert, L. Comparing partitions / L. Hubert, Ph. Arabie // Journal of Classification. – 1985. – Vol. 2. – P. 193-218.
  16. Strehl, A. Cluster ensembles – a knowledge reuse framework for combining multiple partitions / A. Strehl, J. Ghosh // The Journal of Machine Learning Research. – 2003. – Vol. 3. – P. 583-617. – DOI: 10.1162/153244303321897735.
  17. Meila, M. Comparing clusterings by the variation of information / M. Meila // Proceedings of 16th Conference on Learning Theory and 7th Kernel Workshop (COLT/Kernel 2003). – 2003. – P. 173-187.
  18. Wu, J. External validation measures for k-means clustering: A data distribution perspective / J. Wu, J. Chen, H. Xiong, M. Xie // Expert Systems with Applications. – 2009. – Vol. 36, Issue 3, Part 2. – P. 6050-6061. – DOI: 10.1016/j.eswa.2008.06.093.
  19. mlbench: Machine Learning Benchmark Problems [Электронный ресурс]. – URL: https://cran.r-project.org/web/pac­kages/mlbench/index.html (дата обращения 02.03.17).
  20. Hyperspectral Remote Sensing Scenes [Электронный ресурс]. – URL: http://www.ehu.eus/ccwintco/index.php?title=Hyper­spectral_Remote_Sensing_Scenes (дата обращения 02.03.17).
  21. Hossam, M.A. Accelerated hyperspectral image recursive hierarchical segmentation using GPUs, multicore CPUs, and hybrid CPU/GPU cluster / M.A. Hossam, H.M. Ebied, M.H. Abdel-Aziz, M.F. Tolba // Journal of Real-Time Image Processing. – 2014. – P. 1-20. – DOI: 10.1007/s11554-014-0464-4.
  22. Рылов, С.А. Использование графических процессоров NVIDIA при кластеризации мультиспектральных данных сеточным алгоритмом CCA / С.А. Рылов, И.А. Пес­тунов // Интерэкспо ГЕО-Сибирь. – 2015. – Т. 4, № 2. – С. 51-56.
  23. Chang, D. Compute pairwise Euclidean distances of data points with GPUs / D. Chang, N.A. Jones, D. Li, M. Ouyang, R.K. Ragade // Proceedings of the IASTED International Symposium Computational Biology and Bioinformatics (CBB 2008). – 2008. – P. 278-283.

© 2009, IPSI RAS
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20