Meniu

Algoritmul Apriori în Data Mining: Implementare cu exemple

  • Principal
  • Alte
  • Algoritmul Apriori în Data Mining: Implementare cu exemple

apriori algorithm data mining

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Tutorial în profunzime despre algoritmul Apriori pentru a afla seturi de articole frecvente în exploatarea datelor. Acest tutorial explică pașii din Apriori și cum funcționează:

In acest Seria de tutoriale de minerit de date , ne-am uitat la Algoritmul arborelui decizional în tutorialul nostru anterior.

Există mai multe metode pentru Data Mining, cum ar fi asocierea, corelația, clasificarea și gruparea.

cum se numesc erorile din software-ul de calculator

Acest tutorial se concentrează în principal pe minerit folosind reguli de asociere. Prin reguli de asociere, identificăm setul de articole sau atribute care apar împreună într-un tabel.

Algoritmul Apriori

Ce veți învăța:

Ce este un set de articole?

Un set de articole împreună se numește set de articole. Dacă un set de articole are k-items, se numește k-itemset. Un set de articole constă din două sau mai multe articole. Un set de articole care apare frecvent se numește set de articole frecvente. Astfel, extragerea frecventă a seturilor de articole este o tehnică de extragere a datelor pentru a identifica articolele care apar adesea împreună.

De exemplu , Pâine și unt, Laptop și software Antivirus etc.

Ce este un set de articole frecvente?

Un set de articole este numit frecvent dacă îndeplinește o valoare prag minimă pentru sprijin și încredere. Asistența arată tranzacțiile cu articole cumpărate împreună într-o singură tranzacție. Încrederea arată tranzacțiile în care articolele sunt achiziționate unul după altul.

Pentru metoda frecventă de extragere a articolelor, luăm în considerare doar acele tranzacții care îndeplinesc cerințele minime de sprijin și de încredere. Perspectivele acestor algoritmi de minerit oferă o mulțime de beneficii, reducerea costurilor și un avantaj competitiv îmbunătățit.

Există o perioadă de compensare luată pentru exploatarea datelor și volumul de date pentru exploatarea frecventă. Algoritmul de exploatare frecventă este un algoritm eficient pentru extragerea tiparelor ascunse ale seturilor de articole într-un timp scurt și cu un consum mai mic de memorie.

Exploatarea frecventă a modelelor (FPM)

Algoritmul frecvent de extragere a modelelor este una dintre cele mai importante tehnici de extragere a datelor pentru a descoperi relații între diferite elemente dintr-un set de date. Aceste relații sunt reprezentate sub forma unor reguli de asociere. Ajută la găsirea neregulilor din date.

FPM are multe aplicații în domeniul analizei datelor, erorilor software, cross-marketing, analiza campaniilor de vânzare, analiza coșului de piață etc.

Seturile de obiecte frecvente descoperite prin Apriori au multe aplicații în sarcinile de extragere a datelor. Sarcini precum găsirea de modele interesante în baza de date, aflarea secvenței și extragerea regulilor de asociere este cea mai importantă dintre ele.

Regulile de asociere se aplică datelor tranzacțiilor din supermarket, adică pentru a examina comportamentul clienților în ceea ce privește produsele achiziționate. Regulile de asociere descriu cât de des sunt achiziționate articolele împreună.

Regulile de asociere

Exploatarea regulilor de asociere este definită ca:

„Fie I = {…} un set de atribute binare„ n ”numite elemente. Fie D = {….} Setul tranzacției numită bază de date. Fiecare tranzacție din D are un ID de tranzacție unic și conține un subset al articolelor din I. O regulă este definită ca o implicație a formei X-> Y unde X, Y? Eu și X? Y = ?. Setul de itemi X și Y se numește antecedent și, respectiv, consecința regulii. ”

Învățarea regulilor de asociere este utilizată pentru a găsi relații între atribute în baze de date mari. O regulă de asociere, A => B, va avea forma „pentru un set de tranzacții, o anumită valoare a setului de elemente A determină valorile setului de articole B în condiția în care suportul și încrederea minime sunt îndeplinite”.

Asistența și încrederea pot fi reprezentate de următorul exemplu:

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

Afirmația de mai sus este un exemplu de regulă de asociere. Acest lucru înseamnă că există o tranzacție de 2% care a cumpărat împreună pâine și unt și există 60% dintre clienții care au cumpărat pâine, precum și unt.

Suportul și încrederea pentru elementele A și B sunt reprezentate de formule:

Formula de sprijin și încredere pentru elementele A și B.

Exploatarea regulilor de asociere constă din 2 pași:

  1. Găsiți toate seturile obișnuite.
  2. Generați reguli de asociere din elementele frecvente de mai sus.

