Curs 2 Data Mining

76
Introducere în Data Mining Curs 2: Date Lucian Sasu, Ph.D. Universitatea Transilvania din Braşov, Facultatea de Matematică şi Informatică April 7, 2014 [email protected] (UNITBV) Curs 2 April 7, 2014 1 / 76

Transcript of Curs 2 Data Mining

Page 1: Curs 2 Data Mining

Introducere în Data MiningCurs 2: Date

Lucian Sasu, Ph.D.

Universitatea Transilvania din Braşov, Facultatea de Matematică şi Informatică

April 7, 2014

[email protected] (UNITBV) Curs 2 April 7, 2014 1 / 76

Page 2: Curs 2 Data Mining

Outline

1 Tipuri de dateAtribute şi măsurătoriTipuri de seturi de date

2 Calitatea datelorProbleme legate de măsurarea şi colectarea datelorCalitatea datelor din perspectiva aplicaţiilor

3 Preprocesarea datelorAgregareEşantionareReducerea dimensionalităţiiSelectarea subsetului de atributeCrearea de trăsăturiDiscretizare şi binarizareTransformarea de variabile

4 Măsuri de similaritate si deosebire

[email protected] (UNITBV) Curs 2 April 7, 2014 2 / 76

Page 3: Curs 2 Data Mining

Tipuri de date (1)

Un set de date este o colecţie de obiecte-dată (eng: data objects) şide atributeSinonime pentru obiecte-dată: înregistrare, punct, vector, pattern

(termen ce poate induce confuzie), eveniment, caz, eşantion

(termen ce poate induce confuzie), observaţie, entitate.Obiectele sunt descrise prin atribute

Sinonime pentru atribut: variabilă, caracteristică, trăsătură

(feature), dimensiune (a nu se confunda cu omonimul din algebră).

[email protected] (UNITBV) Curs 2 April 7, 2014 3 / 76

Page 4: Curs 2 Data Mining

Tipuri de date (2)

Definiţie

Atribut: proprietate sau caracteristică a unui obiect ce poate sa varieze fiede la un obiect la altul, fie de la un moment de timp la altul.

Exemple: culoarea ochilor, temperatura.

Trebuie făcută diferenţa între proprietăţile atributelor şi proprietatilevalorilor atributelor:

acelaşi atribut poate avea valori diferite: înălţimea poate fi măsurată înmetri sau picioarediferite atribute pot fi măsurate cu acelasi tip de date, dar proprietăţileatributelor pot fi diferite: pentru nişte persoane, atributele “inaltime” şi“id” sunt reprezentate prin numere întregi; în timp ce are sens sa facimedia înălţimilor, nu are nicio noimă media id-urilor; operaţiile ce sepot face pentru înaltime (medie, max etc.) nu se aplică şi pentru id-uri;id-urile nu au un maxim, în timp ce înălţimea - da.

[email protected] (UNITBV) Curs 2 April 7, 2014 4 / 76

Page 5: Curs 2 Data Mining

Tipuri de atribute

Există diferite tipuri de atribute:

Categoriale (calitative)

nominale: valori diferite care permit recunoaşterea diferenţelor;exemple: cod postal, id-uri, culoarea ochilor, genul; operatii permisibile:=, 6=;ordinale: valorile permit ordonarea obiectelor; exemple: scara durităţiimineralelor, grade (militare etc.), gradul de satisfacţie pentru unanumit produs; operaţii permise: =, 6=, <, >; funcţii aplicabile:mediana, percentile etc.

Numerice (cantitative)

interval: se poate face diferenţa între valori (i.e. există unităţi demasură asociate); exemple: date calendaristice, temperaturi in gradeCelsius sau Fahrenheit; pe lângă operaţiile de mai sus admit şi adunare,scădere; funcţii aplicabile: media, deviatia standard, corelaţiamultiplicabile: permit împărţiri şi înmultiri; exemple: temperatura înKelvin, cantităţi monetare, număr de elemente, vârsta, greutate;operatii: cele de mai sus şi ∗, /; funcţii aplicabile: media geometrică,variaţie procentuală.

[email protected] (UNITBV) Curs 2 April 7, 2014 5 / 76

Page 6: Curs 2 Data Mining

Transformari la nivel de atribute

Există nişte transformări care se pot efectua sau nu asupra unor atribute:

pentru atribute nominale: orice asociere unu-la-unu (bijecţie), deexemplu permutări; dacă toţi angajaţii au un id, reasignarea lor nu armodifica esenţa datelor;

pentru atribute ordinale: orice modificare de valori care respectăordinea datelor (transformare monotona): val_noua = f (val_veche),unde f (·) funcţie monoton crescătoare; {bun, mai bun, cel mai bun}poate fi reprezentat prin {1, 2, 3} sau la fel de bine prin {0.3, 12, 14};

pentru atribute interval: transformări de forma a ∗ val_veche + b undea şi b sunt constante; ex: transformarea din Celsius în Fahrenheit;

val_noua/val_veche = a; ex: raportul greutăţii lui x si y este 2.

[email protected] (UNITBV) Curs 2 April 7, 2014 6 / 76

Page 7: Curs 2 Data Mining

Descrierea atributelor prin numarul de valori (1)

Atribute discrete:

o mulţime cel mult numărabilă de valori;exemple: coduri poştale, cuvinte într-un documentse reprezintă cel mai frecvent ca numere naturalecaz special — atribute binare: {prezent, absent}

Atribute continue:

valorile sunt exprimate prin numere realeexemple: temperatura, masadpdv practic reprezentarea se face cu o precizie finităreprezentare actuală: valori în virgulă mobilă

[email protected] (UNITBV) Curs 2 April 7, 2014 7 / 76

Page 8: Curs 2 Data Mining

Descrierea atributelor prin numarul de valori (2)

Valori asimetrice:

doar prezenţa unei trăsături (i.e. valoare non–zero) este importantăexemple: vectorul care reprezintă daca nişte cuvinte sunt prezente(eventual: de cate ori) într-un documentdacă se iau in considerare doi astfel de vectori, contează mai multcuvintele pe care le au în comun decât cuvintele care lipsesc din ambeledocumente, simultan

[email protected] (UNITBV) Curs 2 April 7, 2014 8 / 76

Page 9: Curs 2 Data Mining

Tipuri de seturi de date

Seturi de date de tip: înregistrare, de tip graf şi de tip secvenţă

Caracteteristici generale:

dimensionalitatea = numărul de atribute pe care obiectele-dată le au.Un numar de dimensiuni prea mare duce la “blestemuldimensionalităţii”; pentru multe dimensiuni se pot aplica tehnici dereducere a numarului de dimensiuni;caracterul rarefiat al datelor = procentul de date utile; de exemplu,pentru date asimetrice este numarul de valori nenule. Speculareaacestui caracter poate reduce drastic necesarul de memorie sau timpulde calcul;rezoluţia = scara la care se face raportarea valorilor; e posibil ca scăridiferite sa releve (sau sa ascundă) pattern-uri; ex: măsurători meteoraportate pe zile pot arăta iminenţa unei furtuni, dar la scală desăptămâni aşa ceva nu mai e vizibil.

[email protected] (UNITBV) Curs 2 April 7, 2014 9 / 76

Page 10: Curs 2 Data Mining

Seturi de date de tip înregistrare

cel mai des furnizate si frecvent utilizate in aplicatii: multime deobiecte cu un set predefinit de atribute

nu exista legatura intre inregistrari distincte

stocare: fisiere text (e.g. CSV), Excel, baze de date relationale –views

[email protected] (UNITBV) Curs 2 April 7, 2014 10 / 76

Page 11: Curs 2 Data Mining

Cazuri remarcabile de seturi de date inregistrare (1)

Tranzactii, date specifice cosurilor de cumparaturi:

exemplu: intr-un magazin, setul de produse cumparate de un client intimpul unei sesiuni de cumparaturi = continutul cosului decumparaturi

se analizeaza asocierea intre produsele individuale din tranzactii

posibilitate de reprezentare: indicator boolean care arata daca unprodus anume face sau nu parte dintr-un cos de cumparaturi

variatie: cate exemplare din produs au fost achizitionate (0, 1, . . . )

[email protected] (UNITBV) Curs 2 April 7, 2014 11 / 76

Page 12: Curs 2 Data Mining

Cazuri remarcabile de seturi de date inregistrare (2)

Matrice de date:

pentru cazul in care datele au acelasi set fix de atribute numerice

fiecare data in parte poate fi considerata un punct in spatiumultidimensional

fiecare atribut considerat este o dimensiune

este tipul de date standard pentru analiza statistica

nota: intre conceptul de dimensiune asa cum e definit in matematicasi cel de dimensiune—atribut pot exista diferente

[email protected] (UNITBV) Curs 2 April 7, 2014 12 / 76

Page 13: Curs 2 Data Mining

Cazuri remarcabile de seturi de date inregistrare (3)

Matrice de date rarefiate:

caz special al datelor matricedate asimetrice: in putine cazuri anumite trasaturi sunt prezente,predominanta este lipsa trasaturilorexemplu: tranzactii din cosuri de cumparaturi in care modelarea seface: obiectul (nu) a fost cumparatexemplu: documente cu continut dintr-un anumit lexic; pentru undocument se creeaza un vector numeric, care la fiecare cuvant areprecizat daca apare (eventual: de cate ori apare) sau nu = matriceadocument–termenin practica, tipuri de date specializate pentru date rare sunt benefice

[email protected] (UNITBV) Curs 2 April 7, 2014 13 / 76

Page 14: Curs 2 Data Mining

Seturi de date de tip graf

reprezentare convenabilă pentru cazurile:

graful reprezintă relaţii între obiecteobiectele însele sunt reprezentate ca graf

[email protected] (UNITBV) Curs 2 April 7, 2014 14 / 76

Page 15: Curs 2 Data Mining

Seturi graf - caz: datele reprezintă relaţii între obiecte

1 obiectele sunt reprezentate ca noduri în graf

2 relaţiile dintre obiecte sunt reprezentate sub formă de arce sau muchii

3 exemplu: pagini web care conţin legături către alte pagini

4 exemplu de algoritm ce foloseşte structura de graf:algoritmul PageRank

[email protected] (UNITBV) Curs 2 April 7, 2014 15 / 76

Page 16: Curs 2 Data Mining

Seturi graf - caz: obiectele-dată sunt grafuri

obiectele pot conţine subobiecte care sunt legate între ele

uneori nu doar legăturile sunt importante, ci şi forma lor: unghiuldintre muchii poate avea aceeaşi relevanţă ca şi legăturile însele;

exemplu: formulele chimice - benzen = C6H6

utilitate: se poate detecta care substructură apare mai des; sau dacăprezenta sau absenţa unor astfel de substructuri este legata deprezenţa/absenţa anumitor proprietăţi chimice.

domeniu aparte: “mineritul” substructurilor

[email protected] (UNITBV) Curs 2 April 7, 2014 16 / 76

Page 17: Curs 2 Data Mining

Seturi de tip secvenţă

atributele au relaţii care implică ordonare în timp sau spaţiu

subtipuri: date secvenţiale, secvenţă, serii de timp şi date spaţiale

[email protected] (UNITBV) Curs 2 April 7, 2014 17 / 76

Page 18: Curs 2 Data Mining

Seturi de tip secvenţă: date secvenţiale

numite şi date temporale

fiecare înregistrare are un atribut suplimentar de timp asociat

[email protected] (UNITBV) Curs 2 April 7, 2014 18 / 76

Page 19: Curs 2 Data Mining

Seturi de tip secvenţă: date secvenţă

setul de date entităţi individuale, precum secvenţe de cuvinte sau delitere;

similare cu cele secvenţiale, dar fără timp inclus

poziţia din secvenţă este importantă

exemplu: informaţia genetică este o secvenţă de nucleotide (gene)

aplicaţie: predicţia similarităţilor în structura şi funcţia genelor pebaza similarităţii dintre secvenţe

[email protected] (UNITBV) Curs 2 April 7, 2014 19 / 76

Page 20: Curs 2 Data Mining

Seturi de tip secvenţă: serii de timp

fiecare înregistrare e o serie de timp = o serie de măsurători efectuatela anumite momente de timp

exemplu: seturi de date de tip financiar, reprezentând valorile unorstocuri

exemplu: date meteo măsurate lunar

[email protected] (UNITBV) Curs 2 April 7, 2014 20 / 76

Page 21: Curs 2 Data Mining

Seturi de tip secvenţă: date spaţiale

cazul datelor care au atribute spaţiale sau areale

exemplu: date climatice raportate pe regiuni

exemplu: date adunate pentru scurgerea unui fluid — poziţiadiferitelor puncte este inregistrată

[email protected] (UNITBV) Curs 2 April 7, 2014 21 / 76

Page 22: Curs 2 Data Mining

Outline

1 Tipuri de dateAtribute şi măsurătoriTipuri de seturi de date

2 Calitatea datelorProbleme legate de măsurarea şi colectarea datelorCalitatea datelor din perspectiva aplicaţiilor

3 Preprocesarea datelorAgregareEşantionareReducerea dimensionalităţiiSelectarea subsetului de atributeCrearea de trăsăturiDiscretizare şi binarizareTransformarea de variabile

4 Măsuri de similaritate si deosebire

[email protected] (UNITBV) Curs 2 April 7, 2014 22 / 76

Page 23: Curs 2 Data Mining

Calitatea datelor

Presupunerea că datele pe baza cărora se face DM sunt de calitateperfectă este naivă

Prevenirea problemelor care duc la scăderea calităţii datelor nu este oopţiune pentru un data miner

Abordări:

detectarea şi corectarea erorilor = curăţarea datelor

construirea de algoritmi care să tolereze o calitate slabă a datelor

surse de probleme în calitatea datelor:

procesele de măsurareaplicaţiile folosite

[email protected] (UNITBV) Curs 2 April 7, 2014 23 / 76

Page 24: Curs 2 Data Mining

Calitatea datelor: zgomot

Zgomot: componentă aleatoare care se adaugă unui proces demăsurare

Exemplu: distorsiunea vocii unei persoane pe o linie telefonică slabă

Dacă eroarea apare mereu în acelaşi loc: artefact

(a) Două funcţii sinusoidale (b) Două funcţii sinusoidale + zgo-mot

[email protected] (UNITBV) Curs 2 April 7, 2014 24 / 76

Page 25: Curs 2 Data Mining

Calitatea datelor: precizie, abatere, acurateţe (1)

Definiţie

Precizie: apropierea valorilor rezultate prin măsurători repetate aleaceleiaşi cantităţi.

Definiţie

Abatere (eng: bias): o variaţie sistematică a măsurătorilor faţă decantitatea reală.

Exemplu: se măsoară o cantitate de 1 gram. Valorile obţinute sunt:{1.015, 0,990, 1.013, 1,001, 0.986}. Media este 1.001, deci abaterea este|1.001 − 1| = 0.001.

[email protected] (UNITBV) Curs 2 April 7, 2014 25 / 76

Page 26: Curs 2 Data Mining

Calitatea datelor: precizie, abatere, acurateţe (2)

Precizia este considerată abaterea standard:

σ =√

E [(X − E (X ))2] (1)

deci pentru datele de mai sus precizia este 0.013.

Definiţie

Acurateţea: apropierea măsurătorilor faţă de valoarea adevărată ce se vreaa fi măsurată.

[email protected] (UNITBV) Curs 2 April 7, 2014 26 / 76

Page 27: Curs 2 Data Mining

Calitatea datelor: anomalii

Anomaliile sunt obiecte cu caracteristici considerabil diferite faţă demajoritatea obiectelor din setul de date

Anomaliile (outliers) nu sunt zgomote, ci obiecte legitime

Utilitate: detectarea de nişe pe piaţă, detectarea fraudelor

[email protected] (UNITBV) Curs 2 April 7, 2014 27 / 76

Page 28: Curs 2 Data Mining

Calitatea datelor: valori lipsă

Cazuri: una sau mai multe valori de atribute lipsesc

Motive pentru lipsa valorilor:

informaţia nu este colectată — oamenii nu vor să spună vârsta saugreutateaatributele nu se pot aplica tot timpul tuturor obiectelor: copiii nu auvenituri

Operarea în aceste situaţii:

eliminarea obiectelor-dată sau a atributelor cu valori lipsăestimarea valorilor lipsăignorarea valorilor lipsă în timpul analizei

[email protected] (UNITBV) Curs 2 April 7, 2014 28 / 76

Page 29: Curs 2 Data Mining

Calitatea datelor: valori inconsistente; duplicare

Valori inconsistente:

Exemplu: oras si cod poştal precizate, dar codul poştal nu e conţinutîn oraş

Exemplu: typos, mărimi cu valori improprii (greutate negativă)

Operare: detectarea valorilor greşite şi corectarea folosind intervenţieumană

E necesară utilizarea surselor de date redundante sau a cunoştinţelorspecifice domeniului

Date duplicate:

Duplicarea poate să fie exactă sau aproape exactă

Exemplu: aceeaşi persoană cu adrese de email diferite

Procesul de curăţare = deduplicare

[email protected] (UNITBV) Curs 2 April 7, 2014 29 / 76

Page 30: Curs 2 Data Mining

Calitatea datelor din perspectiva aplicaţiilor

Din perspectiva aplicaţiilor, “datele au calitate bună dacă sunt potrivitepentru utilizarea intenţionată”

Caracterul oportun al datelor — dacă datele sunt perimate, atuncimodele şi pattern–urile obţinute sunt depăşite

Relevanţa — in cazul in care se vrea crearea de modele pentruaccidente rutiere, omiterea genului şi vârstei coducătorilor ducemodele cu acurateţe mică; altă situaţie este dată de eşantionareaneadecvată

Cunoştinţele apriori despre date — de exemplu, faptul ca anumiteatribute sunt puternic corelate sau construite unele pe baza altorapoate fi utilizată pentru reducerea redundanţei şi a dimensionalităţii;cunoaşterea preciziei datelor, a caracterului lor oportun sau a scalei demăsură e de cele mai mult ori esenţială.

[email protected] (UNITBV) Curs 2 April 7, 2014 30 / 76

Page 31: Curs 2 Data Mining

Outline

1 Tipuri de dateAtribute şi măsurătoriTipuri de seturi de date

2 Calitatea datelorProbleme legate de măsurarea şi colectarea datelorCalitatea datelor din perspectiva aplicaţiilor

3 Preprocesarea datelorAgregareEşantionareReducerea dimensionalităţiiSelectarea subsetului de atributeCrearea de trăsăturiDiscretizare şi binarizareTransformarea de variabile

4 Măsuri de similaritate si deosebire

[email protected] (UNITBV) Curs 2 April 7, 2014 31 / 76

Page 32: Curs 2 Data Mining

Scopul pasului de preprocesare

Strategii si tehnici complexe, ce pot cere până la 60% din timpul totalal procesului de extragere de cunoştinţe

Două variante:1 selectara obiectelor-dată şi a atributelor2 crearea/schimbarea de atribute

Variante de preprocesare:

agregareeşantionarereducerea dimensionalităţiiselectarea unui subset de atributecrearea de atributediscretizare şi binarizaretransformarea variabilelor

[email protected] (UNITBV) Curs 2 April 7, 2014 32 / 76

Page 33: Curs 2 Data Mining

Agregare (1)

Scop: combinarea a două sau mai multe atribute (sau obiecte)într–un singur atribut (sau obiect)

Scop:

reducerea cantităţii de dateschimbarea scalei: oraşele sunt agregate în regiuni, state, continentedate mai stabile: datele agregate au tendinţa de a avea variabilitatemai mică

[email protected] (UNITBV) Curs 2 April 7, 2014 33 / 76

Page 34: Curs 2 Data Mining

Agregare (2)

(a) Abaterea standard pentru precip-itatiile medii lunare

(b) Abaterea standard pentru precipitati-ile medii anuale

Figure 1: Datele agregate au tendinţa de a avea variabilitate mai mică

[email protected] (UNITBV) Curs 2 April 7, 2014 34 / 76

Page 35: Curs 2 Data Mining

Eşantionare (1)

principala tehnică folosită pentru selectarea datelor

în statistică, a fost folosită atât pentru investigaţii preliminare cât şipentru analiza finală a datelor

este folosită pentru că obţinerea întregului set de date este imposibilăsau costisitoare

în DM eşantionarea este folosită pentru că procesarea întregului setde date este consumatoare de timp

un eşantion este reprezentativ dacă are aproximativ aceleaşiproprietăţi de interes ca şi setul originar

utilizarea unui eşantion reprezentativ e aproape la fel de exactă cafolosirea întregului set de date

[email protected] (UNITBV) Curs 2 April 7, 2014 35 / 76

Page 36: Curs 2 Data Mining

Eşantionare (2): tipuri

Tipuri de eşantionare:

eşantionare aleatoare uniformă: avem o probabilitate egală de alegerea unui obiect anume

eşantionare fără înlocuire: dacă un obiect este selectat, atunci el estescos din populaţie

eşantionare cu înlocuire: obiectele nu sunt scoase din populaţie atuncicând sunt selectate; un acelaşi obiect poate fi selectat de mai mult deo dată

eşantionarea stratificată: se divid datele în partiţii (ex:femei/bărbaţi); din fiecare partiţie se extrage apoi eşantion, a.i.proportia din straturi sa fie aceeasi cu proportia din mulţimea iniţială.

[email protected] (UNITBV) Curs 2 April 7, 2014 36 / 76

Page 37: Curs 2 Data Mining

Eşantionare (3): Mărimea eşantionului

(a) Eşantion de 8000 depuncte

(b) Eşantion de 2000 depuncte

(c) Eşantion de 500 depuncte

[email protected] (UNITBV) Curs 2 April 7, 2014 37 / 76

Page 38: Curs 2 Data Mining

Determinarea mărimii eşantionului - exemplu

problemă: avem un set de date care constă dintr-un numar mic degrupuri, în fiecare grup e aproximativ acelaşi număr de obiectetrebuie extras un eşantion astfel încât din fiecare grup să fie cel puţinun element selectat“garantarea” se exprimă probabilist: care e numărul de date dineşantion astfel încât probabilitatea ca să fie adevărată proprietatea dela punctul anterior să depăşească un anumit prag?

