Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи побудови правила класифікації
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
КН
Кафедра:
Автоматизовані Системи Управління
Інформація про роботу
Рік:
2013
Тип роботи:
Лабораторна робота
Предмет:
Інтелектуальний аналіз даних
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Кафедра АСУ
Звіт
з лабораторної роботи №1
з дисципліни:
«Інтелектуальний аналіз даних»
на тему:
«Методи побудови правила класифікації.»
Мета: Оволодіти методами побудови правил класифікації та навчитись застосовувати ці знання на практиці.
Теоретична частина:
Data Mining – сукупність методів виявлення в даних раніше невідомих, нетривіальних, практично корисних і доступних інтерпретацій знань, необхідних для прийняття рішень в різноманітних сферах людської діяльності.
Завдання класифікації
Класифікація є найбільш простою і одночасно найбільш часто розв'язуваною задачею Data Mining. Зважаючи на поширеність задач класифікації необхідне чітке розуміння суті цього поняття.
Наведемо кілька визначень.
Класифікація - системний розподіл досліджуваних предметів, явищ, процесів за родами, видами, типами, з якими-небудь істотними ознаками для зручності їх дослідження; угрупування вихідних понять і розташування їх у певному порядку, що відбиває ступінь цієї схожості.
Класифікація - впорядкована по деякому принципу множина об'єктів, які мають подібні класифікаційні ознаки (одну або декілька властивостей), обраних для визначення схожості або відмінності між цими об'єктами.
Класифікація вимагає дотримання наступних правил:
В кожному акті поділу необхідно застосовувати тільки одну ознаку;
Розподіл має бути пропорційним, тобто загальний обсяг видових понять повинен дорівнювати обсягу діленого родового поняття;
Члени поділу повинні взаємно виключати один одного, їх обсяги не повинні перехрещуватися;
Розподіл має бути послідовним.
Розрізняють:
допоміжну (штучну) класифікацію, яка проводиться за зовнішніми ознаками і служить для надання множині предметів (процесів, явищ) потрібного порядку;
природну класифікацію, яка проводиться по істотних ознаках, що характеризують внутрішню спільність предметів і явищ. Вона є результатом і важливим засобом наукових досліджень, тому передбачає і закріплює результати вивчення закономірностей об'єктів, що класифікуються.
В залежності від обраних ознак, їх поєднання та процедури поділу понять класифікація може бути:
простою - поділ родового поняття тільки за ознакою і тільки один раз до розкриття усіх видів. Прикладом такої класифікації є дихотомія, при якій членами поділу бувають тільки два поняття, кожне з яких є суперечним іншому (тобто дотримується принцип: "А і не А");
складною - застосовується для поділу одного поняття з різних підстав і синтезу таких простих розподілів в єдине ціле. Прикладом такої класифікації є періодична система хімічних елементів.
Під класифікацією будемо розуміти віднесення об'єктів (спостережень, подій) до одного з наперед відомих класів.
Алгоритм побудови 1-правил
Розглянемо найпростіший алгоритм формування елементарних правил для класифікафії об’єкту. Він будує правила по значенню одної незалежної змінної, тому в літературі його часто називають «1-правило» (1-rule) або коротко 1R-алгоритм.
Ідея алгоритму дуже проста. Для будь-якого можливого значення кожної незалежної змінної формується правило, яке класифікує об’єкти із навчальної вибірки. При цьому в заключній частині правила вказується значення залежної змінної, яке найбільш часто зустрічається в об’єктів із вибраним значенням незалежної змінної. В даному випадку помилкою правила буде кількість об’єктів, які мають те ж значення поточної змінної, але не відносяться до вибраного класу.
Таким чином, для кожної змінної буде отримано набір правил (для кожного значення). Оцінивши ступінь помилки кожного набору, вибирається змінна, для якої побудовані правила з найменшою помилкою.
Класифікація за допомогою дерев рішень
Дерево прийняття рішень - це дерево, в листках якого стоять значення цільової функції, а в інших вузлах - умови переходу (наприклад "СТАТЬ є ЧОЛОВІЧА"), що визначають по якому з ребер йти. Якщо для даного спостереження умова істина то здійснюється перехід по лівому ребру, якщо ж брехня - по правому.
Основні методи класифікації за допомогою дерев рішень
Нижче перераховані кілька основних методів, які використовують дерева прийняття рішень. Їх короткий опис, плюси і мінуси.
1. CART
CART (англ. Classification and regression trees - Класифікаційні та регресійні дерева) був першим з методів, придуманий в 1983 четвіркою відомих вчених в галузі аналізу даних: Лео Брайман, Джером Фрідман, Річард Олшен і Стоун.
Суть цього алгоритму полягає в звичайному побудові дерева прийняття рішень, не більше і не менше.
На першій ітерації ми будуємо всі можливі (в дискретному сенсі) гіперплощини, які розбивали б наш простір на два. Для кожного такого розбиття простору обраховується кількість спостережень у кожному з підпросторів різних класів. В результаті вибирається таке розбиття, яке максимально виділило в одному з підпросторів спостереження одного з класів. Відповідно, це розбиття буде нашим коренем дерева прийняття рішень, а листами на даній ітерації будуть два розбиття.
На наступних ітераціях ми беремо один гірший (в сенсі ставлення кількості спостережень різних класів) лист і проводимо ту ж операцію по розбиттю його. В результаті цей лист стає вузлом з якимось розбиттям, і двома листами.
Продовжуємо так робити, поки не досягнемо обмеження по кількості вузлів, або від однієї ітерації до іншої перестане поліпшуватися загальна помилка (кількість неправильно класифікованих спостережень всім деревом). Однак, отримане дерево буде "перенавчене" (буде підігнано під навчальну вибірку) і, відповідно, не буде давати нормальні результати для інших даних. Для того, що б уникнути "перенавчання", використовують тестові вибірки (або крос-валідацію) і, відповідно, проводиться зворотний аналіз (так званий pruning), коли дерево зменшують в залежності від результату на тестовій вибірці.
Відносно простий алгоритм, в результаті якого виходить одне дерево прийняття рішень. За рахунок цього, він зручний для первинного аналізу даних, наприклад, що б перевірити на наявність зв'язків між змінними та іншим.
Плюси:
Швидка побудова моделі
Легко інтерпретується (через простоту моделі, можна легко відобразити дерево і простежити за всіма вузлами дерева)
Мінуси:
Часто сходиться на локальному вирішенні (наприклад, на першому кроці була вибрана гіперплощина, яка максимально ділить простір на цьому кроці, але при цьому це не призведе до оптимального рішення)
2. Random Forest
Random forest (Випадковий ліс) - метод, придуманий після CART одним з четвірки – Лео Брайманом у співавторстві з Адель Катлер в основі якого лежить використання комітету (ансамблю) дерев прийняття рішень.
Суть алгоритму, що на кожній ітерації робиться випадкова вибірка змінних, після чого, на цій новій вибірці запускають побудова дерева прийняття рішень. При цьому проводиться "bagging" - вибірка випадкових двох третин спостережень для навчання, а залишившася третина використовується для оцінки результату. Таку операцію роблять сотні або тисячі разів. Результуюча модель буде буде результатом "голосування" набору отриманих при моделюванні дерев.
Плюси:
Висока якість результату, особливо для даних з великою кількістю змінних і малою кількістю спостережень.
Можливість распаралелювання
Не вимагається тестова вибірка
Мінуси:
Кожне з дерев величезне, в результаті модель виходить також величезна
Довга побудова моделі, для досягнення хороших результатів.
Складна інтерпретація моделі (Сотні або тисячі великих дерев складні для інтерпретації)
Хід роботи
Ми маємо вибірку, яка показує чи покупець покупку ноутбуку чи ні, яка описуються такими характеристиками: фірма, процесор, оперативна пам’ять та ціна. Залежно від вибраних характеристик покупець вирішує здійснити покупку чи ні. Вибірка представлена у Таблиця 1.
Таблиця 1
Фірма
Процесор(GHz)
Оперативна пам’ять(GB)
Ціна(грн)
Покупка
Asus
1,8
2
3520
Ні
Lenovo
2,0
3
2860
Так
Acer
1,6
2
2970
Так
Asus
1,6
2
3300
Ні
Lenovo
2,2
4
3200
Так
Acer
1,8
2
3150
Так
Asus
2,2
4
4800
Ні
Dell
2,2
4
4550
Так
HP
2,0
2
3600
Ні
Lenovo
2,4
4
3450
Так
Acer
2,0
4
3380
Так
HP
1,8
2
3300
Ні
Dell
2,4
4
4900
Ні
Dell
2,6
6
6300
Так
Будуємо правила класифікації за 1R-алгоритмом. З Таблиця 1 ми бачимо, що характеристика ціна представлена різними числовими значеннями. Тому, для зменшення кількості правил, розіб’ємо ці характеристики по певних проміжках:
Ціна:
2860 2970 3150 3200 3300 3380 3450 3520 3600 4550 4800 4900 6300
Так Ні
В даному випадку діапазон значень можна розбити наступним чином:
{2860…3200;3300…3520;3600…6300}
В Таблиця 2 наведемо правила класифікації.
Таблиця 2
Правило
Помилка
Якщо (фірма = Asus) тоді (покупка = ні)
0/3
Якщо (фірма = Aser) тоді (покупка = так)
0/3
Якщо (фірма = Dell) тоді (покупка = ні)
1/3
Якщо (фірма = HP) тоді (покупка = ні)
0/2
Якщо (фірма = Lenovo) тоді (покупка = так)
0/3
Якщо (процесор = 1,6) тоді (покупка = так)
1/2
Якщо (процесор = 1,8) тоді (покупка = ні)
1/3
Якщо (процесор = 2,0) тоді (покупка = так)
1/3
Якщо (процесор = 2,2) тоді (покупка = так)
1/3
Якщо (процесор = 2,4) тоді (покупка = так)
1/2
Якщо (процесор = 2,6) тоді (покупка = так)
0/1
Якщо (оперативна пам’ять = 2) тоді (покупка = ні)
2/6
Якщо (оперативна пам’ять = 3) тоді (покупка = так)
0/1
Якщо (оперативна пам’ять = 4) тоді (покупка = так)
2/6
Якщо (оперативна пам’ять = 6) тоді (покупка = так)
0/1
Якщо (ціна = 2860…3450) тоді (покупка = так)
2/8
Якщо (ціна = 3520…6300) тоді (покупка = ні)
2/6
Будуємо дерево рішень за допомогою методу класифікації CART. Вузлами цього дерева будуть критерії з Таблиця 2, а листками – прийняття рішення про покупку.
/
Висновок: На даній лабораторній роботі я оволодів методами побудови правил класифікації та навчився застосовувати ці знання на практиці.
20.01.2014 19:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора