Будь умным!

У вас вопросы?
У нас ответы:) SamZan.net

2012 Методичні вказівки до лабораторної роботи 4 ldquo;Dt Mining ~ класифікація та регресія

Работа добавлена на сайт samzan.net:


Методичні вказівки

до лабораторної роботи № 1

“ Data Mining – класифікація та регресія.

Методи побудови правила класифікації”

з дисципліни

“Інтелектуальний аналіз даних”

для студентів базового напрямку підготовки по спеціальності

“ Комп’ютерні науки ” (шифр 0804)

Львів-2012

Методичні вказівки до лабораторної роботи № 4 “Data Mining – класифікація та регресія. Методи побудови правила класифікації” з дисципліни “Інтелектуальний аналіз даних” для студентів спеціальності - шифр 0804 “Комп’ютерні науки”/ Укл. доц. Ковівчак Я.В., Львів: Національний університет “Львівська політехніка”, 2012.  

Методичні вказівки обговорено та схвалено на засіданні кафедри АСУ Протокол № ___________ від «___»___________2012 р.

Завідувач кафедрою АСУ   ______________   Медиковський М. О.

Методичні вказівки обговорено та схвалено на засіданні методичної комісії базового напрямку підготовки

Протокол № ___________ від «___»___________2012 р.Протокол № ___________ від «___»___________2012 р.

Лабораторна робота № 1

Методи побудови правила класифікації.

Мета: Оволодіти методами побудови правил класифікації та навчитись застосовувати ці знання на практиці.

Теоретична частина:

Data Mining – сукупність методів виявлення в даних раніше невідомих, нетривіальних, практично корисних і доступних інтерпретацій знань, необхідних для прийняття рішень в різноманітних сферах людської діяльності.

Завдання класифікації

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

Наведемо кілька визначень.

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

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

Класифікація вимагає дотримання наступних правил:

  •  В кожному акті поділу необхідно застосовувати тільки одну ознаку;
  •  Розподіл має бути пропорційним, тобто загальний обсяг видових понять повинен дорівнювати обсягу діленого родового поняття;
  •  Члени поділу повинні взаємно виключати один одного, їх обсяги не повинні перехрещуватися;
  •  Розподіл має бути послідовним.

Розрізняють:

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

В залежності від обраних ознак, їх поєднання та процедури поділу понять класифікація може бути:

  •  простою - поділ родового поняття тільки за ознакою і тільки один раз до розкриття усіх видів. Прикладом такої класифікації є дихотомія, при якій членами поділу бувають тільки два поняття, кожне з яких є суперечним іншому (тобто дотримується принцип: "А і не А");
  •  складною - застосовується для поділу одного поняття з різних підстав і синтезу таких простих розподілів в єдине ціле. Прикладом такої класифікації є періодична система хімічних елементів.

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

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

Класифікація відноситься до стратегії навчання з вчителем (supervised learning), яке також іменують контрольованим або керованим навчанням.

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

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

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

Класифікація може бути одномірною (за однією ознакою) та багатовимірної (з двох і більше ознаками).

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

Методи

Для класифікації використовуються різні методи. Основні з них:

класифікація за допомогою дерев рішень;

  1.  Байєсова (“наївна”) класифікація;
  2.  Класифікація за допомогою штучних нейронних мереж;
  3.  Класифікація методом опорних векторів;
  4.  Статистичні методи, зокрема, лінійна регресія;
  5.  Класифікація за допомогою методу найближчого сусіда;
  6.  Класифікація CBR-методом;
  7.  Класифікація за допомогою генетичних алгоритмів.
  8.  Класифікація за допомогою дерев рішень

Класифікація за допомогою дерев рішень

Дерево прийняття рішень - це дерево, в листках  якого стоять значення цільової функції,  а в інших вузлах - умови переходу (наприклад "СТАТЬ  є ЧОЛОВІЧА"), що визначають по якому з ребер йти. Якщо для даного спостереження умова істина то здійснюється перехід по лівому ребру, якщо ж брехня - по правому.

Основні методи класифікації за допомогою дерев рішень

 Нижче перераховані кілька основних методів, які використовують дерева прийняття рішень. Їх короткий опис, плюси і мінуси.

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

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

