DATA MINING MACHINE LEARNING.

Algoritmul 1R, Arbori de Decizie

33

3. Machine learning. Clasificarea.

4.1. Clasificarea Clasificarea este utilizată pentru a prezice la ce clasă aparŃine un obiect.

Problema clasificării poate fi formulată astfel:

• Bazându-ne pe caracteristici existente în clasa care descrie datele de antrenare, dezvoltăm o descriere sau un model pentru fiecare clasă.

In exemplul de mai jos se urmăreşte găsirea unui clasificator care să specifice condiŃia de ocupare a unui post.

Procesul de Clasificare (1): Construirea Modelului

• Având dat un set de date de antrenare, (n+1) obiecte de forma (a1, a2, …,an, ck) unde ai (1 ≤ i ≤ n) sunt atribute şi ck (1 ≤ k ≤ m) este eticheta clasei, găseşte regulile care partiŃionează setul de date în grupe disjuncte cu cei mai mulŃi membri în fiecare grup având aceiaşi etichetă de clasă.

Date de Antrenare

NAME RANK YEARS TENUREDMike Assistant Prof 3 noMary Assistant Prof 7 yesBill Professor 2 yesJim Associate Prof 7 yesDave Assistant Prof 6 noAnne Associate Prof 3 no

Algorithm de

Clasificare

IF rank = ‘professor’ OR years > 6 THEN tenured = ‘yes’

Clasificator (Model)

DATA MINING MACHINE LEARNING.

Algoritmul 1R, Arbori de Decizie

34

• Având un set de date de te,t putem verifica dacă regulile descoperite generalizează satisfăcător, măsurând acurateŃea predicŃiei.

Procesul de Clasificare (2): Utilizarea modelului in PredicŃie

Datele utilizate la construcŃia unui model de clasificare constau din:

• Un set de înregistrări – fiecare înregistrare descrie un obiect. • Fiecare înregistrare are acelaşi număr de câmpuri (caracteristicile

obiectului). • Un câmp în aceste înregistrări conŃine indicatorul clasei căreia

înregistrarea îi aparŃine (câmpul Nivel_creditare din exemplu din figura Fig. 3.1.).

• Celelalte câmpuri sunt numite câmpuri independente şi descriu caracteristici individuale care compun înregistrarea.

Un set de date de antrenare este prezentat în figura 3.1

Vârsta Venitul Student Nivel creditare <=30 mare nu normal 31…40 mare nu normal >40 mediu nu normal >40 mic da normal >40 mic da excelent 31…40 mic da excelent

Clasificare

Date de test

NAME RANK YEARS TENUREDTom Assistant Prof 2 noMerlisa Associate Prof 7 noJeff Professor 4 yesJoseph Assistant Prof 7 yes

Unseen

(Jeff, Professor, 4)

Tenured?

DATA MINING MACHINE LEARNING.

Algoritmul 1R, Arbori de Decizie

35

<=30 mediu nu normal <=30 mic da normal >40 mediu da normal <=30 mediu da excelent 31…40 mediu nu excelent 31…40 mare da normal >40 mediu nu excelent

Fig. 3.1. Set de date de antrenare

Sunt câŃiva algoritmi Data Mining mai importanŃi pentru clasificare cum ar fi:

algoritmul 1R, arbori de decizie, reŃele neuronale, cei mai apropiaŃi k vecini (k - nearest neighbors), algoritmi genetici, modelul regulilor de asociere, etc. În continuare se vor prezenta câŃiva dintre aceşti algoritmi.

3.2. Algoritmul 1R Ca şi alte metode empirice de învăŃare, 1R are ca intrare un set de exemple in

care fiecare element (exemplu) din set este caracterizat de un număr de atribute şi clase.

