A-priori algoritme

In datamining is het a-priori algoritme een algoritme om associatieregels te leren uit een database met transacties, zoals gekochte producten in een supermarkt of bezochtte pagina's op een website. Het algoritme tracht associatieregels te leren door patronen te vinden in de data. Formeler gezegd tracht het algoritme verzamelingen van items te vinden die een minimaal aantal keer voorkomen in de data.

Achtergrond

We gebruiken de volgende database $D$ met tien transacties bij voorbeelden in dit artikel:

1	{ 1, 2, 3 }
2	{ 1, 2, 4, 5 }
3	{ 2, 5 }
4	{ 3, 4, 5 }
5	{ 1, 4, 5 }
6	{ 3, 4 }
7	{ 2, 4, 5 }
8	{ 2, 4, 5 }
9	{ 1, 3, 5 }
10	{ 2, 4 }

In de praktijk kan dit een deel van de database van een supermarkt zijn die per transactie bijhoudt welke producten er gekocht zijn.

Support van een itemverzameling

De support van een itemverzameling $X$ op een database $D$ met transacties is gedefinieerd als:

$support(X) = \frac{ | \{ t \in D \ | \ X \subseteq t \} | }{ | D | }$

Met andere woorden: de support van een itemverzameling is het aantal transacties waar de items van $X$ in voorkomen gedeeld door het aantal transacties in de database.

Voor de bovenstaande database geldt $support(\{ 2, 5 \}) = 0,4$ want er zijn vier van de tien transacties waar zowel item 2 als item 5 in voorkomt.

Algoritme

De invoer van het algoritme bestaat uit een database $D$ en een getal dat de minimale support aanduidt (deze kan door de gebruiker gekozen worden). Het doel van het algoritme is nu om zo groot mogelijke itemverzamelingen te vinden die de gewenste minimale support hebben. Het algoritme begint met itemverzamelingen met grootte 1 en het voegt telkens een item toe om te zien of grotere verzamelingen ook aan de minimale support voldoen.

Het algoritme bestaat uit twee fasen:

• het genereren van verzamelingen die mogelijk de minimale support hebben; dit worden kandidaten genoemd.
• het controleren van de kandidaten welke daarvan de minimale support hebben

Deze fasen worden per niveau uitgevoerd, dus voor itemverzamelingen met grootte 1, met grootte 2, enzovoort.

Een verzameling met lengte $n$ is een kandidaatverzameling als elk van de deelverzamelingen met lengte $n - 1$ de minimale support hebben.

Het algoritme stopt wanneer er geen kandidaten meer gevonden kunnen worden.

Voorbeeld

Het uitvoeren van het a-priori algoritme op bovenstaande database $D$ en minimale support = 0,3 geeft het volgende resultaat.

Allereerst bekijkt het algoritme de volgende verzamelingen met grootte 1:

	Support
{ 1 }	0,4
{ 2 }	0,6
{ 3 }	0,4
{ 4 }	0,7
{ 5 }	0,7

Elk van de itemverzamelingen heeft minimaal support 0,3 dus elk van de items kan gebruikt worden om kandidaten te genereren:

	Support
{ 1, 2 }	0,2
{ 1, 3 }	0,2
{ 1, 4 }	0,2
{ 1, 5 }	0,3
{ 2, 3 }	0,1
{ 2, 4 }	0,4
{ 2, 5 }	0,4
{ 3, 4 }	0,2
{ 3, 5 }	0,2
{ 4, 5 }	0,5

Alleen de verzamelingen { 1, 5 }, { 2, 4 }, { 2, 5 } en { 4, 5 } hebben de minimale support van 0,3. Het algoritme zal nu kandidaten genereren met drie items. Een voorwaarde voor een kandidaatverzameling is dat elk van de deelverzamelingen ook de minimale support hebben. Om deze reden zal de verzameling { 1, 2, 5 } niet gegenereerd worden als kandidaat want alhoewel { 1, 5 } en { 2, 5 } de minimale support hebben, heeft de verzameling { 1, 2 } dat niet. Om dezelfde reden valt { 1, 4, 5 } af (wegens { 1, 4 }). De itemverzameling { 2, 4, 5 } voldoet wel want zowel { 2, 4 }, { 2, 5 } als { 4, 5 } hebben een support van minimaal 0,3. De kandidaten met grootte 3 zijn:

	Support
{ 2, 4, 5 }	0,3

Het algoritme eindigt hier aangezien er geen kandidaten met grootte vier gegenereerd kunnen worden.

Elk van de verzamelingen met minimale support die men tijdens het construeren is tegengekomen, kan gebruikt worden om associatieregels te construeren.

Construeren van associatieregels

Een associatieregel op basis van een itemverzameling $S$ heeft de vorm $X \Rightarrow Y$ waarbij $X, Y \subset S$ en $Y = S \ \backslash \ X$ met de betekenis dat als de verzameling $X$ voorkomt dan komt ook de verzameling $Y$ voor.

De verkregen itemverzameling { 1, 5 } geeft bijvoorbeeld de volgende regels:

$\{ 1 \} \Rightarrow \{ 5 \}$ (regel A)

$\{ 5 \} \Rightarrow \{ 1 \}$ (regel B)

Deze associatieregels geven de patronen in de data weer. Er zijn bijvoorbeeld vier transacties waarin item 1 voorkomt en in drie van die transacties komt ook item 5 voor. Regel A klopt dus in 3 van de 4 gevallen. Regel B klopt in 3 van de 7 gevallen. Hier kan men ook een minimale grens instellen waar een regel aan moet voldoen, bijvoorbeeld een regel die minimaal in 50% van de gevallen klopt.

In het voorbeeld van de supermarkt betekent zo'n regel dat als iemand product 1 koopt dan koopt deze (doorgaans) ook product 5. De grote hoeveelheid data die een supermarkt bezit over het koopgedrag van klanten kan nu geanalyseerd worden om patronen te herkennen. Een supermarkt kan daar vervolgens op inspelen, bijvoorbeeld met aanbiedingen.