Data Mining - homepagebrescia/documents/ASTROINFOEDU/brescia...U-matrix con componenti connesse M....

Data Mining

Riepilogo indici di qualità clustering

2

Indice di Davies-Bouldin

Rapporto tra distanza intra-cluster ed inter-cluster

Errore di quantizzazione

Similarità degli input assegnati al medesimo BMU

Errore topografico

Dissimilarità degli input assegnati a BMU differenti

Indice di accuratezzaRapporto tra cluster attesi ed individuati

Indice di completezzaDisgiunzione dei cluster

Distanza intra-clusterDistanza inter-cluster

M. Brescia - Data Mining

𝑸𝑬 =𝟏

𝟐𝑵

𝒋=𝟏

𝑷

𝒏∈𝑩𝑴𝑼𝒋

𝒙𝒏 − 𝑩𝑴𝑼𝒋𝟐

Two-stage clustering

3

Lo scopo dell’attuazione di un metodo di clustering a due stadi è quello di superare iprincipali problemi di cui sono afflitti i metodi convenzionali, come la sensibilità ai prototipiiniziali (proto-cluster) e la difficoltà di determinare un appropriato numero di cluster attesi.

L’approccio maggiormente utilizzato è la combinazione di una tecnica di clusteringgerarchico o una SOM, seguita da una tecnica di clustering partizionale.La funzione della SOM al primo stadio è quella di identificare un numero iniziale dicandidati cluster e relativi centroidi. Nel secondo stadio invece, una tecnica di clusteringpartizionale assegnerà in maniera rafforzativa un cluster per ogni pattern.

Il vantaggio principale risiede nel fatto che il secondo stadio viene applicato a partire dainodi (proto-cluster) dello strato di Kohonen, che generalmente sono in numero inferiore aipattern input (sperabilmente).Tale tecnica si traduce quindi in un notevole vantaggio dal punto di vista computazionale. Intaluni casi però potrebbe essere necessaria la scelta di un numero di cluster attesi(partitioning clustering).


SOM + K-Means

M. Brescia - Data Mining 4

Si può scegliere di non selezionare i centri iniziali dei cluster in base alla distribuzione deipunti del dataset, bensì tra i BMU calcolati da una SOM. Questo tipo di approccio permette diridurre la sensibilità al rumore, in quanto i BMU sono medie locali dei dati e quindi menosensibili a variazioni degli stessi. Anche gli outlier non sono un problema poichè, perdefinizione, rappresentano solo una piccolissima percentuale del numero di dati e, in quantotali, incapaci di influenzare il processo. Tuttavia, se il nostro intento fosse quello di individuareeffettivamente gli outlier, allora l’utilizzo di questo approccio sarebbe controproducente.

la suddivisione in partizioni avviene tra i nodi BMU dello strato diKohonen. Affinché questo processo sia applicabile, è quindi necessarioindividuare un numero di cluster attesi inferiore al numero di BMUindividuati dalla SOM

U-matrix con componenti connesse


In dataset multi-dimensionali di grandi dimensioni, visualizzare i cluster sulla U-Matrix puòrisultare un compito non facile. Esiste un metodo per migliorare l’interpretazione della mappadi Kohonen, immaginando i nodi della stessa come vertici di un grafo in cui delle componenticonnesse (CC) siano identificative di altrettanti cluster.

Il procedimento con cui le CC sono identificate si basa sul concetto che, per ognuna di esse,esisterà un nodo, definito nodo interno ad una CC, il cui gradiente sarà inferiore rispetto aquello di tutti gli altri.

Sperimentalmente gli autori del metodo hannoosservato che l’utilizzo di una tecnica in grado dieliminare inutili frammentazioni della U-Matrixrendendola più omogenea, migliora notevolmente irisultati ottenuti nella ricerca delle CC. Questo effettoè ottenibile tramite l’applicazione alla mappa, di unfiltro gaussiano di sfocatura comunemente utilizzato indiversi software grafici. L’idea di base di questo filtro èche ogni pixel diventi una media pesata dei pixelattorno ad esso. Il peso di ogni pixel è maggiore inproporzione alla vicinanza al pixel che si staattualmente sfocando.

𝑮 𝒊, 𝒋 =𝟏

𝟐 𝝅 𝝈𝟐𝒆−

𝒊−𝒋

𝟐 𝝈𝟐

i pixel in fase di sfocaturaJ Pixel di cui calcolare il peso𝑖 − 𝑗 distanza tra coordinate di i e j

σ ampiezza gaussiana del grado di sfocatura

x = NODE SELECTED FROM KOHONEN

LAYERx

FIND m = NODE WITH MINIMUM

GRADIENT AMONG NEIGHBOORS OF x

m = x ? NO

x = m

x WAS ASSIGNED TO A

CLUSTER ?

CLUSTER LABEL OF NODE x

ASSIGN CLUSTER LABEL TO NODE x

READ ALL KOHONEN

LAYER ?

YES

CREATION OF A NEW CLUSTER

NO

START

END

YES

FIND CC NODE

START

END

NO

YES



Per ogni nodo della mappa quindiverranno valutati i gradienti di tutti isuoi nodi adiacenti. Se il nodoesaminato non è quello con il minimogradiente, allora ci si potrà muoverelungo un percorso attraversando di voltain volta il nodo con gradiente minimo,seguendo i suoi vicini e connettendotutti i nodi attraversati. Nel caso di unnodo interno ad una CC, la proceduratermina, passando ad esaminare unnodo successivo. Con tali CC, al di sopradella U-Matrix, l’appartenenza di unnodo ad un cluster diventa evidente.

A sinistra la U-Matrix standard ea destra quella ottenuta con lecomponenti connesse



L’applicazione di questa funzione, a tutti i pixel circostanti al pixel considerato per la sfocatura,fornirà una matrice dei pesi. Le dimensioni di questa matrice dipenderanno dal numero dipixel considerati vicini. Tale parametro, noto come kernel, può essere l’intera immagine oavere un raggio più piccolo. A questo punto, il nuovo valore del pixel correntementeanalizzato sarà la somma dei valori dei pixel compresi nel raggio di sfocatura moltiplicati per ilrispettivo peso.E’ bene notare che i risultati ottenuti con il metodo Umat-CC possono variare, in alcunidettagli, proprio in base al grado di sfocatura applicato, il quale dipenderà dal parametro σdell’equazione peso gaussiana. Poiché non esiste una regola per il calcolo di questoparametro, in quanto dipendente dalle caratteristiche dello specifico esperimentoconfigurato, esso dovrà essere settato di volta in volta qualora il risultato ottenuto non siaritenuto soddisfacente.

Utilizzo del grado di sfocaturadella U-Matrix

In questo procedimento di regolazione può essere utile farricorso alla U-Matrix, che verrà mostrata in output senzal’applicazione del filtro. In tal modo, ove ci si renda conto dipossibili errori, si potrà ripetere il post-processing settandoun livello di sfocatura più basso o più alto a seconda dei casi.

Osservando i gradienti dei nodi e ricordando come Umat-CC li raggruppa, si intuisce chel’attribuzione ad un cluster isolato del nodo colorato in azzurro (sinistra), può essere un erroredovuto ad un livello di sfocatura eccessivo. A destra è mostrato il risultato ottenuto con unfiltro di sfocatura meno invasivo.

Two-winners linkage


Il Two Winners Linkage (TWL) è un metodo di clustering, post-processing dello strato diKohonen, che si ispira alla tecnica per il calcolo del vicinato usata nel modello Evolving SOM,che vedremo fra poco. Tale meccanismo consiste nell’instaurare una connessione tra i dueBMU di ogni pattern in modo che, al termine dell’algoritmo, le componenti connesse rivelino icluster individuati.

E’ necessario introdurre un meccanismo per evitare la connessione dinodi troppo lontani. A tal fine sfruttiamo il duale del concetto di nodointerno ad una CC, visto prima, dove un nodo interno di una CC è statodefinito come quel nodo che sulla U-Matrix risulta avere un gradienteinferiore a quello di tutti i nodi ad esso adiacenti. Ciò si verifica nelcaso in cui i suddetti nodi siano molto vicini al nodo interno.In virtù di questo, possiamo quindi definire come nodo esterno ad unaCC quel nodo il cui gradiente è maggiore rispetto a quello di tutti inodi ad esso adiacenti. Per come è stato definito, un nodo esternoindividuerà quindi un nodo isolato nello spazio dei pesi.

Two-winners linkage


Un nodo esterno può essere interpretato in diversi modi. Il casopiù semplice si verifica quando tale nodo non è risultato BMU dialcun pattern, individuando quindi una zona “vuota” dellospazio dei dati. Tali nodi sono quelli che in pratica rendono la U-Matrix un potente strumento di visualizzazione, distinguendo lezone ad alta densità di pattern.

NODI ESTERNI

Se viceversa, il nodo esterno è risultato BMU per qualchepattern, possono essersi verificate due situazioni. In primoluogo, il nodo può identificare degli outliers e, in quest’ottica,l’isolamento di tale nodo permette la loro individuazione.

In secondo luogo, nel caso di dati particolarmente complessi,un nodo esterno può essere frutto di una particolaredisposizione dei pattern. Quando i cluster non sono infattinettamente distinguibili, i nodi esterni possono configurarsicome dei “separatori”, che si posizionano a metà tra un clustered un altro, permettendo quindi al metodo di distinguerli.

Two-winners linkage


Nella seguente immagine è mostrato il ruolo che i suddettinodi esterni possono avere nel processo di clustering con ilmetodo illustrato. Il nodo celeste e i due nodi di tonalitàarancione si configurano nettamente come separatori diclasse, mentre i pattern individuati dal nodo verdepotrebbero essere outliers.

START

FIND 2th BEST MATCHING UNIT

FIRST AND SECOND BMU ARE CONNECTED ?

FIRST BMU AND SECOND BMU ARE EXTERNAL NODES ?

CONNECT FIRST AND SECOND BMU

READ ALL PATTERNS ?

NO

NO

YES

YES

NO

END

YES

BMUTable

(from SOM)

LOADinput pattern

Alla luce delle considerazioni fatte, il filtro di sfocatura gaussianadella U-Matrix, esposto in precedenza, dovrà assumere valori moltobassi, al fine di evitare di uniformare troppo la mappa, nonriconoscendo i nodi esterni come tali.

Strategy for Two stage clustering


Il sistema software è pensato per venireincontro alle esigenze di diversi utenti, inbase alla loro conoscenza sui dati e/o deimodelli. La strategia è suddividere intipologie di esecuzione differenti il processo.

• SINGLE-STAGE: no post-processing,rendendo definitivo il proto-clusteringeffettuato dalla SOM;•AUTOMATIC: In tal caso sarà il softwarestesso, in base a dei parametri interniprestabiliti, a selezionare la tecnica di post-processing più opportuna tra K-means eUmat-CC; nel caso in cui l’utente abbia adisposizione delle informazioni sui dati, potràutilizzarle selezionando il numero di clusterattesi;EXPERT: caso d’uso riservato all’utenzaesperta, in cui spetterà all’utente la scelta delmetodo da utilizzare e, nel caso il metodo lorichieda, il numero di cluster attesi.

Limiti del modello SOM


SOM e Dimensionality Reduction : problema della griglia

SOM parte da un grafo preimpostato i cui vertici sidispongono sullo spazio dei dati

