ALGORITMII EVOLUTIVI IN EXPLORAREA SI EXPLOATAREA BAZELOR DE DATE MEDICALE

ABSTRACT

Obiectiv

Lucrarea de fata isi propune sa prezinte principiile de baza ale algoritmilor evolutivi precum si aplicarea acestora intr-un caz concret pentru diagnosticul asistat de calculator. Obiectivul studiului este de a veni in ajutorul medicului in practica sa cotidiana oferindu-i un mijloc simplu de a accede la informatiile continute intr-o baza de date cu imagini deja interpretate de catre alti medici.

Material si metoda

Vom prezenta un algoritm de cautare a imaginilor in functie de continutul lor intr-o baza de date medicale in vederea stabilirii diagnosticului in retinopatia diabetica. Pentru caracterizarea continutului se vor utiliza doua abordari : prima globala si generica si cea de a doua locala si specifica leziunilor interesate. Baza de date continand 457 imagini de retinopatie interpretate a fost interogata pntru a evalua performantele algoritmului.

Rezultate

Precizia algoritmului asupra acestei baze de date depaseste 92%. Imaginile noi propuse spre examinare au fost actualizate cu confirmarea sau infirmarea diagnosticului, adaugandu-se astfel bazei de cunostinte si asigurand premizele unei rafinari ulterioare a cautarii.

Concluzii

Imaginea a fost dintotdeauna utilizata in medicina pentru instruire si pentru diagonstic. Retinopatia diabetica este un exemplu de maladie care necesita producerea unui numar mare de imagini medicale pe parcursul examenelor medicale. Algoritmiul evolutiv descris in lucrare se constituie intr-un instrument util si eficient in rezolvarea problemelor medicale de acest gen.

CUVINTE CHEIE: calcul evolutiv, retinopatie diabetica, diagnostic asistat, algoritmi evolutivi, baze de date medicale.

INTRODUCERE

Ín general, orice sarcina abstracta care trebuie îndeplinita, poate fi privita ca fiind rezolvarea unei probleme, care, la rândul ei, poate fi perceputa ca o cautare în spatiul solutiilor potentiale. Deoarece, de obicei, cautam cea mai buna solutie, putem privi acest proces ca fiind unul de optimizare. Pentru spatii mici, metodele clasice exhaustive sunt suficiente; pentru spatii mari, pot fi folosite tehnicile speciale ale inteligentei artificiale. Metodele calculului evolutiv se numara printre aceste tehnici; ele folosesc algoritmi ale caror metode de cautare au ca model câteva fenomene naturale: mostenirea genetica si lupta pentru supravietuire. Cele mai cunoscute tehnici din clasa calculului evolutiv sunt algoritmii genetici, strategiile evolutive, programarea genetica si programarea evolutiva. Exista si alte sisteme hibride care încorporeaza diferite proprietati ale paradigmelor de mai sus; mai mult, structura oricarui algoritm de calcul evolutiv este, în mare masura, aceeasi. Ín ultimii 30 de ani, s-a manifestat un mare interes în rezolvarea problemelor de sistem bazate pe principiile evolutiei si ereditatii. Astfel de sisteme mentin o populatie de solutii potentiale, ele au unele procese de selectie bazate pe fitness individual, si cativa operatori genetici. Un astfel de system este o clasa a evolutiei strategice i.e, algoritmi care imita principiile evolutiei naturale pentru problemele de optimizare de parametru (Rechemberg, Schwefel). Evolutia programarii lui Fogel este o tehnica de cautare intr-un spatiu finit, mic de masini. Tehnologiile de cautare a masinii lui Glover Scatter mentin o populatie de puncte de referinta, generand o stare speciala prin greutatea combinatiilor liniare. Alte tipuri de sisteme evolutionare sunt Holland's Genetic Algorithms. Ín 1990 Koza a propus un astfel de sistem evolutional, genetic programming, pentru a cauta cel mai potrivit program de computer sa rezolve o problema particulara .

MATERIAL SI METODA

Algoritmii Genetici sunt o familie de modele inspirate de teoria evolutiei, sunt programe inteligente capabile sa solutioneze probleme folosind un conceptul al evolutiei speciilor. Acesti algoritmi codifica solutiile posibile ale unor probleme specifice într-o structura de date de tip cromozom si aplica acestor structuri operatori de recombinare, pentru a pastra informatia utila.

Un cromozom este un vector sau un sir de gene. Pozitia unei gene este numita locusul ei. Valorile pe care le poate lua o gena sunt numite alele, sunt multimi finite de numere întregi, intervale de numere reale, sau chiar structuri complexe de date. Alele variaza de la un locus la altul.

