Home » Articole » Articole » Afaceri » Știința datelor (Data Science) » Data mining » Algoritmi în învățarea automată a regulilor de asociere în mineritul datelor (data mining)

Algoritmi în învățarea automată a regulilor de asociere în mineritul datelor (data mining)

postat în: Data mining 0

Proces

Data Mining - Setul de articole frecvente(Setul de articole frecvente, unde culoarea casetei indică câte tranzacții conțin combinația de articole. Rețineți că nivelurile inferioare ale rețelei pot conține cel mult numărul minim de articole ale părinților lor; de exemplu. {ac} poate avea numai cel mult min(a, c) elemente. Aceasta se numește proprietatea de închidere în jos.)

Regulile de asociere sunt de obicei necesare pentru a satisface un suport minim specificat de utilizator și o încredere minimă specificată de utilizator în același timp. Generarea regulilor de asociere este de obicei împărțită în două etape separate:

  1. Se aplică un prag minim de asistență pentru a găsi toate seturile de articole frecvente dintr-o bază de date.
  2. O constrângere minimă de încredere se aplică acestor seturi frecvente de articole pentru a forma reguli.

În timp ce al doilea pas este simplu, primul pas necesită mai multă atenție.

Găsirea tuturor seturilor de articole frecvente într-o bază de date este dificilă, deoarece presupune căutarea tuturor seturilor de articole posibile (combinații de articole). Setul de seturi de articole posibile este setul de putere peste I și are dimensiunea 2n -1 (excluzând setul gol care nu este un set de articole valid). Deși dimensiunea setului de putere crește exponențial în numărul de elemente n în I, este posibilă căutarea eficientă folosind proprietatea de închidere în jos a suportului (numită și anti-monotonitate) care garantează că pentru un set de articole frecvente, toate subseturile sale sunt de asemenea, frecvente și, prin urmare, pentru un set de articole rar, toate super-seturile sale trebuie să fie, de asemenea, rare. Exploatând această proprietate, algoritmii eficienți (de exemplu, Apriori și Eclat) pot găsi toate seturile de articole frecvente.

Istorie

Conceptul de reguli de asociere a fost popularizat în special datorită articolului din 1993 al lui Agrawal și colab., care a obținut peste 18.000 de citări conform lui Google Scholar, în august 2015, și este, prin urmare, una dintre cele mai citate lucrări din domeniul mineritului de date. Cu toate acestea, este posibil ca ceea ce se numește acum „reguli de asociere” să fie similar cu ceea ce apare în lucrarea din 1966 despre GUHA, o metodă generală de extragere a datelor dezvoltată de Petr Hajek și colab.

O utilizare timpurie (circa 1989) a suportului minim și a încrederii pentru a găsi toate regulile de asociere este cadrul de modelare bazată pe caracteristici, care a găsit toate regulile cu supp(X) și conf(X Y) mai mari decât constrângerile definite de utilizator.

Măsuri alternative de interes

Pe lângă încredere, au fost propuse și alte măsuri de interes pentru reguli. Câteva măsuri populare sunt:

  • Toată încrederea
  • Puterea colectivă
  • Convingerea
  • Pârghia
  • Creșterea (numit inițial dobândă)

Mai multe măsuri sunt prezentate și comparate de Tan și colab. și de Hahsler. Căutarea tehnicilor care să modeleze ceea ce a cunoscut utilizatorul (și folosirea acestor modele ca măsuri de interes) este în prezent o tendință de cercetare activă sub numele de „Interesantitate subiectivă”.

Asociații statistice solide

O limitare a abordării standard de a descoperi asocieri este că, prin căutarea unui număr masiv de asocieri posibile pentru a căuta colecții de articole care par a fi asociate, există un risc mare de a găsi multe asocieri false. Acestea sunt colecții de elemente care apar concomitent cu o frecvență neașteptată în date, dar o fac doar întâmplător. De exemplu, să presupunem că luăm în considerare o colecție de 10.000 de articole și căutăm reguli care conțin două articole în partea stângă și 1 articol în partea dreaptă. Există aproximativ 1.000.000.000.000 de astfel de reguli. Dacă aplicăm un test statistic pentru independență cu un nivel de semnificație de 0,05 înseamnă că există doar 5% șanse de a accepta o regulă dacă nu există asociere. Dacă presupunem că nu există asociații, ar trebui să ne așteptăm totuși să găsim 50.000.000.000 de reguli. Descoperirea statistică a asocierilor controlează acest risc, în majoritatea cazurilor reducând riscul de a găsi asocieri false la un nivel de semnificație specificat de utilizator.

Algoritmi

De-a lungul timpului au fost prezentați mulți algoritmi pentru generarea regulilor de asociere.

Unii algoritmi bine cunoscuți sunt Apriori, Eclat și FP-Growth, dar fac doar jumătate din treabă, deoarece sunt algoritmi pentru extragerea de elemente frecvente. Un alt pas trebuie făcut după generarea regulilor din seturile de articole frecvente găsite într-o bază de date.

Algoritmul Apriori

Apriori folosește o strategie de căutare pe lățime mai întâi pentru a număra suportul seturilor de articole și utilizează o funcție de generare a candidatului care exploatează proprietatea de închidere descendentă a suportului.

Algoritmul Eclat

Eclat (alt. ECLAT, înseamnă Equivalence Class Transformation) este un algoritm de căutare în profunzime care utilizează intersecția setată. Este un algoritm natural elegant, potrivit atât pentru execuție secvențială, cât și pentru execuție paralelă, cu proprietăți de îmbunătățire a localizării. A fost introdus pentru prima dată de Zaki, Parthasarathy, Li și Ogihara într-o serie de lucrări scrise în 1997:

  • Mohammed Javeed Zaki, Srinivasan Parthasarathy, M. Ogihara, Wei Li: New Algorithms for Fast Discovery of Association Rules. KDD 1997.
  • Mohammed Javeed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Wei Li: Parallel Algorithms for Discovery of Association Rules. Data Min. Knowl. Discov. 1(4): 343-373 (1997)

Algoritmul de creștere FP

FP înseamnă tipar frecvent (frequent pattern).

În prima trecere, algoritmul contorizează apariția elementelor (perechile atribut-valoare) din setul de date și le stochează în „tabelul antetului”. În a doua trecere, construiește structura arborelui FP prin inserarea instanțelor. Elementele din fiecare instanță trebuie să fie sortate în ordinea descrescătoare a frecvenței lor în setul de date, astfel încât arborele să poată fi procesat rapid. Elementele din fiecare caz care nu îndeplinesc pragul minim de acoperire sunt eliminate. Dacă multe cazuri au cele mai frecvente elemente în comun, arborele FP oferă o compresie ridicată aproape de rădăcina arborelui.

Procesarea recursivă a acestei versiuni comprimate a setului de date principal crește direct seturi mari de articole, în loc să genereze elemente candidate și să le testeze pe întreaga bază de date. Creșterea începe din partea de jos a tabelului antet (având cele mai lungi ramuri), prin găsirea tuturor instanțelor care se potrivesc condiției date. Este creat un nou arbore, cu numărătoare proiectate din arborele inițial corespunzătoare setului de instanțe care sunt condiționate de atribut, fiecare nod primind suma numerelor fii. Creșterea recursivă se încheie atunci când niciun element individual condiționat de atribut nu mai atinge pragul minim de suport, iar procesarea continuă pentru elementele de antet rămase ale arborelui FP original.

Odată ce procesul recursiv s-a încheiat, toate seturile mari de articole cu acoperire minimă au fost găsite și începe crearea regulilor de asociere.

Alți algoritmi

AprioriDP

AprioriDP utilizează programarea dinamică în extragerea frecventă a seturilor de articole. Principiul de funcționare este eliminarea generației candidate, cum ar fi arborele FP, dar stochează numărul de suport într-o structură de date specializată în loc de arbore.

Algoritmul de minerit cu reguli de asociere bazată pe context

CBPNARM (Context Based Association Rule Mining Algorithm) este algoritmul dezvoltat în 2013 pentru a aplica regulile de asociere miniere pe baza contextului. Folosește o variabilă de context pe baza căreia suportul unui set de articole este modificat pe baza căreia regulile sunt în cele din urmă populate în setul de reguli.

Algoritmi bazați pe seturi de noduri

FIN, PrePost și PPV sunt trei algoritmi bazați pe seturi de noduri. Ei folosesc noduri într-un arbore FP de codare pentru a reprezenta seturile de articole și folosesc o strategie de căutare în profunzime pentru a descoperi seturi de articole frecvente folosind „intersecția” seturilor de noduri.

Procedura GUHA ASOC

GUHA este o metodă generală de analiză exploratorie a datelor care are fundamente teoretice în calculul observațional.

Procedura ASSOC este o metodă GUHA care analizează regulile de asociere generalizate folosind operații rapide cu șiruri de biți. Regulile de asociere extrase de această metodă sunt mai generale decât cele produse de Apriori, de exemplu, „articolele” pot fi conectate atât cu conjuncții, cât și cu disjuncții, iar relația dintre antecedent și consecință a regulii nu se limitează la stabilirea unui suport și încredere minime, ca în Apriori: poate fi utilizată o combinație arbitrară de măsuri de interes susținut.

Căutare OPUS

OPUS este un algoritm eficient pentru descoperirea regulilor care, spre deosebire de majoritatea alternativelor, nu necesită constrângeri monotone sau antimonotone, cum ar fi suportul minim. Folosit inițial pentru a găsi reguli pentru un rezultat fix, a fost ulterior extins pentru a găsi reguli cu orice element ca o consecință. Căutarea OPUS este tehnologia de bază în popularul sistem de descoperire a asociației Magnum Opus.

Lore

O poveste faimoasă despre minerit cu reguli de asociere este povestea „berei și scutecului”. Un presupus sondaj privind comportamentul cumpărătorilor din supermarketuri a descoperit că clienții (presumabil bărbați tineri) care cumpără scutece tind să cumpere și bere. Această anecdotă a devenit populară ca exemplu al modului în care regulile de asociere neașteptate pot fi găsite din datele de zi cu zi. Există opinii diferite cu privire la cât de adevărată este povestea. Daniel Powers spune:

”În 1992, Thomas Blischok, managerul unui grup de consultanță de retail la Teradata, și personalul său au pregătit o analiză a 1,2 milioane de coșuri de piață de la aproximativ 25 de magazine Osco Drug. Au fost dezvoltate interogări de baze de date pentru a identifica afinitățile. Analiza „a descoperit că între orele 17:00 și 19:00 consumatorii cumpărau bere și scutece”. Managerii Osco NU au exploatat relația bere și scutece prin apropierea produselor pe rafturi.”

Alte tipuri de minerit a asocierilor

Reguli de asociere cu relații multiple: Reguli de asociere cu relații multiple (MRAR) este o nouă clasă de reguli de asociere care, spre deosebire de regulile de asociere primitive, simple și chiar multi-relaționale (care sunt de obicei extrase din baze de date multi-relaționale), fiecare element de regulă constă dintr-o entitate dar mai multe relații. Aceste relații indică relații indirecte între entități. Luați în considerare următorul MRAR în care primul element constă din trei relații locuința, vecinătatea și umiditatea: „Cei care locuiesc într-un loc care este în apropierea unui oraș cu tip de climă umedă și, de asemenea, au mai puțin de 20 de ani -> starea lor de sănătate este bună” . Astfel de reguli de asociere pot fi extrase din datele RDBMS sau din datele web semantice.

Regulile de asociere bazate pe context este o formă de regulă de asociere. Regulile de asociere bazate pe context pretind mai multă acuratețe în analizarea regulilor de asociere, luând în considerare o variabilă ascunsă numită variabilă de context care modifică setul final de reguli de asociere în funcție de valoarea variabilelor de context. De exemplu, orientarea coșurilor în analiza coșului de piață reflectă un model ciudat în primele zile ale lunii. Acest lucru se poate datora unui context anormal, adică salariul este luat la începutul lunii.

Învățarea setului de contrast este o formă de învățare asociativă. Cursanții cu set de contrast folosesc reguli care diferă semnificativ în distribuția lor între subseturi.

Învățarea la clasă ponderată este o altă formă de învățare asociativă în care ponderea poate fi atribuită claselor pentru a se concentra pe o anumită problemă de interes pentru consumatorul rezultatelor mineritului de date.

Descoperirea modelelor de ordin înalt facilitează capturarea de modele de ordin înalt (politetice) sau asocieri de evenimente care sunt intrinseci datelor complexe din lumea reală.

Descoperirea modelului K-optimal oferă o alternativă la abordarea standard a învățării regulilor de asociere care necesită ca fiecare model să apară frecvent în date.

Mineritul setului de articole frecvente aproximat este o versiune relaxată a mineritului setului de articole frecvente care permite ca unele dintre elementele din unele rânduri să fie 0.

Taxonomie ierarhică a regulilor de asociere generalizate (ierarhie conceptuală)

Reguli de asociere cantitativă, date categorice și cantitative

Reguli de asociere a datelor cu intervale, de ex. împărțiți vârsta în reguli de asociere maxime cu intervale de 5 ani

Mineritul secvențial al modelelor descoperă subsecvențele care sunt comune pentru mai mult decât secvențele minsup într-o bază de date de secvențe, unde minsup este setat de utilizator. O secvență este o listă ordonată de tranzacții.

Reguli secvențiale care descoperă relațiile dintre articole, luând în considerare ordinea în timp. Se aplică în general pe o bază de date de secvențe. De exemplu, o regulă secvențială găsită în baza de date cu secvențe de tranzacții ale clienților poate fi aceea că clienții care au cumpărat un computer și CD-Rom-uri, au cumpărat ulterior o cameră web, cu o anumită încredere și suport.

Clusteringul subspațial, un tip specific de clustering de date cu dimensiuni înalte, se bazează, în multe variante, și pe proprietatea de închidere descendentă pentru anumite modele de clustering.

Warmr este livrat ca parte a suitei de extragere a datelor ACE. Permite învățarea regulilor de asociere pentru reguli relaționale de ordinul întâi.

Minimizarea așteptată a entropiei flotante descoperă simultan relațiile dintre nodurile (denumite elemente aici) ale unui sistem și, de asemenea, între diferitele stări în care se pot afla nodurile. Teoria leagă asocierile inerente sistemelor, precum creierul, de asocierile prezente în percepție.

Referințe

  • Hâjek, Petr; Feglar, Tomas; Rauch, Jan; and Coufal, David; The GUHA method, data preprocessing and mining, Database Support for Data Mining Applications, Springer, 2004, ISBN 978-3-540-22479-2
  • Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). “Chapter 6. Association Analysis: Basic Concepts and Algorithms” (PDF). Introduction to Data Mining. Addison-Wesley. ISBN 0-321-32136-7.

Sursa: Drew Bentley, Business Intelligence and Analytics. © 2017 Library Press, Licență CC BY-SA 4.0. Traducere și adaptare: Nicolae Sfetcu

Introducere în Business Intelligence
Introducere în Business Intelligence

O resursă esențială pentru toți cei interesați de analiza datelor și de optimizarea proceselor de afaceri.

Nu a fost votat 14.32 lei25.71 lei Selectează opțiunile Acest produs are mai multe variații. Opțiunile pot fi alese în pagina produsului.
Statistica pentru afaceri
Statistica pentru afaceri

Instrumentul esențial pentru decizii inteligente în mediul de afaceri!

Nu a fost votat 19.11 lei40.94 lei Selectează opțiunile Acest produs are mai multe variații. Opțiunile pot fi alese în pagina produsului.
Tehnologia Blockchain - Bitcoin
Tehnologia Blockchain – Bitcoin

Transformă-ți perspectiva asupra tehnologiei blockchain și începe să descoperi oportunitățile digitale de mâine!

Nu a fost votat 23.89 lei57.41 lei Selectează opțiunile Acest produs are mai multe variații. Opțiunile pot fi alese în pagina produsului.

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *