UNIVERSITA' POLITECNICA DELLE MARCHE
FACOLTA' DI INGEGNERIA
Corso di Laurea triennale in Ingegneria Informatica e dell'Automazione
IMPLEMENTAZIONE E SPERIMENTAZIONE DI ALGORITMI
DI APPRENDIMENTO FUZZY SU RETI NEURALI DI TIPO
NEURAL GAS
Relatore: Chiar.mo
Prof. Aldo Franco Dragoni
Tesi di Laurea di:
Gianluca Giulianelli
Correlatore:
Dott. Mauro Mazzieri
Anno accademico 2009 - 2010
Un ringraziamento speciale e dal profondo del cuore va a mio padre
Erminio e mia madre Maria che mi hanno sempre sostenuto ed
incoraggiato.
Ringrazio il relatore prof. Aldo Franco Dragoni ed il correlatore dott.
Mauro Mazzieri per la disponibilità e la pazienza con cui mi hanno
seguito fin dall'inizio del tirocinio.
Grazie a tutti i miei amici, che hanno condiviso con me i momenti felici e
che mi hanno sorretto nei momenti difficili.
Indice
INTRODUZIONE
pag 1
CAPITOLO 1
Le Reti Neurali
1.1 - Concetto di rete neurale
1.2 - Reti neurali e Clustering
1.3 - Rete neurale Neural Gas (NG)
1.4 - Rete neurale Growing Neural Gas (GNG)
1.5 - Indici caratteristici delle reti neurali
pag 6
pag 9
pag 11
pag 14
pag 18
CAPITOLO 2
Implementazione delle reti neurali NG e GNG
2.1 - Strutture dati utilizzate
2.2 - Interfaccia ReteNeurale
2.3 - Classe Gng
2.4 - Classe NeuralGas
2.5 - Implementazione versione asimmetrica
pag 20
pag 36
pag 39
pag 51
pag 55
CAPITOLO 3
Implementazione dell' algoritmo Fuzzy
3.1 - Algoritmo di apprendimento Fuzzy
3.2 - Strutture dati utilizzate
3.3 - Classe FuzzyGng
3.4 - Implementazione versione asimmetrica
pag 56
pag 60
pag 65
pag 72
CAPITOLO 4
Valutazione sperimentale
4.1 - Convergenza al variare dei parametri e confronto
4.2 - Andamento degli indici caratteristici
4.3 - Valutazione sperimentale delle reti asimmetriche
4.4 - Visualizzazione grafica - clustering
4.5 - Sperimentazione su dataset di prova
pag 73
pag 79
pag 80
pag 82
pag 89
CONCLUSIONI
pag 92
BIBLIOGRAFIA
pag 93
INTRODUZIONE
In questa tesi viene descritto il lavoro di implementazione in linguaggio
java e sperimentazione di alcuni tipi di reti neurali ad apprendimento non
supervisionato, cioè le reti neurali di tipo Neural Gas (NG) e Global
Neural Gas (GNG).
Per ognuna di queste reti sono stati condotti esperimenti al fine di
valutarne le prestazioni e capire in che misura la variazione dei parametri
di apprendimento incida sull'efficienza delle reti stesse.
Successivamente è stata implementata una versione innovativa
dell'algoritmo di apprendimento: la versione Fuzzy, che rivoluziona il
concetto di connessione tra i nodi della rete.
Anche sulla versione Fuzzy sono stati condotti esperimenti di valutazione
delle performance al variare dei parametri di apprendimento e, pur essendo
un algoritmo ancora in fase di sviluppo, sono state fatte alcune
osservazioni con la speranza che siano utili ai ricercatori che se ne
occuperanno in futuro.
Le tre reti neurali (NG, GNG e Fuzzy-GNG) sono state sottoposte ad uno
stesso training per confrontarne la convergenza e l'apprendimento e per
dimostrare la validità dell'algoritmo di apprendimento Fuzzy.
Delle tre reti neurali è stata implementata e valutata sperimentalmente la
versione asimmetrica , su questa versione si è voluto
anche osservare la distribuzione delle connessioni unidirezionali rispetto a
quelle bidirezionali.
Inoltre si è dato ampio risalto all'applicazione di clustering di dati, alla
quale sono state applicate le reti neurali implementate.
Infatti è stata creata un'applicazione java che sfrutta le librerie JOGL (Java
Open GL) per visualizzare l'evoluzione della rete durante l'apprendimento
ed osservarne la capacità di individuare i cluster.
Infine è stato condotto un esperimento di clustering su dati relativi alla
frequenza con cui compaiono alcune parole all'interno degli articoli
rilasciati da un'agenzia di stampa.
Capitolo 1
LE RETI NEURALI
1.1 Concetto di rete neurale
Una rete neurale è una struttura logico-matematica ispirata all'attività di
apprendimento di nuove informazioni esercitata dal cervello umano
tramite le sue unità fondamentali: i neuroni biologici.
Il neurone biologico ,in prima approssimazione, genera un impulso
elettrico di un certo potenziale sul suo assone (output) il cui valore dipende
dalla somma pesata dei potenziali presenti sui dendriti (input) del neurone
stesso.
Il segnale di output che si propaga lungo l'assone viene a sua volta
modulato dalla sinapsi prima di andare ai dendriti degli altri nodi, sinapsi
diverse modulano il segnale presente sull'assone in modo diverso.
Una rete neurale quindi è una struttura composta da varie unità: nodi;
ogni nodo è sono caratterizzato da un insieme di valori numerici che ne
denota la posizione all'interno dello spazio di stato della rete (di
dimensione arbitraria).
Tra due nodi della rete, può essere presente o meno una connessione che
sta ad indicare che i due nodi sono collegati tra loro; a seconda del tipo di
rete neurale implementata la connessione può essere :
simmetrica -->
connessione(a,b) = connessione(b,a)
asimmetrica--> connessione(a,b) ≠ connessione(b,a)
Dato un nodo “a”, l'insieme dei nodi con cui è connesso, viene detto
insieme dei nodi vicini (topologicamente) o anche dei connessi al nodo.
La rete neurale di conseguenza, oltre ad una sua rappresentazione
geometrica data dalla posizione dei nodi nello spazio di stato, ha anche una
sua topologia definita dalle varie connessioni tra nodi.
Le reti neurali possono apprendere in due modi:
–
apprendimento supervisionato
–
apprendimento non supervisionato
Nell'apprendimento supervisionato alla rete neurale vengono presentati dei
dati in input per cui si conosce già l'output desiderato che deve assumere la
rete alla fine dell'apprendimento.
Questi dati costituiscono il training set della rete , essendo già noto l'errore
tra la posizione dei nodi desiderata e la posizione dei nodi effettiva, i
parametri relativi all'apprendimento vengono modificati ad ogni passo
cercando di ridurre al minimo tale errore.
Alla fine della fase di training quindi, si avranno i parametri che verranno
usati dalla rete neurale durante l' apprendimento vero e proprio.
L'apprendimento non supervisionato è quello utilizzato dalle reti neurali
che verranno descritte nei seguenti paragrafi, non è supervisionato perchè
alla rete vengono presentati solo dati di input significativi per cui non si
conosce un output desiderato. La rete cerca man mano di inserire dati di
input simili all'interno dello stesso gruppo con un apprendimento
autonomo, senza controllo esterno sull'errore.
Questo tipo di apprendimento viene utilizzato spesso quando non è
disponibile un set di dati di riferimento o addirittura non si è a conoscenza
della categoria di appartenenza dell'input.
1.2 Reti neurali e Clustering
Una rete neurale apprende se, quando gli viene proposta una sequenza di
dati di input (dataset), i suoi nodi tendono sempre più ad avvicinarsi
all'input e la topologia che assume la rete permette di evidenziare gruppi di
dati simili tra loro (clustering).
Se prendiamo come esempio banale, una serie di punti appartenenti al
piano cartesiano come dati di input:
si può notare facilmente che usando come criterio di clustering la distanza
euclidea tra i vari punti , i punti si possono raggruppare in prima
approssimazione in 3 cluster :
Se ad una rete neurale vengono proposti in input i suddetti punti, alla fine
dell'apprendimento la rete deve assumere una conformazione tale da poter
estrapolare i 3 cluster .
Un' ipotetica rete neurale che abbia appreso in modo corretto, può avere
questa morfologia:
La rete sopraindicata è composta da nodi (punti bianchi) coerenti con lo
spazio di stato del set di dati di input (punti neri), ed assume una topologia
che evidenzia correttamente i tre cluster in cui si raggruppano i dati.
Il clustering di dati è infatti una delle applicazioni più comuni in cui
vengono utilizzate le reti neurali.
1.3
Rete Neurale Neural Gas (NG)
La rete neurale di tipo Neural Gas è una rete ad apprendimento non
supervisionato che si pone l'obbiettivo di riconoscere ed adattarsi alla
topologia del dataset di input che gli viene proposto, senza avere alcuna
informazione preliminare sui legami di similarità tra gli elementi del
dataset stesso.
In questa tipologia di rete, si ha un numero più o meno consistente di nodi
(N) che va stabilito a priori e che rimane costante durante tutta la fase di
apprendimento.
Di solito la posizione iniziale di ogni singolo nodo è scelta casualmente
all'interno dello spazio dimensionale dell'input o semplicemente ogni nodo
viene scelto tra gli stessi dati del dataset.
Prima del training ogni nodo è isolato, ovvero non possiede alcuna
connessione verso gli altri nodi della rete, associando un' età ad ogni
connessione possiamo riconoscere la mancanza di quest'ultima ponendo
l'età a zero, quindi inizialmente le età di tutte le possibili connessioni
( N X N ) hanno valore zero.
La fase di training è composta da vari adaptation step, in ognuno dei quali
si parte con il sottoporre alla rete un dato di input appartenente al dataset,
questo dato viene confrontato con i nodi della rete e l'insieme dei nodi
viene ordinato in ordine crescente ripetto alla distanza (solitamente
euclidea) tra nodo e dato di input.
Successivamente si procede allo spostamento dei nodi verso l'input ,
l'incremento dello spostamento dipende dalla posizione che ogni nodo
assume nell'ordinamento visto in precedenza.
Inoltre, ad ogni adaptation step viene creata o resettata l'età della
connessione tra il nodo vincitore (primo della lista - più vicino) ed il
secondo , cioè si ha età(vincitore, secondo)=1, mentre tutte le età relative
alle connessioni tra il vincitore e gli altri nodi della rete (se diverse da 0)
vengono incrementate di 1.
Se l'età di una connessione ha raggiunto una determinata età massima,
viene eliminata (età=0).
Questo meccanismo di creazione ed eliminazione delle connessioni
rappresenta l'apprendimento della rete neurale, che alla fine del training
deve portare la rete stessa ad assumere una topologia coerente a quella del
set di dati in input.
Algoritmo NEURAL GAS: [1]
(1)
La rete è composta inizialmente da "n" nodi aventi posizione
casuale all' interno dello spazio di stato.
ωn ε Rⁿ
(2)
viene sottoposto alla rete un dato di input “ζ”.
(3)
Determinare la sequenza di nodi ki (i = 0,1,... n-1) della rete
tale che:
|| ωk0– ζ || < || ωk1 – ζ || <............... < || ωkn – ζ ||
(4)
muovere i nodi della rete verso il dato di input di uno
spostamento pari a:
Δωki = ε · e
i
λ
· || ζ – ωki ||
(5)
se non esiste , creare la connessione tra il nodo k0 (vincitore) ed
il nodo k1 (secondo); se esisteva resettarne l'età.
(6)
Incrementare l'età di tutte le connessioni che collegano k0 agli
altri nodi.
(7)
Rimuovere le connessioni di k0 che superano l'età massima T.
(8)
Se un criterio di stop non è stato soddisfatto tornare al passo 1.
I parametri di apprendimento cambiano ad ogni adaptation step e
dipendono dal rapporto tra il numero di steps effettuati (t) ed il numero
totale degli steps di training previsti (tmax) :
λ = λi · ( λf / λi)
ε = εi · (εf / εi)
t/tmax
t/tmax
T = Ti · (Tf / Ti)
t/tmax
Il passo (3) dell'algoritmo, dove si procede all'ordinamento dei nodi in
base alla distanza dal dato di input, è sicuramente il più oneroso in termini
di tempo di elaborazione. Quindi, osservando che lo spostamento dei nodi
è molto piccolo per i >> λ e che, essendo (λf << λi), con l'aumentare di t
λ tende ad essere piccolo, con il crescere degli adaptation steps si può
ridurre il numero dei nodi da ordinare (i << n).
1.4 Rete Neurale GNG (Growing Neural Gas)
La rete neurale di tipo GNG (Growing Neural Gas) è una rete ad
apprendimento non supervisionato, nata per risolvere alcune problematiche
riscontrate nell'utilizzo della rete neurale di tipo NG (Neural Gas) .
Uno dei problemi che si deve affrontare quando si sottopone un certo set di
dati in input alla NG per effettuare un clustering dei dati stessi, è che
dobbiamo stabilire a priori il numero dei nodi della rete.
A volte questo numero si rivela insufficiente e bisogna rielaborare da capo
il set di dati in input ,sottoponendoli ad una rete NG composta da un
numero maggiore di nodi.
Nella NG il numero di nodi ,di cui si compone la rete, va stabilito a priori e
rimane invariato durante tutta la sua evoluzione; ciò significa che non
vengono aggiunti nuovi nodi, e non vengono rimossi nodi preesistenti,
questa caratteristica da un lato pone un limite certo alla dimensione della
rete, e quindi allo spazio di memoria utilizzato per tener traccia dei nodi e
delle connessioni, però dall'altro lato pone il problema di conoscere già in
fase di inizializzazione il numero dei nodi: questo problema ha ispirato il
l'idea su cui si fonda la Gng .
La rete GNG al contrario della NG, inizialmente è composta da un numero
limitato di nodi che cresce durante la fase di apprendimento.
Infatti, l'idea principale su cui si basa il funzionamento della GNG, è di
aggiungere nuovi nodi alla rete al crescere dei passi di adattamento verso i
dati di input (adaptation step).
I nuovi nodi vengono aggiunti alla rete tenendo conto della sua evoluzione
passata , cioè basandosi su alcune misure statistiche di cui si è tenuta
traccia durante gli adaptation steps precedenti.
Il meccanismo di gestione dell'età delle connessioni tra i nodi è identico a
quello descritto nella trattazione della NG, ovvero:
in ogni adaptation step viene creata una connessione tra il nodo più vicino
ed il secondo e vengono incrementate le età di tutti i connessi al vincitore;
le connessioni la cui età supera l'età massima vengono rimosse.
Quindi la topologia della rete cambia continuamente perchè ad ogni passo
di adattamento possono essere create nuove connessioni tra nodi oppure
eliminate alcune connessioni preesistenti.
Durante la sua crescita, la rete può anche perdere dei nodi, ciò è dovuto al
fatto che alcuni dei nodi rimangono isolati (non connessi con nessun altro
nodo) e quindi vengono eliminati.
Con l'aumentare del numero di adaptation step, i nodi della rete neurale
GNG tendono ad avvicinarsi globalmente ai dati di input, e la topologia
della rete evidenzia con maggiore accuratezza gruppi di dati simili
(clusters).
Un'altra differenza importante rispetto alla NG è che nella GNG i
parametri relativi all'apprendimento si mantengono costanti.
Algoritmo GNG: [2]
(1)
La rete è composta inizialmente da due nodi “a” e “b” aventi
posizione casuale all'interno dello spazio di stato:
ωa ε Rⁿ , ωb ε Rⁿ
(2)
viene sottoposto alla rete un dato di input “ζ”.
(3)
trovare il nodo più vicino “s1” ,ed il secondo più vicino “s2” al
dato di input.
(4)
Incrementare l'età di ogni connessione che parte da s1.
(5)
Aggiungere il quadrato della distanza tra l' input ed il nodo s1,
ad una variabile locale (errore) che fa riferimento ad s1:
Δerror(s1) = ( || ωs1 – ζ || )²
(6)
muovere s1 ed i nodi a lui connessi, verso il dato di input ζ , di
una frazione della distanza tra s1 e ζ ; rispettivamente di “εb”
ed “εn” :
Δ ωs1 = εb · || ζ – ωs1 ||
per il nodo s1
Δ ωsn = εn · || ζ – ωsn ||
per i nodi connessi ad s1
(7)
Se s1 e s2 sono già connessi resettare l'età della connessione,
altrimenti creare la connessione tra i due nodi
(8)
rimuovere le connessioni che hanno un età maggiore ad
“αmax” (età massima) ; se, come conseguenza, uno o più nodi
divengono isolati, eliminarli dalla rete.
(9)
Se il numero di dati sottoposti alla rete finora è un multiplo
intero del parametro “λ”, aggiungere un nuovo nodo alla rete
nel seguente modo:
(9.1) trovare il nodo “q” che ha accumulato maggior errore
(Δerror)
(9.2) inserire il nuovo nodo “r” a metà tra il nodo q el il nodo tra
i suoi connessi che ha maggiore errore “f”:
ωr = 0,5 · (ωq + ωf)
(9.3) connettere il nodo r con i nodi q e f, rimuovere la
connessione tra q ed f
(9.4) ridurre gli errori associati a q ed f, moltiplicandoli per una
costante α < 1 , inizializzare l'errore associato ad r con il
nuovo valore dell'errore di q.
(10)
ridurre gli errori associati a tutti i nodi, moltiplicandoli per una
costante d < 1.
(11)
se un criterio di stop non è stato soddisfatto ,ritorna al passo 1
Come vediamo dall'algoritmo, i nodi vengono spostati verso il dato di
input (passo 6), in questo modo i nodi della rete tenderanno globalmente
ad avvicinarsi al set di dati di input.
La creazione della connessione tra il nodo vincitore (più vicino) ed il
secondo (passo 7), l'incremento dell'età associata alle connessioni
(passo 4), e di conseguenza la rimozione delle connessioni troppo vecchie
e dei nodi isolati (passo 8), permettono di definire una topologia della rete
coerente con quella dei dati in input.
La variabile locale errore, associata ad ogni nodo, serve a sapere in quale
zona è più opportuno inserire il nuovo nodo e come collegarlo.
1.5 Indici caratteristici delle reti Neurali
Lunghezza media di un cammino (L):
In una rete neurale, la distanza tra due nodi, si definisce come il numero
connessioni del cammino più breve che li connette.
La lunghezza media di cammino della rete è la media aritmetica delle
distanze tra coppie di nodi.
Nelle reti che rappresentano ambiti del mondo reale , di solito L non è
molto grande , ciò è dovuto al fenomeno detto “small world”.
Coefficiente di Clustering (C):
Dato un nodo della rete j , connesso direttamente a Kj nodi , si possono
Kj ·(Kj-1)
avere al più
connessioni tra questi nodi.
2
Di solito ce ne sono di meno, per ipotesi supponiamo che ci sono Ej
connessioni effettive (Ej < Kj).
Il coefficiente di clustering del nodo j si definisce come il rapporto :
cioè ,
Cj =
Ej
Kj
2 · Ej
Kj ·(Kj-1)
Il coefficiente di clustering della rete ( C ) è dato dalla media aritmetica di
tutti i coefficienti Cj ed è compreso tra 0 e 1 (1 se la rete è totalmente
connessa) [3].
Distribuzione del grado (P):
Il grado di un nodo è il numero di connessioni che il nodo ha verso gli altri
nodi.
La distribuzione del grado mette in relazione il grado ,con la quantità dei
nodi della rete che possiedono tale grado.
Capitolo 2
IMPLEMENTAZIONE DELLE RETI NEURALI
NG E GNG
2.1 Strutture Dati Utilizzate
A prescindere dalle varie implementazioni di una rete neurale , si possono
comunque individuare alcune strutture dati che rappresentano i principali
componenti della rete stessa: i nodi e le connessioni tra nodi.
Per quanto riguarda i nodi, essi sono caratterizzati da un insieme di valori
C={c1,c2,c3,....,cn}
ci ε R , rappresentativi della loro posizione
all'interno dello spazio di stato della rete.
Se si considera l'insieme dei nodi N = { nodo1 ,nodo2 ,nodo3 ,....., nodom}
numerabile ,allora una possibile struttura dati che mette in relazione i nodi
ai rispettivi valori (N X C) è una matrice come quella raffigurata sotto:
dove la colonna j-esima (j=1,2,3...m) indica i valori caratteristici del nodo j
, cioè Cj= { c1,j , c2,j , c3,j ,........ , cn,j}.
Un altro componente della rete neurale che possiamo rappresentare
mediante una matrice sono le connessioni.
Una connessione rappresenta la presenza di un collegamento tra un nodo
ed un altro , la presenza del collegamento può essere indicata da un flag ,
cioè da una variabile che assume valore pari ad 1 (collegamento presente)
o pari a 0 (collegamento non presente).
Quindi se si associa un flag ad ogni coppia possibile di nodi (N X N), si
hanno le informazioni necessarie per comprendere la topologia della rete
neurale.
Le connessioni quindi possono essere rappresentate in memoria da una
matrice binaria (i suoi elementi possono assumere solo valore pari a 0 o 1)
come quella sottostante:
In questo caso abbiamo che da ogni colonna j-esima (o riga) , si riesce a
capire con quali nodi è connesso il nodo j, osservando gli indici di riga per
i quali: matrice(i,j) = 1 (nodoi connesso a nodoj)
I valori sulla diagonale sono tutti uguali ad 1 perchè si considera che un
nodo sia sempre connesso con se stesso.
Efficienza strutture dati:
E' utile. al fine di trovare la struttura dati più efficiente per rappresentare in
memoria una matrice , sapere se essa può definirsi densa o sparsa.
Una matrice si definisce sparsa se contiene pochi valori diversi da zero ,
mentre al contrario si definisce densa se contiene pochi valori pari a zero.
Questa distinzione è importante perchè le matrici sparse possono essere
memorizzate e gestite in modo più efficiente tramite l'utilizzo di
contenitori associativi che tengono traccia soltanto dei pochi valori diversi
da zero contenuti nella matrice.
L'utilizzo di un classico array bidimensionale per la memorizzazione di
una matrice sparsa comporta spreco di memoria e maggiore lentezza
nell'esecuzione delle operazioni sulla matrice ,come ad esempio la ricerca
di un valore al suo interno.
Nel caso dell'implementazione delle reti neurali , la matrice
rappresentativa delle connessioni è spesso una matrice sparsa perchè
l'interconnessione tra i nodi è ben lontana dall'essere totale.
Matrici Dinamiche:
Un altro aspetto di cui tenere conto per l'implementazione delle strutture
dati da utilizzare è che di solito nelle reti neurali si ha una crescita del
numero di nodi all'aumentare del numero di dati presentati in input
alla rete.
La crescita del numero di nodi comporta quindi una modifica del numero
di righe e/o di colonne delle matrici utilizzate; per esempio, per quanto
riguarda la matrice delle connessioni, si ha una crescita della sua
dimensione.
Di conseguenza, nello sviluppo del codice di implementazione, si è fatto
largo uso di matrici dinamiche.
Implementazione delle strutture dati in linguaggio Java:
Per implementare le suddette strutture dati in linguaggio Java , ho
utilizzato le librerie Parallel-Colt , che sono delle librerie open source
utilizzate per applicazioni scientifiche e tecniche che richiedono
performance elevate.
Queste librerie vengono anche utilizzate nel campo di ricerca dell' High
Energy Physics del CERN di Ginevra, dove si devono affrontare problemi
matematici in dimensioni molto elevate ed è richiesta una grande velocità
di computazione ed allo stesso tempo un'occupazione di memoria minima .
Le classi contenute nei vari package di Parallel-Colt rappresentano vari
costrutti matematici utili in campo scientifico, come riportato nel sito
ufficiale dedicato a questa libreria [4]:
“The Colt library provides fundamental general-purpose data
structures optimized for numerical data, such as resizable arrays,
dense and sparse matrices (multi-dimensional arrays), linear
algebra, associative containers and buffer management. The Jet
library contains mathematical and statistical tools for data
analysis, powerful histogramming functionality, Random Number
Generators and Distributions useful for (event) simulations, and
more.”
Come si evince dalla descrizione del contenuto sopra riportata, il
Parallel-Colt offre strutture dati ottimizzate per l'utilizzo di matrici
dense e sparse che, come già detto, vengono utilizzate
nell'implementazione efficiente dei vari tipi di reti neurali.
Inoltre questa libreria mette a disposizione altri strumenti come gli
array ridimensionabili (dinamici), che si adattano perfettamente a
rappresentare alcune variabili di stato di un sistema in evoluzione
come le reti neurali.
Le classi utilizzate della libreria Parallel-Colt per l'implementazione delle
reti neurali di tipo Neural Gas e Global Neural Gas sono principalmente
quelle relative a matrici sparse di interi e sono:
–
cern.colt.list.tint.IntArrayList
–
cern.colt.matrix.tint.impl.SparseIntMatrix1D
–
cern.colt.matrix.tint.impl.SparseIntMatrix2D
Infatti SparseIntMatrix2D implementa una matrice di interi gestita
tramite contenitori associativi poiché sparsa, mentre a sua volta
SparseIntMatrix1D implementa un vettore sparso che è utile ad
esempio nel rappresentare una riga o una colonna della matrice stessa.
IntArrayList invece implementa un vettore ridimensionabile
(dinamico) di interi che viene spesso utilizzato perchè richiesto da alcuni
fondamentali metodi di SparseIntMatrix2D come ad esempio il metodo
getNonZeros() da cui si ottengono i valori diversi da zero della matrice
sparsa, questo metodo richiede come argomenti 3 oggetti di tipo
IntArrayList.
Però, relativamente all'implementazione di una rete neurale, servono
matrici sparse che siano anche dinamiche, ovvero che sia possibile
variarne le dimensione.
Quindi le matrici dinamiche devono consentire operazioni come l'aggiunta
di una riga e/o di una colonna (aumenta la dimensione) e la rimozione di
una riga e/o di una colonna (riduce la dimensione).
Per implementare la matrice di interi sparsa e dinamica ho sviluppato la
classe:
Mat2DIntSparsaDinamica
(matrice sparsa dinamica):
SparseIntMatrix2D
Mat2DIntSparsaDinamica
La classe Mat2DIntSparsaDinamica eredita dalla classe
SparseIntMatrix2D del package cern.colt.matrix.tint.impl della
libreria Parallel-Colt, quindi è un'implementazione valida di una matrice
sparsa. I costruttori di SparseIntMatrix2D sono stati tutti sovrascritti per
poter sfruttare tutte le funzionalità di tale classe.
I metodi che sono stati aggiunti rispetto alla classe madre hanno il fine di
rendere questa matrice sparsa, una matrice sparsa dinamica.
I metodi sviluppati sono:
–
Mat2DIntSparsaDinamica aggiungiRiga(SparseIntMatrix1D riga)
Questo metodo restituisce una matrice identica a quella originaria con l'aggiunta di
una riga costituita dal vettore sparso “riga”, la riga aggiuntiva viene inserita dopo
l'ultima riga della matrice originaria.
Codice metodo aggiungiRiga(riga):
public Mat2DIntSparsaDinamica aggiungiRiga(SparseIntMatrix1D riga) throws
Exception
{
// controlla se la riga è
della stessa dimensione di quelle della matrice
if (riga.size()!=columns())
throw new Exception("dato non compatibile--> dim riga: "
+riga.size()+"
colonne mat: "+columns());
//nuova matrice, vuota con una riga in più
Mat2DIntSparsaDinamica nuova=new Mat2DIntSparsaDinamica(rows()+1,columns());
// estrapolo le coordinate dei valori diversi da zero
IntArrayList righe=new IntArrayList();
IntArrayList colonne=new IntArrayList();
IntArrayList valori=new IntArrayList();
getNonZeros(righe, colonne, valori);
// inserisco i dati estrapolati nella nuova matrice
for(int i=0;i<righe.size();i++)
nuova.setQuick(righe.get(i), colonne.get(i), valori.get(i));
// estrapolo le coordinate dei valori diversi da 0 dalla nuova riga
IntArrayList indici=new IntArrayList();
IntArrayList valoririga=new IntArrayList();
riga.getNonZeros(indici, valoririga);
// inserisco i dati diversi da 0 della riga nella nuova matrice (ultima riga)
for(int i=0;i<indici.size();i++)
nuova.setQuick(rows(), indici.get(i), valoririga.get(i));
return nuova;
}
Dal codice, possiamo vedere come solo gli elementi diversi da 0 della
matrice e della riga da aggiungere ,vengano effettivamente letti e scritti in
memoria durante l'elaborazione.
–
Mat2DIntSparsaDinamica aggiungiColonna(SparseIntMatrix1D
colonna)
Questo metodo restituisce una matrice identica a quella originaria con l'aggiunta
di una colonna costituita dal vettore sparso “colonna”, la colonna aggiuntiva
viene inserita dopo l'ultima colonna della matrice originaria.
–
Mat2DIntSparsaDinamica rimuoviRiga (int indice_riga)
Questo metodo restituice una matrice composta da tutte le righe della matrice
originaria, tranne la riga di indice “indice_riga”.
Codice metodo rimuoviRiga(indice_riga):
public Mat2DIntSparsaDinamica rimuoviRiga(int indice_riga) throws Exception
{
// controlla se l'indice della riga da eliminare è valido
if ((indice_riga<0)||(indice_riga>=rows()))
throw new Exception("indice non valido--> indice riga:
"+indice_riga+"
righe mat: "+rows());
//nuova matrice, vuota con una riga in meno
Mat2DIntSparsaDinamica nuova=new Mat2DIntSparsaDinamica(rows()-1,columns());
// estrapolo le coordinate dei valori diversi da zero
IntArrayList righe=new IntArrayList();
IntArrayList colonne=new IntArrayList();
IntArrayList valori=new IntArrayList();
getNonZeros(righe, colonne, valori);
// inserisco i dati
nella nuova matrice
for(int i=0;i<righe.size();i++)
{
if(righe.get(i)<indice_riga)
// non necessita lo shift
nuova.setQuick(righe.get(i), colonne.get(i), valori.get(i));
else
if(righe.get(i)>indice_riga) // necessita lo shift di riga
nuova.setQuick(righe.get(i)-1, colonne.get(i), valori.get(i));
}
return nuova;
}
In questo caso c'è da notare che la parte più importante del metodo
consiste nel ricopiare i dati della matrice originaria nella nuova matrice in
modo tale da lasciare intatte le righe di indice inferiore a quello della riga
da eliminare ed invece effettuare lo shift verso l'alto delle righe con indice
superiore .
descritto in pseudocodice ==> nuova_mat(i,j) = vecchia_mat( i+1, j )
–
Mat2DIntSparsaDinamica rimuoviColonna (int indice_colonna)
Questo metodo restituisce una matrice composta da tutte le colonne della matrice
originaria tranne la colonna di indice “indice_colonna”.
Per quanto riguarda il codice dei metodi aggiungiColonna(colonna) e
rimuoviColonna(indice_colonna), esso si può dire analogo rispettivamente
a quello di aggiungiRiga e rimuoviRiga.
Quindi, da un'analisi di questa implementazione, si deduce che rendere
dinamica una matrice Sparsa comporta meno operazioni, garantendo
maggiore velocità di esecuzione nell'aggiungere o rimuovere righe (o
colonne), rispetto ad una matrice normale.
Test delle classe Mat2DIntSparsaDinamica:
Questa classe rappresenta i mattoni con i quali si costruiranno le
implementazioni delle reti neurali, quindi sono state sviluppate delle
opportune classi di test per verificare l'efficacia dei vari metodi e non
ritrovarsi errori banali nelle fasi di sviluppo successive.
Codice del test
int[][] mat={{1,0,0,0,0},
// matrice 5x5 sparsa
{0,2,0,0,0},
{0,0,3,0,0},
{0,2,4,0,0},
{0,2,0,0,5}};
Prova prova=new Prova();
Mat2DIntSparsaDinamica sparsadin=new Mat2DIntSparsaDinamica(5,5);
for(int i=0;i<mat.length;i++)
for (int j=0;j<mat[i].length;j++)
sparsadin.setQuick(i, j, mat[i][j]);
sparsadin.trimToSize();
prova.stampaMatrice(sparsadin);
try{
// togliamo la colonna 3
Mat2DIntSparsaDinamica nuova1=sparsadin.rimuoviColonna(3);
prova.stampaMatrice(nuova1);
// togliamo la riga 0
Mat2DIntSparsaDinamica nuova2=nuova1.rimuoviRiga(0);
prova.stampaMatrice(nuova2);
// aggiungiamo la riga
SparseIntMatrix1D riga=new SparseIntMatrix1D(4);
riga.setQuick(2, 9); // [0 0 9 0]
Mat2DIntSparsaDinamica nuova3=nuova2.aggiungiRiga(riga);
prova.stampaMatrice(nuova3);
// aggiungiamo la colonna
SparseIntMatrix1D colonna=new SparseIntMatrix1D(5);
colonna.setQuick(4, 8); // [0 0 0 0 8]
Mat2DIntSparsaDinamica nuova4=nuova3.aggiungiColonna(colonna);
prova.stampaMatrice(nuova4);
}
catch(Exception e){
System.out.println(e.getMessage());
System.exit(1);
}
public void stampaMatrice(SparseIntMatrix2D sparsa)
{
System.out.println("-----------");
for(int i=0;i<sparsa.rows();i++) // stampa matrice
{
String s="";
for (int j=0;j<sparsa.columns();j++)
s+=" "+sparsa.getQuick(i, j);
System.out.println(s);
}
System.out.println("-----------");
}
di seguito sono riportati i risultati (output su console) del test:
----------1 0 0 0 0
0 2 0 0 0
0 0 3 0 0
0 2 4 0 0
0 2 0 0 5
-----------
--> matrice di partenza
----------1 0 0 0
0 2 0 0
0 0 3 0
--> dopo la rimozione della colonna 3
0 2 4 0
0 2 0 5
--------------------0 2 0 0
0 0 3 0
0 2 4 0
--> dopo la rimozione della riga 0
0 2 0 5
--------------------0 2 0 0
0 0 3 0
0 2 4 0
--> dopo l'aggiunta della riga [0 0 9 0]
0 2 0 5
0 0 9 0
--------------------0 2 0 0 0
0 0 3 0 0
0 2 4 0 0
--> dopo l'aggiunta della colonna [0 0 0 0 8]
0 2 0 5 0
0 0 9 0 8
-----------
NOTE: per completezza è stato verificato anche il lancio delle eccezioni
variando appositamente le dimensioni della riga e della colonna aggiunti,
rendendole (prima una e poi l'altra) incompatibili con la matrice.
Lo stesso per gli indici della riga e della colonna da rimuovere :
- ipotesi di indice negativo.
- ipotesi di indice > indice max.
Altre classi usate:
Un'altra classe che è stata utilizzata nel progetto è la classe OpVettori , in
questa classe sono stati sviluppati una serie di metodi (static) utili per
effettuare le varie operazioni sui vettori (vettori di double e vettori di
interi). In realtà solo una parte di questi metodi si può dire significativa
nell'implementazione delle reti neurali , essi sono:
-double[] aggiungiAVettore(double[] vet, double x)
aggiunge l'elemento x in coda al vettore vet
-double[] copiaDelVettore(double[] vet)
ci restituisce una copia del vettore vet
-double[] differenzaVettori(double[] vet1, double[] vet2)
calcola il vettore differenza tra vet1 e vet2
-double distanzaVettori(double[] v1, double[] v2)
restituisce la distanza tra due vettori
-double distanzaVettoriCoseno(double[] v1, double[] v2)
restituisce la distanza coseno tra due vettori
-boolean elementoPresente(double[] vet, double x)
ci indica se l'elemento x è presente nel vettore vet
-double[] motiplicaPerScalare(double[] vet, double x)
moltiplica il vettore vet per lo scalare x
-double norma(double[] v)
restituisce la norma del vettore, norma 2
-double norma1(double[] v)
restituisce la norma1 del vettore
-double prodottoScalare(double[] v1,double[]v2)
effettua il prodotto scalare dei due vettori
-double[] rimuoviDaVettore(double[] vet, int i)
rimuove l'elemento di indice i dal vettore vet
-double[] sommaVettori(double[] vet1, double[] vet2)
calcola il vettore somma di vet1 e vet2
-double[] vettoreRandom(int dim,double min, double max)
restituisce un vettore a caso di dimensione 3 e con coordinate appartenenti
all'intervallo (min:max)
-double[] vettoreRandom2D(double xmin, double xmax,double ymin,
double ymax)
restituisce un vettore a caso di dimensione 2 e con coordinate appartenenti
all'intervallo (xmin:xmax),(ymin:ymax)
-double[] verroreRandom3D(....
analogo al metodo vettoreRandom2D , restituisce un vettore 3D
-double[] vettoreRandomSfera(double r)
restituisce un vettore a caso di dimensione 3 e con coordinate interne ad una sfera di
raggio r e centro nell'origine
note: Anche per la classe OpVettori è stato effettuato il testing dei metodi,
ed i test sono stati superati.
2.2 Interfaccia Rete Neurale
A prescindere dalla tipologia di rete neurale implementata , ci sono delle
caratteristiche generali comuni ad ogni tipo, come ad esempio l'esser
costituite da nodi oppure la tendenza per cui man mano che la rete
apprende, i nodi tendono a formare dei clusters.
Queste caratteristiche comuni, in un linguaggio Object Oriented come Java
possono essere rappresentate da un'interfaccia, ovvero una sorta di
contratto che obbliga le classi che implementano l'interfaccia a fornire
un'implementazione dei metodi in essa indicati.
Il vantaggio di usare un'interfaccia è soprattutto quello di poter sviluppare
del codice senza la necessità di fare riferimento ad una classe ben definita
di oggetti.
Per esempio le chiamate di metodi che prendono come argomento un
riferimento all'interfaccia, possono essere fatte prendendo come argomento
qualsiasi oggetto che sia definito da una classe che implementi tale
interfaccia.
Inoltre, anche se si fa riferimento ad un interfaccia per chiamare un
metodo, in realtà verrà eseguito il codice della classe di cui fa parte
l'oggetto, ciò è detto polimorfismo, una caratteristica peculiare dei
linguaggi Object Oriented molto utile per la riusabilità del codice e
l'estensione delle applicazioni.
Costituendo l'interfaccia ReteNeurale si vuole ottenere proprio questo,
usare lo stesso codice per i vari tipi di reti neurali implementate.
Ciò è molto utile in questo progetto, perchè sono state sviluppate classi
relative alla sperimentazione che devono essere applicate a tutti i tipi di
reti neurali per ottenere un confronto coerente delle performance.
Anche le classi sviluppate per la visualizzazione grafica della rete neurale
e della sua evoluzione, contengono metodi che richiedono come
argomento un riferimento di tipo ReteNeurale.
Metodi dell'interfaccia ReteNeurale:
- public void aggiungiDato(double[] dato) throws Exception;
sottopone alla rete neurale un nuovo dato di input.
- public int getDimensione();
restituisce il numero di nodi della rete neurale.
- public int getDimensioneNodi();
restituisce la dimensione di ogni nodo della rete neurale ,cioè la
dimensione dello spazio di stato della rete.
-
public double[] getNodo(int indice) throws
IndexOutOfBoundsException;
restituisce le coordinate del nodo identificato dall'indice “indice”
-
public int[] ricerca_connessi(int nodo);
restituisce un vettore che contiene gli indici dei nodi connessi al nodo
-
public int ricercaVincitore(double[] input);
restituisce l'indice del nodo più vicino al dato di input
-
public double getErroreGlobale(ArrayList<double[]> dataset);
restituisce l'errore tra i nodi della rete e i dati del dataset
-
public ArrayList<int[]> getClusters();
restituisce i gruppi di nodi (clusters) formati nella rete
2.3 Classe Gng.java
Implementazione della rete neurale GNG:
ReteNeurale
Gng
La classe Gng contenuta nel package “retineurali” rappresenta
l'implementazione in linguaggio java di una rete neurale di tipo
Growing Neural Gas.
Questa classe implementa i metodi dell'interfaccia ReteNeurale , ognuno
dei quali è stato sviluppato tenendo conto delle particolari caratteristiche
della GNG.
Dall'algoritmo Gng descritto nel capitolo precedente (par 1.4), si evincono
alcune variabili di stato necessarie al corretto funzionamento della rete:
–
L'insieme dei nodi della rete e la rispettiva posizione.
–
l'insieme delle connessioni e la rispettiva età.
–
il vincitore attuale s1 ed il suo secondo s2.
–
l'insieme degli errori locali relativi ad ogni nodo
Inoltre si devono tener presente i parametri costanti :
–
εb , εn
–
αmax
–
λ
–
α
–
d
I valori di default dei parametri sono [2]:
λ=100 , εb=0.2 , εn=0.006 , α=0.5 , αmax=50 , d=0.995
Le variabili d'istanza della classe Gng rappresentano appunto le variabili di
stato ed i parametri della rete.
L'ArrayList nodi rappresenta l'insieme dei nodi di cui è composta la rete.
Ogni nodo della rete è identificato da un indice intero univoco ed è
caratterizzato da una serie di valori di tipo double che ne rappresentano la
posizione all'interno dello spazio di stato, quindi viene stabilita la
corrispondenza:
nodo ==> (int indice , double[] valori).
La struttura dati rappresentata dal contenitore generico
ArrayList<double[]> (package java.util) è quindi adatta a
rappresentare la lista dei nodi.
La variabile d'istanza eta_connessioni è la struttura dati che contiene
l'età di ogni connessione della rete, in pratica stabilisce la corrispondenza:
connessione ==> ([nodo 1 , nodo 2 ], età)
Una matrice è la struttura dati ideale per implementare tale corrispondenza.
Tenendo presente che durante l'apprendimento il numero dei nodi della
rete GNG varia, e che l'interconnessione tra gli stessi, di solito, è ben
lontana dall'esser totale (la non connessione è identificata da età=0), si
evince che una matrice dinamica e sparsa è adatta a rappresentare questa
variabile di stato.
Costruttori della classe Gng
Come visto dall'algoritmo Gng (passo 1), la rete neurale GNG deve essere
inizializzata con solo due nodi.
La classe Gng possiede 4 costruttori :
- public Gng (int dim)
Richiede soltanto di indicare la dimensione del dataset e dei nodi della
rete, cioè dello spazio di stato.
I due nodi iniziali vengono scelti in modo casuale tramite il metodo
double[] verroreRandom(dim,0 , 0.5) della classe OpVettori (package
vettori_matrici), inoltre vengono inizializzate le altre variabili d'istanza e
vengono settati i parametri della rete con i valori di default indicati nel
Fritzke95.
- public Gng (double[] nodo1, double[] nodo2)
Permette di impostare i nodi iniziali della rete, (magari presi a caso dal
dataset di cui si vuole effettuare il clustering).
e poi i costruttori :
–
public Gng (int dim,int l ,double eb ,double en,double
alfa ,int alfa_max, double d)
–
public Gng (double[] nodo1,double[] nodo2, int l ,
double eb ,double en ,double alfa ,
int alfa_max , double d)
Analoghi a quelli visti in precedenza , che però offrono la possibilità di
inizializzare i parametri caratteristici della rete con valori a scelta.
Metodi implementati in Gng.java
Tra i metodi dell'interfaccia ReteNeurale che sono stati implementati nella
classe Gng è particolarmente significativo il metodo:
int[] ricerca_connessi(int indice_nodo) , che restituisce i
connessi al nodo identificato dall'indice “indice_nodo”.
Questo metodo viene richiamato spesso, sia all'interno della classe stessa
(perchè richiesto in molti passi dell'algoritmo Gng : passi 4 , 6 , 9.2 ), sia
dalle altre classi che usano la classe Gng , come ad esempio quelle adibite
alla visualizzazione grafica della rete.
Per trovare i nodi connessi si crea una vista della riga di indice
“indice_nodo” dalla matrice eta_connessioni; essendo la matrice
sparsa, anche questa riga sarà un vettore sparso.
I nodi connessi sono identificati dagli indici dei valori diversi da 0
contenuti in questo vettore (perchè solo le età≠0 rappresentano una
connessione).
Un altro metodo molto importante è:
public ArrayList<int[]> getClusters() che restituisce una lista
contenente i vari gruppi di nodi identificati dalla topologia della rete .
Questa informazione è fondamentale se si usa la rete neurale GNG per il
clustering di dati.
Un esempio dell'applicazione di getClusters() è :
Lo pseudocodice del metodo getClusters() è:
l= lista dei cluster , inizialmente vuota
vis = vettore dei nodi visitati , inizialmente vuoto
per ogni nodo s della rete
{
se il nodo non è in vis
{
nodicluster = vettore dei nodi che fanno parte del cluster,
inizialmente contiene solo s
q = pila dei nodi da espandere, inizialmente contiene solo s
finchè q non è vuoto
{
estrai e togli un elemento u dalla pila q
per ogni nodo v collegato a u
{
se il nodo v non è già in nodicluster
{
aggiungi v al vettore
nodicluster
aggiungi v ai nodi da espandere (pila q)
}
}
}
aggiungi il vettore nodicluster alla lista l
aggiungi i nodi contenuti in nodicluster al vettore dei nodi
visitati vis
}
}
il risultato è la lista dei cluster l
gli altri metodi implementati sono:
public int ricercaVincitore(double[] input) che restituisce
l'indice del nodo più vicino al dato di input .
Viene scandito l'intero ArrayList nodi , per ognuno di essi si calcola la
distanza con l'input tramite il metodo distanzaVettori(input,nodo) della
classe OpVettori (package vettori_matrici) e si tiene traccia dell'indice del
nodo avente distanza minima.
public double getErroreGlobale(ArrayList<double[]>
dataset) che restituisce l'errore tra i nodi della rete e i dati del dataset.
Per ogni dato del dataset trova il nodo della rete meno distante
richiamando il metodo ricercaVincitore(input) visto in precedenza , somma
la relativa distanza ad una variabile e che alla fine sarà l'errore globale
della rete
public void aggiungiDato(double[] dato) throws Exception
Sottopone alla rete neurale un nuovo dato di input.
Prima effettua un controllo sulla dimensione del dato , se non è uguale a
quella dei nodi della rete lancia un'eccezione.
Una volta accertato che l'input è compatibile, chiama il metodo
algoritmoGng(input) che applica l'algoritmo Gng , ciò comporta un
adaptation step della rete neurale.
public double[] getNodo(int indice) throws
IndexOutOfBoundsException
richiama il metodo nodi.get(indice) , ma prima fa un controllo sull'indice e
se non è valido lancia un'eccezione.
public int getDimensione()
richiama il metodo nodi.size()
public int getDimensioneNodi()
richiama il metodo nodi.get(0).size()
Metodo di implementazione dell'algoritmo GNG in Gng.java
il metodo algoritmoGNG(double[] input) rappresenta il metodo
più importante della classe perchè in esso è sviluppata l'implementazione
dell'algoritmo che descrive l'apprendimento della rete neurale GNG.
codice metodo
private void algoritmoGNG(double[] input)
{
int[] s=ricercaPiuVicini(input);
s1=s[0];
//passo 2 GNG Algorithm
s2=s[1];
int[]connessi_vin=ricerca_connessi(s1);
int[] old=incrementaEtaConnessioni(s1,connessi_vin);//passo 3 GNG Algorithm
aggiornaErrore(s1,input);
// passo 4 GNG
Algorithm
muoviVincitore(input,s1);
// passo 5 GNG Algorithm
muoviConnessiVincitore(input,connessi_vin);
resetConnessione(s1,s2);
// passo 6 GNG Algorithm
rimuoviConnessioni(old);
// passo 7 GNG Algorithm
if((n%l)==0)
// passo 8 GNG Algorithm
{
int q=ricercaNodoMaxErrore();
// passo 8.1 GNG Algorithm
int[] connessi_max_errore=ricerca_connessi(q);
int f=ricercaNodoMaxErrore(connessi_max_errore);
double[] nuovo=calcolaNodoIntermedio(q,f);
nodi.add(nuovo);
// passo 8.2 GNG Algorithm
collegaNuovoNodo((getDimensione()-1),q,f);
// passo 8.3 GNG Algorithm
errore[q]=alfa*errore[q];
// passo 8.4 GNG Algorithm
errore[f]=alfa*errore[f];
errore=OpVettori.aggiungiAVettore(errore,errore[q]);
eta_connessioni.trimToSize();
// utile a contenere la memoria occupata
}
for(int i=0;i<errore.length;i++) // passo 9 GNG Algorithm
errore[i]=d*errore[i];
}
Come si vede dal codice quasi tutti i passi dell'algoritmo Gng sono stati
sviluppati in un rispettivo metodo.
La suddivisione dell'algoritmo in più metodi rende l'architettura del codice
modulare, consentendo maggiore flessibilità ai cambiamenti
nell'implementazione di uno o più passi .
Inoltre, essendoci maggiore frammentazione delle funzionalità, nello
sviluppo di ogni metodo si sono dovute affrontare problematiche meno
complesse, con soluzioni semplici, e quindi meno possibilità di ritrovarsi
errori in fase di compilazione.
L'approccio modulare è utile anche in fase di debug, la minor presenza di
istruzioni annidate facilita l'individuazione delle parti di codice che che
provocano gli errori in fase di esecuzione (runtime).
La modularità porta vantaggi anche rispetto alla riusabilità del codice,
perchè una maggiore semplificazione dei metodi di una classe madre
comporta una maggiore probabilità del loro utilizzo da parte delle classi
derivate.
Osservando il codice del metodo, si nota che il nodo più vicino al dato di
input (vincitore) ed il secondo, vengono ricavati nel medesimo metodo
int[] ricercaPiuVicini (input), ciò è stato fatto per ragioni di efficienza,
perchè usare una sola scansione di tutti i nodi per ricavare le relativa
distanza, invece che due (se si usavano due metodi distinti), comporta un
guadagno in termini di velocità di esecuzione dell'algoritmo; questo
aspetto risulta essere cruciale nel caso che la rete neurale debba elaborare
molti dati e di conseguenza giunga ad avere un numero di nodi molto
elevato.
Lo stesso tipo di ragioni sono alla base dell'utilizzo del vettore old, che
contiene i nodi con cui il vincitore (nodo più vicino) ha una connessione
ormai scaduta che deve essere eliminata.
Le connessioni indicate da old sono state individuate durante l'incremento
dell'età delle connessioni che partono dal vincitore ( passo 4), quindi non
c'è bisogno di ricercare le stesse quando si procede all'eliminazione delle
connessioni vecchie ( passo 8). Nello stesso ciclo di scansione si fanno
entrambe le cose (incremento età e ricerca connessioni scadute ) riducendo
quindi il tempo di elaborazione.
2.4
Classe NeuralGas.java
Implementazione della rete neurale NEURAL GAS:
ReteNeurale
Gng
NeuralGas
La classe NeuralGas implementa in linguaggio java una rete neurale di
tipo Neural Gas. Questa classe eredita dalla classe Gng ed implementa
quindi i metodi dell'interfaccia ReteNeurale.
Rispetto alla classe Gng, cambiano le variabili d'istanza relative ai
parametri:
Queste variabili contribuiscono alla determinazione di alcuni importanti
parametri di apprendimento della rete che cambiano ad ogni passo di
apprendimento, in particolare relativamente all'algoritmo Neural Gas visto
nel capitolo precedente (par 1.3):
l_ng = li · (lf / li)
t/tmax
e_ng = ei · (ef / ei)
t/tmax
eta_max = ti · (tf / ti)
t/tmax
==>
coeff. apprendimento λ
==>
coeff. apprendimento ε
==>
età massima connessioni T
I valori di default di queste variabili sono: li = 30 , lf = 0.01 , ei = 0.3 ,
ef = 0.05 , ti = 20 , tf = 200 [1].
C'è da notare che la classe madre Gng possiede già una variabile d'istanza
relativa all'età massima (int alfa_max), la scelta di aggiungere un'altra
variabile (double eta_max) è dovuta principalmente al vantaggio di
osservare meglio i valori che essa assume durante l'apprendimento (tramite
breakpoint in fase di debug); le due variabili, come si vedrà in seguito,sono
comunque correlate da un semplice cast.
Costruttori della classe NeuralGas.java
I costruttori della classe NeuralGas differiscono da quelli della classe Gng,
perchè i nodi iniziali della rete sono più di due:
- public NeuralGas (int dim, int num_nodi)
Richiede, di indicare la dimensione dello spazio di stato ed il numero di
nodi di cui deve essere composta la rete.
I due nodi iniziali vengono scelti in modo casuale tramite il metodo
double[] verroreRandom(dim, 0, 1.0) della classe OpVettori (package
vettori_matrici), quindi all'interno di un ipercubo di lato 1, inoltre
vengono inizializzate le altre variabili d'istanza e vengono settati i
parametri della rete con i valori di default indicati.
- public NeuralGas (ArrayList<double[]> nodirete)
Permette di impostare i nodi della rete, (magari presi a caso dal dataset di
cui si vuole effettuare il clustering), che cui cardinalità rimarrà costante per
tutta la durata dell'apprendimento.
E poi ci sono i costruttori:
- public NeuralGas(ArrayList<double[]> nodirete,double li
,double lf,double ei,double ef,int ti,int tf,int tmax)
- public NeuralGas (int dim,int num_nodi,double li
,double lf,double ei,double ef,int ti,int tf,int tmax)
Analoghi a quelli visti in precedenza , che però offrono la possibilità di
inizializzare i parametri caratteristici della rete con valori a scelta.
Metodi implementati in NeuralGas.java
Rispetto alla Gng, viene aggiunto il metodo getNumeroSteps() che
restituisce il numero di adaptation steps effettuati.
Inoltre vene sovrascritto il metodo aggiungiDato, dove una volta
accertato che l'input è compatibile, viene chiamato il metodo
algoritmoNeuralGas(input) che applica l'algoritmo Neural Gas:
private void algoritmoNeuralGas(double[] input)
{
l_ng=li*Math.pow((lf/li),(double)t/tmax);
e_ng=ei*Math.pow((ef/ei),(double)t/tmax);
eta_max=ti*Math.pow((double)tf/ti,(double)t/tmax);
alfa_max=(int)(eta_max);
int[] k_nodi=ordinaNodi(input);
s1=k_nodi[0];
s2=k_nodi[1];
muoviNodiRete(input,k_nodi);
//passo 2 NG Algorithm
resetConnessione(s1,s2);
// passo 3 NG Algorithm
// passo 4 NG Algorithm
int[]connessi_vin=ricerca_connessi(s1);
// passo 5 NG Algorithm
int[] old=incrementaEtaConnessioni(s1,connessi_vin);
rimuoviConnessioniVecchie(s1,old);
}
// passo 6 NG Algorithm
2.5
Implementazione delle reti asimmetriche in Java
ReteNeurale
Gng
NeuralGas
GngAsimmetrica
NeuralGasAsimmetrica
Le classi implementate: GngAsimmetrica e NeuralGasAsimmetrica
ereditano dalle rispettive classi e sovrascrivono i vari metodi in cui appare
l'aggiornamento di età delle connessioni.
La GngAsimmetrica sovrascrive i metodi protected della classe Gng :
resetConnessione(int a, int b)
eliminaConnessione(int a, int b)
incrementaEtaConnessione(int a, int b)
boolean nodoIsolato(int nodo)
La NeuralGasAsimmetrica similmente sovrascrive gli stessi metodi dalla
classe NeuralGas, tranne nodoIsolato ,che in NeuralGas non è presente.
Capitolo 3
IMPLEMENTAZIONE DELL'ALGORITMO
FUZZY
3.1 Algoritmo di apprendimento fuzzy
Una versione diversa ed innovativa della rete neurale GNG è la sua
versione fuzzy.
La logica di tipo fuzzy prevede che alle connessioni tra i nodi venga
associato un certo peso p Є R, e non una determinata età come visto in
precedenza nella GNG versione classica.
Quando si sottopone un dato di input alla rete neurale Fuzzy, viene cercato
il nodo più vicino (come nella Gng), e vengono aggiornati i pesi delle
connessioni tra il suddetto nodo e tutti gli altri nodi della rete.
Il peso della connessione tra il vincitore (nodo più vicino) ed un altro
nodo viene incrementato maggiormente, se la distanza tra quest'ultimo ed
il dato di input è minore, ovvero il peso della connessione tra il vincitore
ed il secondo nodo più vicino all'input verrà incrementato maggiormente
rispetto al peso della connessione tra il vincitore ed il terzo e così via....
Successivamente tutti i nodi della rete (compreso il vincitore), vengono
avvicinati all'input; lo spostamento è crescente rispetto al peso della
connessione.
Il peso delle varie connessioni è fondamentale per capire la topologia della
rete, infatti anche se tutte le connessioni hanno un certo peso diverso da
zero, saranno le connessioni con peso maggiore ad essere significative
nello stabilire il rapporto di vicinanza tra nodi necessario per il clustering.
Il peso associato alle connessioni inoltre, è importante anche nella fase di
avvicinamento dei nodi stessi ai dati del dataset di input (convergenza
della rete) perchè lo spostamento nello spazio di stato dei nodi dipende
appunto dal peso delle connessioni tra quest'ultimi ed il vincitore.
Come si può notare, un'importate differenza rispetto alla Gng classica è
che ,nella versione fuzzy , ad ogni adaptation step dobbiamo tener conto di
tutti i nodi della rete e non solo di alcuni, perchè ogni volta che alla rete
fuzzy viene sottoposto un dato di input, tutti gli "n" nodi vengono spostati
e tutti i pesi tra gli "n-1" nodi ed il vincitore vengono aggiornati.
Anche nella Gng versione Fuzzy, i nodi iniziali sono 2 e si aggiungono
nuovi nodi alla rete durante l'apprendimento: i nuovi nodi vengono
aggiunti basandosi su alcune misure statistiche dipendenti dall'evoluzione
passata della rete , ma anche tenendo conto del peso relativo ad alcune
connessioni; perciò, l'importanza di una corretta gestione dei pesi delle
connessioni, si nota anche nella fase di crescita della rete.
Algoritmo FUZZY-GNG:
(1)
La rete è composta inizialmente da due nodi “a” e “b” aventi
posizione casuale all'interno dello spazio di stato:
ωa ε Rⁿ
, ωb ε Rⁿ .
(2)
viene sottoposto alla rete un dato di input “ζ”.
(3)
trovare il nodo più vicino "s1" al dato di input
(4)
Aggiungere il quadrato della distanza tra il dato in input ed il
nodo s1, ad una variabile locale (errore) che fa riferimento ad
s1:
(5)
Δerror(s1) = (|| ωs1 – ζ ||)²
incrementare i pesi delle connessioni tra s1 e gli altri nodi della
rete di un incremento:
Δps1,sn = 1 – (
1
-an
1+ e
con an = || ζ – ωsn ||
)
e normalizzare i pesi.
(6)
muovere i nodi della rete verso il dato di input di uno
spostamento pari a:
Δωs1 = b1 · e‾ kw · (1 – Ps1,s1) · || ζ – ωs1 ||
Δωsn = b2 · e‾ kw · (1 – Ps1,sn)
· || ζ – ωn ||
per il nodo s1
per gli altri nodi
con Ps1,sn => peso della connessione tra s1 ed il nodo sn.
(7)
Se il numero di dati sottoposti alla rete finora è un multiplo
intero del parametro “λ”, aggiungere un nuovo nodo alla rete
nel seguente modo:
(7.1) trovare il nodo 'q' che ha accumulato maggior errore
(Δerror)
(7.2) inserire il nuovo nodo 'r' a metà tra il nodo q el il nodo 'f '
a cui corrisponde il maggiore prodotto ( error(f) · Pq,f ) :
ωr = 0,5 · (ωq + ωf)
(7.3) impostare il peso delle connessioni tra il nodo r ed i nodi
q e f, come il peso della connessione tra q ed f:
pr,q = pq,f ;
pr,f = pq,f
settare a zero il peso della connessione tra q ed f:
pq,f = 0
(7.4) ridurre gli errori associati a q ed f, moltiplicandoli per
una costante α < 1 , inizializzare l'errore associato ad r
con il nuovo valore dell'errore associato a q.
(8)
ridurre gli errori associati a tutti i nodi, moltiplicandoli per una
costante d < 1.
(9)
se un criterio di stop non è stato soddisfatto, ritorna al passo 1.
note:
Vediamo dall'algoritmo, che la funzione di incremento dei pesi è una
funzione logistica , che ha un andamento decrescente rispetto all'aumento
della distanza .
La funzione che rappresenta lo spostamento dei nodi verso l'input invece è
una funzione esponenziale con argomento negativo del tipo: eˉ
(1 – peso)
,
essa è crescente per pesi crescenti. Ciò significa che lo spostamento è più
pronunciato se la distanza tra e dato di input è minore (nodo più vicino)
3.2 Strutture dati utilizzate
Relativamente all'implementazione di una rete neurale Gng versione
Fuzzy, serve una matrice che rappresenti i pesi delle connessioni tra i vari
nodi della rete.
A differenza della matrice rappresentativa dell'età delle connessioni vista
nell'implementazione delle reti neurali GNG e NG (capitolo 2), la matrice
rappresentativa dei pesi sarà densa e conterrà valori di tipo double
Per quanto riguarda la creazione e l'utilizzo di matrici dense, la libreria
Parallel-Colt mette a disposizione le seguenti classi:
–
cern.colt.matrix.tdouble.impl.DenseDoubleMatrix1D
–
cern.colt.matrix.tdouble.impl.DenseDoubleMatrix2D
DenseDoubleMatrix2D implementa una matrice densa che contiene
valori di tipo double, questa classe mette a disposizione alcuni metodi
relativi alla possibilità di attuare trasformate di tipo DFT (discrete Fourier
trasformate) o DHT (discrete Hartley trasformate) sulla matrice o sulle sue
righe e/o colonne.
DenseDoubleMatrix1D implementa un vettore denso che è utile ad
esempio nel rappresentare una riga o una colonna della matrice stessa.
Però, visto che il numero di nodi della rete Fuzzy-Gng cresce durante
l'apprendimento, servono una matrice dense che sia anche dinamica,
ovvero che sia possibile variarne le dimensione.
Per implementare tale matrice ho sviluppato la classe:
Mat2DDoubleDensaDinamica
(matrice densa dinamica):
DenseDoubleMatrix2D
Mat2DDoubleDensaDinamica
La classe Mat2DDoubleDensaDinamica eredita dalla classe
DenseDoubleMatrix2D del package
cern.colt.matrix.tdouble.impl della libreria Parallel-Colt,
quindi è un'implementazione valida di una matrice densa.
I metodi che sono stati aggiunti rispetto alla classe madre hanno il fine di
rendere questa matrice densa , una matrice densa dinamica.
Lo scopo di ogni metodo è lo stesso visto per la classe
Mat2DIntSparsaDinamica (par 2.1 pag 26), cioè permettere le operazioni
di aggiunta e rimozione di righe e colonne, per rendere la matrice
dinamica. La maggiore differenza rispetto all'implementazione di
Mat2DIntSparsaDinamica è che ,essendo di fronte ad una matrice densa ,
dovremmo tener conto di tutti i valori della matrice durante le operazioni
di ridimensionamento, ciò comporta una maggiore lentezza nella loro
esecuzione come si può facilmente notare nel codice del metodo
aggiungiRiga(riga):
public Mat2DDoubleDensaDinamica aggiungiRiga(DenseDoubleMatrix1D riga) throws
Exception
{
if (riga.size()!=columns()) // controlla se la riga è della stessa dimensione di
quelle della matrice
throw new Exception("dato non compatibile--> dim riga:
"+riga.size()+"
colonne mat: "+columns());
//nuova matrice, vuota con una riga in più
Mat2DDoubleDensaDinamica nuova=new Mat2DDoubleDensaDinamica(rows()+1,columns());
for (int i=0; i<rows(); i++)
for (int j=0; j<columns(); j++)
nuova.setQuick(i,j,getQuick(i,j));
<== vengono elaborati tutti i valori
for(int i=0;i<riga.size();i++) //inserisco i dati della riga nella nuova matrice
nuova.setQuick(rows(), i, riga.getQuick(i));
return nuova;
}
Anche l'occupazione di memoria è maggiore, sia perchè la matrice è densa
sia perchè contiene valori di tipo double che occupano maggiore quantità
di memoria rispetto agli interi (il double occupa 8 byte).
Come visto per la matrice Mat2DIntSparsaDinamica, la classe è stata
sottoposta ad un test per verificarne le funzionalità, il codice del test è
analogo a quello riportato nel paragrafo 2.1.
Risultati del Test su Mat2DDoubleDensaDinamica
--------------------1.1 0.0 0.0 0.0 0.0
0.0 2.2 0.0 0.0 0.0
0.0 0.0 3.3 0.0 0.0
--> matrice di partenza
0.0 2.2 4.4 0.0 0.0
0.0 2.2 0.0 0.0 5.5
----------------------------------------1.1 0.0 0.0 0.0
0.0 2.2 0.0 0.0
0.0 0.0 3.3 0.0
0.0 2.2 4.4 0.0
0.0 2.2 0.0 5.5
---------------------
--> dopo la rimozione della colonna 3
--------------------0.0 2.2 0.0 0.0
0.0 0.0 3.3 0.0
--> dopo la rimozione della riga 0
0.0 2.2 4.4 0.0
0.0 2.2 0.0 5.5
----------------------------------------0.0 2.2 0.0 0.0
0.0 0.0 3.3 0.0
0.0 2.2 4.4 0.0
--> dopo l'aggiunta della riga [0.0 0.0 9.0 0.0]
0.0 2.2 0.0 5.5
0.0 0.0 9.0 0.0
----------------------------------------0.0 2.2 0.0 0.0 0.0
0.0 0.0 3.3 0.0 0.0
0.0 2.2 4.4 0.0 0.0
--> dopo l'aggiunta della colonna [0.0 0.0 0.0 0.0 8.0]
0.0 2.2 0.0 5.5 0.0
0.0 0.0 9.0 0.0 8.0
---------------------
Package vettori_matrici
Le matrici Mat2DIntSparsaDinamica e Mat2DDoubleDensaDinamica
nonché la classe OpVettori fanno parte del package vettori_matrici che
offre appunto classi per la gestione di vettori e matrici.
3.3 Classe FuzzyGng.java
Implementazione della rete neurale FUZZY-GNG
ReteNeurale
Gng
FuzzyGng
NeuralGas
La classe FuzzyGng contenuta nel package “retineurali” rappresenta
l'implementazione in linguaggio java della versione fuzzy di una rete
neurale GNG (Growing Neural Gas).
Questa classe rappresenta una rete che ha molti meccanismi in comune con
la GNG come si evince osservando i due algoritmi, per questo motivo
eredita dalla classe Gng. Ciò comporta il vantaggio di non dover ripetere
lo sviluppo del codice relativo alle funzionalità già sviluppate in Gng.java.
Analizzando più attentamente l'algoritmo fuzzy, si notano però alcune
differenze sostanziali rispetto alla Gng, di cui si è dovuto tener conto nello
sviluppo della classe FuzzyGng.
Queste differenze si riperquotono subito nelle variabili d'istanza della
classe, che devono rappresentare i nuovi parametri: b1, b2 , kw; e
soprattutto la matrice rappresentativa dei pesi delle connessioni.
La matrice dei pesi , al contrario di quella che rappresenta l'età nella classe
Gng , è una matrice densa perchè ad ogni adaptation step vengono
incrementati tutti i pesi delle connessioni tra il vincitore e gli altri nodi
della rete, ciò implica che conterrà quasi tutti valori diversi da 0.
Allo stesso tempo è una matrice di double perchè la normalizzazione dei
pesi (passo 5) produce valori compresi tra 0 e 1, ed è dinamica perchè il
numero dei nodi della rete, durante l'apprendimento, tende ad aumentare.
Costruttori classe FuzzyGng
I costruttori della classe FuzzyGng sono molto simili a quelli della classe
Gng ; differiscono per lo più sui parametri che si possono impostare (b1,
b2 , kw) per la FuzzyGng, al posto di (λ , εb , εn , α , αmax , d ) per la
Gng.
Sono considerati di default : b1 = 0.2 , b2 = 0.006 , kw = 9.0
Metodi della classe FuzzyGng.java
I metodi che sono stati sviluppati in aggiunta a quelli della classe Gng
sono:
int[] ricerca_connessi(int indice_nodo,double pesosoglia)
Il peso soglia indica il valore minimo del peso, che una connessione deve
avere per rappresentare due nodi connessi topologicamente (facenti parte
dello stesso cluster).
In questo metodo si effettua una scansione della riga relativa al nodo di
indice "indice_nodo" all'interno della matrice dei pesi in cerca di pesi con
valore superiore al "pesosoglia" per stabilire quali sono i nodi connessi.
L'indice di colonna di un peso superiore al peso soglia identifica un nodo
connesso. Questo metodo di ricerca dei connessi viene usato nel metodo
getClusters(double pesosoglia) per ottenere i clusters.
double getPeso(int nodoa, int nodob)
restituisce il peso della connessione tra il nodo "nodoa" ed il nodo
"nodob".
public void aggiungiDato(double[] dato) throws Exception
Dopo aver fatto i dovuti controlli sulla dimensione del dato di input
chiama il metodo algoritmoFuzzyGng(input) che applica l'algoritmo
fuzzy.
Implementazione dell'algoritmo Fuzzy in FuzzyGng.java
Il metodo algoritmoFuzzyGng rappresenta il metodo più importante
della classe perchè in esso è sviluppata l'implementazione dell'algoritmo
fuzzy:
codice metodo
private void algoritmoFuzzyGng(double[] input)
{
int s1=ricercaVincitore(input);
aggiornaErrore(s1,input);
//passo 2 fuzzyGNG
//passo 3 fuzzyGNG
double somma=incrementaPesi(s1,input); // passo 4 fuzzyGng
normalizzaPesi(somma,s1);
// passo 4 fuzzyGng normalizzazione
muoviNodi(input,s1);
// passo 5 fuzzyGng
if((n%l)==0)
// passo 6 fuzzyGng
{
//rimuoviNodiIsolati(); // rimuove i nodi che tendono a rimanere isolati
int q=ricercaNodoMaxErrore();
// passo 6.1 fuzzyGng
int f=ricercaSecondaUnità(q);
double[] nuovo=calcolaNodoIntermedio(q,f);
// passo 6.2 fuzzyGng
nodi.add(nuovo);
collegaNuovoNodo((getDimensione()-1),q,f);
errore[q]=alfa*errore[q];
// passo 6.3 fuzzyGng
// passo 6.4 fuzzyGng
errore[f]=alfa*errore[f];
errore=OpVettori.aggiungiAVettore(errore,errore[q]);
}
for(int i=0;i<errore.length;i++) // passo 7 fuzzyGng
errore[i]=d*errore[i];
}
Valgono le stesse considerazioni fatte nella descrizione del metodo di
implementazione dell'algoritmo in Gng.java, a riguardo dei vantaggi nella
modularità del codice.
note: c'è il metodo commentato rimuoviNodiIsolati che attualmente non è
stato utilizzato, ma che potrebbe essere utile in sviluppi futuri.
Effetti della distanza sulla funzione di incremento dei pesi:
La funzione di incremento dei pesi è una funzione logistica:
Δps1,sn = 1 – (
1
1+ e -an
)
l'esponenziale decrescente al denominatore 1+ e-an dipende dalla distanza
tra il nodo (sn) a cui fa riferimento il peso da incrementare ed il dato di
input:
dist = an = || ζ – ωsn ||
con
Se questa distanza è eccessiva, e
- dist
ζ = input
risulta essere davvero molto piccolo.
Dalle prove effettuate sulla rete fuzzy si è riscontrato, in fase di debug ,
che anche per dataset non eccessivamente dispersivi (dati non troppo
distanti tra loro), il valore assunto da e- dist risulta essere talmente piccolo
che viene approssimato a zero durante l'esecuzione.
Ciò comporta un errore grave perchè la funzione logistica si annulla :
se e- dist
> 0
1–(
1
1+ e-dist
)
>
1-(
1
1
)= 0
Ciò annulla l'incremento dei pesi , e di conseguenza pregiudica
l'apprendimento della rete neurale fuzzy-gng.
Durante le prove infatti si è assistito ad un errore non decrescente quando
la distanza tra dati del dataset era maggiore .
Ad esempio la prova di clustering su dati che nello spazio 3D sono
all'interno di 3 cubi distanti tra loro, fatta con la FuzzyGng, da come esito
una rete che non apprende, se i cubi sono distanziati tra loro di 50.
Una possibile soluzione è inserire un nuovo parametro alla fuzzy del tipo:
1
1–(
1+
e -( g · dist)
)
con 0 < g < 1
Il parametro “g” può abbassare l'ordine di grandezza dell'argomento
dell'esponenziale decrescente.
Es: se dist=50 e g=0.1 ===>
e
-( g · dist)
= e
verrà approssimato a zero durante l'esecuzione.
-( 5 )
che almeno non
3.4 Implementazione versione asimmetrica
La classe FuzzyGngAsimmetrica sovrascrive semplicemente il metodo
protected della classe FuzzyGng impostaPeso, cioè:
protected void impostaPeso(int a, int b, double peso)
{
}
pesi.setQuick(a, b, peso);
al posto del metodo della FuzzyGng (simmetrica):
protected void impostaPeso(int a, int b, double peso)
{
pesi.setQuick(a, b, peso);
pesi.setQuick(b, a, peso);
}
Capitolo 3
VALUTAZIONE SPERIMENTALE
4.1 Convergenza al variare dei parametri e confronto
GNG
errore
Andamento dell'errore al variare del parametro εb
80
70
60
50
Єb=0.05
Єb =0.2
Єb=0.8
40
30
20
10
0
n iterazioni
errore
Andamento dell'errore al variare del parametro εn
90
80
70
60
50
Єn=0.001
Єn =0.006
Єn=0.05
40
30
20
10
0
n iterazioni
note : La valutazione dell'errore è stata fatta su un dataset composto da 200
punti presi a caso all'interno di un cubo (3D) avente lato = 1 .
Il training è costituito da 8000 adaptation steps su dati presi a caso dal
dataset , l'errore è stato ricalcolato per ogni 200 passi.
Le 3 reti sono state inizializzate con gli stessi nodi (2 dati presi a caso dal
dataset) e sono state sottoposte ai medesimi passi di apprendimento.
FUZZY-GNG
Per quanto riguarda la rete neurale implementata nella classe FuzzyGng, è
stato molto importante valutare sperimentalmente l'efficienza della rete al
variare dei parametri di apprendimento, essendo un algoritmo ancora in
fase di sviluppo.
errore al variare di b1
100
90
80
errore
70
60
50
40
.b1=0.05
.b1=0.2
.b1=0.8
30
20
10
0
n iterazioni
errore al variare di b2
90
80
70
errore
60
50
.b2=0.0005
.b2=0.006
.b2=0.05
40
30
20
10
0
n iterazioni
errore al variare di kw
90
80
70
errore
60
50
40
Kw = 1 .0
Kw = 9.0
Kw = 18.0
30
20
10
0
n iterazioni
note: Il dataset, il tipo di training e le altre condizioni di prova sono
analoghe a quelle viste nella Gng (andamento errore al variare dei
parametri).
Confronto convergenza tra GNG, FUZZY-GNG e NG
errore gng - fuzzy gng
90
80
70
errore
60
50
40
GNG
FUZZY-GNG
30
20
10
0
n iterazioni
Le due reti (Gng e Fuzzy-Gng) sono state sottoposte al medesimo training:
stesso dataset, stesso ordine anche se casuale e stesso numero di adaptation
steps.
Anche i nodi iniziali sono gli stessi per entrambe , e sono stati scelti
casualmente nel dataset.
errore gng - fuzzy - ng
80
70
60
errore
50
40
GNG
FUZZY
NG
30
20
10
0
n iterazioni
4.2 Andamento degli indici caratteristici nella Gng:
Lunghezza media
L
5
4,5
4
3,5
3
2,5
2
1,5
1
0,5
0
n iterazioni
C
Coefficiente di clustering
0,7
0,6
0,5
0,4
0,3
0,2
0,1
0
num nodi
n iterazioni
Distribuzione Grado
35
30
25
20
15
10
5
0
1
2
3
4
5
6
7
8
grado
4.3 Valutazione sperimentale delle reti asimmetriche
Attraverso l'utility grafica "Gnuplot" [5], è stato possibile avere una
visualizzazione grafica di una rete neurale Neural Gas Asimmetrica.
I nodi in questa visualizzazione, non sono collegati soltanto da linee,
infatti le connessioni sono rappresentate da frecce che indicano anche il
verso della connessione.
Dalla rappresentazione grafica si può notare come le connessioni tra nodi
vicini sono spesso bidirezionali, ovvero se a e b sono vicini esiste sia la
connessione (a ==> b) che la connessione (a <== b).
Le connessioni tra nodi lontani ,invece, sono spesso unidirezionali.
Questo fenomeno trova spiegazione nel fatto che, durante l'apprendimento,
la rete tende ad costituire connessioni tra nodi che identificano uno stesso
cluster (nodi vicini) e allo stesso tempo eliminare le connessioni residue
tra i nodi di clusters diversi (nodi lontani) .
Non ci sono sostanziali differenze nell'andamento dell'errore rispetto alla
errore
versione asimmetrica delle reti neurali:
errore GNG - GNG Asimmetrica
80
70
60
50
GNG
GNG ASIM
40
30
20
10
0
n iterazioni
errore
errore fuzzy - fuzzy asimmetrica
80
70
60
50
40
F uzzy
Fuzzy asim
30
20
10
0
n iterazioni
L'andamento dell'errore relativo alla rete di tipo Neural Gas è identico a
quello della sua versione asimmetrica perchè il movimento dei nodi verso
l'input non dipende dalla topologia della rete, ma solo dalla distanza tra
quest'ultimo ed ogni nodo.
4.4 Visualizzazione grafica- Clustering
Il package "vis_grafica" è utilizzato per contenere tutte le classi utili per la
visualizzazione grafica dell'evoluzione topologica e spaziale delle reti
neurali.
Le applicazioni che vogliono fare uso di queste classi devono usare un
componente grafico in cui si può visualizzare un disegno 3D: il GLCanvas.
Il GLCanvas è disponibile nella libreria JOGL [6] che implementa le
istruzioni grafiche openGL in java.
Al GLCanvas viene registrato un listener : GraficoGLEventListener
(JOGL) che contiene i metodi per l'aggiornamento grafico del componente
Di conseguenza è stata modificata la classe GraficoGLEventListener, alla
quale si possono dare come parametri al costruttore un elenco di figure, le
quali verranno disegnate sul GLCanvas ad ogni aggiornamento grafico.
Le figure vengono disegnate sfruttando il polimorfismo, perchè le classi
relative ad ogni figura devono tutte implementare l'interfaccia
FiguraOpenGL ed il relativo metodo disegna(GL).
Clustering rete Gng
I punti verdi rappresentano i dati del dataset, che sono uniformemente
contenuti nei 3 cubi disegnati in nero.
I punti rossi rappresentano i nodi della rete implementata dalla classe
Gng , mentre le linee rosse sono le connessioni esistenti tra i vari nodi.
Si nota che la topologia della rete neurale (rossa) all'aumentare degli
adaptation steps (iterazioni), riesce a ricalcare le similarità tra i dati del
dataset , infatti la rete riconosce i 3 cluster rappresentati dai cubi.
Clustering rete NeuralGas
Anche nel caso della rete neurale di tipo Neural Gas, si nota che la
topologia della rete neurale (rossa) all'aumentare degli adaptation steps
(iterazioni), riesce a ricalcare le similarità tra i dati del dataset , infatti la
rete riconosce i 3 cluster rappresentati dai cubi.
Per quanto riguarda la Fuzzy-Gng, si è scelto di usare una classe di test per
il clustering sui 3 cubi (visti in precedenza) che alla fine
dell'apprendimento riporti in 3 file di testo i clusters rilevati dalle reti Gng,
FuzzyGng e NeuralGas, il relativo spezzone di codice è:
ProvaClusteringCubi pc2=new ProvaClusteringCubi(); // classe contenente il main
// I clusters di dati della Gng vengono memorizzati su un file di log
RegistratoreLog rl1=new RegistratoreLog("gruppiclustercubi1.txt");
rl1.salvaVettore(pc2.getElencoClusters(reteneurale1,clusters1, dataset));
System.out.println(rl1.toString());
// I clusters di dati della Fuzzy vengono memorizzati su un file di log
RegistratoreLog rl2=new RegistratoreLog("gruppiclustercubi2.txt");
rl2.salvaVettore(pc2.getElencoClusters(reteneurale2,clusters2, dataset));
System.out.println(rl2.toString());
// I clusters di dati della NG vengono memorizzati su un file di log
RegistratoreLog rl3=new RegistratoreLog("gruppiclustercubi3.txt");
rl3.salvaVettore(pc2.getElencoClusters(reteneurale3,clusters3, dataset));
System.out.println(rl3.toString());
}
Il metodo che estrapola i clusters del dataset tramite la rete neurale è:
public String[] getElencoClusters(ReteNeurale rn,ArrayList<int[]> clusters,
ArrayList<double[]> dataset)
{
int ngruppi=clusters.size();
// costituisce i cluster del dataset
IntArrayList[] gruppi=new IntArrayList[ngruppi];
for(int i=0;i<ngruppi;i++)
gruppi[i]=new IntArrayList();
for(int i=0;i<dataset.size();i++)
{
int vin=rn.ricercaVincitore(dataset.get(i));
for(int j=0;j<ngruppi;j++)
{
int[] gruppo=clusters.get(j);
if (OpVettori.elementoPresente(gruppo, vin))
{
gruppi[j].add(i);
break;
}
}
}
// predispone i cluster ad essere esportati in un file di testo
String[] gruppitesto=new String[dataset.size()+ngruppi];
int k=0;
for(int i=0;i<gruppi.length;i++){
for(int j=0;j<gruppi[i].size();j++){ // inserisce la
parola nel gruppo di parole
double[] dato=dataset.get(gruppi[i].getQuick(j));
gruppitesto[k]="
"+dato[0]+"
"+dato[1]+"
"+dato[2];
k++;
}
gruppitesto[k]="";
k++;
// lascia una riga tra un gruppo ed un'altro
}
return gruppitesto;
}
Da un'analisi dei 3 file di testo è stato osservato che i clusters individuati
dalle 3 reti sono identici ed esatti, essendo corrispondenti ai gruppi
rappresentati dai tre cubi.
4.5 Sperimentazione su Dataset di prova
Implementazione delle reti neurali con metrica coseno
ReteNeurale
Gng
Gng
Coseno
Gng
Asimmetrica
FuzzyGng
FuzzyGng
Asimmetrica
FuzzyGng
Coseno
NeuralGas
NeuralGas
Asimmetrica
NeuralGas
Coseno
In alcune ambiti, le reti neurali devono operare su dataset in cui si fa
riferimento alla metrica coseno e non a quella euclidea per ottenere la
distanza tra due punti appartenenti allo spazio di stato .
prodotto scalare (a,b)
cos(α) =
|| a || * || b ||
Distanza
coseno = (1 ― cos(α))
per implementare il calcolo del nuovo tipo di distanza nelle varie classi di
reti neurali si è semplicemente sovrascritto il metodo
double distanza(double[] input,double[] nodo)
sviluppato in Gng,
chiamando il metodo distanzaVettoriCoseno(input,nodo) della libreria di
funzioni rappresentate dai metodi della classe OpVettori , ad esempio per
la classe GngCoseno.java:
protected double distanza(double[] input,double[] nodo)
{
return (1-OpVettori.distanzaVettoriCoseno(input,nodo));
}
La sperimentazione su dataset di prova è stata effettuata sottoponendo ad
una rete neurale di tipo GNG, implementata nella classe Gng.java, una
serie di dati ed osservando il risultato del clustering ottenuto tramite la rete
stessa.
Il dataset di prova è composto dalle parole contenute nei lanci di un'
agenzia di stampa, ed i valori che caratterizzano le varie parole, sono
identificativi della frequenza con cui la data parola compare in ogni
articolo.
Questi valori sono espressi in metrica coseno, quindi per il test, è stata
utilizzata l' implementazione delle reti neurali in metrica coseno.
I dati elaborati fanno riferimento a 9100 parole contenute in 600
documenti che rappresentano le news date dall'agenzia .
Al termine della prova si osservano vari gruppi di parole (clusters), ogni
gruppo dovrebbe contenere un'insieme di parole che spesso compaiono
insieme nello stesso articolo.
Da un'analisi dei vari clusters si trova conferma a quanto ipotizzato ,
perchè si nota una correlazione tra le parole contenute in uno stesso
cluster.
Ad esempio , in diverse elaborazioni del dataset con la rete neurale (nodi
iniziali diversi, diverso ordine degli adaptation steps) si osserva sempre la
presenza di un cluster contenente la parola “dollaro” e la parola “yen”,
Queste due parole sono evidentemente correlate dal fatto di essere
entrambe identificative di una valuta, e logicamente compaiono spesso
insieme nelle stesse news.
Quindi si può supporre ragionevolmente che la rete neurale adempie al
compito di clustering sul dataset in questione.
CONCLUSIONI
Dalla valutazione sperimentale si osserva che la versione Fuzzy
dell'algoritmo di apprendimento è valida per quanto relativamente alla
convergenza della rete neurale con i dati del dataset.
Per quanto riguarda il clustering, si può stabilire che l'individuazione dei
clusters della rete si complica per via della necessità di determinare il peso
soglia che differenzi una connessione significativa da una trascurabile
però, i molti esperimenti condotti in tal senso hanno dimostrato che, con il
peso soglia appropriato, i clusters estrapolati sono coerenti con il
clustering effettuato tramite la GNG o la NG.
Il confronto sull'efficienza, in termini di difficoltà computazionale e quindi
di velocità nell'esecuzione dell'algoritmo, per adesso, va a favore delle
versioni "classiche" (Gng,NeuralGas); infatti nella versione Fuzzy i pesi
associati alle connessioni sono considerati dei valori double, perciò la
funzione di incremento dei pesi ed il calcolo dello spostamento di tutti i
nodi (ad ogni adaptation step), sono relativamente più pesanti rispetto
all'incremento dell'età delle connessioni e rispettivo spostamento di alcuni
nodi, che avviene nelle reti neurali "classiche".
In conclusione, la versione Fuzzy dell'algoritmo di apprendimento
rappresenta senz'altro un'innovazione molto importante nel campo delle
reti neurali; attualmente è meno conveniente rispetto alle vecchie versioni,
ma rivoluziona in maniera significativa i meccanismi di apprendimento
della rete, perciò è logico pensare che valga la pena continuarne la fase di
sviluppo.
L'implementazione delle reti neurali descritte nei capitoli precedenti, ha
richiesto molte delle potenzialità che un linguaggio Object-Oriented come
java offre, ad esempio l'ereditarietà ed il polimorfismo.
L'augurio è che le classi sviluppate per redarre questa tesi, potranno essere
riusate anche in futuro, soprattutto per la continuazione del lavoro di
sviluppo dell'algoritmo Fuzzy.
BIBLIOGRAFIA
[1] Thomas Martinetz, Klaus Shulten 1991:
A "Neural Gas" Network Learns Topologies
[2] Bernd Fritzke 1995:
A Growing Neural Gas Network Learns Topologies
[3] Rossano Gaeta (Università degli studi di Torino) :
Network complessi e modelli
[4] http://acs.lbl.gov/software/colt/index.html
[5] http://www.gnuplot.info/
[6] http://java.net/projects/jogl/