Sarcina unui algoritm genetic e sa descopere cromozomi din ce în ce mai buni, pâna la atingerea unei valori a raportului dintre evaluarea asociata unui sir si evaluarea medie a tuturor sirurilor populatiei (fitness) despre care se stie ca este optimala, sau pâna când algoritmul genetic nu mai poate aduce îmbunatatiri.

Implementarea unui algoritm genetic începe cu o populatie de cromozomi (aleasa aleator). Se evalueaza, apoi, aceste structuri si se aloca facilitati reproductive astfel încât acei cromozomi, care reprezinta o solutie mai buna pentru problema tinta, sa aiba mai multe sanse de a se reproduce decât acei cromozomi care sunt solutii mai putin bune. Definirea unei solutii bune se face în raport cu populatia curenta.

Într-un sens mai larg, algoritm genetic este orice model bazat pe ideea de populatie si care foloseste selectie si operatori de recombinare pentru a genera noi puncte într-un spatiu de cautare. Multe modele au fost introduse de cercetatori dintr-o perspectiva experimentala. Cercetatorii sunt orientati spre aplicatii, fiind interesati de algoritmii genetici doar ca mijloace de optimizare.

Ei sunt recomandati pentru aflarea solutiilor neliniare ale unor probleme atunci când nu este posibila modelarea matematica si nici euristica în domeniu.

Adevaratii profesionisti combina adesea cele mai variate tehnologii inteligente în scopul exploatarii avantajelor fiecareia, obtinând asa-numitele sisteme hibride. Sunt posibile combinari de genul

folosirea retelelor neuronale la ajustarea parametrilor în sistemele expert fuzzy,

extragerea cunoasterii din retele neuronale pentru a fi utilizata în sistemele expert,

folosirea algoritmilor genetici la crearea unor retele neuronale mai compacte si mai eficiente,

folosirea unei retele neuronale pentru asistarea functionarii unui algoritm genetic,

folosirea algoritmilor genetici la reglarea parametrilor unui sistem expert fuzzy pentru controlul proceselor,

îmbunatatirea performantei unui sistem expert prin încorporarea rationamentului bazat pe cazuri, etc.

Asemenea cercetari sunt în prezent în mare voga în cele mai specializate laboratoare ale lumii stiintifice.

Cîteva subiecte ale conceptelor de baza

• probleme de optimizare - doar doua componente principale sunt dependente de problema de rezolvat codificarea si functia de evaluare. Scopul este de a fixa parametrii în asa fel încât iesirea sa fie optima.Variabilele desemnând parametrii sunt reprezentati prin siruri binare iar functia de evaluare este parte a descrierii problemei.
• algoritmul genetic canonic - consta în generarea populatiei initiale. Se aplica acestei populatii selectia pentru a obtine o populatie intermediara. Apoi se aplica recombinarea si mutatii pentru a crea o populatie urmatoare (next population). Acest proces de trecere de la populatia curenta la populatia urmatoare reprezinta o generatie în executia unui algoritm genetic.
• selectia hiperplanelor - nu este afectata de extremele locale. Cresterea ratei de selectie a hiperplanelor peste medie nu garanteaza convergenta catre un optim global, ce ar putea fi un vârf relativ izolat.
• teorema schemei - furnizeaza o margine inferioara a schimbarii ratei deselectie pentru un singur hiperplan de la generatia t la generatia t+1.
• alfabetele binare - utilizarea lor va rezulta în urma unor calcule simple. Un alfabet minimal maximizeaza numarul de hiperplane utilizabile pentru codificarea procesarii
• critica teoremei schemei - inexactitatea inegalitatii face ca încercarea de a prezice pe baza teoremei reprezentarea unui anumit hiperplan de-a lungul generatiilor, sa fie fara succes.

Aplicatii ale algoritmilor genetici - Algoritmii genetici reprezinta o metoda cu care pot fi atacate relativ usor probleme dificile de optimizare sau control, cu rezultate bune sau chiar optimale. Când se vorbeste de aplicarea unei idei din software, se refera în general la un prototip care arata cum ar putea fi folosita respectiva idee într-un domeniu practic.

Sisteme Inteligente bazate pe Algoritmi Genetici

Mecanismul specific acestor sisteme este inspirat din functionare sistemelor biologice, în sensul ca încurajeaza solutiile candidat capabile sa rezolve o problema si penalizeaza solutiile fara succes. În felul acesta se obtin, dupa mai multe generatii, solutii foarte bune pentru probleme de optimizare complexe, cu un mare numar de parametri.

Ideea de baza a unui algoritm genetic consta în a începe cu o populatie de solutii, fiecare mai performanta decât precedentele. Fazele ciclului prin care opereaza un asemenea algoritm sunt

1. creearea unei populatii de membri",(solutii candidat la rezolvrea unei probleme),
2. selectia membrilor care s-au adaptat cel mai bine necesitatilor problemei de solutionat,
3. reproducerea (se folosesc operatorii genetici de încrucisare si mutatie,
4. pentru a obtine noi membri),
5. evaluarea gradului în care noii membri corespund mai bine solutionarii problemei,
6. abandonarea populatiei vechi prin înlocuirea ei cu populatia noua din noua generatie.

Structura unui algoritm evolutiv :

Putem prezenta acum structura algoritmului genetic fundamental:

Pasul 1: t ← 0.

Pasul 2: Se initializeaza aleator populatia P(t).

Pasul 3: Se evalueaza cromozomii populatiei P(t).

Pasul 4: Cât timp nu este indeplinita conditia de terminare se executa pasii urmatori:

Pasul 4.1: Se selecteaza cromozomii din P(t) care vor contribui la formarea noii generatii. Fie P1 multimea cromozomilor selectati (P1 reprezinta o populatie intermediara).

Pasul 4.2: Se aplica cromozomilor din P1 operatorii genetici.

Cei mai utilizati sunt operatorii de mutatie si încrucisare.

Un ciclu se repeta pâna când este identificata cea mai buna solutie la problema în cauza. Datorita structurii lor inerent paralele, sisteme inteligente bazate pe algoritmi genetici s-au dovedit performante în problemele de cautare si identificare a structurilor si relatiilor specifice în cadrul bazelor de date si bazelor de cunostinte voluminoase (data mining).

Vom prezenta un algoritm de cautare de imaginii dupa continutul lor intr-o baza de date medicale in vederea stabilirii diagnosticului in retinopatia diabetica.

Interogarea bazei de date se va face prin prezentarea unei imagini rezultate din examinarea pacientului, sistemul oferind ca si raspuns un numar n de imagini - cele mai apropiate ca si continut acompaniate fiind si de interpretarea lor.

Pentru caracterizarea continutului se vor utiliza doua abordari : prima globala si generica si cea de a doua locala si specifica leziunilor interesate. Pentru fiecare abordare imaginea va fi codificata in vederea unei mai bune concentrari a informatiei.

Cea de a doua abordare este specifica leziunilor studiate, in particular pe cele care privesc retinopatia diabetica si se bazeaza pe o invatare si o detectie a acestor leziuni in imagine. Pentru evaluarea sistemului de indexare se va incepe prin regruparea imaginilor in clase . Decupajul bazei de date in clase se va face avand in vedere 2 criteri : stadiul maladiei sau leziunile continute in fiecare imagine (o imagine contine sau nu leziuni de un anumit tip dat). Pentru fiecare imagine i din baza de date vom lansa algoritmul de cautare pentru gasirea numarul k de imagini cele mai asemanatoare lui i (k fiind numita fereastra de cautare). Se vor evalua mai multe elemente: numarul de obiecte apropriate extrase, falsurile pozitive (imagini gasite in timpul cautarii dar care nu corespund criterilor de cautare), falsurile negative (imagini care corespund criterilor de cautare dar negasite in timpul cautarii).

Pentru fiecare clasa C considerata vom prezenta pe rand fiecare imagine apartinand lui C bazei de date pe urma vom calcula precizia si numarul de obiecte apropriate pentru aceasta clasa. Aceste doua marimi trebuie utilizate impreuna pentru a evalua corect performanta algoritmului. In consencinta valorile lor vor depinde de marimea ferestrei de cautare aleasa. Daca este prea mare numarul de obiecte apropriate va fi in mod fals prea mare. Daca ea este prea mica, precizia va avea sanse mult mai mari ca sa fie buna. Pentru a se putea elibera de influenta marimii ferestrei de cautare, vom face ca ea sa varieze si masuram de fiecare data numarul de obiecte apropriate si precizia.

REZULTATE SI DISCUTII

Utilizand un algoritm de cautare de imaginii intr-o baza de date medicale am urmarit stabilirea diagnosticului in cazul retinopatiei diabetice. Obiectivul studiului a fost de a veni in ajutorul medicului in practica sa cotidiana oferindu-i un mijloc simplu de a accede la informatiile continute intr-o baza de date cu imagini deja interpretate de catre alti medici. Interogarea bazei de date s-a facut prin prezentarea unei imagini rezultate din examinarea pacientului, sistemul oferind ca si raspuns un numar n de imagini - cele mai apropiate ca si continut acompaniate fiind si de interpretarea lor. Pentru caracterizarea continutului s-au folosit doua abordari : prima globala si generica si cea de a doua locala si specifica leziunilor interesate. Aceste doua metode fiind complementare, rezultatele oferite de fiecare dintre metode au fost coroborate prin metode de fuziune. Baza de date imagistica care a fost interogata contine 457 de imagini de retinopatie interpretate, ea fiind construita pentru a evalua performantele algoritmului. Precizia algoritmului asupra acestei baze de date depaseste 92 % pentru unele din criteriile de evaluare.