Algoritmul se utilizează atât pentru valori ale atributelor continue (acestea iau valori intr-un interval), cat şi discrete (nominale) . In urma operaŃiei de clasificare care se lansează pentru fiecare atribut in parte, se obŃin un număr de clasificatori egali cu numărul de atribute . Dintre aceştia se alege cel mai semnificativ clasificator (criteriul fiind data de precizia de clasificare pe care o realizează – respectiv nivelul de eroare pe care îl are) Deci Algoritmul 1R construieşte clasificatorul pe baza unui singur atribut, selecŃia acestuia, fiind făcută funcŃie de rezultatul clasificării - se construiesc toŃi clasificatorii corespunzători atributelor prezente, după care se alege unul considerat reprezentativ. Algoritmul a fost prezentat pentru prima oara in articolul : Very Simple Classification Rules Perform Well on Most Commonly Used Datasets, Robert C. Holte, Computer Science Department, University of Ottawa in Machine Learning 11: 63-91 1993

Pentru a ilustra această tehnica vom considera setul de exemple prezent in Tabelul 3.2. Tabelul prezintă datele (Quinlan, 1994) ce caracterizează condiŃiile meteo în care se poate juca sau nu golf.

Un element din set are patru atribute din care: • doua atribute cu valori nominale:

1. outlook cu valorile sunny, overcast and rain, şi 2. windy (cu valorile true şi false), si • doua atribute cu valori continue: 2. temperature şi 3. humidity. Se observă prezenŃa a doua clase Play şi Don’t Play

DATA MINING MACHINE LEARNING.

Algoritmul 1R, Arbori de Decizie

36

Tabel 3.2 Set date care specifica condiŃiile in care se poate juca golf 3.2.1. ConstrucŃia clasificatorului pentru cazul atributelor nominale cu valori discrete Pentru a demonstra cum funcŃionează algoritmul, vom considera numai valorile nominale prezente in setul de date: Outlook şi respectiv Windy.

Intrare: a // mulŃimea atributelor ce definesc un element din setul de date

Ieşire if a are valoare v then clasa este c // clasificator

For fiecare atribut a, construieşte o regula astfel:

For fiecare valoare nominala v din domeniul lui a, Selectează acele elemente unde a are valoarea v. Fie c cea mai frecventa clasa in acest setul de date. Aduna următoare clauza la regula pentru a:

if a are valoare v then clasa este c Calculează acurateŃea clasificării pentru regula introdusă. Utilizează regula cu cea mai buna acurateŃe de clasificare

Atribute Outlook Temp. Hum. Windy Class

sunny 85 85 false Don’t Play sunny 80 90 true Don’t Play

overcast 83 86 false Play V rainy 70 96 false Play a rainy 68 80 false Play l rainy 65 70 true Don’t Play o overcast 64 65 true Play r sunny 72 95 false Don’t Play i sunny 69 70 false Play rainy 75 80 false Play sunny 75 70 true Play overcast 72 90 true Play overcast 81 75 false Play

rainy 71 91 true Don’t Play

DATA MINING MACHINE LEARNING.

Algoritmul 1R, Arbori de Decizie

37

FrecvenŃele pentru fiecare clasa, pentru fiecare valoare a atributelor nominale este arătata in Tabelul 3.2. Regulile derivate din acest tabel şi acurateŃea acestora este prezentata in Tabelul 3.3

Tabel 3.2: Frecventa valorilor in atributele nominale

outlook windy

Precizie = 10/14 (71.4%) Precizie = 9/14 (64.3%)

Tabel 3.3: Reguli derivate din Tabelul 3.2

Pentru fiecare atribut si valoare, clasa aleasa este aceea in care apare cel mai frecvent combinaŃia atribut – valoare de exemplu când atributul outlook este sunny, clasa aleasa este Don’t Play deoarece aşa cum se vede din tabelul 4.2, acesta apare de trei ori in timp ce in clasa Play apare numai de doua ori. Daca cele mai mari frecvente sunt egale se procedează la o alegere aleatoare a uneia din ele. De exemplu in regula windy din tabelul 3 daca if true then Play se alege, ea este la fel de acceptabila ca şi regula if true then Don’t Play care este arătata. Din aceste exemple se observa ca atributul windy care are valoarea true nu are nici o contribuŃie in a decide daca vremea are sau nu o contribuŃie in a stabili daca se joaca sau nu golf. 3.2.2. ConstrucŃia clasificatorului pentru cazul atributelor cu valori continue.

Tehnica presupune construirea de intervale in care, valoarea tributului luat in

considerare pentru construcŃia clasificatorului ia valori. Numărul de intervale este egal cu numărul de clase in care elementele din setul de date sunt reclasificate.

Pentru a demonstra cum funcŃionează algoritmul vom considera numai valorile continue prezente in setul de date Temperature şi respectiv Humidity.

outlook Play Don’t Play overcast 4 0 sunny 2 3 rain 3 2

windy Play Don’t Play true 3 3 false 6 2

If overcast then Play (4/4) else if sunny then Don’t Play (3/5) else if rain then Play (3/5)

If true then Don’t Pay (3/6) else if false then Play (6/8)

DATA MINING MACHINE LEARNING.

Algoritmul 1R, Arbori de Decizie

38

DiscuŃia se va efectua pentru valori continue ale atributului Temp.

Intrare: v // mulŃimea valorilor ce definesc un atribut din setul de date

Ieşire if a are valoare v then clasă este c // clasificator

1. Sortează elementele după valoarea v atributului. 2. Construieşte intervale, prin plasarea unei separator intre fiecare pereche de diferite

valori. 3. repeta a. elimina separatorul dintre intervalele ce aparŃin aceleaşi clase, b. examinează pierderea de precizie care apare ca urmare a îndepărtării separatorilor, c. elimină cele mai puŃin costisitoare puncte de separare (in eventualitate de egalitate se alege unul in mod aleatoriu pana când nu mai exista separatori); until numărul de intervale este diferit de numărul de clase 4. Alege cel mai bun interval găsit din punctul de vedere a preciziei de clasificare. Modul in care funcŃionează algoritmul este arătat pentru setul de date prezentat mai sus. Succesiunea de operaŃii prezintă următoarea desfăşurare pentru cele doua clase in care este reclasificat setul de exemple (P---Play şi D---Don’t Play): (1.) Sortează elementele după valoarea v atributului. (2.) Construieşte intervale, prin plasarea unei separator intre fiecare pereche de diferite valori

Temp. 64 65 68 69 70 71 72 72 75 75 80 81 83 85 Clasă P D P P P D D P P P D P P D Nr interval 1 2 3 4 5 6 7 8 9 10 11 12

(3.) repeta a. elimina separatorul dintre intervalele ce aparŃin aceleaşi clase

Temp. 64 65 68 69 70 71 72 72 75 75 80 81 83 85 Clasă P D P P P D D P P P D P P D Nr interval 1 2 3 4 5 6 7 8

OperaŃia are ca efect reducerea numărului de intervale . In acest prima iteraŃie in exemplul dat reducerea este de la 12 la 8 intervale

DATA MINING MACHINE LEARNING.

Algoritmul 1R, Arbori de Decizie

39

b. examinează pierderea de precizie care apare ca urmare a îndepărtării separatorilor

Fiecare din separatoare delimitează clase diferite. Eliminându-le pe oricare dintre acestea, scădem acurateŃea cuantizării. De exemplu, eliminând separatorul dintre 65 şi 68 obŃinem un nou interval de la 65 la 70 in care clasă predominantă este Play. Ca urmare atributul Don’t Play este clasificat incorect ca şi Play, rezultând o reducere a acuratei de la 100% la 75%.

In clasă sunt prezente : 3 valori Play 1 valoare Don’t Play Total 4 Valori Precizie pentru Play 3 / 4=75%

Daca se va construi o regula pentru acest interval ea va fi pentru clasă Play. Valorile care urmează a fi clasificate cu acest clasificator vor avea deci o precizie de 75%. Această transformare corespunde eliminării unui separator care corespunde celei mai mici reduceri a acurateŃei de clasificare.

