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


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

На рівнині

На болотах

У лісі


 

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

50950. ОПРЕДЕЛЕНИЕ ЦЕНЫ ДЕЛЕНИЯ И ВНУТРЕННЕГО СОПРОТИВЛЕНИЯ ГАЛЬВАНОМЕТРА 8.1 MB
  Проверка закона Ампера основана на измерении периодов колебаний Т физического маятника зависящих от тока I. где собственная частота колебаний; частота колебаний при наличии тока. Определить с помощью секундомера время 10 полных колебаний t и вычислить период колебаний маятника T0 = t 10. Повторить определение периода колебаний маятника Т0 еще 4 раза.
50952. Обработка данных 90 KB
  Сбор данных. По мере того как фирма производит продукцию или услуги, каждое её действие сопровождается соответствующими записями данных. Обычно действия фирмы, затрагивающие внешнее окружение, выделяются особо как операции, производимые фирмой.
50953. Представление информации в цифровых автоматах 136 KB
  Любая предназначенная для практического применения система счисления должна обеспечивать: возможность представления любого числа в рассматриваемом диапазоне величин; единственность представления каждой комбинации символов должна соответствовать одна и только одна величина; простоту оперирования числами. Для изображения какогото числа в этой системе нужно записать количество палочек равное данному числу. Эта система неэффективна так как запись числа получается длинной.
50954. Информационные ресурсы и информационные технологии 99 KB
  Создание WebстраницHTML Создание Web документов Применение языка HTML Публикация Web документов Обработка числовых данных в электронных таблицах общие сведения об электронных таблицах EXEL. Создание Web страниц HTML Размещение собственных материалов в Интернете включает два этапа: подготовку материалов и их публикацию. Подготовка материалов состоит в создании документов имеющих формат принятый в Интернете то есть Webстраниц написанных на языке HTML Публикация материалов то есть открытие к ним доступа осуществляется...
50955. Введение в дисциплину. Понятие информатики. Место информатики в ряду других фундаментальных наук 59 KB
  Направления для практических приложений: архитектура вычислительных систем приемы и методы построения систем предназначенных для автоматической обработки данных; интерфейсы вычислительных систем приемы и методы управления аппаратным и программным обеспечением; программирование приемы методы и средства разработки компьютерных программ; Преобразование данных приемы и методы преобразования структур данных; защита информации обобщение приемов разработка методов и средств защиты данных; автоматизация функционирование...
50956. Информационные процессы и информационные технологии. Информационный ресурс и его составляющие 96.5 KB
  Создание Web страниц HTML Размещение собственных материалов в Интернете включает два этапа: подготовку материалов и их публикацию. Подготовка материалов состоит в создании документов имеющих формат принятый в Интернете то есть Webстраниц написанных на языке HTML Публикация материалов то есть открытие к ним доступа осуществляется после решения организационных вопросов связанных с получением дискового пространства на Webсервере для их размещения. Создание Webдокументов Автономные Webдокументы используют язык HTML...
50957. Обработка данных. Основные виды обработки данных 87 KB
  Для реализации распределенной обработки данных были созданы многомашинные ассоциации структура которых разрабатывается по одному из следующих направлений: многомашинные вычислительные комплексы МВК; компьютерные вычислительные сети. Обобщенная структура компьютерной сети Компьютерные сети являются высшей формой многомашинных ассоциаций. Основные отличия компьютерной сети от многомашинного вычислительного комплекса: Размерность. Необходимость решения в сети задачи маршрутизации сообщений.
50958. Функциональная и структурная организации компьютера 63.5 KB
  Алгоритм решения задач имеет ряд своих обязательных свойств; дискретность разбиение процесса обработки информации на более простые этапы шаги выполнения выполнение которых компьютером или человеком не вызывает затруднений; определенность алгоритма однозначность выполнения каждого отдельного шага преобразования информации; выполнимость конечность действий алгоритма решения задач позволяющая получить желаемый результат при допустимых исходных данных за конечное число шагов; массовость пригодность алгоритма для решения...