Meny

Apriori-algoritme i datautvinning: implementering med eksempler

  • Hoved
  • Annen
  • Apriori-algoritme i datautvinning: implementering med eksempler

apriori algorithm data mining

Prøv Instrumentet Vårt For Å Eliminere Problemer

Dybdegående opplæring om apriori-algoritme for å finne ut hyppige varesett i datamining. Denne opplæringen forklarer trinnene i apriori og hvordan det fungerer:

I dette Data Mining Tutorial Series , vi så på Beslutningstresalgoritme i vår forrige opplæring.

Det er flere metoder for Data Mining som tilknytning, korrelasjon, klassifisering og klynging.

programvare for å laste ned videoer fra nettsteder

Denne opplæringen fokuserer primært på gruvedrift ved hjelp av assosieringsregler. Ved tilknytningsregler identifiserer vi settet med elementer eller attributter som forekommer sammen i en tabell.

Apriori-algoritme

Hva du vil lære:

Hva er et varesett?

Et sett med elementer sammen kalles et varesett. Hvis noen artikelsett har k-elementer, kalles det et k-varesett. Et varesett består av to eller flere gjenstander. Et varesett som forekommer ofte kalles et hyppig varesett. Dermed er hyppig vareutvinning en data mining-teknikk for å identifisere elementene som ofte forekommer sammen.

For eksempel , Brød og smør, Laptop- og antivirusprogramvare osv.

Hva er et hyppig varesett?

Et sett med varer kalles hyppig hvis det tilfredsstiller en minimumsverdi for støtte og tillit. Support viser transaksjoner med varer kjøpt sammen i en enkelt transaksjon. Tillit viser transaksjoner hvor varene er kjøpt etter hverandre.

For hyppig vareminnesmetode vurderer vi bare de transaksjonene som oppfyller minimumskrav til støtte og tillit. Innsikt fra disse gruvedriftalgoritmene gir mange fordeler, kostnadsbesparelser og forbedret konkurransefortrinn.

Det tar en kompromisstid å bryte data og datamengden for hyppig gruvedrift. Den hyppige gruvedriftsalgoritmen er en effektiv algoritme for å utvinne de skjulte mønstrene til varesett innen kort tid og mindre minneforbruk.

Frequent Pattern Mining (FPM)

Den hyppige algoritmen for mønsterutvinning er en av de viktigste teknikkene for datautvinning for å oppdage forhold mellom forskjellige elementer i et datasett. Disse forholdene er representert i form av foreningsregler. Det hjelper å finne uregelmessigheter i data.

FPM har mange applikasjoner innen dataanalyse, programvarefeil, kryssmarkedsføring, salgskampanjeanalyse, analyse av markedskurven, etc.

Hyppige varesett oppdaget gjennom Apriori har mange applikasjoner i data mining-oppgaver. Oppgaver som å finne interessante mønstre i databasen, finne ut sekvens og utvinning av tilknytningsregler er den viktigste av dem.

Tilknytningsregler gjelder for transaksjonsdata for supermarkeder, det vil si for å undersøke kundens atferd med hensyn til de kjøpte produktene. Foreningsregler beskriver hvor ofte varene blir kjøpt sammen.

Foreningsregler

Association Rule Mining er definert som:

“La jeg = {...} være et sett med‘ n ’binære attributter kalt elementer. La D = {….} Være et sett med transaksjoner som kalles database. Hver transaksjon i D har en unik transaksjons-ID og inneholder en delmengde av elementene i I. En regel er definert som en implikasjon av form X-> Y der X, Y? Jeg og X? Y = ?. Settet med gjenstander X og Y kalles fortilfælde og følger av regelen. '

Learning of Association-regler brukes til å finne sammenhenger mellom attributter i store databaser. En assosieringsregel, A => B, vil ha formen 'for et sett med transaksjoner, en verdi av varesett A bestemmer verdiene til varesett B under den betingelse at minimumsstøtte og tillit er oppfylt'.

Støtte og tillit kan representeres av følgende eksempel:

Bread=> butter (support=2%, confidence-60%)

Ovennevnte uttalelse er et eksempel på en assosieringsregel. Dette betyr at det er en 2% transaksjon som kjøpte brød og smør sammen, og det er 60% av kundene som kjøpte brød i tillegg til smør.

Støtte og tillit for varesett A og B er representert med formler:

Formel for støtte og tillit for varesett A og B

Association mining mining består av to trinn:

  1. Finn alle de hyppige varesettene.
  2. Generer tilknytningsregler fra ovennevnte hyppige varesett.

