Menu

Apriori-algoritme in datamining: implementatie met voorbeelden

  • Hoofd
  • Andere
  • Apriori-algoritme in datamining: implementatie met voorbeelden

apriori algorithm data mining

Probeer Ons Instrument Voor Het Oplossen Van Problemen

Diepgaande tutorial over Apriori-algoritme om frequente itemsets in datamining te ontdekken. Deze tutorial legt de stappen in Apriori uit en hoe het werkt:

In deze Datamining Tutorial Series , we hebben de Algoritme van beslissingsboom in onze vorige tutorial.

Er zijn verschillende methoden voor datamining, zoals associatie, correlatie, classificatie en clustering.

gratis flowchart maker voor mac

Deze tutorial richt zich voornamelijk op mijnbouw met behulp van associatieregels. Door middel van associatieregels identificeren we de set items of attributen die samen in een tabel voorkomen.

Apriori-algoritme

Wat je leert:

Wat is een itemset?

Een set items samen wordt een itemset genoemd. Als een itemset k-items heeft, wordt dit een k-itemset genoemd. Een itemset bestaat uit twee of meer items. Een itemset die vaak voorkomt, wordt een frequente itemset genoemd. Frequente itemset-mining is dus een dataminingtechniek om de items te identificeren die vaak samen voorkomen.

Bijvoorbeeld , Brood en boter, laptop- en antivirussoftware, enz.

Wat is een frequente itemset?

Een set items wordt frequent genoemd als deze voldoet aan een minimale drempelwaarde voor ondersteuning en vertrouwen. Ondersteuning toont transacties met items die samen in één transactie zijn gekocht. Vertrouwen toont transacties waarbij de items na elkaar worden gekocht.

Voor frequente itemset-mijnbouwmethoden houden we alleen rekening met die transacties die voldoen aan minimale drempelondersteuning en betrouwbaarheidsvereisten. Inzichten van deze mining-algoritmen bieden veel voordelen, kostenbesparingen en verbeterd concurrentievoordeel.

Er is een afwegingstijd die nodig is om gegevens te minen en de hoeveelheid gegevens voor frequente mijnbouw. Het frequente mining-algoritme is een efficiënt algoritme om de verborgen patronen van itemsets in korte tijd en met minder geheugengebruik te minen.

Frequent Pattern Mining (FPM)

Het algoritme voor frequent pattern mining is een van de belangrijkste technieken van datamining om relaties tussen verschillende items in een dataset te ontdekken. Deze relaties worden weergegeven in de vorm van associatieregels. Het helpt om de onregelmatigheden in de gegevens te vinden.

FPM heeft veel toepassingen op het gebied van data-analyse, softwarefouten, cross-marketing, analyse van verkoopcampagnes, marktkorfanalyse, enz.

Frequente itemsets die via Apriori worden ontdekt, hebben veel toepassingen in datamining-taken. Taken zoals het vinden van interessante patronen in de database, het achterhalen van de volgorde en het ontginnen van associatieregels zijn de belangrijkste.

Verenigingsregels zijn van toepassing op transactiegegevens van supermarkten, dat wil zeggen om het klantgedrag in termen van de gekochte producten te onderzoeken. Verenigingsregels beschrijven hoe vaak de items samen worden gekocht.

Verenigingsregels

Association Rule Mining wordt gedefinieerd als:

'Laat I = {…} een set van‘ n ’binaire attributen zijn, items genaamd. Laat D = {….} Een transactie zijn met de naam database. Elke transactie in D heeft een unieke transactie-ID en bevat een subset van de items in I. Een regel wordt gedefinieerd als een implicatie van de vorm X-> Y waarbij X, Y? Ik en X? Y = ?. De set items X en Y worden respectievelijk antecedent en gevolg van de regel genoemd. '

Het leren van associatieregels wordt gebruikt om relaties tussen attributen in grote databases te vinden. Een associatieregel, A => B, zal de vorm hebben 'voor een set transacties, een bepaalde waarde van itemset A bepaalt de waarden van itemset B onder de voorwaarde dat aan minimale ondersteuning en vertrouwen wordt voldaan'.

Ondersteuning en vertrouwen kunnen worden weergegeven door het volgende voorbeeld:

​

De bovenstaande verklaring is een voorbeeld van een associatieregel. Dit betekent dat er een transactie van 2% is die brood en boter samen heeft gekocht en dat 60% van de klanten naast boter ook brood heeft gekocht.

Ondersteuning en vertrouwen voor itemset A en B worden weergegeven door formules:

Formule voor ondersteuning en vertrouwen voor itemset A en B

Het minen van associatieregels bestaat uit 2 stappen:

  1. Vind alle frequente itemsets.
  2. Genereer associatieregels op basis van de bovenstaande frequente itemsets.

