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


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

На рівнині

На болотах

У лісі


 

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

5784. Определение жесткости токарного станка производственным методом 546.5 KB
  Определение жесткости токарного станка производственным методом Цель работы Ознакомиться с производственным методом определения жесткости. Определить суммарную жесткость передней бабки и суппорта, задней бабки и суппорта, построить диаграмму...
5785. Расчет ленточного конвейера и цилиндрического косозубого редуктора 3.47 MB
  Создание машин, отвечающих потребностям народного хозяйства, должно предусматривать их наибольший экономический эффект и высокие тактико-технические и эксплуатационные показатели. Основные требования, предъявляемые к создаваемой машине: выс...
5786. Расчет механической частоты вращения электродвигателя 748.5 KB
  Ведение Электрический привод (ЭП) представляет собой электромеханическую систему, обеспечивающую реализацию различных технологических и производственных процессов в промышленности, сельском хозяйстве, на транспорте, коммунальном хозяйстве и в быту с...
5787. Действительный одноступенчатый поршневой компрессор 1015 KB
  Действительный одноступенчатый поршневой компрессор Цель: Изучить процессы, протекающие в действительном поршневом компрессоре, и их влияние на основные технические характеристики, такие как производительность, работа, мощность, температурный режим,...
5788. Многоступенчатое сжатие в поршневых компрессорах 760.5 KB
  Многоступенчатое сжатие в поршневых компрессорах Цель: Изучить закономерности сжатия воздуха в многоступенчатом поршневом компрессоре. Выяснить условия наивыгоднейшей работы его и проанализировать случаи работы двухступенчато...
5789. Идеальный поршневой компрессор 355.5 KB
  Идеальный поршневой компрессор Цель: На примере идеального поршневого компрессора проследить характер протекания основных процессов в поршневом компрессоре, используя основные зависимости термодинамики. Уметь определять главные техническ...
5790. Термодинамические основы сжатия газов 151.5 KB
  Термодинамические основы сжатия газов Цель: На примерах термодинамических процессов, протекающих в элементах пневмоэнергетических систем, усвоить применение основных законов термодинамики и гидромеханики для анализа явлений, имеющих место в компресс...
5791. Неорганические вяжущие материалы 439.5 KB
  Неорганические вяжущие материалы Общие сведения Вяжущими веществами называют материалы, способные в определенных условиях (при смешивании с водой, нагревании и др.) образовывать пластично-вязкое тесто, которое самопроизвольно или под действием ...
5792. Предмет и функции философии. Философские дисциплины 60.5 KB
  Содержание Предмет и функции философии. Философские дисциплины. Список источников. §1. Предмет и функции философии. Два основных определения предмета философия: 1. Философия - это теоретически разработанная мировоз...