[C] fkmeans - C library for clustering data through k-means

[imported_BlackLight]

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:

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:

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. Ogni cluster contiene poi a sua volta gli elementi del dataset associati, ognuno di dimensione dataset_dim.

Esempio per esplorare i cluster:

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:

./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:

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.

 

[PyLinX]

Spero di diventare come te, sei veramente unico in quello che fai. Ti ammiro...

 

[TheGadget]

Non so se è il posto giusto dove chiedere, ma tentar non nuoce, quindi...
Volevo chiedere come si approssima matematicamente un cluster ad un punto.