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 і т.д. Останній атрибут – атрибут прийняття рішень. Потім будується матриця (атрибути у останньому стовпчику, у порядку спадання).


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

На рівнині

На болотах

У лісі


 

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

50315. Дослідження підсистеми комутації та керування системи Alcatel 1000 E-10 759.5 KB
  Мета роботи: Вивчити принципи побудови функції підсистеми комутації та керування ОСВ283 lctel 1000 E10 призначення мультипроцесорних станцій. У процесі самопідготовки вивчити призначення апаратних засобів ОСВ283. Ознайомитися з функціональною архітектурою ОСВ283.3 Розглянути програмні засоби ОСВ283 lctel 1000 E10.
50317. Учбова установка АТСЕ «КАРПАТИ» 498.5 KB
  Призначення основних блоків структурної схеми АТСЕ КАРПАТИ.Привести структурну схему АТСЕ КАРПАТИ ємністю менше 720 абонентів з призначенням її основних блоків. Структурна схема учбової установки АТСЕ КАРПАТИâ ємністю менше 720 АЛ БАЛ блок абонентських ліній; САК блок спарених абонентських комплектів; БФСЛ1 БФЗЛ1 блок фізичних зєднувальних ліній...
50319. Построение простейших экспертных систем 315.5 KB
  Задание к работе: составить программу, содержащую сведения о лучшей десятке фильмов. Данные для построения вывода: название, режиссер, сценарист, год выпуска, киностудия, страна-производитель. В программе должна быть реализована возможность получения следующей информации: по порядковому номеру – фамилия режиссера, название фильма, страны-производителя; все фильмы одного годы выпуска или одной киностудии; все фильмы одной страны.
50320. ЗНАЙОМСТВО ІЗ ПАКЕТОМ СИМУЛЯЦІЇ ЕЛЕКТРОННИХ СХЕМ «PROTEUS» 488 KB
  Proteus - це пакет програм класу САПР, який поєднує в собі дві основні програми: ISIS - засіб розробки і налагодження в режимі реального часу електронних схем та контролерів і ARES - засіб розробки друкованих плат.
50321. ІНТЕГРОВАНЕ СЕРЕДОВИЩЕ РОЗРОБКИ ПРОГРАМ AVR STUDIO 1.54 MB
  Початок роботи При програмуванні в середовищі VR Studio необхідно виконати стандартну послідовність дій: створення проекту; написання програми; компіляція; симуляція. Натискаємо завершити Finish на цьому проект створений і ми потрапляємо в головне вікно програми. Загальний вид вікна програми Вікно розділене на 4 частини. Трохи нижче ліворуч розташовується вкладки Диспетчер проекту Project Перегляд вводу виводу I O View Інформація Info праворуч Текст програми.
50322. Изучение явления дифракции света с помощью лазера 276 KB
  Рассмотрим дифракцию Фраунгофера от одной узкой прямоугольной щели рис. на щель падает плоская монохроматическая световая волна с длинной перпендикулярно к плоскости щели. Поместим за щелью на расстоянии во много раз большим по сравнению с шириной щели L а экран. В точке о лежащей на перпендикуляре к плоскости щели восстановленном из середины щели будут встречаться световые пучки длина пути которых от всех условных точечных источников щели до данной точки почти одинакова т.
50323. Изучение поляризации отраженного от диэлектриков света 682.5 KB
  Изучение поляризации отраженного от диэлектриков света. Цель работы: Изучение свойств света поляризованного при отражении от диэлектриков; изучение законов поляризации света при отражении от прозрачной среды; изучение методов определения показателя преломления диэлектрика по степени поляризации отраженного света. Приборы и принадлежности: Источник света; коллиматор; исследуемые образцы; анализатор; фотоэлемент; собирающая линза; миллиамперметр; транспортир. Подробно явление...