De ce exploatarea frecventă a obiectelor?

Exploatarea frecventă de articole sau tipare este utilizată pe scară largă datorită aplicațiilor sale largi în regulile de asociere a minelor, corelații și constrângerea tiparelor grafice care se bazează pe tipare frecvente, tipare secvențiale și multe alte sarcini de minerit de date.

Algoritmul Apriori - Algoritmi de modele frecvente

Algoritmul Apriori a fost primul algoritm care a fost propus pentru extragerea frecventă a obiectelor. Ulterior a fost îmbunătățit de R Agarwal și R Srikant și a devenit cunoscut sub numele de Apriori. Acest algoritm utilizează doi pași „join” și „prune” pentru a reduce spațiul de căutare. Este o abordare iterativă pentru a descoperi cele mai frecvente seturi de articole.

Apriori spune:

Probabilitatea ca elementul I să nu fie frecvent este dacă:

  • P (I)
  • P (I + A)
  • Dacă un set de articole are o valoare mai mică decât suportul minim, atunci toate supersetele sale vor cădea, de asemenea, sub suportul minim și, prin urmare, pot fi ignorate. Această proprietate se numește proprietatea Antimonotone.

Pașii urmați în algoritmul Apriori de extragere a datelor sunt:

  1. Alătură-te lui Step : Acest pas generează (K + 1) set de articole din K-itemsets prin unirea fiecărui articol cu ​​el însuși.
  2. Prune Step : Acest pas scanează numărul fiecărui articol din baza de date. Dacă elementul candidat nu îndeplinește sprijinul minim, atunci este considerat ca fiind rar și astfel este eliminat. Acest pas este efectuat pentru a reduce dimensiunea seturilor de articole candidate.

Pași în Apriori

Algoritmul Apriori este o secvență de pași care trebuie urmați pentru a găsi cel mai frecvent set de articole din baza de date dată. Această tehnică de extragere a datelor urmează pașii iterați de îmbinare și prune până când se atinge cel mai frecvent set de articole. Un prag minim de asistență este dat în problemă sau este asumat de utilizator.

# 1) În prima iterație a algoritmului, fiecare element este luat ca un candidat de 1 element. Algoritmul va număra aparițiile fiecărui element.

#Două) Să existe un sprijin minim, min_sup (de ex. 2). Se determină setul de 1 - seturi de articole a căror apariție îndeplinește valoarea minimă. Numai acei candidați care contează mai mult sau egal cu min_sup, sunt luați înainte pentru următoarea iterație și ceilalți sunt tăiați.

# 3) Apoi, sunt descoperite 2-itemset obiecte frecvente cu min_sup. Pentru aceasta, în pasul de asociere, setul de 2 articole este generat prin formarea unui grup de 2 prin combinarea articolelor cu el însuși.

# 4) Candidații cu 2 articole sunt tăiați folosind valoarea pragului min-sup. Acum tabelul va avea 2 seturi de elemente numai cu min-sup.

# 5) Următoarea iterație va forma 3 seturi de elemente folosind unirea și pasul de tăiere. Această iterație va urma proprietății antimonotone în care subseturile de 3-itemsets, adică cele 2 -setetsets ale fiecărui grup se încadrează în min_sup. Dacă toate subseturile cu 2 articole sunt frecvente, supersetul va fi frecvent, altfel este tăiat.

# 6) Următorul pas va urma realizarea 4-itemset prin alăturarea 3-itemset cu el însuși și tăiere dacă subsetul său nu îndeplinește criteriile min_sup. Algoritmul este oprit când se realizează cel mai frecvent set de articole.

Pașii Apriori

(imagine sursă )

Exemplu de Apriori:Prag de asistență = 50%, Încredere = 60%

TABELUL 1

TranzacţieListă de obiecte
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, I2, I3, I4

Soluţie:

Prag de asistență = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Numărul fiecărui articol

MASA 2

ArticolNumara
I14
I25
I34
I44
I5Două

2. Pas de prune: MASA 2 arată că elementul I5 nu îndeplinește min_sup = 3, astfel este șters, doar I1, I2, I3, I4 îndeplinesc numărul min_sup.

TABELUL-3

ArticolNumara
I14
I25
I34
I44

3. Alăturați-vă pasului: Formular 2 seturi de articole. Din TABELUL 1 aflați aparițiile 2-itemset.

TABEL-4

ArticolNumara
I1, I24
I1, I33
I1, I4Două
I2, I34
I2, I43
I3, I4Două

Patru. Pas de prune: TABEL -4 arată că setul de articole {I1, I4} și {I3, I4} nu îndeplinește min_sup, deci este șters.

TABELUL-5

ArticolNumara
I1, I24
I1, I33
I2, I34
I2, I43

