4414

Побудова дерева рішень шляхом застосування алгоритму ID3

Лабораторная работа

Информатика, кибернетика и программирование

План: Мета роботи. Теоретичні відомості. Постановка задачі. Алгоритм розв`язку задачі. Виконання роботи. Висновок. Мета роботи: Навчитися будувати дерева рішень шляхом застосування алгоритму ID3. Теоретичні ...

Украинкский

2012-11-18

79.5 KB

47 чел.

План:

  1.  Мета роботи.
  2.  Теоретичні відомості.
  3.  Постановка задачі.
  4.  Алгоритм розв`язку задачі.
  5.  Виконання роботи.
  6.  Висновок.

1. Мета роботи: Навчитися будувати дерева рішень шляхом застосування алгоритму ID3.

2. Теоретичні відомості:

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

        Алгоритм ID3один з алгоритмів побудови дерев прийняття рішень, розроблений Джоном Р. Квінланом.

3. Постановка задачі:

        Написати программу реалізації алгоритму ID3. Перед побкдовою дерева провести мінімізацію та ліквідувати суперечності у вхідній матриці. Вхідна матриця будується відповідно до наступної предметної області, атрибути визначаються відповідно до питання – які параметри впливають на: «Ремонт квартири».

        

4. Алгоритм розв`язку задачі:

  1.  Визначення атрибутів та параметрів вхідної таблиці;
  2.  Побудова вхідної таблиці;
  3.  Мінімізація та ліквідування суперечностей у вхідній таблиці;
  4.  Побудова дерева прийняття рішень;
  5.  Код програми та аналітичне її представлення;
  6.  Висновки;
  7.  Контрольні запитання;

5. Виконання роботи:

1) Параметри:

- Проблемність полювання (так, ні);

- Кваліфікація мисливця (Висока,Середня, Низька);

- Якість рушниці (Висока,Середня, Низька);

- Види плювання (На рівнині, У лісі, На болотах);

Атрибути:

- день полювання (D1-D6);

- Завершення полювання (так, ні);

2) Побудова вхідної таблиці:

День

Проблемність полювання

Кваліфікація мисливців

Якість рушниці

Види полювання

Завершення полювання

D1

Так

Висока

Висока

На рівнині

Так

D2

Ні

Середня

Середня

У лісі

Так

D3

Ні

Низька

Висока

На болотах

Ні

D4

Так

Висока

Низька

У лісі

Ні

D5

Так

Висока

Висока

На рівнині

Ні

D6

Так

Середня

Середня

У лісі

Ні

3) Мінімізація та ліквідування суперечностей у вхідній таблиці:

D1

D2

D3

D4

D6

D1

0

0

a,b,d

c,d

b,c,d

D2

0

0

b,c,d

a,b,c

a

D3

a,b,d

b,c,d

0

0

0

D4

c,d

a,b,c

0

0

0

D6

b,c,d

a

0

0

0

fA = (a˅b˅d) ˄( c˅d) ˄(b˅c˅d) ˄( a˅b˅c) ˄(a) = b˄d;

День

Кваліфікація мисливців

Види полювання

Перемога

D1

Висока

На рівнині

Так

D2

Середня

У лісі

Так

D3

Низька

На болотах

Ні

D4

Висока

У лісі

Ні

D6

Середня

У лісі

Ні

4) Побудова дерева прийняття рішень:


5) Код програми та аналітичне її представлення:

Type of hunting = forest

    qualification = Medium

      0

    qualification = Medium

      0

    qualification = Medium

      1

Type of hunting = swamp  

    qualification = Low

      0

Type of repair = plain

    qualification = High

      1

Type of hunting

qualification

qualification

qualification

                                  

                     0        1                                      0                                       1

6) Висновки:

У цій практичній роботі я на практиці розглянув один з методів побудови дерев прийняття рішень – метод ID3. Цей метод виявився дуже ефективним для побудови дерев рішень.


7) Контрольні запитання:

1. Алгоритм ID3:

А) Взяти всі ознаки, що не використовуються, і порахувати їх ентропію відносно тестових екземплярів;

Б) Вибрати ознаку, для якої ентропія мінімальна;

В) Зробити вузол дерева, який включає цю ознаку.

2.  Недоліки алгоритму ID3:

В процесі побудови дерева рішень на основі таблиці прийняття рішень великих розмірів, яка містить реальні дані, виникає проблема суперечливості цих даних.

3. Технологія мінімізації таблиці та вилучення суперечностей:

А) Вилучаємо з вхідної таблиці об`єкти з неточної області;