SOM costruisce una mappatura inversa, dal grafo allospazio dei dati

SOM non assicura la costruzione di una TopologyPreserving Map

Grafo bi-dimensionale rappresentate lo strato di Kohonen che si distribuisce su uno spazio dei dati di forma quadrata

Limiti del modello SOM


Il grafo consiste in un reticolo 1D.La sua mappatura sullo spazio deidati preserva la vicinanza, infattivertici adiacenti nel grafo sonovicini sullo spazio dei dati. Alcontrario la relazione duale nonsussiste in quanto punti vicini sullospazio dei dati non sono verticiadiacenti nel grafo. Ne consegueche la mappatura non è unaTopology Preserving Map

Qui il grafo consiste di unreticolo 2D. In tal caso sia lamappatura dallo spazio deidati al grafo, che l’inversapreservano la vicinanza. Soloin questo caso quindi lamappa è una TopologyPreserving Map

Beyond SOM


Una delle principali limitazioni del modello SOM originario è la staticità della dimensione edella struttura topologica della griglia output. Questo aspetto ha un impatto particolarmentenegativo nel caso di problemi di clustering dinamico (on-line clustering) o incrementale, in cuiè altresì desiderabile che la struttura della rete e la sua dimensione possa evolvere conl’andamento dei dati acquisiti. Questo avviene per il modello Evolving Self Organizing Map (E-SOM), basato sulla legge di apprendimento e di preservazione della topologia della rete delleSOM, in grado di evolvere dinamicamente l’estensione dello strato di Kohonen.

Da notare che tale modello rappresenta una delle due più interessanti varianti del modelloSOM. In generale, infatti, evoluzioni della SOM possono essere derivate partendo da unelemento comune (estensione dinamica del numero di nodi dello strato di Kohonen), madirezionate su criteri distinti: (i) mantenere la legge di apprendimento di Kohonen invariata,modificandone la topologia; oppure (ii) modificare la legge di apprendimento, mantenendoinalterata la topologia.

Al primo criterio appartiene ad esempio il modello Evolving Tree (E-TREE), in cui la topologiadello strato di Kohonen è strutturata sottoforma di albero di ricerca, in cui nuovi nodi sonocreati in base alla soglia del numero di volte in cui un nodo ha assunto il ruolo di BMU.

Il modello E-SOM invece appartiene al secondo filone di varianti evolute della SOM. Di seguitoviene descritto il funzionamento interno e la relativa implementazione.

Evolving Trees (Etree)


Evoluzione supervisionata della SOM con strutturaincrementale ad albero che supera il problema della grigliastatica

Inizialmente rete costituita da un singolo nodo che subisceuna fase di splitting con cui vengono creati i figli

Ogni nodo ha associata una variabile che conta il numerodi volte in cui è stato BMU (Best Matching Unit), quandosupera una certa soglia si procede allo splitting del nodoincrementando la struttura dell’albero

Per aggiornare la posizione delle foglie utilizza la legge diapprendimento di Kohonen

𝒘𝒊 𝒕 + 𝟏 = 𝒘𝒊 𝒕 + 𝒉𝒄𝒊 𝒕 𝒙 𝒕 − 𝒘𝒊 𝒕

𝒉𝒄𝒊 𝒕 = 𝜶 𝒕 𝒆[−

𝒅(𝒓𝒄,𝒓𝒊)𝟐

𝟐𝝈𝟐(𝒕)]

Durante la costruzione dell’albero si impone una legge didecay del contatore del numero di volte che un nodo èrisultato il BMU per un pattern

𝒃𝒊 𝒕 + 𝟏 = 𝜸𝒃𝒊(𝒕)

La ricerca del BMUavviene partendodalla radice escendendo fino adun nodo foglia

Trattandosi di unalbero la distanzatra neuroni è datadal numero di archiche intercorrono trai due nodi

Clustering supervisedLegge di Kohonen invariataTopologia ad albero

Evolving SOM (ESOM)


L’algoritmo inizia con una rete vuota, senza cioè nodi econnessioni. I nodi vengono creati incrementalmente conl’avvicendarsi dei dati input. Quando viene presentato unpattern input, i nodi presenti nella rete competono tra loro e siaggiornano le connessioni dei vincitori (BMU). In particolarequando i primi due BMU non sono interconnessi, viene creatauna connessione diretta tra loro. Un nuovo nodo nella reteviene creato quando nessun altro nodo preesistente risultacandidato a rappresentare un pattern input.

Evolving SOM (ESOM)


START START PRUNING TIMER

SELECT PATTERN FROM DATASET

EMPTY OUTPUT LAYER ?

SET WEIGHTS VECTOR FOR A

NEW NODE

YES

FIND FIRST AND SECOND BMU

NO

COMPUTE DISTANCE OF FIRST

BMU FROM PATTERN SELECTED

DISTANCE > ɛ ?ALLOCATION OF

NEW NODE YESFIRST NODE ?

CONNECT NEW NODE WITH FIRST AND SECOND BMU

NO

FIRST AND SECOND BMU ARE CONNECTED ?

UPDATE WEIGHTS AND CONNECTIONS

YES

SET CONNECTION BEETWEEN FIRST

AND SECOND BMU

NO

INCREMENT PRUNING TIMER

PRUNING TIMER > TRESHOLD ?

NO

PRUNE WEAKEST CONNECTIONYES

RESET PRUNING TIMER

DATASETCOMPLETED?

END

NO

NO

YES

YES

Flow Chart del loop di training del modello E-SOM

Poiché nel modello E-SOM i neuroni nonsono inseriti all’interno di una struttura rigidacome la griglia dello strato di Kohonen, èevidente l’impossibilità di utilizzare la classicaU-Matrix come strumento di visualizzazione.Tuttavia, al fine di fornire un metodo divisualizzazione del risultato del clustering, èstata implementata una U-Matrix modificata,in cui i neuroni sono disposti sulla griglia nonin base all’effettiva posizione nello spazio deipesi, bensì raggruppati per cluster diappartenenza.

Evolving SOM (ESOM)


Implementa una tecnica di self-creatingsuperando i limiti imposti da una strutturafissa

Parte da una griglia vuota

Se l’input corrente non trovacorrispondenza adeguata, ovvero ladistanza supera una certa soglia ε, vieneaggiunto un nuovo nodo alla rete

Nodo aggiunto relativo al pattern in input:allocazione più semplice che migliora leperformance di una SOM statica

Per ogni pattern si calcolano i migliori dueBMU e se una connessione tra loro esiste,quest’ultima viene aggiornata, altrimentiviene creata

Legge di apprendimento

Attivazione

Clustering unsupervisedLegge di Kohonen modificataTopologia simile alla SOM

Global Strategy


E-TREEEvolving Tree

E-SOMEvolving SOM

Umat-CCU-matrix a

Componenti ConnesseK-Means

TWLTwo Winners Linkage

SOM

Self Organizing Maps

Evoluzione topologia Evoluzione apprendimento

2-stageClustering

20

Sulla pagina web del corso trovate:Gli esempi di dati mostrati per test su modelli di clustering;I codici sorgente C++ del modello E-TREE; M. Brescia - Data Mining

Clustering examples

Heptaclearly defined clusters, different variances

Size 212Dimensions 3Classes 7

Chainlink linear not separableSize 1000Dimensions 3Classes 2

Golfball no clusters at allSize 4002Dimensions 3Classes 2

Target outliersSize 770Dimensions 2Classes 6

IRIS outliersSize 150Dimensions 3Classes 3

CFHT Extended structuresUGRIZ,700x700 pixels

M101 Spiral galaxySingle band, 530x530 pixels

IRISConfronto tra

K-Means standard e modelli di clustering

