Apriori-algoritm i datautvinning: implementering med exempel

apriori algorithm data mining

Fördjupad handledning om Apriori-algoritm för att ta reda på frekventa artiklar i datautvinning. Denna handledning förklarar stegen i apriori och hur det fungerar:

I denna Data Mining Tutorial Series , vi tittade på Beslutsträdalgoritm i vår tidigare handledning.

Det finns flera metoder för Data Mining såsom association, korrelation, klassificering och kluster.

webbplats som låter dig ladda ner youtube-videor

Denna handledning fokuserar främst på gruvdrift med associeringsregler. Enligt associeringsregler identifierar vi uppsättningen objekt eller attribut som förekommer tillsammans i en tabell.

Vad du kommer att lära dig:

• Vad är en artikeluppsättning?
  • Vad är ett frekvent objekt?
  • Frequent Pattern Mining (FPM)
  • Föreningsregler
• Varför frekvent produktgruppbrytning?
  • Apriori-algoritm - Frekventa mönsteralgoritmer
    • Steg i Apriori
    • Fördelar
    • Nackdelar
• Metoder för att förbättra apriorieffektivitet
• Tillämpningar av apriori algoritm
• Slutsats
  • Rekommenderad läsning

Vad är en artikeluppsättning?

En uppsättning föremål tillsammans kallas ett föremål. Om någon artikel har k-artiklar kallas den för k-artiklar. En artikeluppsättning består av två eller flera artiklar. En artikeluppsättning som förekommer ofta kallas en frekvent artikeluppsättning. Således är frekvent artikeluppsättning en data miningsteknik för att identifiera de artiklar som ofta förekommer tillsammans.

Till exempel , Bröd och smör, bärbar dator och antivirusprogram etc.

Vad är ett frekvent objekt?

En uppsättning objekt kallas frekvent om den uppfyller ett minsta tröskelvärde för stöd och förtroende. Support visar transaktioner med föremål som köpts tillsammans i en enda transaktion. Förtroende visar transaktioner där varorna köps efter varandra.

För frekventa artiklar för gruvdrift beaktar vi endast de transaktioner som uppfyller minimikrav på stöd och förtroende. Insikter från dessa gruvalgoritmer erbjuder många fördelar, kostnadsbesparingar och förbättrad konkurrensfördel.

Det tar en avvägningstid att bryta data och datamängden för frekvent gruvdrift. Den frekventa gruvalgoritmen är en effektiv algoritm för att bryta de dolda mönstren för artiklar på kort tid och mindre minneskonsumtion.

Frequent Pattern Mining (FPM)

Den frekventa mönsterbrytningsalgoritmen är en av de viktigaste teknikerna för datamining för att upptäcka relationer mellan olika objekt i en dataset. Dessa relationer representeras i form av föreningsregler. Det hjälper till att hitta oegentligheter i data.

FPM har många applikationer inom dataanalys, programvarufel, kryssmarknadsföring, försäljningskampanjanalys, analys av marknadskorgen etc.

Frekventa föremål som upptäcks genom Apriori har många applikationer för datautvinning. Uppgifter som att hitta intressanta mönster i databasen, ta reda på sekvens och Mining of association-regler är de viktigaste av dem.

Föreningsregler gäller för transaktionsdata för stormarknader, det vill säga för att undersöka kundbeteendet när det gäller de köpta produkterna. Föreningsregler beskriver hur ofta varorna köps tillsammans.

Föreningsregler

Association Rule Mining definieras som:

”Låt jag = {...} vara en uppsättning binära attribut” n ”som kallas objekt. Låt D = {….} Vara en uppsättning av transaktioner som kallas databas. Varje transaktion i D har ett unikt transaktions-ID och innehåller en delmängd av objekten i I. En regel definieras som en implikation av form X-> Y där X, Y? I och X? Y = ?. Uppsättningen av artiklarna X och Y kallas antecedent respektive följd av regeln. ”

Learning of Association-regler används för att hitta relationer mellan attribut i stora databaser. En associeringsregel, A => B, kommer att ha formen ”för en uppsättning transaktioner, något värde för artikeluppsättning A bestämmer värdena för artikeluppsättning B under det villkor där minimistöd och förtroende uppfylls”.

Support och förtroende kan representeras av följande exempel:

