Algoritmul de creștere a modelului frecvent (FP) în exploatarea datelor

frequent pattern growth algorithm data mining

Tutorial detaliat despre algoritmul de creștere a modelelor frecvente care reprezintă baza de date în forma unui arbore FP. Include comparația FP Growth Vs Apriori:

Algoritmul Apriori a fost explicat în detaliu în tutorialul nostru anterior. În acest tutorial, vom afla despre Creșterea frecventă a modelelor - Creșterea FP este o metodă de extragere a seturilor de articole frecvente.

care site oferă o recenzie despre software-ul de curățare a registrului

După cum știm cu toții, Apriori este un algoritm pentru exploatarea frecventă a modelelor, care se concentrează pe generarea de seturi de articole și descoperirea celui mai frecvent set de articole. Reduce foarte mult dimensiunea setului de articole din baza de date, cu toate acestea, Apriori are și propriile sale neajunsuri.

Citiți prin intermediul nostru Întreaga serie de instruire în domeniul mineritului de date pentru o cunoaștere completă a conceptului.

Ce veți învăța:

• Neajunsurile algoritmului Apriori
• Algoritmul de creștere a modelelor frecvente
• Arborele FP
• Pași frecvenți ai algoritmului modelului
• Exemplu de algoritm de creștere FP
• Avantajele algoritmului de creștere FP
• Dezavantaje ale algoritmului de creștere FP
• FP Growth vs Apriori
• ECLAT
• Concluzie
• Lectură recomandată

Neajunsurile algoritmului Apriori

1. Utilizarea Apriori are nevoie de o generație de seturi de articole candidate. Aceste seturi de articole pot avea un număr mare dacă setul de articole din baza de date este imens.
2. Apriori are nevoie de mai multe scanări ale bazei de date pentru a verifica suportul fiecărui set de articole generate și acest lucru duce la costuri ridicate.

Aceste neajunsuri pot fi depășite folosind algoritmul de creștere FP.

Algoritmul de creștere a modelelor frecvente

Acest algoritm este o îmbunătățire a metodei Apriori. Un tipar frecvent este generat fără a fi nevoie de generația de candidați. Algoritmul de creștere FP reprezintă baza de date sub forma unui copac numit copac cu model frecvent sau copac FP.

Această structură arborescentă va menține asocierea dintre seturile de articole. Baza de date este fragmentată folosind un element frecvent. Această parte fragmentată se numește „fragment de model”. Sunt analizate seturile de elemente ale acestor modele fragmentate. Astfel, cu această metodă, căutarea seturilor de articole frecvente este redusă comparativ.

Arborele FP

Arborele de modele frecvente este o structură asemănătoare unui copac care este realizată cu seturile inițiale ale bazei de date. Scopul arborelui FP este de a extrage cel mai frecvent model. Fiecare nod al arborelui FP reprezintă un element din setul de articole.

Nodul rădăcină reprezintă nul, în timp ce nodurile inferioare reprezintă seturile de articole. Asocierea nodurilor cu nodurile inferioare, care sunt elementele cu celelalte seturi, se menține în timpul formării arborelui.

Pași frecvenți ai algoritmului modelului

Metoda frecventă de creștere a tiparului ne permite să găsim tiparul frecvent fără generația candidatului.

Să vedem pașii urmați pentru extragerea modelului frecvent folosind algoritmul de creștere a modelului frecvent:

# 1) Primul pas este scanarea bazei de date pentru a găsi aparițiile seturilor de articole din baza de date. Acest pas este același cu primul pas din Apriori. Numărul de 1 seturi de articole din baza de date se numește numărare de suport sau frecvență de 1 set de articole.

#Două) Al doilea pas este construirea arborelui FP. Pentru aceasta, creați rădăcina arborelui. Rădăcina este reprezentată de nul.

# 3) Următorul pas este scanarea din nou a bazei de date și examinarea tranzacțiilor. Examinați prima tranzacție și aflați elementele din ea. Setul de articole cu numărul maxim este luat în partea de sus, următorul set de articole cu numărul mai mic și așa mai departe. Înseamnă că ramura arborelui este construită cu seturi de articole de tranzacție în ordinea descrescătoare a numărului.

