Il Forum di Orebla.it

Benvenuto nella community di Orebla.it
Oggi è mer 19 set, 2018 5:32 pm

Tutti gli orari sono UTC + 1 ora




Apri un nuovo argomento Rispondi all’argomento  [ 1 messaggio ] 
Autore Messaggio
Messaggio da leggereInviato: ven 19 nov, 2010 11:40 am 
Non connesso
super-guru
super-guru
Avatar utente

Iscritto il: mar 28 dic, 2004 6:54 pm
Messaggi: 300
Località: Pisa
Alcuni sapranno che da un po' sono al lavoro su un modulo per Snort che consente il clustering e la correlazione intelligente di security alerts, con un'interfaccia web integrata per la navigazione e la manipolazione di cluster e grafi di correlazione. Una di queste componenti è la SOM, una rete neurale auto-associativa che esprime (in parole povere) quanto sono correlati due alerts in funzione della loro distanza euclidea fra i loro punti associati sul layer di output, e già a suo tempo per sviluppare questa feature avevo sviluppato una micro-libreria (fsom) già rilasciata. L'idea ora è stata quella di non limitarsi al calcolo della correlazione fra due alert come distanza euclidea (quindi valore numerico), ma prendere il layer di output nel suo complesso, che è una matrice, e trovare i "cluster" di alert, ovvero gli alert marcati come logicamente vicini fra loro. Questi alert molto probabilmente faranno parte dello stesso scenario di attacco, che verrà quindi isolato dal resto.

L'implementazione di questa logica è stata fatta implementando il C l'algoritmo di clustering k-means, probabilmente "il clustering" per eccellenza, ma per quanto sia tanto noto e documentato come algoritmo in giro si fa fatica a trovare librerie in C che consentano di applicarlo a dataset arbitrari di qualsiasi dimensione. Quindi ho cominciato a scrivere il mio codice, estendendo il k-means applicando il criterio di Schwarz per "indovinare" automaticamente il numero ottimale di cluster nel dataset di partenza (il k-means classico prevede che il numero di cluster sia fornito a priori). Ovviamente il k-means classico, fornito il numero di cluster k in partenza, è ancora possibile, a seconda che si usi il metodo kmeans() o kmeans_auto().

Anche qui ho notato che il codice che avevo scritto era riutilizzabile anche in altri contesti, quindi perché non rilasciarlo come libreria? Il risultato è fkmeans, una micro-libreria in C ( https://github.com/BlackLight/fkmeans ) per l'aggregazione di dataset numerici qualsiasi n-dimensionali in cluster. L'interfaccia è volutamente resa minimale e intuitiva: il dataset numerico da aggregare è fornito come vettore di vettori (double**), dove ogni vettore è un elemento n-dimensionale del cluster. Quindi, per aggregare ad esempio un dataset 3-dimensionale composto da N vettori in un numero di cluster n_cluster, basterà questo codice:

Codice:
kmeans_t *km;
double **dataset;
...
km = kmeans_new ( dataset, N, 3, n_cluster );
kmeans ( km );
...
kmeans_free ( km );


Se invece il numero di cluster non è noto a priori e si vuole che l'algoritmo lo calcoli automaticamente attraverso il criterio di Schwarz (o almno fornisca una stima probabile di questo numero), è possibile usare quest'approccio:

Codice:
kmeans_t *km;
double **dataset;
...
km = kmeans_auto ( dataset, N , 3 );
...
kmeans_free ( km );


Una volta inizializzato l'oggetto kmeans_t ed eseguito il k-means si possono esplorare i cluster trovati dall'algoritmo tenendo conto di un paio di semplici cose:

* Il campo 'k' della struttura kmeans_t contiene il numero di cluster trovati dall'algoritmo;
* Il campo 'dataset_size' contiene il numero di elementi nel dataset di partenza;
* Il campo 'dataset_dim' è la dimensione di ognuno degli elementi del dataset (se il dataset è 3-dimensionale, ad esempio, dataset_dim sarà 3 e ogni vettore nel cluster avrà dimensione 3);
* Il campo 'cluster_sizes' è un vettore di int contenente la dimensione di ogni cluster, ovvero il numero di elementi che vi sono contenuti;
* Il campo 'clusters' è un vettore di vettori di elementi del dataset, a loro volta vettori (double***). Tale vettore contiene 'k' elementi, ogni elemento rappresenta un cluster trovato. Ogni vettore i-esimo rappresenta un cluster trovato dall'algoritmo, di dimensione cluster_sizes[i]. Ogni cluster contiene poi a sua volta gli elementi del dataset associati, ognuno di dimensione dataset_dim.

Esempio per esplorare i cluster:

Codice:
for ( i=0; i < km->k; i++ )
{
   printf ( "Cluster %d: [ ", i );

   for ( j=0; j < km->cluster_sizes[i]; j++ )
   {
      printf ( "( " );

      for ( k=0; k < km->dataset_dim: k++ )
      {
         printf ( "%f, ", km->clusters[i][j][k] );
      }

      printf ( "), " );
   }

   printf ( "]\n" );
}


Il README contiene ulteriori informazioni a riguardo, ed è anche possibile generare la documentazione della libreria automaticamente in formato doxygen dando semplicemente il comando `doxygen'. Inoltre è contenuto il file `test.c', compilabile semplicemente dando `make', che è un esempio di applicazione della libreria per il clustering di un dataset bidimensionale con elementi generati in modo casuale. Il programma, una volta compilato, può prendere 0, 1, 2 o 3 argmenti, con sintassi:

Codice:
./kmeans-test [num_items] [min_coord] [max_coord]


Il dataset verrà generato in modo casuale in funzione di questi parametri, quindi il programma troverà il numero ottimale di cluster contenuto lì e li mostrerà con colori diversi. Esempio:

Immagine

Per compilare i sorgenti con questa libreria basta

* Includere il file 'kmeans.h';
* Usare normalmente le funzioni kmeans_new(), kmeans(), kmeans_auto() e kmeans_free();
* Compilare includendo nella lista dei file sorgenti il file 'kmeans.c'.

E questo è tutto. Buon coding.

_________________
Immagine
Immagine


Top
 Profilo  
 
Visualizza ultimi messaggi:  Ordina per  
Apri un nuovo argomento Rispondi all’argomento  [ 1 messaggio ] 

Tutti gli orari sono UTC + 1 ora


{ RELATED_TOPICS }
 Argomenti   Autore   Risposte   Visite    Ultimo messaggio 
Non ci sono nuovi messaggi in questo argomento. [C] fsom - Fast Self-Organizing Maps library

BlackLight

0

1362

dom 31 ott, 2010 2:50 am

BlackLight Vedi ultimi messaggi

 


Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite


Non puoi aprire nuovi argomenti
Non puoi rispondere negli argomenti
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi inviare allegati

Cerca per:
Vai a:  
cron
Powered by phpBB® Forum Software © phpBB Group
Traduzione Italiana phpBBItalia.net basata su phpBB.it 2010
phpBB SEO