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


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

На рівнині

На болотах

У лісі


 

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

21920. РАСПРОСТРАНЕНИЕ РАДИОВОЛН И АНТЕННО-ФИДЕРНЫЕ УСТРОЙСТВА 46.5 KB
  РАСПРОСТРАНЕНИЕ РАДИОВОЛН И АНТЕННОФИДЕРНЫЕ УСТРОЙСТВА Конспект лекций по дисциплине Распространение радиоволн и антеннофидерные устройства для студентов очной формы обучения специальности 201200 Астрахань 2004 УДК 621. Распространение радиоволн и антеннофидерные устройства: Конспект лекций АГТУ. В учебном пособии изложены теоретические сведения по распространению радиоволн и антеннофидерным устройствам Распространение радиоволн и антеннофидерные устройства входит в цикл специальных дисциплин специальности 201200. Влияние окружающие...
21921. Основные характеристики и параметры антенн 292 KB
  РАСЧЕТ ПОЛЯ ИЗЛУЧЕНИЯ АНТЕНН. Применение принципа суперпозиции к расчету поля излучения антенн. Особенности расчета поля в дальней зоне антенны. Это свойство антенны графически изображается диаграммой направленности показывающей зависимость от направления напряжённости электрического поля излученной волны измеренной на большом и одинаковом расстоянии от антенны.
21922. Технологічний процес виробництва горілок, горілок особливих та лікеро-горілчаних виробів 238.5 KB
  Львівський Лікеро - Горілчаний Завод є перший виробник на Україні горілчаної продукції. Горілка порівняно недавній винахід людства. До появи горілки на Галичині прості галичани пили пиво, шляхта - вино, і лише наприкінці 18 ст. в Галичині зявляється мода на горілку
21923. ЭНЕРГЕТИЧЕСКИЕ УСТАНОВКИ КОРАБЛЕЙ 127 KB
  Назначение состав и особенности размещения энергетических установок на надводных кораблях. Устройство и живучесть надводного корабля. Это повлекло за собой усовершенствование конструкции парусного вооружения и способов управления парусами что позволило отказаться от весел сначала на крупных а затем и на остальных кораблях. Наряду с обеспечения движения корабля они стали снабжать оружие и технику различными видами энергии а также использоваться для улучшения обитаемости.
21924. ЗАЩИТА КОРАБЛЯ 142 KB
  ЛЕКЦИЯ: ЗАЩИТА КОРАБЛЯ. УЧЕБНЫЕ ВОПРОСЫ ОСНОВНАЯ ЧАСТЬ: Понятие о конструктивной защите и физических полях корабля. Основные физические поля корабля и способы их снижения. Размагничивающее устройство корабля.
21925. ЖИВУЧЕСТЬ КОРАБЛЯ 151 KB
  ЛЕКЦИЯ: ЖИВУЧЕСТЬ КОРАБЛЯ. УЧЕБНЫЕ ВОПРОСЫ ОСНОВНАЯ ЧАСТЬ: Понятие о живучести корабля и ее элементах. Обеспечение живучести корабля Организация борьбы за живучесть корабля ЗАКЛЮЧЕНИЕ. Устройство и живучесть надводного корабля.
21926. ПОНЯТИЕ ОБ УСТРОЙСТВЕ ПОДВОДНОЙ ЛОДКИ 127.5 KB
  Подводная лодка ПЛ представляет собой боевой корабль способный вести боевые действия как в надводном так и в подводном положении. Ввиду того что при нахождении ПЛ в подводном положении легкий корпус не испытывает гидростатического давления воды его конструкция определяется главным образом соображениями прочности при погружении всплытии и плавании в надводном положении. а Плавучесть подводной лодки Плавучестью ПЛ называется ее способность плавать по заданную ватерлинию в надводном положении и на определенных глубинах не...
21927. БОЕВЫЕ И МОРЕХОДНЫЕ КАЧЕСТВА КОРАБЛЯ 140.5 KB
  ЛЕКЦИЯ: БОЕВЫЕ И МОРЕХОДНЫЕ КАЧЕСТВА КОРАБЛЯ. УЧЕБНЫЕ ВОПРОСЫ ОСНОВНАЯ ЧАСТЬ: Понятие о боевых качествах корабля. Основные сведения о мореходных качествах корабля. Понятие об эксплуатационной прочности корабля.
21928. Устройство надводного корабля 102.5 KB
  Тема: Устройство надводного корабля. Основные сведения по геометрии корпуса корабля. Составные части корпуса корабля и их общая характеристика. Назначением боевого корабля является ведение боевых действий на море.