Hvorfor ofte gruvedrift av varesett?

Hyppig varesett eller mønsterutvinning brukes i stor grad på grunn av dets brede anvendelser i regler for gruvedrift, korrelasjoner og grafmønsterbegrensninger som er basert på hyppige mønstre, sekvensielle mønstre og mange andre datautvinning.

Apriori-algoritme - Hyppige mønsteralgoritmer

Apriori-algoritmen var den første algoritmen som ble foreslått for hyppig utvinning av varesett. Den ble senere forbedret av R Agarwal og R Srikant og ble kjent som Apriori. Denne algoritmen bruker to trinn 'bli med' og 'beskjære' for å redusere søkeområdet. Det er en iterativ tilnærming å oppdage de hyppigste varesettene.

Apriori sier:

Sannsynligheten for at vare I ikke er hyppig er hvis:

  • P (I)
  • P (I + A)
  • Hvis et varesett sett har en verdi som er mindre enn minimumsstøtte, vil alle supersettene også falle under min støtte, og kan dermed ignoreres. Denne eiendommen kalles Antimonotone-eiendommen.

Trinnene som følges i Apriori-algoritmen for data mining er:

  1. Bli med Step : Dette trinnet genererer (K ​​+ 1) varesett fra K-varesett ved å bli med hvert element med seg selv.
  2. Beskjær trinn : Dette trinnet skanner antallet av hvert element i databasen. Hvis kandidatelementet ikke oppfyller minimumsstøtte, blir det sett på som sjeldent og dermed fjernet. Dette trinnet utføres for å redusere størrelsen på kandidatelementene.

Steps In Apriori

Apriori-algoritmen er en sekvens av trinn som skal følges for å finne de hyppigste varesettene i den gitte databasen. Denne data mining teknikken følger sammenføyningen og beskjæringen går trinnvis til det hyppigste varesettet er oppnådd. En minimumsterskel for støtte er gitt i problemet, eller det antas av brukeren.

#1) I den første iterasjonen av algoritmen blir hvert element tatt som en kandidat med 1 vare. Algoritmen vil telle forekomsten av hvert element.

#to) La det være noe minimumsstøtte, min_sup (f.eks. 2). Settet med 1 - varesett hvis forekomst tilfredsstiller min sup bestemmes. Bare de kandidatene som teller mer enn eller lik min_sup, blir ført frem til neste iterasjon, og de andre beskjæres.

# 3) Deretter oppdages 2-itemsett hyppige varer med min_sup. For dette i sammenføyningstrinnet genereres 2-artikelsettet ved å danne en gruppe på 2 ved å kombinere elementer med seg selv.

# 4) Kandidatene på 2 poster blir beskjært ved hjelp av min-sup terskelverdi. Nå vil tabellen ha to - sett med bare min-sup.

# 5) Den neste iterasjonen vil utgjøre 3 - emnesett ved hjelp av sammenføyning og beskjæringstrinn. Denne iterasjonen vil følge antimonotonegenskapen der delmengdene av 3-varesett, det vil si de 2 –emsettmengdene for hver gruppe faller i min_sup. Hvis alle delmengder med 2 elementer er hyppige, vil supersettet være hyppig ellers beskjæres det.

# 6) Neste trinn vil følge å lage 4-varesett ved å bli med 3-varesett med seg selv og beskjæring hvis delmengden ikke oppfyller min_sup-kriteriene. Algoritmen stoppes når det hyppigste varesettet oppnås.

Apriori trinn

(bilde kilde )

Eksempel på Apriori:Støtteterskel = 50%, tillit = 60%

TABELL-1

TransaksjonListe over varer
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, I2, I3, I4

Løsning:

Støtteterskel = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Antall av hvert element

TABELL-2

PunktTelle
I14
I25
I34
I44
I5to

to. Beskjær trinn: TABELL -2 viser at I5-elementet ikke oppfyller min_sup = 3, dermed blir det slettet, bare I1, I2, I3, I4 oppfyller min_sup-antall.

TABELL-3

PunktTelle
I14
I25
I34
I44

3. Bli med i trinn: Skjema 2-artikelsett. Fra TABELL-1 finn ut forekomster av 2-artikelsett.

TABELL-4

PunktTelle
I1, I24
I1, I33
I1, I4to
I2, I34
I2, I43
I3, I4to

Fire. Beskjær trinn: TABELL -4 viser at varesettet {I1, I4} og {I3, I4} ikke oppfyller min_sup, og dermed blir det slettet.

TABELL-5

PunktTelle
I1, I24
I1, I33
I2, I34
I2, I43

