Under opplæring må vi finne det beste delingspunktet ved hver beslutningsnode. Når vi deler dataene inn i to noder, er målet at ulike klasser havner i separate noder.

• Beste tilfelle: alle datapunkter i en node tilhører samme klasse;
• Verste tilfelle: like mange datapunkter for hver klasse.

Gini-impuritet

For å måle hvor god en deling er, kan vi beregne Gini-impuritet. Dette er sannsynligheten for at hvis vi tilfeldig trekker to punkter fra en node (med tilbakelegging), vil de tilhøre forskjellige klasser. Jo lavere denne sannsynligheten (impuriteten) er, desto bedre er delingen.

Du kan beregne Gini-impuritet for binær klassifisering ved å bruke følgende formel:

Hvor

• $m_i$ – antall forekomster av klasse $i$ i en node;
• $m$ – antall forekomster i en node;
• $p_i = \frac{m_i}{m}$ – sannsynlighet for å velge klasse $i$.

Og for multiklasse-klassifisering er formelen:

Hvor

• $C$ – antall klasser.

Kvaliteten på delingen kan måles ved å ta vektet sum av Gini-verdier for begge nodene som oppnås etter en deling. Dette er verdien vi ønsker å minimere.

For å dele en beslutningsnode må vi finne en egenskap å dele på og terskelen:

Ved et beslutningspunkt finner algoritmen grådig den beste terskelen for hver egenskap. Deretter velger den delingen med lavest Gini-impuritet blant alle egenskaper (ved likhet velges tilfeldig).

Entropi

Entropi er et annet mål på impuritet. For et binært klassifiseringsproblem beregnes entropien $H$ til en node med formelen:

hvor:

• $p$ er andelen positive eksempler (klasse 1);
• $1 - p$ er andelen negative eksempler (klasse 0).

For et multiklasse-klassifiseringsproblem beregnes entropien $H$ til en node med formelen:

hvor:

• $k$ er antall klasser;
• $p_i$ er andelen eksempler som tilhører klasse $i$ i noden.

På samme måte som for Gini-impuritet kan vi måle hvor god en deling er ved å beregne vektet sum av entropiverdier for barne-nodene som oppstår etter delingen. Dette er verdien vi ønsker å minimere for å maksimere informasjonsgevinsten.