DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

1

1. Introducere

1.1. Definirea domeniului Data Mining

n ultimii ani a continuat creterea dimensiunii bazelor de date (curent acestea ajung la o mrime de terabytes 1,000,000,000,000 bytes de date). In interiorul acestei mase de date, pot apare informaii importante care nu sunt detectabile la o analiza obinuita. Cu alte cuvinte Exista Riscul de a nu vedea pdurea din cauza copacilor Domeniul a demarat in 1989 si a cunoscut un impuls puternic ncepnd cu 1995. Exemple Interferometrul European are 16 telescoape, fiecare dintre acestea

produce 1 Gigabit/secund de date astronomice intr-o sesiune de 25- zile de observaie, ceea ce creeaz mari probleme de stocare si analiza ;

Datele meteo furnizate de sistemul de sateliii NASA ajung la 46MB/s respectiv la 4,000,000,000,000 bytes pe zi

Baza de date a FBI ce conine amprente are 200,000,000,000,000 bytes Baze de date comerciale: France Telecom are baze de date cu informaii legate de telefonia mobila si fixa de: ~30TB; AT&T ~ 26 TB (T tera) Web Arhiva internet Alexa are: 7 ani de date, 500 TB Google dispune 4+ miliarde pagini, mai multe sute de TB Arhive IBM, 160 TB (2003) Arhiva Internet (www.archive.org),~ 300 TB UC Berkeley 2003 estimeaz c :

5 exabytes (5 milioane terabytes de noi date au fost create in 2002). US produce ~40% din noile date stocate in lume Creterea anuala a cantitii de informaie stocata este estimata la un

procent anual de aproximativ ~30% ea dublndu-se practic la 20 luni MOTIVATIE Foarte puine date pot fi analizate si integrate de operatorul uman. Datele se colecteaz uor, analiza lor este costisitoare. Exist suspiciunea c in masivele de date pot exista cunotine ascunse. Descoperirea Cunotinelor este NECESARA pentru a da sens utilizrii

datelor. Din acest motiv muli cercettori au considerat extragerea cunotinelor din baze de date ca un domeniu semnificativ de investigat.

DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

2

Denumirea de Data Mining (minarea de date, sau extragerea de date) sau Descoperirea de cunotine din baze de date (Knowledge Discovery in Data KDD), a fost adoptat pentru domeniul de cercetare avnd ca scop descoperirea de informaii sau cunotine din date coninute n una sau mai multe structuri de date (tabele de date). Sistemul de descoperire a cunotinelor (Knowledge Discovery systems) care e capabil s opereze pe o baz de date de dimensiune mare, este numit sistem de descoperire a cunotinelor din baze de date (knowledge discovery in database systems - KDD).

KDD a fost conceput n 1989 pentru a desemna o zon de cercetare bazat pe metode de Data Mining, recunoaterea formelor, nvare automat i tehnici de baze de date n contextul bazelor de date de dimensiuni mari. Prima conferin internaional pe Knowledge Discovery i Data Mining a avut loc n 1995 (KDD95). KDD/Data Mining este un domeniu interdisciplinar care dezvolt algoritmi i procese pentru descoperirea cunotinelor (categorii, tipare, concepte, relaii i tendine), construind modele i fcnd preziceri din date structurate, semi-structurate sau nestructurate. De asemenea extrage informaii de interes sau tipare din baze de date mari. Acest proces a fost formalizat de un grup industrial numit CRISP-DM, ( CRoss Industry Standard Process for Data Mining). Definiii Data Mining / KDD Activitatea de extragere a informaiei a crui scop este acela de a

descoperi aspecte necunoscute din bazele de date; Procesul de analiza a unor cantiti mari de date in scopul determinrii de

