X Код для використання на сайті:
Ширина px

Скопіюйте цей код і вставте його на свій сайт

X Для завантаження презентації, скористайтесь соціальною кнопкою для рекомендації сервісу SvitPPT Завантажити собі цю презентацію

Презентація на тему:
Поняття про машинне навчання та Data Mining

Завантажити презентацію

Поняття про машинне навчання та Data Mining

Завантажити презентацію

Презентація по слайдам:

Слайд 1

Тема №13 Машинне навчання та Data Mining

Слайд 2

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

Слайд 3

Рівні навчання: класифікація Уїнстона шляхом програмування; шляхом пояснення; на прикладах; шляхом відкриття.

Слайд 4

Навчання на прикладах та індуктивні міркування Навчання на прикладах найтіснішим чином пов'язано з міркуваннями за індукцією.

Слайд 5

Поняття про Data Mining Інтелектуальний аналіз даних; отримання знань з даних. Одне з визначень: Data Mining - це дослідження і виявлення машиною в “сирих” даних прихованих знань, які раніше не були відомі, нетривіальні, практично корисні, доступні для інтерпретації людиною. “Пояснення” даних; пошук закономірностей.

Слайд 6

Схематична ілюстрація процесу Data Mining Первинна (“сира”) інформація Дані Знання

Слайд 7

Data Mining: деякі задачі та методики. Регресія; прогнозування. Класифікація (визначення класу об’єкта за його характеристиками). Зокрема, побудова дерев рішень. Пошук асоціативних правил. Алгоритм Apriori. Кластерний аналіз. Нейронні мережі. …

Слайд 8

Генетичні алгоритми: вступні слова Важливий підхід до пошуку рішень певної задачі. Типова модель – оптимізаційна задача: f(x1,...xn) -> max при заданих обмеженнях. Втім, оптимальне рішення знаходиться рідко; частіше – якесь наближення. Часто використовуються і для навчання, побудови певних структур тощо. Аналогія з механізмом еволюції, характерним для живої природи.

Слайд 9

Генетичні алгоритми: ключова ідея Пов’язуються з дослідженнями Холланда. Імітація еволюційних процесів. Репродукція – створення нових поколінь, селекція – відбір найкраще пристосованих.

Слайд 10

Основні поняття Популяція – скінченна множина індивидів (можливих рішень). Хромосома – окремий індивід (рішення); послідовність генів. Ген (можливо, окрема властивість) – атомарний елемент хромосоми. Функція пристосованості (fitness, функція оцінки) – міра пристосованості даного індивіда; цільова функція. На кожній ітерації генетичного алгоритму міра пристосованості кожного індивіда оцінюється саме за допомогою цієї функції. Покоління – чергова популяція в ГА.

Слайд 11

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

Слайд 12

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

Слайд 13

Алгоритм рулетки: формула q – кількість хромосом у популяції; F – міра пристосованості

Слайд 14

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

Слайд 15

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

Слайд 16

Кросовер: приклад 010|101 та 110|001 дають нащадків: 010|001 та 110|101 (точка розриву вибирається випадковим чином).

Слайд 17

ГА: простий ілюстративний приклад Знайти хромосому з найбільшою кількістю одиниць. Вважаємо, що хромосоми містять 12 генів, а популяція нараховує 8 хромосом.

Слайд 18

Початкова популяція Ch[1]=[111001100101] Ch[2]=[001100111010] Ch[3]=[011101110011] Ch[4]=[001000101000] Ch[5]=[010001100100] Ch[6]=[010011000101] Ch[7]=[101011011011] Ch[8]=[000010111100]

Слайд 19

Оцінка пристосованості F(ch[1])=7 F(ch[2])=6 F(ch[3])=8 F(ch[4])=3 F(ch[5])=4 F(ch[6])=5 F(ch[7])=8 F(ch[8])=5

Слайд 20

Селекція хромосом v(ch[1])=15,22 v(ch[2])=13,04 v(ch[3])=17,39 v(ch[4])=6,59 v(ch[5])=8,70 v(ch[6])=10,87 v(ch[7])=17,39 v(ch[8])=10,87 Нехай в результаті випадкового вибору сформовано батьківський пул: Ch[7] Ch[3] Ch[1] Ch[7] Ch[3] Ch[7] Ch[4] Ch[2]

Слайд 21

Генетичні оператори Кросовер. Пари: Ch[2] – Ch[7] s=4 Ch[1] – Ch[7] s=3 Ch[3] – Ch[4] s=11 Ch[3] – Ch[7] s=5 Мутація не застосовувалася

Слайд 22

Нова популяція 001111011011 8 101000111010 6 111011011011 9 101001100101 6 011101110010 7 001000101001 4 011101011011 8 101011110011 8

Слайд 23

Деякі типові задачі задача про рюкзак; задача коммівояжера.

Слайд 24

Особливості задач Для задачі про булевий вираз: бітове представлення. Кросовер: 010|101 та 110|001 дають нащадків: 010|001 та 110|101 (точка розриву вибирається випадковим чином). Мутація - випадкова зміна біту. Для задачі про рюкзак - окремий ген являє собою число предметів кожного типу. Для задачі комівояжера - упорядкований кросовер.

Слайд 25

Упорядкований кросовер для задачі комівояжера Дві точки розтину вибираються випадковим чином, але для обох батьків вони співпадають. Нащадки формуються так: спочатку для кожного з них копіюються фрагменти батьківських хромосом між точками розтину; потім кожний нащадок заповнюється містами з іншого батька після другої точки розтину зі збереженням порядку, але вже наявні міста пропускаються. Наприклад, пара (192 | 4657 | 83) та (459 | 1876 | 23) дає нащадків (239 | 4657 | 18) та (392 | 1876 | 45)

Слайд 26

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

Слайд 27

Властивості ГА Основним результатом вважається теорема про схеми: схеми малого порядку, з малим охопленням та з пристосованістю вищою за середню формують експоненційно зростаючу кількість своїх представників у наступних поколіннях генетичного алгоритму. Гіпотеза про будівельні блоки: генетичний алгоритм намагається досягти результату, близького до оптимального, за рахунок комбінування “хороших” схем малого порядку та з малим охопленням. Такі схеми називаються будівельними блоками (цеглинками). “Хороші” схеми – це нібито вдалі комбінації ознак, які мають бути збережені в наступних поколіннях.

Слайд 28

Пошук аналогій Одна з типових постановок задач: якщо А1, то Q1; A2 схоже на А1. Що, якщо А2 ? Типова схема: пошук схожостей (або відмінностей); модифікація дії на основі списку схожостей.

Слайд 29

Задача Еванса Дані малюнки А, В, С. Знайти малюнок Х, який відноситься до С так само, як В до А.

Слайд 30

Схема рішення Схема рішення: Потрібно знайти послідовність операцій f, яка переводить А до В, і послідовність g, яка переводить А до С. Далі або X1=g(B), або X2=f(C). Якщо Х1=Х2, рішення, отримані обома способами, співпадають, і утворюється т.зв. "квадрат Лейбніца".

Слайд 31

Засвоєння понять Загальна постановка задачі: сформувати опис поняття, такий, що всі позитивні навчальні приклади відповідають цьому опису, а всі негативні (ко