Дървото на решенията е един от най-мощните „алгоритми за контролирано обучение“, който се използва както за класификация, така и за регресия. Състои се от блок-схема като дървовидна структура, където всеки вътрешен възел представлява тест на атрибут, всеки клон представлява резултат от теста и всеки листов възел (терминален възел) съдържа етикет на клас. Той се конструира чрез рекурсивно разделяне на данните за обучение на подмножества въз основа на стойностите на атрибутите, докато не бъде изпълнен критерий за спиране, като максималната дълбочина на дървото или минималния брой проби, необходими за разделяне на възел.

По време на обучението алгоритъмът на дървото на решенията избира най-добрия атрибут за разделяне на данните въз основа на показател като ентропия или примес на Джини, който измерва нивото на произволност или нечистота в подмножествата. Целта е да се намери атрибутът, който максимизира придобиването на информация или намаляването на примесите след разделянето.

Какво е дърво на решенията?

Дървото на решенията е йерархичен модел, използван в подкрепа на вземането на решения, който изобразява решенията и техните потенциални резултати, включвайки случайни събития, разходи за ресурси и полезност. Този алгоритмичен модел използва условни контролни изрази и е „непараметрично“ контролирано обучение, полезно както за задачи за класификация, така и за регресия.

Терминология на дървото на решенията

Някои от общите технически термини, използвани при обсъждането на дърветата на решенията, са следните:

  • Коренен възел:Най-горният възел в дървото, който представлява пълния набор от данни. Това е началната точка на процеса на вземане на решение.
  • Решение/вътрешен възел: Възел, който символизира избор по отношение на функция за въвеждане. Разклоняването на вътрешни възли води до листови възли или други вътрешни възли.
  • Листов/терминален възел:Възел без дъщерни възли, който указва етикет на клас или числова стойност.
  • Разделяне:Процесът на разделяне на възел на два или повече подвъзела с помощта на критерий за разделяне и избрана функция.
  • Клон/поддърво: Подсекция на дървото на решенията, която започва от вътрешен възел и завършва на листов възел.
  • Родителски възел:Възелът, който се разделя на един или повече дъщерни възлиs.
  • Дъщерни възли:Възлите, които се появяват, когато родителският възел е разделен.
  • Примеси: Измерване на хомогенността на целевата променлива в подмножество от данни. Отнася се до степента на произволност или несигурност в набор от примери.
  • Дисперсия:Дисперсията измерва колко варират прогнозираните и целевите променливи в различните извадки от набор от данни. Използва се за проблеми с регресия в дървета на решения. Средна квадратна грешка, Средна абсолютна грешкаr, Freidman-mse илиполупоасоново отклонениесе използват за измерване на дисперсия за регресионните задачи в дървото на решенията.
  • Информационно усилване:Информационното усилване е мярка за намаляването на примесите, постигнато чрез разделяне на набор от данни по конкретна характеристика в дърво на решенията. Критерият за разделяне се определя от функцията, която предлага най-голяма печалба от информация. Използва се за определяне на най-информативната характеристика, която да се раздели във всеки възел на дървото, с цел създаване на чисти подмножества.
  • Подрязване: Процесът на премахване на клони от дървото, които не предоставят никаква допълнителна информация или водят до пренастройване.

Мерки за избор на приписване:

Едно дърво може да бъде наученочрез разделяне на изходния набор на подмножества въз основа на мерки за избор на атрибути. Мярката за избор на атрибут (ASM) е критерий, използван в алгоритмите на дървото на решенията за оценка на полезността на различни атрибути за разделяне на набор от данни. Целта на ASM е да идентифицира атрибута, който ще създаде най-хомогенните подмножества от данни след разделянето, като по този начин максимизира печалбата от информация. След това процесът се повтаря за всяко получено подмножество по рекурсивен начин, наречен рекурсивно разделяне. Рекурсията е завършена, когато цялото подмножество във възел има същата стойност като целевата променлива или когато разделянето вече не добавя стойност към прогнозите. Конструирането на класификатор на дърво на решенията не изисква знания за домейн или настройка на параметри и следователно е подходящо за проучвателно откриване на знания. Дърветата на решенията могат да обработват данни с голям размер.

Ентропия:

Ентропията е мярка за степента на произволност или несигурност в набора от данни. В случай на класификации, той измерва произволността въз основа на разпределението на етикетите на класа в набора от данни.

Ентропията за подмножество от оригиналния набор от данни с K брой класове за i-тия възел може да се дефинира като:

където,

  • k е конкретният клас от K класове
  • p(i,k) не трябва да е равно на 0.

Важни точки, свързани с ентропията:

  1. Ентропията е 0, когато наборът от данни е напълно хомогенен, което означава, че всеки екземпляр принадлежи към един и същи клас. Нулата показва липса на несигурност в извадката от набора от данни.
  2. когато наборът от данни е разделен по равно между множество класове, ентропията е на максималната си стойност. Следователно ентропията е най-висока, когато разпределението на етикетите на класа е равномерно, което показва максимална несигурност в извадката от набора от данни.
  3. Ентропията се използва за оценка на качеството на разделянето. Целта на ентропията е да се избере атрибутът, който минимизира ентропията на получените подмножества, чрез разделяне на набора от данни на по-хомогенни подмножества по отношение на етикетите на класа.
  4. Атрибутът с най-висока информационна печалба се избира като критерий за разделяне (т.е. намаляването на ентропията след разделяне на този атрибут) и процесът се повтаря рекурсивно, за да се изгради дървото на решенията.

Джини примес:

Gini Impurity е резултат, който оценява колко точно е разделянето между класифицираните групи. Примесите на Джини оценяват резултат в диапазона между 0 и 1, където 0 е, когато всички наблюдения принадлежат към един клас, а 1 е произволно разпределение на елементите в класовете. В този случай искаме да имаме възможно най-нисък резултат на индекса на Джини. Gini Index е показателят за оценка, който ще използваме, за да оценим нашия модел на дървото на решенията.