(a) 10 grupuri de puncte (b) Probabilitatea deregăsire a măcar unui punctdin fiecare grup, în funcţiede mărimea eşantionului

[email protected] (UNITBV) Curs 2 April 7, 2014 38 / 76

Page 39: Curs 2 Data Mining

Reducerea dimensionalităţii

seturile de date pot avea un număr mare de atribute

apare fenomenul de “blestem al dimensionalităţii”: datele sunt rare înspaţiu multidimenional

valorile pentru densitate de probabilitate şi distanţe dintre puncte –critice pentru clustering şi detectarea de anomalii — devin nerelevante

soluţie: reducerea dimensionalităţii fără a pierde prea mult dininformaţie

beneficii: algoritmii de DM lucrează mai eficient pe dimensiuni maipuţine; modelele rezultate sunt mai simple, inteligibile

[email protected] (UNITBV) Curs 2 April 7, 2014 39 / 76

Page 40: Curs 2 Data Mining

Reducerea dimensionalităţii: blestemul dimensionalităţii

pe măsură ce dimensiunea creşte, datele devin mai rare în spaţiu cumulte dimensiuni

fiind rare, nu permit crearea de modele realiste

exemplu: pentru clasificare, s-ar putea să nu fie suficiente date pentrua construi un model ce asignează o etichetă unui obiect nou

rezultat: clasificarea are o rată de recunoaştere mică

[email protected] (UNITBV) Curs 2 April 7, 2014 40 / 76

Page 41: Curs 2 Data Mining

Reducerea dimensionalităţii: scop şi tehnici

Scopuri:

evitarea blestemului dimensionalităţiireducerea timpului de rulare necesar algoritmilor de DMdatele devin mai uşor de vizualizatpoate ajuta la eliminarea trăsăturilor irelevante sau reducereazgomotului

Tehnici folosite:

analiza componentelor principale (Principal Component Analysis)descompunerea valorilor principale (Singular Value Decomposition)alte metode: supervizate şi transformări neliniare

[email protected] (UNITBV) Curs 2 April 7, 2014 41 / 76

Page 42: Curs 2 Data Mining

Reducerea dimensionalităţii: analiza componentelorprincipale

Bazată pe tehnici de algebră liniarăEfect: schimbarea bazei astfel încât să se obţină direcţiile cu variaţiilemaximePaşi:

se determină vectorii şi valorile proprii pentru matricea de covarianţăvectorii proprii definesc noul spaţiuse selectează vectorii proprii care au valorile proprii asociate cele maimari

[email protected] (UNITBV) Curs 2 April 7, 2014 42 / 76

Page 43: Curs 2 Data Mining

Selectarea subsetului de atribute

motivaţie: de multe ori, în seturile de date pot exista atributeredundante (e.g. pret şi preţ cu taxe incluse) sau irelevante (e.g.id-uri)

unele din aceste atribute pot fi eliminate prin “bun simţ” sau princunoaştere apriori a (datelor) problemei

varianta ideală de lucru: se încearcă toate combinaţiile de trăsături;numărul de încercări ar fi deci: C1

n + C2n + · · · + Cn

n = 2n − 1 deciprohibitiv — brute force

variante:1 metode încorporate — algoritmul de DM însuşi decide ce atribute să se

folosească: e.g. arborii de decizie2 metode de filtrare — atributele sunt selectate înainte de a se aplica

algoritmul: e.g. selectarea atributelor pentru care corelaţia este minimăsau PCA

3 metode bazate pe încercare — se foloseşte un algoritm oarecare de DMşi se încearcă diferite subseturi de trăsături – dar nu brute force;

[email protected] (UNITBV) Curs 2 April 7, 2014 43 / 76

Page 44: Curs 2 Data Mining

Selectarea subsetului de atribute: realizare

Pentru selectarea subsetului de trăsături e nevoie de:

o măsură pentru evaluarea unui subset

o metodă de căutare pentru generarea unui nou subset de atribute

un criteriu de oprire

o procedură de validare

Alternativă pentru selectarea de atribute: ponderarea atributelor

atribute importante → ponderi mari; atribute nerelevante → ponderimici

ponderile se pot asocia pe baza cunoştinţelor asupra domeniului sauprin metode automate

[email protected] (UNITBV) Curs 2 April 7, 2014 44 / 76

Page 45: Curs 2 Data Mining

Crearea de trăsături

Scop: crearea de noi atribute pe baza celor existente (e.g. raportuldintre venituri şi cheltuieli, dintre masa corporală şi înălţime)

Noile atribute pot releva mai eficient informaţia ascunsă în date

Numarul atributelor noi obţinute poate fi mai mic decât la plecare

Metode:

Extragere de trăsăturiTransformarea datelor, utilizarea unui alt spaţiuConstruirea de trăsături

[email protected] (UNITBV) Curs 2 April 7, 2014 45 / 76

Page 46: Curs 2 Data Mining

Crearea de trăsături: extragerea de trăsături

crearea unui nou set de atribute pe baza celor existenteexemplu: fotografie → detectarea muchiilormetodele sunt strâns legate de domeniu — algoritmi de procesaregrafică, utilizarea unor variabile economice derivate etc.

(a) Imaginea iniţială (b) Imagine după “edge detection”

[email protected] (UNITBV) Curs 2 April 7, 2014 46 / 76

Page 47: Curs 2 Data Mining

Crearea de trăsături: transformarea datelor (1)

trecerea de la dimensiunile originare la un alt mod de reprezentarepoate releva pattern-uri

exemplu: trecerea de la coordonatele carteziene la cele polare

[email protected] (UNITBV) Curs 2 April 7, 2014 47 / 76

Page 48: Curs 2 Data Mining

Crearea de trăsături: transformarea datelor (2)

