Page 54 - Microsoft Word - Дисертація.docx

54

за заданим критерієм подібності/відмінності [54]. Як бачимо

формулювання завдання кластеризації практично співпадає з

формулюванням задачі сегментації зображень.

За способом виділення кластерів всі алгоритми автоматичної

класифікації можна розділити на дві великі групи - ієрархічні і

неієрархічні. Ієрархічні алгоритми дозволяють виявити вкладені

кластери. Для цього будується або дерево кластерів – дендрограма [55],

або так звана діаграма досяжності [56]. Неієрархічні алгоритми

обчислюють кластери, виходячи з оптимізації деякого заздалегідь

заданого (явно або неявно) критерію якості. Такі алгоритми можна

умовно розділити на три великі групи: методи розбиття, методи густини

і сіткові методи [54].

Методи розбиття засновані на поетапному поліпшенні деякого

початкового розбиття вихідної множини до отримання оптимального

значення деякої цільової функції. В якості цільової функції часто

використовується сума відстаней від об'єктів до центрів кластерів, до

яких вони віднесені. Основним недоліком методів розбиття, що

використовують цю цільову функцію, є те, що форма виділених ними

кластерів визначається обраною метрикою. На практиці це часто

призводить до явних помилок кластеризації і/або надмірної

роздробленості виділених кластерів. Крім того, методи розбиття не

здатні розглянути всі можливі розбиття і є ймовірність виявлення

локального, а не глобального екстремуму цільової функції.

Одним з перших методів розбиття запропонований алгоритм k-

середніх [57]. Його реалізації включені практично в усі пакети програм,

які призначені для аналізу зображень. Алгоритм дозволяє розбити

вихідну вибірку на N кластерів (N - параметр, що задається

користувачем). Отримані кластери описуються векторами середніх