curs 5 data mining

78
Introducere ˆ ın Data Mining Clasificare: tehnici alternative Lucian Sasu, Ph.D. Universitatea Transilvania din Bra¸ sov, Facultatea de Matematic˘ si Informatic˘ a March 29, 2012 [email protected] (UNITBV) Curs 5 March 29, 2012 1 / 78

Upload: lucian-sasu

Post on 15-Jun-2015

594 views

Category:

Education


7 download

TRANSCRIPT

Page 1: Curs 5 Data Mining

Introducere ın Data MiningClasificare: tehnici alternative

Lucian Sasu, Ph.D.

Universitatea Transilvania din Brasov, Facultatea de Matematica si Informatica

March 29, 2012

[email protected] (UNITBV) Curs 5 March 29, 2012 1 / 78

Page 2: Curs 5 Data Mining

Outline

1 Clasificatori bazati pe reguli

2 Clasificatori bazati pe vecinatate

3 Retele neurale artificiale

4 Support Vector Machine

5 Metode de tip ansamblu

[email protected] (UNITBV) Curs 5 March 29, 2012 2 / 78

Page 3: Curs 5 Data Mining

Clasificatori bazati pe reguli: generalitati

Tehnica de clasificare a ınregistrarilor folosind o colectie de reguli deforma: “daca . . . atunci. . . ”

Notatie:ri : (conditie)→ y

conditie: antecedentul sau preconditiay : consecventul; pentru clasificare, y este eticheta de clasa

Forma generala a unei preconditii:

conditie = (A1 op1 v1) ∧ (A2 op2 v2) ∧ · · · ∧ (Ak opk vk)

unde Aj este un atribut, vj este o valoare din domeniul de valori aleatributului Aj , opj este un operator din multimea {=, 6=, <,>,≤,≥}

[email protected] (UNITBV) Curs 5 March 29, 2012 3 / 78

Page 4: Curs 5 Data Mining

Clasificatori bazati pe reguli: generalitati

Figure: Set de date pentru vertebrate

R1: (Give Birth = no) ∧ (Can Fly = yes) → BirdsR2: (Give Birth = no) ∧ (Live in Water = yes) → FishesR3: (Give Birth = yes) ∧ (Blood Type = warm) → MammalsR4: (Give Birth = no) ∧ (Can Fly = no) → ReptilesR5: (Live in Water = sometimes) → Amphibians

[email protected] (UNITBV) Curs 5 March 29, 2012 4 / 78

Page 5: Curs 5 Data Mining

Clasificatori bazati pe reguli: generalitati

O regula r acopera o ınregistrare x daca atributele lui x satisfacantecedentul regulii

Alternativ: spunem ca x activeaza sau declanseaza regula r

R1: (Give Birth = no) ∧ (Can Fly = yes) → BirdsR2: (Give Birth = no) ∧ (Live in Water = yes) → FishesR3: (Give Birth = yes) ∧ (Blood Type = warm) → MammalsR4: (Give Birth = no) ∧ (Can Fly = no) → ReptilesR5: (Live in Water = sometimes) → Amphibians

Regula R1 acopera prima ınregistrare ⇒ Class = Birds

Regula R3 acopera a doua ınregistrare ⇒ Class = Mammals

[email protected] (UNITBV) Curs 5 March 29, 2012 5 / 78

Page 6: Curs 5 Data Mining

Clasificatori bazati pe reguli: generalitati

Calitatea unei reguli de clasificare se masoara cu: acoperirea siacuratetea

Consideram un set de date D si o regula de clasificare r : A→ y

Acoperirea unei reguli este fractiunea deınregistrari (frecventa relativa aınregistrarilor) care satisfac antecedentulregulii: acoperire = |A|/|D| unde |A| estenumarul de ınregistrari care satisfacantecedentul regulii r , |D| este numarul dedate din setul D

Acuratetea unei reguli este fractiunea deınregistrari care satisfac atat antecedentulcat si consecventul regulii, raportata lanumarul de ınregistrari ce declanseaza pe r :acuratete(r) = |A ∩ y |/|A|

Regula: Status = Single →No: acoperirea = 40%,acuratetea = 50%

[email protected] (UNITBV) Curs 5 March 29, 2012 6 / 78

Page 7: Curs 5 Data Mining

Clasificatori bazati pe reguli: mod de functionare

R1: (Give Birth = no) ∧ (Can Fly = yes) → BirdsR2: (Give Birth = no) ∧ (Live in Water = yes) → FishesR3: (Give Birth = yes) ∧ (Blood Type = warm) → MammalsR4: (Give Birth = no) ∧ (Can Fly = no) → ReptilesR5: (Live in Water = sometimes) → AmphibiansSet de date pentru clasificare:

Prima ınregistrare activeaza regula R3, deci animalul este clasificat camamifer

A doua ınregistrare activeaza atat regula R4 cat si R5 ⇒ ??

A treia ınregistrare nu declanseaza nicio regula ⇒ ??

[email protected] (UNITBV) Curs 5 March 29, 2012 7 / 78

Page 8: Curs 5 Data Mining

Clasificatori bazati pe reguli: mod de functionare

Reguli mutual excluzive: daca nicio ınregistrare nu activeaza douareguli simultan, precum la testoasa

Altfel zis: o ınregistrare este acoperita de cel mult o regula

Reguli exhaustive: daca fiecare combinatie de valori ale atributeloreste acoperita de o regula

Altfel zis: fiecare ınregistrare este clasificata de cel putin o regula

Impreuna: fiecare ınregistrare este acoperita de exact o regula

[email protected] (UNITBV) Curs 5 March 29, 2012 8 / 78

Page 9: Curs 5 Data Mining

Clasificatori bazati pe reguli: mod de functionare

Daca un set de reguli nu este exhaustiv: adaugam o regula implicita:

rd : {} → yd

unde antecedentul este vid, consecventul este clasa implicita, de ex.clasa majoritara din ınregistrarile care nu sunt acoperite de celelaltereguli

Daca regulile nu sunt mutual excluzive: o ınregistrare poate declansamai multe reguli, posibil cu consecvent diferit

Solutii:

Ordonarea setului de reguliFolosirea unei scheme de votare

[email protected] (UNITBV) Curs 5 March 29, 2012 9 / 78

Page 10: Curs 5 Data Mining

Clasificatori bazati pe reguli: prin votare

Setul de reguli nu este ordonat ın niciun fel

Se permite ca o ınregistrare sa se potriveasca mai multor reguli

Se considera consecventul fiecarei reguli ca fiind un vot pentru o clasaparticulara

Voturile pot fi eventual ponderate, de exemplu prin acuratetea regulii

Avantaj: sansa de eroare mai mica ın clasificare ce s-ar datora uneiordonari inadecvate a regulilor

Dezavantaj: intensiv computational, deoarece clasificarea ınseamnaconsultarea tuturor regulilor din multimea de reguli

Alt posibil dezavantaj: necesitatea de a rezolva situatiile de balotaj

[email protected] (UNITBV) Curs 5 March 29, 2012 10 / 78

Page 11: Curs 5 Data Mining

Clasificatori bazati pe reguli ordonate

Regulile sunt ordonate pe baza prioritatilor lor

Setul de reguli ordonat se mai numeste si lista de decizie

Cand o ınregistrare este prezentata clasificatorului:

este asignata etichetei de clasa ce apare ca si consecvent al primeireguli ce acopera ınregistrareadaca nu se activeaza nicio regula se poate folosi clasa (regula) implicita

[email protected] (UNITBV) Curs 5 March 29, 2012 11 / 78

Page 12: Curs 5 Data Mining

Clasificatori bazati pe reguli ordonate: scheme de ordonare

Sisteme bazate pe ordonarea regulilor:

regulile individuale sunt sortate dupa o masura a calitatii loro ınregistrare este clasificata de cea mai buna regula care o acoperadezavantaj: greu de interpretat, pentru ca explicarea regulii aplicatetrebuie sa includa negarea aplicarii regulilor ce o preced

Sisteme bazate pe ordonarea claselor:

regulile sunt grupate pe clase (etichetele care se prezic)clasele sunt cele ordonate, ın finalordonarea regulilor dintr-o clasa nu este importanta (de ce?)interpretarea regulilor este ceva mai usoara decat la cazul precedentmajoritatea clasificatorilor bazati pe reguli folosesc ordonarea claselor(e.g. C4.5rules, RIPPER)

[email protected] (UNITBV) Curs 5 March 29, 2012 12 / 78

Page 13: Curs 5 Data Mining

Clasificatori bazati pe reguli ordonate: scheme de ordonare

Figure: Ordonare la nivel de reguli vs. ordonare la nivel de clase

[email protected] (UNITBV) Curs 5 March 29, 2012 13 / 78

Page 14: Curs 5 Data Mining

Construirea de clasificatori bazati pe reguli

Metode directe

Extrag reguli direct din datee.g.: RIPPER, CN2, algoritmul 1R al lui Holte

Metode indirecte

extrag reguli din alte modele de clasificare (e.g. arbori de decizie, reteleneurale, k-NN etc.)exemplu: C4.5rules, extragerea de reguli din retele Fuzzy ARTMAP

[email protected] (UNITBV) Curs 5 March 29, 2012 14 / 78

Page 15: Curs 5 Data Mining

Metoda directa: acoperirea secventiala

Setul de reguli creste dupa o strategie greedy

Algoritmul extrage regulile pe clase = sistem bazat pe ordonareaclaselor

Criteriul pentru alegerea efectiva a clasei poate fi bazat pe:

procentajul de date pe care ıl acopera fiecare clasacostul datorat clasificarii gresite

Schita algoritmului:1 Porneste de la o ordonare a claselor Y = {y1, y2, . . . , yk}2 Pentru fiecare clasa y1, y2, . . . , yk−1:

1 Porneste de la un set de reguli gol pentru clasa curenta

2 Creaza o regula folosind functia Learn-One-Rule

3 Elimina ınregistrarile din setul de antrenare ce sunt acoperite de regula

creata

4 Repeta pasii 2 si 3 pana se ındeplineste un criteriu de oprire

[email protected] (UNITBV) Curs 5 March 29, 2012 15 / 78

Page 16: Curs 5 Data Mining

Metoda directa: acoperirea secventiala

Exemplu:

[email protected] (UNITBV) Curs 5 March 29, 2012 16 / 78

Page 17: Curs 5 Data Mining

Metoda directa: acoperirea secventiala

Exemplu (cont):

[email protected] (UNITBV) Curs 5 March 29, 2012 17 / 78

Page 18: Curs 5 Data Mining

Metoda directa: acoperirea secventiala

Observatii:

Pot exista mai multe reguli care se pot urma la un moment dat; sefoloseste un criteriu care permite alegerea celei mai bune reguli din celeconsiderate (greedy)Toate ınregistrarile care apartin clasei curente sunt considerate“pozitive”, restul de ınregistrari — negativeOdata aleasa o regula, se elimina toate ınregistrarile acoperite de acearegula

Elemente ce trebuie discutate:

Functia Learn-One-Rule

Strategia de creare a regulilorEliminarea instantelorEvaluarea regulilorCriterii de oprireRetezarea regulilor

[email protected] (UNITBV) Curs 5 March 29, 2012 18 / 78

Page 19: Curs 5 Data Mining

Acoperirea secventiala: functia Learn-One-Rule

Obiectiv: extragerea unei reguli de clasificare

Se doreste ca o regula sa acopere cat mai multe exemple pozitive (ceapartin clasei curent iterate)

Posibil ca aceasta regula sa acopere si ınregistrari negative – si ınacest caz ar trebui sa fie cat mai putine

Gasirea unei reguli optimale este problema computational intensiva

Euristica folosita este de tip Greedy

[email protected] (UNITBV) Curs 5 March 29, 2012 19 / 78

Page 20: Curs 5 Data Mining

Acoperirea secventiala: strategia de creare a regulilor

Doua strategii larg folosite:de la general la specificde la specific la general

Strategia “de la general la specific”:se pleaca de la regula implicita r : {} → y

regula are o calitate slaba, acoperind toate ınregistrarile ramase ın setulde antrenarese adauga succesiv conditii ın antecedent pentru a creste calitateareguliiprocesul continua pana cand se ındeplineste un criteriu de oprire (e.g.criteriul adaugat nu ımbunatateste semnificativ clasificarea)

Figure: Strategia “de la general la specific”

[email protected] (UNITBV) Curs 5 March 29, 2012 20 / 78

Page 21: Curs 5 Data Mining

Acoperirea secventiala: strategia de creare a regulilor

Strategia “de la specific la general”:

Una din ınregistrarile pozitive este aleasa aleatorRegula se generalizeaza succesiv prin eliminarea de conditii dinconsecventPasul se repeta pana cand se ındeplineste un criteriu de oprire

Figure: Strategia “de la specific la general”

[email protected] (UNITBV) Curs 5 March 29, 2012 21 / 78

Page 22: Curs 5 Data Mining

Acoperirea secventiala: eliminarea instantelor

De ce se elimina instantele acoperite de o regula?

Altfel, data viitoare urmatoarea regula ar fi aceeasi ca si cea curenta

De ce eliminam instantele pozitive acoperite de regula curenta?

Daca ar fi pastrate ınregistrarile pozitive acoperite de regula curenta,atunci ar aparea o supraestimare a acuratetei uneia din regulilecandidat urmatoare, ın detrimentul altor reguli candidat

De ce eliminam instantele negative acoperite de regula curenta?

Altfel ar aparea o subestimare a acuratetei uneia din regulile candidaturmatoare, ın detrimentul altora

(a se vedea bibliografia pentru detaliere si exemplu grafic)

[email protected] (UNITBV) Curs 5 March 29, 2012 22 / 78

Page 23: Curs 5 Data Mining

Acoperirea secventiala: evaluarea regulilor

Trebuie date criterii care spun care dintre conditii se adauga la (sauelimina din) antecedent pentru a obtine o regula mai buna

Alegere aparent evidenta pentru functia de utilitate a unei reguli:acuratetea

Contraexemplu:

set de antrenare cu 60 pozitive si 100 negativeR1: acopera 50 pozitive si 5 negative; acuratete 90.9%R2: 2 pozitive si niciuna negativa; acuratete 100%totusi, R1 e mai buna decat R2, deoarece acopera mai multeınregistrari; acuratetea lui R2 este ınselatoare si poate fi semn desupra–specializare, ceea ce poate induce o generalizare slaba

[email protected] (UNITBV) Curs 5 March 29, 2012 23 / 78

Page 24: Curs 5 Data Mining

Acoperirea secventiala: evaluarea regulilor

Alte metrici:

Laplace =f+ + 1

n + k(1)

m − estimare =f+ + kp+

n + k(2)

n (resp. f+) = numarul de exemple (resp. exemple pozitive) acoperitede regula

k = numarul total de clase

p+ = probabilitatea apriori pentru clasa pozitiva (curenta)

daca acoperirea regulii este mare, atunci ambele metrici tind catreacuratetea regulii

[email protected] (UNITBV) Curs 5 March 29, 2012 24 / 78

Page 25: Curs 5 Data Mining

Acoperirea secventiala: criteriul de oprire

Calculeaza castigul adus de noua regula

Daca nu e suficient de mare, atunci te opresti cu regula aici

[email protected] (UNITBV) Curs 5 March 29, 2012 25 / 78

Page 26: Curs 5 Data Mining

Acoperirea secventiala: retezarea regulilor

Scopul: cresterea puterii de generalizare

Proces similar cu retezarea aposteriori pentru arbori de decizie

Retezare pentru reducerea erorii:

Se sterge una din conditiile din antecedentul reguliiSe compara ratele de eroare ınainte si dupa regula, pe un set de validareDaca eroarea creste, atunci se face retezare: elimina conditia curenta

[email protected] (UNITBV) Curs 5 March 29, 2012 26 / 78

Page 27: Curs 5 Data Mining

Metode indirecte pentru construirea de reguli

Se genereaza regulile de clasificare pornind de la alte modele declasificare, pentru care se face extragere de reguli (proces de “reverseengineering”)

Ex: pentru un arbore de decizie, neretezat

Figure: Convertirea unui arbore de decizie la reguli de clasificare

conditiile de-a lungul caii de la radacina catre frunza alcatuiescconsecventuleticheta frunzei este consecventul

Daca se pleaca de la un arbore neretezat, setul de reguli obtinut esteexhaustiv si mutual excluziv

Uneori setul de reguli poate fi simplificat

[email protected] (UNITBV) Curs 5 March 29, 2012 27 / 78

Page 28: Curs 5 Data Mining

Metode indirecte: C4.5rules

Se pleaca de la un arbore de decizie neretezat obtinut prin algoritmulC4.5

Pentru fiecare regula r : A→ y

considera o regula alternativa r ′ : A′ → y unde A′ se obtine din A prineliminarea unei conditii din A

se compara ratele de eroare pesimista a lui r si r ′

se reteaza daca vreuna din variantele r ′ are o eroare pesimista mai micase repeta pana cand nu se mai poate ımbunatati eroarea de generalizare

[email protected] (UNITBV) Curs 5 March 29, 2012 28 / 78

Page 29: Curs 5 Data Mining

Metode indirecte: C4.5rules

Se face gruparea regulilor obtinute pe clase ⇒ subseturi de reguli

Fiecare subset este o colectie de reguli cu acelasi consecvent

Se calculeaza lungimea descrierii aferenta fiecarui subset de reguli

Lungimea descrierii = L(eroare) + g ·L(model)

L(eroare) este numarul de biti necesari pentru reprezentareaınregistrarilor clasificate gresitL(model) este numarul de biti necesar reprezentarii modelului claseicurenteg este dependent de numarul de atribute redundante din model

[email protected] (UNITBV) Curs 5 March 29, 2012 29 / 78

Page 30: Curs 5 Data Mining

Metode indirecte: C4.5 vs. C4.5rules

Set de date:

[email protected] (UNITBV) Curs 5 March 29, 2012 30 / 78

Page 31: Curs 5 Data Mining

Metode indirecte: C4.5 vs. C4.5rules

Figure: Arbore C4.5 obtinut pentrudatele din slide-ul anterior

Reguli obtinute prin C4.5rules

(Give Birth=No, Can Fly=Yes)→ Birds

(Give Birth=No, Live inWater=Yes) → Fishes

(Give Birth=Yes) → Mammals

(Give Birth=No, Can Fly=No,Live in Water=No) → Reptiles

{} → Amphibians

[email protected] (UNITBV) Curs 5 March 29, 2012 31 / 78

Page 32: Curs 5 Data Mining

Caracteristicile clasificatorilor bazati pe reguli

Expresivitate aproape echivalenta cu cea a arborilor de decizie; unarbore de decizie reprezinta datele prin reguli exhaustive si mutualexcluzive

Pentru un set de reguli de decizie, daca o ınregistrare poate declansamai multe reguli atunci se poate ajunge la suprafete de decizie maicomplexe;

Clasificatorii bazati pe reguli de decizie au performanta comparabilacu arborii de decizie

Metodele bazate pe ordonarea claselor este adecvata pentrumanipularea seturilor de date puternic neechilibrate (fractiuni cuvariabilitate mare)

[email protected] (UNITBV) Curs 5 March 29, 2012 32 / 78

Page 33: Curs 5 Data Mining

Outline

1 Clasificatori bazati pe reguli

2 Clasificatori bazati pe vecinatate

3 Retele neurale artificiale

4 Support Vector Machine

5 Metode de tip ansamblu

[email protected] (UNITBV) Curs 5 March 29, 2012 33 / 78

Page 34: Curs 5 Data Mining

Clasificatori bazati pe instante

Arborii de decizie si regulile de clasificare construiesc efectiv un modelcare este folosit apoi pentru clasificarea datelor noi

Rezultat: eager learners

Strategie opusa: se amana crearea unui model de clasificare ⇒ lazy

learners

Exemplu: clasificatorul Rote

se memoreaza ıntregul set de datese face clasificarea unei ınregistrari doar daca atributele ei sunt identicecu atributele unei ınregistrari memorateslabiciune evidenta: uneori nu se poate face clasificare deoarece nicioınregistrare memorata nu se potriveste cu ınregistrarea de test

[email protected] (UNITBV) Curs 5 March 29, 2012 34 / 78

Page 35: Curs 5 Data Mining

Metoda celor mai apropiati k vecini

Eng: k-Nearest Neighbor, prescurtat: k-NN

Se folosesc k vecini, cei mai apropiati de ınregistrarea ce se vrea a ficlasificata

Metoda are nevoie de:

setul de ınregistrari cu clase cunoscuteo metrica (distanta, functie de similaritate) care calculeaza distantaıntre doua ınregistrari, pe baza valorilor atributelorvaloarea k , numarul de vecini cei mai apropiati care sunt considerati

Pentru clasificarea unei ınregistrari:

se calculeaza distanta catre alte ınregistrari din setul de antrenarese identifica cei mai apropiati k vecinise folosesc etichetele de clasa ale acestor k vecini pentru a estima clasaasociata ınregistrarii de test (de exemplu prin considerarea votuluimajoritar)

[email protected] (UNITBV) Curs 5 March 29, 2012 35 / 78

Page 36: Curs 5 Data Mining

Metoda celor mai apropiati k vecini

Figure: k-nearest [email protected] (UNITBV) Curs 5 March 29, 2012 36 / 78

Page 37: Curs 5 Data Mining

Metoda celor mai apropiati k vecini

Figure: K -NN, pentru diverse valori ale lui k

[email protected] (UNITBV) Curs 5 March 29, 2012 37 / 78

Page 38: Curs 5 Data Mining

Metoda celor mai apropiati k vecini

Valoarea lui k este importanta:daca e prea mic, atunci clasificatorul poate fi suspectat de overfitting,pentru ca devine prea senzitiv la zgomotul din datele de intrare(zgomot ⇒ date eronate)daca e prea mare, atunci s–ar putea ca prea multi dintre cei k veciniconsiderati sa fie departati de punctul curent si deci irelevanti pentruclasificarea curenta

