IPRI - www.ipri.kiev.ua -  IPRI - www.ipri.kiev.ua -
Раздел [RUS]
Регистрация, хранение и обраб. данных. — 2012. — Т. 14, № 1.
[UKR]
Реєстрація, зберігання і оброб. даних. — 2012. — Т. 14, № 1.
[ENG]
Data Rec., Storage & Processing. — 2012. — Vol. 14, N 1.
Страницы 25-34
PDF, full text
Заглавие [RUS]
Метод кластеризации на основе последовательного запуска k-средних с вычислением расстояний до активных центроидов
[UKR]
Метод кластеризації на основі послідовного запуску k- середніх з обчисленням відстаней до активних центроїдів
[ENG]
The Clustering Method Based on the Consequential Running of k-Means with Calculation of the Distances to the Active Centroids
Авторы [RUS]
Ткаченко А.Н., Биличенко Н.А., Грийо Тукало О.Ф., Дзись А.В.
[UKR]
Ткаченко О.М., Біліченко Н.О., Грійо Тукало О.Ф., Дзісь О.В.
[ENG]
Tkachenko O.M., Bilichenko N.O., Griyo Tukalo O.F., Dzis O.V.
Аннотация [RUS]
Рассмотрен один из вариантов решения задачи кластеризации на основе алгоритма k-средних, который широко применяется во многих областях науки и техники. Главными недостат-ками алгоритма k-средних являются зависимость результатов кластеризации от выбора начальной конфигурации центроидов (инициализации) и сходимость к локальному минимуму целевой функции. Предложенный в работе усовершенствованный метод k-средних позволяет получить решение, приближенное к глобальному минимуму искажения путем последовательного запуска k-средних для центроидов. Значительное ускорение работы достигается за счет вычисления расстояний только к активным центроидам, а также уменьшения количества векторов-кандидатов на выбор места первоначального расположения нового центроида. Преимущество данного подхода существенно возрастает при больших объемах данных и с увеличением размерности. Предложенный алгоритм целесообразно использовать в задачах кластеризации речевых данных при создании кодовых книг. Ил.: 4. Библиогр.: 8 наим.
[UKR]
Розглянуто один із варіантів розв’язку задачі кластеризації на основі алгоритму k-середніх, який широко застосовується в багатьох сферах науки і техніки. Головними недоліками алгоритму k-середніх є залежність результатів кластеризації від вибору початкової конфігурації центроїдів (ініціалізації) та збіжність до локального мінімуму цільової функції. Запропонований в роботі вдосконалений метод k-середніх дозволяє отримати розв’язок, наближений до глобального мінімуму спотворення шляхом послідовного запуску k-середніх для 1,2,...,k центроїдів. Значне прискорення роботи досягається за рахунок обчислення відстаней лише до активних центроїдів, а також зменшення кількості векторів-кандидатів на вибір місця початкового розташування нового центроїду. Перевага даного підходу суттєво зростає за великих обсягів даних і зі збільшенням розмірності. Запропонований алгоритм доцільно використовувати в задачах кластеризації мовленнєвих даних при створенні кодових книг.
[ENG]
A variant of the clustering problem solution based on k-means algorithm is considered. This algo-rithm is widely used in many fields of science and technology. The main drawbacks of k-means algorithm are the clustering results dependence on the choice of the initial configuration of centroids (initialization) and convergence to local minimum of the objective function. The proposed improved k-means provides а solution close to the global minimum distortion by the sequential k-means running for centroids. A significant speed-up of operation is achieved by calculating the distances only to the active centroids and reducing the number of candidate vectors for the initial choice of the new centroid location. The advantage of this approach is more appreciable when a larger data set with higher dimension is used. The proposed algorithm should be used in the speech data clustering problems when creating code books. Fig.: 4. Refs: 8 titles.
Ключевые слова [RUS]
кодовые книги, кластеризация, k-средних, центроиды, kd-деревья.
[UKR]
кодові книги, кластеризація, k- середніх, центроїди, kd- дерева.
[ENG]
code books, clustering, k-means, centroids, kd-trees.
Ссылки
Файлы 2012-1-3.pdf