UNIVERSITATEA POLITEHNICA BUCURETI

Facultatea de Electronic, Telecomunicaii i Tehnologia Informaiei

Tem de cas
Reele de Calculatoare i Internet
Data mining

Ing. Olga Aldea

Grupa IISC
Master anul II

Bucureti 2011

Contents
Cap 1. Introducere ................................................................................................................... 3
1.1 Principiu, tipuri de informaii pentru data mining................................................................ 3
1.2 Pattern-uri ce pot fi folosite pentru data mining .................................................................. 5
1.3 Clasificarea sistemelor de data mining............................................................................... 6
Cap 2. METODE CLASICE DE DATA MINING ....................................................................... 8
2.1. Metode statistice ............................................................................................................ 8
2.2. Vecini .......................................................................................................................... 9
2.3. Clustering ................................................................................................................... 10
Cap 3. TEHNICI DE NOUA GENERAIE .............................................................................. 11
3.1. Prezentare general: arbori, reele i reguli ...................................................................... 11
3.1.1. Arbori .................................................................................................................. 11
3.1.2. Reele................................................................................................................... 12
3.1.3. Reguli .................................................................................................................. 11
3.2. Mecanismul de arbori de decizie. ................................................................................... 13
3.2.1. ALGORITMII CART I CHAID ............................................................................ 14
CONCLUZII ........................................................................................................................ 16
BIBLIOGRAFIE ................................................................................................................... 17

Cap 1. Introducere
1.1 Principiu, tipuri de informaii pentru data mining
Odat cu creterea rapid a numrului i dimensiunii bazelor de date ct i a
aplicaiilor de baze de date n domeniul comercial, industrial, administrativ i altele, este
necesar i interesant s examinm extragerea automat a cunotinelor din bazele de date de
mari dimensiuni. Muli cercettori au considerat acest domeniu unul provocator i
semnificativ de investigat. [1]
Descoperirea de cunostine din bazele de date (Knowledge Discovery in Databases
KDD) sau extragerea de date (Data Mining DM) reprezint efortul de a nelege, analiza i
eventual de a utiliza o cantitate imens de date disponibile [2].
KDD a fost conceput n anul 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), n zilele de azi
reprezentnd un domeniu de vrf, n plin avnt.
Descoperirea de cunotine n bazele de date este considerat un proces nsemnat de
identificare a unor tipare de date valide, noi, potenial folositoare, care pot fi nelese, aa cum
este artat de ctre Fayyad n [3]. n opinia sa, exist mai multe etape n procesul de
descoperire de cunotine: selectarea, preprocesarea, transformarea, extragerea datelor,
interpretarea sau evaluarea rezultatelor, asa cum este artat n Fig 1.1.
Datorit extragerii de cunotine din bazele de date, acestea au devenit surse bogate i
sigure pentru generarea i verificarea cunotinelor, iar cunotinele descoperite pot fi aplicate
n managementul informatic, procesul de interogare, luarea deciziilor, controlul proceselor i
multe alte domenii de larg interes. Aadar, extragerea de cunotine este considerat unul
dintre cele mai actuale i importante domenii de cercetare n baze de date, conform multor
cercettori din domeniul bazelor de date [4]. Data Mining poate fi definit n prim instan ca
fiind totalitatea proceselor de cutare i manipulare a datelor din bazele de date. Aceast
exploatare a "zcmintelor" de date are ca scop descoperirea unor corelaii necunoscute sau
puin evidente ntre date. Marketingul modern folosete din ce n ce mai mult rezultate
obinute prin data mining.

Fig. 1.1. Etapele procesului de KDD [1]

Funcia principal a DM este, deci, de a extrage modele de cunotine din date. Pentru
aceasta, DM utilizeaz o varietate de algoritmi din statistic, recunoaterea formelor,
clasificare, logica fuzzy, nvare automat (machine learning), algoritmi genetici, reele
neuronale, vizualizarea datelor, etc. Varietatea de algoritmi poate fi grupat n principalele
componente ale DM. Numrul acestor componente difer de la un autor la altul, ele fiind n
principal:
- modelul de alegere a datelor semnificative din baza de date - care, ca orice model
informatic, se reprezint printr-o funcie ntr-un spaiu unidimensional sau
multidimensional (un ansamblu de funcii), depinznd de parametri. El poate fi
reprezentat fie ca o funcie liniar de parametri, fie ca o funcie de probabilitate (de
exemplu normal), fie ca o funcie fuzzy, etc. Obinerea modelului se realizeaz
prin diferii algoritmi, cum ar fi cei de clasificare i grupare (clusterizare); [1], [2]
- criteriile de preferin, de preprocesare a datelor care sunt semnificative pentru
cutarea curent - care pot fi de natur diferit, unele dintre acestea bazndu-se pe
ordonare, altele pe interpolare sau cea mai bun aproximare; [1], [2]
- algoritmi de selecie, care sunt algoritmii de determinare a rezultatelor dorite pe
baza datelor selectate - care conduc la selectarea a trei elemente importante care
apar n DM, i anume: modelul (tiparul), care se selecteaz din baza de modele,
datele, care se selecteaz din baza de date i constituie parametri, i criteriul sau
criteriile de preferine, care se selecteaz din baza de criterii; [1], [2]
- stabilirea abaterilor - care const n general n algoritmi de determinare a deviaiei
i stabilitii; o categorie specific de astfel de algoritmi sunt cei statistici, prin care
se stabilesc abaterile modelului fa de ideal. [1], [2]
Deoarece extragerea de date (Data Mining) este partea central a procesului de
descoperire de cunostine din bazele de date (KDD), termenii data mining i descoperirea de
cunostine din baze de date au fost utilizai alternativ de muli cercettori din domeniu.
4

n cadrul KDD se consider c extragerea cunotinelor se realizeaz n urmtorii pai

(Fig.1.1):
- nvarea domeniului aplicaiei - care const n achiziia unor cunotine despre
starea iniial, precum i despre scopul aplicaiei; [2]
- stabilirea setului de date - cruia i se va aplica procesul de extragere a
cunotinelor; [2]
- curirea i selectarea datelor - care este un proces complex, specific depozitelor
de date, n cadrul cruia se nltur zgomotele, se reduc dimensiunile, se stabilete
modul de nlocuire a datelor care lipsesc, etc.; [2]
- aplicarea procedurilor de DM - care este de fapt pasul cel mai important al
procesului KDD; [2]
- interpretarea rezultatelor din punctul de vedere al utilizatorului - care este o faz
de decizie; dac acesta nu este mulumit de rezultat, poate relua oricare dintre
fazele precedente; [2]
- utilizarea cunotinelor descoperite - care este faza final; aceast utilizare se
realizeaz fie prin includerea lor n sisteme integrate de cunotine fie, pur i
simplu, prin rapoarte simple adresate celor interesai. [2]
Aadar, KDD/Data Mining este un domeniu interdisciplinar care dezvolt algoritmi i
procese pentru descoperirea cunotinelor nestructurate (categorii, tipare, concepte, relaii i
tendine). Deoarece cercettorii din domeniul KDD vin din cele mai diverse domenii, aa
cum era de ateptat, KDD a mprumutat multe de la teoriile tradiionale ale nvrii automate
ct i de la bazele de date.

1.2 Pattern-uri ce pot fi folosite pentru data mining

Dintre mijloacele tradiionale de analiz a datelor, cele mai apropiate de data mining
sunt metodele statistice. Cercetarea statistic, presupune parcurgerea urmtoarelor etape
principale [1]:
formalizarea datelor obinute din investigaii necesare modelrii fenomenului sau
procesului studiat;
dezvoltarea matematic a modelului n scopul fundamentrii prediciilor
fenomenului studiat;
confruntarea prediciilor modelului matematic cu informaiile statistice;
elaborarea concluziilor rezultate n urma analizei.
Etapa de elaborare a modelului matematic este cea mai complex, din acest punct de
vedere, avantajul oferit de procesul data mining, n raport cu metodele statistice, const n
relativa uurin cu care se obin rezultatele. Exist i dificulti n procesul de data mining,
care nu trebuie neglijate, privind etapele de interpretare i validare a rezultatelor obinute.
ncrcarea datelor din depozite de date, nu neaprat din baze de date, constituie un alt
avantaj oferit de data mining. Orict de dificil ar fi procesul de extragere i validare a
modelelor, rezultatele obinute sunt foarte utile pentru cunoaterea i predicia sistemului sau
fenomenului studiat. [1]
Pornind de la tipologia obiectivelor pe care dorim s le atingem n urma procesului
data mining, putem alege una sau mai multe metode care s ne conduc spre obinerea
cunotinelor ateptate.
Metodele data mining pot fi mprite dup scopul funcional n dou categorii: [1]
metode descriptive permit descrierea i explicarea fenomenelor caracteristice
sistemului studiat pe baza modelelor descoperite. Baza de date a acestui tip de data
mining are coninutul neschimbat din punct de vedere temporal.
5

 metode predictive utilizate n realizarea de previziuni referitoare la sistemul sau

fenomenul studiat. Aceste metode sunt folosite n cazul n care baza de date sau
depozitul de date are un coninut variabil n timp, n funcie de evoluia
fenomenului studiat (ex: previziuni meteorologice).
Fiecare categorie conine metode, respectiv algoritmi specifici, care conduc ctre
obinerea modelului.
Din punct de vedere al nvrii autonome avem dou categorii de metode: [1]
metode nesupervizate de nvare. Se folosesc datele de intrare fr o etichetare
prealabil a obiectelor de ctre un agent extern. Din aceast categorie fac parte
urmtoarele metode: clustering, descoperirea regulilor de asociere.
metode supervizate de nvare. Exist o etichetare iniial a datelor de intrare, ce
servete la iniializarea anumitor parametri a metodei de data mining. Aceast
etichetare este fcut de un agent extern. Aici sunt cuprinse: metodele statistice,
arbori de decizie, reele neuronale;

1.3 Clasificarea tipurilor de data mining

