бою свого роду В«ембріонВ» кластера, що складається тільки з одного елемента.
. Для кожного запису вихідної вибірки визначається найближчий до неї центр кластеру.
. Виробляється обчислення центроїдів - центрів тяжіння кластерів. Це робиться шляхом визначення середнього для значень кожної ознаки всіх записів в кластері.
Кроки 3 та 4 повторюються до тих пір, поки виконання алгоритму не перериватиметься, або поки не буде виконана умова відповідно з деяким критерієм збіжності (найчастіше використовується сума квадратів помилок між центроїдом кластера і всіма увійшли до нього записами).
Зупинка алгоритму виробляється, коли кордони кластерів і розташування центроїдів перестають змінюватися, тобто на кожній ітерації в кожному кластері залишається один і той же набір записів. Алгоритм k-means зазвичай знаходить набір стабільних кластерів за кілька десятків ітерацій. [4]
.4.2 G-means
Одним з недоліків алгоритму k-means є відсутність чіткого критерію для вибору оптимального числа кластерів.
Щоб вирішити дану проблему, було розроблено велику кількість алгоритмів, що дозволяють виробляти автоматичний вибір числа кластерів, оптимального з точки зору того чи іншого критерію.
Одним з найпопулярніших алгоритм кластеризації з автоматичним вибором числа кластерів є G-means . У його основі лежить припущення про те, що кластерізуемие дані підпорядковуються деякого унімодальних закону розподілу, наприклад гауссовскому. Тоді центр кластера, який визначається як середнє значень ознак потрапили в нього об'єктів, може розглядатися як мода відповідного розподілу.
Якщо вихідні дані описуються унімодальних гауссовским розподілом із заданими середнім, то можна припустити, що всі вони відносяться до одного кластеру.
Якщо розподіл даних не гауссовское, то виконується поділ на два кластери. Якщо в цих кластерах розподілу виявляться близькі до гауссовскому, то в першому наближенні вважається, що k = 2 буде оптимальним. В іншому випадку будуються нові моделі з великим числом кластерів, і так до тих пір, поки розподілення у кожному з них не виявиться достатньо близьким до гауссовскому. Така модель і, відповідно, число кластерів в ній будуть вважатися оптимальними.
Алгоритм G-means є ітеративним, де на кожному кроці за допомогою звичайного алгоритму k-means будується модель з певним числом кластерів (початкове значення k вибирається рівним 1), яке збільшується на кожній ітерації. Збільшення
