Лабораторне завдання

МЕТА РОБОТИ

Навчитися будувати дерева рішень на базі алгоритму ID3 та вирішувати проблему суперечливості даних у таблицях прийняття рішень.

2.КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ

Для проведення досліджень або для комерційних цілей часто створюються дуже великі бази даних. Іноді ці бази даних стають настільки великими, що їх опрацювання й інтерпретація даних людиною майже не можлива. В наслідок цього утворюється розбіжність між появою нових даних і їх розумінням. Цю розбіжність можуть допомогти подолати інструменти й методи для виявлення нових, раніше невідомих закономірностей, схованих у даних. Ця проблематика спричинила розвиток нових галузей штучного інтелекту — дослідження даних (Data mining), видобування знань з баз даних (Knowledge discovery іn databases) та машинного навчання (Machine learning).

Крім цього постає велика кількість задач прийняття рішень, коли потрібно відносити нові об'єкти до певного класу. Такі задачі прийняття рішень щодо нових об'єктів вимагають пошуку правил, які дозволяють класифікувати об'єкт. Такий пошук правил належить до класу задач машинного навчання, і відбувається на основі вже наявної інформації про об'єкти, яка представляється у вигляді таблиці прийняття рішень.

Knowledge discovery in databases (KDD) - аналітичний процес дослідження людиною великого обсягу інформації з залученням засобів автоматизованого дослідження даних з метою виявлення схованих у даних структур або залежностей. Передбачається повна або часткова відсутність апріорних уявлень про характер прихованих структур і залежностей.

KDD включає в себе:

- попереднє осмислення і неповне формулювання задачі (у термінах цільових змінних);

- перетворення даних до придатного для автоматизованого аналізу формату і їхню попередню обробку;

- виявлення засобами автоматичного дослідження даних (data mining) схованих структур або залежностей;

- апробація виявлених моделей на нових даних, що не використовувалися для побудови моделей, та інтерпретація людиною виявлених моделей.

Data mining (дослівно, "розробка даних") - дослідження і виявлення "машиною" (алгоритмами, засобами штучного інтелекту) в необроблених даних прихованих структур або залежностей, які:

- раніше не були відомі;

- нетривіальні;

- практично корисні;

- доступні для інтерпретації людиною.

В цих галузях використовується велика кількість різних методів і їхні різні комбінації. Перерахуємо найбільш важливі і часто використовувані методи:

• кластеризація (дискретизація);

• асоціація;

• дерева рішень;

• метод найближчих сусідів;

• нейронні мережі;

• генетичні алгоритми;

• регресійні методи;

• неточні множини;

• еволюційне програмування.

2.1. Дерева рішень (decision trees)

Алгоритми дерев рішень - одні з найшвидших і ефективніших в області KDD, через що одержали значне поширення. Зазвичай їх використовують для задач класифікації даних або для задач апроксимації заданої булівської функції. Їхня обчислювальна складність визначається головним чином типом критерія розщеплення. У багатьох випадках час знаходження критерію розщеплення лінійно залежить від кількості полів. Залежність часу рішення від кількості записів n часто лінійна, або близька до неї (n*log(n)).

Переваги використання дерев рішень:

- швидкий процес навчання;

- генерування правил в областях, де експертові важко формалізувати свої знання;

- побудова правил природною мовою;

- інтуїтивно зрозуміла класифікаційна модель;

- висока точність прогнозу, порівняно з іншими методами (статистичними, нейромережевими).

Проте виразна сила дерев рішень часто недостатня для опису складних правил, що зустрічаються в реальних даних. Це приводить до неминучості побудови дуже великих (і тому незрозумілих) дерев. Інша характерна для систем KDD складність пов'язана з вибором критерію для зупинки подальшого дроблення на групи. Дуже важко знайти компроміс між точністю результуючого правила, що виходить, і його статистичною значимістю.

Постановка задачі для використання алгоритмів побудови дерев прийняття рішень може приймати наступний вигляд. Необхідно створити економічну конструкцію, яка б описувала (булівську) функцію, що складається з множини випадків, кожен з яких описується кінцевим набором дискретних атрибутів.

ПРИКЛАД 1.

У цьому прикладі розглянемо випадок коли нам потрібно дізнатися чи переможе футбольна команда матч. Нам відомо, що це залежить від наступних параметрів:

■ положення суперника у турнірній таблиці (вище або нижче);

■ чи вдома відбувається матч;

■ чи пропускає матч хтось із лідерів;

