Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів
DOI:
https://doi.org/10.35681/1560-9189.2012.14.1.311801Ключові слова:
кодові книги, кластеризація, k-середніх, центроїди, kd-дереваАнотація
Розглянуто один із варіантів розв’язку задачі кластеризації на основі алгоритму k-середніх, який широко застосовується в багатьох сферах науки і техніки. Головними недоліками алгоритму k-середніх є залежність результатів кластеризації від вибору початкової конфігурації центроїдів (ініціалізації) та збіжність до локального мінімуму цільової функції. Запропонований в роботі вдосконалений метод k-середніх дозволяє отримати розв’язок, наближений до глобального мінімуму спотворення шляхом послідовного запуску k-середніх для 1,2,...,k центроїдів. Значне прискорення роботи досягається за рахунок обчислення відстаней лише до активних центроїдів, а також зменшення кількості векторів-кандидатів на вибір місця початкового розташування нового центроїду. Перевага даного підходу суттєво зростає за великих обсягів даних і зі збільшенням розмірності. Запропонований алгоритм доцільно використовувати в задачах кластеризації мовленнєвих даних при створенні кодових книг.
Посилання
Arthur D., Vassilvitskii S. k-Means++: The Advantages of Careful Seeding / ACM- SIAM Symposium on Discrete Algorithms (SODA 2007) Astor Crowne Plaza. — New Orleans (Louisiana). — 2007. — pp. 1–11.
Lai Jim Z.C., Huang Tsung-Jen, Liaw Yi-Ching Fast k-Means Clustering Algorithm Using Cluster Center Displacement / Pattern Recognition. — 2009. — N42(11).
Likas A., Vlassis N., Verbeek J. The Global k-Means Clustering Algorithm / Aristidis Likas // Pattern Recognition. — 2003. — Vol. 36, N2.
Hussein N. A Fast Greedy k-Means Algorithm / Master’s Thesis Nr: 9668098 // University of Amsterdam Faculty of Mathematics, Computer Sciences, Physics and Astronomy Euclides Building Plantage Muidergracht 24. — November, 2002.
Alsabti K., Ranka S., Singh V. An Efficient k-Means Clustering Algorithm / In Proc. of the First Workshop on High Performance Data Mining. — Orlando, FL. — March, 1998.
Pelleg D., Moore A. Accelerating Exact k-Means Algorithms with Geometric Reasoning / Technical Report CMU-CS-00105. — Carnegie Mellon University/ — Pittsburgh, PA.
Kanungo T., Mount D.M., Netanyahu N.S. et al. A Local Search Approximation Algorithm for k-Means Clustering / Computational Geometry: Theory and Applications. — 2004. — N 2. — P. 89– 112.
Tkachenko O.M., Feferman O.D., Khrushchak S.V. Efektyvne vektorne kvantuvannya LSF-parametriv pry ushchilnenni movnykh syhnaliv / Informatsiyni tekhnolohiyi ta kompyuterna inzheneriya. — 2007. — № 1. — pp. 124–129.
