Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів
Розглянуто один із варіантів розв’язку задачі кластеризації на основі алгоритму к-середніх, який широко застосовується в багатьох сферах науки і техніки. Головними недоліками алгоритму к-середніх є залежність результатів кластеризації від вибору початкової конфігурації центроїдів (ініціалізації) та...
Збережено в:
| Опубліковано в: : | Реєстрація, зберігання і обробка даних |
|---|---|
| Дата: | 2012 |
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/50557 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів / О.М. Ткаченко, Н.О. Біліченко, О.Ф. Грійо-Тукало, О.В. Дзісь // Реєстрація, зберігання і обробка даних. — 2012. — Т. 14, № 1. — С. 25-34. — Бібліогр.: 8 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859903392353091584 |
|---|---|
| author | Ткаченко, О.М. Біліченко, Н.О. Грійо-Тукало, О.Ф. Дзісь, О.В. |
| author_facet | Ткаченко, О.М. Біліченко, Н.О. Грійо-Тукало, О.Ф. Дзісь, О.В. |
| citation_txt | Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів / О.М. Ткаченко, Н.О. Біліченко, О.Ф. Грійо-Тукало, О.В. Дзісь // Реєстрація, зберігання і обробка даних. — 2012. — Т. 14, № 1. — С. 25-34. — Бібліогр.: 8 назв. — укр. |
| collection | DSpace DC |
| container_title | Реєстрація, зберігання і обробка даних |
| description | Розглянуто один із варіантів розв’язку задачі кластеризації на основі алгоритму к-середніх, який широко застосовується в багатьох сферах науки і техніки. Головними недоліками алгоритму к-середніх є залежність результатів кластеризації від вибору початкової конфігурації центроїдів (ініціалізації) та збіжність до локального мінімуму цільової функції. Запропонований в роботі вдосконалений метод к-середніх дозволяє отримати розв'язок, наближений до глобального мінімуму спотворення шляхом послідовного запуску к-середніх для 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.
|
| first_indexed | 2025-12-07T15:58:11Z |
| format | Article |
| fulltext |
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2012, Т. 14, № 1 25
УДК 621.39
О. М. Ткаченко, Н. О. Біліченко,
О. Ф. Грійо Тукало, О. В. Дзісь
Вінницький національний технічний університет
Хмельницьке шосе, 95, 21021 Вінниця, Україна
Метод кластеризації на основі послідовного
запуску k-середніх з обчисленням відстаней
до активних центроїдів
Розглянуто один із варіантів розв’язку задачі кластеризації на основі
алгоритму k-середніх, який широко застосовується в багатьох сферах
науки і техніки. Головними недоліками алгоритму k-середніх є залеж-
ність результатів кластеризації від вибору початкової конфігурації
центроїдів (ініціалізації) та збіжність до локального мінімуму цільової
функції. Запропонований в роботі вдосконалений метод k-середніх до-
зволяє отримати розв’язок, наближений до глобального мінімуму спо-
творення шляхом послідовного запуску k-середніх для k,...,2,1 центрої-
дів. Значне прискорення роботи досягається за рахунок обчислення
відстаней лише до активних центроїдів, а також зменшення кількос-
ті векторів-кандидатів на вибір місця початкового розташування но-
вого центроїду. Перевага даного підходу суттєво зростає за великих
обсягів даних і зі збільшенням розмірності. Запропонований алгоритм
доцільно використовувати в задачах кластеризації мовленнєвих даних
при створенні кодових книг.
Ключові слова: кодові книги, кластеризація, k-середніх, центроїди, kd-
дерева.
Вступ
Кластеризація даних є відомою науковою та практичною задачею, а саме: як
розподілити експериментально отримані набори векторів за групами, або класте-
рами. Кластеризація часто використовується, зокрема, при статистичному аналізі
даних, векторній квантизації, розпізнаванні образів тощо. В галузі ущільнення
мовлення алгоритми кластеризації застосовуються для створення кодових книг —
спеціальних таблиць, що містять найбільш репрезентативні набори даних.
Задачу кластеризації можна сформулювати так: заданий набір з n векторів,
кожен з яких має розмірність d ; необхідно розбити на підмножини відповідно до
© О. М. Ткаченко, Н. О. Біліченко, О. Ф. Грійо Тукало, О. В. Дзісь
О. М. Ткаченко, Н. О. Біліченко, О. Ф. Грійо Тукало, О. В. Дзісь
26
заданого критерію оптимізації. Як правило, таким критерієм є мінімізація спотво-
рення. Існують різні шляхи оцінювання спотворення, але в більшості прикладних
реалізацій використовують суму середньоквадратичних Евклідових відстаней між
вектором і центром кластера (центроїдом), до якого він належить.
Метод кластеризації k-середніх є найбільш розповсюдженим і найкраще до-
слідженим серед усіх методів кластеризації. Він мінімізує вищезгадане спотво-
рення, розподіляючи дані між регіонами, що не перетинаються та ідентифікують-
ся за їхніми центрами. Поширеність методу k-середніх зумовлено його головними
перевагами: простотою, гнучкістю, швидкою збіжністю. Проте привабливість ме-
тоду суттєво обмежується його недоліками, зокрема:
— результати кластеризації за методом k-середніх значною мірою залежать
від вибору початкової конфігурації центроїдів (ініціалізації);
— робота алгоритму суттєво уповільнюється під час кластеризації великих
обсягів даних;
— алгоритм може сходитися до локального мінімуму цільової функції.
Щоб позбутися цих недоліків було запропоновано низку модифікацій мето-
ду k-середніх. У методі k-середніх++ (k-means++) введено вдосконалену процеду-
ру ініціалізації, що дозволяє покращити результати кластеризації за рахунок спе-
ціального вибору початкової конфігурації центроїдів [1]. Для прискорення проце-
су обчислення відстаней від точок до центроїдів у [2] запропоновано відкидати з
розгляду статичні центроїди, тобто такі, що залишилися на своїх позиціях на по-
точній ітерації. З метою запобігання локальній збіжності в [3] запропоновано іте-
ративний алгоритм, що дозволяє наблизитися до глобального оптимуму шляхом
покрокового послідовного запуску k-середніх. У [4] даний метод було розвинуто
шляхом застосування особливої структури даних — kd-дерев, що дозволило сут-
тєво зменшити обчислювальну складність методу.
У даній роботі поєднуються переваги розглянутих підходів з метою вдоско-
налення методу кластеризації k-середніх, в якому розв’язок, що наближений до
глобального мінімуму, отримується шляхом послідовного запуску k-середніх для
k,...,2,1 центроїдів, і значне прискорення роботи досягається завдяки обрахову-
ванню відстаней лише до тих центроїдів, що змінили своє розташування на попе-
редній ітерації, а також зменшенню кількості векторів-кандидатів на вибір місця
початкового розташування нового центроїда.
Глобальний алгоритм k-середніх
Кластеризація за методом k-середніх розподіляє вхідний набір векторів по k
кластерах ( 1, 2,..., )i i k=S , з кожним з яких пов’язаний центроїд ic . Позначимо
множину вхідних векторів { } n== SxS , . Нехай ),( cxD — відстань між векто-
ром x та центроїдом c . У цій статті використовується незважена Евклідова від-
стань між вектором ( )dxxx ,...,, 21=x та центроїдом ( )dccc ,...,, 21=c :
( )å
=
-=
d
i
ii cx,D
1
22 )( cx .
Метод кластеризації на основі послідовного
запуску k-середніх з обчисленням відстаней до активних центроїдів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2012, Т. 14, № 1 27
Основу кластеризації за методом k-середніх складає процес перетворення
множини центроїдів в іншу множину, поліпшену за критерієм мінімізації спотво-
рення шляхом перерозподілу вхідних векторів між кластерами. Кластеризація
розпочинається з деякого початкового задання центроїдів, і процес перетворення
повторюється, поки не задовольняється умова завершення.
Позначимо множину центроїдів, отриманих на ітерації t , { }it cSC = . Алго-
ритм кластеризації k-середніх в його звичайному варіанті описується наступним
чином.
1. Встановлюємо 0=t та задаємо початкове розташування центроїдів 0SC .
2. Для заданої множини центроїдів tSC для отримання поліпшеної множини
центроїдів 1+tSC виконуємо пункти 2.1 та 2.2.
2.1. Знаходимо таке розбиття S , що розподіляє S по k кластерах
),...,2,1( kii =S та задовольняє умові:
{ }ijDD jii ¹"£= ),(),(| cxcxxS .
2.2. Обчислюємо центроїд ic для кожного кластера ),...,2,1( kii =S , щоб
отримати нову множину центроїдів 1+tSC :
1
1 ( ), 1,2,...,
im
i lj
li
c x j d
m =
= × =å , (1)
де im — кількість векторів, що належать кластеру iS .
3. Обчислюємо сумарне спотворення å
Î
=
S
DE
x
cx ),(22 для 1+tSC . Якщо воно
відрізняється від отриманого на попередній ітерації на достатньо малу величину,
припиняємо процес. В іншому випадку присвоюємо 1+¬ tt та повертаємося до
кроку 2.
Як зазначалося вище, наведеному алгоритму кластеризації k-середніх при-
таманні певні недоліки. З метою їхнього подолання в [3] запропоновано вдоско-
налений варіант кластеризації k-середніх, названий авторами жадібним глобаль-
ним алгоритмом k-середніх (greedy global k-means algorithm). В його основі ле-
жить припущення, що глобальний оптимум може бути досягнутий шляхом запус-
ку k-середніх, коли )1( -k центроїд розташований в оптимальних позиціях, що от-
римані як розв’язок задачі кластеризації для )1( -k центроїда, а k -й центроїд має
бути розміщений у відповідній позиції, яку й треба визначити. Оптимальну клас-
теризацію для 1=k легко отримати, обчисливши координати першого центроїда
як середньоарифметичне відповідних координат усіх векторів множини S . Таким
чином, реалізація даного підходу для отримання k центроїдів потребує послідов-
ного запуску k-середніх для k,...,2,1 центроїдів. Окремо слід зазначити, що пошук
належної позиції і-го центроїда, яка є невідомою, коли відомі позиції попередніх
О. М. Ткаченко, Н. О. Біліченко, О. Ф. Грійо Тукало, О. В. Дзісь
28
)1( -i центроїдів, потребує запуску k-середніх для кожного вектора Xx Îi , який
розглядається як кандидат на позицію вставки нового центроїда. Остаточно виби-
рається той варіант, який забезпечує мінімальне сумарне спотворення для всіх i
центроїдів.
Метод k-середніх з обчисленням відстаней до активних центроїдів
Неважко показати, що, на відміну від звичайної кластеризації k-середніх,
складність якої оцінюється як )(nkO , складність жадібного глобального алгорит-
му k-середніх становить )( 22knO . Це означає, що для практичних застосувань, де
кількість векторів складає кілька десятків або сотень тисяч, а кількість кластерів
— кілька тисяч, час роботи алгоритму є занадто тривалим. Тому в [3] було запро-
поновано для пошуку належної позиції i -го центроїда обмежитися вибором того
вектора, який забезпечує мінімальне спотворення при додаванні його як початко-
вої позиції нового центроїда замість запуску k-середніх для кожного вектора. Крім
того, зменшення обчислювальної складності можливо за рахунок використання
kd-дерев для генерації нових центроїдів, а також для знаходження центроїда, най-
ближчого до даного вектора [5, 6].
У даній роботі пропонується інший підхід, що має на меті зменшення часу
роботи глобального алгоритму k-середніх.
Насамперед відзначимо, що найбільш трудомісткою складовою частиною
обчислень є знаходження центроїда, найближчого до даного вектора, оскільки це
потребує обчислення відстаней від кожного вектора до кожного центроїда. Проте
в міру роботи алгоритму відносно невелика частка центроїдів змінюють свої по-
ложення, а більшість з них залишається на своїх позиціях. Надалі будемо назива-
ти центроїди, що змінюють своє положення на ітерації t , активними, а ті центрої-
ди, які залишаються на своїх позиціях — пасивними. Відповідні множини позна-
чимо як )(a
tSC та )( p
tSC . Таким чином, якщо зберігати для кожної точки відстані
до всіх центроїдів на ітерації t , на ітерації 1+t достатньо обчислити відстані ли-
ше до активних центроїдів )(a
tSC . При цьому виграш у часі буде тим більший, чим
менша відносна частка tr активних центроїдів серед усіх центроїдів на ітерації t :
t
a
t
tr SC
SC )(
= , (2)
де )(a
tSC та tSC — потужності множин )(a
tSC та tSC відповідно.
Для досліджень у галузі ущільнення мовлення типовою є ситуація, коли для
створення кодових книг розміром 1024–4096 центроїдів використовуються трену-
вальні набори, що складаються з 60000–200000 векторів.
На рис. 1 показано, як змінюється доля активних центроїдів r із зростанням
загальної кількості центроїдів SC , яка отримана в результаті кластеризації 75000
векторів розмірністю 5=d . Дані по обох осях наведено у логарифмічному масш-
Метод кластеризації на основі послідовного
запуску k-середніх з обчисленням відстаней до активних центроїдів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2012, Т. 14, № 1 29
табі. Для згладжування кривої, що представлена на рис. 1, дані усереднювалися за
1000 ітерацій.
Рис. 1. Залежність долі активних центроїдів від загальної кількості центроїдів
Як можна побачити, в міру зростання SC від 2 до 40000, r поступово змен-
шується від 0,9 до 0,0012. Середня доля активних центроїдів avr складає приблиз-
но 0,015. Таким чином, кількість обчислень відстаней має зменшитися в 50–100
разів порівняно з глобальним алгоритмом k-середніх. Важливо відзначити, що
центри кластерів не будуть відрізнятися від тих, що отримані при застосуванні
алгоритму глобальної кластеризації.
Разом з тим слід зауважити, що зазначений виграш у швидкодії досягається
за рахунок суттєвого збільшення витрат пам’яті, оскільки для кожного вектора
необхідно зберігати відстані до всіх центроїдів. Проте ці витрати можна значно
скоротити, якщо для кожного вектора зберігати відстані не до всіх, а тільки до m
найближчих центроїдів.
Позначимо положення і-го центроїда на поточній та наступній ітераціях від-
повідно як ic та i¢c . Нехай { }mcccW ,...,, 21= — множина центроїдів, найближчих
до вектора x на поточній ітерації. Позначимо maxD максимальну з відстаней від
вектора x до центроїдів з W : max ( , ) ( , ) , , , 1,2,...,i jD D x c D x c j i i j m= ³ " ¹ = . Не-
хай W складається з активних )(aW і пасивних )( pW центроїдів. Таким чином,
)()( pa WWW U= . Пропонується обирати центроїд, найближчий до точки x , з
множини WWSCWSC UU
)()()()( \ aapa = . Для кожного кластера ( )a
i Îc SC обчи-
слюється відстань ),( iD cx . Якщо max),( DD i <cx , центроїд ic включається до
WWW Utt = . Найближчий до вектора x центроїд jc вибирається з tW , виходя-
О. М. Ткаченко, Н. О. Біліченко, О. Ф. Грійо Тукало, О. В. Дзісь
30
чи з умови jiDD ij ¹"£ ,),(),( cxcx . Після цього з tW формується множина W з
m центроїдів, найближчих до вектора x для наступної ітерації.
При даному підході може виникати помилка у визначенні найближчого
центроїда, що ілюструється на рис. 2 для 2=m . Припустимо, найближчі до x
центроїди 1c та 2c будуть активними та пересунуться на позиції 1¢c та 2¢c відпо-
відно, в результаті чого найближчим до x стане пасивний центроїд jc , відстань
до якого не зберігалась і не обчислювалася. Проте найближчим до x буде вважа-
тися центроїд 1¢c .
Рис. 2. Можлива помилка при визначенні найближчого центроїда
Припускаючи, що події є незалежними, ймовірність )(erp такої помилки на
ітерації t для заданої величини m можна оцінити як
)()(
1
)()()( Õ
=
Î×Î=
m
i
a
ti
p
tj
er
t ppp SCcSCc . (3)
Замінюючи ймовірності в (3) на їхні статистичні оцінки ( )( )p
i tp Îc SC =
( )p
t
t
=
SC
SC
,
t
a
ta
tip
SC
SC
SCc
)(
)( )( =Î , з урахуванням (2) отримаємо:
m
tt
m
i t
a
t
t
a
tt
m
i t
a
t
t
p
ter
t rrp ×-=×
-
=×= ÕÕ
==
)1(
1
)()(
1
)()(
)(
SC
SC
SC
SCSC
SC
SC
SC
SC
. (4)
Функція (4) має максимум при
1+
=
m
mrt , який дорівнює 1
)(
max )1( ++
= m
m
er
m
mp .
Метод кластеризації на основі послідовного
запуску k-середніх з обчисленням відстаней до активних центроїдів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2012, Т. 14, № 1 31
При 0,015avr = ( ) 0,985 0,015er m
avp = × . Таким чином, обираючи, наприклад, 4=m ,
можна отримати 1105 8)( <<×» -er
avp .
Метод k-середніх з обчисленням відстаней до активних центроїдів полягає в
наступному.
1. Визначаємо множину точок SÌ}{ 0x , що будуть використовуватися для
визначення початкової позиції для вставки нового центроїда.
2. Присвоївши 1=k , обчислюємо координати першого центроїда як середнє
значення координат усіх векторів:
1
1 , 1, 2,...,
n
kj ij
i
c x j d
n =
= × =å .
3. Виконуємо 1k k¬ + і знаходимо початкову позицію для вставки центро-
їда kc шляхом вибору вектора }{ 0xxÎ , що забезпечує мінімальне спотворення
å
Î
=
S
DE
x
cx ),(22 .
4. Запускаємо алгоритм k-середніх для k центроїдів, для чого виконуємо
кроки 4.1–4.3.
4.1. Розділяємо множину SC на підмножини )(aSC та )( pSC , що складають-
ся відповідно з активних і пасивних центроїдів.
4.2. Для кожного вектора SÎx визначаємо { }mcccW ,...,, 21= , що містить
множину з m найближчих до х центроїдів. Для кожного )(a
i SCc Î обчислюємо
відстань ),( ii Dr cx= . Якщо Wc Îi , корегуємо відповідне значення відстані ir .
Якщо Wc Ïi , перевіряємо виконання умови maxrri < , де max max ( , ) ,jj
r D x c=
1,2,...,j m= . Якщо умова виконується, додаємо ic до множини W .
4.3. Використовуючи (1), обчислюємо нове положення центроїдів. Якщо
умова збіжності не виконується, повертаємося до 4.1.
4.4. Перевіряємо, чи отримано задану кількість центроїдів maxk . Якщо
maxk k< , повертаємося до 3.
Наведений метод потребує додаткових витрат пам’яті для зберігання індек-
сів m найближчих центроїдів і відстаней до них для кожного вектора.
Крім того, для прискорення перевірки Wc Îi пошук відповідного елемента
можна організувати за допомогою хешування, що також потребує додаткової
пам’яті.
Як видно з рис. 1, з урахуванням (4), для виконання ( ) 1 consterp << » зна-
чення m має бути більшим для малих k та меншим для великих значень k . Про-
те невелике число 4=m дозволяє уникнути збільшення спотворення та може бу-
ти рекомендовано для практичного застосування. Вибір множини }{ 0x у пункті 1
може виконуватися за схемою, що застосовується в алгоритмі k-means ++.
О. М. Ткаченко, Н. О. Біліченко, О. Ф. Грійо Тукало, О. В. Дзісь
32
Експериментальні результати
Ефективність запропонованого в даній статті алгоритму кластеризації з об-
численням відстані тільки до активних центроїдів (Distance Calculation to Active
Centroids, DCAC) оцінювалася за середнім спотворенням в перерахунку на один
вхідний вектор та часом роботи алгоритму. Досліджувався вплив кількості векто-
рів з вхідного набору на похибку та час кластеризації.
Запропонований алгоритм порівнювався з двома модифікаціями алгоритму
k-середніх: класичним алгоритмом k-середніх (надалі k-means), реалізованим в
MATLAB без обмеження кількості ітерацій, та реалізованим на основі kd-дерев з
максимальною кількістю ітерацій 500 (надалі hybrid), запропонованим у [7]. Спе-
цифіка алгоритму hybrid полягає в тому, що для наближення до глобального міні-
муму в ньому поєднано класичний алгоритм k-середніх і локальний пошук (обмін
між існуючими центроїдами та кандидатами на центроїди за умови, що такий об-
мін призводить до зменшення середнього спотворення). Дослідження проводило-
ся на наборі векторів LSF-параметрів [8], які отримані з мовленнєвої бази даних
TIMIT. Всі обчислення виконувалися на комп’ютері Intel Core 2 2.0 GHz з 2 Гб
пам’яті.
На рис. 3 показано, як змінюється середнє спотворення для різних значень
вхідних векторів 5- та 10-вимірної розмірності (відповідно рис. 3,а та 3,б). Кіль-
кість векторів змінюється у діапазоні від 10000 до 100000, кількість згенерованих
центроїдів — 4000. Оскільки алгоритм k-середніх передбачає велику кількість об-
числень відстаней, які можна виконувати одночасно, DCAC також було реалізо-
вано з розпаралелюванням операцій. Введемо позначення, що використовуються
на нижче наведених рис. 3 та 4: 1 — k-means; 2 — hybrid; 3 — DCAC; 4 — DCAC
з розпаралелюванням.
а) б)
Рис. 3. Залежність середнього спотворення від кількості вхідних векторів: а) d = 5; б) d = 10
З аналізу графіків можна зробити висновок, що в усіх трьох алгоритмах се-
реднє спотворення повільно зростає. Найбільше спотворення виникає при засто-
суванні алгоритму кластеризації на основі kd-дерев, інші два алгоритми відрізня-
Метод кластеризації на основі послідовного
запуску k-середніх з обчисленням відстаней до активних центроїдів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2012, Т. 14, № 1 33
ються несуттєво. Зі зростанням розмірності характер залежності майже не змінив-
ся, абсолютні ж значення спотворення зросли на порядок.
Ще одним важливим критерієм оцінювання алгоритму є час його роботи.
Залежність часу роботи від кількості векторів у вхідному наборі наведено на рис.
4 для розмірностей 5=d і 10=d (відповідно рис. 4,а та 4,б). Масштаб по осі ор-
динат логарифмічний.
а) б)
Рис. 4. Залежність часу роботи алгоритмів від кількості вхідних векторів: а) d = 5; б) d = 10
Очевидно, що при збільшенні кількості вхідних векторів час роботи алгори-
тмів зростає. Найбільш стрімке зростання спостерігається для алгоритму, що реа-
лізований у MATLAB. При застосуванні kd-дерев час на обробку 10000 векторів є
найбільшим, але зі збільшенням кількості векторів час його роботи зростає най-
повільніше, і для 5=d (рис. 4,а) після проходження точки в 50000 векторів є
меншим, ніж у запропонованого в даній статті без розпаралелювання. Часові по-
казники алгоритму DCAC з розпаралелюванням є найкращими.
Зі збільшенням розмірності для алгоритму з використанням kd-дерев спо-
стерігається стрімке зростання часу роботи, що зумовлено експоненціальним ха-
рактером залежності часу від розмірності. Проте для великої кількості вхідних
векторів часові показники його роботи є кращими за MATLAB, але поступаються
алгоритму DCAC. Зазначимо, що ефективність алгоритму DCAC практично не
залежить від розмірності.
Висновки
Запропонований в роботі вдосконалений метод k-середніх дозволяє отрима-
ти розв’язок, що наближений до глобального мінімуму спотворення. В середньо-
му похибка кластеризації складає на 10–15 % менше, ніж при використанні алго-
ритму hybrid і знаходиться приблизно на тому ж рівні, що при використанні алго-
ритму k-means (MATLAB). За швидкістю роботи запропонований алгоритм дає
результати кращі в 10–15 разів, ніж алгоритм k-means (MATLAB), що є особливо
важливим під час кластеризації великих обсягів даних. Порівняння з реалізацією
О. М. Ткаченко, Н. О. Біліченко, О. Ф. Грійо Тукало, О. В. Дзісь
34
k-середніх на основі kd-дерев показує, що швидкість роботи представленого алго-
ритму є вищою, якщо відношення кількості точок до розмірності складає менше
20000. Вказані характеристики свідчать про доцільність використання наведеного
алгоритму в задачах кластеризації мовленнєвих даних при створенні кодових
книг.
1. Arthur D. k-Means++: The Advantages of Careful Seeding / D. Arthur, S. Vassilvitskii // ACM-
SIAM Symposium on Discrete Algorithms (SODA 2007) Astor Crowne Plaza. — New Orleans
(Louisiana). — 2007. — P. 1–11.
2. Lai Jim Z.C. Fast k-Means Clustering Algorithm Using Cluster Center Displacement / Jim Z. C.
Lai, Tsung-Jen Huang, Yi-Ching Liaw // Pattern Recognition. — 2009. — N 42(11).
3. Likas A. The Global k-Means Clustering Algorithm / Aristidis Likas, Nikos Vlassis, Jacob J.
Verbeek // Pattern Recognition. — 2003. — Vol. 36, N 2.
4. 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.
5. Alsabti K. An Efficient k-Means Clustering Algorithm / Khaled Alsabti, Sanjay Ranka, Vineet
Singh // In Proc. of the First Workshop on High Performance Data Mining. — Orlando, FL. — March,
1998.
6. Pelleg D. Accelerating Exact k-Means Algorithms with Geometric Reasoning / Dan Pelleg, An-
drew Moore // Technical Report CMU-CS-00105. — Carnegie Mellon University/ — Pittsburgh, PA.
7. A Local Search Approximation Algorithm for k-Means Clustering / [T. Kanungo, D.M. Mount,
N.S. Netanyahu et al.] // Computational Geometry: Theory and Applications. — 2004. — N 2. — P. 89–
112.
8. Ткаченко О.М. Ефективне векторне квантування LSF-параметрів при ущільненні мовних
сигналів / О.М. Ткаченко, О.Д. Феферман, С.В. Хрущак // Інформаційні технології та комп’ютерна
інженерія. — 2007. — № 1. — С. 124–129.
Надійшла до редакції 23.01.2012
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/h/Huang:Tsung=Jen.html
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/l/Liaw:Yi=Ching.html
|
| id | nasplib_isofts_kiev_ua-123456789-50557 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1560-9189 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:58:11Z |
| publishDate | 2012 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | dspace |
| spelling | Ткаченко, О.М. Біліченко, Н.О. Грійо-Тукало, О.Ф. Дзісь, О.В. 2013-10-23T19:25:41Z 2013-10-23T19:25:41Z 2012 Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів / О.М. Ткаченко, Н.О. Біліченко, О.Ф. Грійо-Тукало, О.В. Дзісь // Реєстрація, зберігання і обробка даних. — 2012. — Т. 14, № 1. — С. 25-34. — Бібліогр.: 8 назв. — укр. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50557 621.39 Розглянуто один із варіантів розв’язку задачі кластеризації на основі алгоритму к-середніх, який широко застосовується в багатьох сферах науки і техніки. Головними недоліками алгоритму к-середніх є залежність результатів кластеризації від вибору початкової конфігурації центроїдів (ініціалізації) та збіжність до локального мінімуму цільової функції. Запропонований в роботі вдосконалений метод к-середніх дозволяє отримати розв'язок, наближений до глобального мінімуму спотворення шляхом послідовного запуску к-середніх для 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. uk Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Математичні методи обробки даних Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів Метод кластеризации на основе последовательного запуска к-среднпх с вычислением расстояний до активных центроидов The Clustering Method Based on the Consequential Running of k-Means with Calculation of the Distances to the Active Centroids Article published earlier |
| spellingShingle | Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів Ткаченко, О.М. Біліченко, Н.О. Грійо-Тукало, О.Ф. Дзісь, О.В. Математичні методи обробки даних |
| title | Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів |
| title_alt | Метод кластеризации на основе последовательного запуска к-среднпх с вычислением расстояний до активных центроидов The Clustering Method Based on the Consequential Running of k-Means with Calculation of the Distances to the Active Centroids |
| title_full | Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів |
| title_fullStr | Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів |
| title_full_unstemmed | Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів |
| title_short | Метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів |
| title_sort | метод кластеризації на основі послідовного запуску k-середніх з обчисленням відстаней до активних центроїдів |
| topic | Математичні методи обробки даних |
| topic_facet | Математичні методи обробки даних |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50557 |
| work_keys_str_mv | AT tkačenkoom metodklasterizacíínaosnovíposlídovnogozapuskukseredníhzobčislennâmvídstaneidoaktivnihcentroídív AT bílíčenkono metodklasterizacíínaosnovíposlídovnogozapuskukseredníhzobčislennâmvídstaneidoaktivnihcentroídív AT gríiotukaloof metodklasterizacíínaosnovíposlídovnogozapuskukseredníhzobčislennâmvídstaneidoaktivnihcentroídív AT dzísʹov metodklasterizacíínaosnovíposlídovnogozapuskukseredníhzobčislennâmvídstaneidoaktivnihcentroídív AT tkačenkoom metodklasterizaciinaosnoveposledovatelʹnogozapuskaksrednphsvyčisleniemrasstoâniidoaktivnyhcentroidov AT bílíčenkono metodklasterizaciinaosnoveposledovatelʹnogozapuskaksrednphsvyčisleniemrasstoâniidoaktivnyhcentroidov AT gríiotukaloof metodklasterizaciinaosnoveposledovatelʹnogozapuskaksrednphsvyčisleniemrasstoâniidoaktivnyhcentroidov AT dzísʹov metodklasterizaciinaosnoveposledovatelʹnogozapuskaksrednphsvyčisleniemrasstoâniidoaktivnyhcentroidov AT tkačenkoom theclusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids AT bílíčenkono theclusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids AT gríiotukaloof theclusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids AT dzísʹov theclusteringmethodbasedontheconsequentialrunningofkmeanswithcalculationofthedistancestotheactivecentroids |