Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Правило відсікання




Зупинка навчання

Правило розбиття

Для побудови дерева на кожному внутрішньому вузлі необхідно знайти таку умову (перевірку), яка б розбивала множину, асоційовану з цим вузлом на підмножини. В якості такої перевірки повинен бути вибраний один з атрибутів. Загальне правило для вибору атрибута: обраний атрибут повинен розбити множину так, щоб одержані в результаті підмножини складалися з об'єктів, які належать до одного класу, або були максимально наближені до цього, тобто кількість об'єктів з інших класів ("домішків") в кожній з цих множин було якомога менше.

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

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

· Побудувати дерево.

· Відсікти або замінити піддеревом ті гілки, які призводять до зростання помилки.

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

Метод опорних векторів - це набір схожих алгоритмів виду «навчання із вчителем». Ці алгоритми зазвичай використовуються для задач класифікації та регресійного аналізу. Метод належить до розряду лінійних класифікаторів. Також може розглядатись як особливий випадок регуляризації за А. Н. Тихоновим. Особливою властивістю методу опорних векторів є безперервне зменшення емпіричної помилки класифікації та збільшення проміжку. Тому цей метод також відомий як метод класифікатора з максимальним проміжком. Основна ідея методу опорних векторів – перевід вихідних векторів у простір більш високої розмірності та пошук роздільної гіперплощини з максимальним проміжком у цьому просторі. Дві паралельні гіперплощини будуються по обидва боки гіперплощини, що розділяє наші класи. Роздільною гіперплощиною буде та, що максимізує відстань до двох паралельних гіперплощин. Алгоритм працює у припущенні, що чим більша різниця або відстань між цими паралельними гіперплощинами, тим меншою буде середня помилка класифікатора. Часто в алгоритмах машинного навчання виникає необхідність класифікувати дані. Кожен об'єкт даних представлений як вектор (точка) у р -вимірному просторі (послідовність р чисел) Кожна з цих точок належить тільки одному з двох класів. Нас цікавить, чи можемо ми розділити точки гіперплощиною розмірністю (р -1). Це типовий випадок лінійної роздільності. Таких гіперплощин може бути багато. Тому цілком природно вважати, що максимізація зазору між класами сприяє більш впевненій класифікації. Тобто чи можемо ми знайти таку гіперплощину, щоб відстань від неї до найближчої точки було максимальною. Це б означало, що відстань між двома найближчими точками, що лежать по різні сторони гіперплощини, максимальна. Якщо така гіперплощина існує, то вона нас буде цікавити найбільше; вона називається оптимальною розділяючою гіперплощиною, а відповідний їй лінійний класифікатор називається оптимально поділяючим класифікатором. Алгоритм найближчого сусіда — один з перших і найбільш простих евристичних методів розв'язування задачі комівояжера. Відноситься до категорії жадібних алгоритмів. За кожен крок його виконання до знайденої частини маршруту додається нове ребро. Алгоритм припиняє роботу, коли розв’язок знайдено і не намагається його покращити. Формулюється таким чином:

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

Кроки алгоритму (варіант 1):

1. Вибрати довільну точку V1

2. Т1 = V1

3. Для і=2 до і=N виконати:

4. Вибрати точку Vi, найближчу до точки Ті-1

5. Ti = Vi

6. Т N +1 = V1

7. Кінець алгоритму

Кроки алгоритму (варіант 2):

1. Довільно обрати поточну точку

2. Знайти найкоротше ребро, що сполучає поточну точку з досі ще не відвіданою точкою V

3. Зробити точку V поточною

4. Позначити точку V, як відвідану

5. Коли всі точки розмірності N відвідані, припинити пошук маршруту

6. Перейти до другого кроку

Алгоритм простий у реалізації, швидко виконується, але, як і інші «жадібні» алгоритми, може видавати неоптимальні рішення. Обчислювальна складність алгоритму – O(n2). Результатом виконання алгоритму найближчого сусіда є маршрут, приблизно на 25% довший від оптимального. Одним з евристичних критеріїв оцінки рішення є правило: якщо шлях, пройдений на останніх кроках алгоритму, зіставний зі шляхом, пройденим на початкових кроках, то можна умовно вважати знайдений маршрут прийнятним, інакше, імовірно, існують кращі рішення. Інший варіант оцінки рішення полягає у використанні алгоритму нижньої граничної оцінки. Другий критерій оцінки рішення полягає в застосуванні алгоритму нижньої граничної оцінки. Для будь-якої кількості міст більшій за три в задачі комівояжера можна підібрати таке розташування міст (значення відстаней між вершинами графа і вказівка початкової вершини), що алгоритм найближчого сусіда буде видавати найгірше рішення. Метод Байєса - це простий класифікатор, заснований на імовірнісній моделі, що має сильне припущення незалежності компонент вектора ознак. Метод Байєса - це простий класифікатор, заснований на імовірнісній моделі, що має сильне припущення незалежності компонент вектора ознак. Розуміється, метод Байєса має недоліки: великий обсяг попередньою інформацією, «пригнічення» рідко зустрічаються діагнозів та ін. Однак у випадках, коли обсяг статистичних даних дозволяє застосувати метод Байєса, його доцільно використовувати як один з найбільш надійних і ефективних методів. Метод заснований на простій формулі Байєса. Якщо є стан (діагноз) Di і проста ознака kj, що зустрічається при цьому діагнозі, то ймовірність спільного появи подій (наявність у об'єкта стану Di і ознаки kj) P(Dikj) = P(Di)P(kj/Di) = P(kj)P(Di/kj). З цієї рівності випливає формула Байєса P(Di/kj) = P(Di)P(ki/Di)/P (kj). Дуже важливо визначити точний зміст всіх вхідних в цю формулу величин. P(Di) - ймовірність діагнозу Di, обумовлена ​​за статистичними даними (апріорна ймовірність діагнозу). Так, якщо попередньо обстежено N об'єктів і у Ni об'єктів малося стан Di, то P(Di) = Ni/N. P(kj/Di) - ймовірність появи ознаки kj у об'єктів зі станом Di. Якщо серед Ni об'єктів, що мають діагноз Di, у Nij проявився ознака kj, то P(kj/Di) = Nij/Ni. P(kj) - ймовірність появи ознаки kj у всіх об'єктах незалежно від стану (діагнозу) об'єкта. Нехай із загального числа N об'єктів ознака kj був виявлений у Nj об'єктів, тоді P(kj) = Nj/N. Для встановлення діагнозу спеціальне обчислення P(kj) не потрібно. Як буде ясно з подальшого, значення P(Di) і P(kj/Di), відомі для всіх можливих станів, визначають величину P(kj).




Поделиться с друзьями:


Дата добавления: 2015-05-24; Просмотров: 727; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.