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