Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Методичні вказівки
до лабораторної роботи № 1
“ Data Mining – класифікація та регресія.
Методи побудови правила класифікації”
з дисципліни
“Інтелектуальний аналіз даних”
для студентів базового напрямку підготовки по спеціальності
“ Комп’ютерні науки ” (шифр 0804)
Львів-2012
Методичні вказівки до лабораторної роботи № 4 “Data Mining – класифікація та регресія. Методи побудови правила класифікації” з дисципліни “Інтелектуальний аналіз даних” для студентів спеціальності - шифр 0804 “Комп’ютерні науки”/ Укл. доц. Ковівчак Я.В., Львів: Національний університет “Львівська політехніка”, 2012.
Методичні вказівки обговорено та схвалено на засіданні кафедри АСУ Протокол № ___________ від «___»___________2012 р.
Завідувач кафедрою АСУ ______________ Медиковський М. О.
Методичні вказівки обговорено та схвалено на засіданні методичної комісії базового напрямку підготовки
Протокол № ___________ від «___»___________2012 р.Протокол № ___________ від «___»___________2012 р.
Лабораторна робота № 1
Методи побудови правила класифікації.
Мета: Оволодіти методами побудови правил класифікації та навчитись застосовувати ці знання на практиці.
Теоретична частина:
Data Mining – сукупність методів виявлення в даних раніше невідомих, нетривіальних, практично корисних і доступних інтерпретацій знань, необхідних для прийняття рішень в різноманітних сферах людської діяльності.
Завдання класифікації
Класифікація є найбільш простою і одночасно найбільш часто розв'язуваною задачею Data Mining. Зважаючи на поширеність задач класифікації необхідне чітке розуміння суті цього поняття.
Наведемо кілька визначень.
Класифікація - системний розподіл досліджуваних предметів, явищ, процесів за родами, видами, типами, з якими-небудь істотними ознаками для зручності їх дослідження; угрупування вихідних понять і розташування їх у певному порядку, що відбиває ступінь цієї схожості.
Класифікація - впорядкована по деякому принципу множина об'єктів, які мають подібні класифікаційні ознаки (одну або декілька властивостей), обраних для визначення схожості або відмінності між цими об'єктами.
Класифікація вимагає дотримання наступних правил:
Розрізняють:
В залежності від обраних ознак, їх поєднання та процедури поділу понять класифікація може бути:
Під класифікацією будемо розуміти віднесення об'єктів (спостережень, подій) до одного з наперед відомих класів.
Класифікація - це закономірність, що дозволяє робити висновок щодо визначення характеристик конкретної групи. Таким чином, для проведення класифікації повинні бути присутніми ознаки, що характеризують групу, до якої належить та чи інша подія або об'єкт (зазвичай при цьому на підставі аналізу вже класифікованих подій формулюються якісь правила).
Класифікація відноситься до стратегії навчання з вчителем (supervised learning), яке також іменують контрольованим або керованим навчанням.
Завданням класифікації часто називають пророкування категоріальної залежної змінної (тобто залежної змінної, яка є категорією) на основі вибірки неперервних і / або категоріальних змінних.
Наприклад, можна передбачити, хто з клієнтів фірми є потенційним покупцем певного товару, а хто - ні, хто скористається послугою фірми, а хто - ні, і т.д. Цей тип завдань відноситься до завдань бінарної класифікації, в них залежна змінна може приймати тільки два значення (наприклад, так чи ні, 0 або 1).
Інший варіант класифікації виникає, якщо залежна змінна може приймати значення з деякого множини визначених класів. Наприклад, коли необхідно передбачити, яку марку автомобіля захоче купити клієнт. У цих випадках розглядається безліч класів для залежної змінної.
Класифікація може бути одномірною (за однією ознакою) та багатовимірної (з двох і більше ознаками).
Багатовимірна класифікація була розроблена біологами при вирішенні проблем дискримінації для класифікування організмів. Однією з перших робіт, присвячених цьому напряму, вважають роботу Р. Фішера (1930 р.), в якій організми розділялися на підвиди залежно від результатів вимірювань їх фізичних параметрів. Біологія була і залишається найбільш популярним і зручним середовищем для розробки багатовимірних методів класифікації.
Методи
Для класифікації використовуються різні методи. Основні з них:
класифікація за допомогою дерев рішень;
Класифікація за допомогою дерев рішень
Дерево прийняття рішень - це дерево, в листках якого стоять значення цільової функції, а в інших вузлах - умови переходу (наприклад "СТАТЬ є ЧОЛОВІЧА"), що визначають по якому з ребер йти. Якщо для даного спостереження умова істина то здійснюється перехід по лівому ребру, якщо ж брехня - по правому.
Основні методи класифікації за допомогою дерев рішень
Нижче перераховані кілька основних методів, які використовують дерева прийняття рішень. Їх короткий опис, плюси і мінуси.
1. CART
CART (англ. Classification and regression trees - Класифікаційні та регресійні дерева) був першим з методів, придуманий в 1983 четвіркою відомих вчених в галузі аналізу даних: Лео Брайман, Джером Фрідман, Річард Олшен і Стоун
Суть цього алгоритму полягає в звичайному побудові дерева прийняття рішень, не більше і не менше.
На першій ітерації ми будуємо всі можливі (в дискретному сенсі) гіперплощини, які розбивали б наш простір на два. Для кожного такого розбиття простору обраховується кількість спостережень у кожному з підпросторів різних класів. В результаті вибирається таке розбиття, яке максимально виділило в одному з підпросторів спостереження одного з класів. Відповідно, це розбиття буде нашим коренем дерева прийняття рішень, а листами на даній ітерації будуть два розбиття.
На наступних ітераціях ми беремо один гірший (в сенсі ставлення кількості спостережень різних класів) лист і проводимо ту ж операцію по розбиттю його. В результаті цей лист стає вузлом з якимось розбиттям, і двома листами.
Продовжуємо так робити, поки не досягнемо обмеження по кількості вузлів, або від однієї ітерації до іншої перестане поліпшуватися загальна помилка (кількість неправильно класифікованих спостережень всім деревом). Однак, отримане дерево буде "перенавчене" (буде підігнано під навчальну вибірку) і, відповідно, не буде давати нормальні результати для інших даних. Для того, що б уникнути "перенавчання", використовують тестові вибірки (або крос-валідацію) і, відповідно, проводиться зворотний аналіз (так званий pruning), коли дерево зменшують в залежності від результату на тестовій вибірці.
Відносно простий алгоритм, в результаті якого виходить одне дерево прийняття рішень. За рахунок цього, він зручний для первинного аналізу даних, наприклад, що б перевірити на наявність зв'язків між змінними та іншим.
Плюси:
Мінуси:
2. Random Forest
Random forest (Випадковий ліс) - метод, придуманий після CART одним з четвірки – Лео Брайманом у співавторстві з Адель Катлер в основі якого лежить використання комітету (ансамблю) дерев прийняття рішень.
Суть алгоритму, що на кожній ітерації робиться випадкова вибірка змінних, після чого, на цій новій вибірці запускають побудова дерева прийняття рішень. При цьому проводиться "bagging" - вибірка випадкових двох третин спостережень для навчання, а залишившася третина використовується для оцінки результату. Таку операцію роблять сотні або тисячі разів. Результуюча модель буде буде результатом "голосування" набору отриманих при моделюванні дерев.
Плюси:
Мінуси:
3. Stochastic Gradient Boosting
Stochastic Gradient Boosting (Стохастичне градієнтне додавання) - метод аналізу даних, представлений Джеромом Фрідманом у 1999 році, і представляє собою рішення задачі регресії (до якої можна звести класифікацію) методом побудови комітету (ансамблю) "слабких" прогнозуючих дерев прийняття рішень.
На першій ітерації будується обмежене по кількості вузлів дерево прийняття рішень. Після чого обчислюється різниця між тим, що передбачило отримане дерево помножене на learnrate (коефіцієнт "слабкості" кожного дерева) і шуканої змінної на цьому кроці.
Yi +1 = Yi-Yi * learnrate
І вже по цій різниці будується наступна ітерація. Так продовжується, поки результат не перестане поліпшуватися. Тобто на кожному кроці ми намагаємося виправити помилки попереднього дерева. Однак тут краще використовувати перевірочні дані (що не брали участь в моделюванні), так як на навчальних даних можливо «перенавчання».
Плюси:
Мінуси:
Метод опорних векторів
Метод опорних векторів (Support Vector Machine - SVM) відноситься до групи граничних методів. Вона визначає класи за допомогою меж областей.
За допомогою даного методу вирішуються завдання бінарної класифікації. Мета методу опорних векторів - знайти площину, що розділяє дві множини об'єктів В основі методу лежить поняття площин рішень.Площина розділяє об'єкти з різною класовою приналежністю.
Приклад 1
мал.1. Поділ класів прямою лінією
На мал.1 наведено приклад, в якому беруть участь об'єкти двох типів. лінія яка розділяє задає границю, праворуч від якої - всі об'єкти типу brown (коричневий), а зліва - типу yellow (жовтий). Новий об'єкт, що потрапляє направо, класифікується як об'єкт класу brown або - як об'єкт класу yellow, якщо він розташувався по ліву сторону від розділяючої прямої. У цьому випадку кожен об'єкт характеризується двома вимірами.
Приклад 2
мал.2.
безліч зразків поділено на два класи:
жовті об'єкти належать класу А, коричневі - класу В.
Метод SVM
Вирішення задачі бінарної класифікації за допомогою методу опорних векторів полягає в пошуку деякої лінійної функції, яка правильно розділяє набір даних на два класи.
Задача 1
Розглянемо задачу класифікації, де число класів дорівнює двом.
Задачу можна сформулювати як пошук функції f (x), приймаючої значення менше нуля для векторів одного класу і більше нуля - для векторів іншого класу. В якості вихідних даних для вирішення поставленого завдання, тобто пошуку класифікуючої функції f (x), дано тренувальний набір векторів простору, для яких відома їх приналежність до одного з класів. Сімейство класифікуючих функцій можна описати через функцію f (x). Гіперплощина визначена вектором а й значенням b, тобто f (x) = ax + b.
Вирішення даної задачі проілюстровано на мал.4.
Мал.4. лінійний SVM
В результаті вирішення задачі, тобто побудови SVM-моделі, знайдена функція, що приймає значення менше нуля для векторів одного класу і більше нуля - для векторів іншого класу.
Для кожного нового об'єкта негативне або позитивне значення визначає приналежність об'єкта до одного з класів.
Найкращою функцією класифікації є функція, для якої очікуваний ризик мінімальний. Поняття очікуваного ризику в даному випадку означає очікуваний рівень помилки класифікації.
Безпосередньо оцінити очікуваний рівень помилки побудованої моделі неможливо, це можна зробити за допомогою поняття емпіричного ризику. Однак слід враховувати, що мінімізація останнього не завжди призводить до мінімізації очікуваного ризику. Цю обставину слід пам'ятати при роботі з відносно невеликими наборами тренувальних даних.
Емпіричний ризик - рівень помилки класифікації на тренувальному наборі.
Таким чином, в результаті вирішення задачі методом опорних векторів для лінійно роздільних даних ми отримуємо функцію класифікації, яка мінімізує верхню оцінку очікуваного ризику.
Однією з проблем, пов'язаних з вирішенням завдань класифікації розглянутим методом, є та обставина, що не завжди можна легко знайти лінійну межу між двома класами.
У таких випадках один з варіантів - збільшення розмірності, тобто перенесення даних з площини в тривимірний простір, де можливо побудувати таку площину, яка ідеально розділить безліч зразків на два класи. Опорними векторами в цьому випадку будуть служити об'єкти з обох класів, які є екстремальними.
Таким чином, за допомогою додавання так званого оператора ядра і додаткових розмірностей, знаходяться межі між класами у вигляді гіперплощин.
Однак слід пам'ятати: складність побудови SVM-моделі полягає в тому, що чим вище розмірність простору, тим складніше з ним працювати. Один з варіантів роботи з даними високої розмірності - це попереднє застосування будь-якого методу пониження розмірності даних для виявлення найбільш істотних компонент, а потім використання методу опорних векторів.
Як і будь-який інший метод, метод SVM має свої сильні і слабкі сторони, які слід враховувати при виборі даного методу.
Плюси:
Мінуси:
Метод опорних векторів дозволяє:
Метод "найближчого сусіда"
Метод "найближчого сусіда" або системи міркувань на основі аналогічних випадків.
Слід відразу зазначити, що метод "найближчого сусіда" ("nearest neighbour") відноситься до класу методів, робота яких грунтується на зберіганні даних в пам'яті для порівняння з новими елементами. При появі нового запису для прогнозування знаходяться відхилення між цим записом та подібними наборами даних, і найбільш подібна (або ближній сусід) ідентифікується.
Приклад 3
При розгляді нового клієнта банку, його атрибути порівнюються з усіма існуючими клієнтами даного банку (дохід, вік і т.д.). Безліч "найближчих сусідів" потенційного клієнта банку вибирається на підставі найближчого значення доходу, віку і т.д.При такому підході використовується термін "k-найближчий сусід" ("k-nearest neighbour"). Термін означає, що вибирається k "верхніх" (найближчих) сусідів для їх розгляду в якості безлічі "найближчих сусідів". Оскільки не завжди зручно зберігати всі дані, іноді зберігається тільки безліч "типових" випадків.
У такому випадку використовуваний метод називають міркуванням за аналогією (Case Based Reasoning, CBR), міркуванням на основі аналогічних випадків, міркуванням по прецедентів.
Прецедент - це опис ситуації в поєднанні з детальним зазначенням дій, що вживаються в даній ситуації.
Підхід, заснований на прецедентах, умовно можна поділити на наступні етапи:
Таким чином, висновок, заснований на прецедентах, являє собою такий метод аналізу даних, який робить висновки щодо даної ситуації за наслідками пошуку аналогій, що зберігаються в базі прецедентів.
Даний метод за своєю суттю відноситься до категорії "навчання без учителя", тобто є "самонавчається" технологією, завдяки чому робочі характеристики кожної бази прецедентів з плином часу і накопиченням прикладів поліпшуються. Розробка баз прецедентів по конкретній предметній області відбувається на природному для людини мовою, отже, може бути виконана найбільш досвідченими співробітниками компанії - експертами або аналітиками, працюючими в даній предметній області.
Однак це не означає, що CBR-системи самостійно можуть приймати рішення. Останнє завжди залишається за людиною, даний метод лише пропонує можливі варіанти вирішення і вказує на самий "розумний" з її точки зору.
Плюси:
Мінуси:
Байєсова класифікація
Альтернативні назви: байєсове моделювання, байєсова статистика, метод байєсових мереж.
Байєсова класифікація використовувалася для формалізації знань експертів в експертних системах, також застосовується в якості одного з методів Data Mining.
Так звана наївна класифікація або наївно-байєсовський підхід (naive-bayes approach) є найбільш простим варіантом методу, що використовує Байєсовські мережі. При цьому підході вирішуються завдання класифікації, результатом роботи методу є так звані "прозорі" моделі.
"Наївна" класифікація - досить прозорий і зрозумілий метод класифікації. "Наївною" вона називається тому, що виходить з припущення про взаємну незалежності ознак.
Властивості наївної класифікації:
Плюси:
Мінуси:
Контрольні запитання:
Навчальне видання
“Інтелектуальний аналіз даних”
Методичні вказівки до лабораторної роботи № 4 “Data Mining – класифікація та регресія. Методи побудови правила класифікації ” з дисципліни “ Інтелектуальний аналіз даних ” для студентів спеціальності 0804 “Комп’ютерні науки”
Укладач:
доц. Ковівчак Ярослав Васильович
Комп’ютерний набір, верстку та редагування
здійснили ст. гр. КН-30, каф. АСУ, Никитенко А.Ю., Хомицький Р.Б., Труняк М.С.