Under opplæring må vi finne det beste delingspunktet ved hver beslutningsnode. Når vi deler dataene i to noder, ønsker vi at ulike klasser skal havne 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:

Der

• $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:

Der

• $C$ - antall klasser.

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

For å splitte en beslutningsnode må vi finne et trekk å splitte 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 med 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.