Алгоритми на дървото на решенията - част 1

1. Въведението

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

2. Различни алгоритми на дървото на решенията

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

  • ID3 (Iterative Dichotomiser 3) е разработен през 1986 г. от Рос Куинлан. Алгоритъмът създава многопосочно дърво, намирайки за всеки възел (т.е. по алчен начин) категориалната характеристика, която ще доведе до най-голяма печалба от информация за категорични цели. Дърветата се отглеждат до техния максимален размер и след това обикновено се прилага стъпка на подрязване, за да се подобри способността на дървото да обобщава невидими данни [1].
  • C4.5 е разработен през 1993 г. от Ross Quinlan, е наследник на ID3 и премахна ограничението, че характеристиките трябва да бъдат категорични чрез динамично дефиниране на дискретен атрибут (на базата на числови променливи), който разделя непрекъснатата стойност на атрибута в дискретен набор от интервали. C4.5 преобразува обучените дървета (т.е. изхода на алгоритъма ID3) в набори от правила if-then. След това точността на всяко правило се оценява, за да се определи редът, в който трябва да се прилагат. Подрязването се извършва чрез премахване на предварително условие на правило, ако точността на правилото се подобрява без него [1].
  • C5.0 е последната версия на Quinlan под патентован лиценз. Той използва по-малко памет и изгражда по-малки набори от правила от C4.5, като същевременно е по-точен [1].
  • CART (дървета за класификация и регресия) е много подобен на C4.5, но се различава по това, че поддържа числови целеви променливи (регресия) и не изчислява набори от правила. CART конструира двоични дървета, използвайки функцията и прага, които дават най-голямото привличане на информация във всеки възел [1].

scikit-learn използва оптимизирана версия на алгоритъма CART

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

В съответствие с аналогията с дървото, терминологията е възприета от терминологията на дървото [2].

  • Коренен възел: е първият възел в дърветата на решенията
  • Разделяне: е процес на разделяне на възел на два или повече подвъзела, като се започне от основния възел
  • Възел: разделяне на резултатите от основния възел на подвъзли и разделяне на подвъзли на допълнителни подвъзли
  • Листов или краен възел: край на възел, тъй като възелът вече не може да бъде разделен
  • Подрязване: е техника за намаляване на размера на дървото на решенията чрез премахване на подвъзлите на дървото на решенията. Целта е да се намали сложността за подобрена точност на прогнозиране и да се избегне пренастройването
  • Клон/поддърво: Подраздел на цялото дърво се нарича клон или поддърво.
  • Родителски и дъщерен възел: Възел, който е разделен на подвъзли, се нарича родителски възел на подвъзли, докато подвъзлите са дъщерни на родителски възел.

4. Интуиция в дървото на решенията

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

Ние използваме набора от данни на Hitters, за да прогнозираме заплатата на бейзболния играч (средна дневна заплата) въз основа на годините (броят години, през които е играл във висшите лиги) и посещенията (броят попадения, които е направил през предходната година).

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

  1. Основният възел се разделя на подвъзел с правило за наблюдение, което има години ‹4,5 в левия клон, което означава, че играчите в набора от данни с години‹4,5, имащи средна заплата в дневник, е 5,107 и ние правим прогноза за e5,107 хиляди долара, т.е. $165,174 за тези играчи
  2. Играчи с Години›=4,5 се разпределят към десния клон и след това тази група се подразделя допълнително на Посещения ‹ 177,5 със средна заплата за загуба от 6.
  3. Играчи с Години ›=4,5 се разпределят към десния клон и след това тази група се подразделя допълнително на Посещения ›= 177,5 със средна загуба от заплата от 6,74

В този случай може да се види, че дървото на решенията прави сегмент в три региона, където този регион определя заплатите на бейзболните играчи и може да се каже, че регионът е граница на решение [3].

Тези три региона могат да бъдат записани като

  • R1 ={X | Години‹4.5 }
  • R2 ={X | Години›=4.5 ,Посещения‹117.5 }
  • R3 ={X | Години›=4.5 , Посещения›=117.5 }.

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

5. Разделяне в дървета на решенията

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

f е функцията за извършване на разделянето, Dp и Dj са набор от данни на родителя, j-ти дъщерен възел, I е нашата мярка за примеси, Np е общият брой проби в родителския възел и Nj е броят проби в j-тия дъщерен възел.

Както можем да видим, печалбата от информация е просто разликата между примесите на родителския възел и сумата от примесите на дъщерния възел - колкото по-ниска е примесата на дъщерните възли, толкова по-голяма е печалбата от информация. въпреки това, за опростяване и за намаляване на пространството за комбинаторно търсене, повечето библиотеки (включително scikit-learn) прилагат двоични дървета на решения. Това означава, че всеки родителски възел е разделен на два дъщерни възела, D-ляви D-десен.

мярката за примеси прилага двоични дървета за решения и трите мерки за примеси или критерия за разделяне, които обикновено се използват в двоични дървета за вземане на решения, са Примес на Джини (IG), ентропия (IH) и грешка при неправилна класификация (IE) [4]

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

