logo
DEK

27. Сутністьалгоритмівкластеризації та їхзастосування в сппр.

Кластеризації – це групування об’єктів по схожості їх властивостей. Кожний кластер складається з подібних об’єктів, а об’єктів різних кластерів суттєво різняться.

Алгоритм кластеризації – це функція y = f (x), яка будь-якому об’єкту xn ставить у відповідність кластер yn .

Розрізняють ієрархічні і неієрархічні алгоритми кластеризації.

Суть ієрархічної кластеризації полягає впослідовному об’єднанні менших кластерів у великі або розділенні великих кластерів на менші. Виходячи з цього ієрархічні методи поділяються на дві великі групи:

  1. Агломеративні методи (AgglomerativeNesting, AGNES) – ця група методівхарактеризується послідовним об’єднанням початкових елементів і відповіднимзменшенням числа кластерів.

  2. Дивізимні (подільні) методи (DivisiveAnalysis, DIANA) – ці методи є логічноюпротилежністю агломеративних методів. На початку роботи алгоритму всі належать одному кластеру, який на подальших кроках ділиться на менші кластери,в результаті утворюється послідовність розщеплених груп.

Ієрархічні алгоритми пов’язані з побудовою дендрограм (від грецького dendron –«дерево»), які є результатом ієрархічного кластерного аналізу.Дендрограма описує близькість окремих точок та кластерів один до одного, представляє в графічному вигляді послідовність об’єднання (розділення) кластерів.

Особливостями використання ієрархічних методів є:

При великій кількості спостережень ієрархічні методи кластерного аналізу не є ефективними. В таких випадках використовують неієрархічні методи, засновані на розділенні, які є ітеративними методами ділення початкової множини об’єктів.

В цій групі популярні алгоритми сімейства k-середніх (k-means, fuzzy c-means, Густафсон-Кесселя), які в якості цільової функції використовують суму квадратів відхилень координат об’єктів від центрів шуканих кластерів.

Алгоритм k-середніх будує k кластерів, розташованих на великих відстанях один від одного. Основний тип задач, які вирішує алгоритм k-середніх, – наявність припущень (гіпотез) щодо числа кластерів, при цьому вони повинні бути різні настільки, наскільки це можливо. Вибір числа k може базуватися на результатах попередніх досліджень, теоретичних міркуваннях або інтуїції.

Механізм дії алгоритму:

  1. Первинний розподіл об’єктів по кластерах – вибирається число k, і на першомукроці ці точки вважаються «центрами» кластерів.

  2. Ітеративний процес – обчислюються нові центри кластерів і об’єкти зновуперерозподіляються.

Переваги даного методу:

Використання у СППР (Карти Кохонена). Список галузей науки, де застосовується кластеризація, широкий: біологія, медицина, економіка, маркетинг тощо.