Apriori-algoritmen refererer til algoritmen som brukes til å beregne assosiasjonsreglene mellom objekter. Det betyr hvordan to eller flere objekter er relatert til hverandre. Med andre ord kan vi si at apriori-algoritmen er en assosiasjonsregel som analyserer at personer som kjøpte produkt A også kjøpte produkt B.
Hovedmålet med apriori-algoritmen er å lage assosiasjonsregelen mellom forskjellige objekter. Assosiasjonsregelen beskriver hvordan to eller flere objekter er relatert til hverandre. Apriori-algoritmen kalles også hyppig mønsterutvinning. Vanligvis bruker du Apriori-algoritmen på en database som består av et stort antall transaksjoner. La oss forstå apriori-algoritmen ved hjelp av et eksempel; anta at du går til Big Bazar og kjøper forskjellige produkter. Det hjelper kundene med å kjøpe produktene deres med letthet og øker salgsytelsen til Big Bazar. I denne opplæringen vil vi diskutere apriori-algoritmen med eksempler.
Introduksjon
Vi tar et eksempel for å forstå konseptet bedre. Du må ha lagt merke til at pizzabutikkselgeren lager en kombinasjon av pizza, brus og brødpinner. Han tilbyr også rabatt til sine kunder som kjøper disse kombinasjonene. Tenker du noen gang på hvorfor han gjør det? Han tror kunder som kjøper pizza også kjøper brus og brødpinner. Men ved å lage kombinasjoner gjør han det enkelt for kundene. Samtidig øker han også salgsprestasjonene.
På samme måte går du til Big Bazar, og du vil finne kjeks, chips og sjokolade samlet sammen. Det viser at butikkeieren gjør det komfortabelt for kundene å kjøpe disse produktene på samme sted.
De to ovennevnte eksemplene er de beste eksemplene på foreningens regler i
La oss ta et eksempel for å forstå dette konseptet.
Vi har allerede diskutert ovenfor; du trenger en enorm database som inneholder et stort antall transaksjoner. Anta at du har 4000 kundetransaksjoner i en Big Bazar. Du må beregne Support, Confidence og Lift for to produkter, og du kan si kjeks og sjokolade. Dette er fordi kunder ofte kjøper disse to varene sammen.
Av 4000 transaksjoner inneholder 400 kjeks, mens 600 inneholder sjokolade, og disse 600 transaksjonene inkluderer 200 som inkluderer kjeks og sjokolade. Ved å bruke disse dataene vil vi finne ut støtten, tilliten og løftet.
Brukerstøtte
Support refererer til standard populariteten til ethvert produkt. Du finner støtten som en kvotient av delingen av antall transaksjoner som utgjør det produktet med det totale antallet transaksjoner. Derfor får vi
Support (kjeks) = (transaksjoner relatert til kjeks) / (totalt antall transaksjoner)
= 400/4000 = 10 prosent.
Selvtillit
Tillit refererer til muligheten for at kundene kjøpte både kjeks og sjokolade sammen. Så du må dele antall transaksjoner som omfatter både kjeks og sjokolade med det totale antallet transaksjoner for å få tilliten.
Derfor,
Confidence = (Transaksjoner knyttet til både kjeks og sjokolade) / (Totale transaksjoner som involverer kjeks)
= 200/400
= 50 prosent.
Det betyr at 50 prosent av kundene som kjøpte kjeks kjøpte sjokolade også.
Løfte
Tenk på eksemplet ovenfor; løft refererer til økningen i forholdet mellom salget av sjokolade når du selger kjeks. De matematiske ligningene for løft er gitt nedenfor.
Løft = (Selvtillit (kjeks - sjokolade)/ (Støtte (kjeks)
= 50/10 = 5
Det betyr at sannsynligheten for at folk kjøper både kjeks og sjokolade sammen er fem ganger større enn for å kjøpe kjeksen alene. Hvis løfteverdien er under én, krever det at personene neppe kjøper begge varene sammen. Større verdi, jo bedre er kombinasjonen.
Hvordan fungerer Apriori-algoritmen i datautvinning?
Vi vil forstå denne algoritmen ved hjelp av et eksempel
Tenk på et Big Bazar-scenario der produktsettet er P = {Ris, Pulse, Oil, Milk, Apple}. Databasen består av seks transaksjoner der 1 representerer tilstedeværelsen av produktet og 0 representerer fraværet av produktet.
| Transaksjons-ID | Ris | Puls | Olje melk | eple | |
|---|---|---|---|---|---|
| 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 gjør de gitte forutsetningene
- Alle undersett av et hyppig elementsett må være hyppige.
- Undersettene til et sjeldent elementsett må være sjeldne.
- Fiks et terskelstøttenivå. I vårt tilfelle har vi fastsatt det til 50 prosent.
Trinn 1
Lag en frekvenstabell over alle produktene som vises i alle transaksjonene. Forkort nå frekvenstabellen for å legge til bare de produktene med et terskelstøttenivå på over 50 prosent. Vi finner den gitte frekvenstabellen.
| Produkt | Frekvens (antall transaksjoner) |
|---|---|
| Ris (R) | 4 |
| Puls (P) | 5 |
| Olje (O) | 4 |
| Melk (M) | 4 |
Tabellen ovenfor indikerte produktene som ofte ble kjøpt av kundene.
Steg 2
Lag produktpar som RP, RO, RM, PO, PM, OM. Du får den gitte frekvenstabellen.
| Varesett | Frekvens (antall transaksjoner) |
|---|---|
| RP | 4 |
| RO | 3 |
| RM | 2 |
| ETTER | 4 |
| PM | 3 |
| OM | 2 |
Trinn 3
Implementere den samme terskelstøtten på 50 prosent og vurdere produktene som er mer enn 50 prosent. I vårt tilfelle er det mer enn 3
Dermed får vi RP, RO, PO og PM
tilfeldig i c
Trinn 4
Se nå etter et sett med tre produkter som kundene kjøper sammen. Vi får den gitte kombinasjonen.
- RP og RO gir RPO
- PO og PM gir POM
Trinn 5
Regn ut frekvensen til de to elementsettene, og du vil få opp den gitte frekvenstabellen.
| Varesett | Frekvens (antall transaksjoner) |
|---|---|
| RPO | 4 |
| POM | 3 |
Hvis du implementerer terskelantakelsen, kan du finne ut at kundenes sett med tre produkter er RPO.
Vi har vurdert et enkelt eksempel for å diskutere apriori-algoritmen i datautvinning. I virkeligheten finner du tusenvis av slike kombinasjoner.
Hvordan forbedre effektiviteten til Apriori-algoritmen?
Det er forskjellige metoder som brukes for effektiviteten til Apriori-algoritmen
Hash-basert telling av varesett
I hash-basert telling av varesett må du ekskludere k-elementsettet hvis ekvivalente antall hashingspann er minst enn terskelen er et sjeldent varesett.
Transaksjonsreduksjon
Ved transaksjonsreduksjon blir en transaksjon som ikke involverer noen hyppige X-elementsett ikke verdifull i påfølgende skanninger.
Apriori-algoritme i datautvinning
Vi har allerede diskutert et eksempel på apriori-algoritmen knyttet til den hyppige varesettgenereringen. Apriori-algoritmen har mange applikasjoner innen data mining.
De primære kravene for å finne assosiasjonsreglene i data mining er gitt nedenfor.
Bruk Brute Force
Analyser alle reglene og finn støtte- og tillitsnivåene for den enkelte regelen. Etterpå eliminerer du verdiene som er lavere enn terskelstøtte- og konfidensnivåene.
To-trinns tilnærminger
To-trinns tilnærmingen er et bedre alternativ for å finne foreningens regler enn Brute Force-metoden.
Trinn 1
I denne artikkelen har vi allerede diskutert hvordan du oppretter frekvenstabellen og beregner varesett som har en større støtteverdi enn terskelstøtten.
Steg 2
For å lage assosiasjonsregler, må du bruke en binær partisjon av de hyppige elementsettene. Du må velge de som har høyest konfidensnivå.
I eksemplet ovenfor kan du se at RPO-kombinasjonen var det hyppige varesettet. Nå finner vi ut alle reglene ved å bruke RPO.
RP-O, RO-P, PO-R, O-RP, P-RO, R-PO
Du kan se at det er seks forskjellige kombinasjoner. Derfor, hvis du har n elementer, vil det være 2n- 2 kandidatforeningsregler.
Fordeler med Apriori Algorithm
- Den brukes til å beregne store varesett.
- Enkel å forstå og bruke.
Ulemper med Apriori-algoritmer
- Apriori-algoritmen er en kostbar metode for å finne støtte siden beregningen må gå gjennom hele databasen.
- Noen ganger trenger du et stort antall kandidatregler, så det blir beregningsmessig dyrere.