sublimina.it

  • Full Screen
  • Wide Screen
  • Narrow Screen
  • Increase font size
  • Default font size
  • Decrease font size






  research gate


omino_logo_sublomina


La Conoscenza è come una linea, dove sono i confini non ci è dato di saperlo.

Sublimina.it è un viaggio personale nel mondo del pensiero umano. Per raggiungere ogni meta c'è una via ed ogni via ha un ingresso. Questa è la mia porta personale, l'ho appena aperta. Ognuno ha la sua porta, qualche volta si ha bisogno, però, di intravedere cosa c'è al di là della porta altrui per mirare l'altrove che sta dietro la propria.  Ispirato da: Franz Kafka, Il processo (1925)


K-Means, B-SAS, problemi di Clustering con codice MATLAB

E-mail Stampa PDF

In questo articolo intendo presentare alcuni script in linguaggio MATLAB® per comprendere operativamente come funzionano gli algoritmi di "clustering", due in particolare: il "k-means" e il B-SAS. Prima di presentare gli script, come al solito un po di teoria.

1.0 Introduzione

1.1 Problema di k-clustering in logica crisp

1.2 K-means

1.3 Algoritmo B-SAS (Basic Sequential Algorithmic Scheme)

1.4 DOWNLOAD codice


1.0 Introduzione


Al presente, la ricerca scientifica, in particolare nel campo della Computer Science e dell'Atrificial Intelligence ha prodotto una serie di metodi che consentono alle macchine di "apprendere".  Tale termine andrebbe discusso e contestualizzato ampiamente, ciò non sarà fatto in questo articolo, ma il lettore attento potrà avere una idea, dopo aver compreso e provato gli algoritmi, su cosa si intende per "apprendimento automatico". In letteratura la disciplina che si occupa di studiare e sistematizzare le tecniche di apprendimento automatico è nota come "Machine Learning". In tale ambito è andata consolidandosi una serie di tecniche il cui scopo è modellare un qualsiasi processo fisico o astratto tramite i dati a disposizione. In particolare la Pattern Recognition, appartenente all'ambito generale del Datamining si prefigge lo scopo di classificare una serie di oggetti (pattern) in categorie o classi. La classificazione di tali discipline risulta ardua e non sarà discussa, si sottolinea che in letteratura anglosassone esse sono racchiuse nel generico termine di "Soft Computing".

Cioò che quì interessa è comprendere come il modello di un qualsivoglia processo possa essere ricavato dai dati a disposizione per tale processo (modellamento datadriven). Per inciso, la fisica presenta una serie di modelli matematici che spiegano la stragrande maggioranza dei fenomeni: le equazioni del moto sono un esempio. Tale tecica di modellamento può denominarsi analitica, poiché il modello del processo in questione è fornito analiticamente attraverso equazioni. Si possono pensare tuttavia tutta una serie di processi, la cui struttura analitica non è nota per varie ragioni: il processo è altamente complesso, il processo è altamente non lineare. Il modellamento analitico permette di indagare la natura delle leggi, ma ad oggi sappiamo che ciò non è sempre possibile. Al modellamneto analitico si contrappone il modellamento guidato dai dati (datadriven, appunto) dove il processo è considerato come una sorta diu scatola nera dove abbiamo una serie di ingressi ed una serie di uscite (questo accade se il processo è orientato, altrimenti si hanno solo le uscite ed il processo si definisce non orientato). Il processo è modellato tramite un sistema di calcolo capace di "apprendere un compito specifico tramite esempi".

Ricapitolando, il modellamento datadriven permette di sistetizzare il modello di un processo orientato o non tramite un campionamento sui dati, tale modello sostituisce qualsiasi sintesi analitica del processo considerato come una scatola nera (black box).

Nell'ambito del Machine Learning e del modellamento datadriven si distinguono due metodologie, la prima è nota come apprendimento o modellamento supervisionato, la seconda come come apprendimento o modellamento non supervisionato. La differenza è data dalla conoscenza a priori delle uscite del processo dati gli ingressi (quindi tale metodo si applica ai processi orientati, secondo la definizione accennata in precedenza). In altrer parole per alcuni particolari dati di ingresso (campionamento in ingresso) sono noti i dati di uscita (campionamento in uscita) così da poter sintetizzare una generica funzione test che permette di addestrare il modello per nuovi dati di ingresso (pattern) mai visti in precedenza, quindi differenti da quelli del campionamento iniziale. Per essere precisi questi due tipi di insiemi di campionamento hanno un nome specifico: training set e test set, con la proprietà che l'intersezione di tali insiemi sia vuota. Il modellamento non supervisionato non si avvale di tali conoscenze, ma nel modello stesso sono presenti gli ingredienti necessari per poter sintetizzare a dovere il modello di un opportuno processo.

Sintetizzando quanto detto la Pattern recognition attraverso il modellamento datadriven si prefigge lo scopo di operare una classificazione sui dati (classificazione quì è utilizzato come termine generico) ovvero di assegnare una etichetta ad ogni pattern generato dal processo e non presente quando il modello del processo è stato generato. A questo punto, brevemente si può introdurre un altro concetto legato a quanto detto: un sistema di modellamento siffatto possiede una capacità di generalizzazione ed è noto in letteratura come sistema di modellamento induttivo. Anche qui andrebbe aperta una discussione su cosa si intende per generalizzazione o modellamento induttivo in quanto si può finire nel paradosso secondo il quale un sistema computazionale ampiamente riconosciuto come deduttivo possa "creare" conoscenza induttiva grazie alla capacità di generalizzazione. Per approfondire qui ho tentato un approccio a tale discussione.

Dopo questa brevissima introduzione, possiamo definire cosa sia il clustering e quali istanze di problemi esso approccia.

La Cluster Analysis ha lo scopo di partizionare un insieme di dati in un certo numero di sottoinsiemi a seconda delle esigenze, le principali sono riassumibili in:

  • compressione dei dati;
  • generazione di ipotesi, ossia ricerca di possibili correlazioni tra le caratteristiche (feautures) che descrivono ciascun pattern;
  • verifica di ipotesi, ossia la validazione di ipotetiche correlazioni tra feautures;
  • sintesi di classificatori tramite tecniche di modellamento non supervisionato.

Intuitivamente, il numero di sottoinsiemi in cui un certo numero di pattern può essere clusterizzato può essere un dato di ingresso al problema ovvero già stabilito (problema di k-clustering) o da stabilire opportunamente (problema di free-clustering). Questa divisione rispecchia la tipolo9gia di modellamento che nel primo caso è supervisionata, nel secondo caso no, in quanto un opportuno criterio permette di stabilire il numero di cluster ottimale in cui l'insieme dei dati deve essere partizionato. Per completezza diamo la definizione di problema di k-clustering in logica crisp o aristotelica:

1.1 Problema di k-clustering in logica crisp