Figure: Valoare prea mare a lui k duce la considerare de date irelevante

[email protected] (UNITBV) Curs 5 March 29, 2012 38 / 78

Page 39: Curs 5 Data Mining

1-Nearest Neighbor

Figure: Pentru 1-Nearest neighbor se obtine diagrama Voronoi. In interiorul uneizone delimitate, orice punct ar avea aceeasi clasa ca punctul marcat din aceazona.

[email protected] (UNITBV) Curs 5 March 29, 2012 39 / 78

Page 40: Curs 5 Data Mining

Metoda celor mai apropiati k vecini

Algoritm:

1 Fie k numarul de vecini considerati si D setul de date de antrenare2 Pentru fiecare exemplu de test x′

Calculeaza d(x, x′), distanta ıntre exemplul de test si datele (x, ·) din D

Selecteaza Dz ⊆ D setul celor mai apropiati k vecini ai lui x′

Calculeaza clasa asociata lui x′:

y ′ = argmaxv

(xi ,yi )∈Dz

I (v = yi ) (3)

Observatii:

functia I (·) este functia indicator, cu valoare 1 daca argumentul arevaloarea adevarat, 0 altfel

daca exista mai multi v care maximizeaza partea dreapta a expresiei(3), atunci se alege arbitrar unul din acestia

mai sus se foloseste un sistem de votare ın care fiecare vecin areacelasi impact ın determinarea clasei estimate

[email protected] (UNITBV) Curs 5 March 29, 2012 40 / 78

Page 41: Curs 5 Data Mining

Metoda celor mai apropiati k vecini

Calculul distantei: o alegere populara este distanta Euclidiana: pentrux = (x1, . . . , xn), y = (y1, . . . , yn)

dE (x, y) =

n∑

i=1

(xi − yi )2 (4)

Problema legata de ordinul de marime a datelor:

avem doua atribute: ınaltimea si greutatea unor persoaneınaltimea e masurata ın metri; intervalul poate fi de ex[1.50 m, 2.00 m], deci cu o diferenta de maxim 0.5greutatea se masoara ın kilograme; intervalul poate fi [50 kg , 100 kg ]diferentele de greutate domina pe cele ın ınaltime; o diferenta de 1 kgeste mai mare decat orice diferenta de ınaltime, contribuind deci preamult la calculul distantei

[email protected] (UNITBV) Curs 5 March 29, 2012 41 / 78

Page 42: Curs 5 Data Mining

Metoda celor mai apropiati k vecini

Problema cu distanta Euclidiana: fiecare atribut are exact aceeasipondere ın calculul sumei de sub radical

Chiar daca se face scalarea marimilor (vezi problema cu kg si m), nuınseamna ca fiecare dimensiune are aceeasi relevanta

Se poate folosi o functie ponderata, plecand de la metrica Euclidiana

dE (x, y) =

n∑

i=1

εi (xi − yi )2, εi ≥ 0 (5)

Intrebare: mai este (5) o metrica?

Alte variante de metrici: a se vedea cursul 2

[email protected] (UNITBV) Curs 5 March 29, 2012 42 / 78

Page 43: Curs 5 Data Mining

Metoda celor mai apropiati k vecini

Pentru a reduce senzitivitatea algoritmului k-NN fata de alegerea luik se poate folosi o ponderare a vecinilor

Toti cei k vecini participa la decizia legata de clasa actuala, dar cuponderi diferite:

vecinii mai apropiati au pondere mai marevecinii mai departati au pondere mai mica

Ponderea w poate fi descrescatoare cu distanta fata de punctul ce sevrea a fi clasificat

Formula (3) se transforma din:

y ′ = argmaxv

(xi ,yi )∈Dz

I (v = yi )

ın:y ′ = argmax

v

(xi ,yi )∈Dz

wi × I (v = yi ) (6)

[email protected] (UNITBV) Curs 5 March 29, 2012 43 / 78

Page 44: Curs 5 Data Mining

Caracteristici ale metodei k-NN

Un tip particular de “instance-based learning”

Nu produce efectiv un model; timpul de ınvatare este 0

Clasificarea poate fi lenta, deoarece se face uz de tot corpusul de datedin setul de instruire

Clasificarea se face pe baza informatiei locale, pe cand arborii dedecizie si clasificatorii bazati pe reguli gasesc un model global

k-NN poate produce suprafete de decizie arbitrar de complexe;suprafetele pot avea variabilitate mare, puternic influentate de setulde instruire

Daca nu se foloseste preprocesare (scala diferitelor atribute ar trebuiluata ın considerare) sau o masura de similaritate adecvata, valorileprezise pot fi gresite

[email protected] (UNITBV) Curs 5 March 29, 2012 44 / 78

Page 45: Curs 5 Data Mining

Outline

1 Clasificatori bazati pe reguli

2 Clasificatori bazati pe vecinatate

3 Retele neurale artificiale

4 Support Vector Machine

5 Metode de tip ansamblu

[email protected] (UNITBV) Curs 5 March 29, 2012 45 / 78

Page 46: Curs 5 Data Mining

Retele neurale artificiale

Domeniul este inspirat de studiul retelelor neurale naturale

Retelele neurale artificiale (RNA) sunt compuse din neuroniinterconectati

Legatura dintre neuroni este modelata ca o pondere (valoarenumerica) si aceasta se poate modifica

Printr-un proces de instruire (ınvatare, adaptare), ponderile suntmodificate astfel ıncat sa se faca recunoasterea de pattern-uri

Poate prelua doar intrari numerice, complet precizate (i.e. fara valorilipsa)

RNA sunt folosite pentru:

clasificareestimare de probabilitateregresiegrupare (clustering)