Ovanstående uttalande är ett exempel på en associeringsregel. Det innebär att det finns en transaktion på 2% som köpte bröd och smör tillsammans och det finns 60% av kunderna som köpte bröd såväl som smör.

Stöd och förtroende för artiklar A och B representeras av formler:

Association mining mining består av två steg:

1. Hitta alla frekventa artiklar.
2. Skapa associeringsregler från ovanstående frekventa uppsättningar.

Varför frekvent produktgruppbrytning?

Frekvent artikeluppsättning eller mönsterbrytning används i stor utsträckning på grund av dess breda tillämpningar i regler för gruvföreningar, korrelationer och grafmönster som är baserade på frekventa mönster, sekventiella mönster och många andra uppgifter.

Apriori-algoritm - Frekventa mönsteralgoritmer

Apriori-algoritmen var den första algoritmen som föreslogs för frekvent gruvdrift. Det förbättrades senare av R Agarwal och R Srikant och blev känt som Apriori. Denna algoritm använder två steg 'gå med' och 'beskära' för att minska sökutrymmet. Det är en iterativ metod att upptäcka de vanligaste artiklarna.

Apriori säger:

Sannolikheten att artikel I inte är frekvent är om:

• PI)
• P (I + A)
• Om en artikeluppsättning har ett värde som är mindre än minsta stöd kommer alla dess överuppsättningar också att falla under minsta stöd och kan därför ignoreras. Den här egenskapen kallas egenskapen Antimonotone.

Stegen som följs i Apriori-algoritmen för datautvinning är:

1. Gå med i steg : Detta steg genererar (K + 1) objektuppsättning från K-artiklar genom att sammanfoga varje objekt med sig själv.
2. Beskär steg : Detta steg skannar antalet varje artikel i databasen. Om kandidatobjektet inte uppfyller minimistödet, betraktas det som sällsynt och därför tas det bort. Detta steg utförs för att minska storleken på kandidatobjektuppsättningarna.

Steg i Apriori

Apriori-algoritmen är en sekvens av steg som ska följas för att hitta de vanligaste artiklarna i den angivna databasen. Denna datautvecklingsteknik följer sammanfogningen och beskärningen stiger iterativt tills den vanligaste uppsättningen uppnås. En minsta stödtröskel anges i problemet eller antas av användaren.

# 1) I den första iterationen av algoritmen tas varje objekt som en kandidat med 1 objekt. Algoritmen kommer att räkna förekomsten av varje artikel.

#två) Låt det finnas lite minimistöd, min_sup (t.ex. 2). Uppsättningen av 1 - uppsättningar vars förekomst uppfyller min sup bestäms. Endast de kandidater som räknas mer än eller lika med min_sup tas framåt för nästa iteration och de andra beskärs.

# 3) Därefter upptäcks 2-artikels frekventa artiklar med min_sup. För detta i sammanfogningssteget genereras 2-artikelsatsen genom att bilda en grupp av 2 genom att kombinera objekt med sig själv.

# 4) Kandidaterna med två poster beskärs med min-sup tröskelvärde. Nu kommer tabellen att ha två –uppsättningar med endast min-sup.

# 5) Nästa iteration kommer att bildas 3 - objektuppsättningar genom att gå med och beskära steg. Denna iteration kommer att följa antimonotonegenskapen där delmängderna av 3-objektsuppsättningar, det vill säga de 2 -emsatsuppsättningsdelarna för varje grupp faller i min_sup. Om alla underuppsättningar med två artiklar är frekventa kommer överuppsättningen att vara frekvent annars beskärs den.

# 6) Nästa steg följer att skapa 4-artikelsats genom att gå med 3-artikelsats med sig själv och beskära om dess delmängd inte uppfyller min_sup-kriterierna. Algoritmen stoppas när den vanligaste artikeluppsättningen uppnås.

(bild källa )

Exempel på Apriori: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

två. Beskär steg: TABELL 2 visar att I5-objektet inte uppfyller min_sup = 3, så det raderas, bara I1, I2, I3, I4 uppfyller min_sup-räkningen.

TABELL-3

3. Gå med i steg: Form 2-artikelsats. Från BORD 1 ta reda på förekomsten av 2-itemset.

TABELL-4

Fyra. Beskär steg: TABELL -4 visar att artikeluppsättningen {I1, I4} och {I3, I4} inte uppfyller min_sup, så den tas bort.

TABELL-5

