UNIVERSITATEA BABEŞ-BOLYAI CLUJ-NAPOCA

FACULTATEA DE MATEMATICǍ ŞI INFORMATICǍ

SPECIALIZAREA INFORMATICǍ ROMÂNĂ

LUCRARE DE DIPLOMǍ

Mașini cu suport vectorial în asistarea diagnosticării medicale

Conducător ştiinţificProf. univ. dr. Czibula Gabriela

Absolvent Bacer Andrei

2013

CUPRINS

INTRODUCERE 4

1. Învățărea supervizată 6

1.1 Ce este învățarea supervizată? 61.2 Pașii rezolvării unei probleme de învățare supervizată 71.3 Probleme majore în învățarea supervizată 81.4 Alți factori care trebuiesc luați în considerare în învățarea supervizată 91.5 Cum funcționează algoritmii de învățare supervizată? 101.6 Minimizarea riscului empiric 111.7 Minimizarea riscului structural 111.8 Măsuri de performanță în învățarea supervizată 121.9 Generalizări ale învățării supervizat 121.9.1 Învățarea semi-supervizată 121.9.2 Învățarea activă 141.9.3 Prezicerea structurată 151.9.4 Învățarea prin clasificare 15

2. Mașini cu suport vectorial 16

2.1 Introducere 162.2 Definiția formală a problemei 172.3 Marje: Intuiții 182.4 Marje funcționale și marje geometrice 192.5 Nuclee 202.6 Clasificatorul binar liniar separabil 232.6.1 Aspecte teoretice 232.6.2 Aplicare practică 262.7 Clasificatorul binar pentru date care nu sunt în totalitate liniar separabile 262.7.1 Aspecte teoretice 262.7.2 Aplicare practică 28

2.8 Mașini cu suport vectorial în probleme de regresie 282.8.1 Aspecte teoretice 282.8.2 Aplicare practică 30

3. Diagnosticarea cancerului la sân folosind tehnici de învățare automată asistată 32

3.1 Introducere 32

3.2 Tehnici de învăţare automată în predicţia ratei de supravieţuire 333.3 Referințe din cercetări anterioare 353.4 Capacitatea predictivă a învăţării automate 353.5 Rolul selecției caracteristicilor 383.6 Performanța asupra seturilor de date neechilibrate 393.7 Mașini cu suport vectorial în clasificarea cancerului la sân 403.8 Alte modalități de diagnosticare a cancerului 433.8.1 Rețele neuronale artificiale 443.8.2 Clasificatorul Naive Bayes 443.8.3 Tehnologia microarray 453.8.4 CAD – Detectarea Asistată de Calculator 463.8.5 Regresia logistică 473.9 Comparație între metode 48

CONCLUZII 50

BIBLIOGRAFIE 51

INTRODUCERE

Diagnosticarea medicală este un proces deosebit de important care, făcut corespunzător și

într-un timp util poate duce la salvarea vieții unui pacient sau cel puțin la prelungirea acesteia.

Eroarea umană poate interveni oricând în acest proces și de aceea o a doua părere nu poate decât

să fie benefică în această situație, fie pentru a confirma diagnosticul pus de medic și deci a îi da o

credibilitate mai mare, fie de a-l infirma și atunci aceasta ar putea sugera o refacere a testelor

pentru a cerceta dacă nu a fost comisă o eroare.

În această lucrare este abordată problema cancerului la sân care este al doilea tip de

cancer cauzator de moarte în cazul femeilor. Diagnosticarea asistată de calculator oferă o opinie

radiologiștilor prin identificarea regiunilor care sunt suspecte de a dezvolta o tumoare malignă cu

o mare acuratețe și relevanță. Cele mai multe studii au demonstrat că diagnosticarea asistată de

calculator are un impact pozitiv asupra detectării timpurii a cancerului la sân. Din toate tehnicile

ne-am oprit asupra mașinilor cu suport vectorial, atât pentru că nu sunt o metodă cu largă

răspândire în acest domeniu față de alte tehnici, cât și pentru puterea lor mare de predicție ce

obține rezultate satisfăcătoare.

În primul capitol este făcută o prezentare generală a învățării supervizate, domeniu din

care fac parte și mașinile cu suport vectorial. Este descris ce presupune o problemă de învățare

supervizată, care sunt pașii ce trebuie urmați în rezolvarea unei astfel de probleme, care sunt

problemele majore cu care ne confruntăm în rezolvarea unei probleme de învățare supervizată și

cum putem măsura performanțele unui astfel de algoritm. În finalul capitolului se prezintă

extensii ale conceptului de învățare supervizată și aplicabilitatea lor, extensii precum învățarea

semi-supervizată, învățarea activă sau învățarea prin clasificare. Cel de-al doilea capitol

introduce noțiunea de mașini cu suport vectorial, explică cum sunt folosiți algoritmii de această

natură și discută despre câteva noțiuni cheie pentru a obține performanțe ridicate, cum ar fi

marjele și nucleul (kernel). Sunt descriși apoi pașii pentru rezolvarea problemelor de clasificare

cu date liniar separabile, a problemelor de clasificare cu date care nu sunt în totalitate liniar

separabile și a problemelor de regresie. În capitolul al treilea sunt prezentate alte abordări din

literatură în asistarea diagnosticării cancerului la sân și performanțele care au fost obținute.

Tehnici precum programarea genetică, algoritmii evolutivi, rețelele neuronale artificiale, rețelele

Bayes, regresia logistică sau tehnologiile microarray sunt aduse în discuție, iar apoi se realizează

o comparație între aceste metode pentru a le sublinia pe cele mai eficiente în diverse situații. În

ultimul capitol este prezentată aplicația care folosește librăria LIBSVM și încearcă să clasifice

corect tumori de cancer la sân în tumori maligne și tumori benigne. Este prezentat modul de

realizare al aplicației, arhitectura acesteia, precum și funcționalitățile pe care le oferă, împreună

cu modalitatea de a o utiliza.

În concluzie, lucrarea dorește să prezinte asistarea diagnosticării cancerului la sân

folosind mașinile cu suport vectorial, prin selecția doar a anumitor caracteristici dorite de

utilizator și selectarea diferiților parametri ce pot influența performanța.

CAPITOLUL 1Învățarea supervizată

Scopul acestui capitol este de a realiza o prezentare generală a conceptului de învățare

supervizată, de a scoate în evidență câteva dintre caracteristicile acestei tehnici de învățare

inteligentă și de a ilustra care sunt pașii rezolvării unei probleme de această natură, împreună cu

o descriere succintă a algoritmului general. În continuare sunt prezentate măsurători de

performanță a algoritmilor de învățare supervizată, iar în finalul capitolului sunt expuse câteva

modalități de generalizare a tehnicii.

1.1 Ce este învățarea supervizată?

Învățarea supervizată este una dintre categoriile principale de probleme ale învățării

automate, iar scopul ei este acela de a deduce o funcție din datele de antrenament pe care le

primește [1]. Aceste date de antrenament sunt o mulțime de perechi, fiecare pereche fiind

compusă dintr-un obiect de intrare (de obicei un vector) și valoarea de ieșire dorită. Un algoritm

de învățare supervizată analizează așadar datele de antrenament pe care le primește și

construiește pe baza lor funcția ce va fi folosită ulterior pentru a clasifica noi exemple. Scenariul

optim al rezolvării unei probleme de acest tip va permite algoritmului dezvoltat să generalizeze

de la datele de antrenament până la situații cu care nu s-a mai confruntat cu rezultate

satisfăcătoare.

Exemple de probleme reale în care se poate aplica învățarea supervizată:

O cameră de urgențe dintr-un spital măsoară 17 caracteristici ale pacienților care ajung

acolo (presiunea sângelui, temperatura, vârsta etc.). Este necesară o decizie pentru a se

stabili care sunt pacienții care au nevoie de îngrijire urgentă, Așadar, problema constă în

identificarea pacienților cu riscuri mari și diferențierea lor de cei cu riscuri mai scăzute.

O companie care acordă credite primește mii de aplicații pentru credite noi. Fiecare

aplicație conține următoarele informații despre persoana care face cererea: vârsta, starea

civilă, salariul anual, alte venituri. Problema o constituie clasificarea aplicațiilor primite

în două categorii: aprobate și neaprobate.

1.2 Pașii rezolvării unei probleme de învățare supervizatăPentru a rezolva o problemă de învățare supervizată, trebuie efectuați următorii pași:

Determinarea tipului datelor de antrenament. Mai înainte de orice altceva, utilizatorul

trebuie să decidă ce tip de date îi este necesar pentru a fi folosit ca set de antrenament. De

exemplu, dacă avem de a face cu o problemă pentru recunoașterea scrisului de mână, o

dată de antrenament poate fi constituită de un singur caracter scris de mână, un cuvânt

sau o propoziție întreagă.

Colectarea setului de antrenament. Setul de date de antrenament trebuie să fie relevant în

aflarea funcției pentru aplicabilitatea acesteia în lumea reală. Așadar, este necesară

adunarea de obiecte de intrare cu valorile de ieșire corespunzătoare fie de la experții

umani, fie din măsurători efectuate.

Determinarea reprezentării caracteristicilor obiectului de intrare. De cele mai multe ori

intrarea este transformată într-un vector de caracteristici, care conține însușiri ce descriu

obiectul. Trebuie avut în vedere faptul că acest număr de trăsături nu trebuie să fie foarte

mare, dar trebuie să fie suficient pentru a putea prezice rezultatul cu acuratețe.

Determinarea structurii funcției de învățare și alegerea algoritmului corespunzător de

învățare (exemple de algoritmi de învățare: arbori de decizie, mașini cu suport vectorial,

rețele neuronale artificiale ș.a.).

Rularea algoritmului de învățare pe setul de antrenament colectat. Unii algoritmi necesită

introducerea anumitor parametri de control, care pot fi ajustați prin optimizarea

peformanței pe un subset (numit set de validare) al setului de antrenament sau prin cross-

validare.

Evaluarea acurateței funcției rezultate pentru un set de test independent de cel pe care s-a

făcut antrenarea.

1.3 Probleme majore în învățarea supervizatăO primă problemă o constituie compromisul dintre prejudiciu și variație [2]. Presupunem

că avem disponibile mai multe seturi de date de antrenament la fel de bune. Un algoritm de

învățare are un prejudiciu pentru o intrare particulară dacă atunci când este antrenat pe fiecare

din aceste seturi de date este sistematic incorect în prezicerea ieșirii corespunzatoare pentru .

Un algoritm de învățare are o variație ridicată pentru o intrare particulară dacă prezice diferite

valori de ieșire când este antrenat pe diferite seturi de date. Eroarea de predicție a unui

clasificator este legată de suma dintre prejudiciul și variația algoritmului de învățare [3]. În

general există un compromis între prejudiciu și variație. Un algoritm de învățare cu un prejudiciu

scăzut trebuie trebuie să fie „flexibil” pentru a putea potrivi datele bine, dar dacă va fi prea

flexibil va potrivi fiecare set de date diferit și de aici va avea o variație mare. Unul dintre

aspectele cheie ale multor tehnici de învățare supervizată este faptul că sunt capabile să ajusteze

acest compromis fie automat, fie prin intermediul unui parametru pe care utilizatorul îl poate

modifica.

O altă problemă este reprezentată de cantitatea de date de antrenament disponibilă

raportată la complexitatea funcției ce trebuie determinată. Dacă funcția ce trebuie învățată este

simplă, atunci un algoritm de învățare „inflexibil” cu prejudiciu mare și variație scăzută va fi

capabil să învețe dintr-o cantitate mică de date, dar dacă funcția este complexă (de exemplu

pentru că implică interacțiuni complexe între multe caracteristici diferite de intrare sau se

comportă diferit în părți distincte ale spațiului datelor de intrare), atunci funcția va putea fi

folosită doar cu ajutorul unei cantități mari de date și cu un algoritm „flexibil”. Prin urmare,

algoritmii de învățare cu rezultate satisfăcătoare reglează valoarea compromisului în funcție de

cantitatea de date existentă și complexitatea funcției ce urmează a fi învățată.

A treia problemă este dată de dimensiunea spațiului intrărilor. Dacă vectorul de

caracteristici are o dimensiune foarte mare, problema de învățare poate fi dificilă chiar dacă

funcția depinde doar de un număr mic de caracteristici. Acest comportament al algoritmului are

loc datorită faptului că dimensiunile „extra” îi pot crea confuzii și pot cauza astfel o variație

ridicată. Prin urmare, un spațiu de intrare cu multe dimensiuni obligă algoritmul să aibă un

prejudiciu ridicat și o variație scăzută. În practică, dacă programatorul reușește să elimine

caracteristicile irelevante din setul de date de intrare, funcția învățată va avea o acuratețe mai

mare. În plus, există mulți algoritmi pentru selecția caracteristicilor meniți să le identifice pe cele

semnificative și să le ignore pe cele care nu sunt de folos în procesul de învățare. Acesta este un

exemplu al unei strategii generale de reducere a dimensiunii spațiului de intrare, care are scopul

de a fixa datele de intrare într-un spațiu de dimensiune mai redusă înainte de a executa algoritmul

de învățare supervizată.

O altă problemă o reprezintă gradul de „zgomot” din valorile de ieșire dorite. Dacă

valorile de ieșire sunt adesea incorecte (datorită erorilor umane sau altor erori), atunci algoritmul

de învățare nu ar trebui să încerce să găsească o funcție care potrivește exact exemplele de

antrenament. Încercarea de a potrivi datele cu prea multă atenție conduce la învățarea pe de rost

(overfitting). Acest fenomen face ca algoritmul să aibă o performanță foarte bună pe datele de

antrenament, dar foarte slabă pe datele de test. Învățarea pe de rost poate să apară chiar și atunci

când nu există erori în efectuarea măsurătorilor dacă funcția pe care algoritmul încearcă să o

învețe este prea complexă pentru modelul de învățare. Într-o asemenea situație acea parte din

funcție care nu poate fi modelată, alterează setul de date de antrenament. În practică se folosesc

diferite abordări în vederea atenuării fenomenului de „zgomot” din valorile de ieșire. Exemple de

astfel de abordări le constituie oprirea timpurie a algoritmului pentru a preveni învățarea pe de

rost sau detectarea acelor exemple de antrenament care sunt suspecte de producere de „zgomot”

și eliminarea acestora înaintea antrenării algoritmului de învățare supervizată.

1.4 Alți factori care trebuiesc luați în considerare în învățarea

supervizatăEterogenitatea datelor este de asemenea importantă în procesul de învățare. Dacă vectorul

de caracteristici conține trăsături de multe tipuri diferite (discrete, discrete ordonate, numerice,

valori continue), unii algoritmi sunt mai ușor de aplicat decât alții din diferite considerente. De

exemplu, algoritmi precum mașinile cu suport vectorial, regresia liniară, regresia logistică,

rețelele neuronale artificiale și metodele care folosesc cel mai apropriat vecin necesită ca datele

de intrare pe care se dorește să se facă antrenarea să fie valori numerice scalate similar (în

intervalul [-1.1]). Metodele care folosesc o funcție de distanță (cel mai apropiat vecin sau

mașinile cu suport vectorial cu nucleu Gaussian) sunt în particular sensibile la această problemă.

Pe de altă parte, arborii de decizie au avantajul de a putea manevra cu usurință datele eterogene.

Datele redundante pot crea dificultăți algoritmului de învățare. În cazul în care

caracteristicile de intrare conțin informație redundantă, algorimi precum regresia liniară sau cea

logistică vor avea o performanță scăzută datorită numeroaselor instabilități numerice. Aceste

inconveniente pot fi rezolvate impunând diferite forme de regularizare a datelor.

Un alt factor care trebuie avut în vedere este prezența interacțiunilor și a neliniarităților.

Dacă fiecare din caracteristici au o contribuție independentă la rezultat atunci algorimii bazați pe

funcții liniare (regresia liniară, regresia logistică, mașinile cu suport vectorial, sistemele Bayes) și

cei bazați pe funcții de distanță (cel mai apropiat vecin, mașini cu suport vectorial cu nucleu

Gaussian) au în cele mai multe cazuri o performanță ridicată. Pe de altă parte, dacă există

interacțiuni complexe între trăsături, atunci rezultate mai bune sunt obținute de arborii de decizie

sau rețelele neuronale artificiale, întrucât acești algorimi sunt în special concepuți pentru a

descoperi aceste interacțiuni. Metodele liniare pot fi la rândul lor aplicate în această situație, dar

programatorul trebuie să specifice manual interacțiunile în momentul în care le folosește.

Alegerea algoritmului de învățare supervizată cel mai potrivit pentru o problemă specifică

este un proces experimental care solicită deseori un timp îndelungat. Având anumite resurse

fixate, de multe ori este mai recomandat să se petreacă mai mult timp cu colectarea mai multor

date și a mai multor caracteristici, decât să se folosească și mai mult timp pentru ajustarea

algoritmului de învățare corespunzător. Cei mai răspândiți algoritmi de învățare supervizată sunt:

mașinile cu suport vectorial, regresia liniară, regresia logistică, clasificatorul bayesian, arborii de

decizie, algoritmul al k-lea cel mai apropiat vecin și rețelele neuronale artificiale.

1.5 Cum funcționează algoritmii de învățare supervizată?Fiind dat un set de modele de antrenament de forma , un algoritm

de învățare caută o funcție , unde este spațiul intrărilor și este spațiul ieșirilor.

Funcția este un element dintr-un spațiu al posibilelor funcții , de obicei numit și spațiul

ipotezelor. Uneori este convenabil să îl reprezentăm pe folsind o funcție de scor

astfel încât este definit ca funcția ce îl întoarce pe , valoarea care dă cel mai mare scor:

. Fie spațiul tuturor funcțiilor de scor.

Deși și pot fi orice spații de funcții, mulți algoritmi de învățare sunt modele

probabilistice în care ia forma unui model de probabilitate condiționată sau

ia forma unui model probabilistic comun . De exemplu, clasificatorul Bayes și

analiza liniară discriminantă sunt modele probabilistice comune, în vreme ce regresia logistică

este un model de probabilitate condiționată.

Există două abordări de bază în alegerea funcțiilor și : minimizarea riscului empiric

și minimizarea riscului structural. Minimizarea riscului empiric caută funcția care se potrivește

cel mai bine cu datele de antrenament, iar minimizarea riscului structural include o funcție de

penalizare care controlează compromisul prejudiciu/variație. În ambele cazuri se presupune că

setul de antrenament constă din perechi independente și identic distribuite . Pentru a

măsura cât de bine o funcție se potrivește pe datele de antrenament, se definește o funcție de

pierdere . Pentru exemplul de antrenament pierderea a prezicerii valorii

este .

Riscul al funcției g este definit ca pierderea așteptată a lui . Acesta poate fi

estimat din datele de antrenament ca fiind .

1.6 Minimizarea riscului empiric

În minimizarea riscului empiric, algoritmul de învățare supervizată caută o funcție care

să minimizeze . Prin urmare, un algoritm de învățare supervizată poate fi construit prin

aplicarea unui algoritm de optimizare pentru găsirea lui . Când este o distribuție de

probabilitate condiționată și funcția de pierdere este probabilitatea negativă a

logaritmului: , atunci minimizarea riscului empiric este echivalentă cu

estimarea probabilității maxime. Când conține multe funcții candidat sau setul de antrenament

nu este suficient de mare, minimizarea riscului empiric conduce la o variație ridicată și la o

generalizare scăzută. Algoritmul de învățare este capabil să memoreze exemplele de antrenament

fără a fi capabil sa generalizeze cu succes exemple la „prima vedere”, ajungându-se din nou la

fenomenul de învățare pe de rost.

1.7 Minimizarea riscului structuralMinimizarea riscului structural încearcă să prevină învățarea pe de rost prin încorporarea

în optimizare a unei penalități de regularizare. O mare varietate de penalități au fost întrebuințate

corespunzător diferitor definiții ale complexității funcției. Să considerăm ca model cazul în care

este o funcție liniară de forma: . O penalitate de regularizare cunoscută este

, care este norma euclideană pătrată a ponderilor sau altfel spus norma . Alte norme pot

fi norma , și norma egală cu numărul de valori nenule . Penalizarea se notează cu

.

Problema optimizării învățării supervizate care se pune este găsirea funcției care

minimizează . Parametrul controlează compromisul prejudiciu-

variație. Când se obține o minimizare a riscului empiric cu prejudiciu scăzut și variație

ridicată. Când are o valoare mai mare, prejudiciul și variația se inversează. Valoarea lui

poate fi aleasă empiric folosind cross-validarea.

1.8 Măsuri de performanță în învățarea supervizată Acuratețea – se calculează ca fiind raportul dintre numărul de exemple corect clasificate

și numărul total de exemple. Este opusul erorii și poate fi calculată pe setul de validare

sau pe setul de test. O singură clasă este importantă (clasa pozitivă), iar restul claselor

sunt negative.

Precizia – numărul de exemple pozitive corect clasificate / numărul total de exemple

clasificate ca fiind pozitive. Reprezintă probabilitatea ca un exemplu clasificat pozitiv să

fie relevant. Precizia este egală și cu TP / (TP+FP), TP = True Positive, FP = False

Positive.

Rapelul – numărul de exemple pozitive corect clasificate / numărul total de exemple

pozitive. Reprezintă probabilitatea ca un exemplu pozitiv să fie identificat corect de către

clasificator. Este egal cu TP / (TP+FN), TP = True Positive, FN = False Negative.

Scorul – combină precizia și rapelul, facilitând compararea a doi algoritmi și este media

armonică dintre precizie și rapel: 2PR / (P+R), P = Precizia, R = Rapelul.

Robustețea – tratarea zgomotelor și a valorilor lipsă.

Scalabilitatea – eficiența gestionării seturilor mari de date.

Interpretabilitatea modelului de clasificare.

Proprietatea modelului de a fi compact.

1.9 Generalizări ale învățării supervizateExistă mai multe modalități în care problemele standard de învățare supervizată pot fi

generalizate.

1.9.1 Învățarea semi-supervizatăÎn această situație valorile de ieșire care se doresc a fi calculate sunt obținute doar dintr-

un subset al datelor de antrenare, restul datelor rămânând neetichetate. În general, cantitatea de

date etichetate este mică în comparație cu cea neetichetată. Învățarea semi-supervizată se situează

undeva la granița dintre învățarea supervizată (care folosește doar seturi de date etichetate) și cea

nesupervizată (fără date de antrenare etichetate). Cercetătorii din domeniul învățării automate au

descoperit că folosirea datelor neetichetate în colaborare cu o cantitate mică de date etichetate pot

produce o îmbunătățire semnificativă în acuratețea învățării. De multe ori obținerea datelor

etichetate este un proces anevoios care necesită un agent uman cu experiență sau un experiment

fizic. Costul asociat procesului de etichetare este considerabil ridicat, în vreme ce folosirea

datelor neetichetate este relativ necostisitoare, ceea ce face acest procedeu al învățării semi-

supervizate să aibă o aplicabilitate foarte justificată în această situație.

Similar algoritmului de învățare supervizată, avem un set de date independente identic

distribuite cu etichetele corespunzătoare . Acestora li se adaugă

date neetichetate . Învățarea semi-supervizată încearcă să folosească această

informație combinată pentru a depăși performanța clasificării, lucru care ar putea fi obținut fie

renunțând la datele neetichetate și aplicând învățarea supervizată, fie lăsând la o parte exemplele

etichetate și aplicând un algoritm de învățare nesupervizată.

Învățarea semi-supervizată poate face referire la învățarea transductivă sau la învățarea

inductivă. Învățarea transductivă are scopul de a deduce etichetele corecte doar pentru datele ce

nu sunt etichetate , vreme ce obiectivul învățării inductive este de a indica corect

potrivirea dintre și . Folosind un exemplu intuitiv, am putea să ne gândim la problema de

învățare ca la un examen, iar ca date etichetate să considerăm problemele care au fost rezolvate

de profesor în clasă. Pe lângă aceste probleme, profesorul de asemenea furnizează un set de

probleme nerezolvate. În abordarea transductivă, aceste probleme nerezolvate sunt ca un examen

pentru acasă, deci scopul este să rezolvi corect aceste probleme în particular. Situația inductivă

va considera că aceste probleme sunt probleme de antrenament asemănătoare cu cele pe care

elevul le va primi la examenul ce se va da în clasă. Nu este necesar (și, potrivit principiului lui

Vapnik este imprudent) să efectuăm învățarea transductivă prin deducerea unei reguli de

clasificare peste întregul spațiu de intrare. Oricum în practică, algoritmii pentru învățarea

transductivă și cea inductivă sunt adesea folosiți alternativ.

Algoritmii de învățăre semi-supervizată folosesc cel puțin una din următoarele ipoteze[4]:

Ipoteza netezirii – punctele care sunt apropiate unul de celălalt fac mai probabil parte din

aceeași etichetă.

Ipoteza grupurilor – datele au tendința de a forma grupuri discrete și punctele din același

grup probabil împart aceeași etichetă.

Ipoteza variației – datele se întind pe o variație aproximativă de dimesiuni mult mai mici

decât spațiul de intrare (aplicabil când date cu foarte multe dimensiuni sunt generate în

urma unui proces, iar modelarea directă a lor poate fi anevoioasă).

1.9.2 Învățarea activăÎnvățarea activă este un caz particular al învățării automate semi-supervizate, în care un

algoritm de învățare este capabil să îi pună întrebări utilizatorului (sau unei alte surse de

informații) pentru a obține rezultatele dorite. În literatura statistică este adeseori numită „modelul

optim experimental” [5][6].

Există situații în care cantitatea de date neetichetate este abundentă și o etichetare

manuală este costisitoare. Într-un asemenea scenariu, algoritmii de învățare pot interoga în mod

activ factorul uman. Acest model de învățare supervizată iterativă este numit și învățare activă.

Datorită faptului că persoana care face antrenarea alege exemplele, numărul de exemple necesare

pentru a învăța un concept poate fi de multe ori mai mic decât numărul de exemple din învățarea

supervizată, dar cu această abordare, există un risc ca algoritmul să fie copleșit de exemple care

nu aduc nicio informație.

Să notăm cu setul total de date ce trebuie luate în considerare. În timpul fiecărei iterații

va fi divizat în 3 subseturi:

1. : Punctele pentru care eticheta este deja cunoscută.

2. : Punctele pentru care eticheta este necunoscută.

3. : Un subset al lui care a fost ales pentru etichetare.

Cele mai multe dintre cercetările curente în domeniul cercetării active sunt preocupate de

cea mai bună metodă de a alege punctele .

Algoritmii pentru determinarea datelor care ar trebui etichetate pot fi organizați în diferite

categorii [5]:

Mostrele de incertitudine: se etichetează acele puncte pentru care modelul curent este cel

mai puțin probabil că va obține rezultatele corecte.

Interogare în urma voturilor „comitetului”: o varietate de modele sunt antrenate pe

actualul set de date etichetate, iar acestea votează pentru rezultatele care se vor obține

pentru datele neetichetate; se vor eticheta acele date pentru care „comitetul” are cele mai

multe păreri diferite.

Schimbarea modelului așteptat: se etichetează acele puncte care ar modifica cel mai mult

modelul curent.

Reducerea erorii așteptate: se etichetează acele date care reduc cel mai semnificativ

eroarea modelului.

Reducerea variației: se etichetează punctele care minimizează variația rezultatului,

aceasta fiind una dintre componentele erorii.

1.9.3 Prezicerea structuratăPrezicerea structurată este un termen folosit în învățarea automată și tehnicile de regresie

care implică prezicerea obiectelor structurate. De exemplu, problema traducerii unei propoziții

din limbaj natural într-o reprezentare sintactică poate fi văzută ca o problemă de predicție

structurată, în care domeniul de ieșire structurat îl constituie mulțimea tuturor arborilor posibili

analizați. Predicția structurată generalizează învățarea supervizată în care domeniul de ieșire este

de obicei un set de dimensiune redusă sau cu o structură simplă.

Modelele grafice probabilistice formează o clasă mare de modele de predicție structurată.

În particular, rețelele Bayes și câmpurile aleatoare sunt folosite cu răspândire în rezolvarea

problemelor de prezicere structurată și au aplicabilitate în multe domenii, printre care

bioinformatica sau recunoașterea vocală. Similar tehnicilor folosite în învățarea supervizată,

modelele de predicție structurată sunt antrenate în general prin intermediul datelor observate în

care valoarea predicției este folosită pentru a ajusta parametrii modelului. Datorită complexității

modelului și a legăturilor dintre variabilele de prezicere, procesul de prezicere folosind un model

antrenat este irealizabil computațional și de aceea se folosește deducția aproximativă.

1.9.4 Învățarea prin clasificareÎnvățarea prin clasificare [7] este un tip de problemă de învățare supervizată sau semi-

supervizată, în care obiectivul este de a construi automat un model ierarhizat din setul de date de

antrenament [1]. Datele pentru antrenare constă într-o listă de elemente cu o anumită ordine

specificată între ele, ordine care este de obicei indusă prin introducerea unui scor numeric sau

ordinal sau a unui raționament binar (de exemplu „relevant” sau „irelevant”) pentru fiecare

element. Clasificarea modelului produce o permutare a elementelor listei într-o nouă listă, ceea

ce într-o anumită măsură este similar procesului de ierarhizare a datelor de antrenament.

Acestă extindere a învățării supervizate este o cercetare relativ recentă, care a apărut și a

luat amploare în ultimul deceniu. Domeniile în care această tehnică a fost aplicată sunt: regăsirea

informației, traducerile automate, biologia computațională și altele.

CAPITOLUL 2Mașinile cu suport vectorial

Acest capitol realizează o prezentare a mașinilor cu suport vectorial și a algoritmilor care

folosesc această tehnică, atât din punct de vedere teoretic, cât și din punct de vedere practic. Este

ilustrată definirea problemei clasice, iar apoi se detaliază diferite tipuri de probleme. Sunt

prezentate prima dată problemele de clasificare pentru date liniar separabile, urmează o extindere

a metodologiei mașinilor cu suport vectorial la date care nu sunt în totalitate liniar separabile, iar

apoi se dezvoltă mai departe acest concept în așa fel încât tehnica să poată fi aplicată în

problemele de regresie. În final sunt prezentate noțiuni despre modificarea paramerilor și a

nucleului în vederea obținerii unor performanțe îmbunătățite.

2.1 IntroducereMașinile cu suport vectorial reprezintă o metodă de clasificare introdusă în anul 1992 de

către Boser, Guyon și Vapnik [8]. Clasificatorul care folosește această tehnică este folosit cu

răspândire, atât în bioinformatică cât și în alte discipline, datorită acurateței ridicate și a abilității

de a se descurca bine atunci când întâlnește date cu multe dimensiuni, cum ar fi expresii ale

genelor, dar și pentru flexibilitatea în modelarea diferitelor surse de date [9].

Mașinile cu suport vectorial aparțin unei categorii generale de „metode cu nucleu”. O

astfel de metodă este un algoritm care depinde de date doar prin produse scalare. Când este

necesar, produsul scalar poate fi înlocuit de o funcție nucleu, care calculează acest produs scalar

într-un posibil spațiu de caracteristici multidimensional. Această abordare are două avantaje.

Primul dintre ele este capacitatea de a genera decizii neliniare asupra limitelor folosind metode

construite pentru clasificatorii liniari. Al doilea avantaj îl constituie faptul că folosirea funcțiilor

nucleu permit utilizatorului să aplice un clasificator datelor care nu au o reprezentare a spațiului

vectorial de dimensiune fixă. Printre primele exemple de astfel de date în bioinformatică se

numără ADN-ul și structura proteinelor.

Folosirea mașinilor cu suport vectorial necesită o înțelegere în profunzime a modului în

care acestea funcționează. Când se antrenează un algoritm de mașini cu suport vectorial,

practicantul trebuie să ia un anumit număr de decizii importante: cum vor fi datele preprocesate,

ce fel de nucleu se va folosi și, în final, setarea parametrilor atât pentru nucleu cât și pentru

mașinile cu suport vectorial. Alegerile uniforme pot conduce la o performanță scăzută [10].

2.2 Definiția formală a problemeiMașinile cu suport vectorial construiesc un hiperplan sau o mulțime de hiperplane într-un

spațiu cu mai multe dimensiuni sau cu un număr infinit de dimensiuni, care pot fi utilizate pentru

clasificare, regresie sau alte sarcini. Intuitiv, o bună separare este obținută de hiperplanul care are

cea mai mare distanță până la cea mai apropiată dată de antrenament reprezentată indiferent de

clasa din care aceasta face parte (numită și marjă funcțională), având în vedere că în general cu

cât este mai mare marja, cu atât este mai redusă eroarea de generalizare a clasificatorului.

Chiar dacă problema inițială este specificată într-un spațiu finit dimensional, se întâmplă

de multe ori ca mulțimile care trebuie distinse să nu fie separabile liniar în acel spațiu. Din acest

motiv a fost propus ca spațiul finit original să fie potrivit într-unul mai mare ca dimensiune,

separarea fiind probabil mai ușor de făcut în acest nou spațiu. Pentru a păstra un efort

computațional rezonabil, potrivirile folosite de schemele mașinilor cu suport vectorial sunt

construite în așa fel încât să poată asigura că produsele scalare vor putea fi calculate cu ușurință

în ceea ce privește variabilele din spațiul original, prin definirea unei funcții nucleu

selectate să satisfacă cerințele problemei [10]. Hiperplanele din spațiul cu mai multe dimensiuni

sunt definite prin mulțimi de puncte al căror produs scalar cu un vector din acel spațiu este

constant. Vectorii care definesc hiperplanurile pot fi aleși ca fiind combinații liniare cu

parametrii ai imaginilor vectorilor de caracteristici care există în baza de date. Folosind

această alegere a hiperplanului, punctele din spațiul caracteristicilor care sunt potrivite în

hiperplan sunt definite prin relația . În cazul în care devine

mai mic pe măsură ce crește și mai mult față de , fiecare element din sumă măsoară gradul

de apropiere al punctului de test față de punctul corespunzător din baza de date . În aceste

condiții, suma nucleelor poate fi utilizată în vederea măsurării apropierii relative al fiecărui punct

de test în comparație cu punctul original aparținând uneia dintre mulțimile ce trebuiesc distinse.

Trebuie menționat faptul că mulțimea de puncte potrivită în hiperplan poate fi destul de

înfășurată ca rezultat, permițând deosebiri mult mai complexe între seturi, care nu sunt convexe

deloc în spațiul original.

2.3 Marje: IntuițiiÎn această secțiune vom descrie intuițiile referitoare la marje și la „încrederea” în

predicțiile pe care le facem. Să considerăm regresia logistică, în care probabilitatea

este modelată de . În acest caz vom prezice „1” pentru o intrare

dacă și numai dacă , sau în mod echivalent, dacă și numai dacă .

Considerăm un exemplu pozitiv de antrenament . Cu cât este mai mare , cu atât mai

mare este și deci cu atât mai mare va fi gradul de „încredere” că

eticheta va fi 1. Așadar, în mod informal, ne putem gândi la predicția noastră ca având o

încredere foarte mare că , dacă . În mod similar, în cazul regresiei logistice o

predicție are încredere mare că , dacă . Această idee va fi formalizată utilizând

noțiunea de marjă funcțională.

Pentru un alt tip de intuiție, vom considera figura următoare în care x-urile reprezintă

exemple de antrenament pozitive, o-urile exemple de antrenament negative, o limită de decizie

(dreapta dată de ecuația și numită hiperplan separator) este de asemenea reprezentată și

trei puncte au fost etichetate A, B și C.

Este de remarcat faptul că punctul A este foarte îndepărtat de limita de decizie. Dacă

dorim să facem o predicție pentru valoarea a lui A ar trebui să fim foarte convinși că în acel

punct . În schimb, punctul C este foarte apropiat de limita de decizie pe care vom prezice

că și o mică modificare în alegerea limitei de decizie ar conduce cu ușurință predicția

noastră la . Luând în considerare aceste aspecte suntem mult mai încrezători de predicția

noastră în punctul A, decât de cea în C. Punctul B se situează undeva între aceste două cazuri și

în sens mai larg, observăm că dacă un punct este departe de hiperplanul separator suntem

semnificativ mai încrezători în predicția făcută. Această noțiune are denumirea de marjă

geometrică.

2.4 Marje funcționale și marje geometriceVom formaliza noțiunile de marjă funcțională și marjă geometrică. Fiind dat un exemplu

de antrenament vom defini marja funcțională a lui în raport cu un exemplu de

antrenament ca fiind . Să remarcăm faptul că, dacă , pentru a avea

o marjă funcțională mare (pentru ca predicția noastră să fie sigură și corectă), este necesar ca

să fie un număr pozitiv mare. În caz contrar, dacă , atunci trebuie

să fie un număr negativ mare. Mai mult decât atât, dacă , atunci predicția

noastră pe exemplul corespunzător este corectă. Prin urmare, o marjă funcțională mare

simbolizează o predicție sigură și corectă.

Pentru un clasificator liniar cu alegerea lui dată de (luând

valori din mulțimea {-1,1}), există o proprietate a marjei funcționale care o face să nu fie o foarte

bună măsurătoare a siguranței. Dându-se alegerea noastră pentru , observăm că, înlocuind

cu și cu , din moment ce , nu se va modifica

deloc, ceea ce înseamnă că , și prin urmare , depind doar de semnul, nu și de mărimea

lui .

Pentru analizarea marjei geometrice vom considera figura următoare:

Limita de decizie corespunzătoare lui este reprezentată împreună cu vectorul .

Se observă faptul că este ortogonal (la ) pe hiperplanul separator. Considerăm punctul A

care reprezintă intrarea pentru un exemplu de antrenament cu eticheta . Distanța lui

față de limita de decizie este dată de segmentul AB.

Cum putem găsi așadar valoarea lui ? Considerăm un vector unitate îndreptat în

aceeași direcție. Din moment ce A îl reprezintă pe , atunci B este dat de .

Acest punct se află situat pe limita de decizie și toate punctele situate pe limita de decizie satisfac

ecuația . Deci, .

Calculând obținem

Formula obținută se aplică pentru un exemplu pozitiv de antrenament A din figură, unde

situarea de partea „pozitivă” a limitei de decizie este benefică. Mai general, marja geometrică a

lui este definită în raport cu exemplul de antrenament ca fiind

Să observăm că dacă atunci marja funcțională este egală cu marja geometrică

ceea ce creează o legătură între aceste două noțiuni diferite de marje. De asemenea, marja

geometrică este invariantă la modificarea parametrilor și din acest motiv în momentul în care

încercăm să ajustăm valorile lui și pentru setul de antrenament putem impune o

constrângere de scalare arbitrară asupra lui fără a modifica nimic important.

În final, pentru un set de antrenament dat vom defini marja

geometrică în raport cu ca fiind cea mai mică dintre marjele geometrice ale exemplelor

individuale de antrenament:

2.5 Nuclee

În discuţia axată pe regresia liniară, se dădea o problemă în care – variabilă de intrare,

este zona locuibilă dintr-o casă, şi s-a considerat interpretarea regresiei folosind caracteristicile

, , pentru a obţine funcţii cubice. Pentru a distinge între cele două seturi de variabile, se

denumesc “original” atributele unei probleme (în acest caz , arealul locuibil). Potrivirea

acestora cu un set nou de cantităţi care sunt apoi trimise algoritmului de învăţare, se numesc

“caracteristici de intrare”. Se exprimă φ ca fiind potrivirea caracteristicii, care ajustează de la

atribute la caracteristici. De exemplu, se dă :

Decât să se aplice MSV folosind atributele de intrare originale , se poate învăţa folosind

nişte caracteristici . Pasul următor este de a înlocui în algoritmul anterior cu .

Deoarece algoritmul poate fi scris în întregime în produse scalare , înseamnă că se vor

înlocui toate produsele cu .În mod specific, fiind dată o funcţie de potrivire , se

defineşte nucleul corespondent ca fiind :

Apoi, în fiecare loc unde apare în algoritm, se va putea înlocui simplu cu

, iar algoritmul va învăţa folosind caracteristica .

Acum, fiind dat , se va putea calcula uşor găsind şi luând produsul

lor scalar. Faptul cel mai interesant este că pentru este de multe ori foarte uşor de

determinat rezultatul, chiar dacă în sine, este costisitor de calculat. În aceste situaţii,

folosind în algoritm o metodă eficientă de a calcula putem determina MSV să înveţe

spaţii de caracteristici de dimensiuni mari fiind dat φ, dar fără a avea de găsit în mod explicit sau

de reprezentat vectorii .

Spre exemplu, presupunând şi considerând , putem scrie

aceasta astfel:

unde, vedem că , unde potrivirea caracteristicii este dată de (în

acest ca pentru n =3)

Se observă că în timp ce calculăm de dimensiuni mari ce necesită complexitate de

timp , găsirea lui necesită complexitate de doar – dimensiune liniară a

atributelor de intrare.

Pentru un nucleu relatat, se consideră de asemeni:

Aceasta corespunde cu potrivirea caracteristicilor pentru

unde parametrul controlează ponderea relativă între termenii şi . Într-un sens mai larg,

nucleul corespunde potrivirii caracteristicilor unui spaţiu care

concordă cu monoamele de forma responsabile de . Oricum, în ciuda faptului că

se lucrează în spaţiu dimensional de forma , calculul lui necesită doar timp.

Se presupune pentru o problemă de învăţare că se doreşte utilizarea funcţiei care

este considerată o măsură rezonabilă pentru a stabili cât de similare sunt şi . De exemplu se

alege reprezentarea:

Aceasta este o măsură rezonabilă a similarităţii dintre şi şi se apropie de 1 când şi

au valori apropiate, sau de 0 când şi sunt îndepărtate. Acest exemplu se poate folosi ca

definiție a nucleului în MSV. (nucleul este denumit Gaussian şi corespunde unei potriviri de

caracteristici , cu dimensiune infinită). Generalizând, fiind dată o funcţie , cum se poate

stabili dacă este un nucleu valid? Pentru a demonstra, se poate stabili dacă există vreo potrivire

de caracteristici astfel încât pentru orice și ?

Se presupune că este în mod cert un nucleu valid ce corespunde unei potriviri de

caracteristici . Acum se consideră un set finit de m puncte (nu neapărat setul de antrenament)

şi fie o matrice pătratică de dimensiune definită astfel încât intrarea sa să

fie dată de . Această matrice este numită matricea nucleului. A se lua în calcul

faptul că s-a notat cu funcţia nucleului şi matricea nucleului , datorită relaţiei

evidente dintre ele.

Ideea centrală subliniază că nucleele au o aplicabilitate semnificativ mai largă decât

utilitatea în MSV. Particularizând, pentru orice algoritm de învăţare care se poate scrie doar în

termeni de produse scalare între vectorii atributelor de intrare, atunci înlocuind acestea

cu unde este un nucleu, se poate permite algoritmului să lucreze eficient în spaţii de

caracteristici de dimensiuni mari corespondente lui K.

2.6 Clasificatorul binar liniar separabil2.6.1 Aspecte teoretice

Considerăm că avem puncte de antrenament, pentru care fiecare punct de intrare are

atribute (adică punctele au dimensiunea ) și aparțin uneia dintre cele două clase

sau . Cu aceste presupuneri, datele de antrenament vor avea următoarea formă:

Dacă datele sunt liniar separabile înseamnă că putem trasa o linie pe graful dintre și

care să separe cele două clase atunci când și un hiperplan pe grafurile

pentru situația în care .

Hiperplanul poate fi descris de formula unde:

este normala hiperplanului;

este distanța perpendiculară de la hiperplan până la origine.

Vectorii suport sunt exemplele cele mai apropiate de separarea hiperplanului, iar scopul

mașinilor cu suport vectorial (MSV) este de a orienta acest hiperplan într-o manieră în care să

fie situat la o distanță cât mai mare de cel mai apropiat membru al fiecărei clase.

Figura 1: Hiperplan prin două clase liniar separabile

Făcând referire la Figura 1, implementarea mașinilor cu suport vectorial se reduce la

selecția variabilelor și în așa fel încât datele de antrenament să poată fi descrise de

formulele:

Aceste inecuații pot fi combinate în una singură de forma:

Considerând punctele cele mai apropiate de hiperplanul separator (vectorii suport

reprezentați în cercuri în diagramă), cele două planuri și pe care aceste puncte se găsesc

pot fi descrise prin:

Definim ca fiind distanța de la la hiperplan, iar de la până la acesta.

Echidistanța hiperplanului între și semnifică faptul că , lucru cunoscut și sub

denumirea de „limita” mașinilor cu suport vectorial. În scopul orientării hiperplanului cât mai

departe posibil de vectorii suport, trebuie să maximizăm această limită. Conform geometriei

vectoriale, limita este egală cu și maximizarea ei este echivalentă cu găsirea astfel

încât .

În scopul de a satisface constrângerile din această minimizare, este necesar să le alocăm

multiplicatori Lagrange , unde :

Vrem să găsim valorile pentru și care minimizează, și acel care maximizează

echivalența precedentă. Acest lucru îl putem face prin diferențierea lui în raport cu ,

respectiv cu și egalarea acestor derivate cu 0. Așadar vom obține:

Înlocuind aceste relații în cele de mai sus, obținem o nouă formulă, dependentă de pe

care trebuie să o maximizăm:

astfel încât

unde

astfel încât

Făcând trecerea de la minimizarea lui la maximizarea lui trebuie să găsim:

Aceasta este o problemă de optimizare pătratică convexă și folosind un rezolvitor de

programare pătratică, îl vom afla pe , iar apoi îl vom obține pe , singurul lucru care mai

rămâne fiind astfel aflarea lui b.

Orice punct care satisface relațiile de mai sus și este un vector suport va avea forma

, adică . În relația precedentă reprezintă

mulțimea de indici ai vectorilor suport. va fi determinat prin găsirea indicilor pentru care

. Înmulțind relația cu și folosind , avem . În loc să

folosim un vector suport arbitrar este mai indicat să se considere o medie a tuturor vectorilor

suport din de forma .

Am obținut astfel valorile pentru variabilele și care definesc orientarea optimă a

hiperplanului separator și deci mașina cu suport vectorial căutată.

2.6.2 Aplicare practicăPașii ce trebuie urmați pentru folosirea mașinilor cu suport vectorial în rezolvarea

problemelor de clasificare pentru date liniar separabile sunt:

Crearea lui , unde .

Găsirea lui astfel încât este maximizată, cu condițiile ca și

. Acest lucru se face folosind programarea pătratică.

Calcularea lui .

Determinarea mulțimii de vectori suport prin găsirea indicilor care satisfac condiția

Calcularea lui .

Fiecare punct nou este clasificat prin evaluarea .

2.7 Clasificatorul binar pentru date care nu sunt în totalitate liniar

separabile2.7.1 Aspecte teoretice

În scopul de a extinde metodologia mașinilor cu suport vectorial pentru a putea manevra

date care nu sunt în totalitate liniar separabile, vom slăbi constrângerile din formulele pentru

datele liniar separabile pentru a permite puncte clasificate greșit. Acest lucru se face introducând

o variabilă slabă , ceea ce înseamnă că vom obține formulele:

;

;

.

Aceste inegalități pot fi combinate în una singură de forma:

, unde .

Figura 2: Hiperplan prin două clase neliniar separabile

În cazul acestor mașini cu suport vectorial cu limite ușoare, punctele aflate în partea

greșită a limitei au o penalizare care crește odată cu distanța față de această limită. Având în

vedere încercarea de a reduce numărul de date clasificate eronat, o modalitate de adaptare a

funcției obiectiv de la datele liniar separabile este găsirea , astfel încât

, unde parametrul controlează compromisul între variabila

ușoară de penalizare și dimensiunea limitei. Folosind ca și în abordarea precedentă multiplicatori

Lagrange, trebuie sa minimizăm în raport cu , și și să maximizăm în raport cu (unde

:

Calculând diferențialele în raport cu , și și egalându-le cu 0 obținem:

Făcând înlocuirile, are aceeași formă ca în cazul clasificării datelor liniar separabile,

dar împreună cu se obține . Prin urmare trebuie să găsim:

astfel încât și . În continuare este calculat

într-o manieră asemănătoare, doar că aici vectorii suport utilizați în calculul lui sunt

determinați prin găsirea indicilor pentru care .

2.7.2 Aplicare practicăPașii ce trebuie urmați pentru folosirea mașinilor cu suport vectorial în rezolvarea

problemelor de clasificare pentru date care nu sunt în totalitate liniar separabile sunt:

Crearea lui , unde .

Alegerea nivelului de semnificație la care vor fi tratate datele clasificate greșit, prin

alegerea unei valori potrivite pentru paremetrul .

Găsirea lui astfel încât este maximizată, cu condițiile ca

și . Acest lucru se face folosind programarea pătratică.

Calcularea lui .

Determinarea mulțimii de vectori suport prin găsirea indicilor care satisfac condiția

Calcularea lui .

Fiecare punct nou este clasificat prin evaluarea .

2.8 Mașini cu suport vectorial în probleme de regresie2.8.1 Aspecte teoretice

În locul încercării de a clasifica noi variabile la prima vedere în una din cele două

categorii menționate anterior , în cazul problemelor de regresie se dorește prezicerea

unei valori reale pentru , ceea ce înseamnă că datele de antrenament vor fi de forma:

unde

Figura 3: Regresie cu tub -insensibil

Problemele de regresie care folosesc mașinile cu suport vectorial vor folosi o penalizare

mult mai rafinată decât în situația precedentă, ele nealocând o penalizare dacă valoarea prezisă

este la o distanță mai mică decât valoarea actuală , ceea ce se poate exprima și prin

inegalitatea . Făcând referire la Figura 3, regiunea delimitată de este

denumită tub -insensibil. Cealaltă modificare efectuată asupra funcției de penalizare este că

variabilelor de ieșire situate în afara tubului le sunt atribuite una din valorile variabilelor ușoare

de penalizare, în funcție de situarea acestora deasupra sau dedesubtul tubului (unde

>0, <0 ):

Funcția de eroare pentru mașinile cu suport vectorial pentru regresie poate fi scrisă astfel:

Această funcție trebuie minimizată în raport cu constrângerile >0, <0 și

, . Pentru a face acest lucru vom introduce multiplicatorii

Lagrange :

Înlocuindu-l pe și calculând diferențialele în raport cu , , și egalându-

le cu 0 vom obține:

Făcând înlocuirile în primele două egalități trebuie să îl maximizăm pe în raport cu

și ( ) unde:

Folosind constrângerile împreună cu ultimele două diferențiale

obținem și , ceea ce înseamnă că trebuie să găsim:

astfel încât , și . Făcând ultimele înlocuiri

predicția lui poate fi calculată cu relația

.

O mulțime de vectori suport poate fi construită prin găsirea indicilor pentru care

și (sau ).

Aceasta înseamnă că îl putem calcula pe b:

.

La fel ca în cazul problemelor de clasificare este mai indicat ca în calculul lui b să se

folosească media dintre toți indicii din :

2.8.2 Aplicare practicăPașii ce trebuie urmați pentru folosirea mașinilor cu suport vectorial în rezolvarea

problemelor de regresie sunt:

Alegerea nivelului de semnificație la care vor fi tratate datele clasificate greșit și cât de

întinsă și insensibilă ar trebui să fie regiunea de pierdere, prin alegerea unor valori

potrivite pentru parametrii și .

Găsirea lui și astfel încât

este maximizată,

cu condițiile ca , și . Acest lucru se face

folosind programarea pătratică.

Calcularea lui .

Determinarea mulțimii de vectori suport prin găsirea indicilor care satisfac condiția

și .

Calcularea lui

.

Fiecare punct nou este clasificat prin evaluarea +b.

CAPITOLUL 3Diagnosticarea cancerului la sân folosind tehnici de învățare

automată asistată

În acest capitol sunt prezentate diverse tehnici de învățare automată asistată folosite în

diagnosticarea cancerului la sân, alături de rezultatele pe care le-au obținut și de o scurtă analiză

a performanței. Sunt prezentate modalități de asistare a diagnosticării folosind programarea

genetică, mașinile cu suport vectorial, algoritmii evolutivi, rețelele neuronale artificiale, regresia

logistică, rețele Bayes, tehnologia microarray sau arborii de decizie. În final este făcută o

comparație între metodele folosite, precizându-se care sunt situațiile în care este mai indicat să

aplicăm o metodă în detrimentul alteia.

3.1 IntroducereCancerul de sân se defineşte ca o creştere necontrolată a celulelor din acea zonă. Cancerul

apare ca rezultat al mutaţiilor sau al schimbărilor anormale în genele responsabile de creşterea şi

menţinerea în stare sănătoasă a celulelor. Genele se găsesc în fiecare nucleu al celulei ce poate fi

numit “camera de control”. În mod normal, celulele în corpul uman se înlocuiesc periodic într-un

proces ordonat de creştere a celulelor, prin declanșarea unor anumite gene şi stoparea altora.

Celulele care nu respectă şablonul dobândesc abilitatea de a se divide continuu, fără control,

producând multe celule la fel ca ele şi alcătuind o tumoare.

O tumoare poate fi benignă (nedăunătoare sănătăţii) sau malignă (pune în pericol

sănătatea). Tumorile benigne nu sunt considerate canceroase: celulele lor apar normale din punct

de vedere al caracteristicilor fizice, cresc încet, nu invadează ţesuturile împrejurătoare şi nici nu

se dispersează în alte părţi ale corpului. Tumorile maligne, în schimb, sunt canceroase. Mai puţin

cunoscut, cancerul de sân poate începe în ţesuturile somatice (G.L Takkab, 2003) [11] care

include ţesuturi ale sânului conectate prin grăsimi şi fibre. Totuşi, doar 5-10% din cazurile de

cancer sunt datorate unei anormalităţi moştenite de la tată sau de la mamă. Aproximativ 90% din

cazuri sunt datorate defectelor genetice care rezultă din procesul de îmbătrânire al vieţii în

general. Una din problemele esenţiale în prezent este diagnoza şi anume definirea şi clasificarea

cancerului cu resurse financiare minime. Câteva tehnici de inteligenţă artificială sunt aplicate cu

succes într-o varietate largă de probleme din domeniul medical, în categoria de luare a deciziilor.

Recurenţa cancerului a atras multă atenţie din partea specialiştilor, dar şi a pacienţilor.

Problema clinică fundamentală este că prima detectare a tumorii se întâmplă când deja apar

simptome de metastază. Chiar dacă pacienţilor li se prescriu tratamente precum chimioterapia,

terapii pe bază de radiaţii sau chiar intervenţii chirurgicale, acestea nu oferă nicio siguranţă că

metastazele nu vor reveni. În ciuda evoluţiei semnificative în domeniul tratării cancerului,

abilitatea de a prezice comportamentul metastazelor încă rămâne o provocare în domeniul

oncologiei. Diverse studii au fost efectuate pentru a prezice recurenţa cancerului de sân.

Modelele tradiţionale de predicţie s-au dovedit a conţine anumite restricţii în a se adresa

heterogenităţii cancerului.

Într-o lucrare publicată în “Science Translational Medicine”, informaticienii şi

patologiştii de la Stanford au raportat studiul lor de a antrena calculatoarele să analizeze imagini

microscopice ale cancerului de sân. Analiza efectuată de calculator era mai precisă decât cea

efectuată de oameni. Prin utilizarea calculatoarelor cu instrumente automate, volumele mari de

date medicale sunt colectate şi făcute disponibile grupurilor de cercetare. Ca o consecinţă,

tehnicile de inteligenţă artificială au devenit un instrument de cercetare popular pentru personalul

medical în a identifica şi exploata legătura şi similitudinea numeroaselor variabile, fiind apoi în

măsură să prezică efectul unei boli pe baza seturilor de date istorice.

Pentru a elimina operatorul de dependenţă şi a îmbunătăţi acurateţea diagnosticului,

sistemul de diagnosticare asistată de calculator oferă un mijloc benefic şi valoros de detectare a

cancerului la sân şi clasificarea lui. În general, un sistem este alcătuit din patru etape: pre

procesare, segmentare, extragerea şi selecţia trăsăturilor şi clasificare.

3.2 Tehnici de învăţare automată în predicţia ratei de supravieţuireCapacitatea de a clasifica corect pacienţii cu cancer în clase de risc, și anume de a prezice

rezultatul patologiei la nivel individual, este un ingredient cheie în luarea deciziilor terapeutice.

În ultimii ani, datele cu expresii genice au fost folosite cu succes pentru a completa criteriile

clinice și histologice utilizate în mod tradițional în astfel de predicții. Multe semnături de expresii

genice au fost dezvoltate, spre exemplu seturi de gene ale căror valori dintr-o tumoare pot fi

folosite pentru a prezice rezultatul patologiei. Aici vom investiga utilizarea tehnicilor de învățare

automată pentru a clasifica pacienţii cu cancer de sân, utilizând una dintre aceste semnături

numită „gena 70”.

Programarea genetică (PG) lucrează în mod semnificativ mai bine decât Maşinile cu

Suport Vectorial, perceptronii multistrat și păduri aleatorii în clasificarea pacienților din setul de

date cancer de sân NKI, şi este comparabilă cu metoda iniţială bazată pe notare propusă de

autorii tipului „gena 70”. Mai mult, PG este capabilă de a efectua o selecție automată de

caracteristici.

Terapiile de cancer actuale au efecte secundare grave: în mod ideal, tipul și doza de

tratament ar trebui să fie adaptate pentru fiecare pacient în parte în funcţie de riscul de recidivă al

bolii. Prin urmare, clasificarea pacienţilor cu cancer în clase de risc este un domeniu de cercetare

foarte activ, cu aplicaţii clinice directe. Până de curând clasificarea pacienţilor era bazată pe o

serie de parametri clinici și histologici. Apariția tehnicilor capabile de a măsura expresia genelor

a condus în ultimul deceniu la o accentuare a cercetării în domeniul expresiei genelor în cancer,

și în special în posibilitatea de a utiliza datele cu expresii genice pentru a îmbunătăţi clasificarea

pacientului. Semnătura unei gene este un set de gene ale căror nivele de expresie pot fi folosite

pentru a prezice o stare biologică: în cazul cancerului, semnăturile genei au fost dezvoltate atât

pentru a distinge bolile canceroase de cele non-canceroase și de a clasifica pacienții cu cancer

bazându-se pe agresivitatea tumorii, măsurată de exemplu prin probabilitatea de recurenţă într-un

timp dat.

În timp ce multe studii au fost dedicate identificării semnăturilor genice în diferite tipuri

de cancer, problema algoritmilor care urmează să fie utilizaţi pentru a maximiza puterea

predictivă a unei semnături genice a primit mai puțină atenție. Pentru a investiga această

problemă sistematic, s-a considerat una dintre cele mai bune semnături genice stabilite,

semnătura „gena 70” pentru cancerul de sân, și s-a comparat performanţa a patru tipuri de

învăţare automată în utilizarea acestei semnături pentru a prezice rate supravieţuire a unui grup

de pacienţii cu cancer de sân. Semnătura „gena 70” este un set de caracteristici microarray

selectat [19] în baza unei corelaţii cu supravieţuirea, pe care se bazează testul molecular de

prognoză pentru cancerul de sân. A fost realizată o comparație sistematică a performanței a patru

algoritmi de învățare automată folosind aceleași caracteristici pentru a prezice aceleași clase. În

comparație, selecția caracteristică nu este astfel explicit efectuată ca o fază de pre-procesare

înainte de executarea algoritmilor de învățare automată.

Cele patru tehnici utilizate sunt PG, maşinile cu suport vectorial, perceptroni multistrat şi

pădurile aleatoare, și sunt aplicate problemei utilizării semnăturii „gena 70” pentru a prezice rata

de supravieţuire a pacienţilor cu cancer de sân incluși în setul de date NKI. Acesta este considerat

unul dintre seturile de date standard, semnificative în domeniu. În acest studiu preliminar se

folosesc toate metodele într-o versiune originală pentru a obține o primă evaluare, cât mai

imparțial posibil, a performanțelor metodelor.

3.3 Referințe din cercetări anterioareMulte metode de învăţare automată au fost deja aplicate pentru analiza datelor

microarray, cum ar fi cei mai apropiaţi K-vecini, clusterizare ierarhică, auto-organizarea hărților,

maşini cu suport vectorial sau reţele Bayes. Mai mult, în ultimii ani, algoritmii evolutivi (AE) au

fost folosiţi pentru rezolvarea atât a problemelor de selecție a caracteristicilor cât și a analizei

datelor expresie. Algoritmii genetici (AG) au fost folosiţi pentru a construi selecţii în care fiecare

genă alelă a reprezentării corespunde unei singure gene și starea ei denotă dacă gena este

selectată sau nu. PG pe de altă parte, a fost demonstrată ca fiind potrivită la recunoașterea

structurilor din seturi mari de date.

PG a fost aplicată pe date microarray pentru a genera programe care indică cu precizie

starea de sănătate a ţesutului, sau clasifică diferite tipuri de ţesuturi. Un avantaj intrinsec al PG

este că aceasta selectează automat un număr mic de gene caracteristici în timpul evoluției.

Evoluția clasificatorilor din populația inițială, integrează perfect procesul de selecție al genelor și

construcția clasificatorului. De fapt, PG a fost folosită la date de profilare a expresiei cancerului

pentru a selecta genele caracteristice cu potenţial informativ, pentru a construi clasificatoare

moleculare prin integrarea matematică a acestor gene şi pentru a clasifica probe tumorale. PG a

fost catalogată ca o abordare promiţătoare pentru a descoperi clasificatori comprehensibili, bazaţi

pe reguli proveniţi din seturi de date medicale precum și datele de profilare expresiei genelor.

3.4 Capacitatea predictivă a învăţării automate

Pentru analiză s-a folosit setul de date a cancerului la sân NKI, oferind expresia genelor şi

datele de supravieţuire pentru 295 de pacienţi cu carcinom mamar consecutiv. Am considerat

numai datele expresive pentru genele incluse în semnătura"gena 70".

Datele conţinând atât expresiile de supravieţuire cât şi cele genice au fost transformate în

format binar. Pentru datele de supraviețuire, se defineşte ca rezultat starea de supraviețuire a

pacienților la momentul t_final = 10,3 ani. Prin alegerea acestui obiectiv special, am echilibrat

numărul de pacienți morți și vii: din 148 de pacienți pentru care t_final este cunoscut, 74 au murit

și 74 au fost în viaţă. Expresia de date binare a fost obținută prin înlocuirea tuturor modificărilor

logaritmice pozitive în setul de date original cu 1 și toate cele negative incluzând cele lipsă cu 0.

Setul de date definit este o matrice H = [H (i, j)] a valorilor binare compuse din 148 de

rânduri (instanţe) și 71 de coloane (caracteristici), unde fiecare linie „i” reprezintă semnătura

genică a unui pacient a cărui țintă binară (0 = a supraviețuit după t_final ani, 1 = mort înainte de

t_final ani) a fost plasată la poziția H (I, 71). În acest fel, ultima coloană a matricii H reprezintă

toate valorile țintă cunoscute. Scopul este de a genera o potrivire pentru F astfel încât F (H (i, 1),

H (i, 2),..., H (i, 70)) = H (i, 71) pentru fiecare linie „i” în setul de date.

În mod cert se doreşte ca F să aibă o capacitate de generalizare bună, de exemplu, să

poată evalua valoarea țintă pentru pacienții noi, care nu a fost utilizată în faza de antrenament.

Din acest motiv, se folosesc o serie de tehnici de învăţare automată, cum s-a precizat anterior.

Pentru a compara puterea de predicţie a metodelor de calcul, se efectuează 50 de alegeri

independente din setul de antrenament şi testare, cel de antrenament incluzând 70% dintre

pacienţi, iar testarea restul de 30%. Diferitele metode de predicție rulează pe aceste seturi de date,

astfel încât alegerea seturilor de antrenament și testare a fost aceeași pentru toate metodele, la

fiecare execuţie.

Tabelul 1 sintetizează rezultatele returnate de fiecare metodă de învățare automată pe 50

de rulări. Prima linie indică diferitele metode, cea de a doua linie indică cea mai bună (de

exemplu, cea mai mică) valoare a instanţelor clasificate incorect obținute pe setul de testare pe

mai mult de 50 de rulări, iar a treia linie raportează performanțele medii pentru fiecare grup pe 50

de rulări pe setul de test, împreună cu eroarea standard corespunzătoare mediei (SEM).

Comparație experimentală între numărul instanţelor clasificate incorect găsite pe setul de

testare stabilită prin diferite metode de învățare automată

PG SVM-K1 SVM-K2 SVM-K3 PM PA

Cel mai bun 10 13 14 15 10 12

media 16.40 (0.30) 18.32 (0.37) 16.76 (0.18) 17.62 (0.17) 18.08 (0.39) 17.60 (0.35)

Tabelul 1

Fiecare metodă a fost rulată independent de 50 de ori folosind de fiecare dată un set diferit de

antrenament din setul de validare.

Programare Genetică –PG, Maşini cu Suport Vectorial – SVM cu diferiţi exponenţi pentru

kernelul polinomial 1.0(SVM-K1), 2.0 (SVM-K2), and 3.0 (SVM-K3), Perceptronii

Multistrat(PM) și Păduri Aleatoare (PA).

Soluțiile găsite de PG folosesc de obicei un număr destul de mic de caracteristici. De fapt,

soluțiile din cele 50 de rulări ale PG sunt funcții ale unui număr de terminal care variază de 1 la

23, cu o valoare medie de 4, cu prima și a treia, cuartile de 2 respectiv 7. Câteva dintre aceste

caracteristici tind să se repete în mai multe soluții, cum se poate vedea în tabelul 2, unde gena

simbol, numele genei corespunzatoare fiecărei caracteristici, împreună cu numărul de soluții

unde caracteristica apare, sunt prezentate.

Top 10 cele mai întâlnite caracateristici apărute în soluțiile date de PGID de acces Numele geneiDescrierea genei Soluții

NM_003981 PRC1 regulator de proteine cytokinesis 1 48

NM_002916 RFC4 factor de replicare C (activator 1) 4, 37 kDa 23

AI992158 - - 16

AI554061 - - 10

NM_006101 NDC80NDC80 homolog, kinetochore – componenta complexa (S.

cerevisiae)9

NM_015984 UCHL5 ubiquitin carboxyl-terminal hydrolase L5 7

NM_020188 C16orf61 cromozomul 16 - citire deschisă, cadrul 61 6

NM_016448 DTL denticleless homolog (Drosophila) 6

NM_014791 MELK leucină maternă embrionară zipper kinase 6

NM_004702 - - 6

Tabelul 3

3.5 Rolul selecției caracteristicilor

Pentru a determina în ce măsură selecția caracteristicilor este responsabilă pentru

performanţa bună a PG, s-au identificat 10 caracteristici selectate de PG de cele mai multe ori,

din cele 70 inițiale și se rulează iar PG și MSV cu kernel pătratic, folosind doar aceste

caracteristici. Performanța ambelor metode s-a îmbunătăţit semnificativ: pentru PG, numărul de

caracteristici identificate incorect a scăzut de la 16,40 (eroarea medie standard 0,30) la 12,86

(0,40); pentru MSV a pornit de la 16.76 (0.18) la 14,96 (0,41). Folosind acest tur preliminar de

selecție a caracteristicilor de performanță a PG, se observă detaşat că performanţa PG e mai bună

decât cea a MSV şi a metodei originale de notare.

Aceste rezultate sugerează în primul rând că selecția caracteristicilor realizată de PG are

valoare intrinsecă, nu neapărat legată de utilizarea arborilor de sintaxă, deoarece MSV pot profita

de selecția caracteristicilor efectuată de PG pentru a-şi îmbunătăți propria performanța. În al

doilea rând, o utilizare recursivă a PG, în care o primă rulare este folosită pentru a selecta cele

mai bune caracteristici pentru a fi utilizate într-o a doua rulare, ar putea fi o modalitate

promițătoare pentru optimizarea metodei.

3.6 Performanța asupra seturilor de date neechilibrate

Pentru a verifica dacă performanța PG este legată de alegerea unui set de date echilibrate,

analiza s-a efectuat folosind diferite secţiuni de timp (de 5 și 7,5 ani) și s-a comparat performanța

PG cu MSV folosind kernelul polinomial de gradul 2, fiind cea mai bună metodă sortată după

performanţe ce urmează PG în setul de date echilibrate. Rezultatele sunt prezentate în tabelul 3.

La 7,5 ani, nu este încă nicio diferență semnificativă între performanțele celor două metode. Cu

toate acestea, la 5 ani PG lucrează semnificativ mai bine decât MSV. Concluzionând, echilibrarea

setului de date nu este crucială pentru a obține o performanță bună la PG. [20]

Comparație experimentală între numărul de instanțe clasificate incorect găsite pe setul de

date de PG și Mașinile cu Suport Vectorial cu exponent 2 pe seturi neechilibrate

5 ani 7,5 ani

PG MSV-K2 PG MSV-K2

Cel mai bun 9 10 12 13

Eroarea standard de medie 15.04 (0.41) 17.84 (0.42) 21.18 (0.49) 20.7 (0.46)

Seturile de date sunt definite de statutul de supraviețuire la perioade finite de 5 si 7,5 ani.

Tabelul 4

Rezultatele au arătat că în timp ce toţi algoritmii de învăţare automată folosiţi în

experiment au putere de predicţie în clasificarea pacienţilor cu cancer de sân în clase de risc, PG

surclasează în mod clar toate celelalte metode cu excepția MSV cu kernel polinomial de gradul 2,

a cărui performanță este apropiată de PG. Totuşi, nu există nicio modalitate de a face o astfel de

comparație într-un mod complet imparțial, așa cum s-ar putea argumenta că nivelurile de

optimizare sunt inegale. Pentru a reduce la minimum posibila subiectivitate, s-a ales

implementarea implicită a tuturor metodelor.

3.7 Mașini cu suport vectorial în clasificarea cancerului la sân

Maşinile cu suport vectorial sunt o categorie de învăţare automată folosită ca un

instrument în clasificarea datelor datorită abilităţii de a generaliza ce a funcţionat cu succes în

multe aplicaţii. Calitatea de bază a maşinilor cu suport vectorial este că minimizează

generalizarea erorii prin maximizarea limitelor între setul de date şi hiperplan. Maşinile au un

avantaj în plus deoarece automatizarea modelului de selecţie permite obţinerea dinamică a

numerelor optime şi a locaţiilor în timpul antrenamentului.

Performanţa algoritmilor depinde în cea mai mare parte de nucleu [13][14]. Mostrele de

date de antrenament împreună cu hiperplanurile de lângă granița clasei sunt numite vectori, iar

marginea reprezintă distanţa între vectorii suport şi graniţa clasei hiperplanului. Maşinile sunt

bazate pe conceptul de plan de decizie care defineşte graniţa de decizie. Un plan este cel care

separă între calităţile obiectelor având diferite apartenenţe la clasă. Maşinile cu suport vectorial

sunt o tehnică folositoare în clasificarea datelor. O activitate de clasificare implică de obicei

datele de antrenament şi testare ce conţin instanţe ale datelor. Fiecare instanţă în setul de

antrenament conţine o valoare care trebuie atinsă şi câteva atribute.

Unul din experimentele care a încercat să diagnosticheze cancerul de sân folosind

maşinile cu suport vectorial a avut următoarea structură [15]. Detectarea tumorilor în mamografie

este divizată în trei părţi. Primul pas implică o procedură de intensificare, tehnicile de conturare a

imaginilor sunt folosită să îmbunătăţească aspectul vizual, să crească gradul de zgomot şi să facă

anumite caracteristici mai uşor de vizualizat prin modificarea culorilor şi a intensităţilor. Stagiul

doi care foloseşte valorile imaginilor prelucrate, segmentează zona cu tumoarea şi extrage

caracateristicile din imaginea divizată. Al treilea şi ultimul pas presupune clasificarea folosind

maşinile cu suport vectorial.

Îmbunătăţirea imaginii poate fi definită ca o conversie a calităţii imaginii la un nivel mai

comprehensibil. (a) Procedura de îmbunătăţire a mamografiilor se efectuează cu un filtru fin

Gaussian bazat pe deviația standard. (b) Se execută o mască morfologică de filtrare pe scală de

gri folosind elementul de structurare. Stratul de vârf este folosit să corecteze lumina neuniformă

când fundalul este negru. (c) Masca de vârf a rezultatului este descompusă în două scale şi apoi

imaginea se reconstruieşte.

Figura 1 (a) mamografia originală (b) imaginea filtrată (c) nivelul am doilea de reconstrucţie a

mamografiei (d) rezultatul tumorii segmentat

Mamografia corectată este convertită în imagini binare prin segmentare la diferite valori.

Părţile fragmentate sunt filtrate din nou cu filtru Gaussian pentru a elimina zgomotul. Metoda de

segmentare a imaginii este un pas în optimizarea detecţiei de cancer la sân, împărţind

mamografia în regiuni constituente.

Această metodă a fost testată pe 75 de imagini, având o precizie de 88.75%. Unul din

modurile de a îmbunătăţi performanţa maşinilor cu suport vectorial este folosind metoda de

eliminare recursivă a atributelor propusă de Guyon [16] pentru selecţia genelor sau validarea

încrucişată pentru a extrage atribute optime.

Eliminarea recursivă este o abordare de selecţie înapoi care selectează genele în

conformitate cu influenţa lor (greutatea) într-o maşină cu suport vectorial. Prima dată calculează

criteriul de calitate în funcţie de greutatea maşinii. Apoi elimină atributele cu valoarea cea mai

mică concluzionând cu un proces de repetiţie până când o acurateţe a clasificării mai bună este

îndeplinită. Eliminarea recursivă este folosită să găsească relaţiile discriminatorii într-un set de

date de test şi în datele exprimate sub formă de gene create din microarray-uri de tumori în

opoziţie cu ţesuturile normale.

Totuşi, metoda este sensibilă la perturbări fine în setul de date de antrenament.

Caracteristicile pe care le extrage din set pot să nu aibă performanţă bună în predicţie într-un set

de date independent. Probabil aceasta este cauzată de învăţarea pe de rost care apare când

numărul de caracteristici este mare şi numărul de şabloane de antrenament este mic în comparaţie

sau apar regularităţi în datele de antrenament care nu apar în datele de test.

Validarea încrucişată este folosită cu scopul de a evita învăţarea pe de rost şi a câştiga cea

mai bună acurateţe a prezicerii pentru setul de antrenament. Comparând performanţa clasificării

şi a predicţiei în validarea încrucișată cu cea a eliminării recursive şi a maşinilor cu suport

vectorial rezultă:

validarea încrucişată este potrivită pentru a analiza datele cu zgomot;

are performanţă mai bună decât eliminarea recursivă în robusteţe, zgomot şi abilitatea de

la recupera atribute informative;

poate îmbunătăţi performanţa predicţiei în setul de test de la 0,5826 până la 0,7879.

Următoarele carcteristici au fost implicate în evaluare: senzitivitatea – proporţia actuală de

perechi pozitive care sunt corect identificate, specificitatea - proporţia actuală de perechi negative

care sunt corect identificate, precizia – probabilitatea de precizie pozitivă corectă, acurateţea –

proporţia de perechi prezise corect.

Senzitivitate =

Specificitate =

Precizie =

Acuratețe =

unde AP = adevãrat pozitiv, AN = adevãrat negativ, FN = fals negativ, FP = fals pozitiv

Compararea performanței Mașinilor cu suport vectorial, Eliminarea recursivă și

Validarea încrucișată

Measuratori

Mașini cu suport

vectorial Eliminarea recursivă Validarea încrucișată

#gene 42 18 15

Seturi

De

antrenament

De

test

De

antrenament

De

test

De

antrenament De test

Precizie 97.0% 58.8% 100% 71.4% 100% 74.29%

Acuratețe 98.4% 56.9% 100% 70.8% 100% 73.85%

Senzitivitate 100.0% 58.8% 100% 73.5% 100% 76.47%

Specificitate 96.9% 54.8% 100% 67.7% 100% 70.97%

3.8 Alte modalități de diagnosticare a cancerului

Data mining este un pas esențial în procesul de cunoaștere. Diferite tehnici de data

mining, rețele neuronale și reguli de asociere, au fost folosite pentru detectarea anomaliilor și

clasificare. Din rezultatele experimentale este clar că cele două abordări s-au comportat bine,

obținând o acuratețe de clasificare ajungând la peste 70% la sută pentru ambele tehnici.

Experimentele efectuate, demonstrează utilizarea și eficiența de reguli de asociere în clasificarea

imaginilor. Imaginile medicale reale folosite în experimente au fost luate de la Societatea de

Analiză a Mamografiilor. Au fost 208 imagini normale, 63 benigne și 51 maligne care sunt

considerate anormale. Cazurile anormale sunt în continuare împărțite în șase categorii: micro-

calcifiere, mase circumscrise, mase speculate, masele bolnav definite, distorsiuni arhitecturale şi

asimetrie.

Mamografiile sunt imagini dificil de interpretat, şi o fază de preprocesare a imaginilor

este necesară pentru a îmbunătăți calitatea imaginilor și de a face extracție în fază caracteristică

mai stabilă. Sunt necesare două tehnici de prelucrare a imaginii: o operațiune de decupare și una

de îmbunătățire a imaginii au fost efectuate înainte de faza de extracție. După recoltare și

îmbunătățirea a imaginilor, care reprezintă, practic faza de curăţare de date, funcțiile relevante

pentru clasificare sunt extrase din imaginile prelucrate.

Caracteristicile existente sunt:

Tipul de țesut (dens, gras și gras glandular).

Poziția sânului: fie la stânga sau la dreapta.

Caracteristicile de mai sus extrase sunt calculate pe dimensiuni mici ale imaginii

originale. Aceste patru regiuni sunt din nou despicate în alte patru părți să se obțină extracția mai

precisă a caracteristicilor și pentru investigații suplimentare de localizare. Pentru șaisprezece sub-

părți ale imaginii originale s-au calculat parametrii statistici.

3.8.1 Rețele neuronale artificiale

Arhitectura rețelei neuronale este formată din trei straturi: un strat de intrare, unul ascuns

și un strat de ieșire. Rețeaua neuronală este antrenată cu baza de date de cancer de sân cu ajutorul

modelului de propagare înainte și algoritmul de învățare numit propagarea înapoi cu impuls și

rata de învăţare variabilă. Performanța rețelei trebuie evaluată. Rezultatul experimental arată că,

prin aplicarea abordării în paralel în modelul de rețele neuronale se produc rezultate eficiente.

Strategiile de paralelizare ale reţelelor neuronale sunt în mod inerent paralele în natură, această

tehnică fiind considerată să implementeze paralelismul pentru calcularea puterii la fiecare nod în

diferite straturi ale rețelei. Fiecare neuron funcționează independent, prelucrând intrările ce le

primește, ajustând ponderi şi propagând rezultatul calculat astfel că un neuron reprezintă un nivel

normal de paralelizare pentru rețelele neuronale. Fiecare neuron este tratat ca un proces paralel.

Având în vedere caracteristicile importante ale rețelelor neuronale și avantajele sale

pentru punerea în aplicare a problemei de clasificare, tehnica reţelelor este potrivită pentru

clasificarea datelor legate de domeniul medical. În acest experiment este considert un set de date

legat de cancerul de sân. Baza de date a fost obţinută de la spitalul Universităţii din Wisconsin,

doctor William H. Wolberg

Descrierea bazei de date:

Numărul de cazuri: 699

Număr de atribute: 10 plus atributul de clasă

Distribuție clasă: benigne: 458 (65,5%), malign: 241 (34,5%)

Precizie rețea neuronală artificială: 86,5%

3.8.2 Clasificatorul Naive Bayes

Abdelghani Bellaachia si Erhan Guven au efectuat o analiză a predicție a ratei de

supravieţuire a pacienţilor cu cancer de sân, utilizând tehnici de data mining, Naive Bayes,

propagare înapoi în reţele neuronale, și algoritmii de arbori de decizie C4.5, folosind kitul Weka.

Weka este o colecție de instrumente pentru diverse tehnici de data mining, cum ar fi de

clasificare, regresie, clusterizare, reguli de asociere, și vizualizare. Setul de instrumente este

dezvoltat în Java și este un software open source. O versiune mai nouă a bazei de date REES (din

perioada 1973-2002, cu 482,052 de înregistrări) a fost folosită cu două câmpuri suplimentare

Recode Starea Vital (VSR) și cauza morții. Studiul arată că rezultatele preliminare sunt

promiţătoare pentru aplicarea metodelor data mining în problema predicției supraviețuirii în

conformitate cu bazele de date medicale. Performanțele de predicție obținute sunt comparabile cu

tehnicile existente. Cu toate acestea, algoritm C4.5 are o performanță mult mai bună decât alte

tehnici.

Acuratețe:

Naive Bayes: 84.5%

C4.5 : 86.7%

3.8.3 Tehnologia microarrayInvenţia tehnologiei microarray cu posibilitatea de a examina mii de gene simultan a

schimbat modelul de prognoză a cancerului pentru o nouă eră postgenomică. Spre deosebire de

modelele de prognoză clinice, profilarea expresiei genelor oferă noi modalități de a înțelege

procesul celular legat de cancer, sporind astfel precizia de clasificare. Cu toate acestea, datele

copleșitoare generate de tehnologia microarray necesită o analiză corectă a informaţiilor. Analiza

datelor microarray constă în principal din două părți: selecția caracteristicilor și clasificare.

Microarray oferă o metodă eficientă de colectare a datelor, care pot fi folosite pentru a determina

modelul de exprimare a mii de gene. MRNA-ul (RNA mesager - este un singur fir al ADN-ului,

care a fost copiat) din diferite țesuturi în condiții normale și în caz de boală, ar putea dezvălui

care gene și ce condiții de mediu poate conduce la boala. Multe studii au fost efectuate pentru a

aborda aceste probleme.

Tendințele de clasificare s-au schimbat de la utilizarea unui singur clasificator la a

asambla mai mulţi clasificatori în unul singur pentru a examina diferenţa în expresie a genelor.

Mai mult decât atât, se remarcă, de asemenea, dependența mare față de tehnicile de selecție

uni-variate bazate pe filtrarea caracteristicilor în comparație cu metodele de înveliș și cele

încorporate. În prezent, modelele de prognoză arată o direcție tot mai imperativă față de utilizarea

datelor integrate, cum ar fi microaparat și clinice, sau date genomice şi cele privind studiul

proteinelor, în loc de examinarea separată a reapariţiei cancerului.

Microarray-ul populat este apoi stimulat de un laser şi fiecare punct fluorescent în

consecinţă, din microarray este măsurat. Dacă nici probele nici monstrele de referință nu

hibridizează cu genele reperate pe diapozitiv, locul va apărea cu culoarea neagră. Cu toate

acestea, dacă hibridizarea este predominantă cu proba, locul se va colora în roşu. În schimb, dacă

hibridizarea este în primul rând între referință și ADN-ul aplicat la diapozitiv, locul se va colora

verde. Spotul poate, de asemenea apărea incandescent galben, atunci când ADN-ul din probe şi

monstre de referință hibridizează egal într-un loc dat, indicând faptul că ei au același număr de

nucleotide complementare, în acel loc.

3.8.4 CAD – Detectarea Asistată de CalculatorProgresele tehnologice recente au permis dezvoltarea unor sisteme de detectare asistată de

calculator (CAD) care pot oferi o detectare automată a structurilor patologice și să acționeze ca

un al doilea cititor capabil să asiste radiologii în clarificarea diagnosticului. Sistemul pentru

caracterizarea leziunilor masive se bazează pe un algoritm de trei etape: mai întâi, o tehnică de

segmentare extrage leziunea masivă din imagine, apoi, mai multe caracteristici bazate pe

mărimea, forma și textura leziunii sunt calculate.

Sistemele CAD vor juca un rol tot mai important în spitale fiindcă sunt un al doilea

cititor. Studiile clinice au arătat că sistemele pot îmbunătăţi precizia de detectare a cancerului de

sân. Studiile preclinice au demonstrat potențialul acestei tehnici în a îmbunătăți clasificarea

leziunilor maligne și benigne. Un număr crescut de sisteme CAD sunt dezvoltate pentru diverse

metode imagistice de sân.

Leziunile masive sunt extrem de variabile ca dimensiune, formă și densitate, ele pot

prezenta un contrast foarte slab în imagine sau pot fi foarte dependente de țesutul parenchimal

înconjurător. Din aceste motive segmentarea masivă a leziunilor din ţesutul neuniform normal al

sânului este considerată o sarcină trivial și eforturile de mult au trecut deja prin această problemă.

O leziune masivă este identificată automat într-o regiune dreptunghiulară de interes (ROI) aleasă

interactiv de către radiolog. Regiunea conține leziuni, dar şi o parte considerabilă de țesut

normal.

În scopul de a reduce diagnosticele fals-negative, leziunile cu mai mult de 2% șanse de a

fi maligne vor fi recomandate pentru biopsie [18]. Ca urmare, numai 15-30% din pacienții ce au

efectuat biopsie se constată că au malignitate. Biopsiile inutile nu numai cauzează anxietate

pacientului și morbiditate, dar cresc costurile de îngrijire a sănătăţii. Prin urmare, este important

să se îmbunătățească precizia de interpretare a leziunilor mamografice, crescând astfel valoarea

predictivă pozitivă a mamografiilor.

CAD este un domeniu activ de cercetare şi dezvoltare în imagistica medicală şi radiologie

de diagnostic. Recent, există un număr crescut de aplicații CAD. Până în prezent cel mai mare

număr de sisteme CAD au fost dezvoltate pentru mamografie de screening. Cu toate acestea, un

număr tot mai mare de imagini de sân RMN sunt evaluate. Deși cele mai multe aplicaţii clinice

sunt dedicate pentru depistarea cancerului de sân, în prezent, se poate preconiza caracterizarea

CAD ca o componentă importantă a sistemelor CAD de ultimă generație.

3.8.5 Regresia logisticăScopul a fost de a crea un model de estimare a riscului de cancer de sân bazat pe

descriptorii de la Baza Națională de date Mamografice utilizând regresia logistică care poate

ajuta în luarea deciziilor pentru depistarea precoce a cancerului de sân.

Atunci când este testată pe 100 de femei, noua tehnică s-a dovedit a fi în procent de

aproape 90 % corectă la estimarea gradului de răspândire a bolii și speranţa de viaţă pentru

următorii cinci ani. Abordarea, dezvoltată de o echipă condusă de Raouf Naguib de la

Universitatea din Coventry și Gajanan Sherbet de la Universitatea din Newcastle, se bazează pe o

metodă analitică existentă numită citometria imaginilor. Aceasta analizează la microscop

imaginile tumorii şi foloseşte o aplicaţie pentru a executa o tehnică standard de statistică numită

regresie logistică pentru a prezice dacă pacientul va supraviețui pentru o anumită perioadă

precizată. Prognoza se bazează pe factori cum ar fi vârsta femeii și zonele cu anomalii din tumori

cum ar fi rata de diviziune celulară și forma nucleelor celulelor.

Naguib şi Sherbet tratează aceasta comparativ cu tehnica lor, care utilizează un program

de rețele neuronale și logica fuzzy, un instrument de luare a deciziilor utilizat în mod obișnuit de

către cercetătorii în inteligenţă când analizează date imprecise.

Un alt avantaj a fost că fiecare dintre cele trei abordări au relevat un set diferit de factori

ca fiind cel mai important pentru a face o prezicere. Acest lucru sugerează că bazându-se pe o

singură tehnică statistică ar putea pierde corelații vitale, spune Naguib. Dar Peter Saseini, un

cercetător senior, nu este convins de avantajele noii tehnici. El spune că ar trebui să fie testate pe

grupuri mai mari de pacienţi înainte că valoarea sa reală să fie stabilită.

Naguib recunoaște că studiile au fost relativ mici, și spune că următorul pas va fi să se

aloce un număr mai mare de pacienţi. El vrea, de asemenea, să includă tratamentele pe care

pacienţii le primesc alături de alți factori care vor fi luaţi în calcul de aplicaţie. Acest lucru ar

îmbunătăți și mai mult fiabilitatea tehnicii.

3.9 Comparație între metode

Reţelele neuronale artificiale sunt o paradigmă de prelucrare a informațiilor, care este

inspirată din modul de funcţionare a creierului. Elementul cheie al acestei paradigme este

interconectarea elementelor de prelucrare numite neuroni care lucrează la unison pentru a rezolva

probleme specifice. Mecanismul de învățare în sistemul reţelelor implică ajustări ale conexiunilor

sinaptice care există între neuroni. Mai mult decât atât, metodologia reţelelor neuronale artificiale

reprezintă o alternativă utilă la tehnicile de modelare clasice, când se aplică pe seturi de date

variabile prezentând relații neliniare.

Prin urmare, reţelele sunt folosite predominant în implementarea diferitelor modele de

prognoză a cancerului pentru a aborda problemele referitoare la factori de prognostic corelaţi și

manipularea cenzurată a datelor. Deşi tehnica a dominat multe modele de prognoză ea relevă în

principal din două probleme: selecția de arhitectură şi valoare a parametrului implicat și

înțelegerea regulilor care stau la bază devine imposibilă deoarece este un sistem de procesare tip

„cutia neagră”.

Spre deosebire de reţele, arborele de decizie (DT) reprezintă rezultatele sub forma unui

set de reguli simbolice. În mod formal un arbore este structurat într-un graf sau o diagramă de

noduri, care vor fi utilizate pentru a determina scopul final. În cazul prezicerii cancerului,

obiectivele celor mai mulţi cercetători pot fi clasificate în două categorii distincte.

Deși arborele de decizie este ușor de interpretat și poate gestiona diferite tipuri de date,

inclusiv date numerice si nominale, valorile lipsă pentru un atribut pot duce la ambiguitate în

alegerea ramurii corecte. Mai mult decât atât, aceasta poate genera prea multe reguli, ceea ce îl

face greu de înțeles.

Masinile cu suport vectorial sunt un alt tip de tehică de clasificare. Conceptul de bază în

algoritmul mașinilor este de a crea un hiperplan care separă datele în două clase încadrate in

limita maximă. Ca si rețelele neuronale, masinile cu suport vectorial pot fi utilizate pentru a

efectua clasificări neliniare folosind nucleu neliniar.Tehnica este aproape necunoscută în

comparație cu rețelele neuronale și arborele de decizie în domeniul de prezicere a cancerului.

Alte tehnici precum „cel mai apropiat al k-lea vecin” sunt, de asemenea, foarte rar aplicate în

acest domeniu.

CONCLUZII

BIBLIOGRAFIE

1 Mehryar MOHRI, Afshin ROSTAMIZADEH, Ameet TALWAKAR– Foundations of

Machine Learning, The MIT Press, 2012

2 S. GEMAN, E. BIENENSTOCK, and R. DOURSAT– Neural Networks and the

bias/variance dilemma, Neural Computation 4, 1-58, 1992

3] G. JAMES – Variance and Bias for General Loss Functions, Machine Learning 51, 115-135,

2003

4] A freely available MATLAB implementation of the graph-based semi-supervised algorithms

Laplacian support vector machines and Laplacian regularized least squares.

5] N. RUBENS, D. KAPLAN, M. SUGIYAMA – Reccomender Systems Handbook: Active

Learning in Recommender Systems, Springer, 2011

6] SETTLES, BURR –Active Learning Literature Survey, University of Wisconsin-Madison,

2009

7] Tye-Yan LIU –Learning to Rank for Information Retrieval, Vol. 3, 225-331, 2009

8 B.E. BOSER, I.M. GUYON, V.N VAPNIK – A training algorithm for optimal margin

classifiers, ACM Press, 1992

[9] B. SCHOLKOPF, K. TSUDA, J.P. VERT - Kernel Methods in Computational Biology, MIT

Press, 2004

[10] H. WILLIAM, A. SAUL, J.P. VERT – Section 16.5. Support Vector Machines. Numerical

Recipes: The Art of Scientific Computing (3rd ed.), Cambridge University Press, 2007

11 G.L. TAKKAB, V.P. KAMBOJ – Effect of Altered Hormonal States on Histo-Chemical

Distribution of Polysaccharides, Lucknow: Central Drug Research Institute, 2003

12 C. CORTES, V.N. VAPNIK – Support Vector Networks, Machine Learning Boston, vol.

3, Pg. 273-297, 1995

13 G. JONES, T. POQQIO – Regularization theory and neural network architectures,

Neural computation Cambridge, vol.7, pg.217-269,, 1995

14 A.J. SMOLA, B. SCHOLKOPF, K.R. MULLER – The connection between

regularization operators and support vector kernels, Neural Networks New York, vol.11, pg

637-649, 1998

15 Y. IREANUS et al – International Journal on Computer Science and Engineering,

Vol.1(3), 127-130, 2009

16 I. GUYON, J. WESTON, J. BARNHILL, V. VAPNIK– Gene Selection for Cancer

Classification using Support Vector Machines, Mach Learn, 2002

17 Recursive SVM biomarker selection for early detection of breast cancer in peripheral

blood BMC Medical Genomics , 2013

18 Sickles EA. Periodic mammographic follow-up of probably benign lesions: results in

3184 consecutive cases. Radiology, 1991

19 L.J. VAN’T VEER, H. DAI– Gene expression profiling predicts clinical outcome of

breast cancer, Nature, 2002

20 L.D. MILLER, J. SMEDS, J. GEORGE– An expression signature for p53 status in

human breast cancer predicts mutation status, transcriptional effects, and patient survival ,

Proc Natl Acad Sci USA, 2005