Data miningTemă de casăRețete de Calculatoare si Internet

Ing. Olga AldeaProf. Coordonator Ștefan Stăncescu

1

Introducere (1)

Fig. 1. Etapele procesului de KDD [1]

• Descoperirea de cunoștințe din bazele de date (Kowledge Discovery in Databases – KDD) sau extragerea de date (Data Mining - DM) sunt folosite pentru a prelucra cantități mari de informații și date disponibile.

• Conform Fayyad [2] există mai multe etape în procesul de KDD (vezi Fig. 1)▫ Selectarea▫ Preprocesarea▫ Transformarea▫ Extragerea datelor▫ Interpretarea (evaluarea)

rezultatelor

2

Introducere (2)• DM folosește o varietate de algoritmi grupate în principalele

componente ale DM:▫ Modelul – reprezentat printr-o funcție în spațiu unidimensional sau

multidimensional▫ Criteriile de preferință – unele se pot baza pe ordonare, altele pe

interpolare, etc▫ Algoritmi de selecție – conduc la selectarea modelului, a datelor și a

criteriilor▫ Stabilirea abaterilor – algoritmi de determinare a deviației și stabilității

• Inițial, KDD și DM se foloseau pentru a denumi același lucru, dar în ultimul timp s-a făcut o diferențiere clară: KDD se folosește pentru a extrage informații din bazele de date, iar DM este procesul de aplicare a algoritmilor de descoperire a cunoștințelor, fiind etapă a procesului KDD.

3

Pattern-uri pentru data mining• Metodele statistice sunt cele mai apropiate metode tradiționale de analiză a

datelor față de data mining. [1]• Data mining poate folosi date din depozite de date, nu numai din baze de

date, ceea ce reprezintă un avantaj. [1]• În funcție de tipul obiectivelor propuse, se pot alege una sau mai multe

metode. [1]• După scopul funcțional, metodele data mining sunt: [1]

▫ Predictive – realizează previziuni pentru sistemul sau fenomenul studiat▫ Descriptive – descriu fenomene din sistemul studiat, pe baza modelelor

descoperite• În funcție de tipul de învățare există doup metode de data mining: [1]

▫ Metode supervizate de învățare – definirea categoriilor inițiale se face de către un agent extern (ex. metode statistice, arbori de decizie, rețele neuronale)

▫ Metode nesupervizate de invățare – nu se folosește etichetarea obiectelor (ex. Clustering, reguli de asociere)

4

Clasificarea sistemelor de data mining• Criterii de clasificare:

▫ Categoria de depozit de date ce conține informațiile cărora li se aplică procesul de DM: După modelul de date folosit la construirea depozitului, există sisteme de DM relaționale, tranzacționale,

data warehouse, obiecturale, relațional-obiecturale sau heteorgene După tipul datelor manipulate, există sisteme de DM temporale, secvențiale, text, mutimedia, pentru fluxuri

de date, pentru Web.▫ Categoria de tehnici integrate pentru îndeplinirea funcției:

Sisteme DM ce integrează o singură tehnică (ex. Caracterizarea și discriminarea datelor, clasificare și predicție, grupare și analiză excepții)

Sisteme DM ce integrează tehnici multiple pentru a descoperi categorii diferite de modele ▫ Nivelul de abstracție - sisteme DM ce extrag modele de date pe un singur nivel de abstracție sau pe

mai multe nivele de abstacție▫ Frecvența de aplicare – sisteme ce prelucrează datele regulat sau la intervale neregulate de timp▫ Modul de interacțiune – sistemele DM pot interacționa (sau nu) cu utilizatorul în timpul procesului de

extragere de date▫ Metoda de analiză – analizează datele în funcție de:

Modelul de date în jurul căruia se construiește depozitul de date Forma de analiză a datelor cărora li se aplică data mining

▫ Domeniul de aplicabilitate – sisteme DM adaptate la specificul domeniilor de activitate (finanțe, comerț, telecomunicații, e-mail etc).

5

