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


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

На рівнині

На болотах

У лісі


 

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

38468. Производство РЭС на безвыводных ЧИП-ЭРЭ и миниатюрных ЭРЭ с применением поверхностного монтажа 1.52 MB
  Для обеспечения механической прочности изделия нужно выбрать материал печатной платы с достаточной прочностью стеклотекстолит. Габариты изделия должны быть не более 125x70x30 мм.2 Расчет надежности изделия Исходные данные вносим в таблицу 1 в которой содержится перечень тип и количество используемых компонентов и произведем их анализ. Надёжность свойство изделия выполнять заданные функции в определенных условиях эксплуатации при сохранении значений основных параметров в заранее установленных пределах.
38469. Программы производственной преддипломной практики, итогового междисциплинарного экзамена и методические указания по выполнению выпускных квалификационных работ 372 KB
  Цель прохождения студентами производственной преддипломной практики – закрепить и расширить теоретические знания, полученные в университете по дисциплинам: «Бухгалтерский финансовый учет», «Бухгалтерский управленческий учет», «Комплексный экономический анализ хозяйственной деятельности», «Контроль и ревизия», «Бухгалтерская финансовая отчетность» и других дисциплин.
38470. Перспективи підвищення ефективності функціонування та ролі фінансового ринку в Україні 3.86 MB
  Фінансовий ринок - це складова частина інфраструктури фінансової системи, яка забезпечує територіальне (місце, віртуальне місце), часове і функціональне здійснення трансакцій субєктів національної та міжнародної економіки, встановлення рівноважної ціни за відповідних обсягів купівлі-продажу фінансових активів, інструментів, технологій, а також надання фінансових послуг, необхідних для здійснення господарської та фінансової діяльності.
38471. МЕНЕДЖМЕНТ ОРГАНИЗАЦИИ 1.18 MB
  Анализируется структура дипломного проекта устанавливается последовательность работ выполняемых при его подготовке. Определяются требования к оформлению дипломного проекта и правила проведения его защиты.4 Отчет по практике [4] 2 МЕСТО И НАЗНАЧЕНИЕ ДИПЛОМНОГО ПРОЕКТИРОВАНИЯ В УЧЕБНОМ ПРОЦЕССЕ [5] 3 ЦЕЛИ ДИПЛОМНОГО ПРОЕКТИРОВАНИЯ [6] 4 ВЫБОР ТЕМЫ ДИПЛОМНОГО ПРОЕКТА [7] 5 СРОКИ РАЗРАБОТКИ ДИПЛОМНОГО ПРОЕКТА [8] 6 МЕТОДИЧЕСКАЯ ОСНОВА ФОРМИРОВАНИЯ ДИПЛОМНОГО ПРОЕКТА [8. Эта часть проекта особо важная для дипломного проекта.
38472. Менеджмент организации. Методические рекомендации к производственной практике 235 KB
  Производственная практика студентов проводится на предприятиях производственной и финансово-банковской сфер, в научно-исследовательских учреждениях, государственных организациях и структурах, а также в компаниях и фирмах различных форм собственности.
38473. Составление сметы затрат и определение себестоимости оборудования «Rademaker» по производству хлебобулочных изделий 208.85 KB
  Современное состояние технологического оборудования хлебозаводов и пекарен вызывает тревогу. Лишь 30 предприятий находится в удовлетворительном состоянии значительная часть технологического оборудования эксплуатируется более 20 лет Хлебопечение одна из ведущих отраслей пищевой промышленности. Составить сметы затрат и определение себестоимости оборудования Rdemker по производству хлебобулочных изделий. Для достижения цели в курсовой работе необходимо решить следующие задачи: рассмотрим характеристику планово ...
38474. Проектирование хлебопекарного предприятия «Rademaker» 43.59 KB
  Самостоятельное выполнение работ старшим техником Контроль качества продукции проверка соответствия качества продукции или процесса от которого оно зависит установленным требованиям. Контроль качества продукции включает государственный надзор за качеством продукции ведомственный контроль качества продукции и технический контроль качества в объединениях предприятиях и организациях. За контроль качества продукции на предприятии отвечает старший техник. Технический контроль качества продукции осуществляется на всех стадиях производственного...
38475. Фінанси і кредит усіх форм навчання Всі цитати цифровий та фактичний матеріал бібліо 345 KB
  Для досягнення вказаної мети студенти повинні вирішити такі завдання: з урахуванням бази практики вибрати тему випускової роботи та обґрунтувати її актуальність; опрацювати та узагальнити законодавчу базу України нормативноправові та інструктивні матеріали літературні та інші з досліджуваної проблеми; зібрати практичні матеріали з обраної теми досліджень в умовах реального підприємства установи організації; розглянути теоретичні аспекти за темою досліджень; виконати аналіз стану обраної проблеми та запропонувати шляхи їх...
38476. Насосная станция в условиях системы водоснабжения с. Драынивка Новосанжарского району 3.97 MB
  Кроме того система водоснабжения должна обладать определенной степенью надежности то есть обеспечивать снабжение потребителей водой без недопустимого снижения установленных показателей своей работы в отношении количества или качества подаваемой воды перерывы или снижение подачи воды или ухудшение ее качества в недопустимых пределах. Система водоснабжения населенного места или промышленного предприятия должна обеспечивать получение воды из природных источников ее очистку если это вызывается требованиями потребителей и подачу к местам...