proposti

21

Il dataset è composto da 50 pattern perogni specie di Iris (Setosa, Virginica eVersicolor) per un totale di 150 pattern. Perognuno di essi sono state misurate 4feature: lunghezza e larghezza dei petali edei pistilli.

PARAMETRI SOM

Numero di nodi input 4

Righe dello strato di kohonen 7

Colonne dello strato di kohonen 7

Numero massimo di iterazioni 200

Learning rate iniziale 0.7

Soglia di learning rate decay 0.005

Diametro iniziale del vicinato 14

Normalizzazione dei dati input No

PARAMETRI post-processing (K-means)

Numero di cluster attesi 3

PARAMETRI post-processing (Umat-CC )

Grado di sfocatura della U-matrix 1.5

PARAMETRI post-processing (TWL )

Grado di sfocatura della U-matrix 0.5

PARAMETRI E-SOM

Numero di nodi input 4

Epsilon (soglia minima di distanza tra

pattern e BMU)

0.5

Pruning time (Intervallo di tempo dopo ilquale effettuare il taglio della connessionepiù debole)

10

Learning rate 0.05

Normalizzazione dei dati input no


IRISConfronto tra


proposti

22

Il dataset è composto da 50 pattern perogni specie di Iris (Setosa, Virginica eVersicolor) per un totale di 150 pattern. Perognuno di essi sono state misurate 4feature: lunghezza e larghezza dei petali edei pistilli.

SOM Single-Stage SOM + K-Means SOM + Umat-CC

SOM + TWL E-SOM(nodo azzurro falso outlier; in arancione un nodo separatore di classi)


IRISConfronto tra


proposti

SOM + K-Means SOM + TWL SOM + Umat-CC E-SOM

CLASSE trovati persi %

Iris Setosa 50 0 100%

Iris Virginica 48 2 96%

Iris Versicolor 36 14 72%

Percentuale associazione

SOM + K-Means

Percentuale associazioneSOM + TWL

CLASSE trovati persi %

Iris Setosa 50 0 100%

Iris Virginica 45 5 90%

Iris Versicolor 47 3 94%

23

Il dataset è composto da 50 pattern perogni specie di Iris (Setosa, Virginica eVersicolor) per un totale di 150 pattern. Perognuno di essi sono state misurate 4feature: lunghezza e larghezza dei petali edei pistilli.CONFRONTO STATISTICO SU PRESTAZIONI DI CLUSTERING

MODELLO SOM SOM+K-means SOM+UmatCC SOM+TWL E-SOM

errore di quantizzazione 0.24 0.24 0.24 0.24 0.24

errore topografico 0.23 0.23 0.23 0.23 -

indice di Davies-Bouldin - 0.72 1.32 1.33 0.38


Hepta dataset 3D contenente 212 pattern appartenenti a 7 classi non

sovrapposte

SOM + K-Means SOM + TWLSOM + Umat-CC E-SOM E-TREE

Confronto tra modelli di clustering

proposti

24M. Brescia - Data Mining

Hepta

CONFRONTO STATISTICO SU PRESTAZIONI DI CLUSTERING (Chainlink)

MODELLO E-TREE SOM SOM+K-means SOM+UmatCC SOM+TWL E-SOM

errore di quantizzazione - 0.05 0.05 0.05 0.05 0.12

errore topografico - 0.28 0.28 0.28 0.28 -

indice di Davies-Bouldin - - 1.15 0.68 2.02 1.99

Accuratezza 0 0 0.69 0 0

Completezza 0 1 0 0 0



proposti

25

SOM single stage


Chainlink

CONFRONTO STATISTICO SU PRESTAZIONI DI CLUSTERING (Chainlink)





Accuratezza 0 0 0.69 0 0

Completezza 0 1 0 0 0

Dataset composto da due cluster con la caratteristica di essere non

linearmente divisibili



proposti


