4414

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

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

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

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

Украинкский

2012-11-18

79.5 KB

45 чел.

План:

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


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

На рівнині

На болотах

У лісі


 

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

17133. Меню редактора Ms Word. Панелі інструментів. Меню: Таблица.Створення формул в комірках таблиці 101.5 KB
  Лекція №9 Тема: Меню редактора Ms Word. Панелі інструментів. Меню: Таблица.Створення формул в комірках таблиці. План Екранний інтерфейс і настройки процесора MS Word. Панелі інструментів. Створення таблиць в MS Word. Редагування таблиць. Обчислення в табл
17134. Створення документа. Режими відображення. Редагування та форматування тексту 61.5 KB
  Лекція №10 Тема: Створення документа. Режими відображення. Редагування та форматування тексту. План Створення документа. Режими відображення. Редагування тексту. Форматування текстового документа в Word. Створення документа Під створенням д
17135. Стилі і шаблоні. Теми. Макроси 60.5 KB
  Лекція №11 Тема: Стилі і шаблоні. Теми. Макроси. План Стилі. Створення стилю. Теми. Макроси. Стилі Наймогутнішим засобом автоматизації введення і редагування в Word є стилі. Існує два підходи до форматування оформленню документа. Перший істори...
17136. Табличні процесори. Загальні відомості. Меню Excel. Осередки. Введення інформації 74.5 KB
  Лекція №12 Тема: Табличні процесори. Загальні відомості. Меню Excel. Осередки. Введення інформації. План Інтерфейс вікна Excel. Загальні відомості. Обчислення в електронних таблицях. Автоматизація введення. Особливість електронних таблиць полягає в...
17137. Формули. Арифметичні операції. Операторі відношення. Зведені таблиці. Список. Сортування, фільтр, форма 181.5 KB
  Лекція №13 Тема: Формули. Арифметичні операції. Операторі відношення. Зведені таблиці. Список. Сортування фільтр форма. План Формули. Арифметичні операції. Операторі відношення. Зведені таблиці. Сортування фільтр форма. Формули. Обчисленн
17138. Майстер функцій. Функції логіки. Математичні функції 122 KB
  Лекція №14 Тема: Майстер функцій. Функції логіки. Математичні функції. План Майстер функцій. Функції логіки. Математичні функції. Функції Функції наперед певні формули які виконують обчислення по заданих величинах званих аргументами і у вк...
17139. Матричні функції. Матрична операція. Статистичні функції. Функції категорії: Дата і час 128 KB
  Лекція №15 Тема: Матричні функції. Матрична операція. Статистичні функції. Функції категорії: Дата і час. План Матричні функції. Матрична операція. Статистичні функції. Функції категорії: Дата і час. МОБР повертає зворотну матрицю для матриці ...
17140. Робота з графічними зображеннями. Створення діаграм. Захист комірок 65.5 KB
  Лекція №16 Тема: Робота з графічними зображеннями. Створення діаграм. Захист комірок. План Побудова діаграм і графіків. Різновиди діаграм. Захист комірок книг та листів. Побудова діаграм і графіків Графічне уявлення також може допомогти знайти п...
17141. Загальна характеристика СУБД Access. Реляційна модель даних 165 KB
  Лекція №17 Тема: Загальна характеристика СУБД Access. Реляційна модель даних. План Поняття бази даних. Моделі організації даних. Загальна характеристика СУБД MS Access. Основні етапи розробки бази даних в середовищі MS Access. Поняття бази даних Базу д