De documentatie is te vinden in docs/index.html.
Deze is aan te maken via stack haddock --haddock-arguments "-o docs"
Het script kan uitgevoerd worden door stack ghci en vervolgens main uit te voeren.
TODO:
- Functoren implementeren om enkele functies leesbaarder te maken
- Zorgen dat
bestLiftmeerdere producten returned als de lift hetzelfde is. - Zorgen dat
bestLiftiets anders returned wanneer gebruiker gebruiker geen of niet bestaand product invoerd. - Maybe implementeren voor
support,confidenceenliftwanneer de invoer geen (geldig) product is. - Tests schrijven voor
support,confidenceenlift. - Alle mogelijke producten netter printen in
main. - Zorgen dat een foutieve keuze direct het programma stopt.
- While True-loop introduceren zodat gebruiker niet opnieuw de locatie van de dataset hoeft op te geven.
Het Apriori algoritme kan productaanbevelingen leveren voor klanten gebaseerd op historische data. In feite berekent het algoritme voor iedere set van twee producten haar populariteit. Tevens berekent het algoritme hoe veel vaker een product Y samen met een ander product X wordt verkocht dan dat product X met iets anders of niks wordt gekocht. Door te voorspellen welk product Y het beste bij product X past kunnen aanbevelingen worden gedaan.
Het algoritme bestaat uit de volgende drie begrippen:
- Support
- In hoeveel transacties komt product
Xvoor? - In hoeveel transacties komt de vereniging van
XenYvoor?
- In hoeveel transacties komt product
- Confidence
- Wat is de kans dat product
Yook wordt gekocht alsXwordt gekocht?
- Wat is de kans dat product
- Lift
- Hoeveel maal vaker wordt
Ygekocht alsXwordt gekocht? (Ratio)
- Hoeveel maal vaker wordt
Na het uitvoerig testen van het algoritme bleek dat de huidige functies support, confidence en lift snel genoeg zijn voor de eindgebruiker. Het is niet nodig om eerst alle berekeningen te doen en deze op te slaan. Het vermoedelijke wachten op het berekenen van de verschillende matrixen zal niet opwegen tegen de snelheidswinsten die hierdoor later behaald zullen worden.
De oude implementatie van het algoritme maakt gebruik van drie matrixen. Één voor support, één voor confidence en één voor lift. Iedere rij in de matrixen staat voor een uniek product X. Aanbevelingen worden gemaakt voor dit product X. Iedere kolom van de matrixen staat voor een product Y. Het 'beste' product Y moet worden gezocht voor product X. Door de juiste cell op te zoeken in ieder van de drie matrixen kan de support, confidence of lift worden opgezocht van een bepaalde (X → Y)-combinatie.
De volgende tabel bestaat uit vijf producten waarmee drie transacties zijn gedaan. Iedere rij stelt een transactie voor.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 1 | x | x | x | x | x |
| 2 | x | x | x | ||
| 3 | x | x | x |
De support van ieder individueel product is gemakkelijk te berekenen. Dit is het aantal maal dat het individuele product voorkomt in de transacties, gedeeld door het totaal aantal transacties. Voor producten A en B is de support bijvoorbeeld 2/3. Voor product E is de support 3/3.
De support voor iedere combinatie van twee producten is ook gemakkelijk te berekenen. Voor de combinatie (A ⋂ C) is de support 2/3 aangezien deze twee producten -samen- in twee van de drie transacties zijn gekocht. Alle berekeningen kunnen nu worden ingevuld in de support-matrix:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 2/3 | 1/3 | 2/3 | 1/3 | 2/3 |
| B | 2/3 | 2/3 | 1/3 | 2/3 | |
| C | 1 | 1/3 | 1 | ||
| D | 1/3 | 1/3 | |||
| E | 1 |
Aangezien de support van (A ⋂ C) hetzelfde is als de support van (C ⋂ A) hoeft slechts de helft van de matrix te worden berekend. Dit is beter voor de efficiëntie. Om de tweede helft van de support-matrix te berekenen kan de transpositie van de support-matrix worden opgeteld bij de matrix. (De diagonale waardes dienen door het optellen door twee te worden gedeeld maar dit is een programmeeruitwerking waar wij ons nu niet mee bezig houden.)
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 2/3 | 1/3 | 2/3 | 1/3 | 2/3 |
| B | 1/3 | 2/3 | 2/3 | 1/3 | 2/3 |
| C | 2/3 | 2/3 | 1 | 1/3 | 1 |
| D | 1/3 | 1/3 | 1/3 | 1/3 | 1/3 |
| E | 2/3 | 2/3 | 1 | 1/3 | 1 |
De confidence van (X → Y) is anders dan de confidence van (Y → X). Mede hierom dient er een volledig gevulde support-matrix te worden gemaakt bij de vorige stap. De confidence van (X → Y) wordt berekend door de support van (X ⋂ Y) te delen door de support van X.
In ons voorbeeld is de confidence van (C → D) gelijk aan 1/3 aangezien de support van (C ⋂ D) -of (D ⋂ C)- volgens de support-matrix 1/3 is. De support van C is 1 aangezien C in 100% van de transacties voorkomt. 1/3 gedeeld door 1 is vervolgens 1/3 en dus is de confidence van (C → D) gelijk aan 1/3. De confidence van (D → C) is echter 1.
Alle berekende waardes worden vervolgens opgeslagen in een confidence-matrix.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | x | 0.5 | 1 | 0.5 | 1 |
| B | 0.5 | x | 1 | 0.5 | 1 |
| C | 2/3 | 2/3 | x | 1/3 | 1 |
| D | 1 | 1 | 1 | x | 1 |
| E | 2/3 | 2/3 | 1 | 1/3 | x |
Aangezien C en E in iedere transactie voorkomt is de confidence van (X → C) en (X → E) altijd 1. De diagonale lijn gevuld met x-en zegt niks. De confidence van (X → X) zegt immers niks.
De laatste stap van het algoritme is de lift berekenen voor iedere (X → Y). Aangezien in deze formule de confidence wordt gebruikt, geldt ook hier dat (X → Y) niet hetzelfde is als (Y → X). De formule voor de lift van (X → Y) is de confidence van (X → Y) gedeeld door de support van Y.
De lift van (A → D) is bijvoorbeeld 1.5 aangezien de confidence van (A → D) gelijk is aan 0.5 en de support van D gelijk is aan 1/3. 0.5 gedeeld door 1/3 komt uit op 1.5. Ook bij deze stap worden alle berekeningen weer opgeslagen in een matrix.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | x | 0.75 | 1 | 1.5 | 1 |
| B | 0.75 | x | 1 | 1.5 | 1 |
| C | 1 | 1 | x | 1 | 1 |
| D | 1.5 | 1.5 | 1 | x | 1 |
| E | 1 | 1 | 1 | 1 | x |
Hoe groter de dataset, hoe beter de waardes zijn uiteraard.
Door de lift-matrix wordt het mogelijk om voor ieder product X een product Y aan te kunnen bevelen. Door in de
lift-matrix de rij van product X te selecteren en vervolgens het product Y met de grootste lift te pakken
kan de beste aanbeveling worden gedaan.
Stel: een klant heeft product D in zijn of haar online winkelwagentje. Het algoritme zal producten A en B
aanbevelen aangezien deze de hoogste lift hebben met product D.
- http://learnyouahaskell.com/input-and-output
- https://en.wikipedia.org/wiki/Association_rule_learning
- https://stackabuse.com/association-rule-mining-via-apriori-algorithm-in-python/
- https://stackoverflow.com/questions/3275193/whats-the-right-way-to-divide-two-int-values-to-obtain-a-float
- https://stackoverflow.com/questions/24234517/understanding-withfile-with-example
- https://stackoverflow.com/questions/52910840/haskell-finding-maximum-value-in-a-list-of-tuples