5. Gå med och beskära steg: Form 3-uppsättning. Från BORD 1 ta reda på förekomster av 3-artiklar. Från TABELL-5 , ta reda på de underuppsättningar med två artiklar som stöder min_sup.

Vi kan se för objektuppsättningar {I1, I2, I3} delmängder, {I1, I2}, {I1, I3}, {I2, I3} förekommer i TABELL-5 sålunda är {I1, I2, I3} frekvent.

Vi kan se för objektuppsättningar {I1, I2, I4} underuppsättningar, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} är ​​inte frekventa, eftersom det inte förekommer i TABELL-5 alltså är {I1, I2, I4} inte frekvent, därför raderas den.

TABELL-6

Endast {I1, I2, I3} är frekventa .

6. Generera föreningsregler: Från den frekventa artikeluppsättningen som upptäcktes ovan kan föreningen vara:

{I1, I2} => {I3}

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

{I1, I3} => {I2}

Förtroende = support {I1, I2, I3} / support {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

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

{I1} => {I2, I3}

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

{I2} => {I1, I3}

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

{I3} => {I1, I2}

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

beslutsträdalgoritm vid datautvinning

Detta visar att alla ovanstående associeringsregler är starka om minsta tillförlitlighetströskel är 60%.

Apriori-algoritmen: Pseudokod

C: Kandidatuppsättning av storlek k

L: Frekventa artiklar i storlek k

(bild källa )

Fördelar

1. Lätt att förstå algoritmen
2. Stegen för anslutning och beskärning är enkla att implementera på stora artiklar i stora databaser

Nackdelar

1. Det kräver hög beräkning om artiklarna är mycket stora och minimistödet hålls mycket lågt.
2. Hela databasen måste skannas.

Metoder för att förbättra apriorieffektivitet

Många metoder finns tillgängliga för att förbättra algoritmens effektivitet.

1. Hash-baserad teknik: Denna metod använder en hash-baserad struktur som kallas en hash-tabell för att generera k-itemsets och dess motsvarande antal. Den använder en hash-funktion för att generera tabellen.
2. Transaktionsminskning: Denna metod minskar antalet transaktioner som skannas i iterationer. Transaktionerna som inte innehåller frekventa artiklar markeras eller tas bort.
3. Partitionering: Den här metoden kräver endast två databasskanningar för att bryta de frekventa artiklarna. Det står att för att varje artikeluppsättning ska vara potentiellt frekvent i databasen, bör den förekomma i minst en av partitionerna i databasen.
4. Provtagning: Denna metod plockar ett slumpmässigt urval S från databas D och söker sedan efter frekventa artiklar i S. Det kan vara möjligt att förlora ett globalt frekvent objekt. Detta kan minskas genom att sänka min_sup.
5. Räkning av dynamiska artiklar: Denna teknik kan lägga till nya kandidatuppsättningar vid valfri startpunkt i databasen under genomsökning av databasen.

Tillämpningar av apriori algoritm

Några fält där Apriori används:

1. Inom utbildningsområdet: Extrahera associeringsregler i datautvinning av antagna studenter genom egenskaper och specialiteter.
2. Inom det medicinska området: Till exempel analys av patientens databas.
3. Inom skogsbruk: Analys av sannolikhet och intensitet för skogsbrand med skogsbranddata.
4. Apriori används av många företag som Amazon i Rekommendationssystem och av Google för funktionen för automatisk komplettering.

Slutsats

Apriori-algoritmen är en effektiv algoritm som bara skannar databasen en gång.

Det minskar storleken på artikeluppsättningarna i databasen avsevärt och ger en bra prestanda. Således hjälper data mining konsumenter och industrier bättre i beslutsprocessen.

Kolla in vår kommande handledning för att lära dig mer om Algoritmen för frekvent mönstertillväxt !!

PREV-handledning | NÄSTA självstudie

Rekommenderad läsning

• Data Mining Techniques: Algorithm, Methods & Top Data Mining Tools
• Data Mining: Process, Techniques & Major Issues In Data Analysis
• Exempel på datautvinning: De vanligaste tillämpningarna av datautvinning 2021
• Beslutsträdalgoritmsexempel i Data Mining
• Data Mining Process: Modeller, involverade processsteg och utmaningar
• Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning
• Topp 15 bästa gratis datagruvverktyg: den mest omfattande listan
• JMeter-dataparameterisering med användardefinierade variabler