Frequent Pattern (FP) Growth Algorithm In Data Mining

frequent pattern growth algorithm data mining

Detaljert veiledning om hyppig mønstervekstalgoritme som representerer databasen i form av et FP-tre. Inkluderer FP-vekst mot apriori-sammenligning:

Apriori algoritme ble forklart i detalj i vår forrige opplæring. I denne opplæringen vil vi lære om hyppig mønstervekst - FP-vekst er en metode for gruvedrift av hyppige varesett.

.net intervju spørsmål og svar for erfarne

Som vi alle vet, er Apriori en algoritme for hyppig mønsterdrift som fokuserer på å generere varesett og oppdage det hyppigste varesettet. Det reduserer størrelsen på varesettet i databasen sterkt, men Apriori har også sine egne mangler.

Les gjennom vår Hele Data Mining Training Series for fullstendig kunnskap om konseptet.

Hva du vil lære:

• Mangler i apriori-algoritmen
• Hyppig mønstervekstalgoritme
• FP Tree
• Hyppige trinn for mønsteralgoritme
• Eksempel på FP-vekstalgoritme
• Fordeler med FP-vekstalgoritme
• Ulemper ved FP-vekstalgoritme
• FP Vekst vs Apriori
• SKINNE
• Konklusjon
• Anbefalt lesing

Mangler i apriori-algoritmen

1. Å bruke Apriori trenger en generasjon av kandidatartikler. Disse varesettene kan ha stort antall hvis varesettet i databasen er stort.
2. Apriori trenger flere skanninger av databasen for å kontrollere støtten til hvert genererte artikelsett, og dette fører til høye kostnader.

Disse manglene kan overvinnes ved hjelp av FP-vekstalgoritmen.

Hyppig mønstervekstalgoritme

Denne algoritmen er en forbedring av Apriori-metoden. Et hyppig mønster genereres uten behov for kandidatgenerering. FP-vekstalgoritme representerer databasen i form av et tre som kalles et hyppig mønstertre eller FP-tre.

Denne trestrukturen vil opprettholde sammenhengen mellom varesettene. Databasen er fragmentert ved hjelp av ett hyppig element. Denne fragmenterte delen kalles 'mønsterfragment'. Artikelsettene til disse fragmenterte mønstrene blir analysert. Dermed reduseres søket etter hyppige varesett relativt sett med denne metoden.

FP Tree

Frequent Pattern Tree er en trelignende struktur som er laget med de første elementene i databasen. Formålet med FP-treet er å bryte det hyppigste mønsteret. Hver node i FP-treet representerer et element i varesettet.

Rotnoden representerer null mens de nedre nodene representerer varesettene. Assosiasjonen av nodene med de nedre nodene som er varesettene med de andre varesettene opprettholdes mens du danner treet.

Hyppige trinn for mønsteralgoritme

Metoden for hyppig mønstervekst lar oss finne det hyppige mønsteret uten kandidatgenerering.

La oss se trinnene som følges for å utvinne det hyppige mønsteret ved hjelp av hyppig algoritme for mønstervekst:

#1) Det første trinnet er å skanne databasen for å finne forekomsten av varesettene i databasen. Dette trinnet er det samme som det første trinnet til Apriori. Antallet 1-artikelsett i databasen kalles supporttelling eller frekvens på 1-artikelsett.

#to) Det andre trinnet er å konstruere FP-treet. For dette, skape roten til treet. Roten er representert med null.

# 3) Neste trinn er å skanne databasen igjen og undersøke transaksjonene. Undersøk den første transaksjonen, og finn ut varesettet i den. Varesettet med maksimalt antall er tatt øverst, neste varesett med lavere antall og så videre. Det betyr at grenen av treet er konstruert med transaksjonselementer i fallende rekkefølge.

# 4) Neste transaksjon i databasen undersøkes. Varesettene er ordnet i synkende rekkefølge. Hvis noen varesett av denne transaksjonen allerede er tilstede i en annen gren (for eksempel i den første transaksjonen), vil denne transaksjonsgrenen dele et felles prefiks til roten.

Dette betyr at det felles varesettet er koblet til den nye noden til et annet varesett i denne transaksjonen.

# 5) Antallet av varesettet økes også når det skjer i transaksjonene. Både den felles noden og den nye noden teller med 1 etter hvert som de opprettes og kobles i henhold til transaksjoner.

# 6) Det neste trinnet er å utvinne det opprettede FP-treet. For dette blir den laveste noden undersøkt først sammen med koblingene til de laveste nodene. Den laveste noden representerer lengden på frekvensmønsteret 1. Fra dette, kryss banen i FP-treet. Denne stien eller stiene kalles en betinget mønsterbase.

Betinget mønsterbase er en underdatabase som består av prefiksbaner i FP-treet som forekommer med den laveste noden (suffikset).

# 7) Konstruer et betinget FP-tre, som er dannet av et antall varesett i banen. Varesettene som oppfyller terskelstøtten, blir vurdert i det betingede FP-treet.

# 8) Hyppige mønstre genereres fra det betingede FP-treet.

Eksempel på FP-vekstalgoritme

Støtteterskel = 50%, tillit = 60%

Tabell 1

Løsning:

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

programmer som skjuler IP-adressen din

1. Tell av hvert element

Tabell 2

2. Sorter varesettet i synkende rekkefølge.

Tabell 3

3. Bygg FP Tree

1. Vurderer rotnoden null.
2. Den første skanningen av Transaksjon T1: I1, I2, I3 inneholder tre elementer {I1: 1}, {I2: 1}, {I3: 1}, hvor I2 er knyttet som et barn til rot, I1 er knyttet til I2 og I3 er knyttet til I1.
3. T2: I2, I3, I4 inneholder I2, I3 og I4, hvor I2 er knyttet til rot, I3 er knyttet til I2 og I4 er knyttet til I3. Men denne grenen vil dele I2-noden så vanlig som den allerede er brukt i T1.
4. Øk tellingen av I2 med 1 og I3 er knyttet som barn til I2, I4 er knyttet som barn til I3. Tellingen er {I2: 2}, {I3: 1}, {I4: 1}.
5. T3: I4, I5. Tilsvarende er en ny gren med I5 knyttet til I4 når et barn opprettes.
6. T4: I1, I2, I4. Sekvensen vil være I2, I1 og I4. I2 er allerede knyttet til rotnoden, derav vil den økes med 1. Tilsvarende vil I1 økes med 1, da den allerede er knyttet til I2 i T1, og dermed {I2: 3}, {I1: 2}, {I4: 1}.
7. T5: I1, I2, I3, I5. Sekvensen vil være I2, I1, I3 og I5. Dermed {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
8. T6: I1, I2, I3, I4. Sekvensen vil være I2, I1, I3 og I4. Dermed {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

4. Gruvedrift av FP-tre er oppsummert nedenfor:

1. Det laveste nodeelementet I5 blir ikke ansett, da det ikke har min støtteopptelling, derfor blir det slettet.
2. Den neste nedre noden er I4. I4 forekommer i to grener, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Derfor vurderer I4 som suffiks prefiksbanene vil være {I2, I1, I3: 1}, {I2, I3: 1}. Dette danner den betingede mønsterbasen.
3. Den betingede mønsterbasen betraktes som en transaksjonsdatabase, et FP-tre konstrueres. Dette vil inneholde {I2: 2, I3: 2}, I1 blir ikke ansett da den ikke oppfyller antall støttetall.
4. Denne banen vil generere alle kombinasjoner av hyppige mønstre: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
5. For I3 vil prefiksbanen være: {I2, I1: 3}, {I2: 1}, dette vil generere et FP-tre med to noder: {I2: 4, I1: 3} og hyppige mønstre genereres: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
6. For I1 vil prefiksbanen være: {I2: 4} dette vil generere et enkelt node FP-tre: {I2: 4} og hyppige mønstre genereres: {I2, I1: 4}.

Diagrammet nedenfor viser det betingede FP-treet assosiert med den betingede noden I3.

Fordeler med FP-vekstalgoritme

1. Denne algoritmen trenger å skanne databasen bare to ganger sammenlignet med Apriori som skanner transaksjonene for hver iterasjon.
2. Sammenkoblingen av elementer gjøres ikke i denne algoritmen, og dette gjør det raskere.
3. Databasen lagres i en kompakt versjon i minnet.
4. Den er effektiv og skalerbar for gruvedrift både lange og korte hyppige mønstre.

Ulemper ved FP-vekstalgoritme

1. FP Tree er mer tungvint og vanskelig å bygge enn Apriori.
2. Det kan være dyrt.
3. Når databasen er stor, kan det hende at algoritmen ikke passer inn i det delte minnet.

FP Vekst vs Apriori

SKINNE

Ovennevnte metode, Apriori og FP-vekst, utvider ofte hyppige varesett ved hjelp av horisontalt dataformat. ECLAT er en metode for gruvedrift av hyppige varesett ved hjelp av det vertikale dataformatet. Det vil transformere dataene i det horisontale dataformatet til det vertikale formatet.

For eksempel,Apriori og FP vekstbruk:

ECLAT vil ha formatet til tabellen som:

Denne metoden vil danne 2-itemsett, 3 itemsets, k itemsets i vertikalt dataformat. Denne prosessen med k økes med 1 til ingen kandidatelementer blir funnet. Noen optimaliseringsteknikker som diffset brukes sammen med Apriori.

Denne metoden har en fordel i forhold til Apriori, da den ikke krever skanning av databasen for å finne støtten til k + 1 varesett. Dette er fordi Transaksjonssettet vil føre til antall forekomster av hvert element i transaksjonen (support). Flaskehalsen kommer når det er mange transaksjoner som tar stort minne og beregningstid for å krysse settene.

Konklusjon

Apriori-algoritmen brukes til regler for gruvedrift. Det fungerer på prinsippet, 'de ikke-tomme delmengdene av hyppige varesett må også være hyppige'. Det danner k-itemset-kandidater fra (k-1) varesett og skanner databasen for å finne de hyppige varesettene.

Frequent Pattern Growth Algorithm er metoden for å finne hyppige mønstre uten generering av kandidater. Den konstruerer et FP-tre i stedet for å bruke generere og teststrategien til Apriori. FPs vekstalgoritme fokuserer på fragmentering av elementene og utvinning av hyppige mønstre.

Vi håper disse opplæringene i Data Mining Series beriket din kunnskap om Data Mining !!

type feil i programvaretesting

PREV Opplæring | FØRSTE veiledning

Anbefalt lesing

• Data Mining Techniques: Algorithm, Methods & Top Data Mining Tools
• Apriori-algoritme i datautvinning: implementering med eksempler
• Beslutningstres algoritmeeksempler i datautvinning
• Data Mining Eksempler: De vanligste applikasjonene av Data Mining 2021
• Data Mining: Prosess, teknikker og store problemer i dataanalyse
• Data Mining Process: Modeller, prosessstrinn og utfordringer involvert
• CSTE Software Testing Certification Exam Question Pattern
• Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning