Метод пошуку згущень

Метод k-середніх

Метод k-середніх належить до групи ітеративних методів еталонного типу. Сама назва методу була запропонована Дж. Мак-Куіном у 1967 р.

На відміну від ієрархічних процедур метод k-середніх не вимагає обчислення і збереження матриці відстаней або подібностей між об'єктами. Алгоритм цього методу припускає використання тільки вихідних значень змінних. Для початку процедури класифікації повинні бути задані k випадково обраних об'єктів, що будуть служити еталонами, тобто центрами кластерів. Вважається, що алгоритми еталонного типу зручні і швидкодіючі. У цьому випадку важливу роль відіграє вибір початкових умов, що впливають на тривалість процесу класифікації і на його результати. Метод k-середніх зручний для обробки великих статистичних сукупностей.

Обчислювальні процедури більшості ітеративних методів класифікації зводяться до виконання таких кроків:

Крок 1. Вибір числа кластерів, на які повинна бути розбита сукупність, завдання первісної розбивки об'єктів і визначення центрів ваги кластерів.

Крок 2. Відповідно до обраних мір подібності визначення нового складу кожного кластера.

Крок 3. Після повного перегляду всіх об'єктів і розподілу їх по кластерах здійснюється перерахування центрів ваги кластерів.

Крок 4. Процедури 2 і 3 повторюються доти, поки наступна ітерація не дасть такий же склад кластерів, що і попередня.

Одним з ітеративних методів класифікації, не потребуючих завдання числа кластерів, є метод пошуку згущень. У теорії і на практиці існує кілька різних модифікацій цього методу. Кожна модифікація відрізняється початковим станом, що задається, і критеріями завершення класифікації.

Метод пошуку згущень вимагає обчислення матриці відстаней (або матриці мір подібності) між об'єктами. Потім вибирається об'єкт, що є первісним центром першого кластера. Вибір такого об'єкта може бути довільним, а може ґрунтуватися на попередньому аналізі точок і їхніх околів. Під час використання другого підходу можна значно скоротити число ітерацій, що приводять до розподілу всіх точок по кластерах.

Обрана точка приймається за центр гіперсфери заданого радіуса R. Визначається сукупність точок, що потрапили усередину цієї сфери, і для них обчислюються координати центра (вектор середніх значень ознак). Далі знову розглядаємо гіперсферу такого ж радіуса, але з новим центром, і для сукупності точок, що потрапили в неї, знову розраховуємо вектор середніх значень, приймаємо його за новий центр сфери і т. д. Коли чергове перерахування координат центра сфери приводить до такого ж результату, як і на попередньому кроці, переміщення сфери припиняється, а точки, що потрапили в неї, утворять кластер і з подальшого процесу кластеризації виключаються. Для всіх точок процедури, що залишилися, повторюються, тобто знову вибирається довільний об'єкт, що є первісним центром сфери радіуса R.

Таким чином, робота алгоритму завершується за кінцеве число кроків, і всі точки виявляються розподіленими по кластерах. Число кластерів, що утворилися, заздалегідь невідоме і сильно залежить від вибору радіуса сфери. Деякі модифікації алгоритму дозволяють розділити сукупність на задане число кластерів шляхом послідовної зміни радіуса сфери.

Дата добавления: 2014-11-29