■ чи падає дощ.

На базі цих параметрів була зібрана така статистика:

Таблиця 2.1. Статистика попередніх ігор

Суперник	Гра	Лідери	Дощ	Перемога
Вище	Вдома	На місці	Так	Ні
Вище	Вдома	На місці	Ні	Так
Вище	Вдома	Пропускають	Ні	Так
Нижче	Вдома	Пропускають	Ні	Так
Нижче	В гостях	Пропускають	Ні	Ні
Нижче	Вдома	Пропускають	Так	Так
Вище	В гостях	На місці	Так	Ні

Отже, інформацію про попередні ігри ми помістили у відношення, де атрибутами є параметри, що впливають на якість гри. Атрибут Перемога називається атрибутом прийняття рішення. Спробуємо побудувати дерево використовуючи атрибути в порядку, як вони розміщені у таблиці. Тоді дерево прийме вигляд як на рис. 2.1.

Рис. 2.1 Початковий варіант дерева прийняття рішень.

Дерево на рис.2.1 можна розглядати і як булівську функцію зведену до КНФ. У даному випадку вона прийме наступний вигляд-((Суперник=Нижче)^(Гра=Вдома))v((Суперник=Вище)^(Гра=Вдома)^(Лідери=

=Пропускають) v((Суперник=Вище)v(Гра=Вдома)v(Лідери на місці) ^ (Дощ =Ні)). Отже, для того щоб дізнатись про результат матчу необхідно пройтися від вершини до кінцевого листка, що й буде результатом. Звісно, що дане дерево є неповне і не охоплює всіх можливих випадків. Розглянемо випадок коли:

Таблиця 2.2. Статистика ігор

Суперник	Гра	Лідери	Дощ	Перемога
Нижче	В гостях	На місці	Ні	???

Якщо матч командою буде програний, то дерево міняти не потрібно, але якщо буде виграний, то дерево потрібно змінити до вигляду як на рис.2.2.

Рис.2.2 Зміна дерева після додавання ще одного випадку

Таким чином, за рахунок модифікації дерева проходить машинне навчання.

Отримане дерево є далеко не ідеальним тим більше, що його глибина рівна чотирьом. За основу можна взяти й інший атрибут, наприклад чи падає дощ, тоді глибина відразу зменшиться до двох (рис. 2.3).

Рис.2.3 Оптимальне дерево рішень

У наведеному прикладі легко переконатися, що жоден атрибут сам по собі не може ідеально розділити значення функції, тому дерево на рис.3 є оптимальним (але не обов'язково єдиним). Булівська функція прийме вигляд -- ((Дощ=Так)v(Суперник=Нижче))v((Дощ=Так)v(Гра=Вдома)).

Перебирати всі атрибути, які б були вершинами дерева для пошуку оптимального дерева прийняття рішення є не коректним. Існує механізм вибору атрибуту, що найкраще характеризує цільову функцію. Ця вимога формалізується через ентропію. Для початку введемо кілька визначень:

Def.1 Нехай є множина А, що складається з n елементів, m з яких володіють певною властивістю S. Тоді ентропія множини А по відношенню до властивості S це

Інакше кажучи, ентропія залежить від пропорції в якій ділиться множина. По мірі зростання пропорції від 0 до / ентропія також зростає, а після / -- симетрично спадає. Коли властивість S не бінарна, а може приймати s різних значень, кожна з яких реалізується в m_i випадках, то ентропія зводиться до виразу

Грубо кажучи, ентропія це середня кількість бітів, яка необхідна для кодування атрибуту S в елемента множини А. Якщо ймовірність появи S рівна /, то ентропія рівна 1 і потрібен повноцінний біт; а якщо S з'являється не рівноймовірно, то можна закодувати послідовність елементів А ефективніше.

Отже, при виборі атрибуту для класифікації, вибирати його потрібно так, щоб після класифікації ентропія стала мінімальною(властивість S- потрібно розглядати як значення цільової булівської функції).

Def.2 Нехай є множина елементів А, деяким з них притаманна властивість S, класифіковано по атрибуту Q, що приймає q можливих значень. Тоді приріст інформації визначається:

де, A_i -- множина елементів А, на яких атрибут Q приймає значення і. На кожному кроці жадібний алгоритм вибирає той атрибут, для якого приріст є максимальний.

Як приклад проведемо розрахунок ентропії та приросту інформації для рис. 1 Обчислимо вихідну ентропію (для максимізації приросту цього робити не обов'язково)

Далі розрахуємо прирости інформації для різних атрибутів:

Вже видно, що було обрано не дуже хороший атрибут для кореня дерева.

Отже, обчислення приросту інформації показує, що спочатку потрібно класифікувати по атрибуту Гра (Вдома чи В гостях). Ну і відповідно глибина дерева стане рівною 3.

Для автоматизації побудови дерева рішення було запропоновано алгоритм ID3.

Алгоритм ID3

ID3(A,S,ʋ)

1. Створити корінь дерева.

2. Якщо S виконується на всіх елементах А, поставити в корінь мітку 1 і вийти.

3. Якщо S не виконується на жодному з елементів А, поставити в корінь мітку 0 і вийти.

4. Якщо Q=0, то:

а) якщо S виконується на половині чи більшій частині А, поставити в корінь мітку 1 і вийти;

б) якщо S не виконується на більшій частині А, поставити в корінь мітку 0 і вийти.

5. Вибрати Q є ʋ, для якого Gain(A,Q) є максимальним.

6. Поставити в корінь мітку Q.

7. Для кожного значення q атрибуту Q:

а) добавити нового потомка кореня і помітити відповідне вихідне ребро міткою q;

