Menu

Apriori-algoritme i datamining: implementering med eksempler

  • Vigtigste
  • Andet
  • Apriori-algoritme i datamining: implementering med eksempler

apriori algorithm data mining

Prøv Vores Instrument Til At Fjerne Problemer

Dybdegående tutorial om apriori-algoritme til at finde ud af hyppige varesæt i datamining. Denne vejledning forklarer trinene i apriori og hvordan det fungerer:

Heri Data Mining Tutorial Series , vi kiggede på Beslutningstræ algoritme i vores tidligere tutorial.

Der er adskillige metoder til Data Mining såsom tilknytning, korrelation, klassificering og klyngedannelse.

den bedste mobiltelefon spion software

Denne tutorial fokuserer primært på minedrift ved hjælp af associeringsregler. Ved tilknytningsregler identificerer vi det sæt af elementer eller attributter, der forekommer sammen i en tabel.

Apriori-algoritme

Hvad du vil lære:

Hvad er en varesæt?

Et sæt varer sammen kaldes et artikelsæt. Hvis et artikelsæt har k-artikler, kaldes det et k-artikelsæt. Et varesæt består af to eller flere emner. Et emnesæt, der forekommer ofte, kaldes et hyppigt emnesæt. Således er hyppig varesæt minedrift en data mining teknik til at identificere de emner, der ofte forekommer sammen.

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

Hvad er en hyppig varesæt?

Et sæt varer kaldes hyppigt, hvis det opfylder en minimumsgrænseværdi for støtte og tillid. Support viser transaktioner med varer købt sammen i en enkelt transaktion. Tillid viser transaktioner, hvor varerne købes efter hinanden.

Ved hyppig minesætmetode overvejer vi kun de transaktioner, der opfylder minimumskrav til støtte og tillid til tærskler. Indsigt fra disse minedriftsalgoritmer giver mange fordele, omkostningsbesparelser og forbedret konkurrencefordel.

Der er en afvejet tid til at udvinde data og mængden af ​​data til hyppig minedrift. Den hyppige minedriftsalgoritme er en effektiv algoritme til at udvinde de skjulte mønstre af varesæt inden for kort tid og mindre hukommelsesforbrug.

Frequent Pattern Mining (FPM)

Den hyppige algoritme til minedrift er en af ​​de vigtigste teknikker til datamining til at opdage forhold mellem forskellige elementer i et datasæt. Disse forhold er repræsenteret i form af foreningsregler. Det hjælper med at finde uregelmæssigheder i data.

FPM har mange applikationer inden for dataanalyse, softwarefejl, krydsmarkedsføring, salgskampagneanalyse, analyse af markedskurve osv.

Hyppige varesæt, der er opdaget gennem Apriori, har mange applikationer til dataudvindingsopgaver. Opgaver som at finde interessante mønstre i databasen, finde ud af sekvens og Mining of association-regler er den vigtigste af dem.

Tilknytningsregler gælder for transaktionsdata for supermarkeder, det vil sige for at undersøge kundens adfærd med hensyn til de købte produkter. Foreningsregler beskriver, hvor ofte varerne købes sammen.

Foreningsregler

Association Rule Mining defineres som:

“Lad jeg = {...} være et sæt binære attributter med n kaldet elementer. Lad D = {….} Være et sæt af transaktioner, der kaldes database. Hver transaktion i D har et unikt transaktions-ID og indeholder en delmængde af elementerne i I. En regel defineres som en implikation af form X-> Y hvor X, Y? I og X? Y = ?. Sættet af emnerne X og Y kaldes fortilfælde og følger af henholdsvis reglen. ”

Learning of Association regler bruges til at finde sammenhæng mellem attributter i store databaser. En associeringsregel, A => B, vil have formen 'for et sæt transaktioner, en værdi af varesæt A bestemmer værdierne for varesæt B under den betingelse, hvor minimumsstøtte og tillid er opfyldt'.

Support og tillid kan repræsenteres ved følgende eksempel:

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

Ovenstående erklæring er et eksempel på en associeringsregel. Det betyder, at der er en 2% transaktion, der købte brød og smør sammen, og der er 60% af kunderne, der købte brød såvel som smør.

Support og tillid til varesæt A og B er repræsenteret ved formler:

Formel til støtte og tillid til varesæt A og B

Association regelminedrift består af 2 trin:

  1. Find alle de hyppige varesæt.
  2. Generer tilknytningsregler fra ovenstående hyppige varesæt.

Hvorfor hyppig minesætning med varer

Hyppig varesæt eller mønsterudvinding bruges bredt på grund af dets brede anvendelser i regler for minedriftforeninger, korrelationer og grafmønsterbegrænsning, der er baseret på hyppige mønstre, sekventielle mønstre og mange andre dataudvindingsopgaver.

Apriori algoritme - Hyppige mønsteralgoritmer

Apriori-algoritme var den første algoritme, der blev foreslået til hyppig varesætminedrift. Det blev senere forbedret af R Agarwal og R Srikant og blev kendt som Apriori. Denne algoritme bruger to trin 'join' og 'beskæring' for at reducere søgerummet. Det er en iterativ tilgang til at opdage de hyppigste varesæt.

Apriori siger:

Sandsynligheden for at vare I ikke er hyppig er, hvis:

  • P (I)
  • P (I + A)
  • Hvis et artikelsæt har en værdi, der er mindre end minimumsunderstøttelsen, falder alle dets supersæt også under min understøttelse og kan derfor ignoreres. Denne ejendom kaldes Antimonotone-ejendommen.

De trin, der følges i Apriori-algoritmen for data mining er:

  1. Deltag i trin : Dette trin genererer (K ​​+ 1) emnesæt fra K-emnesæt ved at forbinde hvert emne med sig selv.
  2. Beskær trin : Dette trin scanner antallet af hvert element i databasen. Hvis kandidatemnet ikke opfylder minimumsstøtte, betragtes det som sjældent, og det fjernes således. Dette trin udføres for at reducere størrelsen på kandidatelementer.

Trin i apriori

Apriori-algoritme er en sekvens af trin, der skal følges for at finde de hyppigste varesæt i den givne database. Denne dataminingsteknik følger sammenføjningen, og beskæringen træder iterativt, indtil den hyppigste varesæt er opnået. En minimumstærskel for support er angivet i problemet, eller det antages af brugeren.

# 1) I algoritmens første iteration tages hvert element som en kandidat til 1-itemsets. Algoritmen tæller forekomsterne af hvert element.

#to) Lad der være noget minimumsunderstøttelse, min_sup (f.eks. 2). Sættet med 1 - varesæt, hvis forekomst tilfredsstiller min sup bestemmes. Kun de kandidater, der tæller mere end eller lig med min_sup, føres videre til næste iteration, og de andre beskæres.

# 3) Dernæst opdages 2-artikelsæt hyppige varer med min_sup. Til dette i sammenføjningstrinnet genereres 2-artikelsættet ved at danne en gruppe på 2 ved at kombinere varer med sig selv.

# 4) Kandidaterne med 2 emner beskæres ved hjælp af min-sup tærskelværdi. Nu vil tabellen have 2 –sæt med kun min-sup.

# 5) Den næste iteration vil danne 3 - emnesæt ved hjælp af deltage og beskære trin. Denne iteration følger antimonotonegenskab, hvor delmængderne af 3-artikelsæt, det vil sige de 2-sæt sæt undergrupper for hver gruppe falder i min_sup. Hvis alle delmængder med 2 emner er hyppige, vil supersættet være hyppigt, ellers beskæres det.

# 6) Næste trin følger oprettelse af 4-artikelsæt ved at forbinde 3-artikelsæt med sig selv og beskæring, hvis dets undersæt ikke opfylder min_sup-kriterierne. Algoritmen stoppes, når den hyppigste varesæt opnås.

Apriori trin

(billede kilde )

Eksempel på Apriori:Support tærskel = 50%, tillid = 60%

TABEL 1

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

Løsning:

Support tærskel = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Optælling af hver vare

TABEL-2

VareTælle
I14
I25
I34
I44
I5to

2. Beskær trin: TABEL -2 viser, at I5-elementet ikke opfylder min_sup = 3, så det slettes, kun I1, I2, I3, I4 opfylder min_sup-antallet.

TABEL-3

VareTælle
I14
I25
I34
I44

3. Deltag i trin: Form 2-artikelsæt. Fra TABEL 1 find ud af forekomsterne af 2-artikelsæt.

TABEL-4

VareTælle
I1, I24
I1, I33
I1, I4to
I2, I34
I2, I43
I3, I4to

Fire. Beskær trin: TABEL -4 viser, at varesættet {I1, I4} og {I3, I4} ikke opfylder min_sup, så det slettes.

TABEL-5

VareTælle
I1, I24
I1, I33
I2, I34
I2, I43

5. Deltag og beskær trin: Form 3-artikelsæt. Fra TABEL 1 find forekomster af 3-artikelsæt. Fra TABEL-5 , find ud af de 2-sæt sæt undergrupper, der understøtter min_sup.

Vi kan se for varesæt {I1, I2, I3} undergrupper, {I1, I2}, {I1, I3}, {I2, I3} forekommer i TABEL-5 således er {I1, I2, I3} hyppig.

Vi kan se for varesæt {I1, I2, I4} undersæt, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} er ikke hyppig, da det ikke forekommer i TABEL-5 {I1, I2, I4} er således ikke hyppig, derfor slettes den.

TABEL-6

Vare
I1, I2, I3
I1, I2, I4
I1, I3, I4
I2, I3, I4

Kun {I1, I2, I3} er hyppige .

6. Generer tilknytningsregler: Fra det hyppige varesæt, der blev opdaget ovenfor, kunne foreningen være:

{I1, I2} => {I3}

Tillid = support {I1, I2, I3} / support {I1, I2} = (3/4) * 100 = 75%

{I1, I3} => {I2}

Tillid = support {I1, I2, I3} / support {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

Tillid = support {I1, I2, I3} / support {I2, I3} = (3/4) * 100 = 75%

{I1} => {I2, I3}

Tillid = support {I1, I2, I3} / support {I1} = (3/4) * 100 = 75%

{I2} => {I1, I3}

Tillid = support {I1, I2, I3} / support {I2 = (3/5) * 100 = 60%

{I3} => {I1, I2}

binært søgetræ java-kodeeksempel

Tillid = support {I1, I2, I3} / support {I3} = (3/4) * 100 = 75%

Dette viser, at alle ovenstående tilknytningsregler er stærke, hvis den mindste tillidstærskel er 60%.

Apriori-algoritmen: Pseudokode

C: Kandidatsæt med størrelse k

L: Hyppige varesæt i størrelse k

Psudokode

(billede kilde )

Fordele

  1. Let at forstå algoritme
  2. Deltag og beskær trin er nemme at implementere på store emnesæt i store databaser

Ulemper

  1. Det kræver høj beregning, hvis varesættene er meget store, og minimumsunderstøttelsen holdes meget lav.
  2. Hele databasen skal scannes.

Metoder til at forbedre apriori effektivitet

Der findes mange metoder til forbedring af algoritmens effektivitet.

  1. Hash-baseret teknik: Denne metode bruger en hash-baseret struktur kaldet en hash-tabel til at generere k-itemsets og dens tilsvarende antal. Det bruger en hash-funktion til at generere tabellen.
  2. Transaktionsreduktion: Denne metode reducerer antallet af transaktioner, der scannes i iterationer. Transaktionerne, der ikke indeholder hyppige varer, markeres eller fjernes.
  3. Partitionering: Denne metode kræver kun to databasescanninger for at udvinde de hyppige varesæt. Der står, at for at alle artikelsæt potentielt skal være hyppige i databasen, skal det være hyppigt i mindst en af ​​partitionerne i databasen.
  4. Prøveudtagning: Denne metode vælger en tilfældig prøve S fra database D og søger derefter efter hyppige varesæt i S. Det kan være muligt at miste et globalt hyppigt varesæt. Dette kan reduceres ved at sænke min_sup.
  5. Optælling af dynamisk varesæt: Denne teknik kan tilføje nye kandidatsæt på ethvert markeret startpunkt i databasen under scanning af databasen.

Anvendelser af apriori algoritme

Nogle felter, hvor Apriori bruges:

  1. Inden for uddannelsesområdet: Uddrag af foreningsregler i dataudvinding af optagne studerende gennem egenskaber og specialiteter.
  2. Inden for det medicinske område: For eksempel Analyse af patientens database.
  3. I skovbrug: Analyse af sandsynlighed og intensitet af skovbrand med skovbranddataene.
  4. Apriori bruges af mange virksomheder som Amazon i Anbefalingssystem og af Google for funktionen til automatisk udfyldelse.

Konklusion

Apriori-algoritme er en effektiv algoritme, der kun scanner databasen en gang.

Det reducerer størrelsen på artikelsættene i databasen betydeligt og giver en god præstation. Data-minedrift hjælper således forbrugere og industrier bedre i beslutningsprocessen.

Tjek vores kommende tutorial for at vide mere om den hyppige mønstervækstalgoritme !!

PREV-vejledning | NÆSTE vejledning

Anbefalet læsning

^