Dato un insieme di pattern «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mi»A«/mi»«mo»§#8834;«/mo»«mi»X«/mi»«/math» di cardinalità m ed un intero k>0, determinare una partizione «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mi»P«/mi»«mo»=«/mo»«mo»{«/mo»«msub»«mi»A«/mi»«mn»1«/mn»«/msub»«mo»,«/mo»«msub»«mi»A«/mi»«mn»2«/mn»«/msub»«mo»,«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo»,«/mo»«msub»«mi»A«/mi»«mi»k«/mi»«/msub»«mo»}«/mo»«/math» di «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mi»A«/mi»«/math» in k sottoinsiemi non vuoti e disgiunti: «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«msub»«mi»A«/mi»«mi»i«/mi»«/msub»«mo»§#8800;«/mo»«mo»§#8709;«/mo»«mo»§nbsp;«/mo»«mo»§#8704;«/mo»«mi»i«/mi»«mo»;«/mo»«mo»§nbsp;«/mo»«msub»«mi»A«/mi»«mi»i«/mi»«/msub»«mo»§#8745;«/mo»«msub»«mi»A«/mi»«mi»j«/mi»«/msub»«mo»=«/mo»«mo»§#8709;«/mo»«mo»§nbsp;«/mo»«mo»§nbsp;«/mo»«mo»§#8704;«/mo»«mi»i«/mi»«mo»§#8800;«/mo»«mi»j«/mi»«mo»§nbsp;«/mo»«mi»i«/mi»«mo»,«/mo»«mi»j«/mi»«mo»=«/mo»«mn»1«/mn»«mo»,«/mo»«mn»2«/mn»«mo»,«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo»,«/mo»«mi»k«/mi»«/math» in modo che elementi appartenenti allo stesso sottoinsieme siano "simili" ed elementi appartenenti a sottoinsiemi diversi siano "differenti", secondo un predefinito criterio di similitudine. L'intero k, numero di sottoinsiemi in cui «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mi»A«/mi»«/math» è suddiviso è noto come ordine della partizione P.

Dalla definizione si evince che un problema di clustering ha bisogno di una qualsivoglia misura di similarità. In altre parole i pattern appartenenti all'insieme dei dati vivono in uno spazio topologico normato su cui è definita tale misura. Un esempio classico è la distanza euclidea tra gli elementi appartenenti ad uno spazio multidimensionale. Detto questo possiamo fornire una definizione di cluster:

"Un cluster può essere descritto come una regione connessa di uno spazio multidimensionale caratterizzata da una densità relativamente alta di punti, separata da altre regioni simili da una zona caratterizzata da una bassa densità di punti".

La definizione precedente è in logica crisp, ciò significa che ogni elemento è assegnato ad un solo cluster, tale ipotesi può essere rilassata assegnando ad ogni elemento una misura di appartenenza fuzzy.

Importante è definire come rappresentare un cluster: ciò si può ottenere attraverso il centroide (una sorta di eleemnto medio), o attraqverso un inviluppo. Dopo tale definizione bisogna altresì definire la distanza "punto-insieme", che può essere definita come distanza tra l'elemento e il centroide o tra l'elemento e l'inviluppo. Ciò dipende da scelte progettuali dell'algoritmo di clustering.

1.2 K-means

L'algoritmo k-means permette di trovarare la partizione P dato l'insime dei dati A e l'ordine della partizione k.

In pseudo codice si hanno i seguenti passi:

Initialize mi,  i = 1,…,k, for example, to k random xt

Repeat

For all xt in X

bit <--  1 if || xt - mi || = minj || xt - mj ||

bit <-- 0 otherwise

For all mi,  i = 1,…,k

mi <-- sum over t (bit xt) / sum over t (bit )

Until mi converge

Il vettore m contiene il riferimento al centroide di ogni cluster, x è il generico elemento (pattern di esempio) e b contiene l'etichetta stimata per ogni cluster. La misura di similarità è la distanza euclidea.

Si nota che l'inizializzazione dei centroidi può essere casuale.

La spiegazione dell'algoritmo è la seguente:

  1. scegli secondo qualche criterio (random ad esempio) i parametri di inizializzazione dei centroidi mi dei k cluster.
  2. per ogni pattern di esempio dell'insieme di partenza genera una assegnazione al centroide più vicino (mi).
  3. per ogni cluster ricalcola il centroide mi basandosi sull'assegnazione corrente;
  4. ripeti i punti 2. e 3. fino a convergenza o soddisfacimento di un opportuno criterio di arresto

Un possibile criterio di arresto è stabilire a priori il numero di "epoche" o iterazioni dell'algoritmo. Se tale valore è elevato si può assistere ad una non stabile convergenza, allora si può stabilire un nuovo criterio che si basa sulla distanza δ tra il centroide all'iterazione precedente ed il centroide all'iterazione attuale. In definitiva è usuale mettere le due condizioni in OR logico, al fine di assicurarsi l'arresto.

