Introducere
Arborii de decizie (DT) sunt o metodă de învățare supravegheată neparametrică utilizată pentru clasificare și regresie. Scopul este de a crea un model care prezice valoarea unei variabile țintă prin învățarea unor reguli simple de decizie deduse din caracteristicile datelor.
Entropie
Scopul antrenamentului este de a găsi cele mai bune împărțiri în noduri pentru a găsi cel mai optim arbore. Împărțirile se fac folosind câteva criterii precum: Entropie.
Există multe definiții ale entropiei, cum ar fi:
-
Entropia corespunde cantității de informații conținute într-o sursă de informații.
-
Entropia poate fi văzută și ca aleatorie sau măsurarea surprizei într-un set.
-
Entropia este o metrică care măsoară imprevizibilitatea sau impuritatea din sistem.
În arborii de decizie, vom considera entropia ca măsură a purității în interiorul unui nod. Scopul modelului arborelui de decizie este de a reduce entropia nodurilor la fiecare divizare:
Astfel, dorim să maximizăm diferența dintre entropia nodului părinte și entropia nodurilor copil. Această diferență se numește Câștig de informații.
Entropia $H$ a unei multimi $X$ este formulata matematic dupa cum urmeaza:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Câștig de informații
Câștigul de informații este diferența dintre entropia nodului părinte și suma ponderată a entropiilor nodurilor de copil și, astfel, poate fi formulată după cum urmează:
$$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$$
$$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$$
Unde:
-
$H(.)$ este entropia.
-
$Y$ este populația anterioară divizării, reprezintă nodul părinte.
-
$X$ este variabila pe care dorim să o folosim pentru împărțire.
-
$x$ este o valoare unică a lui X.
-
$Y[X==x]$ este o listă împărțită cu doar valori $x$.
hai sa luam un exemplu corect:
Vom calcula câștigul de informații atunci când împărțim nodul părinte utilizând valorile lui X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Mai întâi, calculăm entropia nodului părinte:
$$ H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow) $$
$$ = - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3 $$
\
Apoi, vom calcula probabilitatea internă a fiecărui nod copil după împărțire folosind valorile unice ale lui X:
$$ unique(X) = [Circle, Square] $$
$$ \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square) $$
$$ + P(Circle|X) \times H(Y | X = Circle) $$
$$ = \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle) $$
Ca:
-
$H(Y | X = Pătrat)$ : reprezintă entropia primului nod copil.
-
$H(Y | X = Cerc)$ : reprezintă entropia celui de-al doilea nod copil.
\
Începem cu primul nod copil:
$$ H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square) $$
$$ - P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square) $$
$$ = - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23 $$
\
Și apoi al doilea nod copil:
$$ H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle) $$
$$ - P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle) $$
$$ = - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28 $$
\
În cele din urmă, înlocuim entropiile în formula Câștig de informații:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
$$ = 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041 $$
\
\
După cum s-a afirmat mai înainte, obiectivul divizării nodului este de a maximiza câștigul de informații și, astfel, de a minimiza Entropia în nodul copil rezultat. Pentru a face acest lucru, trebuie să încercăm să împărțim nodul cu seturi diferite de intrări $ X_1, X_2, \ldots, Xn $ și păstrăm doar împărțirea care maximizează câștigul de informații:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Când să încetezi divizarea
Împărțirea nodurilor în arborii de decizie este recursivă, deci trebuie să existe un criteriu pe care să-l putem folosi pentru a opri împărțirea. Acestea sunt unele dintre cele mai implementate criterii:
-
Când nodul este pur: H(nodul) = 0. Este inutil să împărțiți nodul în continuare.
-
Numar maxim de adancime: Putem seta o adancime maxima pe care modelul o poate atinge, inseamna ca chiar daca nodul nu este pur scindarea este oprita.
-
Număr minim de mostre pe nod: De asemenea, putem seta un număr minim $N$ de mostre pe nod. Dacă numărul de eșantioane per nod este egal cu $N$, atunci oprim divizarea chiar dacă nodul nu este pur.
Până la sfârșitul antrenamentului ( divizarea ), fiecare nod care se bazează pe sfârșitul arborelui de decizie este numit „Frunză”, deoarece nu este o rădăcină a niciunui subarbore. Fiecare frunză va reprezenta randamentul clasa cu cele mai multe mostre.
Concluzie
Arborele de decizie este unul dintre cei mai faimoși algoritmi de învățare automată datorită eficienței, fundalului intuitiv și implementării simple. Acest algoritm poate fi utilizat în continuare cu variabile numerice independente (Arbore de decizie Gaussian) și poate fi extins pentru a rezolva și sarcini de regresie.