Imaginea a fost dintotdeauna utilizata in medicina pentru instruire si pentru diagonstic. In zilele noastre sistemele de imagistica medicala produc din ce in ce mai multe imagini numerice in toate domeniile medicinei . Aceste imagini au un rol foart important in stabilirea diagnostigului ele fiind direct legate de patologia pacientului cat si in ceea ce priveste istoria sa medicala. Prin urmare cantitatea de imagini produsa fiind realmente atat de mare incat a fost neccesara punerea la punct a unei metode eficace pentru a accede la aceste imagini din bazele de date intr-un timp cat mai scurt posibil. Indexarea automatica a imaginilor pornind de la continutul lor numeric CBIR (Content - Based Image Retrieval) este o solutie promitatoare pentru organizarea eficace a bazelor de date de imagini, fara a fi nevoie o descriere semantica a imaginilor pe care acestea le contin. Am utilizat doua abordari diferite pentru indexarea imaginilor (o reprezentare sintetica a informatiei pe care acestea le contin ) si pentru gasirea imaginilor asemanatoare. Datorita puterii de sinteza a informatiilor pe care o ofera codificare imaginilor aceasta e considerata ca fiind foarte importanta in ambele abordarii. Abordarea globala este independenta de imaginea studiata, si se bazeaza pe distribuirea de coeficienti ai transformarii in imaginea codificata. Cea de a doua este specifica leziunilor studiate, in particular pe cele care privesc retinopatia diabetica si se bazeaza pe o invatare si o detectie a acestor leziuni in imagine. Pentru evaluarea sistemului de indexare am regrupat imaginile in clase.

S-au dedus urmatoarele elemente de performanta :

• Numarul de obiecte apropriate : Raportul intre numarul de obiecte apropriate extrase si numarul total de obiecte apropriate (extrase sau neextrase ) din baza de date.
• Precizia : raportul intre numarul de obiecte apropriate extrase si numarul total de obiecte extrase ( apropriate sau neapropriate) .

Pentru fiecare clasa C considerata s-a prezentat pe rand fiecare imagine apartinand lui C bazei de date pe urma vom calcula precizia si numarul de obiecte apropriate pentru aceasta clasa. Aceste doua marimi au fost utilizate impreuna pentru a evalua corect performanta algoritmului. In consencinta valorile lor depind de marimea ferestrei de cautare aleasa. Daca este prea mare numarul de obiecte apropriate va fi in mod fals prea mare. Daca ea este prea mica, precizia va avea sanse mult mai mari ca sa fie buna. Pentru a se putea elibera de influenta marimii ferestrei de cautare, am facut in asa fel incat ea sa varieze si am masurat de fiecare data numarul de obiecte apropriate si precizia.

CONCLUZII

• Algoritmi genetici sunt algoritmi euristici, adica solutia gasita de ei nu este intotdeauna cea mai buna, dar se afla intr-o vecinatate a solutiei optime. Daca problema este complexa este indicata folosirea unui algoritm genetic.
• Avantajul deosebit al algoritmilor genetici este dat de faptul ca solicita doar valorile functiei obiectiv.
• Algoritmi genetici sunt robustii, gratie numarului mare de puncte pe care le considera la fiecare etapa.
• Datorita puterii de sinteza a informatiilor pe care o ofera,    codificare imaginilor e considerata ca fiind o metoda foarte importanta in siagnosticul asistat de calculator;
• Retinopatia diabetica este o maladie care necesita producerea unui numar mare de imagini pe parcursul examenelor medicale;
• CBIR (Content-Based Image Retrieval) este o solutie optima pentru organizarea eficace a bazelor de date de imagini, fara a fi nevoie o descriere semantica a imaginilor pe care acestea le contin;

BIBLIOGRAFIE

Abraham A. Grosan C. Ramos V. Swarm Intelligence in Data Mining

Abraham A. Grosan C. Ramos V. Stigmergic Optimization, 2006

Dumitrescu D. - Algoritmi genetici si strategii evolutive, Ed. Albastra, 2006

Dumitrescu D. - Principiile Matematice ale Teoriei Clasificarii, Ed. Academiei, 1999

Holland, J. - Adaptation in Natural and artificial Systems, 1975