Il k-means è utilizzato in numerosi problemi come ad esempio la character recognition, speech recognition, e problemi di codifica decodifica dei dati.

Ecco lo script MATLAB® che consente facilmente di testare l'lgoritmo di clustering k-means. Lo script richiama una funzione, riportata in seguito, per la generazione dei cluster.



<p>%prova num.7 clastering data una matrice di pattern in R^2
%--simulazione al variare della dispersione dei punti
%--condizioni di partenza casuali
%--inserimento matrice U(k,n) appartenenza puttern i-esimo al j-esimo
%cluster
%--con condizioni di arresto
clear all;
clc;
%___________________________________________________________________
%inizializzazione problema di k-clustering
N=6
spar=[0,10,30,50,80,100]; %sparpagliamento
 
 
for i=1:N
figure(i)
n=300; %numero di pattern
dim=2;%dimensione pattern (numero di caratteristiche)
MAX=10;%numero massimo iterazioni
delta=0.1;
 
%matrice dei pattern casuale uniforme (n x dim)
% a=0.7.*rand(n,dim);
%  c=4+randn(n,2).*(rand(n,2));
% b=randn(n,2).*(rand(n,2));
%  a=c+b;
 
%generazione pattern tramite funzione
e1=8; %polarizzazione cluster 1
e2=0; %polarizzazione cluster 2
a=cluster_gen(n,e1,e2,spar(i));
 
 
%grafico relarivo alla matrice dei pattern
for s=1:n
plot(a(s,1),a(s,2),'.');
hold on
end
 
 
%inizializzazione randomica
%scelta randomica di k centroidi
k=2; %numero di centroidi (k-clustering)
mu=e1*rand(k,dim); %centroidi casuale (matrice)
 
%grafico centroidi casuali
for s=1:k
plot(mu(s,1),mu(s,2),'*');hold on
end
 
%matrice che colleziona l'appartenenza degli n pattern ai k cluster
U=zeros(k,n);
 
centroide=zeros(k,dim);%inizializzazione matrice centroidi
nk=zeros(1,k); %numero di pattern appartenente al centroide s-esimo
 
%inizializzazione ciclo principale
%_______________________________________________________________________
 
iterazioni=0;   
arresto=0; %variabile "binaria"
 
while iterazioni~=MAX &amp;&amp; arresto==0    
iterazioni=iterazioni+1;
 
for i=1:n
 
for s=1:k     
 
dist(s,i)= sqrt(sum((mu(s,:)-a(i,:)).^2));
provadist=dist';%trasposizione
end % fine ciclo sui k cluster
[valore(i),indice(i)]=min((provadist(i,:)));
 
%assegno ogni pattern ad un centroide in accordo al minimo della
%funzione costo            
U(indice(i),i)=1;
 
end %fine ciclo sugli i pattern
 
%calcolo nuovo centroide
for s=1:k
centroide(s,:)=(U(s,:)*a)/sum(U(s,:));
end
%-----------------------------------------------------------------
%calcolo la differenza tra centroidi a passo "iter.." e "iter..-1"
app=(mu-centroide).^2;%matrice differenza con componenti al quadrato
for s=1:k
intercentroide(s,iterazioni)=sqrt(sum(app(s,:)));
end
%calcolo condizione per criterio di arresto
soglia=(sum(intercentroide))./k;
 
 
%-----------------------------------------------
%criterio di arresto
if (soglia(iterazioni))<delta arresto=1; end;
%-----------------------------------------------
%aggiornamento nuovo centroide
mu=centroide;
 
 
%_________
%plotting centoide      
for s=1:k
plot(centroide(s,1),centroide(s,2),'+r');hold on
end      
%________
 
end   %end ciclo while
hold off </p>

Di seguito si riporta la funzione che genera, letti i parametri di ingresso che sono il numero di pattern n, il centro (e1,e2) la deviazione standard (vettore "spar"), due cluster in «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«msup»«mi mathvariant=¨normal¨»§#8477;«/mi»«mn»2«/mn»«/msup»«/math» separati con distribuzione gaussiana.

<p>%funzione che genera  cluster spaziati con distribuzione gaussiana in R^2
 
function c=cluster_gen(s,e1,e2,spar)
 
n=s/2;
a=e1+randn(n,2);
b=e2+randn(n,2);
c=zeros(s,2);
cont=0;
for l=1:s
 
 
if l<s/2  c(l,:)=a(l,:); end;
if l>s/2 cont=cont+1; c(l,:)=b(cont,:); end;
end
 
c=c+spar*rand(s,2);
% for i=1:s
% plot(c(i,1),c(i,2),'.');
% hold on</p>


1.3 Algoritmo B-SAS (Basic Sequential Algorithmic Scheme)

Per il k-means l'insieme dei parametri cosiddetti di training è il numero di iterazioni (o da altro criterio di arresto) e dal fondale parametro k, che definisce il numero si sottoinsiemi in cui partizionare l'insieme dei pattern di partenza.

In molti casi k non è disponibile a priori come parametri di ingresso, ma deve essere calcolato. Algoritmi con tali caratteristiche sono noto come algoritmi di free clustering. Esso è definito come segue:

Dato un insieme di pattern «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mi»A«/mi»«mo»§#8834;«/mo»«mi»X«/mi»«/math» di cardinalità m determinare un intero k>0 e una partizione «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mi»P«/mi»«mo»=«/mo»«mo»{«/mo»«msub»«mi»A«/mi»«mn»1«/mn»«/msub»«mo»,«/mo»«msub»«mi»A«/mi»«mn»2«/mn»«/msub»«mo»,«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo»,«/mo»«msub»«mi»A«/mi»«mi»k«/mi»«/msub»«mo»}«/mo»«/math» di «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mi»A«/mi»«/math» in k sottoinsiemi non vuoti e disgiunti: «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«msub»«mi»A«/mi»«mi»i«/mi»«/msub»«mo»§#8800;«/mo»«mo»§#8709;«/mo»«mo»§nbsp;«/mo»«mo»§#8704;«/mo»«mi»i«/mi»«mo»;«/mo»«mo»§nbsp;«/mo»«msub»«mi»A«/mi»«mi»i«/mi»«/msub»«mo»§#8745;«/mo»«msub»«mi»A«/mi»«mi»j«/mi»«/msub»«mo»=«/mo»«mo»§#8709;«/mo»«mo»§nbsp;«/mo»«mo»§nbsp;«/mo»«mo»§#8704;«/mo»«mi»i«/mi»«mo»§#8800;«/mo»«mi»j«/mi»«mo»§nbsp;«/mo»«mi»i«/mi»«mo»,«/mo»«mi»j«/mi»«mo»=«/mo»«mn»1«/mn»«mo»,«/mo»«mn»2«/mn»«mo»,«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo»,«/mo»«mi»k«/mi»«/math» in modo che elementi appartenenti allo stesso sottoinsieme siano "simili" ed elementi appartenenti a sottoinsiemi diversi siano "differenti", secondo un predefinito criterio di similitudine. L'intero k, numero di sottoinsiemi in cui «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mi»A«/mi»«/math» è suddiviso è noto come ordine della partizione P.

La definizione è simile al problema di k-clustering solo che qui k è una incognita del problema e non un dato fissato a priori.

Il parametro k spesso è calcolato in base ad opportuni criteri (specificatamente da un parametro strutturale «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mi»§#952;«/mi»«mo»§#8712;«/mo»«mi»§#920;«/mi»«/math»), ad esempio la massima dimensione consentita per ciascun cluster oppure una specifica legge di espansione del cluster stesso. In generale si dice che sia k che PA sono funzione dei parametri strutturali «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mi»§#920;«/mi»«/math».

Un seplice algoritmo di free clustering è il B-SAS (Basic Sequential Algorithmic Scheme) noto anche come "regola delta", che si basa su un parametro strutturale definito come una soglia di inclusione di un pattern in un determinato cluster.

Lo pseudo codice per il B-SAS è il seguente:

initialize: cluster list L represented by centroid

FOR i=1 TO m (for any vector xi in A)

{IF (L=Ø) THEN {generate first cluster and take his centroid as xi}

ELSE

{calculate centroid list Liδ which distance from xi is minor or equal to δ}

IF (Liδ=Ø)

THEN {create in L a new cluster end take relative centroid as xi}

ELSE

{put xi in Cj cluster (represented by cj) in Liδ which has minimum distance from xi and refresh the centroid «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«msup»«msub»«mi mathvariant=¨bold-italic¨»c«/mi»«mi»j«/mi»«/msub»«mrow»«mo»(«/mo»«mi»n«/mi»«mi»e«/mi»«mi»w«/mi»«mo»)«/mo»«/mrow»«/msup»«mo»=«/mo»«mfrac»«mrow»«msup»«msub»«mi mathvariant=¨bold-italic¨»c«/mi»«mi»j«/mi»«/msub»«mrow»«mo»(«/mo»«mi»o«/mi»«mi»l«/mi»«mi»d«/mi»«mo»)«/mo»«/mrow»«/msup»«mo»§#183;«/mo»«msub»«mi»n«/mi»«mi»j«/mi»«/msub»«mo»*«/mo»«msub»«mi mathvariant=¨bold-italic¨»x«/mi»«mi»j«/mi»«/msub»«/mrow»«mrow»«msub»«mi»n«/mi»«mi»j«/mi»«/msub»«mo»+«/mo»«mn»1«/mn»«/mrow»«/mfrac»«/math» where nj is the cardinality of Cj before the insertion of xi}

}

}

L'algoritmo analizza i pattern in A una sola volta e a seconda del valore di δ, può clusterizzare in numerosi insiemi  (δ piccolo) o in pochi insiemi (δ grande).

In generale sia per il k-clustering che per il free clustering può essere effettuato un cosiddetto campionamento nello spazio dei poarametri «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mi»§#920;«/mi»«/math», ogni uno dei quali genera una specifica partizione P di A e scegliere quella che rispetta determinate condizioni di ottimalità. L'insermento di tali algoritmi di clustering in "contenitori" di ottimizzazione genera i cosiddetti algoritmi di clustering ottimizzati. Si accenna all'esistenza di numerosi parametri e misure di distanza tra partizioni per caratterizzare il probnlema di clustering.


[al momento è fornito lo script principale nel seguito l'articolo sarà aggiornato con gli indici di validazione e l'indice di compattezza e separabilità di Davis - Bouldin, nonchè il meccanismo di induzione nel clustering Winner Take All (WTA)]


%ALGORITMO BSAS con variazione parametro delta, calcolo numero di cluster
%ottimo
%(codice ripulito)
clear;clc;
 
%prova struct
clear;clc;
%__________________________________________________________________________
 
%Parametro free clustering
%valore limite pari alla diagonale ipercubo unitario se i dati sono 
%normalizzati
delta=[0.125:0.00675/2:sqrt(2)];
 
 
%--------------------------------------------------------------------------
%inizializzazione problema di free-clustering
n=200; %numero di pattern
dim=2;%dimensione pattern (numero di caratteristiche)
 
 
%__________________________________________________________________________
%si vuole dataset normalizzato?
norm=1; %normalizzazione dataset
 
%Parametri generazione cluster
%Numero di cluster
Nc=4;
 
%POLARIZZAZIONI
e11=10; %CL 1 
e21=10; %CL 1
 
e12=0;  %CL 2
e22=0;  %CL 2
 
e13=0;  %CL 3
e23=0;  %CL 3
 
e14=0; %CL 4
e24=0; %CL 4
 
var1=10;
var2=0;
var3=0;
var4=0;
spar=0; %sparpagliamento
 
POL={[e11;e21],[e12;e22],[e13;e23],[e14;e24]};
%__________________________________________________________________________
 
%%%%%%%GENERAZIONE CLUSTER
[a,nCeffett]=cluster_gen(n,Nc,POL,var1,var2,var3,var4,spar,norm);
 
 
n=nCeffett;
%__________________________________________________________________________
 
%grafico relarivo alla matrice dei pattern
figure(1)
for s=1:n
plot(a(s,1),a(s,2),'.');
hold on
end
%hold off
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%CICLO SUL PARAMETRO DELTA%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Lstore={};
Lstore2={};
for m=1:length(delta)
 
m%stampo il numero di ciclo
%inizializzazione LISTA centroidi come aray di celle
L={};
%inizializzo lista centroidi al passo iesimo (listadelta i-esima) come arry
%di celle
listadelta={};
 
%parametri cdi controllo non necessari
indicevett={};njvett=[];
cj=[];
%--------------------------------------------------------------------------
 
%%%%%%%%%%%%%%%%%%%%%%%%Algoritmo di clustering BSAS%%%%%%%%%%%%%%%%%%%%%%%
for i=1:n
%-----
%conmtrollo se L è vuota
if (isempty(L)) 
 
L(i,:)={[a(i,:)],[a(i,:)]}; 
%sprintf('ciclo %d,lista L vuota \ncreo primo centroide \n',i)
%------
else     
%inizializzazione parametri controllo distanza tra pattern e
%centroidi in L
distanza=0;
indice=0;
distanzaList=[];
listadelta={};
 
%parametri di controllo non necessari
contDistminDelta=0;
nj=0;
 
%ciclo sul numero di cluster in L al passo i-esimo
for k=1:size(L,1)  
 
%valutazione distanza tra pattern e centroide in L
distanza=sqrt(sum((a(i,:)-L{k}).^2));
 
%   sprintf('ciclo %d,distanza %d,indice %d \n',i,distanza,indice)          
 
 
if (distanza<delta(m)) 
%      sprintf('ciclo %d,distanza<delta \n',i)
 
contDistminDelta=contDistminDelta+1;
 
%listadelta(contDistminDelta,:)=L(k,:)
listadelta(k,:)=L(k,:);
end   
end
 
for u=1:size(listadelta,1)
if (~cellfun(@isempty,listadelta(u)))
distanzaList(u)=sqrt(sum((a(i,:)-listadelta{u}).^2));
 
else distanzaList(u)=1*10^10;
end
end
[distminima indice]=min(distanzaList);    
indicevett(i)={indice};
 
 
%controllo se la lista dei centroidi al passo i-esimo a distanza 
%minore di delta è vuota 
%------ 
if (isempty(listadelta)) %L=[L;a(i,:)]; 
%  sprintf('ciclo %d,listadelta vuota \naggiungo centroide a L \n',i)
 
%se vuota genero nuovo cluster in L con pattern attuale
%(i-esimo)
L=[L;{a(i,:),a(i,:)}];
 
%------       
else
%1)se non vuota lista delta passo i-esimo, calcolo il centroide più
%vicino al pattern attuale (i-esimo)
%2)inserisco il pattern attuale nella lista L corrispondente al
%3)centroide calcolato
%4)aggiorno il rappresentante attraverso la media dei pattern in lista 
 
