Rezumat Data Mining PDF

Ce este Data Mining? Avantaje. Depozit de date(Data Warehouses) *Data mining* se referă la extragerea cunoștințelor din cantități mari de date. Este considerat un sinonim pentru Knowledge Discovery from Data (KDD) și include pași iterativi precum curățirea datelor, integrarea, transformarea, selec...

Ce este Data Mining? Avantaje. Depozit de date(Data Warehouses) *Data mining* se referă la extragerea cunoștințelor din cantități mari de date. Este considerat un sinonim pentru Knowledge Discovery from Data (KDD) și include pași iterativi precum curățirea datelor, integrarea, transformarea, selectarea, minarea, evaluarea pattern-urilor și prezentarea cunoștințelor. Scopul principal este de a găsi un set mic de informații valoroase dintr-o cantitate mare de materie primă. Data mining are ca *avantaje* furnizarea de cunoștințe noi din datele existente, cum ar fi cele din baze de date publice, surse guvernamentale și baze de date ale companiilor. Aceste date pot fi folosite pentru a îmbunătăți serviciile și producția, precum și pentru a îmbunătăți procesul de extragere de cunoștințe. *Pasi:* A. **Preprocesarea datelor**, unde se pregatesc datele pentru minerit. Acest pas interactioneaza cu utilizatorul sau cu o baza de cunostinte. Include: *Curățirea datelor*- pentru a elimina zgomotul și datele inconsistente *Integrarea datelor*- unde mai multe surse de date pot fi combinate; aici se creeaza data warehouses(depozite de date), responsabile pentru aducerea datelor relevante pe baza cererii de data mining a utilizatorului; scopul este de a memora datele pe termen lung si de a le organiza intr-o maniera care sa faciliteze managementul decisional *Transformarea datelor*- unde datele sunt transformate sau consolidate în forme adecvate pentru minare prin realizarea de operațiuni de sumarizare sau agregare *Selectarea datelor*- unde datele relevante pentru sarcina de analiză sunt extrase din baza de date B. **Analiza datelor (Data mining)**- un proces esențial în care sunt aplicate metode inteligente pentru a extrage pattern-uri din date; consta dintr-un set de module functionale: asocierea si analiza corelatiilor, clasificare, clustering, analiza erorilor si analiza evolutiei in timp C. **Evaluarea modelelor** pentru a identifica pattern-urile cu adevărat interesante care reprezintă cunoștințe pe baza unor măsuri de interes(suportul, increderea, acuratetea, precizia, recall, etc) D. **Prezentarea modelelor/cunoștințelor** unde tehnicile de vizualizare și reprezentare a cunoștințelor sunt utilizate pentru a prezenta cunoștințele minate utilizatorului; Un *data warehouse(DW)* este un depozit centralizat de date integrat, structurat pentru interogare și analiză, mai degrabă decât pentru procesarea tranzacțiilor. Acesta stochează date din diferite surse, creând o bază coerentă pentru raportare și analiză. *Caracteristici:* - **Orientat pe subiecte**: Organizează datele pe subiecte precum vânzări, clienți, produse etc., pentru a sprijini procesul decizional. - **Integrat**: Integrează date din diverse surse într-o structură uniformă. - **Nevolatil**: Datele sunt stabile și nu se modifică odată ce sunt încărcate în data warehouse. - **Variabil în timp**: Păstrează date istorice pentru a permite analizele pe termen lung. *Diferente BD versus DW:* - **Scop**: BD sunt optimizate pentru operațiuni de tip tranzacțional (OLTP= online transaction processing) și gestionarea datelor curente, în timp ce DW sunt optimizate pentru analiza datelor (OLAP=online analytical processing) și suport decizional. - **Structura Datelor**: BD au o structură normalizată pentru a minimiza redundanța și a asigura integritatea datelor, pe când DW utilizează denormalizarea pentru a optimiza performanța interogărilor complexe. - **Tipul de Date**: BD conțin date curente și operaționale, în timp ce DW includ date istorice și agregate pentru analiză. - **ambele stochează date**, fiind utilizate pentru stocarea informațiilor. - **acces la date**, ambele permit interogarea și accesarea datelor stocate. - **integritatea datelor**: se bazează pe mecanisme de asigurare a integrității datelor, asigurându-se că datele sunt corecte și consistente. 1. *Curatirea datelor*: datele din lumea reală tind să fie incomplete, zgomotoase și inconsistente. *Metode:* - **completarea valorilor lipsa**, prin ignorarea tuplelor(folosita cand eticheta clasei lipseste, dar nu este eficienta daca multe attribute au valori lipsa), prin completarea cu o valoare constanta (poate duce la interpretari gresite), folosirea mediei atributului, folosirea mediei pentru aceeasi clasa, folosirea celei mai probabile valori - **tehnici de netezire a zgomotului,** prin binning (netezesc valorile datelor sortate consultand vecinatatea acestora prin medie, mediana sau margini), regresie (regresia liniara- gasirea celei mai bune linii care uneste 2 atrribute sau liniara multipla- mai mult de 2 atribute sunt implicate si datele sunt unite pe o suprafata multidimensionala) - **identificarea valorilor aberante,** prin clustering (valorile similare sunt organizate în clustere, iar valorile care nu se încadrează pot fi considerate puncte anormale) 2. *Integrarea datelor* consta in combinarea mai multor surse de date in aceeasi baza/deposit de date.Integrarea cu grija a datelor poate ajuta la reducerea si evitarea redundantelor si incosistentelor in setul de date rezultat. 3. *Transformarea datelor* consta in reprezentarea sau consolidarea datelor intr-o forma convenabila pt procesul current de minerit al datelor. Procesul implica urmatoarele rutine: netezire ( se foloseste pt eliminarea zgomotului din date), agregare (operatii de sumarizare sau agregare applicate pe date), generalizare(unde primitivele de date de nivel jos sunt inlocuite cu primitive de nivel inalt), discretizare (valorile numerice continue sunt inlocuite cu valori discrete), normalizare (se aplica o scalare intr-un anumit domeniu pentru fiecare atribut in parte). - **Normalizarea binara**- valoarea unui atribut este inlocuita cu valoarea 0 daca inregistrarea respectiva nu contine atrributul respectiv sau 1 daca inregistrarea curenta contine atributul fara a contine cont de valoarea lui. - **Normalizare min-max** presupune cunoasterea valorilor minime si maxime ale atributului. - **Normalizarea z-mediu** presupune ca atributul A este normalizat in baza unei medii si a unei deviatii standard formula *Normalizeaza atributul pe linie* - **Normalizare nominala** -- valoarea unui atribut A se trece in intervalul \[0,1\] in functie de valorile acelui atribut din toate inregistrarile - **Normalizare suma 1** - **Normalizare logaritmica** - **Normalizare ITF** - **Normalizare TF** 4. *Selectia datelor* : agregarea cubului de date ( mai multe attribute sunt reunite si se construieste un nou atribut reprezentativ), selectia unui subset de attribute( atributele irelevante sau redundante sunt detectate si eliminate ), reducerea dimensiunii/comprimarea datelor ( mecanisme de codificare sunt utilizate pentru a reduce dimensiunea setului de date ), discretizarea si generarea conceptului ierarhic ( valorile unui atribut sunt inlocuite prin domenii sau concepte de nivel superior ), reducerea numeroasa/drastica ( datele sunt înlocuite sau estimate cu alte date de dimensiune mult mai mica) *Selectia unui subset de attribute:* - **Metode wrapper**: utilizeaza un model pt a determina calitatea unui subset de attribute/exemple - **Metode de filtrare:** utilizează o altă metodă pentru a calcula un scor pentru fiecare atribut; este mai rapid decât metodele de tip wrapper; castig informational - **Metode Embedded:** algoritmi de învățare care pe parcursul învățării reduc din numărul de exemple *Entropia si castigul informational :* **Entropy Based Discretization** este o măsură care caracterizează (im)puritatea unei colecţii arbitrare de eşantioane (vectori de antrenament, documente), fiind o măsură a omogenităţii setului de date; entropia unui set S relativ la clasificarea eşantioanelor este: formula Pentru o colecţie S de n eşantioane grupate în c clase, pi reprezintă procentul de elemente din S care aparţin clasei i. Entropia este 0 când toate eşantioanele aparţin aceleaşi clase şi este maximă când eşantioanele sunt egal distribuite în clase. **Câştigul informaţional** reprezintă reducerea în entropie, cauzată de gruparea eşantioanelor în acord cu un anumit atribut. Câştigul informaţional se calculează astfel: formula unde Values(A) reprezintă mulţimea de valori posibile pentru atributul A şi Sv este submulţimea din S pentru care atributul A are valoarea v. Gain întoarce valori în domeniul \[0,Entropy(S)\]. Mineritul regulilor de asociere Este un proces prin care se identifică asocieri sau dependențe interesante și corelate în seturi mari de date. Aceste asocieri sunt reprezentate de item-uri (articole), sub-secvențe sau structuri care apar frecvent în setul de date, denumite item-seturi (seturi de articole). *Pași:* - **Găsirea tuturor item-seturilor frecvente**: se identifică toate seturile de articole care apar frecvent în date. Fiecare dintre aceste item-seturi trebuie să apară de cel puțin un număr minim de ori, definit de un prag de suport minim. - **Generarea regulilor de asociere puternice**: După identificarea item-seturilor frecvente, se generează reguli de asociere puternice de forma A =\> B, unde A și B sunt item-seturi. Aceste reguli trebuie să satisfacă atât criteriul de suport minim cât și criteriul de încredere minima. Algoritmul Apriori Este utilizat pentru mineritul regulilor de asociere și identificarea item seturilor frecvente în seturi mari de date. *Pașii principali* ai algoritmului sunt următorii: - Generarea de Candidat pentru 1-itemseturi (C1): la prima iterație, fiecare item individual din setul de date este considerat un candidat pentru 1-itemseturi. - Determinarea 1-itemseturilor Frecvente (L1):se numără aparițiile fiecărui item în setul de date si se identifică item-seturile care satisfac pragul minim de suport și acestea sunt incluse în L1. - Generarea Candiaților pentru k-itemseturi (Ck): pe baza item-seturilor frecvente de la iterația anterioară (Lk-1), se generează candidați pentru k-itemseturi, se elimină candidații care nu satisfac condiția că toate subseturile lor de k-1 itemuri sunt frecvente. - Determinarea k-itemseturilor Frecvente (Lk):se numără aparițiile fiecărui item-set candidat în setul de date si se identifică item-seturile frecvente care satisfac pragul minim de suport și acestea sunt incluse în Lk. - Repetarea Procesului: pașii 3 și 4 sunt repetați pentru generațiile următoare de k-itemseturi (k+1, k+2, etc.) până când nu mai există candidați frecvenți. - Generarea Regulilor de Asociere Puternice: din item-seturile frecvente identificate, se generează reguli de asociere de forma A =\> B. Aceste reguli trebuie să satisfacă atât pragul minim de suport cât și pragul minim de încredere. *Măsurarea Gradului de Interes*: pentru a selecta modelele de reguli de asociere considerate interesante, se folosesc următoarele măsuri: - **Simplitatea**: Gradul de ușurință în interpretarea regulilor. - **încrederea:** Nivelul de încredere în validitatea regulii. formula - **suportul:** Frecvența cu care regula apare în setul de date. *Îmbunătățirea eficienței algoritmului Apriori* prin: - **Tabele Hash**: pentru generarea mulțimilor de 2-itemseturi în paralel cu cele de 1-itemset. - **Reducerea Tranzacțiilor**: Eliminarea tranzacțiilor care nu conțin item-seturi frecvente la nivelul curent. - **Partiționare**: Împărțirea tranzacțiilor din baza de date în părți nesuprapuse și găsirea item-seturilor frecvente din fiecare parte. - **Eșantionare**: Utilizarea eșantioanelor pentru a reduce volumul de date procesate. - **Numărarea Dinamică a Item-setului**: Adăugarea item-seturilor candidate pe parcursul scanării bazei de date. Algoritmul FP-Growth Algoritmul FP-Growth **(Frequent Pattern Growth**) utilizează strategia „divide-and-conquer". *Pașii* algoritmului sunt: - Scanează baza de date pentru a genera mulţimea de 1-itemseturi frecvente - Se stabileşte pragul de suport minim şi se elimină item-urile care nu respecta pragul (L1) - Mulţimea de item-uri este ordonată descrescător după contorul fiecăruia - Se creează arborele de frecvente astfel: se creează un nod rădăcină în arbore etichetat cu „null"; scanăm baza de date încă o data luând fiecare tranzacţie pe rând. Itemu-rile din fiecare tranzacţie sunt sortate după ordinea în care ele apar în mulţimea L1 şi o ramură în arbore este creată pentru fiecare tranzacţie. Dacă există noduri comune pe o cale, acelea nu se introduc în arbore dar se incrementează contorul corespunzător nodului comun urmând să se adauge doar nodurile ne-comune existente pe acea cale - Pattern-urile sunt extrase din FP-tree luând item-urile în ordine inversă faţă de cum apar în L1 şi extragem fiecare cale mergând de la acel item până la rădăcină. Item-urile sunt contorizate în funcţie de ramurile pe care pornesc din nodul rădăcină. Nu se vor însuma contoarele a două item-uri identice care se găsesc în FP-tree pe ramuri diferite plecând din nodul rădăcină. Mineritul pattern-urilor frecvente Implică identificarea regulilor de asociere prin diverse metode și algoritmi. *Clasificarea* acestor algoritmi de extragere a regulilor de asociere poate fi realizată pe baza următoarelor criterii: - **După numărul de dimensiuni al datelor implicate în regulă:** reguli unidimensionale (implică asocieri între item-uri dintr-o singură dimensiune), reguli de asociere multidimensionale (implică asocieri între item-uri din mai multe dimensiuni) - **După nivelul de abstractizare implicat în setul de reguli:** extragere reguli pe un singur nivel de abstractizare (generate la un singur nivel de detaliu), extragere reguli la diferite nivele de abstractizare ( extrase la multiple nivele de abstractizare, permițând o analiză detaliată și complexă a datelor) - **După tipul de valori cu care se lucrează în regulă**: regulă de asociere booleană (implică asocierea între prezența sau absența item-urilor), regulă de asociere cantitativă (implică asocieri între item-uri sau atribute cantitative). Analiza datelor *Metode de invatare:* - **Invatare supervizata**: Această metodă implică utilizarea unor exemple de antrenament care sunt organizate sub forma de perechi intrare-ieșire (X, Y). Scopul este de a construi un model care să poată prezice ieșirea dorită Y pe baza datelor de intrare X.Exemple: clasificarea și predicția. - **Invatare nesupervizata**: În această metodă, exemplele de antrenament conțin doar datele de intrare (X), fără a specifica ieșirea dorită. Algoritmul învață singur să grupeze datele în funcție de similarități, un proces cunoscut sub numele de clustering (grupare). Ex: clustering. *Modul de invatare:* - **Învățare On-line**: schema de clasificare sau clustering este actualizată continuu, după prezentarea fiecărui exemplu de antrenament. - **Învățare Off-line**: pentru fiecare exemplu de antrenament, se determină modificarea ce trebuie adusă schemei de clasificare. Aceste modificări sunt însumate și aplicate schemei de clasificare numai după ce toate datele de antrenament au fost prezentate. - **Antrenare**: selectarea exemplelor de antrenament (alegerea datelor care vor fi folosite pentru a antrena modelul).Analizarea exemplelor de antrenament pentru a obține schema de clasificare sau clustering. - **Testare**: selectarea setului de test (alegerea datelor care vor fi folosite pentru a evalua performanța modelului (setul de test trebuie să fie diferit de setul de antrenament)).Rafinarea schemei de clasificare printr-un proces de testare: Ajustarea modelului pe baza performanței observate în timpul testării. - **Regula 70-30**: setul de date este împărțit astfel încât 70% din date sunt folosite pentru antrenare și 30% pentru testare. - **10-Crossvalidation**: setul de date este împărțit în 10 subseturi. Modelul este antrenat de 10 ori, de fiecare dată folosind un subset diferit pentru testare și restul pentru antrenare.Aceasta metodă ajută la evaluarea mai precisă a performanței modelului. Evaluarea algoritmilor de invatare *Masuri externe:* - **Acuratetea**: procentul de elemente corect clasificate intr-un set de date - **Precizia**: raportul de răspunsuri corecte din totalul răspunsurilor propuse pentru un anumit subiect. - **Recall**: raportul de răspunsuri corecte și numărul total de răspunsuri așteptate pentru un anumit subiect. - **F-measure**: combină precizia și recall-ul folosind media armonică - **True negative rate (TNR)** - **Entropia**: indica omogenitatea unui cluster *Masuri interne:* - **Compactness**: măsoară cât de compacte sunt elementele dintr-un cluster, unde c reprezintă centrul clusterului (centroidul) și xi reprezintă elementele din interiorul clusterului. - **Separability**: măsoară disimilaritatea dintre clustere, indicând cât de distincte sunt clusterele unele față de altele. - **Balance**: măsoară cât de echilibrate sunt clusterele create, indicând distribuția uniformă a elementelor între clustere. Algoritmi de clasificare *Clasificarea* este procesul prin care se atribuie unui exemplu una sau mai multe etichete (clase) dintr-o mulțime de etichete existente. Clasificarea se realizează prin învățare supervizată, care implică *două etape principale:* - **Pasul de invatare**: se construiește clasificatorul pe baza unui set predefinit de date sau concepte. Aceasta este etapa de învățare sau antrenare, în care se extrag regulile sau modelele de clasificare. - **Pasul de clasificare**: Modelele elaborate în prima etapă sunt utilizate pentru clasificarea exemplelor noi. *Tipuri de algoritmi de clasificare:* - **Metode bazate pe asocieri:** K-nearest neighbor (KNN) (clasifică un exemplu nou pe baza celor mai apropiate K exemple din setul de antrenament) - **Metode bazate pe reguli**: Reguli de tip if-then-else - **Arbori de decizie**: Construiesc un model sub formă de arbore, unde fiecare nod intern reprezintă un test pe un atribut, fiecare ramură reprezintă un rezultat al testului, iar fiecare nod terminal reprezintă o clasă. - **Metode Stohastice**: Rețele Bayesiene - **Metode bazate pe nuclee**: Support Vector Machine (SVM) - **Metode bazate pe retele neuronale**: BackPropagation - **Metode evolutioniste**: algoritmi genetici *Clasificatorul k-nearest neighbor(KNN):* se bazează pe învățarea prin analogie. Aceasta presupune compararea unui exemplu de test cu un set de exemple de antrenament similare pentru a determina clasa sa. Fiecare exemplu este reprezentat ca un punct într-un spațiu n-dimensional, unde fiecare dimensiune corespunde unui atribut din setul de date. Astfel, setul de exemple de antrenament este caracterizat de n atribute. Se calculeaza distanta dintre exemplul de test si toate ex din setu de antrenament. Se selecteaza k cei mai apropiati vecini si se voteaza pentru clasa. *Clasificatorul Rocchio*: utilizează centroizi pentru a defini granițele de separare între clase. Centroidul reprezintă \"centrul de greutate\" al membrilor din aceeași clasă. Centroidul unei clase cc este calculat după formula: Granița dintre două clase este setul de puncte care se află la distanță egală între doi centroizi, reprezentată de o linie sau un hyperplan. Pentru a clasifica un punct nou, se verifică zona în care acesta se găsește în raport cu centroizii. Un nou exemplu este asignat clasei celui mai apropiat centroid. *Clasificatorul pe baza arborilor de decizie:* arborii de decizie sunt modele ierarhice utilizate în învățarea automată pentru clasificare. Un arbore de decizie este un graf aciclic direcționat care funcționează ca un clasificator. *Structura:* - Fiecare nod intern reprezintă un test al unui atribut. - Fiecare ramură reprezintă ieșirea testului. - Nodurile frunză reprezintă clase sau distribuții de clase. - Nodul din vârf este nodul rădăcină. - Fiecare nod frunză are asociată o etichetă, care este clasa corespunzătoare clasificării efectuate de calea de la rădăcină până la nodul frunză. - Faza de creștere: Din setul de date de antrenament se construiește un arbore de decizie cuprinzător, de dimensiune mare. - Faza de tăiere (pruning): Se determină dimensiunea finală a arborelui astfel încât rata clasificărilor greșite să fie minimă. - Abordare top-down. - Metrici pentru evaluarea atributelor: Câștigul informațional, mutual information etc. - Se pornește de la un set de date de antrenament D cu m exemple și A atribute grupate în C clase. - Dacă toate cazurile din D aparțin aceleiași clase, se obține un nod frunză etichetat cu numele clasei. - Se selectează atributul care organizează cel mai bine setul de date, pe baza unei metode de separare. - Setul de date D se împarte în n subseturi în funcție de numărul de valori distincte ale atributului selectat. - Dacă nu mai există atribute de test, se creează un nod frunză etichetat cu clasa cea mai probabilă. - Se procesează recursiv fiecare subset generat până când pe toate ramurile se ajunge la un nod frunză. Clustering Este un tip de învățare nesupervizată care implică gruparea automată a unui set de date în submulțimi (clustere) pe baza similarităților sau disimilarităților dintre ele. Un cluster este o colecție de obiecte similare între ele și diferite de obiectele din alte clustere. Fiecare cluster trebuie să conțină cel puțin un element, iar fiecare element trebuie să fie inclus doar într-un singur cluster. *Cerinte:* - **Scalabilitate**: Capacitatea de a lucra cu volume mari de date. - **Dimensionalitate**: Capacitatea de a lucra cu date multidimensionale. - **Adaptabilitate:** Utilizarea diferitelor tipuri de atribute. - **Insensibilitate**: Independența de ordinea de preluare a datelor. - **Abilitate**: Capacitatea de a lucra cu date care conțin zgomot. - **Parametrii** **de Intrare**: Posibilitatea de a stabili parametrii de intrare pe baza cunoștințelor de domeniu. - **Parametrii** **de Ieșire**: Posibilitatea de a forma clustere de formă arbitrară. - **Configurare**: Posibilitatea de a specifica anumite constrângeri. - **Interpretabilitate**: Utilitatea rezultatelor obținute. - **Metode ierarhice**: realizeaza o structura ierarhica a setului de date; tipuri: aglomerativi (abordare bottom-up) si divizivi(abordare top-down) - **Metode partitionale** - **Metode bazate pe densitate** - **Metode bazate pe grid** - **Bazati pe modele si retele (SOM)** - **Bazati pe ordinea atributelor** - Fiecare element de la 1 la n este inițial un cluster separat. - Se calculează matricea de similaritate 𝐷 pentru toate perechile de elemente. - Se determină perechea de clustere cele mai similare (𝑟,). Dacă similaritatea este sub un prag prestabilit, se unește perechea într-un cluster nou. - Se actualizează matricea de similaritate prin eliminarea liniilor și coloanelor corespunzătoare lui 𝑟 și 𝑠, și se adaugă noul cluster. - Se repetă pașii 3-6 până când rămâne un singur cluster sau se atinge condiția de oprire. - **Single Link**: Distanța minimă între cele mai similare elemente din doi clustere. - **Complete Link**: Distanța maximă între cele mai disimilare elemente din doi clustere. - **Average Link:** Distanța medie între toate perechile de elemente din clustere. - **Centroid Link**: Distanța dintre centroizii celor doi clustere. - Alegerea aleatorie a k centroizi din setul de date de antrenament. - Atribuirea fiecărui element rămas la centroidul cel mai apropiat. - Calcularea centrului de greutate pentru fiecare cluster. - Mutarea centroidului în centrul de greutate calculat. - Repetarea procesului până la convergență. - Alegerea arbitrară a k elemente din D ca reprezentative inițiale și atribuirea acestora unui cluster. - Atribuirea fiecărui element rămas din D clusterului cel mai apropiat. - Selectarea aleatorie a unui element nereprezentativ. - Calcularea costului total al înlocuirii obiectului reprezentativ cu cel selectat aleatoriu. - Dacă costul este negativ, se înlocuiește obiectul reprezentativ pentru a forma noul set de k elemente reprezentative; dacă nu, nu se face nicio modificare. - Repetarea pașilor până când nu se mai fac înlocuiri.