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


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

На рівнині

На болотах

У лісі


 

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

50610. Создание объектов при помощи NURBS-кривых и NURBS-поверхностей 278.5 KB
  Отдельные фрагменты NURBS-поверхностей можно прикреплять друг к другу для наращивания общей площади. Различают два типа NURBSповерхностей: точечная поверхность point surfce проходит через все опорные точки заданные в трехмерном пространстве; CVповерхность CV surfce плавно огибает все опорные точки заданные в трехмерном пространстве и называемые управляющими вершинами Control Vertices CV. Создать стеклянные плафоны методом вращения профиля в виде NURBSкривой.
50611. Создание объектов при помощи модификаторов Bevel Bend и Extrude 1.78 MB
  Измените масштаб в окне проекции Front Вид спереди так чтобы вертикальный размер видимой части сетки составлял примерно 55-60 см. Для удобства разверните окно проекции во весь экран. В окнах проекции появится зеркальная копия сплайна выделенная красным цветом. Установка уровня визуализации окна проекции кнопка F9 Сложные сцены зачастую отображаются и визуализируются очень долго.
50612. Создание объектов с помощью лофтинга 3.14 MB
  Выберите команду Grid nd Settings Настройка сетки и привязок меню Customize Настройка и щелкните на корешке вкладки Home Grid Исходная сетка окно диалога Grid nd Snp Settings Настройка сетки и привязок. Щелкните на кнопке Geometry Геометрия командной панели Crete Создать и выберите в раскрывающемся списке разновидностей объектов вариант Compound Objects Составные объекты В свитке Object Type Тип объекта появятся девять кнопок соответствующих типам основных объектов. Щелкните по ней. В свитке Cretion Method Метод...
50613. Создаем окно и дверь для кафе «МАХ» в виде полисеток 256.5 KB
  Теперь когда вы получили опыт работы с полисетками изготовление двери не должно вызвать затруднений. В данном случае длина соответствует высоте полотна будущей двери а высота его толщине. Рисунок Заготовка для двери с двумя сегментами по высоте будущего полотна Давайте сформируем для начала рамку полотна двери создав на нем две филенки то есть вставки которые могут быть и стеклянными сверху и снизу. Полигоны ограничивающие полотно двери по бокам не должны быть выделены.
50614. Простейшие стандартные материалы 1.53 MB
  Введите для материала рис.3 Настройте следующие значения основных цветов материала в свитке Phong Bsic Prmetrs: mbient Подсветка 190; 190; 190 светлосерый; Diffuse Диффузный 240; 240; 240 почти белый; Speculr Зеркальный 255; 255; 255 чистобелый. Величины всех остальных параметров материала оставьте равными их исходным значениям.8 Теперь сохраните только что созданный материал в новой библиотеке: Если окно Mteril Mp Browser Просмотр материалов и карт текстур еще открыто можно просто щелкнуть на образце...
50615. Моделирование асинхронных вычислительных процессов 86 KB
  Пять философов прогуливаясь и размышляя время от времени испытывают приступы голода. Рис 41 При конструировании управления в этой задаче следует учитывать самые разнообразные варианты поведения философов. Необходимо организовать действия философов так чтобы они все были накормлены и не случилось бы так что пять философов одновременно войдут в столовую возьмут левую вилку и застынут в ожидании освобождения правой вилки. Голодная смерть всех философов неминуема если никто из них не захочет расстаться па время со своей левой вилкой.
50617. Изучение твердотельных приборов различного назначения 837 KB
  К твердотельным приборам относят полупроводниковые диоды транзисторы тиристоры варисторы генераторы Ганна оптоэлектронные приборы. Полупроводниковые диоды Полупроводниковым диодом называют прибор c одним или несколькими электрическими переходами и двумя внешними выводами. Основные типы полупроводниковых диодов: выпрямительные диоды стабилитроны варикапы высокочастотные и импульсные диоды туннельные и обращенные диоды. Разновидностью выпрямительных диодов являются лавинные диоды приборы имеющие на обратной ветви вольтамперной...
50618. Тороид, намотанный на сердечник из однородного и изотропного магнетика 865 KB
  Из соображений симметрии ясно что линии вектора поля тороида представляют собой окружности центры которых расположены на оси вращения 00 тора. Поэтому при расчете поля внутри тороида в качестве контура интегрирования L удобно взять одну из таких линий с произвольным радиусом r. Тогда на основании теоремы о циркуляции вектора можно записать: 11 где N число витков в обмотке тороида все витки охватываются контуром интегрирования. 13 Анализ формулы 9 показывает что магнитное поле внутри тороида...