[email protected] (UNITBV) Curs 5 March 29, 2012 46 / 78

Page 47: Curs 5 Data Mining

Retele neurale artificiale: perceptron

Perceptron: un singur neuronInstruirea este de tip supervizat, setul de ınvatare este de forma(x ∈ Rn, y ∈ {−1, 1})Neuronul preia suma intrarilor ınmultite cu ponderile asociate, i.e.produsul scalar ıntre vectorul valorilor intrarilor si vectorul ponderilorSe compara suma cu o valoare de prag, tDaca suma este mai mare decat t atunci perceptronul va produce laiesire valoarea 1, altfel -1Valorile ponderilor w si pragul t sunt determinate prin proces deinstruire si apoi raman fixe

Figure: [email protected] (UNITBV) Curs 5 March 29, 2012 47 / 78

Page 48: Curs 5 Data Mining

Retele neurale artificiale: perceptron

Matematic, iesirea se determina astfel:

y = sgn(w1x1 + w2x2 + · · ·+ wnxn − t) = sgn(〈w, x〉) (7)

unde w = (w0,w1, . . . ,wn)t , x = (x0, x1, . . . , xn)

t cu w0 = −t,x0 = 1, < ·, · > este produs scalar Euclidian iar sgn(·) e functiasignum.

Algoritmul de instruire a perceptronului modifica ponderile w ınfunctie de diferenta existenta ıntre valoarea furnizata de perceptron, ysi valoarea efectiva y a intrarii curente.

Teorema de convergenta a perceptronului spune ca daca un set esteformat din date apartinand de doua clase liniar separabile, atuncidupa un numar finit de ajustari ale ponderilor w perceptronul vadetermina un hiperplan de separare

[email protected] (UNITBV) Curs 5 March 29, 2012 48 / 78

Page 49: Curs 5 Data Mining

Retele neurale artificiale: perceptron

Nu toate problemele de clasificare ın doua clase sunt liniar separabileExemplu: problema XORNu se poate determina un hiperplan (ın cazul 2D: o dreapta) care seaiba de o parte doar punctele dintr-o clasa si de partea cealalta doarpuncte din cealalta clasa

Figure: Problema [email protected] (UNITBV) Curs 5 March 29, 2012 49 / 78

Page 50: Curs 5 Data Mining

Retele neurale artificiale: retea neurala multistrat

Figure: Retea neurala artificiala multistrat cu un singur neuron de iesire

[email protected] (UNITBV) Curs 5 March 29, 2012 50 / 78

Page 51: Curs 5 Data Mining

Retele neurale artificiale: instruirea retelei neuralemultistrat

Functioneaza pentru instruire supervizata; setul de ınvatare consta dinperechi de forma (xk ∈ Rn, yk ∈ Rm)

Se initializeaza ponderile legaturilor dintre neuroni, de exemplu cuvalori aleatoare

Se modifica ponderile a.i. iesirea retelei sa fie apropiata de iesireadorita

Functia obiectiv ce trebuie minimizata este:

E (w) =1

2

i

(iesirea produsai − iesirea doritai )2 (8)

unde i itereaza peste indicii neuronilor din stratul de iesire

Determinarea ponderilor de optim: metodele de tip gradient suntfrecvent folosite

wj ← wj − λ∂E (w)

∂wj

[email protected] (UNITBV) Curs 5 March 29, 2012 51 / 78

Page 52: Curs 5 Data Mining

Retele neurale artificiale: probleme

Numarul de neuroni din stratul ascuns, eventual numarul de straturiascunse trebuie sa fie determinat ınainte de ınceperea instruirii; nueste clar cum se poate alege acesta, de regula se folosesc multipleıncercari

Functia obiectiv (8) este dificil de optimizat; metodele bazate pegradient pot duce ın optime locale, insuficient de bune pentru aconsidera ca reteaua s–a adaptat corespunzator

Setul de date trebuie sa fie complet, fara valori de atributeneprecizate; intrarile si iesirile sunt exlusiv numerice

Timpul de antrenare poate sa fie mare

Greu de interpretat; extragerea de reguli este posibila, dar rareorifacuta; acest tip de retele neurale artificiale sunt mai degrabapercepute ca “black boxes”

[email protected] (UNITBV) Curs 5 March 29, 2012 52 / 78

Page 53: Curs 5 Data Mining

Retele neurale artificiale: trasaturi

Retelele neurale artificiale multistrat sunt aproximatori universali: potaproxima oricat de fidel orice functie reala continua

Pot manipula valori redundante

Nu sunt foarte senzitive la zgomot

Instruirea este lenta, efectuata pe multiple sesiuni ın care se parcurgrepetat datele

Din punct de vedere practic functioneaza bine, arhitectura multistratfiind cea mai implementata si utilizata retea

[email protected] (UNITBV) Curs 5 March 29, 2012 53 / 78

Page 54: Curs 5 Data Mining

Outline

1 Clasificatori bazati pe reguli

2 Clasificatori bazati pe vecinatate

3 Retele neurale artificiale

4 Support Vector Machine

5 Metode de tip ansamblu

[email protected] (UNITBV) Curs 5 March 29, 2012 54 / 78

Page 55: Curs 5 Data Mining

Support Vector Machine (SVM)

Metoda de obtinere a unui dihotomizator = clasificator pentru douaclase

Au fundament matematic solid

Functioneaza bine pentru date multidimensionale

Se poate aplica si pentru clase neliniar separabile

[email protected] (UNITBV) Curs 5 March 29, 2012 55 / 78

Page 56: Curs 5 Data Mining

Support Vector Machine (SVM)

