Summary  
This chapter explains how to evaluate and choose the best split at decision nodes by computing Gini impurity or entropy and selecting the feature–threshold pair that minimizes the weighted impurity (maximizes information gain).

General domain of usage  
Classification tasks in machine learning

Under træning skal vi finde **det bedste split ved hver beslutningsnode**. Når vi opdeler data i to noder, sigter vi efter, at forskellige klasser er i separate noder.

- **Bedste scenarie:** alle datapunkter i en node tilhører samme klasse;
- **Værste scenarie:** et lige antal datapunkter for hver klasse.

## Gini-urenhed

For at måle hvor god en opdeling er, kan vi beregne **Gini-urenheden**. Det er sandsynligheden for, at hvis vi **tilfældigt** vælger to punkter fra en node (med tilbagelægning), vil de tilhøre **forskellige klasser**. Jo lavere denne sandsynlighed (urenhed) er, desto bedre er opdelingen.

Du kan beregne Gini-urenheden for **binær klassifikation** ved hjælp af følgende formel:
$$
\text{gini} = 1 - p_0^2 - p_1^2 = 1 - (\frac{m_0}{m})^2 - (\frac{m_1}{m})^2
$$

Hvor
- $$m_i$$ - antal forekomster af klasse $$i$$ i en node;
- $$m$$ - antal forekomster i en node;
- $$p_i = \frac{m_i}{m}$$ - sandsynlighed for at vælge klasse $$i$$.

Og for **multiklassifikation** er formlen:
$$
\text{gini} = 1 - \sum_{i=0}^C p_i^2 = 1 - \sum_{i=0}^C(\frac{m_i}{m})^2
$$

Hvor
- $$C$$ - antal klasser.

Vi kan måle, hvor god opdelingen er, ved at tage **den vægtede sum af Gini-scorer** for begge noder opnået fra en opdeling. Det er den værdi, vi ønsker at **minimere**.

For at opdele en beslutningsnode skal vi finde en egenskab at opdele på og tærskelværdien:

Ved et beslutningspunkt finder algoritmen **grådigt** den bedste tærskelværdi for hver funktion. Derefter vælger den det split med **lavest Gini-urenhed** blandt alle funktioner (hvis der er lighed, vælges tilfældigt).

## Entropi

**Entropi** er et andet mål for urenhed. For et binært klassifikationsproblem beregnes entropien $$H$$ for en node ved hjælp af formlen:

$$
H(p) = -p \log_2(p) - (1 - p) \log_2(1 - p)
$$

hvor:

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

For et **multiklasse-klassifikationsproblem** beregnes entropien $$H$$ for en node ved hjælp af formlen:

$$
H(p_1, p_2, \dots, p_k) = -\sum_{i=1}^{k} p_i \log_2(p_i)
$$

hvor:

- $$k$$ er antallet af klasser;
- $$p_i$$ er andelen af eksempler, der tilhører klasse $$i$$ i noden.

På samme måde som Gini-impuritet kan vi måle, hvor god en opdeling er, ved at beregne **den vægtede sum af entropiværdier** for de børnenoder, der opnås fra opdelingen. Dette er den værdi, vi ønsker at **minimere** for at **maksimere informationsgevinsten**.

Entropien er **maksimal**, når alle klasser er lige repræsenteret. Den er **minimal** (0), når alle eksempler tilhører **én klasse** (rent node).

Bemærk

Behersk de centrale klassifikationsalgoritmer, der driver moderne maskinlæring. Udforsk hvordan modeller som k-NN, logistisk regression, beslutningstræer og random forests foretager forudsigelser, evaluerer deres nøjagtighed, og forstå hvornår hver model bør anvendes. Opbyg færdigheder til at sammenligne modeller og vælge den bedste til dine data.

Opdag, hvordan k-nærmeste naboer-algoritmen foretager forudsigelser baseret på lighed. Lær at håndtere flere egenskaber, justere parametre og anvende krydsvalidering for at forbedre nøjagtigheden.

Forstå, hvordan logistisk regression modellerer sandsynligheder og klassificerer udfald. Øv implementering, fortolkning af beslutningsgrænser og anvendelse af regularisering for at forhindre overfitting.

Lær, hvordan beslutningstræer opdeler data i meningsfulde grupper baseret på featureværdier. Udforsk, hvordan parametre som trædybde og minimum antal prøver per blad påvirker modellens ydeevne og generalisering.

Undersøg, hvordan random forests kombinerer flere beslutningstræer for at forbedre nøjagtighed og robusthed. Forstå betydningen af tilfældighed og anvend denne ensemble-metode på virkelige data.

Evaluering af modeller ved hjælp af metrikker såsom nøjagtighed, præcision, recall og F1-score. Lær at fortolke forvekslingsmatrixer og sammenligne flere klassifikatorer for at identificere den bedst præsterende model.

Opdeling af Noderne

Gini-urenhed

Entropi