Защо Entropy се използва за вземане на решения в дървото на решенията??

Защо Entropy се използва за вземане на решения в дървото на решенията??

Ако сте начинаещ в машинното обучение, тогава това съмнение трябва да е достигнало до вас, че „защо ентропията е от решаващо значение за вземане на решение в DT???“. Нека се потопим в темата.

Какво е ентропия?

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

където pi е вероятността за i-тия клас.

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

Както знаем, ентропията е мярка за безпорядък или несигурност, т.е. ентропията е индикатор колко объркани са вашите данни.

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

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

Защо ентропия в дървото на решенията?

В дърветата на решенията целта е да се изчистят данните. Опитвате се да разделите вашите данни и да групирате извадките заедно в класовете, към които принадлежат. Знаете техния етикет, тъй като конструирате дърветата от комплекта за обучение. Вие увеличавате максимално чистотата на групите, доколкото е възможно, всеки път, когато създавате нов възел на дървото (което означава, че разрязвате своя набор на две). Разбира се, в края на дървото искате да имате ясен отговор.

Горната фигура изобразява процеса на разделяне. имаме набор от зелени и лилави кръгове. Решението започва с изчисляване на стойностите на характеристиките в първоначалния набор. Въз основа на техните стойности те са разделени на две групи. В този пример, след разделянето, комплектът изглежда по-подреден, тъй като повечето от зелените кръгове са в Set1, а повечето от лилавите кръгове са в Set2.

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

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

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

Математиката зад ентропията

Да приемем, че имаме N елемента и тези елементи попадат в две категории, n имат етикет1 и m=N-n елемента имат етикет2. Нека въведем вероятностите на два етикета:

Ентропията на множеството се дава от следното уравнение:

Набор или възел е чист, ако съдържа подобни елементи (т.е. елементи с еднакви етикети) и разхвърлян, ако съдържа елементи с различни етикети. Когато в набора няма елемент с етикет 1 (p=0) или ако наборът е пълен с елементи с етикет 1 (p=1), ентропията е нула. Ако имате половината с Етикет 1, половината с Етикет 2 (p=1/2), ентропията е максимална (равна на 1, тъй като е логаритмична база 2).

Тази функция количествено определя бъркотията на данните.

Как се оценява ентропията?

В дърветата на решенията при всяко разклоняване входният набор се разделя на 2. Нека разберем как сравнявате ентропията преди и след разделянето. Представете си, че започвате с разхвърлян набор с ентропия едно (половина/половина, p=q). В най-лошия случай може да бъде разделен на 2 разхвърляни комплекта, където половината от елементите са означени с 1, а другата половина имат етикет 2 във всеки комплект. Следователно ентропията на всеки от двата резултатни комплекта е 1. В този сценарий бъркотията не се е променила и бихме искали да имаме същата ентропия преди и след разделянето. Не можем просто да сумираме ентропиите на двете множества. Решение, често използвано в математиката, е да се изчисли средната ентропия на двете групи. В този случай средната стойност е единица. Но в дърветата на решенията вместо това се изчислява претеглена сума от ентропии (претеглена от размера на двете подмножества):

където N1 и N2 са броят елементи от всеки комплект след разделянето, а E1 и E2 са тяхната съответна ентропия. Придава по-голямо значение на набора, който е по-голям (ако има такъв). Идеята е, че е малко по-добре, ако големият комплект стане по-подреден, тъй като изисква повече усилия за подреждане. Представете си най-лошия случай, когато набор от 1000 елемента е разделен на две, с набор от 999 елемента и набор от 1 елемент. Последният набор има ентропия нула, тъй като съдържа само един елемент, един етикет. Но това не е наистина важно, тъй като по-голямата част от данните все още са объркани в по-големия набор. Така че на двата комплекта трябва да се придаде значение спрямо техния размер.

Ако имате повече от 2 етикета, можете да обобщите формулата за ентропия, както следва:

където pi са съотношенията на елементите на всеки етикет в набора. Това е съвсем просто!

Заключение

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

Използвайки ентропията, дърветата на решенията подреждат повече, отколкото класифицират данните.