Figure: Sa se determine o dreapta (hiperplan) care separa cele doua clase depuncte

[email protected] (UNITBV) Curs 5 March 29, 2012 56 / 78

Page 57: Curs 5 Data Mining

Support Vector Machine (SVM)

Figure: O solutie posibila

[email protected] (UNITBV) Curs 5 March 29, 2012 57 / 78

Page 58: Curs 5 Data Mining

Support Vector Machine (SVM)

Figure: Alta solutie

[email protected] (UNITBV) Curs 5 March 29, 2012 58 / 78

Page 59: Curs 5 Data Mining

Support Vector Machine (SVM)

Figure: Alte solutii

[email protected] (UNITBV) Curs 5 March 29, 2012 59 / 78

Page 60: Curs 5 Data Mining

Support Vector Machine (SVM)

Figure: Care e mai buna? B1 sau B2? (ce ınseamna “mai buna”?)

[email protected] (UNITBV) Curs 5 March 29, 2012 60 / 78

Page 61: Curs 5 Data Mining

Support Vector Machine (SVM)

Figure: Enunt mai clar: sa se gaseasca hiperplanul care maximizeaza marginea deseparare. In aceasta conditie, B1 este mai bun decat B2

[email protected] (UNITBV) Curs 5 March 29, 2012 61 / 78

Page 62: Curs 5 Data Mining

Support Vector Machine (SVM)

w, b sunt parametri ai modelului SVM

Clasificarea efectuata de hiperplan:

f (x) =

