A-priorialgoritme

In datamining is het a-priorialgoritme een algoritme om associatieregels te leren uit een database met transacties, zoals gekochte producten in een supermarkt of bezochte 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

bewerken

Neem als voorbeeld de volgende database   met tien transacties 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

bewerken

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

 

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

Voor de bovenstaande database geldt  , want er zijn vier van de tien transacties waarin zowel item 2 als item 5 voorkomt.

Algoritme

bewerken

De invoer van het algoritme bestaat uit een database   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   is een kandidaatverzameling als elk van de deelverzamelingen met lengte   de minimale support hebben.

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

Voorbeeld

bewerken

Het uitvoeren van het a-priorialgoritme op bovenstaande database   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

bewerken

Een associatieregel op basis van een itemverzameling   heeft de vorm   waarbij   en   met de betekenis dat als de verzameling   voorkomt dan komt ook de verzameling   voor.

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

  (regel A)
  (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 de literatuur wordt dit aangeduid als confidence. De conditionele kans van   gegeven dat   is opgetreden:  .

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.