Frekvensmönster (FP) Tillväxtalgoritm i Data Mining

frequent pattern growth algorithm data mining

Detaljerad handledning om frekvent mönsterväxtalgoritm som representerar databasen i form av ett FP-träd. Inkluderar FP-tillväxt jämfört med Apriori:

Apriori-algoritm förklarades i detalj i vår tidigare handledning. I denna handledning lär vi oss om frekvent mönsterväxt - FP-tillväxt är en metod för att bryta frekventa artiklar.

stora dataanalysverktyg öppen källkod

Som vi alla vet är Apriori en algoritm för frekvent mönsterbrytning som fokuserar på att generera artiklar och upptäcka de vanligaste artiklarna. Det minskar storleken på artikeluppsättningen i databasen, men Apriori har också sina egna brister.

Läs igenom vår Hela utbildningsserien för datautvinning för fullständig kunskap om konceptet.

Vad du kommer att lära dig:

• Brister i Apriori-algoritmen
• Frekvent algoritm för tillväxtmönster
• FP-träd
• Frekventa mönsteralgoritmsteg
• Exempel på FP-tillväxtalgoritm
• Fördelar med FP-tillväxtalgoritm
• Nackdelar med FP-tillväxtalgoritm
• FP-tillväxt vs Apriori
• ECLAT
• Slutsats
• Rekommenderad läsning

Brister i Apriori-algoritmen

1. Att använda Apriori behöver en generation av kandidatobjekt. Dessa artiklar kan ha ett stort antal om artiklarna i databasen är enorma.
2. Apriori behöver flera genomsökningar av databasen för att kontrollera supporten för varje genererad artikeluppsättning och detta leder till höga kostnader.

Dessa brister kan övervinnas med hjälp av FP-tillväxtalgoritmen.

Algoritm för frekvent mönstertillväxt

Denna algoritm är en förbättring av Apriori-metoden. Ett frekvent mönster genereras utan behov av kandidatgenerering. FP-tillväxtalgoritm representerar databasen i form av ett träd som kallas ett frekvent mönsterträd eller FP-träd.

Denna trädstruktur kommer att bibehålla kopplingen mellan artiklarna. Databasen är fragmenterad med ett frekvent objekt. Denna fragmenterade del kallas ”mönsterfragment”. Objektuppsättningarna för dessa fragmenterade mönster analyseras. Således med denna metod minskar sökningen efter frekventa artiklar relativt sett.

FP-träd

Frequent Pattern Tree är en trädliknande struktur som skapas med de ursprungliga objektuppsättningarna i databasen. Syftet med FP-trädet är att bryta det vanligaste mönstret. Varje nod i FP-trädet representerar ett objekt i artikeluppsättningen.

Rotnoden representerar null medan de nedre noderna representerar artikeluppsättningarna. Associeringen av noder med de nedre noder som är föremålen med de andra föremålen upprätthålls samtidigt som trädet bildas.

Vanliga mönsteralgoritmsteg

Den frekventa mönsterväxtmetoden låter oss hitta det frekventa mönstret utan att generera kandidater.

Låt oss se stegen som följs för att bryta det frekventa mönstret med frekvent mönsterväxtalgoritm:

# 1) Det första steget är att skanna databasen för att hitta förekomsten av artikeluppsättningarna i databasen. Detta steg är detsamma som det första steget i Apriori. Antalet 1-objektuppsättningar i databasen kallas stödräkning eller frekvens för 1-objektuppsättning.

hur man initierar en länkad lista i java

#två) Det andra steget är att konstruera FP-trädet. För detta, skapa trädets rot. Roten representeras av null.

# 3) Nästa steg är att skanna databasen igen och undersöka transaktionerna. Undersök den första transaktionen och ta reda på artiklarna i den. Objektuppsättningen med maxantalet tas överst, nästa artikeluppsättning med lägre antal och så vidare. Det betyder att trädets gren är konstruerad med transaktionsobjekt i fallande ordning.

# 4) Nästa transaktion i databasen undersöks. Objektuppsättningarna ordnas i fallande ordning. Om någon artikeluppsättning av denna transaktion redan finns i en annan gren (till exempel i den första transaktionen), skulle denna transaktionsgren dela ett gemensamt prefix till roten.

Detta betyder att den gemensamma artikeluppsättningen är länkad till den nya noden i en annan artikeluppsättning i denna transaktion.

# 5) Dessutom ökas räkningen av artikeluppsättningen när den sker i transaktionerna. Både den gemensamma noden och det nya nodantalet ökas med 1 när de skapas och länkas enligt transaktioner.

# 6) Nästa steg är att bryta det skapade FP-trädet. För detta undersöks den lägsta noden först tillsammans med länkarna till de lägsta noderna. Den lägsta noden representerar frekvensmönsterlängden 1. Därifrån korsar du vägen i FP-trädet. Denna väg eller banor kallas en villkorlig mönsterbas.

Villkorligt mönsterbas är en underdatabas som består av prefixvägar i FP-trädet som förekommer med den lägsta noden (suffixet).

# 7) Konstruera ett villkorligt FP-träd, som bildas av ett antal objekt i sökvägen. Objektuppsättningarna som uppfyller tröskelstödet beaktas i det villkorliga FP-trädet.

# 8) Frekventa mönster genereras från det villkorliga FP-trädet.

Exempel på FP-tillväxtalgoritm

Stödtröskel = 50%, förtroende = 60%

bord 1

Lösning:

Stödtröskel = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Räkna av varje artikel

Tabell 2

2. Sortera artikeluppsättningen i fallande ordning.

Tabell 3

java 8 nya funktioner med exempel

3. Bygg FP-träd