%parametri non necessari
nj=size(L{indice,2},1);
njvett(i)=size(L{indice,2},1);
 
 
%aggiunta pattern a(i,:) alla matrice centroidi nella lista
%L(indice)
L{indice,2}=[L{indice,2};a(i,:)];
%calcolo il nuovo centroide come la media degli N=size(L{1,2},1)
%pattern i L{indice }
% cj=sum(L{1,2})/size(L{1,2},1);sbagliato
cj=sum(L{indice,2})/size(L{indice,2},1);
%aggiornamento centroide;
L{indice,1}=cj;     
 
end
end
 
end  %fine algoritmo BSAS (i)     
 
%calcolo il numero di centroidi al passo m (M=length(delta))        
NcentroidiDelta(m)=size(L,1);
% if NcentroidiDelta(m)==2 
%     figure(1)
%    plot(L{1,1}(1,1),L{1,1}(1,2),'r*')
%    plot(L{2,1}(1,1),L{2,1}(1,2),'r*')
% end
 
Lstore(m)={L(:,1)};
Lstore2(m)=[{L}];
 
end %fine ciclo principale su delta (m)
 
%lista per numero di centroidi (dimensione lista L) al variare del
%parametro delta
NumcentrDelta={};
for r=1:length(NcentroidiDelta)
NumcentrDelta(r,1)={NcentroidiDelta(r)};
NumcentrDelta(r,2)={delta(r)};
end
 
 
 