relaii care apar intre elementele prezente in bazele de date si a determinrii de machete (potenial utile) care pot caracteriza global bazele de date. (din Advances in Knowledge Discovery and Data Mining, Fayyad, Piatetsky-Shapiro, Smyth, and Uthurusamy, (Chapter 1), AAAI/MIT Press 1996.

In CONCLUZIE Data Mining este un proces care utilizeaz o varietate de unelte de analiz a datelor pentru a descoperi machete (patterns) si relaii n date, care pot fi utilizate pentru predicii valide. In ultim instan, machetele si relaiile care se determin vor defini un model al datelor in cauz. Grafic acest proces apare in figura de mai jos:

DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

3

Termenul de Data Mining apare in 1990 in comunitatea utilizatorilor bazelor de date. Iniial denumirea era de database mining , dar deoarece aceasta denumire era marc nregistrat, cercettorii s-au rentors la data mining.

Gregory Piatetsky-Shapiro introduce termenul Knowledge Discovery in Databases la primul simpozion pe aceasta tema (1989) i acesta devine cel mai popular in AI si Machine Learning Community. Astfel in Jan 2004, cutarea termenului "data mining" prin Google gsete mai mult de 2,000,000 pagini, pe cnd cutarea pentru knowledge discovery gsete numai 300,000 pagini. Dei aceti doi termeni (KDD Data Mining) au fost folosii alternativ n trecut, cercettorii din domeniu au fcut recent distincie ntre ei. Distincia pe care au fcut-o este aceea c:

descoperirea cunotinelor din baza de date (KDD) poate fi considerat ca procesul de extragere a informaiilor folositoare i interesante din baza de date. Acest proces include selectarea, pregtirea datelor, manipularea i analizarea rezultatelor.

minarea datelor (Data Mining) poate fi vzut ca aplicarea algoritmilor de descoperire a cunotinelor fr alte etape ale procesului de descoperire a cunotinelor, i este deci un subset al KDD. Prin urmare KDD este folositoare n situaiile unde volumul de date este fie foarte mare sau prea complicat pentru metodele tradiionale sau unde experi umani sunt indisponibili pentru extragerea cunotinelor. Aa cum era de ateptat, KDD a mprumutat multe de la teoriile tradiionale ale nvrii automate i de la bazele de date.

Domeniile in care tehnicile de data mining se aplic in prezent sunt:

tiin astronomie, bioinformatic, descoperire de noi medicamente, Afaceri publicitate,

modelare clieni si Managementul relaiilor cu clienii e-Commerce, detectarea fraudelor sntate, investiii, telecomunicaii, investiii,

Date Cunostinte Data Mining

DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

4

Web: maini de cutare Guvernamental

combaterea terorismului, legislaie, combaterea evaziuni fiscale

Data mining si legtura cu alte domenii Este ilustrata in figura 1.1-1. domeniul data mining aprnd la intersecia a trei mari domenii : machine learning, statistica si baze de date. Interfaa cu aceste domenii presupune utilizarea de tehnici specifice, care aparin domeniilor in cauza si care sunt particularizate pentru analiza masivelor mari de date. vs. machine learning metode de tip machine learning sunt utilizate in data mining (clasificare, grupare) vs. statistica: Scopul domeniului data mining poate fi sumarizat de forma: Ce se poate spune ceva interesant despre aceste date ? ceea ce nu reprezint nimic altceva dect statistic. In data mining se investigheaz un set de ipoteze care au un caracter statistic. Data mining reprezint o etapa intermediara in analiza statistica vs. baze de date Utilizarea obinuita a bazelor de date este te tip deductiv Descoperirea cunotinelor este inductiv Fig. 1.1-1. Legtura dintre data mining si machine learning, statistica baze de date.

DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

5

1.2. Definirea procesului de descoperire a cunotinelor Procesul de descoperire de informaii din baze de date mari cuprinde mai multe etape i este prezentat n figura Fig. 21.2-1:

(1) definirea scopului urmrit (2) interogarea surselor de date si definirea structurii datelor supuse

prelucrrii, (3) preprocesarea datelor (selectarea, curarea, transformarea

acestora), (4) minarea datelor pentru extragerea de tipare i de modele

apropiate, (5) evaluarea i interpretarea tiparelor extrase pentru a decide ce

constituie cunotin (knowledge), (6) consolidarea cunotinelor i rezolvarea conflictelor dintre

cunotinele extrase anterior, (7) oferirea cunotinelor spre utilizare.

Date surs

Integrarea

Date Integrate

Date relevante activitii

Selecia Minarea

Tipare

Evaluarea

Fig. 21.2-1. Procesul de descoperire de cunotine

Etapele procesului de descoperire de cunotine (KDD) prezentat n figura Fig. 21.2-1 constau din:

nvarea domeniului problemei, adic specificarea unor cunotine apriori relevante precum i unele scopuri ale aplicaiei.

Integrarea datelor, etap ce const n curarea datelor i preprocesarea acestora (etap ce poate lua 60% din efort).

Selectarea datelor, etap ce const n crearea unui set de date int prin reducerea datelor i transformarea acestora: gsirea caracteristicilor relevante, reducerea dimensionalitii i reprezentarea invarianilor.

DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

6

Minarea datelor, etapa const n alegerea algoritmilor de Data Mining i gsirea tiparelor de interes.

Evaluarea tiparelor i prezentarea cunotinelor, etap ce const n vizualizarea, transformarea i eliminarea tiparelor redundante precum i utilizarea cunotinelor descoperite.

1.3. Un model de Data Mining

Figura Fig. 30-1 prezint un posibil model al procesului Data Mining (minare de date). Sunt prezente mai multe etape premergtoare obinerii modelului ce urmeaz sa caracterizeze baza de date.

Fig. 30-1. Un model al procesului Data Mining

Prepararea datelor, este faza iniial care implic selectarea datelor de interes pentru descoperirea cunotinelor. Utilizatorul poate direciona sistemul KDD la zone de interes folosind abloane, unelte de vizualizare sau prin specificarea unor strategii de eantionare. Rezultatul acestei faze este

DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

7

reducerea setului de date de test i reducerea corespunztoare a spaiului de date ce urmeaz a fi supus prelucrrii in cadrul tehnicilor de data mining. Aceast faz implic de obicei multe interaciuni cu utilizatorul prin browsere i unelte de vizualizare a datelor.

Analiza datelor, este faza in care se aplica funcie de natura datelor care urmeaz a fi prelucrate (categorice, nominale sau mixte) diverse tehnici specifice statisticii matematice sau AI. In urma acestei prelucrri se obine un ablon (model) al datelor analizate.

1.4. Tipuri de cunotine descoperite

Tipul de cunotine care este descoperit din baza de date i forma sa de reprezentare variaz mult, depinznd att de zona de aplicaie ct i de tipul bazei de date.

Cunotinele nvate din seturi de date mari pot lua mai multe forme incluznd cunotine de clasificare, reguli caracteristice, reguli de asociere, relaii funcionale, dependine funcionale i reguli cauzale. n tabelul Tabel1.4-1 sunt indicate tipurile de cunotine care sunt suportate explicit de ctre o selecie de unelte de Data Mining curente. Scopul acestei vederi de ansamblu este de a demonstra marea diversitate a uneltelor de DM i nu aceea de a forma o baz a unor comparri sau evaluri a uneltelor.

Sisteme Clasificare

Reg

uli

de

caracterizare

Reg

uli

de

asociere

Relaii

funcio

nale

Dep

endine

funcio

nale

Reg

uli

cauzale

Tem

porale

Grupare

Clementine X DBMiner(Han, i al. 1996) X X X X X Emerald X X X X Explora(Klsgen 1995) X Mine Rule (Meo, Psaila and Ceri 1996)

X

MineSet 1.1 X Posch (Long, Irani and Slagle 1991)

X

Quest (Agrawal, et al. 1996)

X

RX Project (Blum 1982) X Savnik & Flach (Savnik and Flach 1993)

X

Tabel1.4-1 Tipuri de cunotine care pot fi descoperite in sistemele de Data Mining

DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

8

1.4.1. Cunotine de clasificare

Cunotinele de clasificare pot fi folosite pentru a categorisi noi exemple n clase pe baza unor proprieti cunoscute.

Este realizata prin urmtoarele tehnici:

DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

9

Astfel de informaii pot fi de exemplu folosite de ctre instituii de credit pentru a clasifica riscul de credit al unor posibili clieni pe baza nregistrrilor unor mprumuturi anterioare.

DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

10

1.4.2. Reguli de caracterizare

O regul de caracterizare poate fi definit : O afirmaie care caracterizeaz conceptul satisfcut de toate datele

relevante din baza de date. Regulile de caracterizare sunt reguli eseniale care descriu

caracteristicile unui concept, printr-o abstractizare bazat pe datele din baza de date. Regulile de caracterizare nu fac referire explicit la relaiile dintre entiti sau la uneltele de clasificare a lor. Cunotinele caracteristice sunt utile pentru a oferi o descriere abstract sau sumar a datelor, care poate fi folosit la aplicaii cum ar fi optimizarea interogrilor, asigurarea integritii sau la descoperirea automat a dependinelor.

De exemplu atributele care caracterizeaz un element din setul de date aparin unor domenii a cror dimensiune se cunoate (domeniile caracterizeaz setul in cauza).

1.4.3. Reguli de asociere

Descoperirea de reguli de asociere n baze de date de dimensiuni mari a fost descris prima dat de Agrawal (1993). Motivaia iniial pentru regulile de asociere a fost s ajute n analiza bazelor de date cu tranzacii mari, ca de exemplu acele existente n supermarketuri. Descoperirea de asocieri ntre cumprarea de articole de linie divers poate fi un potenial ajutor pentru luarea unei decizii de ctre organizaiile de comer cu amnuntul. Bazele de date de tranzacii sunt de aceea inta principal pentru descoperirea regulilor de asociere.

De exemplu, ntr-o baz de date care conine detalii de vnzri despre produse utiliznd regulile de asociere permitem utilizatorului s obin cunotine cum ar fi:

Gsete toate regulile care au Diet Lemonade ca i consecin. Astfel de cunotine dau posibilitatea analitilor de vnzri s gseasc

factori care afecteaz vnzarea de Diet Lemonade. n schimb nvarea cererilor cu privire la condiie poate fi pus astfel:

Gsete toate regulile care au Fish ca i condiie. Cereri de exemplul acesteia, care implic gsirea regulilor care au

anumit atribut n condiie pot s ajute analitii n determinarea modului n care un articol special poate fi asociat cu cumprarea de alte articole sau mai general, indic cercettorilor corelrile posibile care pot fi valoroase n viitoarele investigaii. Acest exemplu simplu, poate semnala care decizie oprete vnzrile de Fish.

DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

11

1.4.4. Relaii funcionale

Relaiile funcionale ntre date descriu valoarea uneia sau mai multor atribute n funcie de alte atribute. De exemplu, un atribut y poate fi descris n funcie de alte dou atribute x i z, astfel: zxy 7*2= . Astfel de relaii sunt importante n domeniul tiinific unde relaiile funcionale dintre dou atribute ale datelor pot s reflecte relaii din domeniu.

Cu toate acestea, dei ele pot fi presupuse ca o relaie existent ntre un set de date, relaia exact poate fi necunoscut. Deoarece setul de date din ntrebare poate fi foarte mare i complex, extracia manual a relaiilor din date poate fi impracticabil. De aceea descoperirea automat de relaii funcionale, utiliznd tehnicile inteligenei artificiale (AI) este un domeniu de aplicaie folositor.

1.4.5. Dependine funcionale

Dependinele funcionale descriu relaiile care apar intre tranzaciile dintr-o baza de date, relaii care pot fi utilizate pentru a caracteriza respectiva baza de date.

Un exemplu de dependin funcional poate fi: Cod_curs Nume_curs

Adic dac noi tim codul unui curs, atunci noi putem s-i determinm

numele acelui curs. Implicarea acesteia ntr-o baz de date relaional este c noi avem nevoie s depozitm numai odat fiecare Nume_curs cu corespondena sa Cod_curs. Datorit acestei proprieti, dependinele funcionale sunt utilizate la proiectarea structurii bazei de date relaionale, ajutnd la eliminarea datelor redundante.

1.4.6. Reguli cauzale

Regulile cauzale descriu relaii unde schimbri efectuate ntr-o parte a realitii modelate provoac schimbri ulterioare n alte pri ale domeniului.

Blum a dat urmtoarea definiie operaional a cauzalitii: A se spune c provoac B dac dup observaii repetate (1) A n general precede B, (2) intensitatea lui A este corelat cu intensitatea lui B i (3) nu exist o a treia variabil C cunoscut, responsabil pentru

corelare. Descoperirea de relaii cauzale este important n multe domenii de investigare tiinific, n special n medicin. Cutarea de reguli cauzale n baze de date ofer de asemenea oportuniti de descoperirea unor cunotine folositoare n nelegerea operrii organizaiilor. Lucrrile lui Roddick i alii, au de asemenea relevan n relaiile cauzale,

DATA MINING SISTEME DE DESCOPERIRE A CUNOTINELOR

INTRODUCERE

12

deoarece dependenele temporale pot fi rezultatul unor relaii cauzale. Cu toate acestea, dependenele temporale nu implic relaii cauzale. Relaiile cauzale n mod tipic cer dovezi statistice semnificative, din

aceast cauz, odat detectate prin descoperire de cunotine, pot necesita investigaii adiionale. Cu toate acestea, uneltele KDD sunt folositoare n primul rnd pentru descoperirea unor posibile relaii cauzale.

1.4.7. Cunotine temporale

O caracteristic principal a KDD i Data Mining este prezena unui domeniu dinamic unde datele sunt actualizate ntr-un mod regulat. Astfel, este adesea folositor examinarea modului n care datele i cunotinele derivate din acestea se schimb de-a lungul timpului. Pot aprea, tendine, cicluri i tipare iar detectarea lor poate fi folositoare n analiza datelor istorice i prezicerea comportrii viitoare. De menionat este c aceste tipare pot exista att n cunotinele descoperite ct i n datele pe care se bazeaz. Pe cnd cunotinele temporale pot descrie un domeniu larg de tipuri diferite de reguli derivate din diferite tipuri de date, componenta comun este considerarea dimensiunii temporale i influena sa asupra comportrii entitilor din cadrul domeniului modelat. O form comun de cunotine temporale este existena schimbrilor n seturile de reguli derivate de-a lungul timpului. Detecia de tipare din cadrul seriilor de date temporale a atras o atenie semnificativ. Tipurile de date considerate sunt de obicei numerice, continue i folosesc algoritmi compleci pentru a detecta tipare n cadrul acestor serii. Aa cum a fost observat de Keogh i Smyth cele mai multe abordri pentru rezolvarea acestor tipuri de probleme necesit trei componente fundamentale:

(1) o tehnic pentru reprezentarea unor obiecte abstracte (2) o msur de distan pentru compararea a dou secvene i (3) un mecanism pentru gsirea unor secvene potrivite n cadrul

unor baze de date de serii temporale mari.

1.4.8. Gruparea cunotinelor

Gruparea este o form de nvare nesupervizat care partiioneaz observaiile n clase sau grupuri (colecii numite grupri) (Fisher 1995). Datorit modului de nvare nesupervizat gruparea este aplicabil n aplicaii unde utilizatorul are cunotine de domeniu limitate. Un exemplu de aplicaie este gruparea rezultatelor cutrii pe WEB.

Pe lng o strategie de control corespunztoare i o funcie obiectiv este nevoie s se gseasc metode pentru determinarea numrului optim de grupri ntre date. Obiectivele pot fi unite cu tehnica de clasificare a celor mai apropiai vecini, gsind un punct de oprire pentru acest proces, crend astfel o tehnic care poate estima numrul optimal de grupri ale datelor. Smyth introduce o nou tehnic bazat pe validarea ncruciat Monte Carlo pentru determinarea numrului optim de grupri (Smyth 1996)