б) якщо в А немає випадків, для яких Q приймає значення q (тобто | A_q |= =0), то помітити цього потомка в залежності від того, на якій частині А виконується S (аналогічно до 4);

в) інакше запустити ID3(A_q, S, ʋ\ {Q}) і добавити його результат, як піддерево з коренем у цьому потомку.

ПРИКЛАД 2.

Нехай нам потрібно дізнатися про те чи відбудеться гра в теніс у цю суботу. За результатами попередніх досліджень було сформовано наступне відношення. У відношенні маємо перелік шести днів за яких гра відбувалась чи ні. Атрибут Погода приймає значення {Сонячно; Похмуро; Дощ}, атрибут Вологість --{Висока; Нормальна; Низька}, атрибут Вітер -- {Сильний; Слабкий} атрибут Гра в теніс називається атрибутом прийняття рішень і приймає значення Так або Ні.

Для спрощення у цьому прикладі пропонується тільки початкове відношення та кінцеве дерево.

Таблиця 2.3 Приклад таблиці прийняття рішень

День	Погода	Вологість	Вітер	Гра в теніс
D1	Сонячно	Висока	Слабкий	Ні
D2	Сонячно	Висока	Сильний	Ні
D3	Похмуро	Висока	Слабкий	Так
D4	Дощ	Висока	Слабкий	Так
D5	Дощ	Нормальна	Слабкий	Так
D6	Дощ	Нормальна	Сильний	Ні

Найпростіша структура дерева рішень прийме вигляд як на Рис.2.4:

Рис.2.4 Дерево прийняття рішення

Крім цього, в процесі побудови дерева рішень на основі таблиці прийняття рішень великих розмірів, яка містить реальні дані, виникає проблема суперечливості цих даних. При виконанні алгоритму побудови дерева рішень (наприклад, ID3) ця проблема призводить до того, що для формування листка дерева рішень потрібно приймати спеціальне рішення, виходячи із специфіки задачі. Тому було розроблено серію алгоритмів для попередньої обробки відношень. Фактично їх суть зводиться до підготовки матриці до побудови дерева рішень.

2.3 Технологія неточних множин та метод Boolean Reasoning

Отже, набір даних, що досліджується, подається у вигляді таблиці, кожен рядок якої може представляти подію чи будь-який об'єкт (наприклад, пацієнта). Кожен стовпчик таблиці відповідає певному атрибуту (певній властивості) об'єкта. Позначимо через U непорожню скінчену множину об'єктів, а через A - непорожню скінчену множину атрибутів.

Крім цього, до таблиці входить атрибут прийняття рішення d, який відносить об'єкт до того чи іншого класу. У випадку великих наборів реальних даних (які здебільшого представляють певну модель, предметну область, результати експериментів, тощо), деяка частина цих даних може бути надмірною або ж містити суперечливості. Наприклад, для двох різних об'єктів значення відповідних атрибутів співпадають, а значення атрибуту прийняття рішення відрізняється, тобто неможливо чітко класифікувати ці об'єкти. В такому випадку говорять, що ці елементи належать до т. зв. неточної (rough) області.

Розглянемо для прикладу наступну таблицю даних:

Таблиця 2.4. Приклад таблиці даних з класифікуючим атрибутом d

	Y1	Y2	d
