The Clustering Method Based on the Consequential Running of k-Means with Calculation of the Distances to the Active Centroids
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 (initia...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2012
|
| Теми: | |
| Онлайн доступ: | http://drsp.ipri.kiev.ua/article/view/311801 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Data Recording, Storage & Processing |
Репозитарії
Data Recording, Storage & Processing| id |
drspiprikievua-article-311801 |
|---|---|
| record_format |
ojs |
| spelling |
drspiprikievua-article-3118012024-09-22T23:29:39Z The Clustering Method Based on the Consequential Running of k-Means with Calculation of the Distances to the Active Centroids Метод кластеризации на основе последовательного запуска k-средних с вычислением расстояний до активных центроидов Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів Ткаченко, О. М. Біліченко, Н. О. Грійо Тукало, О. Ф. Дзісь, О. В. кодовые книги кластеризация k-средних центроиды kd-деревья code books clustering k-means centroids kd-trees кодові книги кластеризація k-середніх центроїди kd-дерева 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 а 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 cen- troid 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. Рассмотрен один из вариантов решения задачи кластеризации на основе алгоритма k-средних, который широко применяется во многих областях науки и техники. Главными недостатками алгоритма k-средних являются зависимость результатов кластеризации от выбора начальной конфигурации центроидов (инициализации) и сходимость к локальному минимуму целевой функции. Предложенный в работе усовершенствованный метод k-средних позволяет получить решение, приближенное к глобальному минимуму искажения путем последовательного запуска k-средних для 1, 2,..., k центроидов. Значительное ускорение работь достигается за счет вычисления расстояний только к активным центроидам, а также уменьшения количества векторов-кандидатов на выбор места первоначального расположения нового центроида. Преимущество данного подхода существенно возрастает при больших объёмах данных и с увеличением размерности. Предложенный алгоритм целесообразно использовать в задачах кластеризации речевых данных при создании кодовых книг. Розглянуто один із варіантів розв’язку задачі кластеризації на основі алгоритму k-середніх, який широко застосовується в багатьох сферах науки і техніки. Головними недоліками алгоритму k-середніх є залежність результатів кластеризації від вибору початкової конфігурації центроїдів (ініціалізації) та збіжність до локального мінімуму цільової функції. Запропонований в роботі вдосконалений метод k-середніх дозволяє отримати розв’язок, наближений до глобального мінімуму спотворення шляхом послідовного запуску k-середніх для 1,2,...,k центроїдів. Значне прискорення роботи досягається за рахунок обчислення відстаней лише до активних центроїдів, а також зменшення кількості векторів-кандидатів на вибір місця початкового розташування нового центроїду. Перевага даного підходу суттєво зростає за великих обсягів даних і зі збільшенням розмірності. Запропонований алгоритм доцільно використовувати в задачах кластеризації мовленнєвих даних при створенні кодових книг. Інститут проблем реєстрації інформації НАН України 2012-03-20 Article Article application/pdf http://drsp.ipri.kiev.ua/article/view/311801 10.35681/1560-9189.2012.14.1.311801 Data Recording, Storage & Processing; Vol. 14 No. 1 (2012); 25-34 Регистрация, хранение и обработка данных; Том 14 № 1 (2012); 25-34 Реєстрація, зберігання і обробка даних; Том 14 № 1 (2012); 25-34 1560-9189 uk http://drsp.ipri.kiev.ua/article/view/311801/302956 |
| institution |
Data Recording, Storage & Processing |
| baseUrl_str |
|
| datestamp_date |
2024-09-22T23:29:39Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
code books clustering k-means centroids kd-trees |
| spellingShingle |
code books clustering k-means centroids kd-trees Ткаченко, О. М. Біліченко, Н. О. Грійо Тукало, О. Ф. Дзісь, О. В. The Clustering Method Based on the Consequential Running of k-Means with Calculation of the Distances to the Active Centroids |
| topic_facet |
кодовые книги кластеризация k-средних центроиды kd-деревья code books clustering k-means centroids kd-trees кодові книги кластеризація k-середніх центроїди kd-дерева |
| format |
Article |
| author |
Ткаченко, О. М. Біліченко, Н. О. Грійо Тукало, О. Ф. Дзісь, О. В. |
| author_facet |
Ткаченко, О. М. Біліченко, Н. О. Грійо Тукало, О. Ф. Дзісь, О. В. |
| author_sort |
Ткаченко, О. М. |
| title |
The Clustering Method Based on the Consequential Running of k-Means with Calculation of the Distances to the Active Centroids |
| title_short |
The Clustering Method Based on the Consequential Running of k-Means with Calculation of the Distances to the Active Centroids |
| title_full |
The Clustering Method Based on the Consequential Running of k-Means with Calculation of the Distances to the Active Centroids |
| title_fullStr |
The Clustering Method Based on the Consequential Running of k-Means with Calculation of the Distances to the Active Centroids |
| title_full_unstemmed |
The Clustering Method Based on the Consequential Running of k-Means with Calculation of the Distances to the Active Centroids |
| title_sort |
clustering method based on the consequential running of k-means with calculation of the distances to the active centroids |
| title_alt |
Метод кластеризации на основе последовательного запуска k-средних с вычислением расстояний до активных центроидов Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів |
| description |
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 а 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 cen- troid 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. |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2012 |
| url |
http://drsp.ipri.kiev.ua/article/view/311801 |
| work_keys_str_mv |
AT tkačenkoom theclusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids AT bílíčenkono theclusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids AT gríjotukaloof theclusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids AT dzísʹov theclusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids AT tkačenkoom metodklasterizaciinaosnoveposledovatelʹnogozapuskaksrednihsvyčisleniemrasstoânijdoaktivnyhcentroidov AT bílíčenkono metodklasterizaciinaosnoveposledovatelʹnogozapuskaksrednihsvyčisleniemrasstoânijdoaktivnyhcentroidov AT gríjotukaloof metodklasterizaciinaosnoveposledovatelʹnogozapuskaksrednihsvyčisleniemrasstoânijdoaktivnyhcentroidov AT dzísʹov metodklasterizaciinaosnoveposledovatelʹnogozapuskaksrednihsvyčisleniemrasstoânijdoaktivnyhcentroidov AT tkačenkoom metodklasterizacíínaosnovíposlídovnogozapuskukseredníhzobčislennâmvídstanejdoaktivnihcentroídív AT bílíčenkono metodklasterizacíínaosnovíposlídovnogozapuskukseredníhzobčislennâmvídstanejdoaktivnihcentroídív AT gríjotukaloof metodklasterizacíínaosnovíposlídovnogozapuskukseredníhzobčislennâmvídstanejdoaktivnihcentroídív AT dzísʹov metodklasterizacíínaosnovíposlídovnogozapuskukseredníhzobčislennâmvídstanejdoaktivnihcentroídív AT tkačenkoom clusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids AT bílíčenkono clusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids AT gríjotukaloof clusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids AT dzísʹov clusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids |
| first_indexed |
2024-09-23T04:05:31Z |
| last_indexed |
2024-09-23T04:05:31Z |
| _version_ |
1819202444210470912 |