Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дерева прийняття рішень
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
КСС
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2016
Тип роботи:
Звіт
Предмет:
Системи штучного інтелекту
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра ЕОМ
/
Звіт
лабораторної роботи №2
«Дерева прийняття рішень»
з дисципліни:
«Комп'ютерні системи штучного інтелекту»
Мета роботи : навчитися будувати дерева рішень на базі алгоритму ID3 та вирішувати проблему суперечливості даних у таблицях прийняття рішень. Теоретичні відомості Для проведення досліджень або для комерційних цілей часто створюються дуже великі бази даних. Іноді ці бази даних стають настільки великими, що їх опрацювання й інтерпретація даних людиною майже не можлива. В наслідок цього утворюється розбіжність між появою нових даних і їх розумінням. Цю розбіжність можуть допомогти подолати інструменти й методи для виявлення нових, раніше невідомих закономірностей, схованих у даних. Ця проблематика спричинила розвиток нових галузей штучного інтелекту — дослідження даних (Data mining), видобування знань з баз даних (Knowledge dіscovery іn databases) та машинного навчання (Machine learning). Крім цього постає велика кількість задач прийняття рішень, коли потрібно відносити нові об’єкти до певного класу. Такі задачі прийняття рішень щодо нових об’єктів вимагають пошуку правил, які дозволяють класифікувати об’єкт. Такий пошук правил належить до класу задач машинного навчання, і відбувається на основі вже наявної інформації про об’єкти, яка представляється у вигляді таблиці прийняття рішень.
Дерева рішень (decision trees) Алгоритми дерев рішень – одні з найшвидших і ефективніших в області KDD, через що одержали значне поширення. Зазвичай їх використовують для задач класифікації даних або для задач апроксимації заданої булівської функції. Їхня обчислювальна складність визначається головним чином типом критерія розщеплення. У багатьох випадках час знаходження критерію розщеплення лінійно залежить від кількості полів. Залежність часу рішення від кількості записів n часто лінійна, або близька до неї (n×log(n)). Переваги використання дерев рішень: – швидкий процес навчання; – генерування правил в областях, де експертові важко формалізувати свої знання; – побудова правил природною мовою; – інтуїтивно зрозуміла класифікаційна модель; – висока точність прогнозу, порівняно з іншими методами (статистичними, нейромережевими). Проте виразна сила дерев рішень часто недостатня для опису складних правил, що зустрічаються в реальних даних. Це приводить до неминучості побудови дуже великих (і тому незрозумілих) дерев. Інша характерна для систем KDD складність пов'язана з вибором критерію для зупинки подальшого дроблення на групи. Дуже важко знайти компроміс між точністю результуючого правила, що виходить, і його статистичною значимістю. Постановка задачі для використання алгоритмів побудови дерев прийняття рішень може приймати наступний вигляд. Необхідно створити економічну конструкцію , яка б описувала (булівську) функцію, що складається з множини випадків, кожен з яких описується кінцевим набором дискретних атрибутів.
Алгоритм ID3 ID3(A,S,J ) 1. Створити корінь дерева. 2. Якщо S виконується на всіх елементах А, поставити в корінь мітку 1 і вийти. 3. Якщо S не виконується на жодному з елементів А, поставити в корінь мітку 0 і вийти. 4. Якщо Q=0, то : а) якщо S виконується на половині чи більшій частині А, поставити в корінь мітку 1 і вийти; б) якщо S не виконується на більшій частині А, поставити в корінь мітку 0 і вийти. 5. Вибрати Q ÎJ , для якого Gain(A,Q)
Завдання: Нам потрібно дізнатися чи переможе футбольна команда матч.
Виконання:
Нам відомо, що це залежить від наступних параметрів: n положення суперника у турнірній таблиці (вище або нижче); n чи вдома відбувається матч; n чи пропускає матч хтось із лідерів; n чи падає дощ. На базі цих параметрів була зібрана така статистика : Таблиця 1. Статистика попередніх ігор
/
Отже, інформацію про попередні ігри ми помістили у відношення, де атрибутами є параметри, що впливають на якість гри. Атрибут Перемога називається атрибутом прийняття рішення. Спробуємо побудувати дерево використовуючи атрибути в порядку, як вони розміщені у таблиці. Тоді дерево прийме вигляд як на рис. 1.
/
Рис.1 Початковий варіант дерева прийняття рішень.
Дерево на рис.1 можна розглядати і як булівську функцію зведену до КНФ. У даному випадку вона прийме наступний вигляд – ((Суперник=Нижче)^(Гра=Вдома))v((Суперник=Вище)^(Гра=Вдома)^(Лідери= =Пропускають) v((Суперник=Вище)^(Гра=Вдома)^(Лідери на місці)^(Дощ =Ні)) Отже, для того щоб дізнатись про результат матчу необхідно пройтися від вершини до кінцевого листка, що й буде результатом. Звісно, що дане дерево є неповне і не охоплює всіх можливих випадків. Розглянемо випадок коли :
/
Якщо матч командою буде програний, то дерево міняти не потрібно, але якщо буде виграний, то дерево потрібно змінити до вигляду як на рис.2.
/
Рис.3 Оптимальне дерево рішень
У наведеному прикладі легко переконатися, що жоден атрибут сам по собі не може ідеально розділити значення функції , тому дерево на рис.3 є оптимальним ( але не обов’язково єдиним). Булівська функція прийме вигляд -- ((Дощ=Так)^(Суперник=Нижче))v((Дощ=Так)^(Гра=Вдома)) . Перебирати всі атрибути, які б були вершинами дерева для пошуку оптимального дерева прийняття рішення є не коректним. Існує механізм вибору атрибуту, що найкраще характеризує цільову функцію. Ця вимога формалізується через ентропію. Для початку введемо кілька визначень:
Def.1 Нехай є множина А , що складається з n елементів, m з яких володіють певною властивістю S. Тоді ентропія множини А по відношенню до властивості S це /
Інакше кажучи, ентропія залежить від пропорції в якій ділиться множина. По мірі зростання пропорції від 0 до ½ ентропія також зростає, а після ½ -- симетрично спадає. Коли властивість S не бінарна, а може приймати s різних значень, кожна з яких реалізується в mi випадках, то ентропія зводиться до виразу /
Грубо кажучи, ентропія це середня кількість бітів, яка необхідна для кодування атрибуту S в елемента множини А. Якщо ймовірність появи S рівна ½ , то ентропія рівна 1 і потрібен повноцінний біт; а якщо S з’являється не рівноймовірно, то можна закодувати послідовність елементів А ефективніше. Отже, при виборі атрибуту для класифікації, вибирати його потрібно так, щоб після класифікації ентропія стала мінімальною( властивість S- потрібно розглядати як значення цільової булівської функції). Def.2 Нехай є множина елементів А , деяким з них притаманна властивість S, класифіковано по атрибуту Q, що приймає q можливих значень. Тоді приріст інформації визначається: /
де, Ai -- множина елементів А, на яких атрибут Q приймає значення і. На кожному кроці жадібний алгоритм вибирає той атрибут, для якого приріст є максимальний.
Як приклад проведемо розрахунок ентропії та приросту інформації для рис.1 Обчислимо вихідну ентропію ( для максимізації приросту цього робити не обов’язково) /
Далі розрахуємо прирости інформації для різних атрибутів: /
Вже видно, що було обрано не дуже хороший атрибут для кореня дерева. /
Висновок:
Отже, обчислення приросту інформації показує, що спочатку потрібно класифікувати по атрибуту Гра (Вдома чи В гостях) . Ну і відповідно глибина дерева стане рівною 3. Для автоматизації побудови дерева рішення було запропоновано алгоритм ID3.
11.05.2016 20:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора