Що таке дерево рішень?

Що таке дерево рішень?

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

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

Формат дерева рішень

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

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

Алгоритми для дерев рішень

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

Що ж алгоритми використовуються для фактичного розділення даних на гілки та листя? Існує різні методи, які можна використовувати для розділення дерева, але найбільш поширений метод розділення, ймовірно, – це техніка, яка називається “рекурсивний бінарний розділ“. Коли проводиться цей метод розділення, процес починається з кореня, а кількість характеристик у наборі даних представляє можливу кількість можливих розділів. Використовується функція для визначення того, наскільки точним буде кожен можливий розділ, і розділ здійснюється за критерієм, який жертвує найменшою точністю. Цей процес проводиться рекурсивно, і підгрупи утворюються за допомогою тієї ж загальної стратегії.

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

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

sum(y – prediction)^2

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

Відносно функції вартості для класифікації, функція така:

G = sum(pk * (1 – pk))

Це оцінка Гіні, і це міра ефективності розділення, заснована на кількості екземплярів різних класів у групах, що результатують з розділення. Інакше кажучи, це кількісно оцінює, наскільки змішані групи після розділення. Оптимальне розділення відбувається, коли всі групи, що результатують з розділення, складаються тільки з входів одного класу. Якщо оптимальне розділення створено, значення “pk” буде 0 або 1, і G буде дорівнювати нулю. Ви можете здогадатися, що найгірше розділення відбувається, коли існує 50-50 представлення класів у розділі, у випадку бінарної класифікації. У цьому випадку значення “pk” буде 0,5, і G також буде 0,5.

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

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

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

Розгляд використання дерев рішень

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

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