1. Med tanke på rotnoden null.
2. Den första genomsökningen av Transaktion T1: I1, I2, I3 innehåller tre objekt {I1: 1}, {I2: 1}, {I3: 1}, där I2 är länkat som ett barn till root, I1 är länkat till I2 och I3 är kopplad till I1.
3. T2: I2, I3, I4 innehåller I2, I3 och I4, där I2 är kopplat till rot, I3 är kopplat till I2 och I4 är kopplat till I3. Men den här grenen skulle dela I2-noden så vanligt som den redan används i T1.
4. Öka antalet I2 med 1 och I3 är kopplat som barn till I2, I4 är kopplat som barn till I3. Räkningen är {I2: 2}, {I3: 1}, {I4: 1}.
5. T3: I4, I5. På samma sätt är en ny gren med I5 kopplad till I4 när ett barn skapas.
6. T4: I1, I2, I4. Sekvensen kommer att vara I2, I1 och I4. I2 är redan länkad till rotnoden, därför kommer den att ökas med 1. På samma sätt ökas I1 med 1 eftersom den redan är länkad med I2 i T1, alltså {I2: 3}, {I1: 2}, {I4: 1}.
7. T5: I1, I2, I3, I5. Sekvensen kommer att vara I2, I1, I3 och I5. Således {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
8. T6: I1, I2, I3, I4. Sekvensen kommer att vara I2, I1, I3 och I4. Således {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

4. Brytning av FP-träd sammanfattas nedan:

1. Det lägsta nodobjektet I5 betraktas inte eftersom det inte har ett minsta stödantal, därför raderas det.
2. Nästa nedre nod är I4. I4 förekommer i två grenar, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Därför betraktar I4 som suffix kommer prefixvägarna att vara {I2, I1, I3: 1}, {I2, I3: 1}. Detta utgör den villkorliga mönsterbasen.
3. Den villkorliga mönsterbasen betraktas som en transaktionsdatabas, ett FP-träd konstrueras. Detta kommer att innehålla {I2: 2, I3: 2}, I1 betraktas inte eftersom den inte uppfyller antalet minsta stöd.
4. Den här sökvägen genererar alla kombinationer av frekventa mönster: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
5. För I3 skulle prefixbanan vara: {I2, I1: 3}, {I2: 1}, detta genererar ett FP-träd med två noder: {I2: 4, I1: 3} och frekventa mönster genereras: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
6. För I1 skulle prefixbanan vara: {I2: 4} detta kommer att generera en enda nod FP-träd: {I2: 4} och frekventa mönster genereras: {I2, I1: 4}.

Diagrammet nedan visar det villkorliga FP-trädet som är associerat med den villkorliga noden I3.

Fördelar med FP-tillväxtalgoritm

1. Denna algoritm behöver bara skanna databasen två gånger jämfört med Apriori som skannar transaktionerna för varje iteration.
2. Parning av objekt görs inte i denna algoritm och det gör det snabbare.
3. Databasen lagras i en kompakt version i minnet.
4. Det är effektivt och skalbart för brytning av både långa och korta frekventa mönster.

Nackdelar med FP-tillväxtalgoritm

1. FP Tree är mer besvärligt och svårt att bygga än Apriori.
2. Det kan vara dyrt.
3. När databasen är stor kanske algoritmen inte passar i det delade minnet.

FP-tillväxt vs Apriori

ECLAT

Ovanstående metod, Apriori och FP-tillväxt, bryter frekventa artiklar med horisontellt dataformat. ECLAT är en metod för att bryta frekventa artiklar med vertikalt dataformat. Det kommer att förvandla data i det horisontella dataformatet till det vertikala formatet.

Till exempel,Apriori- och FP-tillväxtanvändning:

ECLAT har tabellformat som:

Denna metod kommer att bilda 2-objekt, 3 artiklar, k-objekt i vertikalt dataformat. Denna process med k ökas med 1 tills inga kandidatobjekt hittas. Vissa optimeringstekniker som diffset används tillsammans med Apriori.

Den här metoden har en fördel jämfört med Apriori eftersom den inte kräver skanning av databasen för att hitta stöd för k + 1-objektuppsättningar. Detta beror på att transaktionsuppsättningen kommer att räkna antalet förekomster av varje artikel i transaktionen (support). Flaskhalsen kommer när det finns många transaktioner som tar enormt minne och beräknad tid för att korsa uppsättningarna.

Slutsats

Apriori-algoritmen används för regler för gruvföreningar. Det fungerar på principen, 'de icke-tomma delmängderna av frekventa artiklar måste också vara frekventa'. Det bildar k-posteruppsättningskandidater från (k-1) objektuppsättningar och genomsöker databasen för att hitta de frekventa objektuppsättningarna.

Frequent Pattern Growth Algorithm är metoden för att hitta frekventa mönster utan kandidatgenerering. Den konstruerar ett FP-träd snarare än att använda generera och testa strategin för Apriori. FP-tillväxtalgoritmen fokuserar på att fragmentera banornas vägar och bryta frekventa mönster.

Vi hoppas att dessa handledning i Data Mining-serien berikade din kunskap om Data Mining !!

PREV-handledning | FÖRSTA självstudier

Rekommenderad läsning

• Data Mining Techniques: Algoritm, Methods & Top Data Mining Tools
• Apriori-algoritm i datautvinning: implementering med exempel
• Beslutsträdalgoritmsexempel i Data Mining
• Data Mining Exempel: De vanligaste tillämpningarna av Data Mining 2021
• Data Mining: Process, Techniques & Major Issues In Data Analysis
• Data Mining Process: Modeller, Process Steps & Challenges Involved
• CSTE Software Testing Certification Exam Question Pattern
• Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning