DataMining_IlicaIoanaMinola

UNIVERSITATEA "POLITEHNICA" TIMIOARA

PROIECT DATA MINING

analiza setului de date

Breast Cancer Wisconsin (Original)

Ilica Ioana Minola

An II MTSSCC

Introducere

In proiectul de fata ne propunem realizarea unei analize in termenii Data Mining.

Denumirea de Data Mining a fost adoptata pentru domeniul de cercetare si are ca scop analiza unor cantitati mari de date pentru determinarea de relatii care apar intre elementele prezente inbazele de date si a determinarii de machete( potential utile) care pot caracteriza bazele dedate. Utilizeaza o varietate de unelte de analiza a datelor pentru a oferi in final predictii utile.Machetele si relatiile care se determina vor defini un model al datelor in cauza. Cateva dintre tehnicile folosite in Data Mining sunt: clasificare, corelatii, grupare si asocieri. Procesul de descoperire de informatii din bazele de date mari cuprinde mai multe etape:

definirea scopului urmarit

interogarea surselor de date si definirea structurii datelor supuse prelucrarii

preprocesarea datelor (selectarea, curatarea, transformarea acestora)

minarea datelor pentru extragerea de tipare si modele apropiate

evaluarea si interpretarea tiparelor extrase pentru a decide ce constituie cunostinta(knowledge)

consolidarea cunostintelor si rezolvarea conflictelor dintre cunostintele extrase anterior,

oferirea cunostintelor spre utilizare

Weka este un tool care are la baza limbajul Java, pentru Machine Learning si Data Mining. Algoritmii sai de analizare a datelor se pot aplica direct pe setul de date sau se pot apela din cod Java. Weka mai cuprinde tool-uri de preprocesare, impartirea in clustere, clasificare, reguli de asociere si modalitati de vizualizare.

Setul de date ales de noi apartine domeniului medical, si poate fi gasit la adresa http://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Original%29 in format text. Folosind Microsoft Office Excel am transformat setul de date initial intr-un set de tipul *.csv, acest tip fiind recunoscut automat de catre Weka. Se asigura transformarea in tipul arff(Attribute-Relation File Format) prin intermediul pachetului Weka, aceasta reprezentand forma in care vom prelucra setul nostru de date: @relation breast-cancer-wisconsin2

@attribute id numeric

@attribute clump_thick numeric

@attribute unif_cell_size numeric

@attribute unif_cell_shape numeric

@attribute adhesion numeric

@attribute epithelial_cell_size numeric

@attribute bare_nuclei numeric

@attribute bland_chromatin numeric

@attribute n_nucleoli numeric

@attribute mitoses numeric

@attribute class {benign,malingn}

@data

1000025,5,1,1,1,2,1,3,1,1,benign

1002945,5,4,4,5,7,10,3,2,1,benign

1015425,3,1,1,1,2,2,3,1,1,benign

1016277,6,8,8,1,3,4,3,7,1,benign

1017023,4,1,1,3,2,1,3,1,1,benign

Descrierea setului de date initial

Setul de date Breast Cancer Wisconsin(Original) este rezultatul unui studiu de cancer la

san efectuat in Wisconsin al carui scop a fost sa se vada daca se poate determina tipul unei

tumori (maligne sau beningne) in urma analizarii unei monstre mici de tesut. Setul de date

cuprinde 699 de pacienti cu tumori, dintre care 241 sunt maligne . Acestea sunt caracterizate

prin zece atribute, plus un atribut corespunzator clasei:

Sample code number (id) reprezinta id-ul pacientului

Clump Thickness (clump_thick) reprezinta grosimea nodulului, pe o scara de la 1 la 10

(grosimea medie in setul de date fiind de 4.41, cu deviatia standard 2.81)

Uniformity of Cell Size (unif_cell_size) masoara pe o scara de la 1 la 10 cat de

uniforme sunt celulele din punct de vedere al marimii (valoarea medie in setul

nostrum de date fiind 3.31, cu o deviatie standard in valoare de 3.05)

Uniformity of Cell Shape(unif_cell_shape) - masoara pe o scara de la 1 la 10 cat de

uniforme sunt celulele din puct de vedere al formei (valoarea medie fiind 3.20, cu o

deviatie standard in valoare de 2.97 )

Marginal Adhesion (adhesion) masoara pe o scara de la 1 la 10 aderenta marginala

intre celule (in medie 2.80, cu o deviatie standard de 2.85)

Single Epithelial Cell Size (epithelial_cell_size) reprezinta marimea unei celule

epiteliale, valori de la 1 la 10 (valoarea medie in setul nostru este 3.21 iar deviatia

standard este 2.21)

Bare Nuclei (bare_nuclei) test cu rezultate intre 1 si 10 (in setul nostrum de date

valoarea intalnita este in medie 3.54, cu o deviatie standard de 3.64)

Bland Chromatin (bland_chromatin) valori intre 1 si 10 (valoare medie in setul

nostru: 3.43, deviatie standard: 2.43)

Normal Nucleoli (n-nucleoli) valori intre 1 si 10 (valoare medie in setul de date: 2.86,

deviatia standard: 3.05)

Mitoses (mitoses) - valori intre 1 si 10 (valoarea medie in setul de date: 1.58, cu

deviatia standard: 1.71)

Atributul de clasa (class) atribut nominal, ia valoarea benign sau malign om functie

de tipul tumorii (in setul nostrum de date apar 241 de cazuri malingne si 458 de cazuri

benigne)

O mai buna idee asupra distributiei generale a datelor se poate obtine din urmatoarea imagine,

care prezinta in ordine, sub forma grafica distributia celor 11 variabile de mai sus in functie de

variabila de clasa:

Preprocesarea setului de date

Preprocesarea unui set de date incepe in mod normal prin eliminarea valorilor aberante.

In cazul nostru 9 dintre atribute definite ca luand valori de la 1 la 10 (pentru atributul id nu se

impune nici o constrangere cu privire la intervalul in care trebuie sa se afle). Din statisticile

descriptive afisate de weka se observa usor ca toate cele 10 atribute respecta aceasta

constrangere : valoarea maxima este 10 iar cea minima este 1 (in figura se poate vedea cazul

variable clump_thick).

In cazul in care am fi avut prezente valori inafara acestui interval eliminarea lor s-ar face

folosind filtrul SubsetByExpression:

Urmatorul pas este reprezentat de eliminarea valorilor lipsa, care se face folosind filtrul

ReplaceMissingValues. In cazult setului nostru de date singura variabila care prezinta valori lipsa

este bare_nuclei (se poate vedea din tabelul de statistici descriptive). Prin folosirea optiunii

ReplaceMissingValues toate valorile lipsa din setul de date vor fi inlocuite cu valoarea medie

(sau moda) corespunzatoare atributului a carui valoare lipseste. Rezultatul acestei operatii este

salvat in fisierul Breast_cancer_wisconsin2.arff, care va fi folosit apoi in analiza.

Cel mai semnificative atribute se pot obtine prin optiunea Select Attributes din meniul

Weka. Se alege Attribute Evaluator si metoda de cautare a atributului Search Metod. In

cazul notru vom alege CvsSubsetEval ca evaluator, respectiv BestFirst ca metoda de cautare.

Optinea CvsSubsetEval presupune evaluarea valorii unui subset de atribute considerand

abilitatea individuala de predictibilitate a acestora cat si gradul de redundanta dintre ele .

In urma acestei prelucrari rezulta ca 9 dintre atribute sunt seminificative:

Clump Thickness (clump_thick) variabila numerica, care reprezinta grosimea

nodulului, pe o scara de la 1 la 10 (grosimea medie in setul de date fiind de 4.41, cu

deviatia standard 2.81)

Uniformity of Cell Size (unif_cell_size) variabila numerica, masoara pe o scara de la 1

la 10 cat de uniforme sunt celulele din punct de vedere al marimii (valoarea medie in

setul nostrum de date fiind 3.31, cu o deviatie standard in valoare de 3.05)

Uniformity of Cell Shape(unif_cell_shape) variabila numerica, masoara pe o scara de

la 1 la 10 cat de uniforme sunt celulele din puct de vedere al formei (valoarea medie

fiind 3.20, cu o deviatie standard in valoare de 2.97 )

Marginal Adhesion (adhesion) variabila numerica, masoara pe o scara de la 1 la 10

aderenta marginala intre celule (in medie 2.80, cu o deviatie standard de 2.85)

Single Epithelial Cell Size (epithelial_cell_size) variabila numerica, reprezinta marimea

unei celule epiteliale, valori de la 1 la 10 (valoarea medie in setul nostru este 3.21 iar

deviatia standard este 2.21)

Bare Nuclei (bare_nuclei) variabila numerica , test cu rezultate intre 1 si 10 (in setul

nostrum de date valoarea intalnita este in medie 3.54, cu o deviatie standard de 3.64)

Bland Chromatin (bland_chromatin) variabila numerica, valori intre 1 si 10 (valoare

medie in setul nostru: 3.43, deviatie standard: 2.43)

Normal Nucleoli (n-nucleoli) variabila numerica, valori intre 1 si 10 (valoare medie in

setul de date: 2.86, deviatia standard: 3.05)

Mitoses (mitoses) - variabila numerica , cu valori intre 1 si 10 (valoarea medie in setul

de date: 1.58, cu deviatia standard: 1.71)

Selectam cele 9 atribute , la care se adauga atributul de clasa , class, care este o variabila

nominal ce poate lua valorile benign sau malingn. Salvam acest subset de date sub numele de

Breast_cancer_wisconsin3.arff.

Clasificare

Clasificarea este o metoda predictiva care face parte din categoria metodelor de invatare supervizate. Clasele sunt reprezentate de valorile atributului clasa (atribut de tip categorial) corespunzator setului de date ales, celelalte variabile avand rolul de predictor. Clasificarea are ca scop realizarea unei predictii asupra clasei unei instante, pornind de la valorile predictorilor.

Acest proces are loc in 2 faze:

Pornind de la o submultime din setul de date cu care lucram (multimea de antrenament) si un algoritm de clasificare (clasificator) se doreste descrierea unui model care descrie cat mai corect pentru instantele din acest set relatiile de asociere dintre valorile variabilelor predictoare si clasa corespunzatoare instantei.

In continuare, folosind instantele neutilizate in etapa anterioara (multimea de testare) se incearca estimarea acuratetii modelului (clasificatorului) . Astfel, pentru fiecare instanta din multimea de testare se aplica clasificatorul iar valoarea optinuta este comparata este comparata cu cea reala. Acuratetea modelului va fi procentul de instante corect clasificate.

Clasificarea este operaia cel mai des folosit de ctre instrumentele comerciale de

data mining. Modul in care instrumentele de data mining analizeaz datele , i tipul de informaie pe care il ofer , depinde de tehnicile pe care le folosete. Cele mai comune tehnici ale clasificrii includ: algoritmul 1R, arbori de decizie, retele neuronale, algoritmi genetici, modelul regulilor de asociere, etc. n continuare se vor prezenta doi dintre acesti algoritmi.

Algoritmul 1R

In evaluarea oricarei metode de invatare empirica avem in vedere doua aspecte:

acuratetea in clasificarea unui set de date de test, respectiv simplitatea. Algoritmul 1R are

avantajul de a fi suficient de simplu si totusi sa mentina un nivel acceptabil de acuratete.

Algoritmul primeste ca si date de intrare un set de instante, fiecare instanta fiind

caracterizata de un numar de atribute si de clase. Programul 1R se aplica pe fiecare atribut,

rezultand un numar de clasificatori egali cu numarul de atribute din care va fi ales cel mai

semnificativ. Atributele pot fi nominale sau continue. Selectia se face pe baza nivelului de eroare

in clasificare. Practic acest algoritm clasificarea se va face in final pe baza unui singur atribut.

Setul nostru de date contine in totalitate atribute nominale. In acest caz tehnica 1R

presupune construirea unor interval in care atributul in calcul va lua valori. Numarul de interval

este egal cu numarul claselor in care vor fi clasificate elementele setului de date.

Algoritmul primeste ca data de intrare un vector v, continand valorile atributului a

considerat in setul de calcul, respectiv clasa lor c corespunzatoare. In final se va optine o regula

de forma if a has value v than class is c, dupa efectuarea urmatorilor pasi:

1. Sorteaza sirul de elemente corespunzator atributului.

2. Construieste interval prin plasarea unui separator intre fiecare pereche diferita

de valori.

3. Repeta

a. Elimina separatorul dintre intervalele care apartin aceleiasi clase

b. Examineaza pierderea de precizie ce are loc in urma acestei eliminari

c. Elimina cele mai putin costisitoare separatoare

Cat timp numarul de interval este diferit de numarul de clase

4. Alege cel mai bun interval gasit in functie de precizia de clasificare.

Pentru cazul nostru, aplicam algoritmul 1R in Weka, bifand optiunea Precentage Split.

Astfel regula de clasificare se construieste pe baza a 66% din baza noastra de date, restul

instantelor fiind folosite pentru testare. Obtinem o clasificare in functie de atributul unif_cell

_size astfel: pentru o valoare mai mica de 3.5 clasa va fi bening iar pentru o valoare mai mare

sau egala cu 3.5 clasa aleasa va fi malign. Acuratetea clasificarii este de 92.01 %, 19 de instante

fiind clasificate gresit dintr-un total de 238 incluse in setul de test. Valoarea statisticii Kappa este

de 0.82 , destul de apropiata de valoarea 1 (valoarea 1 semnifica accord total intre clasificarea

realizata prin aceasta tehnica si valorile observate).

Putem evalua in detaliu acuratetea clasificarii in functie de clasa observata, privind

tabelul de contingenta sau comparand valorile afisate si sumarul afisat deasupra acesteia. Astfel

modelul nostru a gasit 96.1% dintre tumorile benigne si 84.9% din tumorile maligne observate

(sensibilitate:true -positive). In plus putem spune ca probabilitatea ca o tumoare clasificata ca

benigna este intr-adevar benigna este de

91.8% iar probabilitatea ca o tumoare

clasificata maligna sa fie intr-adevar

malinga este de 92.4% (specificitate).

Din matricea de confuzie putem confirma procentajele de mai sus prin valorile exacte

obtinute: dintre cele 238 de instante oferite modelului spre clasificare 146 au fost clasificate

corect ca si beningne respectiv 73 ca maligne. In acelasi timp 6 dintre tumorile benigne au fost

clasificate gresit ca fiind maligne, respectiv 13 dintre cele maligne au fost clasificate gresit ca

fiind benigne.

Practic, algoritmul 1R invata prin analizarea primului nivel al unu arbore de decizie,

realizand toate testele pentru un atribut particular. In cadrul urmatorului algoritm se va discuta

mai pe larg problema arborilor de decizie.

Algoritmul ID3/C4.5 (J48)

Un arbore de decizie este un clasificator care poate fi reprezentat grafic sub forma unui arbore

cu propriettile:

fiecare nod al arborelui reprezint un test pe un anumit atribut si corespunde unei

submultimi ale multimii de antrenament

ramurile care pornesc de la un nod reprezint rezultatele testului;

rdcina corespunde ntregii multimi de antrenament;

frunzele reprezint clasele.

In construirea unui arbore de decizie se aplica o strategie de tip ,,divide et impera:

pentru fiecare nod rezultatul aplicarii testului este partitionarea submultimii corespunzatoare

nodului in submultimi mai mici. Numarul acestor submultimi depinde de tipul atributului testat.

In cazul in care acesta este nominal are loc o partitionare intr-un numar de submultimi egal cu

numarul de valori ale atributului. Daca atributul este numeric, partitionarea se face prin

compararea cu o valoare v, rezultand doua submultimi.

Procesul care creeaz arborele de decizie este numit inductie si cere un numr mic de

treceri prin setul de antrenare. Cei mai multi algoritmi de generarea a arborilor de decizie trec

prin dou faze: faza de construire (crestere) a arborelui( splitting) urmat de faza de tiere

(pruning).

O parte fundamental a oricrui algoritm care construiete un arbore de decizie dintr-un

set de date este modalitatea prin care se selecteaz atributele la nivelul fiecrui nod din

arbore.Acesta problema este extrem de important deoarece atributele care definesc o

nregistrare au contribuii mai mult sau mai putin importante la construirea clasificatorului.

Rezult necesitatea de a gsi un criteriu de selecie a atributelor mai semnificative. Astfel,

punctul central al algoritmilor privind arborii decizionali constau in selectarea atributului ce

urmeaz a fi testat la fiecare nod.

C4.5 (implementat in Weka sub numele J48) este cel mai des folosit algoritm de inducie

a arborilor de decizie, fiind o extensie a algoritmului ID3 care spre deosebire de acesta rezolv

unele probleme precum supra-potrivirea datelor, tratarea atributelor continue i a atributelor

cu valori lips, mrirea eficienei computaionale. Algoritmul C4.5 genereaz un arbore de

decizie prin partiionarea recursiv a mulimii de date, printr-o strategie de parcurgere n

adncime (engl. depth-first). Algoritmul ia n considerare toate testele posibile pentru

partiionarea mulimii de date i selecteaz testul care aduce cel mai mare ctig informaional.

Dac prin entropie nelegem impuritatea unei mulimi de exemple de antrenare S, putem

estima eficiena unui atribut pentru clasificarea acestor exemple. Ctigul informaional (engl.

information gain) msoar reducerea ateptat a entropiei cauzat de partiionarea mulimii

dup valorile unui atribut A.

Algoritmul C4.5(J48 ) primeste ca date de intrare un esantion S din populaia pentru

care se construiete modelul de tip arbore de decizie. Fiecare nregistrare din cadrul

esantionului are are n atribute. In final se va obtine un arbore de decizie, dupa efectuarea

urmatorilor pasi:

Repeta

1. Calculeaz entropia fiecrui atribut pentru toate obiectele esantionului

2. Selecteaz atributul cu entropia cea mai mica (cstigul informaioal

cel mai mare) si valorile acestuia

3. Reduce esantionul pstrnd numai obiectele care prezint valorile atributului

selectat anterior. Reduce numrul de atribute ce definesc obiectele din eantion

cu cel selectat.

Pana cand

- Toate exemplele pentru un anumit nod aparin unei aceleiai clase;

- Nu mai exist nici un atribut pentru partiionri ulterioare;

- Nu rmne nici un exemplu.

-

Dup ce a fost antrenat, un arbore poate prezice o instant nou de date ncepnd de la

nodul rdcin si urmnd o cale n jos pe ramur pn la ntlnirea unui nod frunz. Calea este

determinat prin evaluarea regulilor de tiere bazndu-se pe valorile variabilelor independente

din noua instant. Extragerea de reguli de clasificare din arbore poate fi sintetizat astfel:

Reprezentarea cunostiintelor sub form de reguli IF-THEN;

O regul este creat pentru fiecare cale de la nodul rdcin la un nod frunz;

Fiecare pereche de valori de atribute de-a lungul cii formeaz o conjunctie;

Nodul frunz contine clas predictiei;

Pentru cazul nostru, aplicam algoritmul J48 in Weka, bifand optiunea Precentage Split.

Astfel regula de clasificare se construieste pe baza a 66% din baza noastra de date, restul

instantelor fiind folosite pentru testare. Obtinem un arbore de decizie cu 27 de noduri si 14

frunze. Acuratetea clasificarii este de 95.37 %, 11 de instante fiind clasificate gresit dintr-un total

de 238 incluse in setul de test. Valoarea statisticii Kappa este de 0.90 este destul de apropiata de

valoarea 1, valoare ce semnifica acord total intre clasificarea realizata prin aceasta tehnica si

valorile observate.


tabelul de contingenta sau comparand valorile afisate si sumarul afisat de-asupra acesteia.

Astfel modelul nostru a gasit 95% dintre tumorile benigne si 95% din tumorile maligne

observate (sensibilitate:true -positive). In plus putem spune ca probabilitatea ca o tumoare

clasificata ca benigna este intr-adevar benigna este de 97.3% iar probabilitatea ca o tumoare

clasificata maligna sa fie intr-adevar malinga este de 92.1% (specificitate).




clasificate gresit ca fiind maligne, respectiv 4 dintre cele maligne au fost clasificate gresit ca fiind

benigne.

Regulile de clasificare obtinute pe baza arborelui de mai sus sunt urmatoarele:

IF unif_cell_size= 3 AND

bland_chromatin= 2 AND unif_cell_shape= 2 AND unif_cell_shape= >2 AND unif_cell_size=2 AND unif_cell_size=2

AND clump_thick=2 AND unif_cell_size=2

AND clump_thick=3 AND bare_nucelei= 2 AND unif_cell_shape= >2 AND unif_cell_size=2

AND clump_thick=3 AND bare_nucelei= >6 THEN class=malign

IF unif_cell_size= >2 AND unif_cell_shape= >2 AND unif_cell_size=2

AND clump_thick=>6 THEN class=malign

IF unif_cell_size= >2 AND unif_cell_shape= >2 AND unif_cell_size=>4 THEN class=malign

Analiza regresionala

Pe langa tehnicile folosite de algoritmii de clasificare prezentati mai sus, un alt tip de

model care poate fi construit pentru reprezentarea setului de obiecte poart denumirea de model regresional. Acest model va ingloba matematic relaiile care apar la nivelul setului de atribute a unui obiect ponderate de atributele celorlate obiecte din setul in discuie. Pentru construirea unui astfel de model de clasificare trebuie parcurse urmatoarele etape:

Faza de antrenare (analiza regresionala): cercetarea dependintelor intre variabilele ce caracterizeaza elementele setului de date

Faza de testare: determinarea gradului de dependinta intre variabilele amintite mai sus.

In functie de tipul datelor cu care lucram, exista diferite tipuri de modele regresionale. In

cazul nostru, deoarece ne intereseaza caracterizarea variabilei de clasa care este nominala (cu 2 valori posibile) alegem modelul logistic. Regresia logistica

Se foloseste atunci cand variabila raspuns este binomiala, adica o serie de raspunsuri din

2 variante (in mod traditional o varinata reprezinta succesul si se noteaza cu 1, iar cealalta

esecul si se noteaza cu 0).

Intr-o astfel de regresie ne intereseaza calculul probabilitatii de success in fuctie de

diferiti predictori,sub forma:

nnxxg ...)( 110

unde ix reprezinta predictorii modelului, i reprezinta coeficientii corespunzatori fiecarui

predictor, iar g reprezinta functia logit:

1log)(logit )(g

Pornind de la aceasta ecuatie obtinem probabilitatea de succes :

)...exp(1

)...exp(

110

110

nn

nn

xx

xx

Pentru modelarea unei variabile binomiale printr-un model regresional de tip logistic,

alegem in Weka, in cadrul panoului Classify optiunea SimpleLogistic. De asemenea bifam

optiunea Percentage split, care permite impartirea setului de date in 2: 66% dintre inregistrari

vor fi folosite pentru construirea modelului, iar restul de 33% vor fi folosite in faza de testare.

Observam ca rezultatul este reprezentat de 2 modele. primul modeleaza probabilitatea

de a avea o tumoare benigna, iar cel de-al doilea probabilitatea de a avea o tumoare maligna.

Defapt aceste modele sunt echivalente (sau mai bine spus unul este inversul celuilalt), in sensul

in care daca stim una dintre cele doua probabilitati o putem obtine pe cea de-a doua efectuand

o scadere (suma celor doua probabilitati este 1).

Ne indreptam atentia asupra modelului corespunzator probabilitatii de a avea o

tumoare maligna. Modelul obtinut este urmatorul:

mitosesnucleolinchromatinblandnucleibare

adhesionsizecellunifthickclump

*23.0_*09.0_*16.0_

*19.0*1.0__*22.0_*23.044.4)(logit

de unde

)*23.0_*09.0_*16.0_

*19.0*1.0__*22.0_*23.044.4exp(1

)*23.0_*09.0_*16.0_