Тук,

  • pi е делът на елементите в множеството, които принадлежат към i-та категория.

Придобиване на информация:

Придобиването на информация измерва намаляването на ентропията или дисперсията, което е резултат от разделянето на набор от данни въз основа на конкретно свойство. Използва се в алгоритмите на дървото на решенията, за да се определи полезността на дадена функция чрез разделяне на набора от данни на по-хомогенни подмножества по отношение на етикетите на класа или целевата променлива. Колкото по-висока е печалбата от информация, толкова по-ценна е характеристиката при прогнозиране на целевата променлива.

Информационната печалба на атрибут A по отношение на набор от данни S се изчислява, както следва:

където,

  • A е конкретният атрибут или етикет на клас.
  • |H| е ентропията на извадка от набор от данни S.
  • |Hv| е броят на екземплярите в подмножеството S, които имат стойност V за атрибута A.

Придобиването на информация измерва намаляването на ентропията или дисперсията, постигнато чрез разделяне на набора от данни на атрибут A. Атрибутът, който максимизира привличането на информация, се избира като критерий за разделяне за изграждане на дървото на решенията.

Увеличаването на информацията се използва както в класификацията, така и в регресионните дървета с решения. При класификацията ентропията се използва като мярка за примес, докато при регресията дисперсията се използва като мярка за примес. Изчислението на притока на информация остава същото и в двата случая, с изключение на това, че във формулата се използва ентропия или дисперсия вместо ентропия.

Алгоритъмът на дървото на решенията:

Алгоритъмът на дървото на решенията, известен също като CART (алгоритъм на дървото за класификация и регресия), се използва за изграждане на дървото на решенията. Ето основните стъпки на алгоритъма CART:

  1. Основният възел на дървото трябва да бъде пълният набор от данни за обучение.
  2. Определете нечистотата на данните въз основа на всяка характеристика, присъстваща в набора от данни. Примесите могат да бъдат измерени с помощта на показатели като индекса на Джини или ентропия за класификация и средна квадратична грешка, средна абсолютна грешка, freidman-mse или отклонение на половин Поасон за регресия.
  3. След това изберете функцията, която води до най-голямо усилване на информацията или намаляване на примесите при разделяне на данните.
  4. За всяка възможна стойност на избраната характеристика, разделете набора от данни на две подмножества (ляво и дясно), едно, където характеристиката приема тази стойност, и друго, където не приема. Разделянето трябва да бъде проектирано така, че да създава подмножества, които са възможно най-чисти по отношение на целевата променлива.
  5. Въз основа на целевата променлива определете примесите на всяко получено подмножество.
  6. За всяко подмножество повторете стъпки 2–5 итеративно, докато бъде изпълнено условие за спиране. Например, условието за спиране може да бъде максимална дълбочина на дървото, минимален брой проби, необходими за извършване на разделяне или минимален праг на примеси.
  7. Задайте етикета на класа на мнозинството за задачите за класификация или средната стойност за задачите за регресия за всеки терминален възел в дървото.

Реализацията на Python може да бъде намерена на моята страница в Github.

Предимства на дървото на решенията:

  1. Лесно е за разбиране, тъй като следва същия процес, който човек следва, докато взема каквото и да е решение в реалния живот.
  2. Може да бъде много полезно за разрешаване на проблеми, свързани с вземане на решения.
  3. Помага да се мисли за възможните резултати от даден проблем.
  4. Има по-малка нужда от почистване на данни в сравнение с други алгоритми.

Недостатъци на дърветата на решенията:

  1. Дървото на решенията съдържа много слоеве, което го прави сложно.
  2. Възможно е да има проблем с пренастройване, който може да бъде решен с помощта на алгоритъма Random Forest.
  3. За повече етикети на клас изчислителната сложност на дървото на решенията може да се увеличи.

Кои са подходящи проблеми за обучение в дървото на решенията?

Обучението на дървото на решенията обикновено е най-подходящо за проблеми със следните характеристики:

  1. Екземплярите са представени чрез двойки атрибут-стойност.

В света на обучението в дървото на решенията ние обикновено използваме двойки атрибут-стойност за представяне на екземпляри. Екземплярът се дефинира от предварително определена група от атрибути, като температура, и съответната му стойност, като горещо. В идеалния случай искаме всеки атрибут да има краен набор от различни стойности, като горещо, леко или студено. Това улеснява конструирането на дървета на решенията. По-усъвършенстваната версия на алгоритъма обаче може да побере атрибути с непрекъснати числови стойности, като например представяне на температура с цифрова скала.

2. Целевата функция има дискретни изходни стойности.

Маркираната цел има различни резултати. Методът на дървото на решенията обикновено се използва за категоризиране на булеви стойности, като да или не. Подходите на дървото на решенията могат лесно да бъдат разширени за придобиване на функции с отвъд двойните възможни стойности на резултата. По-същественото разширение ни позволява да придобием знания за набелязаните цели с цифрови резултати, въпреки че използването на дървета на решенията в тази рамка е относително рядко.

3. Може да са необходими разграничителни описания.

Дърветата на решенията естествено представляват дизюнктивни изрази.

4. Данните за обучение може да съдържат грешки.

5. Данните за обучение може да съдържат липсващи атрибути.

В определени случаи входната информация, предназначена за обучение, може да има липсващи характеристики. Използването на подходи на дървото на решенията все още може да бъде възможно, въпреки неизвестните функции в някои примери за обучение. Например, когато се има предвид нивото на влажност през целия ден, тази информация може да е достъпна само за конкретен набор от тренировъчни екземпляри.