%Plotting Numero di centroidi al variare di delta
figure(2)
stem([NumcentrDelta{:,2}],[NumcentrDelta{:,1}])
title('Numero centroidi vs DELTA')
xlabel('DELTA')
ylabel('NUMCentroidi')
 
%calcolo il numero di occorrenze di uno stesso delta rispetto al numero di cluster
counter=[];
for j=1:max(NcentroidiDelta)
counter(j)=length(find(NcentroidiDelta==j));
 
%u=max(NcentroidiDelta)-j;
 
if counter(j)~=0;
 
%min(find(NcentroidiDelta==j))
prv(j)=min(find(NcentroidiDelta==j)); 
assex(j)=NcentroidiDelta(min(find(NcentroidiDelta==j)));
 
end
 
end
 
%plotting numero di occorrenze di uno stesso delta rispetto al numero di
%cluster
figure(3)
plot(assex,counter,'*')
title('occorrenze stesso delta vs Numero cluster')
xlabel('Numero cluster')
ylabel('occorrenze delta')
 
 
 
vettMass=counter;
vettMass(1)=0;
 
if var1==0 v1=0;
else v1=1;end
if var2==0 v2=0;
else v2=1;end
if var3==0 v3=0;
else v3=1;end
if var4==0 v4=0;
else v4=1;end
 
vsomma=v1+v2+v3+v4;
 
[max ind]=max(vettMass)
 
indelta=find([NumcentrDelta{:,1}]==ind);
 
fprintf('il numero di pattern è: %d \n',n)
fprintf('il numero di cluster effettivo è: %d \n',vsomma)
fprintf('il numero di cluester stimato è: %d \n',ind)
 
 
 
fprintf('per un intervallo del parametro delta pari a: %d -- %d \n',delta(min(indelta)),delta(-min(-indelta)))
fprintf('Cho azzeccato??!??!?')
 
for r=1:ind
figure(1)
plot(Lstore{min(indelta)}{r,1}(1),Lstore{min(indelta)}{r,1}(2),'r*')
 
end
hold off
 
%sistemazione Lista centroidi(eliminazione duplicati)
Lstore3=Lstore2(1);
cont=1;
 
 
for i=2:size(Lstore2,2)
 
if size(Lstore2{i},1)~=size(Lstore2{i-1},1)
cont=cont+1;
Lstore3(cont)=Lstore2(i);
end
 
end
save clusterdeltac Lstore NumcentrDelta Lstore3 a 




DOWNLOAD Script in formato compresso!



[*] Il presente materiale è una rielaborazione personale delle dispense del cosrso di "Soft Computing" tenuto dal prof. Antonello Rizzi presso la facoltà di Ingegneria dell'università La Sapeinza di Roma


[**] Lettura consigliata: Konstantinos Koutroumbas, Sergios Theodoridis, Pattern Recognition, 2006, Elsevier USA.

Hanno detto..

You are here: Script Matlab K-Means, B-SAS, problemi di Clustering con codice MATLAB