Waarom frequente mijnbouw met Itemset?

Frequente itemset of patroonontginning wordt algemeen gebruikt vanwege de brede toepassingen ervan in mijnbouwassociatieregels, correlaties en beperking van grafiekpatronen die zijn gebaseerd op frequente patronen, opeenvolgende patronen en vele andere datamining-taken.

Apriori-algoritme - Frequente patroonalgoritmen

Het Apriori-algoritme was het eerste algoritme dat werd voorgesteld voor het regelmatig delven van itemsets. Het werd later verbeterd door R Agarwal en R Srikant en werd bekend als Apriori. Dit algoritme gebruikt twee stappen 'samenvoegen' en 'snoeien' om de zoekruimte te verkleinen. Het is een iteratieve benadering om de meest voorkomende itemsets te ontdekken.

Apriori zegt:

De kans dat item I niet vaak voorkomt, is als:

  • PI)
  • P (I + A)
  • Als een itemset-set een waarde heeft die kleiner is dan de minimale ondersteuning, zullen al zijn supersets ook onder de minimale ondersteuning vallen en kunnen ze dus worden genegeerd. Deze eigenschap wordt de antimonotone-eigenschap genoemd.

De stappen die worden gevolgd in het Apriori-algoritme van datamining zijn:

  1. Doe mee met Step : Deze stap genereert (K + 1) itemset van K-itemsets door elk item met zichzelf samen te voegen.
  2. Snoei Stap : Deze stap scant het aantal van elk item in de database. Als het kandidaatitem niet voldoet aan de minimale ondersteuning, wordt het als zeldzaam beschouwd en wordt het verwijderd. Deze stap wordt uitgevoerd om de grootte van de kandidaatitemsets te verkleinen.

Stappen in Apriori

Het Apriori-algoritme is een reeks stappen die moet worden gevolgd om de meest voorkomende itemset in de gegeven database te vinden. Deze dataminingtechniek volgt de samenvoeg- en snoeistappen iteratief totdat de meest voorkomende itemset is bereikt. Een minimale ondersteuningsdrempel wordt gegeven in het probleem of wordt aangenomen door de gebruiker.

# 1) In de eerste iteratie van het algoritme wordt elk item beschouwd als een 1-itemsets-kandidaat. Het algoritme telt het aantal keren dat elk item voorkomt.

#twee) Laat er wat minimale ondersteuning zijn, min_sup (bijvoorbeeld 2). De set van 1 - itemsets waarvan het voorkomen voldoet aan de min sup worden bepaald. Alleen die kandidaten die meer dan of gelijk zijn aan min_sup, worden vooruitgehaald voor de volgende iteratie en de anderen worden gesnoeid.

# 3) Vervolgens worden 2-itemset frequente items met min_sup ontdekt. Hiervoor wordt in de samenvoegstap de 2-itemset gegenereerd door een groep van 2 te vormen door items met zichzelf te combineren.

# 4) De 2-itemset-kandidaten worden gesnoeid met behulp van de min-sup-drempelwaarde. Nu heeft de tafel 2 itemsets met alleen min-sup.

# 5) De volgende iteratie zal 3-itemsets vormen met behulp van de join- en prune-stap. Deze iteratie volgt de antimonotone eigenschap waarbij de subsets van 3-itemsets, dat wil zeggen de 2-itemset subsets van elke groep, in min_sup vallen. Als alle subsets van 2 itemsets frequent zijn, zal de superset frequent zijn, anders wordt deze gesnoeid.

# 6) De volgende stap volgt het maken van een 4-itemset door de 3-itemset bij zichzelf te voegen en te snoeien als de subset niet voldoet aan de min_sup-criteria. Het algoritme wordt gestopt wanneer de meest frequente itemset is bereikt.

Apriori-stappen