5. Alăturați-vă și tăiați pasul: Formați 3 seturi de articole. De la TABELUL 1 aflați aparițiile unui set de 3 articole. Din TABELUL-5 , aflați subseturile de 2 elemente care acceptă min_sup.

Putem vedea pentru seturile de elemente {I1, I2, I3} subseturi, {I1, I2}, {I1, I3}, {I2, I3} au loc în TABELUL-5 astfel {I1, I2, I3} este frecventă.

Putem vedea subseturile de elemente {I1, I2, I4}, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} nu sunt frecvente, deoarece nu se întâmplă în TABELUL-5 astfel {I1, I2, I4} nu este frecvent, prin urmare este șters.

TABEL-6

Articol
I1, I2, I3
I1, I2, I4
I1, I3, I4
I2, I3, I4

Doar {I1, I2, I3} este frecventă .

6. Generați reguli de asociere: Din elementele frecvente descoperite mai sus, asociația ar putea fi:

{I1, I2} => {I3}

Încredere = suport {I1, I2, I3} / suport {I1, I2} = (3/4) * 100 = 75%

{I1, I3} => {I2}

Încredere = suport {I1, I2, I3} / suport {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

Încredere = suport {I1, I2, I3} / suport {I2, I3} = (3/4) * 100 = 75%

{I1} => {I2, I3}

Încredere = suport {I1, I2, I3} / suport {I1} = (3/4) * 100 = 75%

{I2} => {I1, I3}

Încredere = suport {I1, I2, I3} / suport {I2 = (3/5) * 100 = 60%

{I3} => {I1, I2}

Încredere = suport {I1, I2, I3} / suport {I3} = (3/4) * 100 = 75%

Acest lucru arată că toate regulile de asociere de mai sus sunt puternice dacă pragul minim de încredere este de 60%.

Algoritmul Apriori: Pseudo Cod

C: Set de articole candidate de dimensiunea k

L: Seturi obișnuite de mărime k

Psudocod

(imagine sursă )

Avantaje

  1. Algoritm ușor de înțeles
  2. Pașii de alăturare și tăiere sunt ușor de implementat pe seturi de articole mari din baze de date mari

Dezavantaje

  1. Este nevoie de un calcul ridicat dacă seturile de articole sunt foarte mari și suportul minim este menținut foarte scăzut.
  2. Întreaga bază de date trebuie scanată.

Metode de îmbunătățire a eficienței Apriori

Sunt disponibile multe metode pentru îmbunătățirea eficienței algoritmului.

  1. Tehnica bazată pe Hash: Această metodă folosește o structură bazată pe hash numită tabel hash pentru generarea seturilor k-items și a numărului corespunzător. Folosește o funcție hash pentru generarea tabelului.
  2. Reducerea tranzacției: Această metodă reduce numărul de tranzacții scanate în iterații. Tranzacțiile care nu conțin articole frecvente sunt marcate sau eliminate.
  3. Partiționare: Această metodă necesită doar două scanări ale bazei de date pentru a extrage seturile de articole frecvente. Se spune că, pentru ca orice set de articole să fie potențial frecvent în baza de date, ar trebui să fie frecvent în cel puțin una dintre partițiile bazei de date.
  4. Eșantionare: Această metodă alege un eșantion S din baza de date D și apoi caută seturi obiecte frecvente în S. Poate fi posibil să pierzi un set de obiecte frecvente la nivel global. Acest lucru poate fi redus prin scăderea min_sup.
  5. Numărare dinamică de articole: Această tehnică poate adăuga noi seturi de articole candidate la orice punct de pornire marcat al bazei de date în timpul scanării bazei de date.

Aplicații ale algoritmului Apriori

Unele câmpuri în care se utilizează Apriori:

  1. În domeniul educației: Extragerea regulilor de asociere în extragerea de date a studenților admiși prin caracteristici și specialități.
  2. În domeniul medical: De exemplu, Analiza bazei de date a pacientului.
  3. În silvicultură: Analiza probabilității și intensității incendiilor forestiere cu datele privind incendiile forestiere.
  4. Apriori este utilizat de multe companii precum Amazon în Sistem de recomandare și de Google pentru funcția de completare automată.

Concluzie

Algoritmul Apriori este un algoritm eficient care scanează baza de date o singură dată.

Reduce dimensiunea seturilor de articole din baza de date, oferind o performanță bună. Astfel, extragerea de date îi ajută pe consumatori și industrii să aibă mai bine în procesul decizional.

Consultați următorul nostru tutorial pentru a afla mai multe despre algoritmul de creștere a modelelor frecvente !!

PREV Tutorial | NEXT Tutorial

testarea întrebărilor de interviu pentru profesioniști cu experiență, cu răspunsuri

Lectură recomandată

^