Теоретичний вступ

Інститут гуманітарних та соціальних наук

Кафедра “Соціальних комунікацій та інформаційної діяльності

МЕТОДИЧНІ ВКАЗІВКИ

До лабораторної роботи №3

на тему „Індукція дерев рішень”

з курсу “Технології менеджменту знань”

для студентів, що навчаються за спеціальністю

8.18010015 „Консолідована інформація”

Львів - 2012

Мета лабораторної роботи полягає у вивченні алгоритму побудови дерева рішень та його застосування для розв’язування задач аналізу даних.

Теоретичний вступ

Дерево рішень – це деревовидний граф, у якому внутрішні вершини задають певну умову на значення атрибута, гілки визначають результат виконання умови, а листкові вершини задають класи чи розподіл класів, за якими визначається рішення. Початкова вершина дерева називається кореневим вузлом (коренем дерева). Типове дерево рішень зображено на рис.1. Це дерево описує поняття “покупець комп’ютера”, яке вказує на те, чи має намір покупець придбати комп’ютер. Внутрішні вершини зображені у вигляді прямокутників, листкові – у вигляді овалів.

Рис.1. Дерево рішень “покупець комп’ютера”.

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

Алгоритм індукції дерева рішень належить до класу “жадібних” алгоритмів. Він створює дерево рішень рекурсивно згори-донизу за принципом “поділяй та володарюй”. Наведемо кроки алгоритму побудови дерева рішень ID3.

Алгоритм: Створити_дерево_рішень. Створити дерево рішень на основі даних навчальної вибірки.

Вхідні дані: навчальна вибірка вибірка з дискретно-значними атрибутами; множина допустимих атрибутів список атрибутів.

Вихідні дані: дерево рішень.

Кроки алгоритму:

(1) створити вершину N;

(2) якщо вся вибірка є з того самого класу С, то

(3) повернути N як листок, позначений класом С;

(4) якщо список атрибутів є порожній, то

(5) повернути N як листок, позначений класом, що найчастіше зустрічається у вибірці; //голосування більшістю

(6) вибрати тестовий атрибут, атрибут зі списку атрибутів з найбільшим приростом інформації;

(7) позначити вершину N тестовим атрибутом;

(8) для кожного значення a_i тестового атрибута //розділу вибірки

(9) створити гілку від вершини N для умови тестовий атрибут = a_i;

(10) нехай s_i – підмножина вибірки, для якої тестовий атрибут = a_i;

(11) якщо s_i порожня, то

(12) додати листок, позначений класом, що найчастіше зустрічається у зразках;

(13) інакше додати дерево Створити_дерево_рішень(s_i, список атрибутів - тестовий атрибут);

Основна стратегія алгоритму полягає в наступному:

- початкове дерево складається з однієї вершини, яка представляє всю вибірку (крок 1);

- якщо вся вибірка належить до одного класу, то вершина стає листком і позначається цим класом (кроки 2 та 3);

- в іншому випадку, алгоритм використовує ентропійну міру приросту інформації як евристику для вибору атрибута, який найкраще розділяє вибірку за окремими класами (крок 6); цей атрибут стає “тестовим” або “атрибутом рішення” у вузлі дерева (крок 7); в описаній тут версії алгоритму всі атрибути є категоріальними, тобто дискретними; неперервні атрибути повинні бути дискретизовані перед застосуванням алгоритму;

- для кожного значення тестового атрибута створюється окрема гілка дерева, і відповідно розділяється вибірка (кроки 8-10);

- алгоритм виконується рекурсивно, будуючи дерево рішень для кожного розділу вибірки; при цьому, якщо атрибут з’являється у деякому вузлі дерева, він виключається з розгляду на подальших етапах рекурсії (крок 13);

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

a) весь розділ вибірки для заданої вершини належить до одного класу (крок 2 і 3);

b) не залишилось атрибутів, на основі яких можна далі розділити вибірку (крок 4); у цьому випадку застосовується голосування більшістю(крок 5); це означає, що вузол дерева стає листковою вершиною, позначеною класом, який зустрічається найчастіше у розділі вибірки;

c) не має прикладів для гілки тестовий атрибут = а_i (крок 11); у цьому випадку утворюється листок, який позначається класом, що найчастіше зустрічається у розділі вибірки (крок 12).

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

Нехай S – вибірка, що складається з s прикладів. Припустимо, що атрибут, який позначає клас, має m різних значень, які задають m різних класів С_i (і = 1, …, m). Нехай s_i – кількість прикладів вибірки S класу С_i. Очікувана кількість інформації, необхідної для класифікації певного прикладу, визначається так:

, (1)

де p_i – ймовірність того, що довільний приклад належить до класу С_i, і визначається як s_i/s. Зауважимо, що використовується функція логарифму з основою 2, так як інформація кодується у бітах.