{

1 daca w · x+ b > 0−1 daca w · x+ b < 0

[email protected] (UNITBV) Curs 5 March 29, 2012 62 / 78

Page 63: Curs 5 Data Mining

Support Vector Machine (SVM)

Considerand punctele cele mai aporpiate de hiperplan, putem impuneconditia ca el su a fie astfel trasat ıncat distanta dintre aceste punctesi hiperplan sa fie suficient de mare:

b11 : w · x+ b = 1 (9)

b12 : w · x+ b = −1 (10)

Marginea suprafetei de decizie este data de distanta dintre b11 si b12

Se doreste ca aceasa margine de separare sa fie cat mai mare, decitrebuie determinat max 2

‖w‖2

Daca setul de date de antrenare este {(xi , yi )} cu yi ∈ {±1},1 ≤ i ≤ N, atunci trebuie determinati w si b a.ı.:

{

w · xi + b ≥ 1 daca yi = 1w · xi + b ≤ −1 daca yi = −1

(11)

[email protected] (UNITBV) Curs 5 March 29, 2012 63 / 78

Page 64: Curs 5 Data Mining

Support Vector Machine (SVM)

Considerand maximizarea marginii suprafetei de decizie, obtinemproblema de optimizare:

{

minw

‖w‖2

2

cu constrangerile yi (w · xi + b) ≥ 1, i = 1, . . . ,N(12)

Problema (12) este una de optimizare convexa

Se rezolva prin metoda multiplicatorilor lui Lagrange, pentruproblema urmatoare:

LP =1

2‖w‖2 −

N∑

i=1

λi (yi (w · xi + b)− 1) (13)

[email protected] (UNITBV) Curs 5 March 29, 2012 64 / 78

Page 65: Curs 5 Data Mining

Support Vector Machine (SVM)

Pentru determinarea valorilor multiplicatorilor se aplica conditiileKarush-Kuhn-Tucker si se rezolva problema duala:

LD =N∑

i=1

λi −1

2

i ,j

λiλjyiyjxi · xj (14)

Prin metode de programare patratica se determina valorile λi ,1 ≤ i ≤ N

[email protected] (UNITBV) Curs 5 March 29, 2012 65 / 78

Page 66: Curs 5 Data Mining

Support Vector Machine (SVM)

Cum se poate folosi SVM pentru clase neliniar separabile?

Figure: Clase neliniar separabile

[email protected] (UNITBV) Curs 5 March 29, 2012 66 / 78

Page 67: Curs 5 Data Mining

Support Vector Machine (SVM)

Solutie: se relaxeaza inegalitatile din (11) ın forma:{

w · xi + b ≥ 1− ξi daca yi = 1w · xi + b ≤ −1 + ξi daca yi = −1

(15)

cu ξi ≥ 0 ∀i

Valorile lui ξi nu pot fi prea mari

Functia obiectiv devine:

f (w) =‖w‖2

2+ C

(

N∑

i=1

ξi

)k

(16)

unde C si k sunt valori specificate de utilizator sau determinateprintr-un proces de validare

Se modifica forma Lagrangianului din (13), se obtine o problemaduala adecvata;

Se aplica metode numerice din cadrul tehnicilor de programarepatratica pentru rezolvarea problemei duale

[email protected] (UNITBV) Curs 5 March 29, 2012 67 / 78

Page 68: Curs 5 Data Mining

Outline

1 Clasificatori bazati pe reguli

2 Clasificatori bazati pe vecinatate

3 Retele neurale artificiale

4 Support Vector Machine

5 Metode de tip ansamblu

[email protected] (UNITBV) Curs 5 March 29, 2012 68 / 78

Page 69: Curs 5 Data Mining

Metode de tip ansamblu

Pe baza setului de antrenare se pot construi mai multi clasificatori

Intrebare: nu am putea oare combina mai multi clasificatori pentru aobtine rezultate mai bune decat cu unul singur?

Prin combinarea preditiilor facute de un grup de clasificatori se poateobtine de multe ori un rezultat mai bun decat bazandu–te pe unulsingur

[email protected] (UNITBV) Curs 5 March 29, 2012 69 / 78

Page 70: Curs 5 Data Mining

Metode de tip ansamblu: exemplu de motivatie

Avem 25 de clasificatori binari, fiecare cu rata de eroare (procent declasificare gresita) ε = 0.35

Ansamblul ia ca si valoare prezisa pentru o intrare votul majoritar

Daca clasificatorii sunt identici, atunci ansamblul se va comporta caoricare din ei, deci eroarea de clasificare este tot 0.35

Daca clasificatorii sunt ınsa independenti, atunci ansamblul are eroarede clasificare doar daca cel putin 13 clasificatori gresesc

Astfel, eroarea de clasificare pentru ansamblul de clasificatoriindependenti este:

eansamblu =

25∑

i=13

C i25ε

i (1− ε)25−i = 0.06

[email protected] (UNITBV) Curs 5 March 29, 2012 70 / 78

Page 71: Curs 5 Data Mining

Metode de tip ansamblu: exemplu de motivatie

Conditii necesare pentru ca ansamblul de clasificatori sa duca larezultate mai bune:

1 clasificatorii sa fie independenti unii de altii2 clasificatorul de baza (daca se face replicarea unui aceluiasi clasificator)

sa se comporte mai bine decat unul care procedeaza prin ghicire laıntamplare

Chiar daca clasificatorii sunt ne-independenti, ın practica s–a observatca ansamblurile de metode conduc la rezultate bune

[email protected] (UNITBV) Curs 5 March 29, 2012 71 / 78

Page 72: Curs 5 Data Mining

Metode de tip ansamblu: metode de construire aansamblului

1 Construirea unui ansamblu de clasificatori se face dupa schema demai jos:

[email protected] (UNITBV) Curs 5 March 29, 2012 72 / 78

Page 73: Curs 5 Data Mining

Metode de construire a ansamblului

Prin manipularea setului de antrenare (esantionare); un clasificatoreste construit pentru fiecare set de esantioane; ex: bagging, boosting;varianta: ıntrucat mare parte din algoritmii de ınvatare suntdependenti de ordinea datelor de instruire, se pot face permutarialeatoare ale lui D;

Prin manipularea etichetelor de clasa: daca multimea de clase estesuficient de mare, atunci se poate partitiona ın subseturi (e.g. A0 siA1); un clasificator va lucra doar cu etichetele A0 si A1. Daca laprezentarea unei ınregistrari un clasificator binar de mai sus raspundecu A0, atunci toate etichetele care intra ın A0 primesc un vot;procedeul se repeta pentru partitionari diferite a multimii initiale deetichete

[email protected] (UNITBV) Curs 5 March 29, 2012 73 / 78

Page 74: Curs 5 Data Mining

Metode de construire a ansamblului (cont)

Prin modificarea atributelor de intrare: de exemplu, se aleg (aleatorsau pe baza de experti umani) subseturi de atribute (proiectie) si seconstruiesc clasificatori doar cu aceste atribute;

Prin manipularea algoritmului de ınvatare: aproape toti algoritmii deınvatare au niste hiperparametri care influenteaza comportamentulclasificatorului

retele neurale: factori de ınvatare, numarul de noduri, numarul destraturi, functia de activarek-NN: k , functia de ponderare a vecinilorarbori de decizie: ın loc de a se alege cel mai bun criteriu pentru apartitiona datele dintr-un nod, se alege aleator din cele mai bune p

criterii

[email protected] (UNITBV) Curs 5 March 29, 2012 74 / 78

Page 75: Curs 5 Data Mining

Metode de construire a ansamblului: Bagging

Cunoscut ca si: bootstrap aggregating

Pasii:

se face esantionare dupa o distributie uniforma cu repunerefiecare esantion are aceeasi dimensiune ca setul initialo parte din datele originale pot sa apara ın esantion de mai multe ori,altele delocın medie, un esantion contine aproximativ 63% din datele originaledupa ce se obtin k clasificatori, o instanta de test are clasa estimata pebaza votului majoritarexemplu: Introduction to Data Mining, sectiunea 5.6.4

[email protected] (UNITBV) Curs 5 March 29, 2012 75 / 78

Page 76: Curs 5 Data Mining

Metode de construire a ansamblului: Boosting

Boosting: procedura iterativa prin care se modifica distributia datelorde antrenare prin concentrarea pe ınregistrarile gresit clasificateanterior

Ponderile sunt asociate ınregistrarilor din setul de antrenare si pot fifolosite pentru:

influentarea mecanismului de esantionareinfluentarea clasificatorilor pentru a produce un model care estedirectionat catre ınregistrarile cu ponderi mai mari

Initial, toate ınregistrarile din setul de antrenare au aceeasi pondere1/|D|

Ponderile pot fi modificate la sfarsitul unei runde de boosting

[email protected] (UNITBV) Curs 5 March 29, 2012 76 / 78

Page 77: Curs 5 Data Mining

Metode de construire a ansamblului: Boosting

Inregistrarile care sunt gresit clasificate vor suferi o crestere aponderilor

Inregistrarile care sunt corect clasificate vor avea ponderile scazute

Exemplu: ınregistrarea 4 este greu de ınvatat

Ponderea ei este crescuta, deci sansa de a fi aleasa prin esantionarecreste

[email protected] (UNITBV) Curs 5 March 29, 2012 77 / 78

Page 78: Curs 5 Data Mining

Studiu individual

Din “Introduction to Data Mining”, cap 5:

Clasificatori bayesieni, naıve Bayes, belief networks

SVM neliniar, kernel trick

Descompunerea abatere - varianta

Random forests

Problema claselor nebalansate

Problema multiclaselor

[email protected] (UNITBV) Curs 5 March 29, 2012 78 / 78