UNIVERSITÀ DEGLI STUDI DI SIENA
FACOLTÀ DI INGEGNERIA
Corso di Laurea in Ingegneria delle Telecomunicazioni
Tecniche di analisi del fondo oculare
mediante caratteristiche cromatiche e SVM
Relatore:
Chiar.mo Prof. Alessandro Mecocci
Correlatori:
Ing. Tommaso Capasso
Tesi di Laurea di:
Gianpiero Lenzi
Matr.: 080201169
Anno Accademico 2004-2005
Indice
Indice
pagina
Introduzione
5
1- L’occhio umano
1.1 - Generalità
9
1.2 - Anatomia descrittiva e topografica
10
1.3 - Vascolarizzazione
19
2- La retina
2.1 - Morfologia
22
2.2 - Struttura e ultrastruttura
24
2.3 - Istofisiologia
32
2.4 - Retinopatie vascolari: retinopatia diabetica
33
3- Tecniche di clustering
3.1 - Introduzione
39
3.2 - Sistemi in logica fuzzy
39
3.2.1 - Introduzione alla logica fuzzy
41
3.2.2 - Concetti di base
42
3.2.3 - Insiemi fuzzy
43
3.2.3.1 - Variabili linguistiche
44
3.2.3.2 - Operazioni su insiemi ordinari ed insiemi fuzzy
45
3.2.4 - Relazioni e composizioni nello stesso spazio prodotto
2
47
Indice
3.2.5 - Relazioni e composizioni in spazi prodotto differenti
48
3.2.6 - Logica fuzzy
49
3.2.7 - Ancora sui Sistemi Logici Fuzzy
51
3.2.7.A - Regole
51
3.2.7.B - Motore inferenziale fuzzy
51
3.2.7.C - Fuzzificazione
53
3.2.7.D - Defuzzificazione
53
3.2.8 - Assegnazione dei valori alle funzioni di appartenenza
54
3.3 - Fuzzy C-Means (FCM)
54
3.4 - Statistical Learning Theory
60
3.4.1 - Introduzione
60
3.4.2 - Un limite a performance di una Pattern Recognition
Machine
60
3.4.3 - La dimensione VC
62
3.4.4 - Punti separati con iperpiani orientati in Rn
63
3.4.5 - La dimensione VC e il numero di parametri
64
3.4.6 - Minimizzare il limite minimizzando h
66
3.4.7 - Minimizzazione del rischio strutturale
67
3.5 - Support Vector Machines Lineari
3.5.1 - Il caso separabile
68
69
3.5.1.1 - Le condizioni di Karush-Kuhn-Tucker
3.5.2 - Il caso non-separabile
3.5.2.1 - Esempi usando delle figure
3.6 - Support Vector Machines non lineari
72
73
76
77
3.6.1 - Condizione di Mercer
80
3.6.2 - Alcuni esempi di SVMs non lineari
81
3.7 - La dimensione VC per le SVM
82
3.8 - Esempio di classificazione SVM: IRIS data
84
4- Il progetto
4.1 - Introduzione
88
3
Indice
4.2 - La funzione Normalizzazione
90
4.3 - Le funzioni per binarizzare l’immagine
92
4.4 - La funzione EliminazioneDiscoOttico
96
4.5 - La funzione EstrazioneFeatures
98
4.6 - Valutazione delle prestazioni
99
4.7 - Ulteriori sviluppi
100
4.8 - Conclusioni
101
APPENDICE A - Stretching dell’istogramma
102
APPENDICE B - Metodo del gradiente per evidenziare i vasi sanguigni
104
Bibliografia ragionata
107
4
Introduzione
Introduzione
INTRODUZIONE AL LAVORO SVOLTO
Le malattie dell’occhio umano collegate al diabete sono le più comuni cause
di cecità nel mondo.
Ad esempio, ci sono approssimativamente sedici milioni di Americani che
hanno il diabete o nella forma giovanile (TIPO I) o nella forma adulta (TIPO
II). Tutti sono a rischio di contrarre malattie minacciose per la vista: queste
malattie sono comuni complicanze del diabete. In Singapore più della metà
dei casi di cecità sono causati da malattie della retina e la retinopatia
diabetica è la malattie che dà il maggior contributo.
Per ora il trattamento più efficace per tali malattie dell’occhio è la precoce
scoperta attraverso screenings regolari. Durante gli screenings si ottengono
immagini a colori della retina usando una fotocamera che riesce a fotografare
il fondo dell’occhio (vedi fig.0.1).
fig.0.1. Immagine tipo di occhio di paziente diabetico con evidenziati gli essudati principali.
5
Introduzione
Comunque, tutte le immagini ottenute dagli screenings hanno bisogno di
un’analisi e di una diagnosi manuale. In altre parole, i medici devono
spendere molto tempo e molta energia per riverificare manualmente tutte le
foto.
Per abbassare il costo di tali screenings, si possono adottare delle tecniche
di elaborazione delle immagini e di pattern recognition che consentano di
individuare automaticamente la presenza di anomalie nelle immagini della
retina ottenute durante gli screenings.
Alcuni autori, come Wang e Hsu [1], Osareh e Mirmehdi [2]-[3]-[4], si sono
concentrati su un particolare segno dell’anormalità: la presenza di essudati
(lesioni della retina) nelle immagini della retina. Uno stadio comunemente
presente nel loro lavoro consiste nel pre-processing delle immagini volto a
migliorare il contenuto informativo da elaborare. Essi applicano una
esaltazione del contrasto locale per distribuire i valori dei pixels intorno alla
media locale. In questa maniera, un pixel p, al centro di una piccola finestra
running w, viene modificato assumendo un nuovo valore pn, secondo la
formula seguente:
Pn = 255*[(f(p)-f(Min))/(f(Max)-f(Min))]
con
f(p)=1/[1+exp((valor_medio-p)/varianza)]
dove Min e Max sono i valori di minima e massima intensità nell'intera
immagine, mentre il valor_medio e la varianza (deviazione standard) sono
calcolati all'interno di ogni finestra.
Questa pre-elaborazione dell’immagine è stata presa in considerazione ed
implementata; tuttavia il risultato non è stato quello sperato, essendo affetto
da molto rumore (vedi fig. 0.2):
6
Introduzione
fig.0.2 Miglioramento del contrasto secondo Wang e Hsu [1], Osareh e Mirmehdi [2]-[3]-[4].
Il secondo passo eseguito da Wang e colleghi consiste nell’eseguire una
classificazione utilizzando l’algoritmo Fuzzy C-Means [1]-[2]-[3]-[4]. Come
vedremo in seguito, nel mio progetto non ho implementato un classificatore
Fuzzy perché è risultato più efficace un classificatore SVM. Tale scelta è
derivata dall’esigenza di evidenziare nettamente (e non in maniera fuzzy),
nella foto del fondo ottico, gli essudati scartando il background.
Il terzo passo eseguito dai predetti studiosi consiste nell’eliminazione del
disco ottico, avendo quest’ultimo le stesse caratteristiche cromatiche degli
essudati. Osareh e colleghi propongono due metodi: template matching
(basato su un’immagine campione della sagoma del disco e sulla sua ricerca
all’interno della foto della retina) e localisation using snakes (l’utente
7
Introduzione
inserisce manualmente una circonferenza vicino al bordo del disco ottico e
questa, via via, si allarga fino a combaciare con lo stesso bordo). Anche in
questo caso, però, i risultati sono stati solo parzialmente soddisfacenti e,
pertanto, ho sviluppato un terzo metodo di cui parlerò nel successivo
capitolo: “Il progetto”.
Infine, Wang e colleghi estraggono un certo numero di caratteristiche
(Feature Extraction) per poter caratterizzare al meglio gli essudati. Nel mio
progetto ho preso spunto dall’insieme di features estratte da Wang e colleghi
aggiungendone altre anche in vista di futuri ulteriori sviluppi del programma.
Lo scopo di questa tesi è quindi quello di fornire un classificatore, basato su
SVM, in grado di riconoscere ed evidenziare gli essudati nelle normali
immagini retiniche. Si impone l’ulteriore vincolo di estrarre le caratteristiche
(features) di tali essudati per meglio conoscere le evoluzioni della malattia.
Questo processo deve essere automatico per velocizzare il lavoro ai medici
ed abbattere i costi.
Il mio elaborato per la tesi inizia con l’individuazione del problema a livello
medico: parlerò dell’occhio come organo, della retina e delle retinopatie
diabetiche.
In seguito tratterò le più comuni tecniche di clustering, Fuzzy C-Means e
SVM, soffermandomi anche sulle teorie fondamentali dalle quali scaturiscono
questi algoritmi (Sistemi Fuzzy e Statistical Learning Theory).
Infine, nel capitolo 4, esporrò l’implementazione, da me realizzata in C++, del
progetto: mi soffermerò sulla struttura del programma, sui vari algoritmi da
me realizzati e sui risultati ottenuti.
8
Capitolo 1 – L’occhio umano
Capitolo 1
L’OCCHIO UMANO
1.1 – Generalità
L’apparato visivo è composto essenzialmente da tre formazioni: il globo, o
bulbo oculare; il nervo ottico; gli annessi oculari.
Il globo oculare è un organo dalla forma sferoidale con diametro
anteroposteriore di 24,1 mm, diametro verticale di 23,5 mm e diametro
trasversale di 23 mm. Ha un peso variabile tra i 7 e i 9 g. Vi si considerano
due poli (uno anteriore, al centro della cornea, e uno posteriore), un asse
anatomico che li congiunge, un equatore (circonferenza perpendicolare
all’asse equatoriale, equidistante tra i due poli) che lo divide in due emisferi.
L’asse anatomico non coincide con l’asse visivo (dal centro della cornea alla
fovea centralis), in quanto la fovea si trova spostata di 4 mm lateralmente e 1
mm inferiormente rispetto al polo posteriore.
Tra asse anatomico e asse visivo si forma un angolo aperto in avanti di circa
5-7°. I due assi anatomici dei due occhi formano tra loro un angolo di circa
10° aperto in avanti, mentre ciascuno di essi forma con l’asse della propria
orbita un angolo di circa 18°, giacché i due assi delle cavità orbitarie sono
nettamente divergenti determinando un angolo di circa 46° aperto
anteriormente.
L’occhio alloggia nella cavità orbitaria protetto dalle palpebre e da altri
annessi oculari. La sua funzione è quella di captare le radiazioni luminose
provenienti dal mondo esterno e di trasformarle in impulsi nervosi da inviare
alla corteccia occipitale, ove si realizza la sensazione visiva. Gli impulsi
lasciano il globo oculare, o meglio la retina sua membrana più interna, per
mezzo di fasci di fibre nervose riunite in un’unica struttura: il nervo ottico.
9
Capitolo 1 – L’occhio umano
Il nervo ottico, rivestito da guaine (dura, aracnoide e pia madre), ha un
diametro di 3-4 mm nel tratto intraorbitario e di 4-6,5 mm nel tratto
endocranico; ha una lunghezza che varia individualmente dai 35 ai 55 mm e
termina al chiasma ottico, ove parte delle sue fibre si incrocia per continuarsi
nel tratto ottico controlaterale.
Gli annessi oculari adempiono a funzioni essenziali per la normale
funzionalità del globo oculare. La motilità del bulbo oculare è infatti
assicurata dall’azione dei muscoli estrinseci ricoperti, insieme a parte del
bulbo, da una struttura fibrosa, la capsula di Tenone. La rimanente parte
anteriore del bulbo è rivestita da una membrana mucosa, la congiuntiva.
Questa riveste anche la porzione interna delle palpebre, formazioni
muscolocutanee con svariate funzioni, fra le quali la protezione del bulbo
(unitamente al sopracciglio) e l’uniforme distribuzione del secreto lacrimale
ottenuta con la loro rapida e ritmica chiusura.
Fra gli annessi oculari occorre infine ricordare l’apparato lacrimale, costituito
da ghiandole devolute alla produzione delle lacrime (ghiandole lacrimali) e da
un sistema di vie lacrimali (puntini, canalicoli, sacco e dotto naso-lacrimale)
deputato al loro drenaggio nelle cavità nasali.
1.2 – Anatomia descrittiva e topografica
Il bulbo oculare (figg. 1.1 e 1.2) è contenuto nell’orbita (figg. 1.3 e 1.4), dalle
cui
pareti
dista
in
misura
diseguale.
L’orbita,
che
rappresenta
sostanzialmente un elemento protettivo per il bulbo oculare, è strutturalmente
formata da tessuto osseo; ha l’aspetto di una piramide quadrangolare ad
apice posteriore e base rivolta anteriormente. Le pareti orbitarie sono quattro:
la parete superiore, che divide l’orbita dal seno frontale e dalla fossa cranica
anteriore; la parete laterale, che separa l’orbita dalla fossa cranica media e
da quella temporale; la parete inferiore, in diretto contatto col seno
mascellare; la parete mediale, che separa l’orbita dalla cavità nasale, dalle
cellule etmoidali e dal seno sferoidale.
10
Capitolo 1 – L’occhio umano
fig. 1.1. Anatomia del bulbo oculare. 1) Parte ciliare della retina; 2) corpo ciliare e muscolo ciliare; 3)
canale di Schlemm (seno venoso della sclerotica); 4) zona ciliare; 5) iride; 6) cornea; 7) camera
anteriore; 8) cristallino; 9) angolo iridocorneale; 10) congiuntiva; 11) ora serrata; 12) tendine del
muscolo retto mediale; 13) corpo vitreo; 14) canale ialoideo; 15) vasi venosi e arteriosi; 16) lamina
cribrosa della sclerotica; 17) nervo ottico; 18) arteria e vena centrali della retina; 19)-20) guaine del
nervo ottico; 21) fovea; 22) fascia bulbare; 23) sclera; 24) spazio sovracoroideo; 25) coroide; 26) parte
visiva della retina; 27) tendine del muscolo retto laterale.
A livello dell’apice orbitario si presentano tre aperture, attraverso le quali
decorrono strutture fondamentali per la fisiologia oculare: il forame ottico
(nervo ottico, arteria oftalmica e fibre nervose simpatiche); la fessura orbitaria
11
Capitolo 1 – L’occhio umano
superiore (nervo oculomotore comune, nervo trocleare, prima branca del
nervo trigemino, nervo abducente; vene oftalmiche, fibre nervose simpatiche
e un ramo dell’arteria meningea media); la fessura orbitaria inferiore
(seconda branca del nervo trigemino, arteria infraorbitaria e ramo della vena
oftalmica inferiore).
fig. 1.2. Anatomia dell’occhio umano con sezioni su piani diversi (visione posteriore). 1) Arterie ciliari
lunghe posteriore; 2) guaina durale; 3) guaina aracnoide; 4) fasci delle fibre del nervo ottico; 5) vasi
subdurali del nervo ottico; 6) arteria centrale della retina; 7) vena centrale della retina; 8) muscolo retto
laterale; 9) muscolo retto superiore; 10) congiuntiva; 11) corpo ciliare; 12) iride; 13) cristallino; 14)
cornea; 15) zonula ciliare; 16) canale ialoideo; 17) processi ciliari; 18) arterie e vene della coroide; 19)
retina; 20) coroide; 21) sclera; 22) arterie e vene episclerali; 23) muscolo retto inferiore.
12
Capitolo 1 – L’occhio umano
fig. 1.3. Visione d’insieme del fondo della cavità orbitaria con le inserzioni dei muscoli estrinseci
dell’occhio. 1) Foro ottico; 2) muscolo obliquo superiore; 3) troclea o puleggia del muscolo obliquo
superiore; 4) muscolo elevatore della palpebra superiore; 5) muscolo retto superiore; 6) anello dello
Zinn; 7) muscolo retto laterale esterno; 8) fessura sfenomascellare; 9) muscolo retto inferiore; 10)
muscolo obliquo inferiore; 11) canale nasale; 12) muscolo retto mediale interno.
Posteriormente, fra apice dell’orbita e occhio, si accumula una quantità,
individualmente variabile di tessuto adiposo, che contribuisce, tra l’altro, a
rendere il bulbo oculare più o meno sporgente rispetto ai margini dell’orbita
stessa. Oltre al tessuto adiposo, contribuiscono a isolare la tunica più esterna
13
Capitolo 1 – L’occhio umano
(sclerotica) del bulbo dalle pareti orbitarie altre strutture quali: la congiuntiva,
la capsula di Tenone ed i muscoli estrinseci.
fig. 1.4. Muscoli estrinseci dell’occhio visti lateralmente. 1) Seno frontale; 2) fasci del muscolo frontale;
3) nervo sopraorbitale; 4) cellulare adiposo dell’orbita; 5) septum orbitale; 6) tendine connettivo del
muscolo elevatore della palpebra superiore; 7) tendine del muscolo retto superiore; 8) fornice superiore
della congiuntiva; 9) congiuntiva; 10) tendine muscolare del muscolo elevatore della palpebra
superiore; 11) palpebra superiore; 12) muscolo orbicolare della palpebra; 13) tarso superiore; 14)
cornea; 15) pupilla; 16) tarso inferiore; 17) iride; 18) palpebra inferiore; 19) fornice inferiore della
congiuntiva; 20) tendine del muscolo retto inferiore; 21) muscolo obliquo inferiore; 22) seno mascellare;
23) tendine del muscolo retto laterale; 24) tendine del muscolo grande obliquo; 25) volta dell’orbita; 26)
muscolo laterale della palpebra superiore; 27) muscolo retto superiore; 28) muscolo retto mediale; 29)
muscolo retto laterale; 30) muscolo retto inferiore; 31) fossa pterigopalatina; 32) grande ala dello
sfenoide; 33) margine della fessura sferoidale; 34) processo clinoideo anteriore; 35) nervo ottico.
14
Capitolo 1 – L’occhio umano
La congiuntiva è una mucosa che riveste la porzione anteriore della sclera
(congiuntiva bulbare) e che, continuandosi posteriormente e ripiegandosi in
avanti (fornice congiuntivale), riveste anche la superficie interna delle
palpebre (congiuntiva palpebrale).
Le palpebre sono formazioni muscolocutanee che, in numero di due,
consentono di occludere in stato di contrazione l’apertura anteriore
dell’orbita, e che comunque, grazie alla presenza delle ciglia, emergenti dal
loro
bordo
esterno,
costituiscono
sempre
un
elemento
protettivo
determinante per il bulbo oculare e la cornea in particolare.
La palpebra superiore contribuisce poi alla protezione della ghiandola
lacrimale, situata nell’angolo supero-esterno dell’orbita e tutte e due le
palpebre, per mezzo dei puntini e canalicoli lacrimali, assicurano il drenaggio
del secreto lacrimale all’interno del sacco lacrimale. Da questo si diparte un
condotto (dotto nasolacrimale) che termina nel meato nasale inferiore.
La capsula di Tenone è un’aponeurosi, o guaina fibrosa, che avvolge
posteriormente quasi l’intero bulbo oculare e che consente e limita, nel
contempo, i movimenti oculari di verticalità, lateralità e torsione. Tali
movimenti si realizzano per azione dei muscoli estrinseci oculari retti
(laterale, superiore, mediale e inferiore) e obliqui (superiore e inferiore) che
originano, a eccezione del muscolo obliquo inferiore, dall’anello di Zinn,
formazione fibrosa posta all’apice dell’orbita. Da qui vengono a inserirsi
direttamente sulla sclera, anteriormente (retti) e posteriormente (obliqui),
all’equatore bulbare.
La sclera è la tunica bulbare più esterna, con funzioni protettive grazie,
soprattutto, alla sua marcata consistenza e contemporanea elasticità. Essa si
estende per circa i 5/6 posteriori di tutta la superficie bulbare e presenta un
colorito biancastro. Posteriormente presenta un canale dal quale fuoriesce il
nervo ottico, mentre anteriormente, attraverso una limitata area di transizione
(limbus sclerocorneale), si continua con la cornea. Questa formata di cinque
strati strutturalmente ben differenziati, funge essenzialmente da mezzo
diottrico; è avascolare, molto resistente, flessibile e riccamente innervata. Ha
15
Capitolo 1 – L’occhio umano
l’aspetto di una calotta sferica con diametro di circa 12 mm. Lo strato
corneale più esterno (epitelio), normalmente a contatto con l’aria, in
condizioni di chiusura palpebrale viene a trovarsi a contatto diretto con la
congiuntiva palpebrale stessa con l’interposizione di un sottile “film
lacrimale”; lo strato corneale più interno (endotelio) invece, limita
anteriormente la camera anteriore. Questa ha una profondità centrale media
di 3,5 mm ed è limitata posteriormente da un “diaframma” costituito da iride e
cristallino (fig. 1.5).
fig. 1.5. Anatomia della camera anteriore. 1) Cristallino; 2) cornea; 3) muscolo sfintere dell’iride; 4)
ondulazioni dell’iride; 5) camera anteriore; 6) epitelio pigmentato; 7) muscolo dilatatore dell’iride; 8)
camera posteriore; 9) endotelio; 10) membrana di Descemet; 11) legamento sospensore del cristallino
(zonula dello Zinn); 12) linea di Schwalbe; 13) trasecolato e spazi di Fontana; 14) canale di Schlemm;
15) sperone centrale; 16) angolo camerulare; 17) legamento pettinato; 18) processo ciliare; 19) fibre
circolari; 20) fibre radiate; 21) fibre meridionali; 22) congiuntiva; 23) vena ciliare anteriore; 24) sclera;
25) spazio sovracoroideo.
16
Capitolo 1 – L’occhio umano
La camera anteriore contiene umor acqueo che, prodottosi in gran parte
(70%) a livello dell’epitelio che ricopre il corpo ciliare (epitelio ciliare),
attraversa il forame pupillare per poi essere drenato a livello dell’angolo della
camera anteriore, formato dal congiungimento della cornea con l’iride
(angolo iridocorneale). Quasi all’apice di tale angolo, l’umore acqueo,
sollecitato da una pressione endoculare, attraversa un filtro (trabecolato
corneosclerale) e si immette nel canale di Schlemm, dal quale fuoriesce a
mezzo delle vene acquose e episclerali.
Tale angolo iridocorneale normalmente è aperto e consente un agevole
deflusso dell’umore acqueo, ma in condizioni anomale o patologiche può
essere stretto, o addirittura chiuso, rendendo difficoltoso, o impedendo del
tutto, l’accesso dell’umore acqueo al trasecolato corneosclerale. Ne risulta un
aumento della pressione endoculare e l’insorgere di un glaucoma.
L’iride rappresenta, praticamente, il diaframma del sistema diottrico oculare,
regolatore dell’intensità luminosa e della profondità di campo; il colore della
sua superficie anteriore varia da un soggetto all’altro (prevale il castano e
l’azzurro), mentre lo strato profondo è nero o molto scuro in tutti i soggetti
normali. Al centro di essa si trova un foro, la pupilla il cui diametro può ridursi
(miosi) o aumentare (midriasi) in varie condizioni fisiologiche e patologiche e
per azione di farmaci specifici stimolanti o inibenti il sistema nervoso
autonomo. Posteriormente all’iride, e separato da essa ad opera di una
ridottissima cavità, troviamo il cristallino o lente, di forma simile ad una lente
biconvessa, trasparente e privo di vasi e nervi. Anche dopo la nascita il suo
sviluppo procede ininterrottamente, per cui, con l’età, esso viene a perdere
alcune delle proprie caratteristiche biofisiche. La perdita di elasticità conduce
alla presbiopia (verso i 42-45 anni), ovvero alla riduzione del potere
accomodativo del cristallino stesso, sua funzione principale nel sistema
diottrico oculare. La perdita di trasparenza del cristallino, secondaria a varie
cause, prima fra tutte l’età, può condurre alla formazione di una cataratta, e
quindi ad una riduzione spesso marcata della visione.
17
Capitolo 1 – L’occhio umano
Posteriormente al cristallino e limitata dall’intera cupola retinica, vi è
un’ampia cavità (camera vitrea) che contiene una sostanza gelatinosa,
trasparente e avascolare, il vitreo. Esso adempie a funzioni diottriche e di
sostegno. Il vitreo può perdere la sua normale trasparenza soprattutto a
causa di processi patologici a carico della coroide o della retina
(infiammazioni, emorragie, ecc…). Il vitreo è praticamente a contatto con la
più interna delle tre membrane oculari, la retina.
La retina si estende dalla papilla ottica ai corpi ciliari (ora serrata) ed è
esternamente limitata dalla coroide (membrana di Bruch) per mezzo
dell’epitelio pigmentato. E’ una membrana molto sottile con spessore
massimo di 0,5 mm a livello della papilla ottica e, in condizioni normali,
trasparente. Fra la membrana di Bruch e l’epitelio pigmentato esiste uno
spazio virtuale che, nel distacco di retina, diventa reale e colmo di liquido
(liquido sottoretinico) e non consente alla retina di riadagiarsi. La retina è
composta da dieci strati costituiti da elementi ben differenziati, sia dal punto
di vista morfologico, sia da quello funzionale (fig. 1.6). I recettori sono
raggruppati nello strato dei coni (più numerosi nell’area retinica centrale) e
dei bastoncelli (più numerosi alla periferia). L’area della visione distinta è
situata posteriormente e al centro, ove la retina riduce notevolmente il suo
spessore (macula o fovea). Per maggiori dettagli sulla retina si veda il cap. 2.
fig. 1.6. Sezione istologica di occhio umano. 1) Sclera; 2) coroide; 3) retina. (100 X).
18
Capitolo 1 – L’occhio umano
La coroide è il segmento posteriore della tunica vascolare o nutritizia
dell’occhio. Ha un colorito bruno, tappezza internamente la sclera, e su di
essa si adagia la retina. In avanti a livello dell’ora serrata si continua con il
corpo ciliare. La coroide è costituita da 4 strati: la lamina fusca, che separa la
coroide dalla sclera, lo strato dei grossi vasi, lo strato dei capillari ed infine la
lamina vitrea (o membrana di Bruch) che offre sostegno all’epitelio
pigmentato della retina.
Dal punto di vista ottico, l’occhio può essere considerato come una lente
convergente dotata di un notevole potere rifrattivo. Il centro ottico viene a
trovarsi a circa 7 mm dalla cornea; il punto in cui convergono i raggi che
giungono all’occhio (cornea) paralleli tra loro è a 24 mm dalla cornea e
coincide con la retina (fovea). Un occhio otticamente normale e dotato di tali
caratteristiche è detto emmetrope; esistono tuttavia varie anomalie rifrattive
per cui l’occhio può essere ametrope (miopia, ipermetropia e astigmatismo).
Esistono lenti opportune (occhiali, lenti corneali) che consentono di
correggere in tutto od in parte tali difetti visivi.
1.3 – Vascolarizzazione
L’occhio è provvisto di due sistemi vascolari (retinico e ciliare) pressoché
indipendenti, messi in comunicazione tra di loro soltanto a livello
dell’emergenza del nervo ottico dalla sclera (fig. 1.7). Le arterie provengono
dall’arteria oftalmica (ramo della carotide interna); le vene sono affluenti delle
due vene oftalmiche, superiore ed inferiore, tributarie del seno cavernoso.
Il primo sistema è irrorato dall’arteria centrale della retina: di calibro piuttosto
piccolo (0,3 mm), giunta, dopo breve decorso, a circa 1 cm dalla sclera, si
impegna nello spessore del nervo ottico e ne segue l’asse longitudinale sino
alla papilla. Qui, nella maggior parte dei casi, si biforca in un ramo superiore
ed uno inferiore, ciascuno dei quali fornisce subito dopo un ramo mediale o
nasale ed uno laterale o temporale. Decorrendo nello strato delle fibre ottiche
essi si ramificano ripetutamente senza mai entrare in comunicazione e danno
19
Capitolo 1 – L’occhio umano
luogo a due letti capillari ,uno esterno ed uno interno per tutto il territorio
retinico interno, tranne che per la regione della fovea centralis, priva di vasi.
fig. 1.7. Schema della circolazione dell’occhio in una sezione orizzontale. 1) Arterie ciliari posteriori
brevi; 2) arterie ciliari posteriori lunghe; 3) arterie e vene ciliari anteriori; 4) vasi anteriori della
congiuntiva bulbare; 5) vasi posteriori; 6) arteria e vena centrali della retina; 7) vasi sottodurali del
nervo ottico; 8) vasi durali del nervo ottico; 9) vasa vorticosa; 10) arteria e vena episclerali; 11) arteria
coroidea ricorrente; 12) capillari della coroidea; 13) comunicazione tra le arterie ciliari brevi e l’arteria
centrale della retina; 14) comunicazione dei vasi coroidei con i vasi retinici; 15) vasi dei processi ciliari;
16) vasi dell’iride; 17) grande cerchio arterioso dell’iride; 18) canale dello Schlemm; a) nervo ottico e
sua guaina; b) sclera; c) coroide; d) retina; e) iride; f) processi ciliari; g) congiuntiva; h) cornea; i)
cristallino.
20
Capitolo 1 – L’occhio umano
Il secondo sistema è irrorato dalle arterie ciliari che si distinguono in:
1) arterie ciliari posteriori brevi: inizialmente in numero di due o tre, si
ramificano ripetutamente sino a divenire una ventina. Attorniando il
nervo ottico, esse perforano la sclera e giungono alla coroide. Qui,
decorrendo secondo i meridiani, si dividono in numerosi rami (arterie
coroidee);
2) arterie ciliari posteriori lunghe: in numero di due, nasale e temporale,
perforano la sclera in vicinanza del nervo ottico e decorrono tra sclera
e coroide senza dare rami. Arrivate davanti al muscolo ciliare si
biforcano in un ramo ascendente ed uno discendente che si mettono
in comunicazione con il rispettivo controlaterale dando luogo al
cosiddetto grande cerchio arterioso dell’iride;
3) arterie ciliari anteriori: sono collaterali delle due arterie muscolari e si
distaccano da esse all’altezza dell’inserzione dei muscoli retti
sull’occhio. Dopo aver fornito le anse marginali, si gettano nel grande
cerchio arterioso;
4) il grande cerchio arterioso dell’iride fornisce: rami ciliari, iridei e
coroidei messi in comunicazione con i vasi della coroide provenienti
dalle ciliari brevi.
Le vene sono, per il primo sistema, la centrale della retina e, per il secondo,
le ciliari anteriori (che drenano dai processi ciliari), le vorticose (che drenano
dal sistema iridociliare e coroideo) e le ciliari posteriori (dalla porzione
posteriore della sclera).
Nell’occhio non sono stati descritti veri vasi linfatici. Paragonabile a un circolo
linfatico è quello dell’umor acqueo, prodotto dai processi ciliari e drenato
,attraverso il sistema trabecolare sclerocorneale, dal seno venoso della
sclera (o canale dello Schlemm); da qui, per mezzo di esili venuzze, esso
viene trasportato nelle vene episclerali (o vene acquose) tributarie delle vene
ciliari anteriori.
21
Capitolo 2 – La retina
Capitolo 2
LA RETINA
2.1– Morfologia
La retina dell’adulto appare come una membrana sottile, trasparente, a forma
di coppa, che tappezza la porzione interna del bulbo oculare, dal nervo ottico
fino all’orifizio pupillare. La retina può essere suddivisa in una porzione ottica,
estesa dall’area di entrata del nervo ottico fino all’ora serrata; in una porzione
intermedia (ciliare) costituita da uno strato esterno di cellule pigmentate e da
uno strato interno che è in rapporto con la secrezione e il riassorbimento di
umor acqueo; in una porzione anteriore, che corrisponde all’iride ed è
costituita da cellule contrattili che formano i muscoli sfintere e dilatatore della
pupilla, nonché da cellule pigmentate (fig. 2.1).
fig. 2.1. Retina di ratto adulto. Le frecce indicano le cellule pigmentate dell’iride. (650 X).
L’ora serrata, che è il brusco punto di passaggio tra la porzione ottica e
quelle restanti della retina (fig. 2.2) (la cosiddetta retina cieca, in quanto non
deputata alla ricezione di informazioni visive), si presenta come un margine
22
Capitolo 2 – La retina
seghettato composto da arcate adiacenti con la concavità rivolta in avanti. I
denti formati tra un’arcata e l’altra presentano le punte rivolte in avanti, verso
i processi ciliari.
fig. 2.2. Sezione dell’occhio di embrione di ratto di 8 mm. C) Cristallino; I) porzione irido-ciliare della
retina; P) palpebre; R) retina. La freccia indica l’ora serrata. (30 X).
A un esame superficiale della morfologia retinica osserviamo due regioni di
particolare interesse, la macula lutea e la papilla ottica (fig. 2.3). La macula
lutea è un’area ellissoidale, di colorito giallastro, di circa 2-3 mm di larghezza
per 1-1,5 mm di altezza, localizzata a 2,5 cm lateralmente rispetto al punto di
emergenza del nervo ottico nella retina. La macula lutea si presenta rilevata
esternamente e con una depressione centrale, rotondeggiante e non molto
profonda: la fovea centrale. La fovea, che rappresenta la porzione retinica in
cui la visione è più distinta, è circondata in alto e in basso da grossi vasi
sanguigni, mentre nel suo interno sono presenti soltanto arteriole, venule e
capillari. La parte centrale della fovea, con un diametro di circa 0,5 mm,
appare, invece, completamente avascolarizzata.
La papilla ottica rappresenta il punto di emergenza del nervo ottico nella
retina (fig. 2.3). La papilla appare come un’area chiara, rotondeggiante, posta
3-4 mm medialmente e 1 mm inferiormente rispetto al polo posteriore
dell’occhio e misura 1,5 mm di diametro. Al centro della papilla è presente
una depressione in corrispondenza della quale emergono i vasi retinici. La
23
Capitolo 2 – La retina
papilla ottica è l’unica regione della porzione posteriore della retina a essere
insensibile alle stimolazioni luminose.
fig. 2.3. Papilla ottica e vasi sanguigni della retina dell’occhio sinistro visti dal davanti. Il cerchietto sulla
sinistra dell’immagine delimita la papilla ottica. 1) Macula lutea; 2) arteriola e venula maculari superiori;
3) arteriola e venula temporali retiniche superiori; 4) arteriola e venula nasali retiniche superiori; 5)
arteriola e venula mediali della retina; 6) arteriola e venula nasali retiniche inferiori; 7) arteriola e venula
temporali retiniche inferiori; 8) arteriola e venula maculari inferiori.
2.2 – Struttura e ultrastruttura
La parte ottica della retina è costituita da tre strati di cellule nervose
sostenute da cellule gliali specializzate e delimitata da due membrane
limitanti, quella esterna e quella interna. Strutturalmente, procedendo
24
Capitolo 2 – La retina
dall’esterno verso l’interno, si rileva la presenza dei seguenti dieci strati (fig.
2.4):
fig. 2.4. Rappresentazione della struttura della retina in sezione trasversale (a sx). A dx sono indicati i
neuroni dello schema di Cajal. I) Epitelio pigmentato; II) strato dei coni e dei bastoncelli; III) strato
granulare esterno; IV) strato plessiforme esterno; V) cellule orizzontali; VI) cellule bipolari; VII) cellule
amacrine; V), VI), VII) strato granulare interno; VIII) strato plessiforme interno; IX) strato delle cellule
gangliari; X) strato delle fibre nervose; a) membrana limitante esterna; b) membrana limitante interna;
c) fibra di Muller.
1. L’epitelio pigmentato. – Le cellule dell’epitelio pigmentato sono di
forma prismatica, con la base che poggia sulla coroidea e l’apice
diretto verso i fotorecettori, ma non in contatto. Le cellule epiteliali
sono saldate tra loro per mezzo di giunzioni serrate. Il nucleo è posto
alla base della cellula. Funzionalmente l’epitelio pigmentato è
deputato a fornire supporto metabolico e trofico (nutrizione dei tessuti)
ai fotorecettori. Le giunzioni serrate tra le cellule epiteliali adiacenti
costituiscono
un
dispositivo
morfofunzionale
particolarmente
importante che seleziona le sostanze che dal torrente circolatorio
possono
raggiungere
gli
strati
ematoretinica).
25
nervosi
della
retina
(barriera
Capitolo 2 – La retina
2. Strato dei fotorecettori. – I fotorecettori retinici sono cellule nervose
altamente
differenziate,
sensibili
alle
radiazioni
luminose.
Si
conoscono due tipi di recettori retinici, i bastoncelli e i coni.
Strutturalmente
entrambi
gli
elementi
cellulari
hanno
notevoli
somiglianze e si presentano allungati, con la porzione esterna rivolta
verso l’epitelio pigmentato e l’estremità opposta che guarda verso la
porzione interna della retina. Schematicamente i fotorecettori possono
essere suddivisi nelle seguenti porzioni: a) segmento esterno; b)
segmento interno; c) zona nucleare; d) regione sinaptica.
I bastoncelli. – Tutta la porzione visiva della retina, con l’eccezione
della porzione centrale della macula lutea e della papilla ottica,
contiene bastoncelli (fig. 2.5 (A)). Il segmento esterno dei bastoncelli è
costituito da lamelle disposte perpendicolarmente all’asse maggiore
del fotorecettore, di forma appiattita, sovrapposte l’una sull’altra,
avvolte e delimitate dalla membrana limitante del segmento esterno. Il
segmento esterno è congiunto a quello interno da un sottile stelo
provvisto di una struttura ciliforme modificata, di natura contrattile. Il
segmento interno viene comunemente suddiviso in due porzioni:
ellissoide e mioide. La zona nucleare contiene il corpo cellulare con il
nucleo del fotorecettore (piccolo e di forma ovale) ed è in rapporto con
il segmento interno e la regione sinaptica. La regione sinaptica (o
porzione basale del fotorecettore) presenta una forma allargata; a
livello di tale porzione del fotorecettore sono visibili bottoni (spine)
sinaptici attraverso i quali i bastoncelli si articolano con i neuroni
bipolari.
I coni. – I coni (fig. 2.5 (B)). Sono maggiormente addensati nella
macula lutea, e diminuiscono gradatamente di numero procedendo
verso le porzioni periferiche della retina. Diversamente dai bastoncelli
l’articolo esterno dei coni ha una forma conica con base allargata e
apice ristretto. Contrariamente alle lamelle dei bastoncelli, quelle
dell’articolo esterno dei coni non sono separate, ma, per la maggior
26
Capitolo 2 – La retina
parte, sono in continuità con la membrana limitante esterna
dell’articolo. Il segmento interno dei coni è più ampio di quello dei
bastoncelli; la zona nucleare presenta un nucleo di dimensioni
maggiori di quello dei bastoncelli, mentre i lembi citoplasmatici che la
uniscono con il segmento interno sono più corti di quelli dei
bastoncelli. La regione sinaptica è più ampia di quella dei bastoncelli
ed è caratterizzata dalla presenza di tre specializzazioni sinaptiche:
una, centrale, per l’articolazione con i neuroni bipolari, due laterali per
l’articolazione con i neuroni orizzontali.
(A)
(B)
fig. 2.5. (A) Rappresentazione schematica dell’organizzazione ultrastrutturale di un bastoncello. a) segmento esterno; b) stelo di congiunzione tra segmento esterno e corpo cellulare
del fotorecettore; c) ellissoide; d) mioide; e) lembo citoplasmatico di connessione tra segmento esterno e regione nucleare; f) lembo citoplasmatico di connessione tra regione nucleare e
regione sinaptica; g) regione sinaptica.(B) Rappresentazione schematica dell’organizzazione
ultrastrutturale di un cono. a) segmento esterno; b) segmento interno; c) lembo citoplasmatico
di connessione tra segmento esterno e regione nucleare; d) lembo citoplasmatico di connessione tra regione nucleare e regione sinaptica; e) regione sinaptica.
27
Capitolo 2 – La retina
3. Membrana limitante esterna. – La membrana limitante esterna, così
definita perché al microscopio ottico appare come una struttura
omogenea, contiene, invece, complessi giunzionali tra i fotorecettori e
le cellule gliali di sostegno (le cellule di Muller).
4. Strato granulare esterno. – Lo strato granulare esterno contiene i
nuclei dei fotorecettori le cui caratteristiche sono state descritte
precedentemente.
5. Strato plessiforme esterno. – Nello strato plessiforme esterno è stata
dimostrata l’esistenza di contatti sinaptici tra fotorecettori, neuroni
bipolari e neuroni orizzontali. In particolare, i bastoncelli entrano in
contatto prevalentemente con i neuroni bipolari, mentre i coni
prendono contatto sia con i neuroni bipolari che con quelli orizzontali.
6. Strato granulare interno. – Tale strato contiene i corpi cellulari dei
neuroni bipolari e di quelli orizzontali. I neuroni bipolari sono disposti
perpendicolarmente rispetto agli strati retinici; possiedono un corpo
cellulare allungato, uno o più dendriti, che prendono sinapsi con i
fotorecettori, e un solo assone che prende sinapsi con i neuroni
amacrini e con quelli gangliari. I neuroni orizzontali sono costituiti da
scarso citoplasma e da un’ampia arborizzazione dendritica (fig. 2.6
(A)). Nello strato granulare interno è posto il corpo cellulare delle
cellule di Muller (fig. 2.6 (B)) le quali hanno una forma cilindrica.
Funzionalmente possono essere considerate come elementi di
supporto trofico e meccanico ai neuroni retinici; le numerose
propaggini citoplasmatiche delle cellule di Muller si insinuano tra i
neuroni retinici.
7. Strato plessiforme interno. – Contiene i corpi cellulari dei neuroni
amacrini e rappresenta la regione del contatto sinaptico tra neuroni
bipolari, amacrini e gangliari. I neuroni amacrini sono cellule prive di
assone e provviste di numerosi dendriti. Si riconoscono due tipi di
neuroni amacrini: diffusi e stratificati. I dendriti dei neuroni diffusi sono
distribuiti a tutto lo strato plessiforme interno, mentre quelli dei neuroni
28
Capitolo 2 – La retina
stratificati seguono un percorso molto limitato e si mantengono in
prossimità delle cellule di origine.
(A)
(B)
fig. 2.6. (A) Rappresentazione schematica dei componenti di un neurone. Le frecce indicano
la
direzione
dell’impulso.
(B)
Rappresentazione
schematica
dell’organizzazione
ultrastrutturale di una cellula di Muller. n) Nucleo; fi) microfilamenti; bl) lamina basale
(costituisce la membrana limitante interna della retina).
29
Capitolo 2 – La retina
8. Strato delle cellule gangliari. – A livello di tale strato osserviamo il
corpo cellulare dei neuroni gangliari, grosse cellule nervose provviste
di un’abbondante arborizzazione dendritica e di un assone che si
mielinizza notevolmente quando abbandona lo strato: detti anche
multipolari,
i
neuroni
gangliari
costituiscono
l’ultimo
neurone
intraretinico delle vie ottiche (fig. 2.7). I neuroni gangliari sono di
grossa taglia e, in rapporto all’estensione della propria arborizzazione
dendritica, si suddividono in almeno tre gruppi: 1) neuroni gangliari
diffusi, che inviano i propri dendriti in tutto lo strato plessiforme interno;
2) piccoli neuroni gangliari, che posseggono un solo dendrite
principale dal quale si originano, a livello dello strato plessiforme
interno, ramificazioni dendritiche secondarie e terziarie; 3) neuroni
gangliari stratificati, i cui dendriti non abbandonano lo strato delle
cellule gangliari.
9. Strato delle fibre ottiche. – Gli assoni dei neuroni gangliari,
abbandonato lo strato delle cellule gangliari, si mielinizzano e seguono
un decorso radiale per convergere verso la papilla del nervo ottico da
dove, come nervo ottico, abbandoneranno il bulbo oculare (fig. 2.7). A
livello della macula lutea lo strato delle fibre ottiche è particolarmente
sottile (fig. 2.7): infatti le fibre ottiche seguono in decorso particolare,
circondando, piuttosto che attraversando, la macula lutea.
10. Membrana limitante interna. – La membrana limitante interna, che
rappresenta la porzione di confine tra retina e corpo vitreo, è costituita
dalla lamina basale delle cellule di Muller ed è rappresentata nella fig.
2.6 (B).
30
Capitolo 2 – La retina
fig. 2.7. Rappresentazione schematica delle vie ottiche. In alto a destra sono rappresentate le
cellule nervose retiniche: a) fotorecettori; b) neuroni bipolari; c) neuroni multipolari; d) fibre del
nervo ottico. Si osservi il parziale incrociamento delle vie ottiche in corrispondenza del
chiasma dei nervi ottici.
31
Capitolo 2 – La retina
2.3 – Istofisiologia
Il processo visivo a livello retinico avviene, fondamentalmente, in due fasi. I
raggi luminosi, attraversati i mezzi diottrici dell’occhio, sono proiettati sullo
strato fotosensibile (fotorecettori) della retina, dove determinano una
modificazione biochimica delle molecole di pigmento visivo dei fotorecettori.
A seguito di tale modificazione, si altera lo stato della membrana dei
fotorecettori, che depolarizzandosi o iperpolarizzandosi dà inizio alla
neurotrasmissione di impulsi nervosi lungo le vie ottiche.
I pigmenti visivi prodotti dalle cellule dell’epitelio pigmentato derivano dalla
molecola della Vit. A e, strutturalmente, sono una combinazione tra retinene
(derivato aldeidico della Vit. A) e glicoproteine idrofobiche: le opsine. I
bastoncelli contengono tutti un solo tipo di pigmento visivo, la rodopsina, che
viene attivata dalla luce crepuscolare. I coni, invece, posseggono tre diversi
tipi di pigmenti visivi, che vengono attivati, rispettivamente, dalla luce rossa,
blu e verde. Dunque, i bastoncelli sono i neuroni retinici della visione in
bianco e nero, i coni sovraintendono alla visione a colori.
fig. 2.8. Fovea centrale di retina di Macacus rhesus. 1) Sclera; 2) coroidea; 3) epitelio pigmentato; 4)
strato dei fotorecettori; 5) strato granulare esterno; 6) strato plessiforme esterno; 7) strato granulare
interno; 8) strato plessiforme interno; 9) strato delle cellule gangliari; 10) membrana limitante interna.
32
Capitolo 2 – La retina
Mentre i bastoncelli sono diffusi pressoché ovunque nella retina, i coni sono
addensati principalmente nella macula lutea e nella fovea centrale (fig. 2.8).
In quest’ultima zona, dal diametro di circa 500-550 µm, sono presenti almeno
quattro milioni di coni.
2.4 – Retinopatie vascolari: retinopatia diabetica
Nei paesi industrializzati, ove il 2-5% della popolazione è diabetica o è
destinata a divenire tale, la retinopatia diabetica è divenuta la prima causa di
cecità provocando oltre il 20% dei non vedenti. Ciò avviene perché l’insulina
e gli ipoglicemizzanti orali hanno prolungato la sopravvivenza dei diabetici,
ma per effetto della maggior durata della vita sono aumentate le
complicazioni: oculari, cardiache, renali, cerebrali, ecc.... La retinopatia è la
complicanza più temibile per la qualità della vita perché appare quando le
funzioni cardiache e renali sono ancora buone e diviene rapidamente
invalidante. Attualmente, circa la metà dei portatori di retinopatia diventano
subvedenti o ciechi entro 5-7 anni dalla scoperta della retinopatia, o per una
degenerazione maculare, o per una vitreopatia da neoformazione vasale,
mentre circa la metà dei subvedenti da un occhio lo diverrà anche dal
secondo nei 2 anni seguenti.
La frequenza della retinopatia diabetica varia a seconda dell’età nella quale
compare la malattia di base e a seconda della durata: in linea di massima i
giovani al di sotto dei 30 anni hanno maggiori probabilità di sviluppare la
retinopatia rispetto agli anziani nei quali però essa compare più
precocemente anche perché l’arteriosclerosi e l’ipertensione sono fattori
peggiorativi.
La durata del diabete è un dato incerto perché è sempre difficile stabilire la
data d’inizio della malattia e perché lo stato del compenso metabolico
influenza la comparsa della retinopatia: in linea di massima nei diabetici mal
compensati è sufficiente un periodo fra i 2 ed i 5 anni. Esistono rari casi di
resistenza individuale che dopo 20-30 anni di malattia non mostrano alcun
33
Capitolo 2 – La retina
segno oftalmoscopico o fluoroangiografico di malattia. La retinopatia
diabetica non compare o ha un decorso molto blando in occhi con importanti
alterazioni corioretiniche cicatriziali o atrofiche, come nelle grandi miopie
degenerative.
La patogenesi della retinopatia diabetica è un fenomeno complesso con
molte zone ancora in ombra, condizionato da fattori generali e locali. Fra i
fattori endocrini, a parte il deficit insulinico, la partecipazione dell’ipofisi(1) è il
più nitido. Il ruolo patogenetico dell’ormone somatotropo ipofisario (HGH)
sembra
confermato
dalla
comparsa
di
lesioni
capillari
retiniche
simildiabetiche negli animali da esperimento dopo trattamento con HGH e da
una nutrita serie di osservazioni cliniche nell’uomo che vanno dal
peggioramento della retinopatia umana dopo somministrazione di HGH, al
rilievo di alti livelli basali di ormone somatotropo nei diabetici retinopatici. Fra
i fattori locali, la lesione fondamentale è la microangiopatia diabetica, una
sequenza di fenomeni che dall’ipossia (=carenza di ossigenazione del
sangue) primitiva della retina giunge all’occlusione dei capillari retinici. Si
ritiene che l’ipossia retinica provochi inizialmente una vasodilatazione
funzionale dei capillari per supplire alle richieste metaboliche della retina.
L’accumulo di acido lattico e di anidride carbonica nel sangue accentua il
fenomeno di vasodilatazione al quale nel tempo si associano (o fanno
seguito) danni della parete capillare – l’alterazione delle cellule endoteliali,
l’ispessimento della membrana basale – che riducono la capacità di
autoregolazione dei capillari e provocano una riduzione del flusso ematico.
Sono contemporanee le alterazioni ematiche, l’aumento della viscosità
ematica e il rallentamento del flusso nel circolo capillare retinico.
NOTA (1): l’ipofisi
è una ghiandola endocrina situata alla base dell’encefalo e in una posizione
inferoventrale rispetto all’ipotalamo, al quale è collegata mediante un peduncolo. La sua forma è
ovoidale, schiacciata, e il suo asse maggiore è orientato trasversalmente. Le dimensioni medie
nell’adulto sono le seguenti: diametro trasversale 15 mm, diametro verticale 5 mm, diametro sagittale 7
mm. Nella specie umana pesa circa 0,5 g. E’ uno degli organi più importanti dell’organismo perché
produce numerosi ormoni mediante i quali controlla l’attività di altre ghiandole endocrine; inoltre essa
immagazzina e immette in circolo neurormoni di provenienza ipotalamica.
34
Capitolo 2 – La retina
L’occlusione del capillare retinico è la naturale evoluzione delle modifiche
parietali
ed
ematiche.
Da
essa
prendono
origine,
in
chiave
di
ischemia(=insufficiente afflusso di sangue arterioso)-ipossia, tutte le
alterazioni retiniche, microaneurismi (=cedimento, dilatazione patologica di
un tratto di parete arteriosa), essudati (=liquido che filtra attraverso le pareti
dei capillari sanguigni di un tessuto infiammato) duri e molli, edema
(=accumulo anomalo di liquido negli spazi interstiziali dei tessuti e nelle
cavità del corpo umano), emorragie, neovascolarizzazione, anastomosi
(=comunicazione tra due o più canali corporei) artero-venose, che nelle più
disparate combinazioni ed associazioni compongono i quadri clinici della
retinopatia diabetica (fig. 2.9).
fig. 2.9. Retinopatia diabetica. Fase non proliferativa. Evidenti i microaneurismi, le emorragie, gli
essudati retinici e le alterazioni vasali.
35
Capitolo 2 – La retina
Lo studio clinico della retinopatia diabetica richiede la biomicroscopia e la
fluoroangiografia che permettono di visualizzare le alterazioni anatomiche e
funzionali, edema maculare, microaneurismi, aree di occlusione capillare,
aree di permeabilità capillare, che non sono visibili all’oftalmoscopia.
Per la variabilità dei decorsi e per il polimorfismo dei quadri clinici la
retinopatia diabetica sfugge a tentativi organici, ma relativamente semplici, di
classificazione. Nella tendenza attuale prevalente viene distinta in due forme
o stadi, non obbligatoriamente evoluti l’uno nell’altro, la retinopatia semplice
e la retinopatia proliferante.
La retinopatia semplice o non proliferante corrisponde allo stadio
microangiopatico della malattia. Allo stadio iniziale è caratterizzata dalla
presenza di numerosi microaneurismi, localizzati soprattutto al polo
posteriore, e da piccole aree ischemiche (fig. 2.10).
fig. 2.10. Retinopatia diabetica non proliferativa. L’esame fluoroangiografico evidenza numerosi
microaneurismi e l’edema maculare.
36
Capitolo 2 – La retina
Con il passare del tempo aumentano le aree focali di chiusura capillare e
l’ipossia retinica. Compaiono le alterazioni venose – dilatazioni, tortuosità --,
le emorragie intraretiniche e più raramente epiretiniche, gli essudati duri e
l’edema retinico quando le aree di aumentata permeabilità capillare sono
divenute consistenti. Nello stadio avanzato compaiono gli essudati molli
(aree di rigonfiamento e necrosi neuronale intraretiniche, espressione di una
marcata ipossia retinica), le anastomosi artero-venose e, talvolta, la
neoformazione vasale epiretinica ed epipapillare, che iniziano lo stadio
proliferante. Nei diabetici giovani per lo più prevalgono le componenti
emorragiche e gli essudati molli, negli anziani invece gli essudati duri, le
microemorragie intraretiniche, l’edema e la degenerazione maculare. In linea
di massima, se non vi sono rapide alterazioni maculari, la visione centrale
rimane abbastanza conservata anche per periodi abbastanza lunghi ma
tende comunque a decadere ad acutezze mediocri. La cecità completa è rara
nella retinopatia semplice a patto che non evolva verso la forma proliferante.
La retinopatia proliferante è lo stadio terminale del 10-15% delle retinopatie
semplici ma può raramente esordire già come tale. E’ caratterizzata da una
neovascolarizzazione epiretinica che di solito inizia nella media periferia
peripapillare per poi farsi epipapillare ma può esordire direttamente sulla
papilla ottica allargandosi poi sulla superficie retinica. Lo stimolo alla
neovascolarizzazione è sostenuto dalla ischemia-ipossia.
Successivamente si ha una partecipazione al processo del corpo vitreo che
contrae aderenze (=connessioni patologiche che uniscono tra loro due
organi, o parti di organo, primi vicini tra loro ma non uniti, spesso in
conseguenza di un processo infiammatorio) con i vasi neoformati. Inizia così
lo stato ialopatico nel quale i vasi neoformati penetrano nel vitreo dapprima
liberi poi rivestiti da un tessuto fibroso di tipo guainale che li rende simili a
cordoni che talora sanguinano nel vitreo. La coartazione (=costrizione,
restringimento) ed il distacco posteriore del vitreo provocano poi una
attrazione in avanti dei vasi neoformati e della retina, aprendo la via a
massicce emorragie intravitreali. Le emorragie provocano immediatamente
37
Capitolo 2 – La retina
una brusca caduta della visione: tendono a riassorbirsi lentamente
soprattutto nei giovani, diventano con facilità definitive specie negli anziani.
Tali emorragie stimolano la trasformazione fibroplastica del vitreo, e
successivamente si ha un distacco retinico secondario da trazione,
localizzato al polo posteriore o diffuso, visibile quando l’intorbidamento
vitreale diminuisce: la visione a questo punto è definitivamente perduta.
38
Capitolo 3– Tecniche di clustering
Capitolo 3
TECNICHE DI CLUSTERING
3.1- Introduzione
In questo capitolo vengono analizzati e descritti i concetti alla base della
logica Fuzzy e della Statistical Learning Theory nonché l’implementazione di
due tipici classificatori: FCM (Fuzzy c-Means) e quello basato su SVM
(Support Vector Machine). In particolare sarà analizzato un classificatore
SVM, da me usato per classificare, basandomi sul colore, sia gli essudati
diabetici sia il disco ottico (hanno più o meno lo stesso colore) rispetto al
background.
Dato un universo di dati finito X={x1, ..., xn}, lo scopo della clusterizzazione è
quello di individuare una partizione di X in c cluster (sottoinsiemi di X) con
2≤c≤n.
La condizione c=1 comporterebbe il rifiuto dell’ipotesi di esistenza di possibili
cluster tra i dati. La condizione c=n corrisponde alla situazione, poco
significativa, in cui ogni singolo elemento di X forma un cluster.
Volendo noi un classificatore binario varrà c=2.
3.2- Sistemi in logica fuzzy
La fig. 3.1 illustra un’architettura di sistema in logica fuzzy (SLF) largamente
utilizzata nell’ambito del settore dei controlli automatici e della processazione
dei segnali.
39
Capitolo 3– Tecniche di clustering
fig. 3.1. Sistema Logico Fuzzy (SLF).
Un SLF mappa ingressi numerici in uscite numeriche. Contiene quattro
componenti principali: il sistema di regole, il fuzzificatore, il motore
inferenziale ed il defuzzificatore. Una volta che si sono fissate le regole, la
mappatura ingresso-uscita può essere espressa quantitativamente come
y=f(x) dove x è il vettore degli ingressi e y è l’uscita scalare. Tale mappatura
non deve essere necessariamente lineare. L’obbiettivo è ora quello di
ottenere una formula esplicita per questa mappatura tra x e y.
Le regole o come sarà poi spiegato, le regole ingegneristiche sono espresse
mediante una collezione di asserzioni IF-THEN del tipo “IF u1 è alto e u2 è
medio THEN v è medio-alto”. Questa enunciazione evidenzia come sia
fondamentale la conoscenza di:
1.
Variabili linguistiche, invece che valori numerici di una certa variabile
(es. molto freddo confrontato con una temperatura di 0°C).
2.
Un metodo di quantificazione di variabili linguistiche (es. u1 potrebbe
avere un numero finito di termini linguistici ad esso associati: basso, alto,
medio). Ogni termine linguistico è associato ad un insieme fuzzy. Dato un
ingresso numerico, il valore assunto dalla funzione di appartenenza
40
Capitolo 3– Tecniche di clustering
dell’insieme fuzzy stabilisce quanto sia attivato il termine linguistico ad esso
associato.
3.
Connessioni logiche tra variabili linguistiche (and, or,...).
4.
Metodi di valutazione di implicazioni del tipo “IF A THEN B” e metodi
di estrapolazione di un risultato numerico nella situazione di attivazione di più
regole.
Il fuzzificatore mappa i valori numerici negli insiemi fuzzy: questo si rende
necessario perché le regole sono attivate in termini di variabili linguistiche
che hanno degli insiemi fuzzy associati ad esse.
Il motore inferenziale mappa insiemi fuzzy su insiemi fuzzy. Come gli uomini
usano diversi tipi di procedure inferenziali per capire concetti o prendere
decisioni, così esistono differenti procedure inferenziali fuzzy, ma solo poche
sono usate nelle applicazioni ingegneristiche.
Il defuzzificatore mappa le uscite fuzzy in valori numerici.
3.2.1- Introduzione alla logica fuzzy
La usuale logica bivalente (di tipo Cartesiano) si basa su una visione del
mondo in cui tutto è o bianco o nero senza altre possibilità. Il mondo descritto
dalla logica fuzzy, invece, è ricco di sfumature ed il bianco ed il nero non
sono altro che due casi particolari.
Il linguaggio naturale abbonda di termini e concetti sfumati ed imprecisi, del
tipo “Ulisse è alto”, oppure “Oggi è molto freddo”.
Queste proposizioni sono difficili da tradurre in un linguaggio più preciso
senza perdere parte del valore semantico, per esempio “Ulisse è alto 185
cm” non asserisce precisamente che è alto, d’altro canto la frase “Ulisse ha
una deviazione standard di 1.3 cm dall’altezza media dei maschi della sua
età e del suo contesto sociale” non è immediatamente comprensibile ed irta
di difficoltà: un uomo con deviazione standard 1.9 cm è alto? Come si
definisce l’appartenenza di Ulisse all’insieme delle persone alte?
41
Capitolo 3– Tecniche di clustering
Si può essere d’accordo sul fatto che la vaghezza è un ostacolo alla
chiarezza, ma solo i tradizionalisti più ostinati possono sostenere che non si
perderebbe ricchezza di significato togliendo dal linguaggio asserzioni del
tipo “Ulisse è alto”. Eppure è ciò che succede quando si tenta di tradurre il
linguaggio umano nella logica classica.
Questa perdita non si avverte nella costruzione di un programma contabile,
ma quando si vogliono effettuare delle ricerche basate sul linguaggio
naturale: nel progettare ad esempio un programma di diagnostica medica, la
decisione su una particolare dose di medicinale è legata alla relativa
robustezza del paziente ed al suo stato patologico, piuttosto che ad un rigido
rapporto età/altezza/peso. Ben diverso sarà il problema da me trattato, gli
essudati diabetici, che o lo sono oppure non lo sono (perciò, come si vedrà
nel capitolo seguente, la mia scelta di classificatore è cascata su quello
basato sulle SVM).
I sistemi fuzzy affrontano i dati e la loro manipolazione con maggiore
flessibilità rispetto ai sistemi tradizionali. La logica bivalente (o classica) si
occupa solo di ciò che è completamente vero e di conseguenza di ciò che è
completamente falso, la logica fuzzy invece estende il suo interesse anche a
ciò che non è completamente vero, a ciò che è verosimile od incerto, in una
parola a tutto ciò che è fuzzy (sfumato).
3.2.2- Concetti di base
Nel 1965 Lofti A. Zadeh pubblicò “Fuzzy Sets” [5]: in tale articolo egli
descrisse la matematica degli insiemi fuzzy e da questa derivò la logica
fuzzy. La sua teoria proponeva che la funzione di appartenenza (o del vero e
falso) operasse nell’intero campo reale da 0 a 1 senza limitarsi ai valori
estremi, concetto su cui si fonda invece la logica classica.
La nozione centrale dei sistemi fuzzy considera i valori di verità (logica fuzzy)
o di appartenenza (insiemi fuzzy) estesi a tutto il campo reale [0,1], con 0 che
rappresenta l’assoluta falsità ed 1 l’assoluta verità.
42
Capitolo 3– Tecniche di clustering
Consideriamo per esempio la proposizione “Ulisse è vecchio”: se Ulisse ha
80 anni possiamo considerare di assegnare alla proposizione un valore di
verità di 0.8. La proposizione si può anche tradurre, nella terminologia dei
fuzzy set, con “Ulisse appartiene in una certa misura (0.8) all’insieme delle
persone vecchie”, o, in forma simbolica,
mVECCHIO(Ulisse) = 0.8
dove m è la funzione di appartenenza nell’insieme fuzzy degli uomini vecchi:
ciò è in netta contraddizione con la logica bivalente dove “o Ulisse è vecchio
o è non-vecchio” e non vi è una terza possibilità. E’ importante sottolineare
anche il rapporto che esiste tra sistemi fuzzy e probabilità: ambedue operano
sullo stesso campo reale ed in prima istanza ambedue hanno gli stessi valori;
ma esiste una sostanziale differenza, cioè l’approccio probabilistico
considera la proposizione “vi è una probabilità dell’80% che Ulisse sia
vecchio”, concludendo comunque che Ulisse o è vecchio o è non-vecchio,
mentre la semantica fuzzy, al contrario, afferma che Ulisse è più vecchio che
non-vecchio e che comunque appartiene, in una certa misura, ad ambedue
gli insiemi.
3.2.3- Insiemi fuzzy
Mentre in un insieme bivalente X l’appartenenza è descritta da un indicatore
I(x) che può assumere soltanto due valori (l’elemento x appartiene (1) o no
(0) all’insieme X), in un insieme fuzzy la stessa è descritta da una funzione di
appartenenza m(x) il cui valore va da 0 a 1 e può assumere ogni valore
intermedio: 0≤m(x)≤1. Già si intravede la natura estensiva della teoria degli
insiemi fuzzy che non rinnega totalmente la teoria degli insiemi bivalenti, ma
la comprende come proprio caso particolare.
Poiché un certo elemento x appartiene all’insieme X in una certa misura, ne
consegue che lo stesso non appartiene all’insieme in una certa misura.
L’appartenenza e la non-appartenenza all’insieme può non rappresentare
l’insieme vuoto (come invece sostiene la teoria degli insiemi bivalenti); alla
43
Capitolo 3– Tecniche di clustering
stessa maniera l’appartenenza o la non-appartenenza all’insieme può non
rappresentare l’insieme universo.
Un insieme fuzzy F definito in un universo del discorso U può essere
rappresentato da un insieme di coppie x e funzione di appartenenza:
F={(x,m(x))|x∈U}.
3.2.3.1- Variabili linguistiche
Sia u una variabile linguistica (per esempio una temperatura). Il valore
numerico della variabile linguistica u si indica simbolicamente con x, dove
x∈U. Una variabile linguistica viene decomposta in una serie di termini T(u)
che coprono tutto l’universo del discorso.
Ad ogni termine corrisponde un insieme fuzzy ed una funzione di
appartenenza. Noto il valore numerico x è possibile ricavare il grado di
appartenenza a ciascun insieme e di conseguenza al termine della variabile
linguistica ad esso associato.
Esempio: sia temperatura (u) una varibile linguistica. Tale variabile può
essere decomposta in una serie di termini T(temperatura)={molto freddo,
freddo, okay, caldo, molto caldo}, dove ciascun termine è caratterizzato da
un insieme fuzzy nell’universo del discorso U=[-10°C,45°C].
Si potrebbe interpretare molto freddo come una temperatura al di sotto dei
0°C, freddo come una temperatura intorno ai 8°C, okay una temperatura
intorno ai 20°C, caldo una temperatura intorno ai 30°C e molto caldo una
temperatura superiore ai 40°C (vedi fig.3.2).
44
Capitolo 3– Tecniche di clustering
fig.3.2. Funzione di appartenenza per temperatura.
Sia x=12°C, questo valore numerico rientra negli insiemi fuzzy temperatura
freddo e temperatura okay, con differenti gradi di appartenenza; questo
comporta che i due termini linguistici ad essi associati vengono “attivati”
(dall’ingresso x) di una quantità proporzionale al grado di appartenenza. Se
si disponesse di un SLF che sfrutta regole del tipo 1) IF temperatura freddo
THEN... 2) IF temperatura okay THEN... sollecitando con x=12°C verrebbero
attivate entrambe le regole(in base alla funzione di appartenenza): in base ad
esse il SLF dovrebbe essere in grado di fornire un’uscita adeguata.
3.2.3.2- Operazioni su insiemi ordinari ed insiemi fuzzy
Per introdurre le operazioni sugli insiemi fuzzy, conviene definire prima quelle
sugli insiemi ordinari facendo uso della funzione appartenenza.
Siano A e B due insiemi ordinari quindi:
mA(x) = 1 se x∈A ∧ mA(x) = 0 se x∉A;
mB(x) = 1 se x∈B ∧ mB(x) = 0 se x∉B;
si noti che, parlando di insiemi ordinari, le funzioni di appartenenza possono
valere solo 0 oppure 1.
45
Capitolo 3– Tecniche di clustering
L’unione di A e B, indicata con A∪B, contiene tutti gli elementi di A e tutti
quelli di B, quindi mA∪B(x)=1 se x∈A ∨ se x∈B; l’intersezione di A e B indicata
con A∩B contiene tutti gli elementi che sono simultaneamente in A e B,
quindi mA∩B(x)=1
se x∈A ∧ se x∈B. Sia Ā il complemento di A, esso
contiene tutti gli elementi che non appartengono ad A cioè mĀ(x)=1 se x∉A ∧
mĀ(x)=0 se x∈A.
Da quanto sopra si può verificare che:
A∪B⇒ mA∪B(x)=max[mA(x), mB(x)]
(1a)
A∩B⇒ mA∩B(x)=min[mA(x), mB(x)]
(1b)
Ā⇒ mĀ(x)=1- mA(x)
(1c)
Mentre un insieme ordinario può essere definito enumerando tutti gli elementi
che lo compongono, oppure dando una descrizione dei suoi elementi o
tramite la funzione di appartenenza, un insieme fuzzy è definito soltanto
tramite quest’ultima. Intersezione, unione e complemento sono perciò così
definiti (formule motivate dalle (1a), (1b), (1c)):
mA∪B(x)=max[mA(x), mB(x)]
(2a)
mA∩B(x)=min[mA(x), mB(x)]
(2b)
mĀ(x)=1- mA(x)
(2c)
Si noti che in questa definizione non si pone alcun vincolo alle funzioni di
appartenenza; esse possono assumere qualsiasi valore compreso tra 0 ed 1.
Una conseguenza di questo è che le leggi aristoteliche:
Legge di non Contraddizione: A∪Ā=U
Legge del Terzo Escluso:
A∩Ā=∅
46
Capitolo 3– Tecniche di clustering
non sono rispettate perché considerando un x: mA(x)=0.5 allora mĀ(x)=1mA(x)=0.5 e questo è in contraddizione con le due leggi aristoteliche.
Il max e il min non sono gli unici operatori che si possono usare per
modellare l’unione e l’intersezione fuzzy; lo stesso Zadeh nella sua prima
pubblicazione usò operatori diversi:
Unione fuzzy (massimo e somma algebrica)
mA∪B(x)=mA(x)+mB(x)- mA(x)mB(x)
(3a)
Intersezione fuzzy (minimo e prodotto algebrico)
mA∩B(x)=mA(x)mB(x)
(3b)
Successivamente furono introdotti altri operatori, definiti su base assiomatica,
l’operatore t-conorma per l’unione fuzzy, noto anche come s-norma (indicato
simbolicamente
⊕)
con
simbolicamente con
e
la
t-norma
per
l’intersezione
(indicata
):
mA∪B(x)=mA(x)⊕mB(x)
(4a)
mA∩B(x)=mA(x) mB(x)
(4b)
Confrontando le (2) e (3) con le (4) si osserva che:
•
max e somma algebrica sono t-conorme ⊕
•
min e prodotto algebrico sono t-norme
3.2.4- Relazioni e composizioni nello stesso spazio prodotto
Mentre una relazione su insiemi ordinari rappresenta la presenza o l’assenza
di associazioni, interazioni o interconnessione tra elementi di due o più
insiemi, nel campo fuzzy ne rappresenta il grado di presenza o assenza.
Le relazioni fuzzy giocano un ruolo fondamentale nei sistemi logici fuzzy.
47
Capitolo 3– Tecniche di clustering
Siano U e V due universi del discorso. Una relazione fuzzy, R(U,V) è un
sottoinsieme fuzzy nello spazio prodotto UxV ed è caratterizzato dalla
funzione di appartenenza mR(x,y) dove x∈U e y∈V, cioè R(U,V)={((x,y),
mR(x,y))|(x,y)∈UxV}.
Siano R(x,y) ed S(x,y) (R e S per brevità) due relazioni fuzzy nello stesso
spazio prodotto UxV. L’intersezione e l’unione di R ed S che sono
composizioni delle due relazioni sono definite come:
mR∪S(x,y)=mR(x,y) mS(x,y)
(5a)
mR∩S(x,y)=mR(x,y)⊕mS(x,y)
(5b)
3.2.5- Relazioni e composizioni in spazi prodotto differenti
Siano P(U,V) e Q(V,W) due relazioni fuzzy definite su due spazi prodotto
differenti, la composizione di queste due relazioni è così indicata:
R(U,W)=P(U,V)°Q(V,W)
(6)
ed è definita su un sottoinsieme di R(U,W) di UxW tale che (x,w)∈R se e solo
se ∃ almeno un y∈V|(x,y)∈P ∧ (y,w)∈Q.
Associate con R ed S ci sono le rispettive funzioni di appartenenza, le quali
permettono di introdurre la formula matematica per determinare mR°S(x,y).
Prima di introdurla vale la pena di dare la definizione per insiemi ordinari.
Definizione: La composizione max-min di relazioni P(U,V) e Q(V,W) è definita
per mezzo della funzione di appartenenza mP°Q(x,z) dove
mP°Q(x,z)={(x,z),maxy[min(mP(x,y),mQ(y,z))]}
(7)
La composizione max-prodotto di relazioni P(U,V) e Q(V,W) è definita per
mezzo della funzione di appartenenza mPxQ(x,z) dove
48
Capitolo 3– Tecniche di clustering
mPxQ(x,z)={(x,z),maxy[mP(x,y),mQ(y,z)]}
(8)
Dopo aver introdotto la definizione per gli insiemi ordinari si consideri la
definizione per gli insiemi fuzzy, la composizione sup-star di R ed S è definita
come:
mR°S(x,z)=supy∈V[mR(x,y) mS(y,z)]
(9)
che è motivata dalle (7), (8) e (4).
Si potrebbe osservare che, a differenza del caso ordinario nel quale l’uso
della (7) o della (8) porta agli stessi risultati, lo stesso non vale nel caso
fuzzy. Questa è la maggiore differenza tra composizioni fuzzy e composizioni
ordinarie.
Consideriamo adesso il caso particolare in cui la relazione R sia un insieme
fuzzy, allora mR(x,y) diventa mR(x). Quindi V=U e si ha:
supy∈V[mR(x,y) mS(y,z)]= supx∈U[mR(x) mS(x,z)] che è funzione solo di z;
questo ci permette di semplificare la notazione mR°S(x,z) in mR°S(z), così
quando R è un insieme fuzzy:
mR°S(z)=supx∈U[mR(x) mS(x,z)]
(10)
3.2.6- Logica fuzzy
La logica proposizionale tradizionale introduce la regola inferenziale Modus
Ponens:
Modus Ponens—Premessa 1: “x è A”; Premessa 2: “IF x è A THEN y è B”;
Conseguenza: “y è B”. Il Modus Ponens è associato con l’implicazione “A
implica B” [A→B]. In termini di proposizioni p e q, il Modus Ponens è
espresso come (p∧(p→q))→q.
Estendendo i concetti della logica tradizionale alla logica fuzzy, l’asserzione
“IF u è A, THEN v è B”, dove u∈U e v∈V, ha una funzione di appartenenza
49
Capitolo 3– Tecniche di clustering
mA→B(x,y) ∈[0,1] che misura il grado di verità della relazione di implicazione
tra x e y e che può essere espressa così:
mA→B(x,y)=1-min[mA(x),1-mB(y)]
mA→B(x,y)=max[1-mA(x),mB(y)].
Nella logica fuzzy il Modus Ponens è esteso al Modus Ponens
Generalizzato :
Modus Ponens Generalizzato—Premessa 1: “u è A*”; Premessa 2: “IF u è A
THEN v è B”; Conseguenza: “v è B*”.
Confrontando i due enunciati si vede come nel secondo caso l’insieme fuzzy
A* non debba essere necessariamente uguale all’antecedente della regola
IF-THEN (l’insieme fuzzy A) e come l’insieme fuzzy B* non debba essere
uguale al conseguente B.
Esempio: si consideri la regola “IF un uomo è basso, THEN non sarà mai un
bravo giocatore professionista di basket”. Qui A è l’insieme uomini bassi e
l’insieme fuzzy B è bravi giocatori professionisti di basket. Prendiamo in
esame una Premessa 1 in cui A* è la variabile linguistica uomini sotto 1.80 m
di altezza: quindi A(A*, ma A è simile ad A*. Si può allora dedurre che B*
sarà un insieme fuzzy simile a B, ma comunque diverso. Per esempio, se lo
volessimo etichettare con un attributo linguistico potrebbe essere l’insieme
scarsi giocatori professionisti di basket.
Riepilogando, nella logica fuzzy la regola IF-THEN è attivata quando c’è un
grado di similarità non nullo tra la premessa e l’antecedente della regola e il
risultato dell’attivazione è una conseguenza che ha un grado di similarità non
nulla con il conseguente della regola.
Quindi il Modus Ponens Generalizzato non è altro che una composizione
fuzzy dove la prima relazione fuzzy è sostituita dall’insieme fuzzy A*. Allora la
mB*(y) si ottiene dalla formula:
mB*(y)=supx∈U[mA*(x)
mA→B(x,y)].
50
Capitolo 3– Tecniche di clustering
3.2.7- Ancora sui Sistemi Logici Fuzzy
A questo punto si possono discutere più approfonditamente i quattro
elementi che compongono il SLF di fig.3.1; lo scopo di questa sezione è
quello di fornire le formule matematiche che legano gli ingressi all’uscita del
sistema.
3.2.7.A- Regole
Le regole fuzzy sono una collezione di regole del tipo IF-THEN che possono
essere espresse così:
R(l):
IF u1 è Fl1 e u2 è Fl2 e ... up è Flp
THEN v è Gl
(11)
dove l=1,2,...,M, Fli e Gl sono insiemi fuzzy in Ui⊂R e V⊂R (R è l’insieme dei
numeri reali), u=col(u1, u2, ... ,up)∈U1xU2x ... xUp e v∈V. u e v sono variabili
linguistiche ed i loro valori numerici sono rispettivamente x∈U e y∈V. Questa
regola presenta un antecedente multiplo che equivale a considerare un
sistema a più ingressi. Se il numero degli ingressi è p ed n è il numero di
termini linguistici associati ad ognuno di essi, il numero di regole necessarie
sarà sempre minore o uguale al prodotto pn. Nel caso di numero massimo di
regole, l’antecedente multiplo è una combinazione logica di ∧ delle singole
variabili linguistiche e la (11) ne è la spiegazione formale. Nei casi in cui il
numero di regole è minore si parla di insieme di regole incompleto, ma ci si
può sempre ricondurre formalmente alla (11).
3.2.7.B- Motore inferenziale fuzzy
Il motore inferenziale fuzzy sfrutta i principi della logica fuzzy per combinare
le regole IF-THEN al fine di ottenere una mappatura dall’insieme fuzzy di
ingresso U=U1xU2x ... xUp nell’insieme fuzzy di uscita V. Ciascuna regola
viene interpretata come un’implicazione fuzzy. Facendo riferimento alla (11),
sia Fl1xFl2x ... xFlp=A e Gl=B allora R(l): Fl1xFl2x ... xFlp→Gl=A→B.
51
Capitolo 3– Tecniche di clustering
La mappatura del motore inferenziale avviene per mezzo dalla mA→B(x,y)
dove adesso x è un vettore perchè le regole hanno un antecedente multiplo.
Quindi:
mR(l)(x,y)= mA→B(x,y)=mF1(l)(x1) ... mFp(l)(xp) mG(l)(y)
(12)
Si è implicitamente assunto che gli antecedenti siano connessi tramite
operatori AND (∧), da qui l’uso della t-norma.
L’input p-dimensionale per R(l) si ottiene dall’insieme fuzzy Ax la cui funzione
di appartenenza è data da:
mAx(x)=mx1(x1) ... mxp(xp)
(13)
dove Xk⊂Uk (k=1,2,...,p) sono insiemi fuzzy che descrivono l’input.
Ogni regola R(l) determina un insieme fuzzy di uscita B(l)=Ax°R(l) la cui
funzione di appartenenza risulta essere:
mB(l)(y)=mAx°R(l)=supx∈U[mAx(x),mA→B(x,y)]
(14)
Quest’equazione è la relazione ingresso-uscita tra l’insieme fuzzy che attiva
una regola del motore inferenziale e l’insieme fuzzy di uscita del motore
stesso (vedi fig.3.1).
Ancora non è stato spiegato come ottenere un unico valore numerico di
uscita: questo processo avviene tramite la cosiddetta defuzzificazione di cui
si parlerà nel seguito. In realtà il processo di defuzzificazione avviene a
partire dalla funzione di appartenenza di un insieme fuzzy, mentre finora si è
solamente individuato un metodo per ottenere l’insieme fuzzy di uscita di una
regola. In un SLF le regole sono molte per cui l’eccitazione di un ingresso
può dar vita a più insiemi fuzzy (e quindi a molte funzioni di appartenenza) in
uscita
dal
motore
inferenziale.
Il passo successivo consiste nella
connessione delle regole. L’insieme fuzzy in uscita (in fig.3.1 prima del
blocco di defuzzificazione) B=Ax°[R(1), R(2),...,R(M)] si ottiene combinando i Bl
52
Capitolo 3– Tecniche di clustering
e quindi le funzioni membro ad esso associate mAx°R(l)(y) (questo processo è
noto come connessione delle regole).
3.2.7.C- Fuzzificazione
Il fuzzificatore mappa un punto x=col(x1,...,xn)∈U in un insieme fuzzy A* in U.
Il fuzzificatore più usato è il singleton fuzzifier:
mA*(x)=1 se x=x’;
mA*(x)=0 altrimenti;
L’uso del singleton elimina la presenza dell’operatore sup e semplifica molto i
meccanismi inferenziali:
mB(l)(y)=mAx°R(l)(y)=supx∈Ax[mAx(x),mA→B(x,y)]=mA→B(x’,y)
Ciò ha fatto la fortuna di questo fuzzificatore.
3.2.7.D- Defuzzificazione
E’ il processo inverso al precedente (la defuzzificazione), dato un insieme
fuzzy restituisce un valore numerico rappresentativo di quell’insieme.
Esistono molti criteri di defuzzificazione, ma non esiste nessun fondamento
scientifico per essi. Dal punto di vista ingegneristico un criterio di scelta può
consistere nella semplicità computazionale. Usando questo criterio i
defuzzificatori candidati sono:
Maximum Defuzzificator
Esaminando l’insieme fuzzy B viene scelto come uscita il valore di y per il
quale mB(y) è massima. Il difetto di questo metodo è che non tiene conto
della distribuzione della funzione di appartenenza.
Mean of Maxima Defuzzifier
Vengono trovati i massimi locali di mB(y) e l’uscita viene calcolata come
media di essi. Quando il massimo è soltanto uno, questo defuzzificatore
53
Capitolo 3– Tecniche di clustering
coincide con il Maximum Defuzzificator (ereditando i suoi difetti). Altro difetto
grave è che la media dei massimi potrebbe fornire un valore che cade in una
zona in cui la funzione di appartenenza è nulla e questo non ha alcun senso
da un punto di vista ingegneristico.
Centroid Defuzzifier
Il valore numerico scelto per l’uscita viene calcolato come “centro di massa”
dell’insieme fuzzy. Il centroide ŷ viene definito in termini matematici come
l’integrale sul supporto S di mB(y):
ŷ=[∫ ymB(y) dy]/[∫mB(y)]
3.2.8- Assegnazione dei valori alle funzioni di appartenenza
Dopo aver visto come realizzare un SLF rimane un problema da affrontare:
definire le funzioni di appartenenza degli insiemi fuzzy associati alle variabili
linguistiche.
In letteratura esistono molti metodi di assegnazione delle funzioni di
appartenenza; nel seguito sono elencati quelli più noti:
•
Metodo intuitivo
•
Metodo inferenziale
•
Reti neurali
•
Algoritmi genetici
•
Metodo induttivo
•
Metodi di partizione
3.3- Fuzzy C-Means (FCM)
Per sviluppare i metodi di classificazione fuzzy è necessario definire il
concetto di famiglia di insiemi fuzzy {Ai, i=1,2,...,c} come una c-partizione
fuzzy dell’universo del discorso X (che è il nostro insieme delle osservazioni).
Adesso ogni elemento di X può avere una parziale appartenenza a più di un
cluster. Si usa questa notazione:
54
Capitolo 3– Tecniche di clustering
uik=mAi(xk)∈[0,1]
(15)
con il vincolo
∑ci=1 uik=1
∀k=1,...,n
(16)
Anche adesso si impone l’assenza di classi vuote o coincidenti con l’insieme
universo X={x1,...,xn}; ciò è espresso mediante la (17)
0< ∑ci=1 uik <n
(17)
Poiché un elemento di X può avere una parziale appartenenza a più di un
cluster, si ha:
uik ∧ ujk ≠ 0
∀k
(18)
∀k
(19)
ed inoltre valgono
∨ci=1 mAi(xk) = 1
0<∑nk=1 mAi(xk)<n
∀i
(20)
Possiamo adesso definire lo spazio delle c-partizioni fuzzy in termini di
matrici di appartenenza:
Mfc={ U | uik∈[0,1], ∑ci=1 uik=1; 0<∑nk=1 uik<n }
(21)
Ogni matrice U definisce una partizione fuzzy nell’universo X dei dati.
55
Capitolo 3– Tecniche di clustering
Il principio su cui si basa lo FCM è la minimizzazione di un funzionale Jm,
legato alla somma degli errori quadratici medi, mediante un processo
iterativo che si arresta solo al di sotto di una certa soglia. La forma di questa
funzione criterio Jm è la seguente:
J(U;v)= ∑nk=1∑ci=1(uik)m’(dik)2
(22)
dove v=(v1,...,vc)∈Rcxm e vi∈Rm è il vettore del centro dell’i-esimo cluster.
Mentre
dik=⎟⎜xk-vi⎟⎜
(23)
è una distanza qualsiasi che soddisfa queste tre condizioni:
d12=d(x1,x2)
(24a)
d12=0⇒x1=x2
(24b)
d12=d21
(24c)
Il parametro m’ viene chiamato parametro fuzzificatore o esponente fuzzy.
Nella definizione di Dunn vale 2 e successivamente è stato esteso
all’intervallo [1,∞).
Questo parametro determina il grado di “sfumatura” che deve avere la
funzione di appartenenza al variare della distanza. Come si può vedere dalla
fig.3.3, per m’=1 si ottiene una partizione netta (quindi valori binari 0 oppure
1) e via via che m’ aumenta la partizione diventa sempre più sfumata.
56
Capitolo 3– Tecniche di clustering
fig. 3.3. Andamento della funzione di appartenenza al variare della distanza in funzione di m’.
Per minimizzare la (22) Bezdek sfruttò un teorema di cui si riporta solo
l’enunciato:
TEOREMA: Sia d() una distanza che rispetti le (24), m’∈(1,∞) ed X uno
spazio finito con n elementi partizionabile in c cluster. Si definiscono ∀K gli
insiemi
Ik={ i: 1 ≤ i ≤ c; dik=⎟⎜xk-vi⎟⎜=0}
Ĩk={1,2,...,c}-Ik
Allora (U,v)∈Mfc può essere un minimo globale per Jm solo se:
Ik=∅⇒uik=1/∑cj=1(dik/djk)2/(m’-1)
(25.a1)
Ik≠∅⇒uik=0 ∀i∈ Ĩk e ∑i∈Ĩk uik=1
(25.a2)
con
57
Capitolo 3– Tecniche di clustering
vi=∑nk=1(uik)m’xk / ∑nk=1(uik)m’
∀i
(25.b)
Osservazioni: Ik è l’insieme che raccoglie per ogni elemento di X gli indici
delle classi i cui centri vi coincidono proprio con xk, mentre Ĩk è il suo
complementare.
In questo teorema non viene specificata alcun tipo di norma. Si può però
osservare che, scegliendo m’=2 ed usando una norma euclidea, le formule si
semplificano molto.
Da questo teorema Bezdek ideò questo
Algoritmo Fuzzy c-Means (FCM)
(a)
Fissare c, 2≤ c ≤n; scegliere una norma in Rm; si fissa m’,1≤ m’ ≤∞.
Si inizializza U(0)∈Mfc. Poi al passo l, l=0,1,...,:
(b)
Calcolare i c centri dei cluster {vi(l)} mediante la (25b) e la U(l).
(c)
Calcolare la U(l+1) usando la (25.a1) e {vi(l)}.
(d)
Confrontare la U(l) con U(l+1) mediante una norma matriciale opportunamente scelta:
Se (⎟⎜U(l+1)-U(l)⎟⎜≤ εL)
STOP;
Altrimenti
l = l+1 e tornare a (b) ;
◊
L’algoritmo richiede l’inizializzazione di U(0), ma quale è la scelta opportuna
da fare?
Essendo questo un algoritmo iterativo, scegliere una U(0) vicina alla soluzione
significa velocizzarne la convergenza. In generale, avere anche una vaga
idea di quale sia la soluzione non è facile per cui l’inizializzazione viene fatta
fissando casualmente la U(0). Una proposta interessante in tal senso è quella
di Bezdek:
58
Capitolo 3– Tecniche di clustering
•
fissare una U∈Mfc: uij=1/c (è una partizione in cui ogni elemento
appartiene a tutti i cluster con lo stesso grado).
•
fissare una W∈Mc qualsiasi (W è in questo caso una partizione netta).
•
fissare α=(1-√2/2) e β=1-α
•
imporre U(0)=αU+βW
Questa scelta di U(0) è motivata da un parametro di cluster validity, F: la
scelta fatta per α e β comporta che F(αU+βW)=(c+1)/2c ovvero il punto di
mezzo dell’intervallo [1/c,1], all’interno del quale stanno tutti i possibili valori
assunti da questo funzionale. Questa scelta di U(0) è una via di mezzo tra una
partizione U: uij=1/c (che esprime mancanza di aggregazione) ed una
partizione netta.
Nell’implementazione W viene scelto:
⎡1 0 0 ... 0 0 1 0 0 ... 0 0 ...⎤
0 1 0 ... 0 0 0 1 0 ... 0 0 ...
W = .........................................
0 0 0 ... 1 0 0 0 0 ... 1 0 ...
⎣ 0 0 0 ... 0 1 0 0 0 ... 0 1 ...⎦
che permette di ottenere la U(0) in questa forma:
⎡δ η η ... η η δ η η ... η η ...⎤
η δ η ... η η η δ η ... η η ...
U(0)= .........................................
η η η ... δ η η η η ... δ η ...
⎣ η η η ... η δ η η η ... η δ ...⎦
dove:
δ = α(1/c)+β
η = α(1/c)
59
Capitolo 3– Tecniche di clustering
Si può osservare che una scelta di questo tipo non prende assolutamente in
considerazione la distribuzione dei dati da clusterizzare. Nonostante ciò
facendo una serie di test si è visto che:
1. la convergenza è migliore rispetto ad un’inizializzazione totalmente
casuale;
2. quando si introducono criteri di cluster validity per predire il numero di
cluster si ottengono i risultati migliori: non solo, fare una scelta diversa
spesso porta a risultati errati.
3.4- Statistical Learning Theory
3.4.1- Introduzione
La Statistical Learning Theory fu introdotta alla fine degli anni sessanta: fino
agli anni novanta fu puramente una analisi teorica del problema della stima di
una funzione a partire da una collezione di dati forniti. A metà degli anni
novanta furono proposti nuovi algoritmi learning (chiamati support vector
machine) basati su tale teoria, e che fornivano un pratico metodo per stimare
funzioni multidimensionali.
Si deve soprattutto a Vapnik (nel 1995 e nel 1998) l’approfondimento di tale
Statistical Learning Theory.
3.4.2- Un limite alle performance di una Pattern Recognition Machine
In questo paragrafo verranno analizzati i limiti che governano la relazione tra
la qualità di una learning machine e le sue performance. La teoria scaturisce
da considerazioni su quali circostanze e quanto velocemente la media di
alcune quantità empiriche converge uniformemente, incrementando il
numero di dati, alla vera media (che dovrebbe essere calcolata su infiniti
dati).
60
Capitolo 3– Tecniche di clustering
Supponiamo di avere l osservazioni. Ad ogni osservazione è associata una
coppia (xi, yi), dove il vettore xi∈Rn , i=1,...,l, e yi rappresenta la “truth”
(verità) dataci da una sorgente fidata.
Ad esempio, in un problema di riconoscimento di un albero in una immagine,
xi potrebbe essere un vettore contenente i valori dei pixel, mentre yi varrebbe
1 se l’immagine contiene un albero, -1 altrimenti.
Assumiamo ora che esista una qualche distribuzione di probabilità
sconosciuta P(x,y) da cui sono estratti questi dati (i dati sono supposti i.i.d.,
cioè indipendentemente estratti e identicamente distribuiti).
Supponiamo, inoltre, di avere una macchina il cui compito è di imparare la
mappatura xi→yi. La macchina è definita da un insieme di possibili
mappature x→f(x,α), dove le stesse funzioni f(x,α) sono etichettate dal
parametro regolabile α. In più, si assume che la macchina sia deterministica:
per un dato ingresso x, scelto α, darà sempre la stessa uscita f(x,α). Una
particolare scelta di α genera quella che chiameremo una “trained machine”
(macchina esercitata).
Il valor medio dell’errore di test per una trained machine è perciò:
R(α)=∫(1/2)|y - f(x,α)| dP(x,y)
(26)
Notiamo che, quando esiste una densità p(x,y), dP(x,y) potrebbe essere
scritta come p(x,y)dxdy. Questa è una ottima via per scrivere la vera media
dell’errore, ma purtroppo abbiamo una stima di che cosa sia P(x,y).
La quantità R(α) è chiamata rischio medio o rischio teorico o soltanto rischio.
Il rischio empirico Remp(α) è definito come l’andamento medio dell’errore
misurato sull’insieme di training (per un numero fisso e finito di osservazioni):
Remp(α)=(1/2l)∑li=1 |yi – f(xi,α)|
(27)
61
Capitolo 3– Tecniche di clustering
E’ da notare che nella (27) non appare alcuna distribuzione di probabilità.
Remp(α) è un numero fisso per una particolare scelta di α e per un particolare
insieme di training {xi,yi}.
La teoria della convergenza uniforme in probabilità, sviluppata da Vapnik e
Chervonenkis, fornisce anche un limite alla deviazione del rischio empirico
dal rischio teorico; fissato η con 0≤η≤1 vale la seguente disuguaglianza:
R(α) ≤ Remp(α) + {(1/l)[h(log(2l/h)+1)-log(η/4)]}1/2
(28)
dove h è un intero non negativo chiamato la dimensione VapnikChervonenkis (VC). Il secondo termine sulla destra è chiamato la “VC
confidence”.
Nella (28) notiamo tre punti chiave: primo, questo limite superiore è
indipendente da P(x,y), sottolineando soltanto che sia i dati di training che i
dati di test siano estratti indipendentemente secondo qualche P(x,y);
secondo, solitamente non è possibile calcolare il lato sinistro della
disuguaglianza; terzo, se conosciamo h, possiamo facilmente calcolare il lato
destro della disuguaglianza. Così, date parecchie differenti learning machine
(nota che “learning machine” è soltanto un altro nome per una famiglia di
funzioni f(x,α)) e scelto un fisso, sufficientemente piccolo η, prendendo
quella machine che minimizza il lato destro della (28), abbiamo scelto quella
macchina che dà il più basso limite superiore al rischio teorico. Questo è in
principio il metodo per scegliere una learning machine per un dato compito,
ed è l’idea essenziale per minimizzare il rischio strutturale (vedi paragrafi
seguenti).
3.4.3- La dimensione VC
La dimensione VC è una proprietà di un insieme di funzioni {f(α)} (in seguito,
userò α come un generico insieme di parametri: una particolare scelta di α
specifica una particolare funzione) e che possiamo definire per varie classi di
62
Capitolo 3– Tecniche di clustering
funzioni f. Nella mia trattazione considererò soltanto funzioni che
corrispondono al caso di pattern recognition binario, poiché nel mio progetto
di tesi ho utilizzato un classificatore binario: così si ha f(x,α)∈{-1,1} ∀x,α.
Ora, se un dato insieme di l punti può essere etichettato in tutti i 2l modi
possibili, e per ogni etichettamento, può essere trovato un membro
dell’insieme {f(α)} che assegna correttamente quelle etichette, diciamo che
quell’insieme di punti è shattered (letteralmente, scomposto, separato) da
quell’insieme di funzioni. La dimensione VC per l’insieme di funzioni {f(α)} è
definito come il numero massimo di punti di training che possono essere
separati da {f(α)}. Notiamo infine che, se la dimensione VC è h, esisterà
almeno un insieme di h punti che può essere separato, ma in generale non
sarà vero che ogni insieme di h punti può essere separato.
3.4.4- Punti separati con iperpiani orientati in Rn
Supponiamo che i dati appartengano allo spazio R2 e l’insieme {f(α)} consista
di linee rette orientate, cosicché per una certa linea, tutti i punti da un lato
siano assegnati alla classe 1 e tutti i punti dall’altro lato alla classe -1.
L’orientamento è mostrata in fig.3.4 con una freccia, specificando da quale
lato della linea i punti devono essere assegnati alla classe 1.
2
fig.3.4. Tre punti in R , separati da linee orientate.
63
Capitolo 3– Tecniche di clustering
Mentre è possibile trovare tre punti che possono essere separati da questo
insieme di funzioni, non è possibile trovarne quattro. Perciò la dimensione
VC dell’insieme di rette orientate in R2 è tre.
Consideriamo ora degli iperpiani in Rn. Il seguente teorema potrà esserci
utile:
TEOREMA: Consideriamo alcuni insiemi di m punti in Rn. Scegliamo
qualcuno di tali punti come origine. Gli m punti possono essere separati da
iperpiani orientati se e solo se i vettori posizione dei rimanenti punti sono
linearmente indipendenti.
COROLLARIO: La dimensione VC di un insieme di iperpiani orientati in Rn è
n+1, poiché possiamo sempre scegliere n+1 punti e poi sceglierne uno come
origine, cosicché i vettori posizione dei rimanenti n punti siano linearmente
indipendenti, ma non possiamo mai scegliere n+2 di tali punti (poiché n+1
vettori in Rn non possono essere linearmente indipendenti).
3.4.5- La dimensione VC e il numero di parametri
LA dimensione VC dà così concretezza al concetto di capacità di un dato
insieme di funzioni. Intuitivamente chiunque potrebbe essere indotto ad
aspettarsi che learning machine con molti parametri avrebbero una
dimensione VC grande, mentre learning machine con pochi parametri
avrebbero una dimensione VC piccola. C’è però un impressionante
controesempio a ciò dovuto a E.Levin e J.S.Denker: una learning machine
con appena un parametro, ma con la dimensione VC infinita (una famiglia di
classificatori è detta di avere dimensione VC infinita se può separare l punti,
indipendentemente da quanto è grande l).
Definiamo la funzione gradino θ(x), x∈R: {θ(x)=1 ∀x>0; θ(x)=-1 ∀x≤0}.
Consideriamo la famiglia di funzioni ad un parametro definita da
64
Capitolo 3– Tecniche di clustering
f(x,α) = θ(sin(αx)),
x,α∈R
(29)
Possiamo scegliere alcuni numeri l e trovare l punti che possono essere
separati. Possiamo scegliere punti come:
xi=10-i,
i=1,...,l
(30)
Possiamo scegliere le etichette a piacere:
y1,...,yl,
yi∈{-1,1}
(31)
f(α) fornisce tali etichette se scegliamo α nel seguente modo:
α = π(1+∑li=1[(1-yi)10i/2])
(32)
La dimensione VC di questa machine è infinito.
Stranamente, sebbene possiamo separare un numero arbitrariamente
grande di punti, possiamo trovare appena quattro punti che non possono
essere separati: essi devono semplicemente essere equi-spaziati ed avere
l’etichette come in fig.3.5. Ciò può essere visto come segue: scriviamo la
fase in x1 come φ1=2nπ+δ. Così la scelta dell’etichetta y1=1 richiede 0<δ<π.
La fase in x2, mod2π, è 2δ; così y2=1⇒0<δ<π/2. Similmente, il punto x3 forza
δ>π/3. Infine x4, π/3<δ<π/2 implica che f(x4,α)=-1, contrariamente all’etichetta
assegnata.
fig.3.5. Quattro punti che non possono essere separati da θ(sin(αx)), malgrado una dimensione VC
infinita.
65
Capitolo 3– Tecniche di clustering
3.4.6- Minimizzare il limite minimizzando h
La fig.3.6 mostra come il secondo termine sul lato destro della (28) vari con
h, data una scelta del 95% di livello di confidenza (η=0.05) e assumendo un
campione di training di grandezza 10000. La VC confidence è una funzione
di h monotona crescente. Ciò è vero per ogni valore di l.
fig.3.6. VC confidence è monotona in h.
Date alcune selezioni di learning machine il cui rischio empirico è zero,
vogliamo scegliere quella learning machine a cui è associato un insieme di
funzioni che ha dimensione VC minima. Ciò ci condurrà ad un limite
superiore migliore al rischio teorico.
In altre parole vogliamo che il lato sinistro della (28) sia grande il più
possibile, mentre vogliamo che il lato destro sia il più piccolo possibile. Perciò
66
Capitolo 3– Tecniche di clustering
vogliamo una famiglia di classificatori che dia il peggior possibile rischio
teorico di 0.5, un rischio empirico pari a zero, e la cui dimensione VC sia
semplice da calcolare e sia minore di l. Un esempio è il seguente, il
cosiddetto “notebook classifier”. Questo classificatore consiste di un
notebook con abbastanza spazio per annotare le classi di m osservazioni di
training, dove m ≤ l. Supponiamo inoltre che i dati abbiano la stessa quantità
di esempi positivi (y=1) e esempi negativi (y=-1) e che i campioni siano scelti
casualmente. Il classificatore notebook avrà rischio empirico zero per m
osservazioni; 0.5 errore di training per tutte le seguenti osservazioni; 0.5
rischio teorico; dimensione VC h = m. Sostituendo questi valori nella (28), il
limite diventa:
(m/4l) ≤ ln(2l/m)+1-(1/m)ln(η/4)
(33)
che vale ∀η se
f(z)=(z/2)exp((z/4)-1) ≤ 1,
z=(m/l),
0≤ z ≤ 1
(34)
la quale è vera, poiché f(z) è monotona crescente con f(z=1)=0.236.
3.4.7- Minimizzazione del rischio strutturale
Parlerò ora del principio di minimizzazione del rischio strutturale (SRM).
Notiamo che il termine della VC confidence nella disuguaglianza (28)
dipende dalla classe di funzioni scelta, mentre il rischio empirico e il rischio
teorico dipendono da una particolare funzione scelta con la procedura di
training. Ci piacerebbe trovare quel sottoinsieme dell’insieme di funzioni
scelto, tale che il limite del rischio per quel sottoinsieme sia minimizzato. A tal
scopo introduciamo una “struttura” dividendo l’intera classe delle funzioni in
sottoinsiemi annidati (fig.3.7).
67
Capitolo 3– Tecniche di clustering
fig.3.7. Sottoinsiemi annidati di funzioni, ordinati secondo la dimensione VC.
Per ogni sottoinsieme, dobbiamo poter calcolare ciascun h o almeno
prendere un limite allo stesso h. SMR consiste nel trovare quel sottoinsieme
di funzioni che minimizza il limite del rischio teorico. Questo può essere fatto
semplicemente
esercitando
una
serie
di
macchine,
una
per
ogni
sottoinsieme, dove il fine del training per un dato sottoinsieme è
semplicemente minimizzare il rischio empirico. In seguito si considera quella
trained machine che ha la somma tra il rischio empirico e la VC confidence
minima rispetto alle altre.
3.5- Support Vector Machines Lineari
Le Support Vector Machines sono state sviluppate negli AT&T Bell
Laboratories da Vapnik e colleghi (Boser 1992, Guyon 1993, Cortes 1995,
Scholkopf 1995).
Dato il contesto industriale, la ricerca sulle SVM ha finora avuto una decisa
polarizzazione applicativa.
L’algoritmo Support Vector alla base delle SVM è, in realtà, una
generalizzazione dell’algoritmo Generalized Portrait sviluppato in Russia
(Vapnik e Lerner 1963, Vapnik e Chervonenkis 1964). E’ inquadrabile nella
Statistical Learning Theory, o teoria di Vapnik-Chervonenkis (Vapnik e
Chervonenkis 1974, Vapnik 1982 e 1995).
68
Capitolo 3– Tecniche di clustering
Essenzialmente, la teoria VC caratterizza le proprietà degli algoritmi di
apprendimento che permettono loro di generalizzare a dati nuovi elementi
appresi in precedenza.
3.5.1- Il caso separabile
Inizierò la mia trattazione sulle SVM con il caso più semplice: macchine
lineari addestrate su dati separabili.
Di nuovo, etichettiamo i dati di training {xi,yi}, i=1,...,l, yi∈{-1,1}, xi∈Rd.
Supponiamo di avere qualche iperpiano che separa gli esempi positivi da
quelli negativi (un iperpiano “separatore”). I punti x che giacciono
sull’iperpiano soddisfano l’equazione
w⋅x+b=0
dove w è la normale all’iperpiano, |b| /⎟⎜w⎟⎜ è la distanza perpendicolare
dall’iperpiano all’origine, e⎟⎜w⎟⎜ è la norma Euclidea di w. Sia inoltre d+ (d-) la
distanza più piccola dall’iperpiano separatore all’esempio positivo (negativo)
più vicino. Definiamo inoltre “margine” dell’iperpiano separatore la quantità
d++d- . Per il caso linearmente separabile, l’Algoritmo Support Vector
semplicemente cerca l’iperpiano separatore con il margine più grande. Ciò
può essere formulato come segue: supponiamo che tutti i dati di training
soddisfino i seguenti vincoli:
xi ⋅ w + b ≥ +1
per yi=+1
(35)
xi ⋅ w + b ≤ -1
per yi=-1
(36)
Le due disuguaglianze possono essere riunite nell’unica disuguaglianza :
69
Capitolo 3– Tecniche di clustering
yi (xi ⋅ w + b) – 1 ≥ 0
∀i
(37)
Consideriamo ora i punti per i quali vale l’uguaglianza nella (35). Questi punti
giacciono sull’iperpiano H1: xi ⋅ w + b = +1 con normale w e distanza
perpendicolare dall’origine |1-b|/⎟⎜w⎟⎜. Similmente i punti per i quali vale
l’uguaglianza nella (36) giacciono sull’iperpiano H2: xi ⋅ w + b = -1, con
normale ancora w e distanza perpendicolare dall’origine |-1-b|/⎟⎜w⎟⎜. Da qui,
d+=d-=1/⎟⎜w⎟⎜e il margine è semplicemente 2/⎟⎜w⎟⎜. Notiamo che H1 e H2
sono paralleli (hanno la stessa normale) e che nessun punto di training giace
tra loro. Ora non ci resta che cercare la coppia di iperpiani che danno il
margine massimo minimizzando ⎟⎜w⎟⎜2, soggetti ai vincoli (37).
Così ci aspettiamo che la soluzione per un tipico caso in due dimensioni
abbia la forma mostrata in fig.3.8. Quei punti di training per i quali vale
l’uguaglianza nella (37) e la cui eliminazione cambierebbe la soluzione
trovata sono chiamati support vectors; essi sono indicati in fig.3.8 con un
cerchio extra.
fig. 3.8. Iperpiani che separano linearmente per il caso separabile. I support vectors sono cerchiati due
volte.
Ora ci sposteremo su una formulazione di Lagrange del problema. Ci sono
due ragioni per fare ciò: primo, i vincoli (37) saranno sostituiti da vincoli sui
70
Capitolo 3– Tecniche di clustering
moltiplicatori di Lagrange stessi, che saranno più semplici da maneggiare.
Secondo, in questa riformulazione del problema, i dati di training saranno
rappresentati soltanto da prodotti puntuali (scalari) tra vettori.
Introduciamo quindi i moltiplicatori positivi di Lagrange αi, i=1,...,l, uno per
ognuno dei vincoli di disuguaglianza (37). Ricordo che la regola è che per
vincoli della forma ci ≥ 0, le equazioni di vincolo sono moltiplicate per
moltiplicatori positivi di Lagrange e sottratte dalla funzione obbiettivo per
formare la Lagrangiana. Per vincoli di uguglianza, i moltiplicatori di Lagrange
sono non costrittivi. Così si ha la Lagrangiana:
LP ≡ (1/2)⎟⎜w⎟⎜2 - ∑li=1[αiyi(xi ⋅ w + b)] + ∑li=1 αi
(38)
Dobbiamo ora minimizzare LP rispetto a w, b, e simultaneamente si richiede
che le derivate di LP rispetto a tutti gli αi tenda a zero, il tutto soggetto alle
restrizioni αi ≥ 0.
Possiamo inoltre equivalentemente risolvere il seguente problema duale:
massimizzare LP, soggetto ai vincoli che il gradiente di LP rispetto a w e b si
annulli e che αi ≥ 0.
La richiesta che il gradiente di LP rispetto a w e b tenda a zero ci dà le
seguenti condizioni:
w = ∑i αiyixi
(39)
∑i αiyi = 0
(40)
Possiamo così sostituire questi vincoli duali nell’equazione (38) per avere:
LD = ∑li=1 αi – (1/2) ∑i,j αiαjyiyjxi ⋅ xj
(41)
dove il pedice D sta per duale.
71
Capitolo 3– Tecniche di clustering
Il training del Support Vector (per il caso lineare e separabile) equivale a
massimizzare LD rispetto a αi, soggetto alla restrizione (40) ed alla positività
di αi, con la soluzione data dalla (39). Notiamo che c’è un moltiplicatore di
Lagrange αi per ogni punto di training: quei punti per cui αi > 0 sono chiamati
“support vectors” e giacciono su uno degli iperpiani H1, H2. Tutti gli altri punti
hanno αi = 0 e giacciono o su H1 o su H2 (cosicché vale l’uguaglianza nella
(37)), o su quel lato di H1 o H2 cosicché vale la disuguaglianza stretta nella
(37). Per le Support Vector Machines, i support vectors sono gli elementi
critici dell’insieme di training. Essi giacciono il più vicino possibile alla
frontiera della decisione; se si rimuovono tutti gli altri punti di training e si
ripete il training, si ritroverebbe lo stesso iperpiano di separazione.
3.5.1.1- Le condizioni di Karush-Kuhn-Tucker
Le condizioni di Karush-Kuhn-Tucker (KKT) giocano un ruolo centrale nella
teoria e nella pratica della ottimizzazione. Per il problema sopra espresso, le
condizioni KKT sono:
∂(LP)/∂wv = wv - ∑i αiyixiv = 0
v=1,...,d
∂(LP)/∂b = - ∑i αiyi = 0
(42)
(43)
yi(xi ⋅ w + b) – 1 ≥ 0
i=1,...,l
(44)
αi ≥ 0
∀i
(45)
αi[yi(xi ⋅ w + b) - 1] = 0
∀i
(46)
72
Capitolo 3– Tecniche di clustering
Nel 1987 Fletcher dimostrò che le condizioni KKT sono condizioni necessarie
e sufficienti per trovare una soluzione per w, b e α. Così risolvere il problema
SVM è equivalente a trovare una soluzione alle condizioni KKT.
Come immediata applicazione, notiamo che, mentre w è esplicitamente
determinato con la procedura di training, la soglia b non lo è, cioè è
implicitamente determinata. Comunque b è trovato facilmente usando la
condizione complementare KKT (46), scegliendo qualche i per cui αi ≠ 0 e
calcolando b.
Una volta che abbiamo esercitato una Support Vector Machine, come la
possiamo usare? Semplicemente decidiamo da quale lato della frontiera
decisionale (quell’iperpiano che giace a metà strada tra H1 e H2 e ad essi
parallelo) giace un dato test pattern x e assegnamo l’etichetta della
corrispondente classe, cioè il classificatore è dato da:
f(x) = sgn(x ⋅ w + b).
3.5.2- Il caso non-separabile
L’algoritmo precedente non può essere applicato a dati non separabili: come
possiamo fare allora in questo caso?
Ci piacerebbe rilassare i vincoli (35) e (36), ma soltanto quando necessario,
introducendo un ulteriore costo per far ciò. Ciò può essere fatto introducendo
le variabili positive ξi , i=1,...,l, nei vincoli, le quali diventano:
xi ⋅ w + b ≥ +1-ξi
per yi=+1
(47)
xi ⋅ w + b ≤ -1+ξi
per yi=-1
(48)
73
Capitolo 3– Tecniche di clustering
ξi ≥ 0
∀i
(49)
Quando accade un errore, il corrispondente ξi deve superare l’unità, così ∑i ξi
è un limite superiore sul numero di errori di training. Da qui una naturale via
per assegnare un costo extra per gli errori è di cambiare la funzione
obbiettivo minimizzandola rispetto a {(1/2)⎟⎜w⎟⎜2 + C(∑iξi)k}, invece che
rispetto a (1/2)⎟⎜w⎟⎜2 , dove C è un parametro scelto dall’utente (un grande C
corrisponde ad assegnare un’alta penalità agli errori). Scegliendo k=1 si ha il
vantaggio che nessuno degli ξi, neppure i loro moltiplicatori di Lagrange,
appaiono nel problema duale, che diventa:
Massimizzare:
LD ≡ ∑i αi – (1/2) ∑i,j αiαjyiyjxi ⋅ xj
(50)
soggetto a:
0 ≤ αi ≤ C ,
(51)
∑i αiyi = 0
(52)
La soluzione è ancora una volta data da
w = ∑Nsi=1 αiyixi
(53)
dove NS è il numero dei support vectors. Così l’unica differenza dal caso di
iperpiano ottimale è quella che gli αi ora hanno un limite superiore, C. La
situazione è riassunta in fig. 3.9.
74
Capitolo 3– Tecniche di clustering
fig.3.9. Iperpiani che separano linearmente per il caso non-separabile.
Avremo bisogno delle condizioni di KKT per risolvere il problema. La
Lagrangiana diventa:
LP ≡ (1/2)⎟⎜w⎟⎜2 + C∑iξi - ∑i αi {yi(xi ⋅ w + b) -1 + ξi} - ∑i µiξi
(54)
dove i µi sono i moltiplicatori di Lagrange introdotti per imporre la positività
degli ξi. Le condizioni di KKT diventano perciò (è da notare che i va da 1 al
numero dei punti di training, mentre v da 1 alla dimensioni dei dati):
∂(LP)/∂wv = wv - ∑i αiyixiv = 0
v=1,...,d
(55)
∂(LP)/∂b = - ∑i αiyi = 0
(56)
∂(LP)/∂ξi = C - αi - µi = 0
(57)
yi(xi ⋅ w + b) – 1 + ξi ≥ 0
(58)
ξi ≥ 0
∀i
75
(59)
Capitolo 3– Tecniche di clustering
αi ≥ 0
∀i
(60)
µi ≥ 0
∀i
(61)
αi[yi(xi ⋅ w + b) – 1 + ξi] = 0
(62)
µiξi = 0
(63)
Come prima, possiamo usare le condizioni di KKT complementari, (62) e
(63), per determinare la soglia b. Notiamo inoltre che la (57) combinata con
la (63) mostra che ξi = 0 se αi < C. Perciò possiamo semplicemente prendere
qualche punto di training per cui 0 < αi < C per usare l’equazione (62) (con
ξi=0) per calcolare b.
3.5.2.1- Esempi usando delle figure
La fig. 3.10 mostra due esempi di problema di pattern recognition in due
dimensioni, uno separabile e uno non separabile. L’errore nel caso non
separabile è identificabile con un attraversamento (nota che i support vectors
sono evidenziati mediante un cerchio supplementare).
fig. 3.10. Il caso lineare, separabile (a sinistra) e non (a destra).
76
Capitolo 3– Tecniche di clustering
3.6- Support Vector Machines non lineari
Come possono essere generalizzati i metodi sopra descritti al caso in cui la
funzione di decisione non è una funzione lineare dei dati?
Partiamo dal fatto che nelle equazioni del problema di training (50)-(52) i dati
appaiono solo nella forma di prodotti scalari xi ⋅ xj . Supponiamo ora di
mappare i dati in qualche altro (possibilmente di dimensione infinita) spazio
Euclideo H, usando una mappatura che chiameremo Φ:
Φ: Rd → H
(64)
Così l’algoritmo di training dipenderà soltanto dai dati attraverso il prodotto
scalare in H, cioè da funzioni della forma Φ(xi) ⋅ Φ(xj). Ora, se esistesse una
“funzione kernel” K tale che K(xi , xj) = Φ(xi) ⋅ Φ(xj), avremo bisogno soltanto
di usare K nell’algoritmo di training, e non avremo mai bisogno di sapere
esplicitamente cosa sia Φ. Un esempio è:
K(xi , xj) = exp {-(⎟⎜xi - xj⎟⎜2 ) / (2σ2)}
(65)
Tutte le considerazioni dei precedenti paragrafi valgono poiché stiamo
comunque facendo una separazione lineare, ma in uno spazio differente. Ma
come possiamo usare questa machine?
Dopo tutto, noi abbiamo bisogno di w, che esiste anche in H (vedi la (53)).
Ma una SVM è usata per calcolare i prodotti puntuali di un dato punto di test
x con w, o più precisamente per calcolare il segno della funzione
f(x) = ∑Nsi=1 αiyiΦ(si) ⋅ Φ(x) + b = ∑Nsi=1 αiyiK(si , x) + b
77
(66)
Capitolo 3– Tecniche di clustering
dove gli si sono i support vectors. Ancora una volta vogliamo evitare di
calcolare Φ(x) esplicitamente e usiamo invece la funzione
K(si , x) = Φ(si) ⋅ Φ(x)
Indichiamo ora lo spazio a cui appartengono i dati con L (L sta per “low”, cioè
per dimensione bassa, mentre H sta per “high”). E’ da notare che, oltre al
fatto che w esiste in H, in generale non esisteranno vettori in L che
mappano, attraverso Φ, w. Inoltre si nota che è facile trovare kernels (ad
esempio, kernels che sono funzioni dei prodotti scalari degli xi in L) tali che
l’algoritmo di training e la soluzione trovata sono indipendenti dalla
dimensione di ambedue L e H.
Descriviamo ora un semplice esempio di kernel ammesso, attraverso cui
possiamo costruire la mappatura Φ.
Supponiamo di avere dei dati che sono vettori in R2, e di scegliere un kernel
della forma
K(xi , xj) = (xi ⋅ xj)2
E’ facile trovare uno spazio H e la mappatura Φ da R2 a H, tali che
(x ⋅ y)2 = Φ(x) ⋅ Φ(y)
Scegliamo H = R3 e
Φ(x) = (x12, x1x2√2 , x22)T
(67)
Infatti
(x ⋅ y)2 = [(x1,x2)(y1,y2)T]2 = (x12y12 + 2x1x2y1y2 + x22y22) =
78
Capitolo 3– Tecniche di clustering
= (x12, x1x2√2 , x22) (y12, y1y2√2 , y22)T = Φ(x) ⋅ Φ(y)
fig.3.11. Immagine, in H, del quadrato [-1,1]x[-1,1]∈R2 sotto la mappatura Φ.
Per dati in L definiti sul quadrato [-1,1]x[-1,1]∈R2 l’immagine di Φ è mostrata
in fig.3.11.
La figura mostra cosa pensare di questa mappatura: l’immagine di Φ può
esistere in uno spazio anche di dimensione infinita, ma è solo una superficie,
anche se molto “contorta”, la cui dimensione intrinseca, il numero di
parametri necessari per specificare un punto, è la stessa dello spazio di
appartenenza dei vettori x, cioè L.
Notiamo che né la mappatura Φ né lo spazio H sono unici per un dato kernel.
Infatti potremmo, ugualmente bene, scegliere H = R3 e
Φ(x) = (1/√2)[(x12 – x22), 2x1x2 , (x12 + x22)]T
(68)
oppure H = R4 e
Φ(x) = (x12 , x1x2 , x1x2 , x22)T
(69)
79
Capitolo 3– Tecniche di clustering
Solitamente nei testi sulle SVM lo spazio H è chiamato spazio di Hilbert,
pensandolo come una generalizzazione dello spazio Euclideo.
3.6.1- Condizione di Mercer
Ma per quali kernels esiste una coppia {H,Φ}, con le proprietà sopra
descritte, e per quali non esiste?
La risposta ci viene data dalla condizione di Mercer:
esiste una mappatura Φ e un’espansione
K(x,y) = ∑i Φ(x)i Φ(y)i
(70)
se e solo se, per qualsiasi g(x) tale che
∫ g(x)2 dx
è finito
(71)
allora
∫ K(x,y) g(x) g(y) dx dy ≥ 0
(72)
Ancora una volta, c’è da sottolineare che in casi specifici potrebbe essere
difficile verificare se la condizione di Mercer è soddisfatta. La (72) deve
valere per ogni g che soddisfi la (71), che non è altro che una norma.
Comunque, possiamo facilmente provare che la condizione è soddisfatta per
potenze positive del prodotto scalare: K(x,y) = (x ⋅ y)p. Dobbiamo mostrare
che
∫ (∑di=1 xiyi)p g(x) g(y) dx dy ≥ 0
(73)
Espandendo il termine (∑di=1 xiyi)p si ottiene la forma
80
Capitolo 3– Tecniche di clustering
(p!/(r1!r2!...(p-r1-r2...)!)) ∫ x1r1x2r2... y1r1y2r2... g(x) g(y) dx dy
(74)
da cui, per il lato sinistro della (72), si ottiene
= (p!/(r1!r2!...(p-r1-r2...)!)) {∫ x1r1x2r2... g(x) dx}2
(75)
Una semplice conseguenza è che qualsiasi kernel che può essere espresso
come K(x,y) = ∑∞p=0 cp(x ⋅ y)p , dove cp sono coefficienti reali positivi e la
serie è uniformemente convergente, soddisfa la condizione di Mercer, fatto
dimostrato da Smola, Scholkopf e Muller nel 1998.
3.6.2- Alcuni esempi di SVMs non lineari
I primi kernels studiati per il problema del pattern recognition furono i
seguenti:
K(x,y) = (x ⋅ y + 1)p
(76)
K(x,y) = exp {-(⎟⎜x - y⎟⎜2 ) / (2σ2)}
(77)
K(x,y) = tanh(κx ⋅ y - δ)
(78)
L’equazione (76) rappresenta un classificatore polinomiale di grado p ;
l’equazione (77) dà un classificatore basato sulla funzione Gaussiana
Radiale (Gaussian Radial Basis Function) GRBF ed infine la (78)
rappresenta un tipo particolare di rete neurale sigmoidale a due strati.
La fig. 3.12 mostra i risultati per lo stesso problema di pattern recognition
mostrato in fig. 3.10, ma dove è stato scelto un kernel polinomiale di grado 3.
Notiamo che, nonostante che il numero di gradi di libertà sia grande, la
81
Capitolo 3– Tecniche di clustering
soluzione per il caso linearmente separabile (figura a sinistra) è pressappoco
lineare, indicando che la qualità diventa controllata; inoltre, il caso non
linearmente separabile (figura a destra) diventa separabile.
fig. 3.12. Kernel polinomiale di grado 3.
Finalmente notiamo che i classificatori SVM descritti sopra sono classificatori
binari, che possono essere facilmente combinati per manipolare il caso multiclasse.
3.7- La dimensione VC per le SVM
Mostriamo ora che la dimensione VC delle SVMs può essere molto grande
(anche infinito). Chiameremo qualsiasi kernel che soddisfi la condizione di
Mercer kernel positivo, e lo spazio corrispondente H lo embedding space.
Chiameremo inoltre qualsiasi embedding space con la dimensione minima
per un dato kernel lo minimal embedding space. Esiste il seguente
TEOREMA: Sia K un kernel positivo che corrisponde a un minimal
embedding space H. La dimensione VC della corrispondente support vector
machine (dove la penalità di errore C può avere tutti i valori) è dim(H) + 1.
Vediamo ora due esempi.
82
Capitolo 3– Tecniche di clustering
Calcoliamo ora la dimensione VC per i kernels polinomiali; consideriamo una
SVM con un kernel polinomiale omogeneo, agente su dati in RdL:
K(x1,x2) = (x1 ⋅ x2)p, x1,x2∈ RdL
(79)
Come nel caso in cui dL=2 e il kernel è quadratico, possiamo esplicitamente
costruire la mappatura Φ. Sostituendo zi=x1ix2i, si ha K(x1,x2) = (z1+...+zdL)p,
osserviamo che ogni dimensione di H corrisponde a un termine con potenze
di zi nell’espansione di K. Possiamo quindi esplicitamente scrivere la
mappatura per qualsiasi p e dL:
Φr1r2...rdL(x) = (x1r1...xdLrdL)[p! / (r1!...rdL!)]1/2 , ∑dLi=1 ri = p , ri ≥ 0
(80)
da cui si ricava il seguente
TEOREMA: Se lo spazio in cui esistono i dati ha dimensione dL (cioè L =
RdL), la dimensione VC per il minimal embedding space, per kernels
polinomiali omogenei di grado p (K(x1,x2) = (x1 ⋅ x2)p, x1,x2∈ RdL), è (pdL+p-1).
Calcoliamo infine la dimensione VC per i kernels GRBF; ci viene in aiuto il
seguente
TEOREMA: Consideriamo la classe di kernels positivi per cui K(x1,x2)→0 se
⎟⎜x1 – x2⎟⎜→∞, e per cui K(x,x) è O(1), e assumiamo che i dati possono
essere scelti arbitrariamente in Rd. La famiglia di classificatori composti da
SVM che usano questi kernels, e per cui la penalità di errore può assumere
qualsiasi valore, ha dimensione VC infinita.
83
Capitolo 3– Tecniche di clustering
3.8- Esempio di classificazione SVM: IRIS data
L’iris data set contiene quattro attributi del fiore dell’iris; lo scopo è quello di
individuare la classe di appartenenza di un iris basandosi su questi quattro
attributi.
Per semplicità considereremo solo i due attributi che portano maggiore
informazione riguardo alla classe di appartenenza: la lunghezza e la
larghezza del petalo.
La distribuzione dei dati è rappresentata in fig. 3.13. Nelle figure seguenti
(3.14-3.18) ci sono i risultati ottenuti.
fig. 3.13. Distribuzione dei dati.
84
Capitolo 3– Tecniche di clustering
fig.3.14. SVM lineare: separa facilmente le classi Setosa e Versicolor.
fig. 3.15. SVM polinomiale di grado 2 con C=∞.
85
Capitolo 3– Tecniche di clustering
fig. 3.16. SVM polinomiale di grado 10 con C=∞.
fig. 3.17. SVM RBF con σ=1.0 e C=∞.
86
Capitolo 3– Tecniche di clustering
fig. 3.18. SVM polinomiale di grado 2 e C=10.
87
Capitolo 4– Il progetto
Capitolo 4
IL PROGETTO
4.1- Introduzione
In questo capitolo finale verranno illustrate le parti fondamentali del programma
implementato per questa tesi.
L’ambiente di sviluppo di tale programma è Microsoft Visual C++ 6.0, contenuto
in Microsoft Visual Studio 6.0 Professional Edition.
Avendo sviluppato il programma in C++, la struttura che meglio identifica questo
linguaggio di programmazione è la Classe: perciò il mio progetto è stato
implementato strutturalmente come una Classe chiamata DiabeticBlobs.
Le funzioni membro che fanno parte di tale classe e che verranno esplicitate nei
prossimi paragrafi sono:
1. funzione
Normalizzazione,
che
effettua
la
pre-elaborazione
dell’immagine;
2. funzione BinarizzazioneLineare, che utilizzando una SVM lineare
realizza la binarizzazione dell’immagine;
3. funzione BinarizzazionePolinomiale, che utilizzando una SVM non
lineare polinomiale binarizza l’immagine;
4. funzione BinarizzazioneEsponenziale, che è una funzione simile alla 3
ma utilizza una SVM non lineare RBF;
5. funzione EliminazioneDiscoOttico, che come dice il nome elimina il disco
ottico;
6. funzione EstrazioneFeatures, che serve per estrarre le caratteristiche
volute dall’immagine
7. funzione ElaborazioneLineare, che comprende le funzioni 1, 2, 5, 6;
8. funzione ElaborazionePolinomiale, che contiene la 1, 3, 5, 6;
9. funzione ElaborazioneEsponenziale, che comprende la 1, 4, 5, 6.
88
Capitolo 4– Il progetto
Inoltre, per implementare una piccola parte del programma, ho fatto uso
dell’algoritmo SVMlight, open source code per usi scientifici, che altro non è che
l’implementazione del learning della mia SVM.
Infine
per caricare e salvare le immagini ed estrarne i valori dei pixels ho
utilizzato la Classe CTlabImage sviluppata da Etruria Innovazione Spa.
Le immagini del fondo oculare da elaborare mi sono state date gentilmente dal
caro amico Dott. Gianluca Martone, della Clinica Oftalmologica del Policlinico
Le Scotte di Siena. Un esempio è la seguente fig. 4.1.
fig. 4.1. Esempio di foto del fondo oculare.
89
Capitolo 4– Il progetto
4.2- La funzione Normalizzazione
Come già accennato nell’introduzione a questo capitolo, questa funzione serve
a pre-elaborare la foto, che nel nostro caso significa migliorare il contrasto
dell’immagine, per normalizzare il più possibile il colore del nostro target nelle
varie immagini retiniche facendole risaltare rispetto al background.
Siano (x1,y1) le coordinate di un pixel p qualsiasi all’interno dell’immagine di
partenza. L’algoritmo da me utilizzato può essere così schematizzato:
Algoritmo Normalizzazione:
(a) caricare l’immagine di partenza;
(b) portarla in scala di grigi, ottenendo così p_grigio(x1,y1);
(c) stretch (vedi appendice A alla fine del capitolo) dei livelli di grigio
dell’immagine, con risultato p_stretch(x1,y1);
(d) il pixel p_new(x1,y1) della nuova immagine sarà dato dalla
relazione:
p_new(x1,y1) = (red_new, green_new, blue_new) =
=([red_old*p_stretch(x1,y1)/p_grigio(x1,y1)],
[green_old*p_stretch(x1,y1)/p_grigio(x1,y1)],
[blue_old*p_stretch(x1,y1)/p_grigio(x1,y1)]);
dove red_..., green_..., blue_... sono i valori rosso, verde e blu dei tre canali
RGB.
L’algoritmo Normalizzazione va ripetuto per tutti i pixel dell’immagine della
retina. Il risultato di tale pre-processing è visibile in fig. 4.3 ricavata dalla fig. 4.2.
90
Capitolo 4– Il progetto
fig. 4.2. Immagine prima della funzione Normalizzazione.
fig. 4.3. Immagine risultante dopo l’applicazione della funzione Normalizzazione
91
Capitolo 4– Il progetto
4.3- Le funzioni per binarizzare l’immagine
Come accennato nell’introduzione, per implementare il learning delle mie
SVMs, cioè per ricavare i support vectors dei tre casi di kernel (lineare,
polinomiale e RBF) da me utilizzati per creare le mie machines, ho utilizzato
l’algoritmo learn del open source code
SVM-light, realizzato da Thorsten
Joachims: tale algoritmo, seguendo quanto detto nel capitolo 3, non fa altro che
ricevere in ingresso dei dati di training e fornire in uscita i support vectors,
cercando di massimizzare il margine, calcolato come una semplice distanza tra
vettori, tra i due cluster di dati.
Per passare i dati di training bisogna per prima cosa prendere l’immagine in
uscita alla funzione Normalizzazione e, con un semplice programma che può
modificare le foto (ad esempio, Microsoft Paint), etichettare gli essudati ed il
disco ottico (che hanno le stesse caratteristiche cromatiche) con il colore bianco
(r=255, g=255, b=255) ed il background con il colore nero (r=0, g=0, b=0), come
per esempio è stato fatto in fig. 4.4.
fig. 4.4. Immagine che serve per il training.
92
Capitolo 4– Il progetto
A questo punto bisogna creare un file di testo con ogni riga della seguente
forma:
A questo punto lanciamo il learn e otteniamo un file di testo dove sono indicati
vari parametri come b, i pesi (αi), le coppie (xi,yi) dei support vector, ecc....,
come si può vedere sotto:
A questo punto leggiamo quest’ultimo file e calcoliamo le tre binarizzazioni,
stando attenti a quali parti del file di testo da cui si ricavano i support vector
devono essere considerate. Nelle fig. 4.5-4.8 c’è un esempio della
binarizzazione.
93
Capitolo 4– Il progetto
fig. 4.5. Immagine da rendere binaria.
fig. 4.6. Binarizzazione lineare.
94
Capitolo 4– Il progetto
fig. 4.7. Binarizzazione polinomiale di grado 2.
fig. 4.8. Binarizzazione RBF con 1/(2σ2) = 0.005.
95
Capitolo 4– Il progetto
Come si può vedere da queste immagini la SVM con kernel RBF è più precisa
nel classificare gli essudati dell’immagine. Rimando al paragrafo 4.6 per
considerazioni più precise.
4.4- La funzione EliminazioneDiscoOttico
Questa funzione rappresenta un algoritmo originale sviluppato appositamente
per la presente applicazione.
Dopo aver osservato le immagini del fondo oculare in mio possesso, ho notato
che il disco ottico, essendo l’attaccatura del nervo ottico, è attraversato dalle
arterie principali: queste lo attraversano correndo verticalmente rispetto al piano
della foto. Da qui nasce la mia idea di cercare le arterie verticali per eliminare il
disco ottico.
Per prima cosa etichetto tutte le macchie trovate dal processo di binarizzazione.
L’algoritmo per etichettare è il seguente:
Algoritmo per etichettare:
(1) inizzializzo la variabile numero_etichetta a 0;
(2) scorro tutti i pixels dell’immagine;
(3) se trovo un pixel a 255 (siamo di fronte o a un essudato o al disco
ottico) non ancora etichettato:
a) incremento la variabile numero_etichetta;
b) metto il pixel in una pila;
(4) finché la pila non è vuota:
a) estraggo l’ultimo pixel della pila;
b) lo etichetto;
c) controllo tutti vicini: se un vicino vale 255 lo si mette nella
pila;
96
Capitolo 4– Il progetto
Dopo avere etichettato tutte le macchie, ne calcolo il centro e il raggio massimo
per cercare di raggruppare le più vicine; una volta raggruppate, mi concentro
sull’estrazione dei bordi delle vene: per far ciò estraggo il canale verde
dall’immagine iniziale (è il meno affetto da rumore) e lo convolvo con il
gradiente (vedi appendice B) di una funzione Gaussiana larga 9 pixel, per
ottenere prima solo i bordi verticali e poi solo quelli orizzontali. Estratti questi
bordi, li utilizzo per ottenere un’immagine con i soli bordi massimamente
verticali. A questo punto etichetto le coppie di pixel delle arterie con la loro
larghezza: dopo passo l’immagine risultante attraverso un filtro per eliminare le
coppie isolate che potrebbero essere frutto di rumore.
A questo punto siamo alla fine: scorro l’immagine con le arterie verticali e cerco
quella macchia che comprende una coppia di pixel delle arterie; se ce ne è più
di una estraggo quella con area maggiore. Il disco ottico coinciderà con tale
macchia. Il risultato di questo algoritmo è il seguente:
fig. 4.9. Immagine prima dell’applicazione EliminazioneDiscoOttico.
97
Capitolo 4– Il progetto
fig. 4.10. Immagine risultante.
4.5- La funzione EstrazioneFeatures
Come passo finale il programma attraverso la funzione EstrazioneFeatures
estrae alcune caratteristiche delle macchie (cioè degli essudati) che potrebbero
essere utili, a mio parere, ai medici per supervisionare l’evoluzione della
malattia e i possibili miglioramenti o peggioramenti dovuti a cure adatte o errate.
Vengono salvate su un file di testo le seguenti features:
1. area della macchia;
2. perimetro della macchia;
3. coordinate del centro;
4. raggio massimo;
5. raggio medio;
98
Capitolo 4– Il progetto
6. distanza dal disco ottico;
7. macchia più vicina;
8. distanza dalla macchia più vicina;
9. emisfero, cioè se si trovano nella parte superiore o inferiore rispetto al
disco ottico;
10. valori RGB (red, green, blue) massimi;
11. valori RGB medi;
12. media della luminanza;
13. varianza della luminanza;
Dopo consultazione con i medici potranno essere, in qualunque momento,
aggiunte altre caratteristiche che si riterranno significative per lo studio della
retinopatia diabetica.
4.6- Valutazione delle prestazioni
Nel mio progetto ho sperimentato tre tipi di SVM: il modello lineare, il modello
polinomiale e il modello RBF. Per la tesi mi sono state fornite 25 immagini a
colori della retina: 13 foto, con i loro circa 1000 objects, sono state usate per il
training delle mie SVMs, operazione durata circa due settimane. Ogni object è
stato etichettato come una regione target o come una regione background. Le
restanti 12 immagini sono state usate per il test sulla qualità del progetto: per
qualità intendo due parametri, la sensibilità e la specificità. La sensibilità è il
rapporto delle decisioni positive vere rispetto al numero dei casi positivi; la
specificità è il rapporto delle decisioni negative vere rispetto al numero totale dei
casi negativi. I risultati sono riportati nella tabella 1.
CLASSIFICATORE
SENSIBILITA’
SPECIFICITA’
SVM lineare
50%
90%
SVM polinomiale
55%
90%
SVM RBF
85%
82%
Tabella 1. Risultati.
99
Capitolo 4– Il progetto
Le regioni target delle dimensioni di circa 25x25 pixels sono classificate
ottimamente da tutti e tre i classificatori, mentre quelle più piccole sono ben
classificate soltanto dalla SVM RBF: quest’ultima SVM classifica erroneamente
alcune zone intorno al disco ottico come regioni target. Come è evidente dalla
tabella 1 il miglior compromesso per buone prestazioni è l’utilizzo del
classificatore SVM RBF. Considerando il numero ristretto di immagini di
training, i risultati sono abbastanza buoni. Sicuramente con più immagini il
progetto migliora notevolmente, considerando che le SVM si basano sulla
Statistical Learning Theory.
4.7- Ulteriori sviluppi
Per rendere l’interfaccia più immediata e più semplice da usare, la classe da me
implementata è stata importata in una interfaccia grafica sviluppata con Visual
C++ Microsoft, come si può vedere in fig. 4.11.
fig. 4.11. Interfaccia grafica con Visual C++ Microsoft.
100
Capitolo 4– Il progetto
I tasti del menù sono pratici per qualsiasi applicazione medica.
4.8- Conclusioni
L’obbiettivo della mia tesi era di implementare un metodo per automatizzare
l’analisi delle immagini a colori della retina con lo scopo di individuare e
classificare le lesioni superficiali dovute alla maculopatia diabetica. I risultati
sono
stati
abbastanza
soddisfacenti
e
mostrano
che
l’identificazione
automatizzata degli essudati sulla base delle caratteristiche cromatiche del
fondo oculare è pratica e di facile utilizzo per gli oftalmologi.
Un lavoro futuro per perfezionare il programma sarà sicuramente il
miglioramento del training e del test. Una volta raggiunta una sensibilità e una
specificità intorno al 90-93%, un ulteriore sviluppo al mio progetto potrebbe
essere l’identificazione di altre patologie della retina, come i microaneorismi e le
emorragie, per realizzare un sistema di screening a basso costo completo.
101
Capitolo 4– Il progetto
APPENDICE A- Stretching dell’istogramma
L’istogramma è una funzione che mostra il numero di pixels nell’immagine che
hanno un certo livello di grigio: per ogni livello vale
i(x,y)∈{0,1,2,...,2k-1} ∧ k∈Z
H(z) = ∫∫ [i(x,y) = z] dx dy
L’istogramma è un operatore unario che mappa l’immagine in un array di valori
{H(0),H(1),H(2),...,H(2k-1)}. E’ da notare che un’immagine ha un unico
istogramma, ma in generale non vale il contrario poiché un istogramma
contiene soltanto informazioni radiometriche e non informazioni spaziali. Un
esempio di istogramma è in fig. (a).
fig. (a). Esempio di istogramma.
Quando il range dei livelli di grigio dell’immagine originale non copre l’intero
range disponibile, il contrasto è mediocre. Per incrementare il contrasto si
utilizza il metodo dell’ histogram stretching: il livello minimo dell’immagine può
102
Capitolo 4– Il progetto
essere rimappato nel livello minimo della scala dei grigi e lo stesso può essere
fatto con il massimo; gli altri livelli dell’immagine originale sono rimappati
linearmente in livelli intermedi (vedi fig. (b)-(c)).
fig. (b). Immagine e istogramma prima dello stretching.
fig. (c). Immagine e istogramma dopo lo stretching.
Dopo lo stretching, l’istogramma ha la seguente forma
o(x,y) = (2k-1){[i(x,y)-min] / [max-min]}.
103
Capitolo 4– Il progetto
APPENDICE B- Metodo del gradiente per evidenziare i vasi sanguigni
La convoluzione di un’immagine I(x) con un kernel Gaussiano
G(x) = exp[-(x12+x22)/2σ2]
produce una immagine “liscia” e pulita dal rumore
S(x) = G(x) ⊗ I(x)
Se eseguito come convoluzione in due dimensioni, il calcolo può essere
particolarmente pesante (specialmente per grandi valori di σ). Anche se la
costruzione delle maschere di miglioramento dei vasi è molto efficiente, il
calcolo di S(x) renderebbe l’algoritmo inefficiente: fortunatamente esistono delle
strategie per renderlo efficiente.
Infatti è degno di nota che i kernels gaussiani sono separabili, cioè possono
essere espressi come
G(x) = g(x1)g(x2)
con g(z) = exp(-z2/2σ2)
Ciò significa che la convoluzione in due dimensioni G(x) ⊗ I(x) può essere
eseguita efficientemente convolvendo il kernel 1-D g(z) con le colonne
dell’immagine risultante dalla convoluzione delle righe di I(x) con lo stesso
kernel, cioè
S(x) = (g(x1) ⊗ I(x1,x2)) ⊗ g(x2)
Potendo applicare questa proprietà, possiamo iniziare a usare G(x) per
costruire altre maschere capaci di enfatizzare i vasi sanguigni o alcune delle
loro caratteristiche.
104
Capitolo 4– Il progetto
Così i tratti dei vasi possono essere approssimativamente pensati come delle
coppie di bordi a gradino vicini e paralleli con opposto contrasto: iniziamo
costruendo filtri sensibili ai bordi dei vasi aventi specifiche direzioni.
Al fine di enfatizzare i contorni dei vasi ortogonali alla direzione di un dato
vettore unitario (versore) n usiamo una stima della derivata direzionale In(x)
dell’immagine originale I(x) in una tale direzione:
In(x) = dI(x) / dn ≈ dS(x) / dn = d(G(x) ⊗ I(x)) / dn = Gn(x) ⊗ I(x)
dove Gn(x) = dG(x) / dn è una derivata direzionale del kernel Gaussiano (la fig.
(d) rappresenta il grafico di Gn(x) per n=[1,0]) e l’ultima equazione è dovuta alla
linearità della convoluzione e del’operatore differenziale.
fig. (d). Grafico di un operatore derivata direzionale del kernel Gaussiano Gn(x).
La ragione per poter utilizzare questa approssimazione è che Gn(x) può essere
decomposta come
Gn(x) = n ⋅ ∇G(x) = n1∂G(x)/∂x1 + n2∂G(x)/∂x2
dove n1 e n2 sono le componenti di n. Questo significa che In(x) può essere
ottenuta al costo di una addizione e due moltiplicazioni per pixel una volta che
105
Capitolo 4– Il progetto
sono note ∂G(x)/∂xi ⊗ I(x) (per i=1,2). Fortunatamente, non sono richieste tutte
queste convoluzioni e le maschere di derivate parziali della Gaussiana possono
essere decomposte con considerevole accuratezza con le medie di kernels
Gaussiani spostati appropriatamente. Per esempio
∂G(x)/∂x1 ≈ (1/σ) {G(x+[(σ/2),0]) – G(x-[(σ/2),0])}
Così ∂G(x)/∂xi ⊗ I(x)
può essere stimato da S(x) soltanto al costo di una
sottrazione e di una moltiplicazione per pixel.
Combinando appropriatamente le versioni spostate della nostra efficiente
realizzazione di Gn(x) è ora possibile costruire filtri sensibili alla struttura dei
vasi sanguigni in ogni direzione.
106
Bibliografia ragionata
Bibliografia ragionata
Introduzione
•
[1] Wang H., Hsu W., An effective approach to detect lesions in color
retinal images, 2002, IEEE, Singapore
•
[2] Osareh A., Mirmehdi M., Automatic Recognition of Exudative
Maculopathy using Fuzzy C-Means Clustering and Neural Networks,
IEEE, Bristol
•
[3] Osareh A., Mirmehdi M., Colour Morphology and Snakes for Optic
Disc Localisation, IEEE, Bristol
•
[4] Osareh A., Mirmehdi M., Classification and Localisation of DiabeticRelated Eye Disease, 2002, IEEE, Bristol
L’occhio umano
•
Duke-Elder S., System of Ophthalmology, 1965, Kimpton, London
•
Testut L., Latarjet A., Anatomia umana, IV, 1971, UTET, Torino
•
Toselli C., Miglior M., Oftalmologia clinica, 1979, Monduzzi, Bologna
•
Giunchi G., Enciclopedia medica italiana, 1986, USES, Firenze
107
Bibliografia ragionata
La retina
•
Cavallotti C., Amenta F., Vie e centri nervosi, 1982, USES, Firenze
•
Davson H., The physiology of the eye, 1972, Academic Press, New York
•
Bloom W., Fawcett D. W., Trattato di istologia, 1981, Piccin, Padova
•
Morgan W. W., Cell biology of the eye, 1982, Academic Press, New York
•
Frezzotti R., Guerra R., Oftalmologia essenziale, 1982, C.E.A., Siena
Tecniche di clustering
•
[5] Zadeh L.A., Fuzzy Set, 1965, Information and control vol.8
•
Yager R.R., Filer D.P., Template-based fuzzy sistems modelling, 1994, J.
Intell. And Fuzzy Syst. Vol. 2
•
Mandami E.H., Application of fuzzy alghorithms for simple dynamic plant,
1974, IEEE
•
Larsen P.M., Industrial applications of fuzzy logic control, 1980, Mach.
Studies vol.12 n.1
•
Dubois D., Prade H., Fuzzy sets and Systes: theory and application,
1980, FL. Accademic, Orlando
108
Bibliografia ragionata
•
Bezdek J., Pattern Recognition with Fuzzy objective Function Algorithm,
1981, Plenum New York
•
Dunn J.C., A fuzzy relative of the ISODATA process and its Use in
detecting compact,Well separated clusters, 1974, J. Cybern
•
Bezdek J., Fuzzy mathematics in pattern classification, 1973, Cornell
University, Ithaca
•
Vapnik V.N., The Nature of Statistical Learning Theory, 1995, New York
•
Scholkopf B., Support Vector Learning, 1997, Munich
•
Burges C.J.C., A tutorial on Support Vector Machines for Pattern
Recognition, Boston
•
Vapnik V.N., An overwiew of Statistical Learning Theory, 1999, IEEE
•
Scholkopf B., Statistical Learning and Kernel Methods, 2000, Cambridge
•
Shilton A., Incremental Training of Support Vector Machines, 2005, IEEE
•
Palaniswami M., Machine learning using support vector machines, 2000,
AISAT
109

IL SISTEMA HYDROCLEAN STEINHARDT per la grigliatura delle

Visto di bilancio_201501701

Impegni_201501888 - Comune di Riva del Garda

Visto di bilancio_201501514

Visto di bilancio_201501516

Ieri eravamo vivi - Prima di copertina

Impegni_201501514 - Comune di Riva del Garda

"» , ..`15 - accademia capellini

Determinazione DETRS201500163 - numero: 159 di data 20