# 4) Următoarea tranzacție din baza de date este examinată. Seturile de articole sunt ordonate în ordine descrescătoare de numărare. Dacă vreun set de articole al acestei tranzacții este deja prezent într-o altă ramură (de exemplu în prima tranzacție), atunci această ramură a tranzacției ar avea un prefix comun la rădăcină.

Aceasta înseamnă că elementul comun este legat de noul nod al unui alt element din această tranzacție.

# 5) De asemenea, numărul de elemente este incrementat pe măsură ce apare în tranzacții. Atât numărul comun de noduri, cât și numărul de noduri noi sunt crescute cu 1 pe măsură ce sunt create și legate în funcție de tranzacții.

# 6) Următorul pas este de a extrage arborele FP creat. Pentru aceasta, cel mai mic nod este examinat mai întâi împreună cu legăturile celor mai mici noduri. Cel mai mic nod reprezintă lungimea modelului de frecvență 1. De aici, parcurgeți calea din Arborele FP. Această cale sau căi sunt numite o bază de model condițional.

Baza tiparului condițional este o subdată de date care constă din căi de prefix în arborele FP care au loc cu cel mai mic nod (sufix).

# 7) Construiți un arbore FP condiționat, care este format dintr-un număr de seturi de articole din cale. Seturile de elemente care îndeplinesc suportul pragului sunt luate în considerare în Arborele FP condițional

# 8) Modele frecvente sunt generate din arborele FP condiționat.

Exemplu de algoritm de creștere FP

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

tabelul 1

Soluţie:

cum se face o copie a unui array Java

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

1. Numărul fiecărui articol

masa 2

2. Sortați setul de articole în ordine descrescătoare.

Tabelul 3

3. Construiți FP Tree