Temp. 64 65 68 69 70 71 72 72 75 75 80 81 83 85 Clasă P D P P P D D P P P D P P D Nr interval 1 2 3 4 5 6 7

c. elimina cele mai puŃin costisitoare puncte de separare (in eventualitate de egalitate se alege unul in mod aleatoriu pana când nu mai exista separatori; Acum delimitatorul dintre 64 şi 65 poate fi eliminat fără o pierdere a acurateŃei 6 intervale

Temp. 64 65 68 69 70 71 72 72 75 75 80 81 83 85 Clasă P D P P P D D P P P D P P D Nr interval 1 2 3 4 5 6

3 intervale

Temp. 64 65 68 69 70 71 72 72 75 75 80 81 83 85 Clasă P No P P P D D P P P D P P D Nr interval 1 2 3

until numărul de intervale este diferit de numărul de clase

Temp. 64 65 68 69 70 71 72 72 75 75 80 81 83 85 Clasă P D P P P D D P P P D P P D Nr interval 1 2

DATA MINING MACHINE LEARNING.

Algoritmul 1R, Arbori de Decizie

40

(4.) Alege cel mai bun interval găsit din punctul de vedere a preciziei de clasificare. Precizia de clasificare se calculează astfel:

In clasă 1 sunt prezente : 7 valori Play 3 valori Don’t Play Total 10 Valori Precizie pentru Play 7 / 10=70%

In clasă 2 sunt prezente : 2 valori Play 2 valori Don’t Play Total 4 Valori Precizie pentru Play 2 / 4=50% Ca urmare se alege primul interval pentru construirea clasificatorului. Rezultă

următorul set de reguli complet pentru întregul set de date Atribute Reguli Eroare Eroare

totala Outlook Sunny → Don’t Play

Overcast → Play Rainy → Play

2/5 0/4 2/5

4/14

Temp <=77.5 → Play* >77.5 → Don’t Play

3/10 2/4

5/14

Humidity <=82.5 → Play >82.5 and<=95.5 → Don’t Play >95.5→ Play

1/7 2/6 0/1

3/14

Windy False → Play True → Don’t Play*

2/8 3/6

5/14

Se alege ca şi clasificator pentru modelul datelor din set atributul Humidity deoarece prezintă eroarea cea mai mica

ObservaŃie

(1) Pentru temperatură, valoarea 77.5 a rezultat din tabel prin medierea valorilor de la graniŃa celor două intervale găsite (75+80)/2=77.5

(2) Orice metodă, prin care se mapează un set de valori în intervale disjuncte

trebuie sa ia în considerare necesitatea de a crea cât mai multe reguli cu intervale cât mai mici – pentru asigurarea acurateŃei de clasificare. Acesta reprezintă o problemă, deoarece apare o contradicŃie prin aceea că clasificatorul astfel obŃinut nu acoperă setul de date şi deci nu generalizează bine. Pentru a

DATA MINING MACHINE LEARNING.

Algoritmul 1R, Arbori de Decizie

41

rezolva această problema soluŃia este de a asigura prezenŃa intr-o clasă a mai mult de 1 element ObservaŃii empirice arată că limita inferioara a numărului de elemente prezent intr-un interval de discretizare trebuie să aibă o valoare de 6 pentru seturi de date cu un număr mare de elemente şi de 3, pentru seturi mici de seturi de date (mai puŃin de 50 elemente) [Holte et. al, 1989].

Important În concluzie, algoritmul 1R învaŃă prin analizarea primului nivel al arborelui de decizie, realizând toate testele pentru un atribut particular. O ramura va fi creată pentru fiecare atribut. Fiecare ramura va assigna cea mai frecventă clasă – şi va corespunde unui clasificator posibil de luat in considerare. Se alege acel clasificator (acea ramură) care conduce la cea mai mică eroare de clasificare. Pentru exemplul discutat avem

Atribute Outlook Temp Humidity Windy Eroare 4/14 5/14 3/14 5/14 Model (clasificator) *

Set date