Target Dataset composto da cluster non linearmente divisibili e con quattro

gruppi di outliers agli angoli dell’immagine


CONFRONTO STATISTICO SU PRESTAZIONI DI CLUSTERING (Target)





Accuratezza 0 0 0.2 0 0.33

Completezza 0 1 0.48 0 0.34


proposti


Golfball dataset composto da 4002 pattern 3Dcon la caratteristica di appartenentitutti ad un unico cluster

SOM + TWLSOM + Umat-CC E-SOM E-TREE


proposti

28

CONFRONTO STATISTICO SU PRESTAZIONI DI CLUSTERING (Golfball)

MODELLO E-TREE SOM SOM+UmatCC SOM+TWL E-SOM

errore di quantizzazione - 0.17 0.17 0.17 1.0

errore topografico - 0.76 0.76 0.76 -

indice di Davies-Bouldin - - 2.76 1.13 0.0

Accuratezza 0 0.6 0.33 0

Completezza 0 0 0 0


CFHTImmagine astronomica

multibanda di un campo con HST

29

Un’immagine multi-banda è un file FITScomposto da un insieme di immagini in singolabanda dello spettro elettromagnetico, la cuisovrapposizione produce un’immagine a colori(relativi ai tipi di banda usati).Per il test si è scelto un campo deep fieldosservato dallo strumento CFHT nelle bandedel visibile UGRIZ, in cui ogni singola immaginemonocromatica ha dimensioni 700x700 pixelhttp://www3.cadc-ccda.hia-iha.nrc-cnrc.gc.ca/community/CFHTLS-SG/docs/cfhtlsD1.html


http://www3.cadc-ccda.hia-iha.nrc-cnrc.gc.ca/community/CFHTLS-SG/docs/cfhtlsD1.html



30

SOM Single-Stage

Istogramma di distribuzione cluster output




31

SOM + K-Means





32

SOM + Umat-CC





33

SOM + TWL





34

E-SOM





35

Il migliore risultato è palesementeottenuto dal modello E-SOM. Ilvalore del parametro DB tuttavia,indica che vi è una sovrastima delnumero di cluster identificati. Ciòinfatti deriva dal notevole numerodi raggruppamenti evidenziatiall’interno di alcuni degli oggetticelesti.

SOM Single-Stage SOM + K-Means

SOM + Umat-CC SOM + TWL E-SOM

CONFRONTO STATISTICO SU PRESTAZIONI DI CLUSTERING






M101Immagine astronomica monocromatica di una

Galassia a spirale

SOM + K-Means (k = 6) SOM + TWLSOM + Umat-CC E-SOM

SOM (Single Stage)

CONFRONTO STATISTICO SU PRESTAZIONI DI CLUSTERING (Img M101)






M101Immagine astronomica monocromatica di una

Galassia a spirale

SOM + K-Means (k = 6) SOM + TWLSOM + Umat-CC E-SOM

SOM (Single Stage)

37

SOM Single-Stage produce eccessivi raggruppamenti. Nell’immagine M101, le variazionidinamiche del background sono indotte dagli aloni dei rami della spirale. I test evidenzianosimilarità di SOM + K-Means ed E-SOM, che individua lo stesso numero di cluster del K-Means,pur non avendo a priori alcuna conoscenza sul numero.TWL individua un numero inferiore di cluster, inglobando in cluster unici alcuni degli aloni chegli oggetti celesti presentano. Umat-CC è pagonabile al TWL ma, per sua natura, non è in gradodi lavorare correttamente su una U-Matrix generata da una così particolare configurazione deinodi della rete. Il metodo riconosce i nuclei degli oggetti e gran parte dello sfondo,confondendone gli aloni.


• Le diverse combinazioni di tecniche, nel clustering a due stadi, presentano caratteristiche tali darenderli adatti in diverse situazioni.

• Le evoluzioni incrementali del modello SOM possono essere usate in maniera ottimale sia perclustering che per classificazione

SOM + K-Means SOM + Umat-CC SOM + TWL E-SOM E-TREE

Dimensionedello strato di

output

Ininfluente Grande numero di nodi migliora i

risultati

Grande numero di nodi aumenta la

densità del clustering

Grande numero di nodi aumenta la

densità del clustering

ininfluente

OutliersPoco robusto Poco robusto Robusto Robusto (dipendente

da parametri)Robusto

Dimensionalità dataset

Ininfluente poco adatto su dataset 1D

Ininfluente Ininfluente Ininfluente

Dati linearmente non divisibili

Inefficace Poco efficace Efficace Efficace Efficace

Dipendenza dai parametri input

Alta Media Media Alta Alta

Confronto prestazioni tra metodi


Configurazioni parametri esempi

39

SOM Hepta Chainlink Target Golfball M101 CFHT-D1Nodi input 3 3 2 3 1 5Colonne grid output 20 15 15 8 15 15Righe grid output 20 15 15 8 15 15Vicinato iniziale 20 15 20 10 10 10N° max iterazioni 200 300 100 1000 200 200Normalizzazione No No No No No SiModalità post-processing

0 0 0 0 0 0

SOM + K-Means HEPTA Chainlink Target M101 CFHT-D1Nodi input 3 3 2 1 5Colonne grid output 20 15 15 15 15Righe grid output 20 15 15 15 15Vicinato iniziale 20 15 20 10 10N° max iterazioni 200 300 100 200 200Normalizzazione No No No Si SiModalità post-processing 2 2 2 2 2Metodo di post-processing 1 1 1 1 1N° clusters attesi (k) 7 2 6 6 11



40

SOM + Umat-CC Hepta Chainlink Target Golfball M101 CFHT-D1Nodi input 3 3 2 3 1 5Colonne grid output 20 15 15 8 15 15Righe grid output 20 15 15 8 15 15Vicinato iniziale 20 15 20 10 10 10N° max iterazioni 200 300 100 1000 200 200Normalizzazione No No No No Si SiModalità post-processing 2 2 2 2 2 2Metodo di post-processing 2 2 2 2 2 2Grado sfocatura U-matrix 2 2 0.8 1.5 3.5 2.5

SOM + TWL Hepta Chainlink Target Golfball M101 CFHT-D1Nodi input 3 3 2 3 1 5Colonne grid output 5 15 15 8 15 15Righe grid output 5 15 15 8 15 15Vicinato iniziale 5 15 20 10 10 10N° max iterazioni 5 300 100 1000 200 200Normalizzazione No No No No Si SiModalità post-processing 2 2 2 2 2 2Metodo di post-processing 3 3 3 3 3 3Grado sfocatura U-matrix 1.5 2 2.4 1.5 0.6 0.1



41

E-SOM Hepta Chainlink Target Golfball M101 CFHT-D1Nodi input 3 3 2 3 1 5Soglia di distanza minima 1 0.5 0.2 0.5 0.5 0.05Pruning time 10 30 5 50 200 50Normalizzazione No No No No Si Si

E-TREE Hepta Chainlink Target Golfball

Soglia di splitting 10 10 10 10

Numero di nodi generati per splitting 2 2 2 2

η0 tasso di apprendimento iniziale 0.8 0.8 0.8 0.8

σ0 diametro iniziale del vicinato 0.6 0.6 0.6 0.6

τ1 costante temporale 4 4 4 4

τ2 costante temporale 5 5 5 5

Fattore di decadimento occorrenze BMU 0.8 0.8 0.8 0.8

Numero di esecuzioni del K-Means 2 2 2 2


Date post:	03-May-2020
Category:	Documents
Upload:	others
View:	8 times
Download:	0 times

Data Mining - homepagebrescia/documents/ASTROINFOEDU/brescia...U-matrix con componenti connesse M....

Documents