Metode clasice de data mining (1)Cele mai cunoscute metode clasice de data mining sunt:• Metodele statistice

▫ Regresia▫ Metodele lineare generalizate▫ Arborii de regresie▫ Analiza variabilității▫ Metodele cu efect mixt▫ Analiza de factor▫ Analiza discriminantă▫ Seriile de timp▫ Analiza de supraviețuire

• Vecinii - Algoritmul celor mai apropiați k-vecini▫ Tehnica k-NN presupune că întregul set de antrenare include atât datele cât și clasificările dorite

pentru fiecare item.▫ K reprezintă numărul de cazuri similare sau numărul de articole din grup.▫ Algoritmul k-NN are doi parametri principali: [7]

numărul celor mai apropiate (similare) cazuri k o metrică pentru măsurarea similarității

▫ Algoritmul k-NN este bazat pe conceptul de distanță iar aceasta necesită o metrică pentru determinarea distanțelor.

6

Metode clasice de data mining (2)• Clustering – gruparea datelor multi-dimensioanle în clustere definite algoritmic

▫ În general, pentru a putea folosi un algoritm de clasificare, este nevoie ca mai întâi să se precizeze: [3] a) Un tip de distanță între punctele unui spațiu multidimensional. b) O strategie de alegere a punctului reprezentativ (adică a „centrului”) pentru orice grupare de puncte. Cei

mai mulți oameni au tendința de a alege media aritmetică (adică „centrul de greutate”). c) Un tip de distanță între două grupe de puncte. Cele mai folosite asemenea distanțe iau în considerare

distanța între puncte aleasă anterior;▫ Odată ce au fost efectuate alegerile, un algoritm ierarhic de clasificare va funcționa în felul următor:

[8] Pasul 1. Fiecare punct este considerat ca grupă separată (de 1 punct). Pasul 2. Cele mai apropiate două grupe sunt amalgamate într-o grupare mai mare (dendrogramă, Fig. 2). Pasul 3. Se aplica o procedură „de tăiere” asupra dendrogramei; în acest fel se identifică numărul „obiectiv”

de grupe (clusters), apoi componența fiecăreia.

Fig. 2. Exemplu de dendrogramă

7

Tehnici de noua generațiePrintre tehnicile de noua generație pentru data mining se numără: arborii,

rețelele și regulile.• Rețelele

▫ Rețelele neuronale sunt sisteme dinamice, al căror comportament poate fi caracterizat prin urmărirea stărilor la momente diferite de timp.

▫ Starea unei rețele la un moment dat este definită de ansamblul nivelurilor de activare a neuronilor și de intensitățile conexiunilor dintre neuroni.

▫ Rețelele neuronale nu operează decât direct asupra variabilelor numerice.▫ Pentru seturi de date cu număr mare de atribute, folosirea rețelelor neuronale devine nefezabilă .▫ Rețeaua odată instruită poate realiza predicții rapide pentru instanțe noi. Astfel, rețelele neuronale

sunt utilizate cu succes în probleme care necesită răspuns în timp real.▫ Rețelele neuronale nu restrictionează output-ul la un singur atribut.

• Regulile de asociere▫ Măsurile cheie în cadrul extragerii regulilor de asociere sunt suportul (la proporţia în care o relaţie

apare în date) şi încrederea (probabilitatea de a găsi un antecedent având o consecinţă).▫ Regulile de asociere se folosesc pentru a găsi mulţimile frecvente de articole în bazele de date ce

conţin tranzacţiile consumatorului, problemă cunoscută sub denumirea de analiza coşului de cumpărături (market basket analysis).

▫ În cazul analizei click-urilor se lucrează pe o bază de date cu sesiunile serverului care înregistrează solicitările utilizatorilor. Determinarea linkurilor frecvente şi a regulilor de asociere este esenţială pentru problema analizei click-urilor, modul în care utilizatorii navighează pe Internet şi accesează diverse site-uri.

8

Tehnici de noua generație (2)• Arborii de decizie

