МЕТОД ВЫБОРА НАЧАЛЬНЫХ ПРИБЛИЖЕНИЙ ЦЕНТРОВ КЛАСТЕРОВ ДЛЯ АЛГОРИТМА К-СРЕДНИХ
Abstract
Разрабатывается метод поиска начальных приближений центров кластеров для алгоритма
К-средних, который позволяет сократить количество итераций алгоритма К-средних в 2,9 раза по сравнению с существующими методами. Нулевые кластеры в ходе обработки данных отсутствуют. Вычислительная сложность процедуры кластеризации в целом у предложенного метода меньше, чем у существующих методов, так как алгоритм К-средних в процедуре выбора начальных приближений не используется. В отличие от других методов ошибка кластеризации контролируется на стадии выбора начальных приближений. Также точность кластеризации увеличивается за счет того, что начальные приближения выбираются по всем существенным признакам исходного набора данных и выполняется замена полученных значений начальных приближений ближайшими элементами исходного набора данных.
About the Authors
В. Загребнюк
Одесская национальная академия связи им. А.С. Попова
Ukraine
Ukraine
В. Кумыш
Одесская национальная академия связи им. А.С. Попова
Ukraine
Ukraine
References
1. MacQueen, J.B. Some methods for classification and analysis of multivariate observations /
2. J.B. MacQueen // Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. – Berkley : University of California Press, 1967. – Vol. 1. – Р. 281–297.
3. Bradley, P.S. Refining initial points for k-means clustering / P.S. Bradley, U.M. Fayyad //
4. Proceedings 15th International Conf. on Machine Learning. – San Francisco, CA, 1998. – Р. 91–99.
5. Pena, J. An Empirical comparison of four initialization methods for the k-means algorithm /
6. J. Pena, J. Lozano, P. Larranaga // Pattern Recognition Letters. – 1999. – Vol. 20. – P. 1027–1040.
7. Likas, A. The Global k-means Clustering algorithm / A. Likas, N. Vlassis, J.J. Verbeek //
8. Pattern Recognition. – 2003. – Vol. 36. – P. 451–461.
9. Khan, S.S. Cluster Center Initialization for K-mean Clustering / S.S. Khan, A. Ahmad //
10. Pattern Recognition Letters. – 2004. – Vol. 25. – P. 1293–1302.
11. Al-Daoud, M.B. A New Algorithm for Cluster Initialization / M.B. Al-Daoud // Proceedings
12. of World Academy of science, engineering and technology. – 2005. – Vol. 4. – P. 74–76.
13. Deelers, S. Enhancing K-Means Algorithm with Initial Cluster Centers Derived from Data
14. Partitioning along the Data Axis with the Highest Variance / S. Deelers, S. Auwatanamongkol //
15. Proceedings of World Academy of science, engineering and technology. – 2007. – Vol. 26. –
16. Р. 323–328.
17. Babu, G. A near optimal initial seed value selection in k-means algorithm using a genetic
18. algorithm / G. Babu, M. Murty // Pattern Recognition Letters. – 1993. – Vol. 14. – P. 763–769.
19. Berkeley Segmentation Dataset [Electronic resource]. – Мode of access : http://www.eecs.
20. berkeley.edu/Research/Projects/CS/vision/grouping/segbench. – Date of access : 05.10.2009.
Review
For citations:
, . Informatics. 2010;(1(25)):32-40. (In Russ.)
Views: 559
Email this article 