1. Având în vedere nodul rădăcină nul.
2. Prima scanare a tranzacției T1: I1, I2, I3 conține trei elemente {I1: 1}, {I2: 1}, {I3: 1}, unde I2 este legat ca un copil la rădăcină, I1 este legat de I2 și I3 este legat de I1.
3. T2: I2, I3, I4 conține I2, I3 și I4, unde I2 este legat de rădăcină, I3 este legat de I2 și I4 este legat de I3. Dar această ramură ar împărți nodul I2 la fel de comun pe cât este deja utilizat în T1.
4. Creșteți numărul de I2 cu 1 și I3 este legat ca un copil de I2, I4 este legat ca un copil de I3. Numărul este {I2: 2}, {I3: 1}, {I4: 1}.
5. T3: I4, I5. În mod similar, o nouă ramură cu I5 este legată de I4 pe măsură ce se creează un copil.
6. T4: I1, I2, I4. Secvența va fi I2, I1 și I4. I2 este deja legat de nodul rădăcină, prin urmare va fi incrementat cu 1. În mod similar I1 va fi incrementat cu 1 deoarece este deja legat cu I2 în T1, astfel {I2: 3}, {I1: 2}, {I4: 1}.
7. T5: I1, I2, I3, I5. Secvența va fi I2, I1, I3 și I5. Astfel {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
8. T6: I1, I2, I3, I4. Secvența va fi I2, I1, I3 și I4. Astfel {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

4. Exploatarea arborelui FP este rezumată mai jos:

1. Elementul cel mai scăzut al nodului I5 nu este luat în considerare deoarece nu are un număr minim de suport, prin urmare este șters.
2. Următorul nod inferior este I4. I4 apare în 2 ramuri, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Prin urmare, considerând I4 ca sufix, căile de prefix vor fi {I2, I1, I3: 1}, {I2, I3: 1}. Aceasta formează baza modelului condițional.
3. Baza modelului condițional este considerată o bază de date de tranzacții, se construiește un arbore FP. Acesta va conține {I2: 2, I3: 2}, I1 nu este considerat, deoarece nu îndeplinește numărul minim de asistență.
4. Această cale va genera toate combinațiile de modele frecvente: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
5. Pentru I3, calea prefixului ar fi: {I2, I1: 3}, {I2: 1}, aceasta va genera un arbore FP cu 2 noduri: {I2: 4, I1: 3} și se generează modele frecvente: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
6. Pentru I1, calea prefixului ar fi: {I2: 4} aceasta va genera un singur nod FP-tree: {I2: 4} și se generează modele frecvente: {I2, I1: 4}.

Diagrama prezentată mai jos prezintă arborele FP condiționat asociat cu nodul condițional I3.

Avantajele algoritmului de creștere FP

1. Acest algoritm trebuie să scaneze baza de date doar de două ori în comparație cu Apriori care scanează tranzacțiile pentru fiecare iterație.
2. Împerecherea articolelor nu se face în acest algoritm și acest lucru îl face mai rapid.
3. Baza de date este stocată într-o versiune compactă în memorie.
4. Este eficient și scalabil pentru exploatarea modelelor frecvente atât lungi, cât și scurte.

Dezavantaje ale algoritmului de creștere FP

1. Arborele FP este mai greoi și mai dificil de construit decât Apriori.
2. Poate fi scump.
3. Când baza de date este mare, este posibil ca algoritmul să nu se potrivească în memoria partajată.

FP Growth vs Apriori

ECLAT

Metoda de mai sus, creșterea Apriori și FP, extrage frecvent seturi de articole folosind formatul de date orizontale. ECLAT este o metodă de extragere a unor obiecte frecvente folosind formatul de date verticale. Acesta va transforma datele în formatul orizontal al datelor în format vertical.

De exemplu,Utilizarea creșterii Apriori și FP:

ECLAT va avea formatul tabelului ca:

Această metodă va forma 2 seturi de elemente, 3 seturi de elemente, k seturi de elemente în formatul de date verticale. Acest proces cu k este mărit cu 1 până când nu se găsesc seturi de articole candidate. Unele tehnici de optimizare precum diffset sunt utilizate împreună cu Apriori.

Această metodă are un avantaj față de Apriori, deoarece nu necesită scanarea bazei de date pentru a găsi suportul k + 1 seturi de articole. Acest lucru se datorează faptului că setul de tranzacții va transporta numărul de apariții al fiecărui articol din tranzacție (suport). Blocajul vine atunci când există multe tranzacții care necesită memorie imensă și timp de calcul pentru intersectarea seturilor.

Concluzie

Algoritmul Apriori este utilizat pentru regulile de asociere minieră. Funcționează pe principiul, „subseturile ne-goale de obiecte frecvente trebuie să fie și ele frecvente”. Formează candidați k-itemset din (k-1) seturi de elemente și scanează baza de date pentru a găsi seturile de articole frecvente.

Algoritmul de creștere a modelelor frecvente este metoda de a găsi modele frecvente fără generația candidatului. Construiește un arbore FP, mai degrabă decât folosind strategia de generare și testare a Apriori. Accentul algoritmului FP Growth este pe fragmentarea căilor articolelor și exploatarea tiparelor frecvente.

cum se adaugă elemente într-o matrice Java

Sperăm că aceste tutoriale din seria Data Mining vă vor îmbogăți cunoștințele despre Data Mining !!

PREV Tutorial | PRIMUL Tutorial

Lectură recomandată

• Tehnici de extragere a datelor: algoritm, metode și instrumente de top pentru extragerea datelor
• Algoritmul Apriori în Data Mining: Implementare cu exemple
• Exemple de algoritmi de arborele decizional în exploatarea datelor
• Exemple de minerit de date: cele mai frecvente aplicații de minerit de date 2021
• Data Mining: Proces, tehnici și probleme majore în analiza datelor
• Procesul de extragere a datelor: modele, pași de proces și provocări implicate
• CSTE Software Testing Certificate Certification Exam Pattern Pattern
• Data Mining Vs Machine Learning Vs Intelligence Artificial Vs Deep Learning