Clasificarea sistemelor Data Mining se face n funcie de criterii astfel stabilite nct
s ofere fiecrui utilizator posibilitatea de a identifica cu uurin sistemul Data Mining cel
mai potrivit pentru necesitile sale manageriale. Principalele criterii de clasificare a
sistemelor Data Mining sunt urmtoarele: [5]
1. n funcie de depozitul de date care conine datele asupra crora se aplic procesul
Data Mining i care, la rndul lor, se clasific n funcie de: [5]
- modelul de date n jurul cruia este construit depozitul de date, caz n care se
deosebesc sisteme Data Mining relaionale, tranzacionale, data warehouse, obiecturale,
relational-obiecturale sau heterogene;
- tipul datelor manipulate, caz n care se deosebesc, n principal, sisteme Data Mining
temporale, secveniale sau time-series, text sau multimedia, pentru fluxuri i secvene de date,
precum i pentru Web;
2. n funcie de numrul de tehnici Data Mining integrate pentru ndeplinirea
funciilor Data Mining, care caz n care se deosebesc sisteme Data Mining care: [5]
- integreaz o singur categorie de tehnici Data Mining care realizeaz funciile Data
Mining pentru descoperirea unei singure categorii de modele de date, ca de exemplu tehnici
pentru caracterizarea i discriminarea datelor, pentru asocierea i corelaia datelor, pentru
clasificare i predicie, pentru grupare i analiz excepii sau pentru analiza evoluiei datelor;
- integreaz tehnici Data Mining multiple care realizeaz funciile Data Mining pentru
descoperirea unor categorii variate de modele de date necesare n diverse aplicaii i/sau
pentru a rspunde asteptrilor diferiilor utilizatori (sisteme Data Mining complexe);
3. n funcie de nivelul de abstracie la care se prelucreaz datele, caz n care se
deosebesc sisteme Data Mining care asigur extragerea modelelor de date: [5]
- pe un singur nivel de abstracie, corespunztor unui singur nivel de detaliu care este
specificat de utilizator, caz n care se obin cunotine generalizate la un nivel ridicat de
abstracie sau cunotine primare la cel mai de jos nivel de abstracie;
- pe mai multe nivele de abstracie, corespunztoare nivelelor de detaliu solicitate de
utilizatori (sisteme Data Mining avansate);
4. n funcie de frecvena de aplicare a procesului Data Mining, caz n care se
deosebesc sisteme Data Mining care prelucreaz datele: [5]

- regulat (frecvent sau ritmic), pentru extragerea modelelor de date respectate de

majoritatea datelor din setul de date selectat de utilizator pentru analiz; n general, tehnicile
Data Mining de tip caracterizare i discriminare, asociaie i corelaie, clasificare i predicie,
precum i grupare prelucreaz datele cu regularitate, rejectnd excepiile;
- neregulat (la nevoie), pentru extragerea datelor aflate n afara modelelor de date
respectate de majoritatea datelor din setul de date selectat de utilizator pentru analiz,
considerate excepii; n acest caz n care se folosesc, n mod uzual, tehnicile Data Mining de
analiz a excepiilor;
5. n funcie de modul de interaciune cu utilizatorul implicat, caz n care se
deosebesc sistemele Data Mining care: [5]
- nu interacioneaz cu utilizatorul implicat pe durata procesului Data Mining
(autonome sau independente);
- interactioneaz cu utilizatorul implicat pe durata procesului Data Mining
(interactive); spre exemplu, interaciunea bazat pe interogare (query-driven);
6. n funcie de metoda de analiz a datelor utilizate, caz n care se deosebesc
sisteme Data Mining care folosesc metode de analiz a datelor orientate pe: [5]
- modelul de date n jurul cruia este construit depozitul de date care conine datele
asupra crora se aplic procesul Data Mining, care, la modul general, poate fi bidimenional
pentru baze de date sau multidimensional pentru data warehouse;
- forma de analiz a datelor asupra crora se aplic procesul Data Mining, caz n care
se deosebesc sisteme Data Mining pentru analiza statistic sau vizual, pentru reele neurale
etc.
7. n funcie de domeniul de aplicabilitate, caz n care se deosebesc sisteme Data
Mining adaptate la specificul domeniilor de activitate care utilizeaz forme avansate de
analiz a datelor pentru eficientizarea managementului decizional, ca de exemplu finane,
comer, telecomunicaii, e-mail, pentru Web etc. [5]

Cap 2. METODE CLASICE DE DATA

