Introduktion
Decision Trees (DTs) är en icke-parametrisk övervakad inlärningsmetod som används för klassificering och regression. Målet är att skapa en modell som förutsäger värdet av en målvariabel genom att lära sig enkla beslutsregler som härleds från datafunktionerna.
Entropi
Målet med träningen är att hitta de bästa klyvningarna i noderna för att hitta det mest optimala trädet. Uppdelningarna görs med hjälp av vissa kriterier som: Entropi.
Det finns många definitioner av entropi som:
-
Entropi motsvarar mängden information som finns i en informationskälla.
-
Entropi kan också ses som slumpmässigheten eller mätningen av överraskning i en uppsättning.
– Entropi är ett mått som mäter oförutsägbarheten eller orenheten i systemet.
I beslutsträd kommer vi att betrakta entropi som mått på renheten inuti en nod. Målet med beslutsträdsmodellen är att minska nodernas entropi vid varje delning:
Därför vill vi maximera skillnaden mellan entropin för modernoden och entropin för undernoderna. Denna skillnad kallas Informationsvinsten.
Entropin $H$ för en mängd $X$ är matematiskt formulerad enligt följande:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Informationsvinst
Informationsvinst är skillnaden mellan entropin för modernoden och den vägda summan av entropierna för chlidnoderna, och den kan därför formuleras enligt följande:
$$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])$$
var:
-
$H(.)$ är entropin.
-
$Y$ är populationen före uppdelningen, den representerar den överordnade noden.
-
$X$ är variabeln som vi vill använda för uppdelningen.
-
$x$ är ett unikt värde på X.
-
$Y[X==x]$ är en delad lista med endast $x$-värden.
låt oss ta ett riktigt exempel:
Vi kommer att beräkna informationsvinsten när vi dividerar modernoden genom att använda värdena på X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Först beräknar vi entropin för modernoden:
$$ 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 $$
\
Sedan kommer vi att beräkna den interna sannolikheten för varje barnnod efter uppdelningen genom att använda de unika värdena för 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) $$
Till exempel:
-
$H(Y | X = Square)$ : representerar entropin för den första underordnade noden.
-
$H(Y | X = Circle)$ : representerar entropin för den andra barnnoden.
\
Vi börjar med den första barnnoden:
$$ 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 $$
\
Och sedan den andra barnnoden:
$$ 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 $$
\
Slutligen ersätter vi entropierna i formeln Information Gain:
$$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 $$
\
\
Som nämnts tidigare är syftet med en noddelning att maximera informationsvinsten och därmed minimera entropin i den resulterande barnnoden. För att göra detta måste vi försöka dela noden med olika uppsättningar av ingångar $ X_1, X_2, \ldots, Xn $ och vi behåller bara splittringen som maximerar informationsvinsten:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
När ska man sluta dela
Noddelningen i beslutsträd är en rekursiv, så det måste finnas ett kriterium som vi kan använda för att stoppa uppdelningen. Dessa är några av de mest implementerade kriterierna:
-
När noden är ren: H(nod) = 0. Det är meningslöst att dela upp noden ytterligare.
-
Maximalt antal djup: Vi kan ställa in ett maximalt djup som modellen kan nå, det betyder att även om noden inte är ren stoppas uppdelningen.
-
Minsta antal sampel per nod: Vi kan också ställa in ett minsta antal $N$ av sampel per nod. Om antalet sampel per nod är lika med $N$ så slutar vi dela även om noden inte är ren.
I slutet av träningen (delningen) kallas varje nod som förlitar sig på slutet av beslutsträdet för ett "Löv", eftersom det inte är en rot till något underträd. Varje blad kommer att representera avkastningen klassen med flest prover.
Slutsats
Decision tree är en av de mest kända maskininlärningsalgoritmerna på grund av dess effektivitet, intuitiva bakgrund och enkla implementering. Denna algoritm kan vidare användas med numeriska oberoende variabler ( Gaussian Decision Tree ), och den kan utökas för att även lösa regressionsuppgifter.