Според Уикипедия [5],

Използван от алгоритъма CART (дърво за класификация и регресия) за класификационни дървета, Примесът на Джини е мярка за това колко често произволно избран елемент от набора би бил неправилно етикетиран, ако е бил етикетиран произволно според към разпределението на етикетите в подмножеството.

Математически можем да напишем Джини примес по следния начин

където jе броят класове, присъстващи във възела, а pе разпределението на класа във възела.

Проста симулация с Набор от данни за сърдечни заболявания с 303 реда и 13 атрибута. Целта се състои от 138 стойност 0 и 165 стойност 1

За да изградим дърво на решенията от набора от данни и да определим кое разделяне е най-добро, имаме нужда от начин за измерване и сравняване на примесите на Gini във всеки атрибут. Най-ниската стойност на Gini Impurity на първата итерация ще бъде коренният възел. можем да запишем уравнение 3 като:

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

Как да измерим примесите на Джини в половия атрибут

Джини примес — ляв възел

Джини примес — десен възел

Сега, след като измерихме примеса Gini за двата листни възела. Можем да изчислим общия примес на Джини със средно тегло. Левият възел представлява 138 пациента, докато десният възел представлява 165 пациента

Общо Джини примеси — листен възел

Как да измерим Gini Purity във Fbs (кръвна захар на гладно) атрибут

Джини примес — ляв възел

Джини примес — десен възел

Общо Джини примеси — листен възел

Как да се измери Gini Purity в атрибут Exang (ангина, предизвикана от физическо натоварване)

Джини примес — ляв възел

Джини примес — десен възел

Общо Джини примеси — листен възел

Fbs (кръвна захар на гладно) има най-ниското Джини примес, така че го използвайте в коренния възел

5.2 Ентропия

Използва се от алгоритмите за генериране на дърво ID3, C4.5 и C5.0. Придобиването на информация се основава на концепцията за ентропия, мярката за ентропия се определя като [5]:

където jе броят класове, присъстващи във възела, а pе разпределението на класа във възела.

В същия случай и същия „набор от данни“ се нуждаем от начин за измерване и сравняване на ентропията във всеки атрибут. Най-високата стойност на ентропия на първата итерация ще бъде коренният възел.

Първо трябва да изчислим ентропията в атрибута Target

Как да измерите ентропията в атрибута Sex

Ентропия — Пол = 0

Ентропия — Пол = 1

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

Ентропия - Секс

Как да измервате ентропията в атрибут Fbs

Ентропия — Fbs = 0

Ентропия — Fbs = 1

Ентропия — Fbs

Как да измервате ентропията в атрибут Exang

Ентропия — Exang = 0

Ентропия — Exang = 1

Ентропия — Exang

Fbs (кръвна захар на гладно) има най-високото примеси на Джини, така че ще го използваме в коренния възел, точно същите резултати, които получихме от Примесите на Джини.

5.3 Неправилно класифициране на примес

Друга мярка за примес е неправилно класифицирането примес. Математически можем да напишем неправилно класифициране примес, както следва

От гледна точка на качеството, този индекс не е най-добрият избор, тъй като не е особено чувствителен към различни вероятностни разпределения (които могат лесно да насочат селекцията към подразделение, използвайки Джини или ентропия)[6].

6. Предимства и недостатъци на дърветата

Предимства

  1. Дърветата са много лесни за обяснение на хората. Всъщност те са дори по-лесни
    за обяснение от линейната регресия!
  2. Някои хора вярват, че дърветата на решенията отразяват по-точно човешкото
    вземане на решения, отколкото регресионните и класификационните подходи
    , видяни в предишните глави.
  3. Дърветата могат да бъдат показани графично и лесно се интерпретират дори от
    неспециалист (особено ако са малки).
  4. Дърветата могат лесно да се справят с качествени предиктори, без да е необходимо
    да създават фиктивни променливи[3].

Недостатъци

  1. За съжаление, дърветата обикновено нямат същото ниво на предсказваща точност като някои от другите подходи за регресия и класификация [3].

Продължаване на обучението — Процес на разделяне в дърветата на решения

  1. Класификация в дървото на решенията — стъпка по стъпка CART (Дърво на класификация и регресия) — част 2)
  2. Регресия в дървото на решенията — CART стъпка по стъпка (Дърво на класификация и регресия) — част 3)

* Пакетът scikit-learn прилага CART като дърво на решенията по подразбиране.

За мен

Аз съм специалист по данни, фокусирам се върху машинното обучение и дълбокото обучение. Можете да се свържете с мен от Medium и Linkedin

Моят уебсайт: https://komuternak.com/

Справка

  1. Sklearn - Дървета на решенията
  2. https://gdcoder.com/decision-tree-regressor-explained-in-depth/
  3. Въведение в статистическото обучение
  4. Рашка, Себастиан. Машинно обучение на Python
  5. https://en.wikipedia.org/wiki/Decision_tree_learning
  6. Бонакорсо, Джузепе. Алгоритъм за машинно обучение