5. Bli med og beskjær trinn: Skjema 3-artikelsett. Fra TABELL- 1 finn ut forekomster av 3-artikelsett. Fra TABELL-5 , finn ut delmengdene med 2 varesett som støtter min_sup.

Vi kan se for varesett {I1, I2, I3} delsett, {I1, I2}, {I1, I3}, {I2, I3} forekommer i TABELL-5 dermed er {I1, I2, I3} hyppig.

Vi kan se for varesett {I1, I2, I4} delsett, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} er ikke hyppig, da det ikke forekommer i TABELL-5 dermed er {I1, I2, I4} ikke hyppig, derfor blir den slettet.

TABELL-6

Punkt
I1, I2, I3
I1, I2, I4
I1, I3, I4
I2, I3, I4

Bare {I1, I2, I3} er hyppige .

6. Generer tilknytningsregler: Fra det hyppige varesettet som ble oppdaget ovenfor, kunne foreningen være:

{I1, I2} => {I3}

Tillit = støtte {I1, I2, I3} / støtte {I1, I2} = (3/4) * 100 = 75%

{I1, I3} => {I2}

Tillit = støtte {I1, I2, I3} / støtte {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

Tillit = støtte {I1, I2, I3} / støtte {I2, I3} = (3/4) * 100 = 75%

{I1} => {I2, I3}

Tillit = støtte {I1, I2, I3} / støtte {I1} = (3/4) * 100 = 75%

{I2} => {I1, I3}

c vs c ++ forskjeller

Tillit = støtte {I1, I2, I3} / støtte {I2 = (3/5) * 100 = 60%

{I3} => {I1, I2}

Tillit = støtte {I1, I2, I3} / støtte {I3} = (3/4) * 100 = 75%

Dette viser at alle ovennevnte tilknytningsregler er sterke hvis minimumsgrensen for tillit er 60%.

Apriori-algoritmen: Pseudokode

C: Kandidatsett sett med størrelse k

L: Hyppige varesett i størrelse k

Psudokode

(bilde kilde )

Fordeler

  1. Enkel å forstå algoritme
  2. Bli med og beskjære trinn er enkle å implementere på store varesett i store databaser

Ulemper

  1. Det krever høy beregning hvis varesettene er veldig store og minimumsstøtten holdes veldig lav.
  2. Hele databasen må skannes.

Metoder for å forbedre apriorieffektivitet

Mange metoder er tilgjengelige for å forbedre effektiviteten til algoritmen.

  1. Hash-basert teknikk: Denne metoden bruker en hash-basert struktur kalt en hash-tabell for å generere k-itemsets og dens tilsvarende antall. Den bruker en hash-funksjon for å generere tabellen.
  2. Transaksjonsreduksjon: Denne metoden reduserer antall transaksjoner som skannes i iterasjoner. Transaksjonene som ikke inneholder hyppige varer er merket eller fjernet.
  3. Oppdeling: Denne metoden krever bare to databasesøk for å utvinne de hyppige varesettene. Det står at for alle artikelsett å være potensielt hyppige i databasen, bør det være hyppig i minst en av partisjonene i databasen.
  4. Prøvetaking: Denne metoden plukker et tilfeldig utvalg S fra database D og søker deretter etter hyppige varesett i S. Det kan være mulig å miste et globalt hyppig varesett. Dette kan reduseres ved å senke min_sup.
  5. Telling av dynamisk varesett: Denne teknikken kan legge til nye kandidatelementer ved hvilket som helst markert startpunkt i databasen under skanningen av databasen.

Anvendelser av apriori-algoritme

Noen felt der Apriori brukes:

  1. I utdanningsfeltet: Utvinne foreningsregler i datautvinning av opptatte studenter gjennom egenskaper og spesialiteter.
  2. I det medisinske feltet: For eksempel analyse av pasientens database.
  3. I skogbruk: Analyse av sannsynlighet og intensitet av skogbrann med skogbranndataene.
  4. Apriori brukes av mange selskaper som Amazon i Anbefalingssystem og av Google for funksjonen for automatisk fullføring.

Konklusjon

Apriori-algoritme er en effektiv algoritme som bare skanner databasen en gang.

Det reduserer størrelsen på artikelsettene i databasen, noe som gir god ytelse. Dermed hjelper data mining forbrukere og bransjer bedre i beslutningsprosessen.

Ta en titt på vår kommende veiledning for å vite mer om Algoritmen for hyppig mønstervekst !!

PREV Opplæring | NESTE veiledning

Anbefalt lesing

^