X1
X2
X3
X4

Одразу видно, що елементи Х2 та Х3 належать до неточної області, оскільки за однакових значень атрибутів для них відрізняється значення класифікуючого атрибуту (атрибут прийняття рішень). Також можна бачити що таблиця є надмірною, оскільки елементи Х1 та Х4 є однаковими. Ці елементи належать до одного класу еквівалентності. У реальних великих наборах даних може бути велика кількість різних класів еквівалентності. А оскільки для представлення всього такого класу потрібен лише один його елемент, то можна легко зменшити обсяг даних, що аналізуються, і це не вплине на кінцевий результат. Крім цього, з таблиці видаляються суперечливі дані (які входять в неточну область).

З метою подальшої мінімізації даних з таблиці видаляються зайві стовпці даних, які не впливають на класифікацію об'єктів. Мінімальний набір атрибутів, що залишилися, називають редуктом (reduct). Іншими словами, редукт є підмножиною множини атрибутів А і дозволяє здійснювати класифікацію так само, як і з використанням всієї множини А. Слід зазначити, що атрибутам таблиці можна також присвоювати деякий коефіціент важливості, наприклад з інтервалу [0, 1].

Знаходження редукту є NP-складною задачею, однак існують досить ефективні методи, які дозволяють це робити за прийнятний час. Наприклад, метод Boolean reasoning - логічне виведення, який займає важливе місце в методології неточноих множин.

Основою методу є побудова на базі таблиці прийняття рішень функції розрізнення, яка є булевою функцією від m змінних і визначається наступним чином:

Де - кількість атрибутів таблиці А, n - кількість об'єктів, - атрибут таблиці, c*_ij - елемент спеціальної матриці розрізнення М(А). Цей елемент представляє

собою множину атрибутів, за якими відрізняються два об'єкти u_i та u_j з U, причому ці об'єкти повинні мати різне значення атрибуту прийняття рішення. Якщо об'єкти мають однакові значення атрибуту прийняття рішення, то c*_ij= 0. Тобто, матриця М(А) є симетричною

матрицею розмірів n*n з нульовою діагоналлю.

Наступним кроком є приведення функції до вигляду кон'юнктивної нормальної форми. Для цього достаньо реалізувати скорочення за законами ідемпотентності для кон'юнкції a л a = a та спрощення (a v b) л a = a. Після такого спрощення булева функція містить елементи, які відповідають атрибутам, що входять до редукту.

2.4 Мінімізація таблиці та вилучення суперечностей

Розглянемо застосування методу Boolean Reasoning на прикладі таблиці прийняття рішень наведеної в таб. 2.5.

Таблиця. 2.5. Приклад таблиці прийняття рішень

день	погода	температура	вологість	вітер	гра
D1	Сонце	Спека	Висока	Слабкий	Так
D2	Сонце	Спека	Висока	Слабкий	Ні
D3	Хмари	Помірно	Висока	Слабкий	Так
D4	Дощ	Помірно	Висока	Слабкий	Так
D5	Дощ	Холод	Норма	Слабкий	Так
D6	Дощ	Холод	Норма	Сильний	Ні

Таблиця містить 6 об'єктів, 4 атрибути і атрибут прийняття рішення «гра». З таблиці видно, що об'єкти D1 і D2 належать до неточної області, тому вилучаємо з таблиці, наприклад, D2. Для побудови функції розрізнення побудуємо матрицю розрізнення М(А). В ній літери a, b, c, d будуть представляти відповідно атрибути погода, температура, вологість, вітер.

Таблиця 2.6. Матриця розрізнення М(А)

	D1	D3	D4	D5	D6
D1					a,b,c,d
D3					a,b,c,d
D4					b,c,d
D5					d
D6	a,b,c,d	a,b,c,d	b,c,d	d

Тепер з цієї матриці випишемо літери з непорожніх стовпців і отримаємо функцію

розрізнення:

внаслідок спрощення якої отримаємо функцію: f = aлd.

Це означає, що редукт виглядає так: {погода, вітер}. Тобто мінімізована таблиця містить лише два атрибути, а кількість рядків зменшилась до чотирьох (після того, як ми вилучили рядок D5, що дублювався у мінімізованій таблиці рядком D4).

Таблиця. 2.7. Мінімізована таблиця прийняття рішень

день	погода	вітер	гра
D1	Сонце	Слабкий	Так
D6	Дощ	Сильний	Ні
D3	Хмари	Слабкий	Так
D4	Дощ	Слабкий	Так

