ID3 (algoritme)

Het ID3-algoritme is een algoritme dat kan worden gebruikt om een beslissingsboom te genereren. De methode werd door Ross Quinlan uitgevonden in 1986. ID3 is de voorloper van het C4.5-algoritme.

Het algoritme is gebaseerd op Ockhams scheermes: een voorkeur voor kleinere bomen boven grotere bomen. Echter, het genereert niet altijd de kleinste boom en is daarom een heuristiek. Geformulariseerd geldt het concept van Entropiemaximalisatie.

Bij de start van het algoritme wordt voor elk attribuut berekend waar de meeste 'winst' kan worden bepaald om als knoop te dienen.

$G(S,a)=Entropie(S)-\sum _{v\in V(a)}{\dfrac {|S_{v}|}{|S|}}Entropie(S_{v})$.

Dit wordt herhaald voor de overige data punten en attributen. Het resultaat is een beslissingsboom in de vorm van if-then regels.

Externe links

• Uitwerking van een voorbeeld
• Implementatie in Ruby
• Implementatie in Python
• Implementatie als onderdeel van een pakket Het Id3 algoritme, opgenomen in het weka-softwarepakket (Java)

Bronnen, noten en/of referenties