Нехай атрибут А має v різних значень {a₁, a₂, …, a_v}. Атрибут А можна використати для поділу вибірки S на v розділів {S₁, S₂, …, S_v}, де S_j містить ті приклади вибірки S, для яких атрибут A приймає значення a_j. Якщо А вибраний як тестовий атрибут (тобто, найкращий атрибут для поділу), то ці підмножини повинні відповідати гілкам, що йдуть від вузла, який охоплює вибірку S. Нехай s_ij – кількість прикладів класу С_і у підвибірці S_j. Ентропія, або очікувана інформація, що базується на розподілі вибірки S за атрибутом А на розділи, обчислюється за формулою:

. (2)

Вираз діє як вага j-го розділу і дорівнює кількості прикладів у розділі (для якого значення атрибута А рівне a_j) поділеній на загальну кількість прикладів у вибірці S. Чим менше значення ентропії, тим більша “чистота” розділів. Зауважимо, що для заданої підгрупи S_j:

, (3)

де – ймовірність того, що приклад з S_j належить до класу С_і.

Кількість інформації, яка отримується внаслідок розгалуження дерева за атрибутом А становить:

. (4)

Іншими словами, Gain(A) – це очікуване зменшення ентропії, причиною якого є те, що нам стало відоме значення атрибута А.

Алгоритм обчислює приріст інформації для кожного атрибута. Атрибут з найбільшим приростом інформації вибирається як тестовий атрибут для заданої вибірки S. Для вибраного атрибута створюється вузол, а для кожного значення цього атрибута – гілки дерева. При цьому кожній гілці відповідає певний розділ вибірки.

Приклад. Індукція дерева рішень. У таблиці 1 поданий навчальний набір кортежів даних, взятий з бази даних покупців AllElectronics. Атрибут покупець_комп’ютера, який позначає клас, має два різних значення {так, ні}, тобто, маємо два різних класи (m = 2).

Таблиця 1. Навчальний набір AllElectronics.

№	вік	дохід	студент	кредито­­спроможність	Клас: покупець_ комп’ютера
	<=30	високий	ні	добра	ні
	<=30	високий	ні	відмінна	ні
	31…40	високий	ні	добра	так
	>40	середній	ні	добра	так
	>40	низький	так	добра	так
	>40	низький	так	відмінна	ні
	31…40	низький	так	відмінна	так
	<=30	середній	ні	добра	ні
	<=30	низький	так	добра	так
	>40	середній	так	добра	так
	<=30	середній	так	відмінна	так
	31…40	середній	ні	відмінна	так
	31…40	високий	так	добра	так
	>40	середній	ні	відмінна	ні

Нехай клас С₁ відповідає значенню так, а С₂ – значенню ні. У вибірці є 9 прикладів класу так і 5 прикладів класу ні. Для обчислення приросту інформації кожного атрибута, спочатку використовуємо формулу (1) для того, щоб порахувати очікувану інформацію, необхідну для класифікації заданого прикладу:

.

Потім обчислюємо ентропію кожного атрибута. Розглянемо розрахунок ентропії на прикладі атрибута вік. Дивимось на розподіл значень атрибута, який позначає клас (значень так і ні атрибута покупець_комп’ютера) для кожного значення атрибута вік. Обчислюємо за формулою (3) очікувану інформацію для кожного з цих розподілів.

Для значення вік = “<=30“:

s₁₁ = 2; s₂₁ = 3;

.

Для значення вік = “31…40“:

s₁₂ = 4; s₂₂ = 0;

.

Для значення вік = “>40”:

s₁₃ = 3; s₂₃ = 2;

.

Використовуючи формулу (2), обчислюємо очікувану кількість інформації, необхідної для класифікації заданого прикладу, якщо вибірка поділена за атрибутом вік:

.

Звідси, приріст інформації при такому розгалуженні дерева згідно з формулою (4) буде становити:

.

Аналогічно обчислюється приріст інформації для інших атрибутів: Gain(прибуток) = 0.029, Gain(студент) = 0.151, Gain(кредитоспроможність) = 0.048.

Так як атрибут вік має найвищий приріст інформації, вибираємо його як тестовий атрибут. Створюємо вузол і позначаємо його атрибутом вік. Для кожного значення атрибута (“>=30”, “31…40”, “<40”) формуємо гілку дерева (всього 3). Для кожної гілки дерева формується розділ вибірки – підмножина прикладів навчальної вибірки, для яких значення атрибута вік співпадає з відповідним значенням, яким помічена гілка дерева (рис. 2).

Зауважимо, що всі приклади, які відносяться до розділу вік = ”31…40” належать до одного класу так. Тому для відповідної гілки дерева формується листок, який позначається міткою так. Остаточне дерево рішень, яке створює алгоритм на основі таблиці 1, зображене на рис. 1.

Індукція дерев рішень має широку сферу застосування в задачах аналізу даних.

Рис. 2. Кореневий атрибут дерева рішень “покупець комп’ютера”.