MINING
2.1. Metode statistice
Printre metodele clasice folosite pentru data mining se numr metodele statistice,
metodele care folosesc informaii de la vecini i cele de clustering. Printre metodele clasice
cele mai folosite se numr:
Regresia: n general, metodele de regresie sunt folosite pentru a anticipa valoarea
unui rspuns cu una sau mai multe variabile predictive, n cazul n care variabilele sunt
numerice. Exist diverse forme de regresie, cum ar fi linear, multipl, polinomial,
nonparametric si robust (metodele robuste sunt folositoare doar n cazul n care erorile nu
pot satisface condiiile de normalitate sau cnd datele contin aberaii nsemnate). [6]
Modele lineare generalizate: Aceste modele i generalizarea lor (modele aditive
generalizate) permit stabilirea unei relaii ntre o variabil de rspuns categoric (sau unele
forme ale acestuia) i o serie de variabile predictive n acelai fel n care o variabil de
rspuns numeric folosete regresia linear. Modelele lineare generalizate cuprind regresia
logic i regresia Poisson. [6]
Arborii de regresie: Acetia pot fi folosii pentru clasificare i predicie. Arborii sunt
binari. Un arbore de regresie e asemntor unui arbore de decizie, n sensul c testele se fac la
nivelul nodurilor interne. O diferen major e la nivelul frunzelor, pentru ca ntr-un arbore de
decizie o majoritate de vot e destinat s atribuie o etichet de clas unei anumite frunze, n
timp ce la un arbore de regresie atributul obiectiv este codat i folosit drept valoare
predictiv. [6]
Analiza variabilitii: Aceste tehnici analizeaz datele experimentale pentru dou sau
mai multe populaii descrise de un rspuns numeric variabil i una sau mai multe variabile
categoriale (factori). n general, o problem ANOVA (ANalysis Of VAriance - analiz a
variabilitii n funcie de un factor unic) implic de fapt o comparaie ntre caracteristicile
populaiei K pentru a vedea dac mcar dou dintre aceste caracteristici sunt diferite. Exist
i alte probleme ANOVA mult mai complexe. [5]
Modele cu efect mixt: Aceste modele sunt folosite pentru analizarea datelor grupate,
date care pot fi clasificate cu ajutorul a uneia sau a mai multor variabile de grupare. n
general, acestea descriu relaiile dintre o varaibil de rspuns i unele covariate n date
grupate n funcie de unul sau mai muli factori. Zonele comune de aplicaie cuprind date
multinivel, date de msuri repetate, block design i date longitudinale. [5]
Analiza de factor: Aceast metod este folosit pentru a determina care variabile sunt
combinate pentru a genera un anumit factor. De exemplu, pentru multe date psihiatrice, nu e
posibil msurarea direct a unui factor de interes (cum ar inteligena); totui, este posibil
analiza altor cantiti (de ex. notele studenilor la un examen) care reflect factorul de interes.
n acest caz, nici una dintre variabile nu e desemnat ca dependent. [5]
Analiza discriminant: Aceasta tehnic este folosit pentru a anticipa o variabil de
rspuns categorial. Spre deosebire de modelele lineare generalizate, acest tehnic presupune
c variabilele independente urmeaz o distribuie normal multivariat. Aceast procedur
ncearc s determine funcii discriminante (combinaii lineare ale variabilelor independente)
8

care fac deosebirea ntre grupurile definite de variabila de rspuns. Analiza discriminant este
folosit mai ales n tiinele sociale. [5]
Seriile de timp: Acestea sunt diverse tehnici de statistic utilizate pentru analizarea
datelor de tip serii de timp, cum ar fi metodele de autoregresie, ARIMA (AutoRegressive
Integrated Moving Average) univariate i modelele de serii de timp memorie de lung durat.
[5]
Analiza de supravieuire: Exist cteva tehnici statistice bine cunoscute pentru
analiza de supravieuire. La origine, acestea au fost concepute pentru a anticipa probabilitatea
cu care un pacient supus unui anumit tratament va supravieui mcar un timp . Totui,
metodele analizei de supravieuire sunt aplicate i n cazul echipamentelor industriale pentru
a estima durata de via a utilajelor. Metodele cele mai cunoscute sunt Kaplan-Meier
(estimarea duratei de via), Cox (modelele de regresie a riscurilor proporionale) i extensiile
lor. [5]

2.2. Vecini
Algoritmul celor mai apropiai k vecini (k-nearest neighbors, k-NN) este o tehnic
predictiv potrivit pentru clasificarea modelelor. Tehnica k-NN presupune c ntregul set de
antrenare include att datele ct i clasificrile dorite pentru fiecare item. Ca urmare a
aplicrii tehnicii datele de antrenare devin modelul. K reprezint numul de cazuri similare
sau numrul de articole din grup. [7]
La apariia unui caz sau exemplu nou n model, algoritmul verific toate datele pentru
a gsi un subset care este cel mai apropiat de cel nou i ofer acest subset ca i rezultat,
plasndu-l n clasa care conine cei mai muli itemi din acest set al celor mai apropiai k itemi.
[7]
Algoritmul k-NN are doi parametri principali: [7]
numrul celor mai apropiate (similare) cazuri k
o metric pentru msurarea similaritii
La fiecare utilizare a algoritmului k-NN este necesar s se specifice o valoare ntreag
pozitiv pentru k. Aceast valoare reprezint numrul de cazuri existente care sunt analizate
la precizarea unui nou caz. [7]
Algoritmul k-NN decide n ce clas s plaseze un nou caz prin examinarea unui numr
k de cazuri (vecini) cu un grad mare de asemnare. [7]
Algoritmul k-NN este bazat pe conceptul de distan iar aceasta necesit o metric
pentru determinarea distanelor. Presupunem c avem n vectori de caracteristici x1, x2, ...,xn i
c acetia fac parte din grupri compacte, cu c<n. Fie mi media vectorilor din gruparea i.
Daca gruprile sunt bine separate putem utiliza un clasificator de distan minim pentru a le
separa. Adic putem spune c x este n gruparea i dac distana x-mi este minimul dintre toate
cele k distane. [7]
Pentru atributele continue putem folosi distana Euclidian iar pentru variabilele de tip
enumeraie trebuie s gsim un mod potrivit pentru calcularea distanelor dintre atributele din
setul de date. Alegerea unei metrici potrivite este o problem dificil deoarece diferite metrici
folosite pe acelai set de antrenare pot da rezultate complet diferite. Aceasta nseamn c
avem nevoie de un expert n domeniu care s ajute la alegerea unei metrici potrivite. [7]