Ця мінімізована таблиця не містить суперечливостей, зберігає правильність класифікації об'єктів і дозволить без проблем побудувати дерево рішень.

3. КОНТРОЛЬНІ ЗАПИТАННЯ

1. Алгоритм ID3

2. Недоліки алгоритму ID3

3. Технологія мінімізації таблиці та вилучення суперечностей

4. Які проблеми виникають при обробці великих таблиць?

5. Як будується матриця розрізнення?

ЛАБОРАТОРНЕ ЗАВДАННЯ

Написати програму реалізації алгоритму ID3. Перед побудовою дерева провести мінімізацію та ліквідувати суперечності у вхідній матриці. Вхідна матриця будується відповідно до наступної предметної області, атрибути визначаються відповіддю на питання - які параметри впливають на...

Таблиця 4.1. Варіанти індивідуальних завдань

	Придбання книги
	Придбання автомобіля
	Гру в баскетбол
	Ловлю хижої риби
	Результат полювання
	Придбання комп'ютера
	Ремонт квартири
	Відвідування занять
	Гарний відпочинок
	Ремонт автомобіля
	Вирощування бананів
	Ремонт комп'ютера
	Придбання квартири
	Погода на день завтрашній
	Відмінне самопочуття
	Придбання велосипеда
	Наявність Інтернету
	Результати виборів до Верховної Ради
	Результати виборів до Кабміну
	Успішну здачу іспиту
	Успішну здачу цієї лабораторної роботи
	Придбання мобільного телефону
	Роздача Інтернету студентам на каф. ЕОМ
	Придбання кондиціонера
	Придбання пральної машини

Вхідні дані повинні бути сформовані у вигляді текстового файлу. Результатом роботи програми повинен бути текстовий файл із мінімізованою та матрицею прийняття рішень та деревом прийняття рішень. Наприклад, дерево прийняття рішень може виглядати так:

Match=Home

Leaders=Play

Rain=Yes

Rain=No

Leaders=Pass 1

Match=Away 0

Що відповідатиме, такому дереву:

Рис. 4.1. Аналітичне представлення результатів роботи програми

5. ЗМІСТ ЗВІТУ

Звіт повинен містити такі розділи:

1. Титульний аркуш із вказанням номеру та назвою лабораторної роботи, особа що прийняла та виконала роботу;

2. Мета роботи;

3. Короткі теоретичні відомості;

4. Постановка задачі;

5. Алгоритм розв'язку задачі;

6. Інтерфейс програми із зазначеним розтлумаченням введених даних;

7. Результати роботи програми із розтлумаченням отриманих результатів;

8. Висновок

7. СПИСОК РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ

1. Паклин Н.Б., Орешков В.И. Бизнес-аналитика: от данных к знаниям (+ СD). — СПб: Изд. Питер, 2009. — 624 с.

2. Дюк В., Самойленко А. Data Mining: учебный курс (+CD). — СПб: Изд. Питер, 2001. — 368 с.

3. Журавлёв Ю.И., Рязанов В.В., Сенько О.В. РАСПОЗНАВАНИЕ.Математические методы.Программная система. Практические применения — М.: Изд. «Фазис», 2006. — 176 с. — ISBN 5-7036-0106-8.

4. Зиновьев А. Ю. Визуализация многомерных данных — Красноярск: Изд. Красноярского государственного технического университета, 2000. — 180 с.

5. Чубукова И. А. Data Mining: учебное пособие — М.: Интернет-университет информационных технологий: БИНОМ: Лаборатория знаний, 2006. — 382 с. — ISBN 5-9556-0064-7.

6. Айвазян С. А., Бухштабер В. М., Юнюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. - М.: Финансы и статистика, 1989.

7. Knowledge Discovery Through Data Mining: What Is Knowledge Discovery? - Tandem Computers Inc., 1996.

8. Кречетов Н.. Продукты для интеллектуального анализа данных. - Рынок программных средств, N14-15_97, c. 32-39.

9. Boulding K. E. General Systems Theory - The Skeleton of Science//Management Science, 2, 1956.

10. Гик Дж., ван. Прикладная общая теория систем. - М.: Мир, 1981.

11. Киселев М., Соломатин Е.. Средства добычи знаний в бизнесе и финансах. - Открытые системы, № 4, 1997, с. 41-44.

12. Дюк В.А. Обработка данных на ПК в примерах. - СПб: Питер, 1997.

Дата добавления: 2015-11-14