Apriori-algoritm hänvisar till algoritmen som används för att beräkna associationsreglerna mellan objekt. Det betyder hur två eller flera objekt är relaterade till varandra. Med andra ord kan vi säga att apriori-algoritmen är en associationsregel som analyserar att personer som köpt produkt A också köpt produkt B.
Det primära syftet med apriori-algoritmen är att skapa associationsregeln mellan olika objekt. Associationsregeln beskriver hur två eller flera objekt är relaterade till varandra. Apriori-algoritmen kallas också frekvent mönsterutvinning. I allmänhet använder du Apriori-algoritmen på en databas som består av ett stort antal transaktioner. Låt oss förstå apriori-algoritmen med hjälp av ett exempel; anta att du går till Big Bazar och köper olika produkter. Det hjälper kunderna att köpa sina produkter med lätthet och ökar försäljningsresultatet för Big Bazar. I den här handledningen kommer vi att diskutera apriori-algoritmen med exempel.
Introduktion
Vi tar ett exempel för att förstå konceptet bättre. Du måste ha märkt att pizzabutikssäljaren gör en kombination av pizza, läsk och brödpinnar. Han erbjuder också rabatt till sina kunder som köper dessa kombinationer. Tänker du någonsin varför han gör så? Han tycker att kunder som köper pizza också köper läsk och brödpinnar. Men genom att göra kombos gör han det enkelt för kunderna. Samtidigt ökar han också sin försäljningsprestation.
På samma sätt går du till Big Bazar och du kommer att hitta kex, chips och choklad tillsammans. Det visar att butiksinnehavaren gör det bekvämt för kunderna att köpa dessa produkter på samma ställe.
Ovanstående två exempel är de bästa exemplen på föreningsregler i
Låt oss ta ett exempel för att förstå detta koncept.
Vi har redan diskuterat ovan; du behöver en enorm databas som innehåller ett stort antal transaktioner. Anta att du har 4000 kundtransaktioner i en Big Bazar. Du måste beräkna Support, Confidence och Lift för två produkter, och du kan säga kex och choklad. Detta beror på att kunder ofta köper dessa två artiklar tillsammans.
Av 4000 transaktioner innehåller 400 kex, medan 600 innehåller choklad, och dessa 600 transaktioner inkluderar 200 som inkluderar kex och choklad. Med hjälp av denna information kommer vi att ta reda på stödet, förtroendet och lyftet.
Stöd
Support hänvisar till standardpopulariteten för alla produkter. Du hittar stödet som en kvot för divisionen av antalet transaktioner som utgör den produkten med det totala antalet transaktioner. Därför får vi
Support (Kex) = (Transaktioner relaterade till kex) / (Totala transaktioner)
= 400/4000 = 10 procent.
Förtroende
Förtroende syftar på möjligheten att kunderna köpt både kex och choklad tillsammans. Så du måste dividera antalet transaktioner som omfattar både kex och choklad med det totala antalet transaktioner för att få förtroendet.
Därav,
Förtroende = (Transaktioner som rör både kex och choklad) / (Totala transaktioner som involverar kex)
= 200/400
= 50 procent.
Det betyder att 50 procent av kunderna som köpte kex köpte choklad också.
Hiss
Betrakta exemplet ovan; lyft hänvisar till ökningen av andelen försäljning av choklad när du säljer kex. De matematiska ekvationerna för lyftet ges nedan.
Lyft = (Förtroende (Kex - choklad)/ (Support (Kex)
= 50/10 = 5
Det betyder att sannolikheten för att folk köper både kex och choklad tillsammans är fem gånger större än att köpa kexen ensam. Om lyftvärdet är under ett, kräver det att personerna sannolikt inte köper båda föremålen tillsammans. Större värde, desto bättre är kombinationen.
Hur fungerar Apriori-algoritmen i Data Mining?
Vi kommer att förstå denna algoritm med hjälp av ett exempel
Tänk på ett Big Bazar-scenario där produktuppsättningen är P = {Ris, Pulse, Oil, Milk, Apple}. Databasen omfattar sex transaktioner där 1 representerar närvaron av produkten och 0 representerar frånvaron av produkten.
| Transaktions ID | Ris | Puls | Olja Mjölk | Äpple | |
|---|---|---|---|---|---|
| t1 | 1 | 1 | 1 | 0 | 0 |
| t2 | 0 | 1 | 1 | 1 | 0 |
| t3 | 0 | 0 | 0 | 1 | 1 |
| t4 | 1 | 1 | 0 | 1 | 0 |
| t5 | 1 | 1 | 1 | 0 | 1 |
| t6 | 1 | 1 | 1 | 1 | 1 |
Apriori-algoritmen gör de givna antagandena
- Alla delmängder av en frekvent artikeluppsättning måste vara frekventa.
- Delmängderna av en sällsynt artikeluppsättning måste vara sällsynta.
- Fixa en tröskelstödsnivå. I vårt fall har vi fixat det till 50 procent.
Steg 1
Gör en frekvenstabell över alla produkter som förekommer i alla transaktioner. Förkorta nu frekvenstabellen för att bara lägga till de produkter med en tröskelstödnivå på över 50 procent. Vi hittar den givna frekvenstabellen.
| Produkt | Frekvens (antal transaktioner) |
|---|---|
| Ris (R) | 4 |
| Puls(P) | 5 |
| Olja(O) | 4 |
| Mjölk (M) | 4 |
Tabellen ovan angav de produkter som ofta köps av kunderna.
Steg 2
Skapa par av produkter som RP, RO, RM, PO, PM, OM. Du kommer att få den givna frekvenstabellen.
| Artikeluppsättning | Frekvens (antal transaktioner) |
|---|---|
| RP | 4 |
| RO | 3 |
| RM | 2 |
| EFTER | 4 |
| PM | 3 |
| HANDLA OM | 2 |
Steg 3
Implementera samma tröskelstöd på 50 procent och överväga de produkter som är mer än 50 procent. I vårt fall är det fler än 3
Således får vi RP, RO, PO och PM
hoppa över listan
Steg 4
Leta nu efter en uppsättning med tre produkter som kunderna köper tillsammans. Vi får den givna kombinationen.
- RP och RO ger RPO
- PO och PM ger POM
Steg 5
Beräkna frekvensen för de två postuppsättningarna, så får du den givna frekvenstabellen.
| Artikeluppsättning | Frekvens (antal transaktioner) |
|---|---|
| RPO | 4 |
| POM | 3 |
Om du implementerar tröskelantagandet kan du räkna ut att kundernas uppsättning av tre produkter är RPO.
Vi har övervägt ett enkelt exempel för att diskutera apriori-algoritmen i datautvinning. I verkligheten hittar du tusentals sådana kombinationer.
Hur kan man förbättra effektiviteten hos Apriori-algoritmen?
Det finns olika metoder som används för effektiviteten av Apriori-algoritmen
Hash-baserad räkning av artiklar
I hash-baserad artikeluppsättningsräkning måste du utesluta k-varuuppsättningen vars ekvivalenta antal hash-bucket är minst än tröskeln är en sällsynt artikeluppsättning.
Transaktionsminskning
Vid transaktionsreduktion blir en transaktion som inte involverar några frekventa X-poster inte värdefull i efterföljande skanningar.
Apriori-algoritm för datautvinning
Vi har redan diskuterat ett exempel på apriori-algoritmen relaterad till den frekventa artikeluppsättningsgenereringen. Apriori-algoritmen har många tillämpningar inom datautvinning.
De primära kraven för att hitta föreningsreglerna inom datautvinning anges nedan.
Använd Brute Force
Analysera alla regler och hitta stöd och förtroendenivåer för den individuella regeln. Ta sedan bort de värden som är lägre än tröskelvärdena för stöd och konfidensnivåer.
Tvåstegsansatserna
Tvåstegsmetoden är ett bättre alternativ för att hitta föreningens regler än Brute Force-metoden.
Steg 1
I den här artikeln har vi redan diskuterat hur man skapar frekvenstabellen och beräknar objektuppsättningar som har ett större stödvärde än tröskelstödet.
Steg 2
För att skapa associationsregler måste du använda en binär partition av de frekventa objektuppsättningarna. Du måste välja de som har de högsta konfidensnivåerna.
I exemplet ovan kan du se att RPO-kombinationen var den vanliga artikeluppsättningen. Nu tar vi reda på alla regler med RPO.
RP-O, RO-P, PO-R, O-RP, P-RO, R-PO
Du kan se att det finns sex olika kombinationer. Därför, om du har n element, kommer det att finnas 2n- 2 kandidatföreningsregler.
Fördelar med Apriori Algorithm
- Den används för att beräkna stora artiklar.
- Enkel att förstå och tillämpa.
Nackdelar med Apriori-algoritmer
- Apriori-algoritmen är en dyr metod för att hitta stöd eftersom beräkningen måste gå igenom hela databasen.
- Ibland behöver du ett stort antal kandidatregler, så det blir beräkningsmässigt dyrare.