2.3. Clustering
Aceast metod statistic este folosit pentru a grupa date multi-dimensionale (adic
puncte ce reprezint cazuri sau observaii) n grupe (clusters) definite algoritmic. [8]
Aceast metod este util pentru sumarizarea unor cantiti mari de informaie, fiecare
grup reprezentnd mai multe puncte avnd caracteristici similare. Clusterele distincte nu se
suprapun (sunt disjuncte).
De fapt, analiza clasificrii const dintr-o colecie de algoritmi ce exploateaz mai
multe euristici fundamentate n principal pe experiena noastr vizual n gruparea
punctelor n nori de puncte.
n general, pentru a putea folosi un algoritm de clasificare, este nevoie ca mai nti s
se precizeze: [8]
a) Un tip de distan ntre punctele unui spaiu multidimensional.
b) O strategie de alegere a punctului reprezentativ (adic a centrului) pentru orice
grupare de puncte. Cei mai muli oameni au tendina de a alege media aritmetic (adic
centrul de greutate).
c) Un tip de distan ntre dou grupe de puncte. Cele mai folosite asemenea distane
iau n considerare distana ntre puncte aleas anterior;
Odat ce au fost efectuate alegerile, un algoritm ierarhic de clasificare va funciona n
felul urmtor: [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.
Acest pas este repetat pn cnd toate punctele au fost grupate ntr-o grupare final (care
conine totul). Schema de amalgamare este reprezentat diagramatic printr-o dendrogram
(hierarchical tree plot) a se vedea figura de mai jos pentru un exemplu (Fig 3.1).

Fig 3.1. Exemplu de dendrogram

Pasul 3. Se aplic o procedur de tiere asupra dendrogramei; n acest fel se
identific numrul obiectiv de grupe (clusters), apoi componena fiecreia.

10

Cap 3. TEHNICI DE NOUA GENERAIE

3.1. Prezentare general: reguli, arbori i reele neuronale
3.1.1. Reguli
Regulile de asociere se definesc astfel:
Fie I = {i1,i2,...,im} un numr de simboluri, numite elemente. Se consider D o
mulime de tranzacii, n care fiecare tranzacie T se constituie ca o submulime al lui I, unde
T este o mulime inclus sau egal cu I. Se iau n considerare doar prezena (reprezentat
binar) a elementelor n tranzacie i nu se consider alte caracteristici cantitative sau calitative
ale acestora. Fiecrei tranzacii i este asociat un identificator (tid). [5]
Msurile cheie n cadrul extragerii regulilor de asociere sunt suportul i ncrederea.
Suportul se refer la proporia n care o relaie apare n date. Confidena / ncrederea regulilor
de asociere se refer la probabilitatea de a gsi un antecedent avnd o consecin.
Determinarea regulilor de asociere se face n doi pai: [5]
- Determinarea seturilor de elemente frecvente, cele care au suport suficient;
- Determinarea regulilor de asociere dintre aceste seturi, determinarea de reguli tari.
Acest pas se rezolv astfel: pentru fiecare set frecvent X i pentru fiecare subset al
lui X ,Y X se determin parametrii regulii X\Y Y innd cont c rezultatul
reuniunii prii stngi cu partea dreapta trebuie s reprezinte un set frecvent, n
acest caz X\Y Y =X .
Regulile de asociere se folosesc pentru a gsi mulimile frecvente de articole n bazele
de date ce conin tranzaciile consumatorului, problem cunoscut sub denumirea de analiza
coului de cumprturi (market basket analysis). Analiza coului de cumprturi const n
gsirea de asocieri ntre produsele cumprate, respectiv afiate pe bonul de casa. Se studiaza
astfel ce cumprturi fac clienii pentru a obine informaii asupra produselor ce tind a fi
cumprate n acelai timp. n acest caz, baza de date cu tranzaciile consumatorilor este
reprezentat printr-o secven de tranzacii T=(t1,...tn), iar fiecare tranzacie este o mulime
de articole. De exemplu, n cazul coului de cumprturi se poate cere ca ncrederea s fie
semnificativ mai mare dect n cazul n care articolele ar fi plasate aleator n co. Se poate
gsi o regul {lapte, unt} => pine pe principiul c mult lume cumpr pine, nsa exemplul
bere/scutece descoperit n SUA arat c regula {scutece}=>{bere} este verificat cu o
ncredere semnificativ mai mare dect a mulimii de couri coninnd bere. Rezultatul acestui
studiu ajut vnztorii n procesul de aezare a articolelor n rafturi i controleaz modul n
care un cumprator tipic traverseaz magazinul. [5]
n cazul analizei click-urilor se lucreaz pe o baz de date cu sesiunile serverului care
nregistreaz solicitrile utilizatorilor. Sesiunile utilizatorilor sunt secvene S=(s 1,...,sn)
formate cu paginile vizitate de utilizator. Determinarea linkurilor frecvente i a regulilor de
asociere este esenial pentru problema analizei click-urilor, modul n care utilizatorii
navigheaz pe Internet i acceseaz diverse site-uri. [5]
De multe ori, tranzaciile sunt nregistrate innd cont de o secven temporal. De
exemplu, tranzaciile pentru deintorii unui card de loialitate corespund secvenei de chitane
de vnzare.
Tranzaciile care nregistreaz cile de navigare urmate de ctre un anumit utilizator
web sunt asociate cu o secven temporal a sesiunilor. n astfel de situaii, analitii sunt
interesai s extrag regulile de asociere care iau n considerare dependene temporale.
11

Problema descoperirii regulilor secveniale a fost introdus prima dat de ctre Agrawal i
Srikant n [10].

3.1.2. Arbori
Arborele decizional este o tehnic de explorare a datelor cu potenial att predictiv, ct i
descriptiv. Denumirea sa provine de la aceea c rezultatul se prezint utilizatorului sub forma
unui graf de tip arbore. Output-ul major al unui model bazat pe arbori decizionali este arborele n
sine.
Procesul de instruire care creeaz arborele este numit inducie. Inducia presupune, ca i
n cazul reelelor neuronale, parcurgerea de cteva ori a setului de date de instruire, cu deosebirea
ca n cazul arborilor, timpul de instruire si implicit numrul de baleieri ale setului de date este
mult mai mic dect la reelele neuronale. Mai precis, numrul de parcurgeri ale setului de
instruire este egal cu numrul de niveluri n arbore. [9]
Majoritatea algoritmilor nu folosesc ntregul set de date indicat de utilizator pentru
inducie. Pentru aceti algoritmi, construirea arborelui presupune transferul instanelor din setul
de date de instruire n memoria RAM. Dimensiunea limitat a memoriei face ca programul s
transfere n RAM numai un subset de date, selectat aleator. n consecin, gradul de
reprezentativitate al modelului construit este determinat de capacitatea aplicaiei de a selecta un
subset reprezentativ pentru ntreg setul de inducie. O critic adus frecvent arborilor decizionali
este aceea c algoritmii de inducie nu iau n considerare la momentul mpririi efectul pe care
respectiva separare o are asupra viitoarelor mpriri. n plus, toate separrile se fac secvenial,
ceea ce determin dependena fiecrei mpriri de cele precedente. [9]
Majoritatea algoritmilor care construiesc arbori decizionali pot fi aplicai fr restricii
legate de tipul datelor. Dei variabila dependent trebuie s fie de natur numeric (n cazul
problemelor de regresie) sau categoric (n cazul problemelor de clasificare), pentru majoritatea
algoritmilor, variabilele independente pot lua valori n orice domeniu. Tehnica se caracterizeaz
prin capacitate de prelucrare a unor seturi de date cu numr mare de atribute. Exist situaii n
care o instan poate fi descris printr-un numr relativ mare de atribute, de ordinul sutelor sau
chiar miilor. n astfel de situaii, explorarea prin tehnica arborilor decizionali reprezint singura
alternativ, cei mai multi algoritmi fiind capabili s trateze seturi de date cu peste 1000 de
coloane. [9]

3.1.3. Reele neuronale

Tehnica are la baza dou concepte aparinnd domeniului inteligenei artificiale.
Neuronul artificial reprezint unitatea de baz pentru prelucrarea informaiei n cadrul calculului
neuronal. Prin analogie cu neuronul biologic, el a fost definit ca o unitate ce proceseaz inputuri
informaionale i genereaz outputuri. Reeaua neuronal artificial reprezint un ansamblu de
neuroni artificiali, legai prin conexiuni. [5]
Retelele neuronale sunt sisteme dinamice, al cror comportament poate fi caracterizat prin
urmrirea strilor la momente diferite de timp. Starea unei reele la un moment dat este definit
de ansamblul nivelurilor de activare a neuronilor i de intensitatile conexiunilor dintre neuroni. n
plus fa de aceti parametri ajustabili, o reea este definit i de urmtorii parametri fici:
configuraia conexiunilor i tipul funciilor de activare. [5]
Reelele neuronale nu opereaz dect direct asupra variabilelor numerice. Drept urmare,
orice variabil nonnumeric din setul de date care se dorete analizat va trebui convertit n
variabila numeric nainte de utilizarea sa n instruirea reelei. n cazul problemelor complexe,
utilizatorul este pus n situaia de a rezolva un compromis, ntre a crete numrul de neuroni
12

ascuni, ceea ce poate conduce la o instruire foarte lent i a accepta o topologie mai simpl,
asociat unei soluii mai putin precise. [5]
Pentru seturi de date cu numr mare de atribute, folosirea reelelor neuronale devine
nefezabil. Determinarea numrului de neuroni ascuni, pentru probleme complexe de clasificare,
nu se poate face dect experimental, ceea ce pe de o parte crete substanial timpul alocat cutarii
modelului optim de clasificare, iar pe de alt parte las calitatea rezultatelor analizei s depind
de nivelul de experien al utilizatorului. [5]
Reeaua odat instruit poate realiza predicii rapide pentru instane noi. Aceast
caracteristic face ca reelele neuronale s fie utilizate cu succes n probleme care necesit
rspuns n timp real. Pn n prezent, reelele neuronale reprezint metoda cea mai eficient de
modelare a unor relaii neliniare. Mai mult, aplicaiile de pn acum au demonstrat aplicabilitatea
acestei tehnici n domenii dificil de modelat, precum vederea electronic sau recunoatere vocal.
Spre deosebire de celelalte tehnici de data mining, reelele neuronale nu restrictioneaz
output-ul la un singur atribut. Folosind o arhitectur de reea potrivit se pot obine predicii
simultane pentru mai multe variabile, ceea ce poate nsemna o eficientizare semnificativ a
proceselor de explorare a datelor. [5]

3.2. Mecanismul de arbori de decizie.

Un arbore de decizie (Decision Tree) este un model de clasificare sau estimare care
poate fi privit ca un arbore. Fiecare subarbore din componena sa reprezint un rspuns la o
ntrebare de clasificare, frunzele arborelui sunt partiii sau segmentri ale setului de date n
funcie de clasificarea realizat, iar nodurile prezint informaii statistice.
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 cutare de factori predictivi pentru a construi
subarborii pn cnd nu mai exist date de procesat. Reducerea arborelui (tree pruning) crete
acurateea la datele-zgomot i poate fi realizat atunci cnd arborele este n construcie (prepruning), sau dup construcia arborelui (post-pruning).[9]
Arborele de decizie genereaz un output cu o interpretare uoar pentru marketing i o
identificare facil a variabilelor semnificative n luarea deciziilor manageriale. La construirea
modelului arborescent se pot utiliza variabilele originale care nu au fost transformate sau
normalizate. Modelul de arbore de decizie va crea reguli asupra datelor de estimat variabila
int. Metodele specifice de arbore de decizie includ arborii de clasificare i regresie
(Classification and Regression Trees: CART) i detecia automat a interaciunii 2 (Chi
Square Automatic Interaction Detection: CHAID). Ei furnizeaz o mulime de reguli ce pot fi
aplicate pentru un set de date neclasificat, pentru a estima care nregistrri vor avea o anumit
ieire. CART segmenteaz un set de date crend subarbori binari, n timp ce CHAID
segmenteaz setul de date crend subarbori oarecare, utiliznd teste. CART necesit de obicei
mai puin pregtire a datelor dect CHAID. [11]
Dei arborii de decizie au fost dezvoltai iniial ca instrumente exploratorii pentru
rafinarea i preprocesarea datelor pentru tehnici statistice, cum ar fi regresia logic, ei sunt
din ce n ce mai mult utilizai pentru predicie. Analiza regresiei este o tehnic statistic
tradiional pentru gsirea unei funcii care descrie relaia dintre un numr de variabile i o
valoare care se dorete estimat. Aceast tehnic utilizeaz, n general, intrri numerice. De
obicei este necesar o preprocesare. Cele mai utilizate tehnici de regresie sunt: regresia
polinomial (polynomial regression), extensie a regresiei lineare i regresia logic (logistic
13

regression), ieirea n acest caz fiind 1 sau 0 [12]. Arborii de decizie luai n considerare n
problema analizelor de regresie sunt numii arbori de regresie.[12]

3.2.1. ALGORITMII CART I CHAID

Algoritmul CART este un algoritm de explorare i predicie [11] care alege fiecare
predictor la construirea arborelui astfel nct s scad dezordinea datelor. Msura pe baza
creia este preferat un predictor altuia este valoarea entropiei. Algoritmul CART este relativ
robust n raport cu datele lips. Dac o valoare lipsete pentru un predictor particular ntr-o
nregistrare particular, la construirea arborelui acea nregistrare nu va fi utilizat n
realizarea determinrii ramificrii optimale. Cnd 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 cnd lipsesc datele pentru predictorul dorit. De exemplu, dei mrimea la
pantofi nu este un predictor perfect pentru nlimea unei persoane, ea poate fi folosit ca un
substitut n ncercarea de a simula o ramificare bazat pe nlime cnd acea informaie
lipsete dintr-o nregistrare particular ce trebuie utilizat n estimarea cu modelul CART.
CHAID difer de CART n modul cum alege ramificarea. Pentru alegerea ramificrii
optimale, CHAID se bazeaz pe testul 2 din tabelele de contingen pentru a determina care
predictor categorial este cel mai departe de independen cu valorile estimate. Algoritmul
CHAID este popular n cercetrile de marketing n contextul studiilor de segmentare a pieei.
Putnd fi utilizai att pentru predicie ct i pentru clasificare, algoritmii CART i CHAID
pot fi aplicai pentru analiza problemelor de tip regresie sau de tip clasificare. Paii urmai la
dezvoltarea algoritmului CHAID sunt: [11]
1. Pregtirea predictorilor. Se construiesc predictorii categoriali din predictorii
continui prin mprirea distribuiei continue ntr-un numr de categorii cu un numr
aproximativ egal de observaii. Pentru predictorii categoriali, categoriile (clasele) sunt
definite de la sine.
2. Fuziunea categoriilor. Parcurgem repetat predictorii pentru a determina pentru
fiecare predictor perechea de categorii predictor care sunt cel mai puin semnificative n
raport cu variabila dependent; pentru problemele de clasificare (unde variabila dependent
este categorial), se va evalua un test Pearson1; pentru problemele de regresie (unde variabila
dependent este continu), se va evalua un test F2. Dac testul respectiv pentru o pereche dat
de categorii predictor nu este semnificant statistic, atunci se vor fuziona categoriile predictor
respective i se va repeta acest pas (adic se va gsi urmtoarea pereche de categorii, care
acum pot include categoriile anterior fuzionate). Dac perechea de categorii predictor este
semnificativ statistic, atunci se va estima un test Bonferroni3 p-valoare4 ajustat pentru
mulimea categoriilor predictorului respectiv.
3. Selectarea valorii de separare. Alegem variabila predictor de separare cu cea mai
mic p-valoare ajustat, adic variabila predictor care produce cea mai semnificativ
separare; dac cea mai mic p-valoare ajustat (Bonferroni) pentru orice predictor este mai

n statistic, testul Pearson calculeaz probabilitatea ca un test s fie detectat ca fals pozitiv n cazul n care
testul poate avea dou ipoteze H0 i H1 [13]
2
Un test F este un test statistic care are o distribuie de tip Student sub ipoteza nul. [14]
3
Bonferroni implic o succesiune de teste t la care pragul de semnificaie este divizat prin numrul de
comparaii. [15]
4
p-valoarea unui test este cea mai mic valoare a lui pentru care datele statistice au probabilitatea de acceptare
HA [16]

14

mare dect o anumit valoare de separare, atunci nu va mai fi executat nici o separare i
nodul respectiv este o frunz.
Acest proces continu pn cnd nu mai poate fi realizat nici o separare.[12]

15

CONCLUZII
Posibilitatea de stocare a volumelor mari de date duce la nevoia de a extrage diferite
informaii pe baza acestor date. Astfel, folosirea Data Mining este util n vederea obinerii
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 complicai, ns rezultatul poate
fi prezentat ntr-un mod uor de neles, 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 msur, i n aplicaiile de clasificare ce sunt solicitate n
diverse domenii cum ar fi experimentele tiinifice, aprobrile 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 fr s piard nici o dat, numrul
total de nregistrri din nodul printe fiind egal cu suma nregistrrilor coninute n cei doi
subarbori fii;
este uor de neles cum a fost construit modelul, n contrast cu alte modele
concurente cum ar fi reele neuronale etc.
Datorit naltului lor nivel de automatism i uurinei de translatare a modelelor
construite cu arbori de decizie n SQL, pentru utilizarea n baze de date relaionale,
tehnologia este uor de integrat n procese IT deja existentele, necesitnd puin preprocesare
i reducere a datelor, sau extragere a lor cu scop precis pentru Data Mining.

16

BIBLIOGRAFIE
[1] Arun K. Pujari Data mining techniques Universities Press, 2001
[2] Fayyad U, et al., From Data Mining to Knowledge Discovery in Databases, Ai Magazine, 1996
[3] Fayyad U.M., Piatetski-Shapiro G., Smyth P. and Uthurusamy R., Advances in Knowledge Discovery and
Data Mining, AAAI/MIT Press, 1996
[4] Silechi Mircea, Curta Lisette, Modelarea matematic a proceselor sociale, Ed. RSR, Bucureti, 1972;
[5] Han, J. & Kamber, M. Data mining concepts and techniques (2nd ed.), edited by Morgan Kaufmann, V.
Harinarayan, A. Rajaraman, [Link]. San Francisco, 2006
[6] Mosteller, F. and Tukey, J. W. (1977) Data Analysis and Regression. Reading, MA: Addison-Wesley.
[7] Hart , P. E. , Cover , T. M. Nearest neighbor pattern classification, IEEE Transactions on Information
Theory, IT-13, 1967
[8] Barbara, D. An introduction to cluster analysis for data mining,
[9] Rokach L., Maimon O. Data mining with decision trees - Theory and Applications
[10] Agrawal, R., Srikant, R. (1995), Mining sequential patterns, International Conference on Data
Engineering(ICDE95), Taipei, Taiwan, pp. 3-14.
[11] Nepomnjashiy, A., Data Mining Algorithms: Microsoft SQL Server 2000 vs. "Yukon" SQL Server,
[Link], 2004, [Link]
[12] Breiman, L., Friedman, J., Olshen, R., Stone, C., Classification and Regression Trees, Stanford University
and the University of California, Berkeley, 1984.
[13] K. Pearson. On a new method of deternining goodness of fit. Biometrika, 26 (4):425442, 1934.
[14] Blackwell M. Multiple Hypothesis Testing: The F-test, 2008
[15] Simer, R.J. An improved Bonferroni procedure for multiple tests of significance. Biometrika 73, 751-4,
1986.
[16] Guy Lebanon p-Values, Power and the Neyman-Pearson Lemma October 15, 2006

17