Б) Будуємо матрицю розрізнення;

В) Будуємо і скорочуємо формулу розрізнення;

Г) Будуємо мінімізовану таблицю;

4) Які проблеми виникають при побудові великих таблиць:

Див. п. 2.

5) Як будується матриця розрізнення:

Видаляються неточні дані, атрибути таблиці асоціюються з атрибутами a, b, c і т.д. Останній атрибут – атрибут прийняття рішень. Потім будується матриця (атрибути у останньому стовпчику, у порядку спадання).


Види полювання

На рівнині

На болотах

У лісі


 

А также другие работы, которые могут Вас заинтересовать

52869. Розвиток комунікативних здібностей школярів на уроках англійської мови 188.5 KB
  Наприклад якщо учні познайомилися один з одним на початку нового шкільного року в них ніколи потім не виникає потреби знову це робити. Учні в класі як правило не мають потреби ставити запитання про те як пройти чи проїхати кудись у певному напрямку але вони мусять знати як це робити в реальних життєвих ситуаціях. Наприклад спочатку учні відпрацьовують команди напрямку.
52870. План-конспект уроку для 4 класу за темою „Christmas” 161 KB
  Тhis day people usually visit their friends. There is a lot of dancing and eating. People bring a piece of coal for good luck. People decorate trees with toys, send greeting cards and find presents in their stockings. People send cards to people they love. They don`t write their names.
52871. СТВОРЕННЯ ТА ВИКОРИСТАННЯ ЕЛЕКТРОННОГО СУПРОВОДУ УРОКІВ АНГЛІЙСЬКОЇ МОВИ 319.5 KB
  Важливого значення з огляду на це набуває питання використання у педагогічному процесі мультимедійних засобів навчання МЗН. Іноземна мова це навчальний предмет який в силу своєї специфічності створення для учнів штучного мовного середовища передбачає найбільш гнучке і широке використання різних технічних засобів навчання. Головною метою навчання іноземних мов у загальноосвітніх навчальних закладах є надбання учнями вмінь та навичок грамотного використання іноземної мови у реальних життєвих ситуаціях не тільки повсякденного але й...
52872. ШЛЯХИ ЕФЕКТИВНОГО ВИКОРИСТАННЯ ПІСЕННОГО МАТЕРІАЛУ НА УРОКАХ АНГЛІЙСЬКОЇ МОВИ 123 KB
  Музика, а саме пісня іноземною мовою, має великі можливості для реалізації навчально-виховних завдань на уроках англійської мови. Важлива роль полягає саме в методично правильному доборі пісенного матеріалу та методики його використання.
52874. ШЛЯХИ ЕФЕКТИВНОГО ВИКОРИСТАННЯ ПІСЕННОГО МАТЕРІАЛУ НА УРОКАХ АНГЛІЙСЬКОЇ МОВИ 164.5 KB
  У структуру гри як процесу входять: а ролі узяті на собі граючи; б ігрові дії як засіб реалізації цих ролей; в ігрове вживання предметів тобто заміщення реальних речей ігровими умовними; г реальні відносини між граючи; д сюжет зміст область дійсності умовно відтворена в грі. Рольові ігри Ідея використання рольової поведінки на уроці одержала підкріплення з боку теорії ролей розробленої соціологами і соціопсіхологамі. Ігри позитивно впливають на формування пізнавальних інтересів школярів сприяють усвідомленому освоєнню іноземної...
52875. Особливості навчання англійської мови молодших школярів 216 KB
  У сучасних умовах іноземна мова розглядається як засіб спілкування і залучення до культури іншого народу. Це поступово стає домінуючою стратегією викладання іноземної мови в початковій школі. Особлива увага приділяється навчанню іноземної мови школярів в початкових класах, бо в дитинстві схильність до вивчення мов набагато більша.
52876. «В чарівній країні англійської мови» «In the Magic Land of English» Сценарій позакласного заходу з англійської мови (7 клас) 138 KB
  Every season is beautiful in its own way but Autumn is a wonderful season. It's like an old woman who is still beautiful and comes to breakfast in her diamonds. Who lights a million candles over the gabled roof and never looks back to see them black, The trees are beautiful in their fantastic yellow, red, golden and brown dresses. The ground is like a carpet of many colours.And everybody feels happy.
52877. The Week of English 1.46 MB
  Аfter World War II Pablo Picasso, was responsible for the decisive use of the dove of peace: his lithograph designed for the international peace congress in Paris, 1949, features the white ancestor of a new family of doves. Since then, graphic artists have produced an endless series of doves of peace in different shapes.