▫ Un arbore de decizie (Decision Tree) este un model de clasificare sau estimare care poate fi privit ca un arbore.

▫ Ideea de bază a algoritmilor de arbori de decizie este utilizarea unui criteriu de divizare pentru a determina cel mai predictiv factor și amplasarea lui ca prim punct de decizie în arbore și în continuare să execute o căutare de factori predictivi pentru a construi subarborii până când nu mai există date de procesat.

▫ Modelul de arbore de decizie va crea reguli asupra datelor de estimat variabila țintă.▫ Deși arborii de decizie au fost dezvoltați inițial ca instrumente exploratorii pentru rafinarea și

preprocesarea datelor pentru tehnici statistice, ei sunt din ce în ce mai mult utilizați pentru predicție .▫ Algoritmul CART (Classification And Regression Trees):

Segmentează un set de date creând subarbori binari. Măsura pe baza căreia este preferat un predictor altuia este valoarea entropiei. Este relativ robust în raport cu datele lipsă. Dacă o valoare lipsește pentru un predictor particular într-o

înregistrare particulară, la construirea arborelui acea înregistrare nu va fi utilizată în realizarea determinării ramificării optimale.

Când CART este utilizat pentru a prezice asupra unor date noi, valorile lipsă pot fi manipulate prin intermediul substitutelor (surrogates). Substitutele sunt valori de ramificare și predictori care simulează ramificarea reală din arbore și pot fi utilizate când lipsesc datele pentru predictorul dorit.

9

Tehnici de noua generație (3)•Arborii de decizie (2):

▫Algoritmul CHAID (Chi Square Automatic Interaction Detection): Segmentează setul de date creând subarbori oarecare Necesită de obicei o mai mare pregătire a datelor Este popular în cercetările de marketing în contextul

studiilor de segmentare a pieței Pașii algoritmului sunt:

Pregătirea predictorilor. Fuziunea categoriilor. Selectarea valorii de separare.

10

Concluzii• Posibilitatea de stocare a volumelor mari de date duce la nevoia de a extrage diferite informații pe

baza acestor date. Astfel, folosirea Data Mining este utilă în vederea obținerii diferitelor statistici sau previziuni într-o gamă largă de domenii.

• Fiind un domeniu relativ nou, metodele vechi de explorare a datelor (regresie, clostering) sunt înlocuite cu metode noi care sunt din ce în ce mai performante (de exemplu, arborii de decizie).

• Arborele de decizie și algoritmul care îl creează pot fi complicați, însă rezultatul poate fi prezentat într-un mod ușor de înțeles, lucru care poate fi extrem de folositor în luarea deciziilor în afaceri. Astfel arborele de decizie este situat în topul modelelor predictive. El poate fi utilizat însă, în egală măsură, și în aplicațiile de clasificare ce sunt solicitate în diverse domenii cum ar fi experimentele științifice, aprobările de credite, target marketing, store location, analizele financiare, customer segmentation, detectarea fraudelor etc.

• Se observă două elemente interesante la acest tip de arbore: • − el divide datele la fiecare punct de ramificare fără să piardă nici o dată, numărul total de

înregistrări din nodul părinte fiind egal cu suma înregistrărilor conținute în cei doi subarbori fii; • − este ușor de înțeles cum a fost construit modelul, în contrast cu alte modele

concurente cum ar fi rețele neuronale etc. • Datorită înaltului lor nivel de automatism și ușurinței de translatare a modelelor construite cu arbori

de decizie în SQL, pentru utilizarea în baze de date relaționale, tehnologia este ușor de integrat în procese IT deja existentele, necesitând puțină preprocesare și reducere a datelor, sau extragere a lor cu scop precis pentru Data Mining.

11

Bibliografie

[1] Arun K. Pujari Data mining techniques Universities Press, 2001 [2] Fayyad U.M., Piatetski-Shapiro G., Smyth P. and Uthurusamy R., Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, 1996 [3] Barbara, D. An introduction to cluster analysis for data mining

12