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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 1 / 78

Outline

1 Clasificatori bazati pe reguli

2 Clasificatori bazati pe vecinatate

3 Retele neurale artificiale

4 Support Vector Machine

5 Metode de tip ansamblu

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 2 / 78

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=, <,>,≤,≥}

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 3 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 4 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 5 / 78

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%

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 6 / 78

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 ⇒ ??

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 7 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 8 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 9 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 10 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 11 / 78

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)

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 12 / 78

Clasificatori bazati pe reguli ordonate: scheme de ordonare

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 13 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 14 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 15 / 78

Metoda directa: acoperirea secventiala

Exemplu:

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 16 / 78

Metoda directa: acoperirea secventiala

Exemplu (cont):

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 17 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 18 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 19 / 78

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”

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 20 / 78

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”

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 21 / 78

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)

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 22 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 23 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 24 / 78

Acoperirea secventiala: criteriul de oprire

Calculeaza castigul adus de noua regula

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 25 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 26 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 27 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 28 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 29 / 78

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

Set de date:

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 30 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 31 / 78

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)

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 32 / 78

Outline

1 Clasificatori bazati pe reguli

2 Clasificatori bazati pe vecinatate

3 Retele neurale artificiale

4 Support Vector Machine

5 Metode de tip ansamblu

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 33 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 34 / 78

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)

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 35 / 78

Metoda celor mai apropiati k vecini

Figure: k-nearest neighborlucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 36 / 78

Metoda celor mai apropiati k vecini

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 37 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 38 / 78

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.

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 39 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 40 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 41 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 42 / 78

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)

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 43 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 44 / 78

Outline

1 Clasificatori bazati pe reguli

2 Clasificatori bazati pe vecinatate

3 Retele neurale artificiale

4 Support Vector Machine

5 Metode de tip ansamblu

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 45 / 78

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)

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 46 / 78

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: Perceptronlucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 47 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 48 / 78

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 XORlucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 49 / 78

Retele neurale artificiale: retea neurala multistrat

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 50 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 51 / 78

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”

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 52 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 53 / 78

Outline

1 Clasificatori bazati pe reguli

2 Clasificatori bazati pe vecinatate

3 Retele neurale artificiale

4 Support Vector Machine

5 Metode de tip ansamblu

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 54 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 55 / 78

Support Vector Machine (SVM)

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 56 / 78

Support Vector Machine (SVM)

Figure: O solutie posibila

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 57 / 78

Support Vector Machine (SVM)

Figure: Alta solutie

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 58 / 78

Support Vector Machine (SVM)

Figure: Alte solutii

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 59 / 78

Support Vector Machine (SVM)

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 60 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 61 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 62 / 78

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)

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 63 / 78

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)

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 64 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 65 / 78

Support Vector Machine (SVM)

Cum se poate folosi SVM pentru clase neliniar separabile?

Figure: Clase neliniar separabile

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 66 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 67 / 78

Outline

1 Clasificatori bazati pe reguli

2 Clasificatori bazati pe vecinatate

3 Retele neurale artificiale

4 Support Vector Machine

5 Metode de tip ansamblu

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 68 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 69 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 70 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 71 / 78

Metode de tip ansamblu: metode de construire aansamblului

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 72 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 73 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 74 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 75 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 76 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 77 / 78

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

lucian.sasu@ieee.org (UNITBV) Curs 5 March 29, 2012 78 / 78