Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів

Abstract

Розглянуто один із варіантів розв’язку задачі кластеризації на основі алгоритму к-середніх, який широко застосовується в багатьох сферах науки і техніки. Головними недоліками алгоритму к-середніх є залежність результатів кластеризації від вибору початкової конфігурації центроїдів (ініціалізації) та збіжність до локального мінімуму цільової функції. Запропонований в роботі вдосконалений метод к-середніх дозволяє отримати розв'язок, наближений до глобального мінімуму спотворення шляхом послідовного запуску к-середніх для 1,2,...,к центроїїдів. Значне прискорення роботи досягається за рахунок обчислення відстаней лише до активних центроїдів, а також зменшення кількості векторів-кандидатів на вибір місця початкового розташування нового центроїду. Перевага даного підходу суттєво зростає за великих обсягів даних і зі збільшенням розмірності. Запропонований алгоритм доцільно використовувати в задачах кластеризації мовленнєвих даних при створенні кодових книг.

Рассмотрен один из вариантов решения задачи кластеризации на основе алгоритма к-средних, который широко применяется во многих областях науки и техники. Главными недостатками алгоритма к-средних являются зависимость результатов кластеризации от выбора начальной конфигурации центроидов (инициализации) и сходимость к локальному минимуму целевой функции. Предложенный в работе усовершенствованный метод к-средних позволяет получить решение, приближенное к глобальному минимуму искажения путем последовательного запуска к-средних для 1.2,...,к центроидов. Значительное ускорение работы достигается за счет вычисления расстояний только к активным центроидам, а также уменьшения количества векторов-кандидатов на выбор места первоначального расположения нового центроида. Преимущество данного подхода существенно возрастает при больших объемах данных и с увеличением размерности. Предложенный алгоритм целесообразно использовать в задачах кластеризации речевых данных при создании кодовых книг.

A variant of the clustering problem solution based on k-means algorithm is considered. This algorithm 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 a solution close to the global minimum distortion by the sequential k-means running for 1, 2,..., k 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.