Плюси:

  •  Висока якість результату, особливо для даних з великою кількістю спостережень і малою кількістю змінних.
  •  Порівняно (з попереднім методом) малий розмір моделі, так як кожне дерево обмежена заданими розмірами.
  •  Порівняно (з попереднім методом) швидкий час побудови оптимальної моделі

Мінуси:

  •  Вимагається тестова вибірка (або крос-валідація)
  •  Відносно слабка стійкість до помилкових даних та «перенавчання»
  •  Складна інтерпретація моделі (Так само як і в Random forest)

Метод опорних векторів

Метод опорних векторів (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)  є найбільш простим варіантом методу, що використовує Байєсовські мережі. При цьому підході вирішуються завдання класифікації, результатом роботи методу є так звані "прозорі" моделі.

"Наївна" класифікація - досить прозорий і зрозумілий метод класифікації. "Наївною" вона називається тому, що виходить з припущення про взаємну незалежності ознак.

Властивості наївної класифікації:

  •  використання всіх змінних і визначення всіх залежностей між ними;
  •  наявність двох припущень щодо змінних;
  •  всі змінні є однаково важливими;
  •  всі змінні є статистично незалежними, тобто значення однієї змінної нічого не говорить про значення іншої.

Плюси:

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

Мінуси:

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

Контрольні запитання:

  1.  Які є методи побудови правил класифікації.
  2.  Що являє собою Data Mining?
  3.  Яка буває класифікація?
  4.  Дотримання яких правил вимагає класифікація?
  5.  Чому не можна в кожному акті поділу застосовувати кілька ознак?
  6.  Яким має бути розподіл для класифікації?
  7.  Що таке крос-валідація і для чого вона потрібна?
  8.  Які є методи класифікації, які вимагають крос-валідації?
  9.  Що таке прецедент?
  10.  Чому Байєсовська класифікація називається також «наївною»?
  11.  Що таке емпіричний ризик та коли він трапляється?
  12.  Що таке «перенавчання»?
  13.  Де використовується коефіцієнт слабкості learnrate?
  14.  В чому полягає суть методу «найближчого сусіда»?
  15.  Де застосовується Байєсовська класифікація і чому?

Навчальне видання

“Інтелектуальний аналіз даних”

Методичні вказівки до лабораторної роботи № 4  “Data Mining – класифікація та регресія. Методи побудови правила класифікації ”  з дисципліни “ Інтелектуальний аналіз даних ” для студентів спеціальності 0804 “Комп’ютерні науки”

Укладач:

доц. Ковівчак Ярослав Васильович

Комп’ютерний набір, верстку та редагування

здійснили ст. гр. КН-30, каф. АСУ,  Никитенко А.Ю., Хомицький Р.Б., Труняк М.С.




1. По содержанию хозяйственных операций документы делятся на материальные денежные и расчетные
2. Кругосвет
3.  Исходные данные на проектирование 1 2
4. Основы менеджмента
5. І. РІЧКИ Гідрологія ~ це- Класичні праці яких вчених випередили європейську гідрологічну науку XVIII
6. Экономическое развитие России в 19001917 годы
7. Тема 1 ЕСТЕСТВЕННОНАУЧНЫЕ ОСНОВЫ ФИЗИЧЕСКОГО ВОСПИТАНИЯ 1 В связи с усилением синтеза структурных б
8. ЛИЧНАЯ ИНФОРМАЦИЯ Фамилия Имя Отчество
9. Задание и исходные данные
10. Доклад- Ударение (акцент)
11. Контрольная работа- Конституционное право граждан на обращение
12. Инспекция Федеральной налоговой службы РФ
13. от субъективного фактора ~ решения предпринимателей инвестировать; 2 объективных факторов ~ нормы процен
14. Философия славянофилов
15. реферату- Зірочник середній
16. Психологические особенности подростков, испытывающих состояние одиночества
17. реферату- Радіація і життєдіяльність людиниРозділ- БЖД Радіація і життєдіяльність людини План 1
18. Статья- Источники Истории Апостольского Века
19. Лабораторная работа 2м Ознакомление с ранжированными переменными и массивамив среде Mthcd Цель работы- 1
20. Виктория расположен на первом этаже бизнес ~ центра Виктория находящийся на проспекте Победителей59

Материалы собраны группой SamZan и находятся в свободном доступе