(beeld bron ​

Voorbeeld van Apriori:Ondersteuningsdrempel = 50%, vertrouwen = 60%

TAFEL 1

TransactieLijst van items
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, I2, I3, I4

Oplossing:

Ondersteuningsdrempel = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Telling van elk item

TAFEL 2

ItemTellen
I14
I25
I34
I44
I5twee

twee. Snoei stap: TAFEL 2 toont aan dat I5-item niet voldoet aan min_sup = 3, dus het wordt verwijderd, alleen I1, I2, I3, I4 voldoen aan min_sup count.

TAFEL 3

ItemTellen
I14
I25
I34
I44

3. Doe mee met stap: Vorm een ​​set van 2 stuks. Van TAFEL 1 ontdek het voorkomen van 2-itemset.

TABEL-4

ItemTellen
I1, I24
I1, I33
I1, I4twee
I2, I34
I2, I43
I3, I4twee

Vier. Snoei stap: TABEL -4 laat zien dat itemset {I1, I4} en {I3, I4} niet voldoen aan min_sup, dus het wordt verwijderd.

TABEL-5

ItemTellen
I1, I24
I1, I33
I2, I34
I2, I43

5. Doe mee en snoei Stap: Vorm een ​​set van 3 items. Van de TAFEL 1 ontdek het voorkomen van 3-itemset. Van TABEL-5 , ontdek de subsets van 2 items die min_sup ondersteunen.

We kunnen zien dat voor itemset {I1, I2, I3} subsets {I1, I2}, {I1, I3}, {I2, I3} voorkomen in TABEL-5 dus {I1, I2, I3} komt vaak voor.

We kunnen zien dat voor itemset {I1, I2, I4} subsets {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} niet vaak voorkomen, omdat het niet voorkomt in TABEL-5 dus {I1, I2, I4} komt niet vaak voor, daarom wordt het verwijderd.

TABEL-6

Item
I1, I2, I3
I1, I2, I4
I1, I3, I4
I2, I3, I4

Alleen {I1, I2, I3} komt vaak voor ​

6. Genereer associatieregels: Van de frequente itemset die hierboven is ontdekt, zou de associatie kunnen zijn:

{I1, I2} => {I3}

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

{I1, I3} => {I2}

Vertrouwen = ondersteuning {I1, I2, I3} / ondersteuning {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

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

{I1} => {I2, I3}

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

{I2} => {I1, I3}

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

{I3} => {I1, I2}

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

Dit toont aan dat alle bovenstaande associatieregels sterk zijn als de minimum betrouwbaarheidsdrempel 60% is.

Het Apriori-algoritme: pseudo-code

C: Kandidaat-itemset van maat k

L: Veel voorkomende itemset van maat k

Psudocode

(beeld bron ​

hoe te openen .torrent-bestand

Voordelen

  1. Makkelijk te begrijpen algoritme
  2. Join en Prune-stappen zijn eenvoudig te implementeren op grote itemsets in grote databases

Nadelen

  1. Het vereist een hoge berekening als de itemsets erg groot zijn en de minimale ondersteuning erg laag wordt gehouden.
  2. De volledige database moet worden gescand.

Methoden om de efficiëntie van Apriori te verbeteren

Er zijn veel methoden beschikbaar om de efficiëntie van het algoritme te verbeteren.

  1. Hash-gebaseerde techniek: Deze methode gebruikt een hash-gebaseerde structuur, een hashtabel genaamd, voor het genereren van de k-itemsets en het bijbehorende aantal. Het gebruikt een hash-functie voor het genereren van de tabel.
  2. Transactievermindering: Deze methode vermindert het aantal transacties dat in iteraties wordt gescand. De transacties die geen frequente items bevatten, worden gemarkeerd of verwijderd.
  3. Verdeling: Deze methode vereist slechts twee databasescans om de frequente itemsets te minen. Het zegt dat om het even welke itemset potentieel frequent in de database zou moeten hebben, deze frequent zou moeten voorkomen in ten minste één van de partities van de database.
  4. Bemonstering: Deze methode kiest een willekeurige steekproef S uit Database D en zoekt vervolgens naar frequente itemset in S. Het kan mogelijk zijn om een ​​globale frequente itemset kwijt te raken. Dit kan worden verminderd door de min_sup.
  5. Dynamische itemset tellen: Deze techniek kan nieuwe kandidaatitemsets toevoegen op elk gemarkeerd startpunt van de database tijdens het scannen van de database.

Toepassingen van het Apriori-algoritme

Enkele velden waar Apriori wordt gebruikt:

  1. Op het gebied van onderwijs: Het extraheren van associatieregels in datamining van toegelaten studenten door middel van kenmerken en specialiteiten.
  2. Op medisch gebied: Bijvoorbeeld analyse van de database van de patiënt.
  3. In bosbouw: Analyse van de waarschijnlijkheid en intensiteit van bosbrand met de bosbrandgegevens.
  4. Apriori wordt gebruikt door veel bedrijven zoals Amazon in de Aanbevelingssysteem en door Google voor de functie voor automatisch aanvullen.

Gevolgtrekking

Het Apriori-algoritme is een efficiënt algoritme dat de database slechts één keer scant.

Het vermindert de grootte van de itemsets in de database aanzienlijk, wat een goede prestatie oplevert. Datamining helpt dus consumenten en industrieën beter in het besluitvormingsproces.

Bekijk onze aanstaande tutorial om meer te weten te komen over het Frequent Pattern Growth Algorithm !!

PREV-zelfstudie ​ VOLGENDE zelfstudie

Aanbevolen literatuur

^