Дървото на решенията е вид алгоритъм за контролирано обучение, който може да се използва както за регресия, така и за класификация.
Дървото на решенията е контролиран прогнозен модел, който може да се научи да предвижда, отговаряйки на набор от прости въпроси. Той отговаря на последователни въпроси, които ни изпращат по определен маршрут на дървото. Правилата за вземане на решения обикновено са под формата на изрази if-then-else. Колкото по-дълбоко е дървото, толкова по-сложни са правилата и по-подходящ моделът.
Как работи дървото на решенията?
Дърветата на решенията използват различни атрибути, за да разделят многократно данните на подмножества и повтарят процеса, докато подмножествата станат чисти. Чисто означава, че всички споделят една и съща целева стойност.
Как се прави разделяне или как дървото решава при коя променлива да се раздели?
Входните променливи могат да бъдат числови или категорични или комбинация от числови и категорични, независимо дали целевата променлива е числова, т.е. регресионен проблем, или целевата променлива е категорична, т.е. проблем с класификацията.
В случай на категорична входна променлива, трябва да намерим променлива, за да разделим набора от данни. За да изчислим тази променлива, трябва да разделим набора от данни с помощта на различни променливи и да изберем променливата, за която посоченият по-долу показател е най-добър.
В случай на цифрова входна променлива, трябва да намерим комбинация от променлива и стойност, за да разделим набора от данни. За да изчислим тази комбинация от променлива и стойност, трябва да разделим набора от данни с помощта на различни променливи и различни стойности на тези различни променливи и да изберем комбинацията от променлива и стойност, за която посоченият по-долу показател е най-добър.
Регресия
- Намаляване на стандартното отклонение
Класификация
- Придобиване на информация
- Джини примес
Намаляване на стандартното отклонение
Намаляването на стандартното отклонение е метод за разделяне на възела, използван, когато целевата променлива е непрекъсната. Използваме стандартно отклонение, за да изчислим хомогенността на числена извадка. Ако числената извадка е напълно хомогенна, нейното стандартно отклонение е нула.
Изчисляване на стандартното отклонение и коефициента на дисперсия съответно за един атрибут и за два атрибута.
Как работи
Стъпка 1: Изчислете стандартното отклонение на целта
Стъпка 2: Изчислете стандартното отклонение на всяко разделяне като среднопретеглено стандартно отклонение на дъщерните възли
Стъпка 3: Изберете клона за разделяне, който дава максимално намаление на стандартното отклонение
Стъпка 4: На практика имаме нужда от някои критерии за прекратяване. Проверете дали коефициентът на вариация на клона е по-малък от прага или не и/или когато в клона останат твърде малко екземпляри (n) (напр. 3), след това прекратете разделянето и свързаният листов възел получава средната стойност на целевата променлива .
Стъпка 5: Повторете горните стъпки, докато всички данни бъдат обработени.
Пример
Стъпка 1: Изчислява се стандартното отклонение на целта.
Стандартно отклонение (Играни часове) = 9,32
Стъпка 2: След това наборът от данни се разделя на различните атрибути. Изчислява се стандартното отклонение за всеки клон. Полученото стандартно отклонение се изважда от стандартното отклонение преди разделянето. Резултатът е намалението на стандартното отклонение
Стъпка 3: Атрибутът с най-голямото намаление на стандартното отклонение се избира за възел за решение.
Стъпка 4a: Наборът от данни се разделя въз основа на стойностите на избрания атрибут. Този процес се изпълнява рекурсивно на нелистовите клонове, докато не бъдат обработени всички данни.
На практика се нуждаем от някои критерии за прекратяване. Например, когато коефициентът на отклонение (CV) за клон стане по-малък от определен праг (напр. 10%) и/или когато в клона останат твърде малко екземпляри (n) (напр. 3).
Стъпка 4b: Подмножеството „Облачно“ не се нуждае от допълнително разделяне, тъй като неговата CV (8%) е по-малка от прага (10%). Свързаният листов възел получава средната стойност на подмножеството „Облачно“.
Стъпка 4c: Въпреки това, клонът „Слънчев“ има CV (28%) над прага (10%), което се нуждае от допълнително разделяне. Избираме „Windy“ като най-добрия възел след „Outlook“, защото има най-големия SDR
Тъй като броят на точките от данни и за двата клона (FALSE и TRUE) е равен или по-малък от 3, ние спираме по-нататъшното разклоняване и присвояваме средната стойност на всеки клон на свързания листов възел.
Стъпка 4d: Освен това „дъждовният“ клон има CV (22%), което е повече от прага (10%). Този клон се нуждае от допълнително разделяне. Избираме „Windy“ като най-добрия възел, защото има най-големия SDR.
Тъй като броят на точките от данни и за трите клона (Хладен, Горещ и Лек) е равен или по-малък от 3, ние спираме по-нататъшното разклоняване и присвояваме средната стойност на всеки клон на съответния листов възел.
Когато броят на екземплярите е повече от един в листов възел, ние изчисляваме средната стойност като крайна стойност за целта.
Придобиване на информация
Мярка за намаляване на ентропията след разделянето на набора от данни е печалбата от информация.
Придобиването на информация е статистическо свойство, което измерва колко добре даден атрибут разделя примерите за обучение според тяхната целева класификация.
Увеличаването на информацията, ако функцията X се използва за извършване на разделяне, може да бъде представена чрез
Придобиване на информация (T,X) = Ентропия (T) — Ентропия (T,X)
or
Където [претеглена средна стойност] * ентропия (деца) = (брой примери в левия дъщерен възел) / (общ брой примери в родителския възел) * (ентропия на левия възел) + (брой примери в десния дъщерен възел) / (общ брой примери в родителския възел) * (ентропия на десния възел)
Какво е ентропия?
Ентропията е начин за измерване на примесите. Това е мярка за случайност или непредсказуемост в набора от данни. Ентропията е мярка за безпорядък или несигурност и тъй като целта на моделите за машинно обучение като цяло е да намалят несигурността, колкото по-ниска е ентропията, толкова по-лесно е да се направи каквото и да е заключение от данните и напротив, колкото по-висока е ентропията, толкова по-трудно е да се направи всякакви заключения от тази информация.
Ентропия=−∑ pj log2pj
- Ентропията е 0, ако всички проби от възел принадлежат към един и същ клас (пробата е хомогенна)
Ентропия=−1log1=0
- Ентропията е максимална, ако имаме равномерно класово разпределение (пробата е разделена по равно)
Ентропия=−0,5log0,5−0,5log0,5=1
- Колкото по-голяма е ентропията на едно разделяне, толкова по-малко информация се получава от това разделяне. Колкото по-голяма е ентропията на разделянето, толкова по-малко се намалява разстройството/несигурността от целевата променлива
- Колкото по-малка е ентропията на едно разделяне, толкова повече информация се получава от това разделяне. Колкото по-малка е ентропията на разделянето, толкова повече разстройството/несигурността се намалява от целевата променлива
- Клон с ентропия 0 е листен възел.
- Клон с ентропия над 0 се нуждае от допълнително разделяне.
стъпки
- Изчислете ентропията на целта
- Изчислете ентропията на всяко разделяне като среднопретеглената ентропия на дъщерните възли
- Изберете разделянето с най-ниска ентропия или най-голямо усилване на информацията
- Повторете горните стъпки, докато постигнете хомогенни възли
Пример
Помислете за пример, при който изграждаме дърво на решенията, за да предвидим дали заем, даден на дадено лице, ще доведе до отписване или не. Цялата ни популация се състои от 30 екземпляра. 16 принадлежат към класа за отписване, а останалите 14 принадлежат към класа за неотписване. Имаме две функции, а именно „Баланс“, който може да приеме две стойности — „‹ 50K“ или „›50K“ и „Жилище“, който може да приеме три стойности — „СОБСТВЕН“, „НАЕМ“ или „ДРУГ“.
Точките са точките от данни с клас вдясно, а звездите са неотписаните. Разделянето на родителския възел на баланса на атрибутите ни дава 2 дъщерни възела. Левият възел получава 13 от общите наблюдения с 12/13 (вероятност 0,92) наблюдения от класа на отписване и само 1/13 (вероятност 0,08) наблюдения от класа без запис. Десният възел получава 17 от общото наблюдение с 13/17 (0,76 вероятност) наблюдения от класа без отписване и 4/17 (0,24 вероятност) от класа на отписване. Нека изчислим ентропията за родителския възел и да видим колко несигурност може да намали дървото чрез разделяне на Balance.
Разделяйки функцията, „Баланс“ води до повишаване на информацията от 0,37 за нашата целева променлива. Нека направим същото нещо за функцията „Жилище“, за да видим как се сравнява. Разделянето на дървото на Residence ни дава 3 дъщерни възела. Левият дъщерен възел получава 8 от общите наблюдения със 7/8 (0,88 вероятност) наблюдения от класа на отписване и само 1/8 (0,12 вероятност) наблюдения от класа без отписване. Средните дъщерни възли получават 10 от общия брой наблюдения с 4/10 (0,4 вероятност) наблюдения от класа на отписване и 6/10 (0,6 вероятност) наблюдения от класа без отписване. Десният дъщерен възел получава 12 от общия брой наблюдения с 5/12 (0,42 вероятност) наблюдения от класа на отписване и 7/12 (0,58) наблюдения от класа без отписване. Вече знаем ентропията за родителския възел. Просто трябва да изчислим ентропията след разделянето, за да изчислим информационната печалба от „Живането“
Информационната печалба от функцията Balance е почти 3 пъти повече от информационната печалба от Residence. Балансът предоставя повече информация за нашата целева променлива, отколкото Резиденцията. Това намалява повече безредици в нашата целева променлива. Алгоритъм на дървото на решенията ще използва този резултат, за да направи първото разделяне на нашите данни с помощта на баланс.
Индекс на Джини или примес на Джини
Това е критерий за минимизиране на вероятността от грешна класификация
Може да се разглежда като функция на разходите, използвана за оценка на разделянията в набора от данни.
Това е метрика за измерване колко често произволно избран елемент би бил идентифициран неправилно.
Изчислява се чрез изваждане на сумата от квадратите на вероятностите за всеки клас от единица. Gini Index работи с категоричната целева променлива „Успех“ или „Провал“. Той изпълнява само двоични разделяния.
Gini=1−∑ p²j
- Индексът на Джини е максимален, ако класовете са идеално смесени (пример в двоичен клас)
Gini=1−(p1²+p2²) =1−((0,5²) +(0,5²)) =0,5
- Атрибут с по-нисък gini индекс има по-малко шансове да бъде неправилно класифициран в сравнение с такъв с по-висок gini индекс. Следователно, изграждайки дървото на решенията, бихме предпочели да изберем атрибута/функцията с най-малък индекс Gini, за да направим разделянето.
- Gini се предпочита пред Entropy, тъй като е по-бърз в изчисленията
стъпки
- Изчислете Gini примесите на всяко разделяне като среднопретеглената Gini примеси на дъщерните възли
- Изберете разделянето с най-ниска стойност на Gini Impurity
- Повторете горните стъпки, докато постигнете хомогенни възли
Пример
Ще използваме същата извадка от данни, която използвахме за пример за получаване на информация. Нека се опитаме да използваме индекса Джини като критерий. Тук имаме 5 колони, от които 4 колони имат непрекъснати данни, а 5-та колона се състои от етикети на класове.
Атрибутите A, B, C, D могат да се разглеждат като предиктори, а етикетите на клас колона E могат да се разглеждат като целева променлива. За да конструираме дърво на решенията от тези данни, трябва да преобразуваме непрекъснати данни в категорични данни.
Избрахме някои произволни стойности, за да категоризираме всеки атрибут:
A
B
C
D
>= 5
>= 3.0
>=4.2
>= 1.4
< 5
< 3.0
< 4.2
< 1.4
Индекс Джини за Var A
Var A има стойност ›=5 за 12 записа от 16 и 4 записа със стойност ‹5 стойност.
За Var A ›= 5 & клас == положителен: 5/12
За Var A ›= 5 & клас == отрицателен: 7/12
gini(5,7) = 1- ((5/12)2 + (7/12)2 ) = 0,4860
За Var A ‹5 & клас == положителен: 3/4
За Var A ‹5 & клас == отрицателно: 1/4
gini(3,1) = 1- ((3/4)2 + (1/4)2 ) = 0,375
Чрез добавяне на тегло и сума на всеки от индексите Джини:
Индекс Джини за Var B
Var B има стойност ›=3 за 12 записа от 16 и 4 записа със стойност ‹5 стойност.
За Var B ›= 3 & клас == положителен: 8/12
За Var B ›= 3 & клас == отрицателен: 4/12
gini(8,4) = 1- ((8/12)2 + (4/12)2 ) = 0,446
За Var B ❤ & клас == положителен: 0/4
За Var B ❤ & клас == отрицателно: 4/4
gin(0,4) = 1- ((0/4)2 + (4/4)2 ) = 0
Индекс Джини за Var C
Var C има стойност ›=4,2 за 6 записа от 16 и 10 записа със стойност ‹4,2 стойност.
За Var C ›= 4.2 & клас == положителен: 0/6
За Var C ›= 4.2 & клас == отрицателен: 6/6
gini(0,6) = 1- ( (0/8)2 + (6/6)2 ) = 0
За Var C ‹ 4.2& клас == положителен: 8/10
За Var C ‹ 4.2 & клас == отрицателен: 2/10
gin(8,2) = 1- ((8/10)2 + (2/10)2 ) = 0,32
Индекс Джини за Var D
Var D има стойност ›=1,4 за 5 записа от 16 и 11 записа със стойност ‹1,4 стойност.
За Var D ›= 1.4 & клас == положителен: 0/5
За Var D ›= 1.4 & клас == отрицателен: 5/5
gini(0,5) = 1- ((0/5)2 + (5/5)2 ) = 0
За Var D ‹ 1.4 & клас == положителен: 8/11
За Var D ‹ 1.4 & клас == отрицателен: 3/11
gini(8,3) = 1- ((8/11)2 + (3/11)2 ) = 0,397
ПРОБЛЕМ С ДЪРВОТО НА РЕШЕНИЯ
Когато изграждаме дърво на решенията, то взема предвид всички колони в набора от данни и избира най-добрата колона клон по клон, за да направи разделянето. Така колоната, която е направила разделяне в основния възел, се счита за по-важна от колоните в другите клонове и следователно всички прогнози ще имат огромно влияние върху колоната в горната част и когато е в сценарий в реално време, ако има наблюдение, за което първата колона не е най-важната характеристика за правене на прогноза, моделът няма да успее да прогнозира добре.
Този проблем води до голяма дисперсия, т.е. точността намалява, когато променим набора от данни, за да прогнозираме. Решението е да се използва произволен горски модел, който намалява дисперсията чрез обучаващи модели, използващи произволно подмножество от характеристики върху произволно подмножество от проби. Така че изходът не е от едно дърво на решенията, където колоните с техните фиксирани нива на важност се използват за всички прогнози на извадките, а по-скоро от изхода на много дървета на решенията, където различни функции се считат за различни по важност.
Подрязване
Пренастройването е практически проблем при изграждането на модел на дърво на решенията. Можем да преодолеем проблема с пренастройването, като използваме алгоритъма на произволна гора или техниката на подрязване.
Подрязването е процес на премахване на листа и клони, за да се подобри работата на дървото на решенията. Подрязването е процес, обратен на разделянето.
Подрязването включва премахване на клоните, които използват функции с ниска важност. По този начин намаляваме сложността на дървото и по този начин увеличаваме неговата предсказваща сила чрез намаляване на прекомерното монтиране.
Предварително подрязване
При предварителната резитба спира изграждането на дървото малко по-рано. Този подход спира незначимите клонове от поколение. Той прекратява генерирането на нов клон въз основа на даденото условие. За предпочитане е да не се разделя възел, ако мярката му за доброта е под прагова стойност.
Подкастряне
Генерира се пълно дърво и след това маловажните клони се подрязват/премахват. Кръстосаното валидиране се извършва на всяка стъпка, за да се провери дали добавянето на новия клон води до повишаване на точността. Ако не, клонът се преобразува в листен възел.
Някои важни параметри за извършване на подрязване са max_leaf_nodes, който намалява броя на листовите възли, min_samples_leaf, който ограничава размера на листа на пробата, max_depth, който намалява дълбочината на дървото, за да се изгради обобщено дърво.
#datascience #machinelearningalgorithms #deeplearningalgorithms #data #algorithms #deloitteusi #deloitteuniversity #intel #target #pwcindia