*19.0*1.0__*22.0_*23.044.4exp(





Deoarece functia logit este monoton crescatoare iar coeficientii variabilelor predictoare

sunt pozitivi, putem concluziona ca probabilitatea de a avea o tumoare maligna creste odata cu

cresterea scorului obtinut in cadrul testului pentru grosimea nodulului, uniformitatea in

marimea celulelor, aderenta marginale, numarul de nuclei goi, valorea bland chromatin,

numarul de nucleoni respectiv mitoze. De asemenea, datorita faptului ca toti predictorii nostri

sunt definiti pe aceeasi scara, putem cuantifica importanta fiecaruia pornind de la valoarea

coeficientilor lor. Astfel cei mai importanti predictori sunt, la egalitate, clump_thick si mitoses,

iar cel mai slab predictor este n_nucleoli.

In contiunuare Weka ne prezinta rezultatele testarii corectitudinii modelului nostru,

folosind cele 33% de inregistrari pe care le-am rezervat in acest scop. Se poate observa ca

96.21% din instantele ramase au fost clasificate corect folosind modelul nostru. Valoarea

apropiata de 1 a statisticii Kappa (0.91) ne indica faptul ca predictiile obtinute folosind modelul

sunt apropiate de valorile observate. Acest lucru este confirmat si de faptul ca eroarea medie

absoluta si abaterea medie patratica a predictiilor relative la valoarile observate sunt destul de

mici: 0.04 si 0.17.


tabelul de contingenta sau comparand valorile afisate si sumarul afisat de-asupra acesteia.

Astfel modelul nostru a gasit 98% dintre tumorile benigne si 93% din tumorile maligne

observate (sensibilitate:true -positive). In plus putem spune ca probabilitatea ca o tumoare

clasificata ca benigna este intr-adevar benigna este de 96.1% iar probabilitatea ca o tumoare

clasificata maligna sa fie intr-adevar malinga este de 96.4% (specificitate).




clasificate gresit ca fiind maligne, respectiv 6 dintre cele maligne au fost clasificate gresit ca fiind

benigne.

Clasificarea unui obiect necunoscut. Compararea tehnicilor de

clasificare

Dupa cum am spus mai sus, clasificarea are ca scop realizarea unei predictii asupra clasei

unei instante, pornind de la valorile predictorilor. Realizarea oricarei predictii devine importanta

atunci cand nu se cunoaste valoarea reala a cantitatii pe care dorim s-o estimam. In cazul

nostrum scopul studiului a fost acela de a gasi un set de reguli/tehnici cu ajutorul carora sa

putem prezice natura beningna sau maligna a unei tumori pe baza scorului optinut in urma unor

examinari. In continuare vom aplica cele 3 tehnici de clasificare prezentate mai sus asupra unui

nou obiect, un pacient cu urmatoarele rezultate la teste:

Clump_thick=4, Unif_cell_size=2, Unif_cell_shape=3, Adhesion=3, Epithelial_cell_size=4, Bare_nuclei=4, Bland_chromatin=2, n_nuceli=2, Mitoses=3

In Weka dupa crearea fiecarei reguli/machete de

clasificare, avem optiunea de a testa regulile folosind un

set nou de instante (optiunea Supplied Test Set). Astfel am

adaugat datele pacientului intr-un nou fisier arff. Deoarece

este vorba de testare, trebuie sa adaugam o valoare si pentru artibutul clasa. Presupunem ca

pacientul a avut o tumoare beningna, si verificam daca cele 3 tehnici de clasificare confirma sau

infirma aceasta presupunere.

Algoritmul 1R are ca rezultat o regula de clasificare pe baza unui singur predictor: daca

valoarea atributului Unif_cell_size este mai mica decat 3.5 tumoarea se considera ca fiind

benigna, in timp ce valorile peste 3.5 corespund unei tumori maligne. Astfel, pe baza regulii

generate de algoritmul 1R concluzinam ca pacientul nostru are o tumoare benigna.

Urmarind insa arboreal de decizie rezultat in urma aplicarii algoritmului C4.5 (J48) afisat

mai sus vom decide prezenta unei tumori maligne. Acest rezultat se obtine urmarind ramura:

uniff_cell_size3.54, clump_thick>3, bland_chromatin

de unde 30.0)83.0exp(1

)83.0exp( . Astfel probabitatea ca pacientul nostru sa aiba o tumoare

maligna este de 30%, ceea ce ne face sa credem ca tumoarea sa este benigna (bineinteles, fiind

vorba de un diagnostic medical am putea considera o decizie in favoarea scenariului nefavorabil,

desi este mai putin probabil).

Avand in vedere faptul ca prin cele 3 tehnici am obtinut rezultate diferite, ne punem

problema care dintre acestea sunt mai de incredere. Am vazut mai sus ca pentru fiecare dintre

cele 3 tehnici mediul Weka a afisat niste masuri pentru corectitudinea modelului nostru:

acuratete, precizie, eroare medie absoulta, abatere medie patratica, respectiv statistica Kappa.

Un model perfect este caracterizat de o acuratete si precizie de 100%, o valoare a statisticii

Kappa cat mai apropiata de 1, respectiv o eroare medie absolita si o abatere medie patratica cat

mai aproape de 0. In tabelul de mai jos se pot compara valorile obtinute pentru cele 3 tehnici:

1R C4.5 (J48)

Regresia logistica

Acuratete 92.0% 95.37% 96.2%

Precizie (benigne) 91.8% 97.3% 96.1%

Precizie (maligne) 92.4% 92.1% 96.4%

Kappa 0.82 0.90 0.91

Eroare medie absoluta 0.07 0.06 0.04

Abaterea medie patratica 0.28 0.21 0.17

Se poate observa cu usurinta pe baza tabelului ca metoda de clasificare cea mai de

incredere pentru setul nostrum de date, pe baza tuturor criteriilor, este cea obtinuta prin

aplicarea regresiei logistice.

Grupare

Gruparea (Cluster analysis) reprezint o tehnic de mprtire in clase (grupuri) a unui set

de date pentru care nu exist nici o clas predefinita. Fiecare dintre aceste clase este definit de

un model, care poate fi un obiect abstract sau cel mai reprezentativ obiect al clasei. Deci spre

deosebire de clasificare unde se atribuie un element la un set de clase cunoscut, de data aceasta

se incearca gsirea claselor fintr-un set de date (obiecte). n acest scop, tehnicile de grupare

opereaz prin gsirea similaritilor dintre date, n conformitate cu caracteristicile prezente in

datele analizate. Grupurile sunt numite clusteri (clusters).

Mai multe definitii au fost propuse pentru grupare si anume:

Set de elemente asemntoare (similare) cu elementele din interiorul aceluiai cluster.

Elementele din diferite grupri nu sunt asemntoare.

Distanta dintre punctele din cadrul unei grupri este mai mic dect distana dintre un

punct din interiorul gruprii i altul din afara.

Ca i tehnic gruparea reprezint o clasificare nesupervizat deoarece nu exist seturi

predefinite de clase.

In prezent domeniul cluster analisys face apel la un set de tehnici de detectare a grupurilor

de obiecte prezente intr-un set de date. Aceste tehnici sunt:

Algoritmi de partitionare: se construiesc diverse partitii de obiecte, care apoi se

evalueaz dup un set de criterii.

Algoritmi ierarhici: se creeaz o decompozitie ierarhic a unui set de date utiliznd un

set de criterii impuse de utilizator.

Algoritmi probabilistici: Sunt bazati pe calculul functiilor de densitate probabilistice

Algoritmi structurali: Se bazeaz pe analiza structurii obiectelor prezente in setul de date

Algoritmi de tip model: Se propune un model pentru fiecare din clusteri care se doresc a

fi create

In continuare vom exemplifica un algoritm de partitionare (K-means).

Algoritmul K-means

Ca orice tehnica de partitionare, algoritmul K-means construieste o partitionare initiala,

pe care apoi incearca s-o imbunatateasca prin mutarea iterativa a obiectelor dintr-un grup in

altul. Procesul se opreste dupa ce se reuseste impartirea setului de date in k grupuri, cu

proprietatea ca fiecare grup contine cel putin un obiect si fiecare obiect apartine unui singur

grup. Se poate spune ca am obtinut o buna partitionare atunci cand obiectele din cadrul

aceluiasi cluster sunt apropiate (asemanatoare) in timp ce obiectele din clusteri diferiti sunt

distante(foarte diferite).

Tehnicile K-means primesc ca parametrul de intrare valoarea k, care reprezinta numarul

de clusteri in care dorim sa partitionam setul de date. Rezultatul final reprezinta o partitionare

in k clusteri, cu proprietatea ca similaritatea din interiorul clusterilor este ridicat, iar intre

clusteri este sczut. Similaritatea clusterilor este msurat n raport cu valoarea medie a

obiectelor dintr-un cluster, care poate fi vzut ca centru de greutate al clusterului.

Astfel, avand k dat, algoritmul k-means implementeaz partiionarea setului de date

(obiecte) in 4 pai:

1. Partitioneaz obiectele in k subseturi nevide

Repeta

2. Calculeaz centrul de greutate a fiecrui cluster din prezenta partiie. Centrul de

greutate este un obiect generic ce caracterizeaz toate obiectele din clusterul

pe care l reprezint.

3. Atribuie fiecare obiect din setul de date la clusterul care prezint cel mai

apropiat centru de greutate

Pana cnd nu mai este nimic de atribuit.

Acest algoritm este relativ eficient, terminandu-se adesea intr-un optim logal. Optimul

global poate fi gsit utiliznd tehnici ca deterministic annealing si genetic algorithm. Din pacate,

tehnica K-means necesita cunoasterea apriori a valorii lui k, si se poate aplica doar in cazul in

care se poate contrui un centru de greutate al clusterilor (apar problem in cazul atributelor

nominale)

In cazul setului nostru de date, ignorand clasa (optiunea Ignore Attributes) incercam o

noua partitionare a datelor in 2 clusteri, folosind distanta Euclidiana. Pentru evaluarea

partitionarii selectam optiunea Classes to clusters evaluation. Numerele afisate mai jos

reprezinta valorile fiecarui atribut al centroizilor pentru intreg setul de date, si pentru cei doi

clusteri. Centroizii reprezinta niste obiecte generice construite de algoritm, care reprezinta

media obiectelor din cluster/set de date.

Evaluarea calitatiii impartirii se va face acum prin compararea cu partitionarea originala,

data de atributul de clasa. Conform matricii afisate, clusterul 0 corespunde tumorilor maligne si

reuneste 33% din instante, iar clusterul 1 corespunde

celor benign, reunind 67% din instante. Observam ca

4.29% din instante au fost asignate clusterului

corespunzator celeilalte clase, astfel: 11 instante

corespunzatoare unor tumori benign au ajus in clusterul 0,

respectiv 19 cu tumori maligne se afla in clusterul 1.

Metode de grupare ierarhica

Tehnicile de grupare ierarhica pot fi aglomerative sau divizive, in functie de cum se

formeaza descompunerea ierarhica. De asemenea exista mai multe modalitati de calcul ale

similaritatii:

Single Link (metoda celei mai mici distante dintre obiecte) - metoda celui mai

apropiat vecin. Se va considera distanta dintre un cluster si alt cluster ca fiind egal

cu cea mai mic distanta care apare ntre oricare din obiectele clusterului si oricare

din obiectele celuilalt cluster .

Complete Link(metoda celei mai mari distante dintre obiecte) metoda diametrului

sau metoda celui mai ndeprtat vecin. Se va considera distanta dintre un cluster si

alt cluster ca fiind egal cu cea mai mare distanta care apare ntre oricare din

obiectele clusterului si oricare din obiectele celuilalt cluster

Average Link: media distantei dintre obiecte. Se va considera distanta dintre un

cluster si alt cluster ca fiind egal cu cea media distantei care apare ntre oricare din

obiectele clusterului si oricare din obiectele celuilalt cluster

Centroid: distanta dintre centrele clusterului

Algoritmii de grupare ierarhica primesc ca date de intrare un set de n obiecte. Pe baza

acestora calculeaza o matrice de dimensiune nxn cu distantele dintre obiecte. Se urmeaza

urmatorii pasi:

1. Initial fiecare obiect din setul de obiecte va defini un cluster.Astfel vom avea n

clustere fiecare cu un element. In aceast faza distanta dintre clustere este dat de

distanta ntre obiectele care le formeaza.

Repeta

2. Se gseste cea mai similara pereche de clustere si se unesc. Prin urmare pe setul de

obiecte vom avea un cluster mai putin.

3. Se calculeaz distant dintre noul cluster si fiecare din vechile clustere.

Pana cand toate obiectele sunt grupate ntr-un singur cluster de dimensiune n.

Aceast metoda nu necesit specificare numrului de clustere dat de intrare, nsa

impune specificarea acestuia ca si conditie de stopare n cazul n se doreste oprirea procesului

de grupare la atingerea unei anumite structuri de clustere. Ca urmare a procesului de

aglomerarea obiectelor (clustere) n noi structuri de clustere apar partitii numite dendograme.

Astfel ca urmare a acestui proces se va defini un arbore n care frunzele reprezint clusterele

individuale(formate dintr-un singur obiect), rdcina defineste un clusterul de dimensiune n

iarclusterul de la nivelul i este reuniunea clusterelor copii de la nivelul i+1. O noua partitionare

se obtine prin tierea dendogramei la un nivel, componentele care se conecteaz formnd un

nou cluster.

In cazul setului nostru de date, ignorand clasa (optiunea Ignore Attributes) incercam o

noua partitionare a datelor in 2 clusteri, folosind distanta Euclidiana si calculul similaritatii prin

Complete Link. Pentru evaluarea partitionarii selectam optiunea Classes to clusters evaluation.

Evaluarea calitatiii impartirii se va face acum prin compararea cu partitionarea originala, data

de atributul de clasa. Conform matricii afisate, clusterul 0 corespunde tumorilor benign si

contine 77% dintre instante, iar clusterul 1 corespunde celor maligne cu 23% din instante.

Observam ca 12.58% din instante au fost asignate clusterului corespunzator celeilalte clase,

astfel: 5 instante corespunzatoare unor tumori benigne au ajus in clusterul 1, respectiv 83 cu

tumori maligne se afla in clusterul 0. Putem vizualiza arborele rezultat ca urmare a procesului.

Fluxul de analiza Knowledge-Flow

Analiza datelor se poate realiza si folosind mediul Weka Knowledge Workflow:

Concluzii

Asupra setului de date Breast_Cancer_Wisconsin(Original).arff sau exemplicat trei

tehnici diferite de clasificare. Primul algoritm, 1R, incearca realizarea unei clasificari pe baza unui

singur atribut: unif_cell_size. Regula de clasificare obtinuta este: orice pacient cu o valoare a

atributului unif_cell_size

pentru gruparea ierarhica s-a vizualizat arborele de partitionare. Rezultatele obtinute in

comparatia cu clasele reale sunt sumarizate de de tabelul de mai jos, algorimul K-means parand

sa se fi descurcat mai bine pe setul nostru de date:

Algoritmul K-means Algoritm ierarhic Instante grupate in clusterul corespunzator tumorilor benigne(%) 67% 77% Instante grupate in clusterul corespunzator tumorilor maligne(%) 33% 23% Instante grupate gresit(%) 4.29% 12.58% Instante grupate corect in clusterul corespunzator tumorilor benigne 447 453 Instante grupate corect in clusterul corespunzator tumorilor maligne 222 158 Instante grupate gresit in clusterul corespunzator tumorilor benigne 19 83 Instante grupate corect in clusterul corespunzator tumorilor maligne 11 5

Scopul acestui proiect a fost realizarea unei analize in termini de Data Mining a setului

de date BreastCancerWisconsin(Original).arff. In cadrul acesteia s-au folosit diferite tehnici de

grupare si clasificare si grupare si s-a incercat evaluarea perfomantelor acestora. Procesul de

Data mining reprezinta insa proces complex, neexistand retete clare pentru alegerea unei

tehnici in defavoarea alteia. Selectarea algoritmilor potriviti pentru un anumit set de date este

subiectiva si depinde de necesitatile proprietarului de date, de ce se doreste a fi estimat si mai

ales, in ce domeniu si pentru ce sunt folosite rezultatele obtinute in urma aplicarii algoritmilor.

Bibliografie

[1] Holban, S: Curs Data Mining

*2+ Markov Zdravko, Russel Ingrid: An Introduction to the WEKA Data Mining [3] UCI Machine Learning Repository: http://archive.ics.uci.edu [4] Weka 3: Data Mining Software in Java :http://www.cs.waikato.ac.nz/ml/weka/

DataMining_IlicaIoanaMinola

Documents

Transcript of DataMining_IlicaIoanaMinola