26. Використання дерев рішень в сппр.

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

Процес конструювання дерева рішень.Алгоритми конструювання дерев рішень складаються з етапів:

1. Побудови або створення дерева (treebuilding) – на даному етапі вирішуються питання вибору критерію розщеплювання і зупинки навчання (якщо це передбачено алгоритмом).

2. Скорочення дерева (treepruning) – дозволяє відсікти деякі гілки дерева.

Складові дерева рішень:

1. Корінь дерева.

2. Гілки дерева.

3. Внутрішні вузли (вузли перевірки).

4. Вершина дерева або Вузли рішення або Кінцевий вузол дерева.

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

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

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

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

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

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

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

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

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

• невеликі об’єми вхідної вибірки об’єктів;

• наочність результатів;

• висока якість кластеризації;

• не потрібно наперед визначати кількість кластерів.

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

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

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

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

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

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

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

• простота використання;

• швидкість використання;

• зрозумілість і прозорість алгоритму.

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