exemplu: analiza Fourier

pentru cazul în care ai o singură undă şi puţin zgomot se poatedetecta uşor care este forma undei

pentru mai multe forme de undă suprapuse şi zgomot adiţional:detectarea directă este imposibilă

transformata Fourier permite obţinere explicită a frecvenţelor

(a) Doua funcţii si-nusoidale de frecvenţediferite

(b) Doua funcţii sinu-soidale plus zgomot

(c) Spectrul de putere,obtinut după aplicareatransformatei Fourier

[email protected] (UNITBV) Curs 2 April 7, 2014 48 / 76

Page 49: Curs 2 Data Mining

Crearea de trăsături: construirea de noi atribute

uneori, atributele originare pot să aibă informaţia necesară

dar formatul acestor date este neadecvat pentru algoritmul de DM

exemplu: pentru reţele neurale intrarea este numerică, dar datelecurente au şi valori nominale

exemplu de trăsătură derivată: densitatea = masa / volumul

crearea de noi trăsături necesită cunoaşterea domeniului problemei

[email protected] (UNITBV) Curs 2 April 7, 2014 49 / 76

Page 50: Curs 2 Data Mining

Discretizare şi binarizare

unii algoritmi cer ca datele să fie în formă de atribute categoriale

algoritmii de determinare a asocierilor cer date binare

apare nevoia de a transforma atribute continue în atribute discrete(discretizare) sau chiar binare (binarizare)

[email protected] (UNITBV) Curs 2 April 7, 2014 50 / 76

Page 51: Curs 2 Data Mining

Binarizare

m valori → fiecare valoare iniţială se transformă într–un număr întregdin intervalul [0, m − 1] şi apoi se foloseşte transcrierea în baza 2

dacă atributele sunt ordinale, atunci trebuie păstrată ordinea printransformare

exemplu: {slab, mediu, bun} →{(x1 = 0, x2 = 0), (x1 = 0, x2 = 1), (x1 = 1, x2 = 0)}⌈log2 m⌉ biţi folosiţi

binarizare asimetrică: pentru m clase se folosesc m biţi; fiecare bitarată prezenţa sau absenţa unei trăsături

exemplu: {slab, mediu, bun} → (x1 = 0, x2 = 0, x3 = 1), (x1 =0, x2 = 1, x3 = 0), (x1 = 1, x2 = 0, x3 = 0)

[email protected] (UNITBV) Curs 2 April 7, 2014 51 / 76

Page 52: Curs 2 Data Mining

Discretizare a atributelor continue

procesul de discretizare este dependent de date şi de tipul problemei

paşi:

se decide numărul de categorii ce se produc;se decide modul de asociere între valorile continue şi cele discrete

exemplu: se sortează datele, se efectuează n − 1 tăieturi în interval şipentru fiecare subinterval se asignează o etichetă

[email protected] (UNITBV) Curs 2 April 7, 2014 52 / 76

Page 53: Curs 2 Data Mining

Discretizare nesupervizată

intervalele pot fi de lăţime egală sau considerate astfel încât săprezinte frecvenţe egalemetode de clustering, e.g. K -meansinspectare vizuală a datelor

(a) Datele originare (b) Discretizare cu lăţimeegală

(c) Discretizare cu frecvenţăegală

(d) Discretizare cu K–means

[email protected] (UNITBV) Curs 2 April 7, 2014 53 / 76

Page 54: Curs 2 Data Mining

Discretizare supervizată

utilizarea de informaţie suplimentară – etichetele de clasă – poateduce la o discretizare mai bună

conceptual: discretizarea să se facă astfel încât să se maximizeze“puritatea” intervalelor

metode statistice: intervale mai mici se unesc astfel încât să nu sedepăşească un prag de puritateexemplu:

k clasemi numărul de valori din intervalul i , 1 ≤ i ≤ n, n fiind numărul deintervalemij numărul de valori de clasa j , 1 ≤ j ≤ k, 1 ≤ i ≤ nentropia ei a intervalului i se calculează cu:

ei = −k

i=1

pij log2 pij , 1 ≤ i ≤ n

unde pij = mij/mi

entropia toală a unei partiţii este e =∑n

i=1 wiei unde wi = mi/m

[email protected] (UNITBV) Curs 2 April 7, 2014 54 / 76

Page 55: Curs 2 Data Mining

Atribute categoriale cu prea multe atribute

exemplu: o multitudine de departamente

se pot unifica pe domenii: inginerie, ştiinţe sociale, biologie

altfel: gruparea poate fi făcută în conjuncţie cu un algoritm de DataMining în care se urmăreşte îmbunătăţirea rezultatului de clasificare

[email protected] (UNITBV) Curs 2 April 7, 2014 55 / 76

Page 56: Curs 2 Data Mining

Transformarea de variabile

transformare care se aplică la toate valorile unei variabile

exemplu: dacă doar amplitudinea unei valori este importantă, atuncise poate considera valoarea absolută a variabilei

funcţii folosite: ex , log, funcţia putere

funcţii complexe: normalizare

[email protected] (UNITBV) Curs 2 April 7, 2014 56 / 76

Page 57: Curs 2 Data Mining

Transformarea de variabile: funcţii simple

√x , log x , exp(x), 1

x

unele transformări pot duce de la valori care nu sunt distribuitenormal la distribuţie Gaussiană

pentru datele care prezintă domeniu mare de valori: scara logaritmică(x → log(x)) poate fi mai adecvată

exemplu: transferuri de date de 109, 108, 1000, 10 octeti; printransformare magnitudinea nu mai e importantă, se ajunge la valoricomparabile: 9, 8, 3, 1.

aplicarea trebuie făcută în cunoştinţă de cauză: transformarea x → 1x

e o funcţie de monotonie descrescătoare;

[email protected] (UNITBV) Curs 2 April 7, 2014 57 / 76

Page 58: Curs 2 Data Mining

Transformarea de variabile: normalizare

în statistică: dacă x este media unui atribut şi sx e abaterea standard:

sx =√

E [(x − x)2]

atunci transformarea x → x−xsx

creează o nouă variabilă cu media zeroşi abaterea 1; operaţia se numeşte standardizare.

exemplu: persoane cu variabilele: venitul anual şi înălţimea;diferenţele între înălţimi sunt mici comparativ cu diferenţele întrevenituri; diferenţele între venituri ar domina distanţa între doi oameni,dacă s–ar calcula direct pe baza valorilor; standardizarea reduceasemenea diferenţe de magnitudine

problemă: abaterea pătratică medie e influenţată prea uşor de dateextreme, outliers; uneori se consideră abaterea absolută medie σa:σa =

∑mi=1 |xi − µ|/m unde µ e media sau mediana

[email protected] (UNITBV) Curs 2 April 7, 2014 58 / 76

Page 59: Curs 2 Data Mining

Outline

1 Tipuri de dateAtribute şi măsurătoriTipuri de seturi de date

2 Calitatea datelorProbleme legate de măsurarea şi colectarea datelorCalitatea datelor din perspectiva aplicaţiilor

3 Preprocesarea datelorAgregareEşantionareReducerea dimensionalităţiiSelectarea subsetului de atributeCrearea de trăsăturiDiscretizare şi binarizareTransformarea de variabile

4 Măsuri de similaritate si deosebire

[email protected] (UNITBV) Curs 2 April 7, 2014 59 / 76

Page 60: Curs 2 Data Mining

Similaritate şi deosebire

Similaritate

Măsură numerică prin care se arată cât de asemănătoare sunt douăobiecteCu cât e mai mare similaritatea, cu atât obiectele sunt considerate maiapropiateDeseori luate cu valori în intervalul [0, 1]

Deosebire

Măsură care arată cât de diferite sunt două obiecteValoare mică atunci când obiectele sunt asemănătoareDeosebirea minimă este de cele mai multe ori considerată 0

Proximitate: similaritate sau deosebire

[email protected] (UNITBV) Curs 2 April 7, 2014 60 / 76

Page 61: Curs 2 Data Mining

Similaritate şi deosebire

[email protected] (UNITBV) Curs 2 April 7, 2014 61 / 76

Page 62: Curs 2 Data Mining

Distanţe: distanţa Euclidiană

Distanţă (metrică): un tip special de măsură de deosebire — satisfacenişte axiome

Distanţa Euclidiană

d(p, q) =

n∑

k=1

(pk − qk)2

unde p = (p1, . . . , pn), q = (q1, . . . , qn)

Se face standardizare dacă scalele diferă

[email protected] (UNITBV) Curs 2 April 7, 2014 62 / 76

Page 63: Curs 2 Data Mining

Distanţe vs. măsuri de similaritate/deosebire

Axiomele distanţei:

d(p, q) ≥ 0 ∀p, q şi d(p, q) = 0 ⇔ p = q – distanţa este pozitivdefinităd(p, q) = d(q, p) – simetried(p, q) ≤ d(p, r) + d(r , q) – inegalitatea triunghiului

Axiomele similarităţii:

s(p, q) = 1 dacă şi numai dacă p = qs(p, q) = s(q, p) pentru toţi p şi q

[email protected] (UNITBV) Curs 2 April 7, 2014 63 / 76

Page 64: Curs 2 Data Mining

Distanţe: exemplu

(a) Patru puncte bidimensionale (b) Coordonatele punctelor

(c) Distanţe între perechi de puncte

[email protected] (UNITBV) Curs 2 April 7, 2014 64 / 76

Page 65: Curs 2 Data Mining

Distanţa Minkowski

Distanţa Minkowski este generalizare a distanţei Euclidiene

d(p, q) =

{

n∑

k=1|pk − qk |r

}1r

r : parametru

r = 1: distanţa L1, Manhattan, taxicab

caz: pentru pk , qk biţi, L1 numărul de poziţii pe care există diferenţeîntre biţi

r = 2: distanţa Euclidiană, L2

r = ∞: distanţa supremum, Lmax sau L∞ este diferenţa maximă întreatributele de pe poziţii corespunzătoare ale vectorilor p, q

[email protected] (UNITBV) Curs 2 April 7, 2014 65 / 76

Page 66: Curs 2 Data Mining

Distanţa Mahalanobis

Formula: dM(p, q) = (p − q)Σ−1(p − q)t

Σ este matricea de covarianţă

Σjk = 1n−1

n∑

i=1(Xij − X j)(Xik − X k)

distanţa se foloseşte acolo unde atributele sunt corelate

[email protected] (UNITBV) Curs 2 April 7, 2014 66 / 76

Page 67: Curs 2 Data Mining

Măsuri de deosebire nemetrice: exemple

Diferenţa de mulţimi: A, B mulţimi finite,dis(A, B) = |A − B| + |B − A|Exemplu: A = {1, 2, 3, 4}, B = {2, 3, 4}, A − B = {1}, B − A = ∅,sim(A, B) = 1 + 0 = 1

Diferenţa de timp:

d(t1, t2) =

{

t2 − t1 dacă t1 ≤ t2

24 + (t2 − t1) dacă t1 > t2

Exemplu: distanţa dintre ora 1 PM şi 2 PM este de o oră; distanţadintre 2 PM şi 1 PM este de 23 de ore.

[email protected] (UNITBV) Curs 2 April 7, 2014 67 / 76

Page 68: Curs 2 Data Mining

Exemple de similarităţi şi pentru vectori binari

M00 = numărul de atribute de pe poziţii k unde pk = qk = 0

M11 = numărul de atribute de pe poziţii k unde pk = qk = 1

M01 = numărul de atribute de pe poziţii k unde pk = 0, qk = 1

M10 = numărul de atribute de pe poziţii k unde pk = 1, qk = 0

Simple matching coefficient:

SMC =M00 + M11

M00 + M11 + M01 + M10

problemă: pentru valori asimetrice valorile de 0 pot domina şi atuncisimilaritatea are valoare mare, datorită absenţelor masive ale unorcaracteristici

Coeficientul Jaccard rezolvă problema de mai sus, ignorand potrivirilede 0:

J =M11

M01 + M10 + M11

[email protected] (UNITBV) Curs 2 April 7, 2014 68 / 76

Page 69: Curs 2 Data Mining

Exemple numerice

p = (1, 0, 0, 0, 0, 0, 0, 0, 0, 0)

q = (0, 0, 0, 0, 0, 0, 1, 0, 0, 1)

M01 = 2, M10 = 1, M00 = 7, M11 = 0

SMC = 0+72+1+0+7 = 0.7

J = 02+1+0 = 0

[email protected] (UNITBV) Curs 2 April 7, 2014 69 / 76

Page 70: Curs 2 Data Mining

Similaritatea cosinus

pentru cazul în care d1 şi d2 sunt vectorii de frecvenţă ai unor cuvintepentru două documente, similaritatea cosinus este

cos(d1, d2) =d1 · d2

‖d1‖‖d2‖ =d1

‖d1‖ · d2

‖d2‖

unde · reprezintă produsul scalar: x · y =∑n

k=1 xkyk

dacă cei doi vectori formează unghi de 0◦, atunci cosinusul este 1;dacă cei doi vectori sunt perpendiculari i.e. nu au nici măcar unelement în comun, atunci cosinusul este 0

exemplu: d1 = (3, 2, 0, 5, 0, 0, 0, 2, 0, 0), d2 = (1, 0, 0, 0, 0, 0, 0, 1, 0, 2);d1 · d2 = 3 · 1 + 2 · 0 + · · · + 0 · 2;‖d1‖ =

√3 · 3 + 2 · 2 + · · · + 0 · 0 = 6.48;

‖d2‖ =√

1 · 1 + 0 · 0 + · · · 2 · 2 = 2.24;cos(d1, d2) = 0.31

[email protected] (UNITBV) Curs 2 April 7, 2014 70 / 76

Page 71: Curs 2 Data Mining

Coeficientul Jaccard extins

aka: coeficientul Tanimoto

formula:EJ(x, y) =

x · y

‖x‖2 + ‖y‖2 − x · y

se reduce la coeficientul Jaccard în cazul atributelor binare

[email protected] (UNITBV) Curs 2 April 7, 2014 71 / 76

Page 72: Curs 2 Data Mining

Corelaţia Pearson

formula:

cor(x, y) =cov(x, y)

as(x) · as(y)

cov(x, y) = 1n−1

n∑

k=1(xk − x)(yk − y)

as(x) =

1n−1

n∑

k=1(xk − x)2

as(y) =

1n−1

n∑

k=1(yk − y)2

x e media lui x, x = 1n

n∑

k=1xk

y e media lui y, y = 1n

n∑

k=1yk

[email protected] (UNITBV) Curs 2 April 7, 2014 72 / 76

Page 73: Curs 2 Data Mining

Corelaţia Pearson: vizualizarea corelaţiilor

cor(x, y) ∈ [−1, 1]corelaţie de ±1 reprezintă legătură liniară între cei doi vectori:xk = ayk + b, sgn(a) = sgn(cor)corelaţia 0 poate exista pentru variabile ce sunt corelate neliniar:x = (−3, −2, −1, 0, 1, 2, 3), y = (9, 4, 1, 0, 4, 9), cor(x, y) = 0 daryk = x2

k deci x şi y sunt corelate — dar nu liniar corelate

[email protected] (UNITBV) Curs 2 April 7, 2014 73 / 76

Page 74: Curs 2 Data Mining

Combinarea de similarităţi (1)

Problemă: uneori atributele sunt eterogene dar se cere o măsură desimilaritate/deosebire pentru două astfel de obiecte

Soluţie:1 pentru atributul k se calculează o similaritate sk în intervalul [0, 1]2 se defineşte o variabilă indicator δk pentru atributul k astfel:

δk =

0 dacă atributul k este asimetric şi cel puţin unul din

obiecte are valoarea 0 pe poziţia k1 altfel

3 Se calculează similaritatea globală dintre două obiecte cu formula:

sim(x, y) =

n∑

k=1

δksk(x, y)

n∑

k=1

δk

[email protected] (UNITBV) Curs 2 April 7, 2014 74 / 76

Page 75: Curs 2 Data Mining

Combinarea de similarităţi (2)

Se poate să nu acordăm diferitelor atribute aceeaşi importanţă:

sim(x, y) =

n∑

k=1wkδksk(x, y)

n∑

k=1δk

unde wk sunt ponderi

Pentru distanţa Minkowski:

d(x, y) =

{

n∑

k=1

wk |xk − yk |r}

1r

[email protected] (UNITBV) Curs 2 April 7, 2014 75 / 76

Page 76: Curs 2 Data Mining

Care distanţă e mai potrivită?

“Metric searching”: domeniu în sine

exemplu: Distance metric learning, with application to clustering withside-information, Eric Xing, Andrew Y. Ng, Michael Jordan, andStuart Russell, In NIPS 15, 2003, aici.

[email protected] (UNITBV) Curs 2 April 7, 2014 76 / 76