Il presente articolo è stato tradotto automaticamente.
Clustering di dati
Rilevamento di dati anomali con il clustering k-Means
Download the Code Sample (VB Version)
Si consideri il problema di individuare gli elementi di dati anomali in un grande set di dati, ad esempio, identificando potenzialmente fraudolente transazioni con carta di credito, le applicazioni di prestito rischioso e così via. Un approccio alla rilevazione dei dati anomali è quello di raggruppare gli elementi di dati in cluster simili e poi cercare gli elementi di dati all'interno di ogni cluster sono in un certo senso diversi da altri elementi di dati all'interno del cluster.
Ci sono molti diversi algoritmi di clustering. Uno dei più antichi e più ampiamente usato è l'algoritmo k-means. In questo articolo farò spiegare come funziona l'algoritmo k-means e presentare un completo programma di demo C#. Ci sono molti standalone clustering di dati strumenti esistenti, così perché si vuole creare k-means clustering codice da zero? Esistenti strumenti di clustering possono essere difficili o impossibili da integrare in un sistema software, potrebbero non essere personalizzabile per affrontare scenari inusuali, e gli strumenti potrebbero avere sul copyright o altre questioni di proprietà intellettuale. Dopo aver letto questo articolo, sarete in grado di sperimentare con k-means clustering e di avere le conoscenze di base per aggiungere funzionalità di clustering per un'applicazione .NET.
Il modo migliore per avere un'idea di cosa k-means clustering è e vedere dove sono diretto in questo articolo è quello di dare un'occhiata a Figura 1. Il programma demo inizia creando un manichino set di 20 dati elementi. Nel clustering di terminologia, gli elementi di dati sono a volte chiamati Tuple. Qui ogni tupla rappresenta una persona e ha due valori di attributo numerico, un'altezza in centimetri e un peso in libbre. Uno dei limiti dell'algoritmo k-means è che essa si applica solo in casi dove le tuple di dati sono completamente numeriche.
.png)
Figura 1 Clustering utilizzando k-Means
I dati fittizi viene caricati in un array in memoria. Successivamente, il numero di cluster è impostato su tre. Anche se ci sono avanzati clustering di tecniche che possono suggerire il numero ottimale di cluster da utilizzare, in generale il clustering di dati è un processo esplorativo e il miglior numero di cluster da utilizzare si trova in genere attraverso tentativi ed errori. Come vedrà a breve, k-means clustering è un processo iterativo. Il programma demo è una variabile maxCount, che viene utilizzato per limitare il numero di volte in cui che verrà eseguito il ciclo principale di clustering. Qui quel valore arbitrariamente è impostato su 30.
Successivamente, dietro le quinte, il programma demo utilizza l'algoritmo k-means a mettere ogni tupla di dati in uno dei tre poli. Ci sono molti modi per codificare un clustering. In questo caso, un clustering è definita da una matrice di int dove l'indice della matrice rappresenta una tupla, e il valore di matrice associati rappresenta l'ID di cluster basato su 0. Così, in Figura 1, tupla 0 (65.0, 220.0) viene assegnato al cluster 0, tuple 1 (73.0, 160.0) viene assegnata al cluster 1, tupla 2 (59,0, 110.0) viene assegnato al cluster 2, tupla 3 (61,0, 120,0) viene assegnato al cluster 2 e così via. Notare che ci sono otto le tuple assegnate a cluster 0, cinque Tuple assegnate al cluster 1 e sette Tuple assegnate al cluster 2.
Successivamente, il programma demo Visualizza i dati, raggruppati per cluster. Se si esaminano i dati in cluster vedrai che cluster 0 potrebbe essere chiamato il cluster di persone pesanti, cluster 1 potrebbe essere chiamato il cluster di persone alte e cluster 2 potrebbe essere chiamato il cluster short people. Il programma demo si conclude analizzando le tuple assegnate a 0 del cluster e determina che da qualche criterio, tupla 5 (67.0, 240.0) è la tupla più anormale.
Nelle sezioni che seguono, vi guiderò attraverso il codice che ha prodotto lo screenshot in Figura 1 modo che sarete in grado di modificare questo codice per soddisfare le proprie esigenze. Questo articolo presuppone che avete abilità di programmazione almeno a livello intermedio con un linguaggio C-famiglia, ma non si assume che si sa nulla di clustering di dati. Ho codificato il programma demo utilizzando c#, ma ho usato uno stile non-OOP, quindi non dovreste avere troppe difficoltà refactoring la demo in un'altra lingua, se lo si desidera. Tutto il codice sorgente per il programma demo presentate in questo articolo. Il codice sorgente è anche disponibile presso archive.msdn.microsoft.com/mag201302kmeans.
L'algoritmo k-Means
In linea di principio, almeno, l'algoritmo k-means è abbastanza semplice. Ma, come vedrete, alcuni dettagli di implementazione sono un po ' complicati. Il concetto centrale dell'algoritmo k-means è il baricentro. Nel clustering di dati, il baricentro di un set di dati Tuple è una tupla è più rappresentativo del gruppo. L'idea è meglio spiegato da esempio. Si supponga di avere tre altezza-peso Tuple simili a quelli riportati Figura 1:
[a] (61.0, 100.0)
[b] (64.0, 150.0)
[c] (70.0, 140.0)
Quale tupla è più rappresentativo? Un approccio è quello di calcolare una tupla di matematica media (Media) e quindi selezionare come il baricentro della tupla che è più vicina a quella media tuple. Così, in questo caso, la tupla media è:
[m] = ((61.0 + 64.0 + 70.0) / 3, (100.0 + 150.0 + 140.0) / 3)
= (195.0 / 3, 390.0 / 3)
= (65.0, 130.0)
E ora, che le tre Tuple è più vicina (65,0, 130.0)? Ci sono diversi modi per definire più vicino. L'approccio più comune e quello utilizzato nel programma demo, è utilizzare la distanza euclidea. In parole, la distanza euclidea tra due tuple è la radice quadrata della somma delle differenze al quadrato tra ogni componente delle tuple. Ancora una volta, un esempio è il modo migliore per spiegare. La distanza euclidea tra tuple (61,0, 100.0) e la media tuple (65.0, 130.0) è:
dist(m,a) = sqrt((65.0 - 61.0)^2 + (130.0 - 100.0)^2)
= sqrt(4.0^2 + 30.0^2)
= sqrt(16.0 + 900.0)
= sqrt(916.0)
= 30.27
Allo stesso modo:
dist(m,b) = sqrt((65.0 - 64.0)^2 + (130.0 - 150.0)^2)
= 20.02
dist(m,c) = sqrt((65.0 - 70.0)^2 + (130.0 - 140.0)^2)
= 11.18
Perché la più piccola delle tre distanze è la distanza tra la media matematica e tuple [c], il baricentro di tre Tuple è tuple [c]. Si potrebbe voler sperimentare con il programma demo utilizzando diverse definizioni della distanza tra due Tuple per vedere come quelli interessano il raggruppamento finale prodotto.
Con la nozione di un centroide del cluster stabilito, l'algoritmo k-means è relativamente semplice. In pseudocodice:
assign each tuple to a randomly selected cluster
compute the centroid for each cluster
loop until no improvement or until maxCount
assign each tuple to best cluster
(the cluster with closest centroid to tuple)
update each cluster centroid
(based on new cluster assignments)
end loop
return clustering
Se cercate sul Web, è possibile trovare diverse buone animazioni online dell'algoritmo k-means in azione. L'immagine in Figura 2 illustrato il clustering prodotta dal programma demo. L'elemento di dati cerchiato in ogni cluster è il centroide del cluster.
.png)
Figura 2 cluster dati e i centroidi
Struttura generale del programma
La struttura generale del programma per la demo mostrata Figura 1, con alcune modifiche minori, è elencato Figura 3. Ho usato Visual Studio 2010 per creare una nuova applicazione console c# denominata ClusteringKMeans; ogni versione recente di Visual Studio dovrebbe funzionare, troppo. Nella finestra Solution Explorer ho rinominato il file Program. cs per ClusteringKMeansProgram, che automaticamente rinominato la classe modello generato. Ho rimosso non necessari utilizzando le istruzioni all'inizio del file.
Figura 3 struttura generale del programma
using System;
namespace ClusteringKMeans
{
class ClusteringKMeansProgram
{
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin outlier data detection demo\n");
Console.WriteLine("Loading all (height-weight) data into memory");
string[] attributes = new string[] { "Height", "Weight" };
double[][] rawData = new double[20][];
rawData[0] = new double[] { 65.0, 220.0 };
rawData[1] = new double[] { 73.0, 160.0 };
rawData[2] = new double[] { 59.0, 110.0 };
rawData[3] = new double[] { 61.0, 120.0 };
rawData[4] = new double[] { 75.0, 150.0 };
rawData[5] = new double[] { 67.0, 240.0 };
rawData[6] = new double[] { 68.0, 230.0 };
rawData[7] = new double[] { 70.0, 220.0 };
rawData[8] = new double[] { 62.0, 130.0 };
rawData[9] = new double[] { 66.0, 210.0 };
rawData[10] = new double[] { 77.0, 190.0 };
rawData[11] = new double[] { 75.0, 180.0 };
rawData[12] = new double[] { 74.0, 170.0 };
rawData[13] = new double[] { 70.0, 210.0 };
rawData[14] = new double[] { 61.0, 110.0 };
rawData[15] = new double[] { 58.0, 100.0 };
rawData[16] = new double[] { 66.0, 230.0 };
rawData[17] = new double[] { 59.0, 120.0 };
rawData[18] = new double[] { 68.0, 210.0 };
rawData[19] = new double[] { 61.0, 130.0 };
Console.WriteLine("\nRaw data:\n");
ShowMatrix(rawData, rawData.Length, true);
int numAttributes = attributes.Length;
int numClusters = 3;
int maxCount = 30;
Console.WriteLine("\nk = " + numClusters + " and maxCount = " + maxCount);
int[] clustering = Cluster(rawData, numClusters, numAttributes, maxCount);
Console.WriteLine("\nClustering complete");
Console.WriteLine("\nClustering in internal format: \n");
ShowVector(clustering, true);
Console.WriteLine("\nClustered data:");
ShowClustering(rawData, numClusters, clustering, true);
double[] outlier = Outlier(rawData, clustering, numClusters, 0);
Console.WriteLine("Outlier for cluster 0 is:");
ShowVector(outlier, true);
Console.WriteLine("\nEnd demo\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
// 14 short static method definitions here
}
}
Per semplicità ho usato un approccio di metodo statico e rimossi tutti i controllo di errore. La prima parte del codice demo imposta i dati di altezza e peso per essere raggruppati. Perché ci sono solo 20 Tuple, ho codificato i dati e i dati memorizzati nella memoria in un array denominato rawData. In genere, i dati verranno memorizzati in un file di testo o una tabella SQL. In questi casi è necessario scrivere una funzione di supporto per caricare i dati in memoria. Se l'origine dati è troppo grande per stare nella memoria del computer, dovrete modificare il codice demo per scorrere un'origine dati esterna, piuttosto che una matrice di dati.
Dopo aver impostato i dati raw, il programma demo chiama la funzione di supporto ShowMatrix per visualizzare i dati. Successivo, le variabili nummaxCount, numClusters e gli attributi sono assegnati valori di 2 (altezza e peso), 3 e 30, rispettivamente. Richiamo maxCount limita il numero di iterazioni del ciclo di elaborazione principale algoritmo. L'algoritmo k-means tende a convergere rapidamente, ma potrebbe essere necessario sperimentare un po ' con il valore di maxCount.
Tutto il lavoro di clustering è eseguito dal metodo Cluster. Il metodo restituisce un array di int che definisce come ogni tupla è assegnato ad un cluster. Dopo aver terminato, il programma demo Visualizza il clustering codificato e visualizza anche i dati grezzi, raggruppati in base al cluster.
Il programma demo si conclude analizzando i dati in cluster per outlier, possibilmente anormale, Tuple utilizzando il metodo outlier. Tale metodo accetta un ID del cluster e restituisce i valori della tupla dati che è la più lontana (come misurato dalla distanza euclidea) dal centroide del cluster (tuple più rappresentativi). In questo caso, per ammasso 0, la persona pesante, la tupla outlier è (240,0, 67.0), la persona più pesante.
Computing Cluster centroidi
Ricordiamo che un centroide del cluster è una tupla che è più rappresentativo delle tuple assegnate a un cluster, e che un modo per determinare un centroide del cluster è quello di calcolare una tupla di media matematica e poi trovare una tupla è più vicina alla media tupla. Metodo Helper UpdateMeans calcola la tupla media matematica per ogni cluster ed è elencato in Figura 4.
Figura 4 Metodo UpdateMeans
static void UpdateMeans(double[][] rawData, int[] clustering,
double[][] means)
{
int numClusters = means.Length;
for (int k = 0; k < means.Length; ++k)
for (int j = 0; j < means[k].Length; ++j)
means[k][j] = 0.0;
int[] clusterCounts = new int[numClusters];
for (int i = 0; i < rawData.Length; ++i)
{
int cluster = clustering[i];
++clusterCounts[cluster];
for (int j = 0; j < rawData[i].Length; ++j)
means[cluster][j] += rawData[i][j];
}
for (int k = 0; k < means.Length; ++k)
for (int j = 0; j < means[k].Length; ++j)
means[k][j] /= clusterCounts[k]; // danger
return;
}
UpdateMeans metodo presuppone che un array di array denominato mezzi già esiste, in contrasto con la creazione della matrice e poi restituirlo. Perché si presume che la matrice mezzi esistono, si potrebbe voler renderlo un parametro ref. Matrice mezzi viene creato utilizzando il metodo di supporto Allocate:
static double[][] Allocate(int numClusters, int numAttributes)
{
double[][] result = new double[numClusters][];
for (int k = 0; k < numClusters; ++k)
result[k] = new double[numAttributes];
return result;
}
Il primo indice dei mezzi matrice rappresenta un ID del cluster e il secondo indice indica l'attributo. Ad esempio, se significa [0] [1] = 150.33 poi la media dei valori di peso (1) di tuple in cluster 0 è 150.33.
Metodo UpdateMeans innanzitutto azzera i valori esistenti nella matrice mezzi, poi scorre ogni tupla dati quadro il numero di tuple in ogni cluster e accumula le somme per ogni attributo e quindi divide ogni somma accumulata per il conteggio dei cluster appropriato. Si noti che il metodo genererà un'eccezione se qualsiasi numero di cluster è 0, quindi si potrebbe desiderare di aggiungere un controllo di errore.
Metodo ComputeCentroid (elencati in Figura 5) determina i valori centroide — i valori della uno tupla che è più vicina ai valori medi tupla per un determinato cluster.
Figura 5 Metodo ComputeCentroid
static double[] ComputeCentroid(double[][] rawData, int[] clustering,
int cluster, double[][] means)
{
int numAttributes = means[0].Length;
double[] centroid = new double[numAttributes];
double minDist = double.MaxValue;
for (int i = 0; i < rawData.Length; ++i) // walk thru each data tuple
{
int c = clustering[i];
if (c != cluster) continue;
double currDist = Distance(rawData[i], means[cluster]);
if (currDist < minDist)
{
minDist = currDist;
for (int j = 0; j < centroid.Length; ++j)
centroid[j] = rawData[i][j];
}
}
return centroid;
}
Metodo ComputeCentroid scorre ogni tupla del set di dati, saltando le tuple che non sono in cluster specificato. Per ogni tupla del cluster specificato, la distanza euclidea tra le tuple e la media di cluster è calcolata utilizzando il metodo di supporto distanza. I valori di tuple che sono più vicini (avendo la distanza più piccola) per i valori medi sono memorizzati e restituiti.
Metodo UpdateCentroids chiama ComputeCentroid per ogni cluster per dare i centroidi per tutti i cluster:
static void UpdateCentroids(double[][] rawData, int[] clustering,
double[][] means, double[][] centroids)
{
for (int k = 0; k < centroids.Length; ++k)
{
double[] centroid = ComputeCentroid(rawData, clustering, k, means);
centroids[k] = centroid;
}
}
UpdateCentroids metodo presuppone che esista una matrice di matrici denominato centroidi. I centroidi matrice è molto simile alla matrice significa: Il primo indice rappresenta un ID del cluster e il secondo indice indica l'attributo dei dati.
Per riassumere, ogni cluster ha un baricentro, che è la tupla più rappresentativa del cluster. Trovando una tupla in ogni cluster che è più vicina alla tupla media (la media) in ogni cluster vengono calcolati valori centroide. Ogni tupla di dati viene assegnato al cluster di cui centroide del cluster è più vicina alla tupla.
La funzione di distanza e la normalizzazione dei dati
Metodo ComputeCentroid chiama un metodo di distanza per determinare quali dati tupla è più vicina a una media di cluster. Come descritto in precedenza, il modo più comune per misurare la distanza da tuple di mezzi è quello di utilizzare la distanza euclidea:
static double Distance(double[] tuple, double[] vector)
{
double sumSquaredDiffs = 0.0;
for (int j = 0; j < tuple.Length; ++j)
sumSquaredDiffs += Math.Pow((tuple[j] - vector[j]), 2);
return Math.Sqrt(sumSquaredDiffs);
}
Si potrebbe voler prendere in considerazione metodi alternativi per definire la distanza. Un'opzione molto comune è quello di utilizzare la somma dei valori assoluti delle differenze tra ogni componente. Perché la distanza euclidea piazze le differenze, le differenze più grandi sono ponderate molto più pesante rispetto a piccole differenze.
Un altro fattore importante relativo alla scelta della funzione di distanza nell'algoritmo k-means clustering è normalizzazione dei dati. Il programma demo utilizza i dati raw, un-normalized. Perché tuple pesi in genere sono valori quali 160.0 e altezze di tuple sono in genere i valori come 67.0, differenze nei pesi hanno molto più influenza di differenze nelle altezze. In molte situazioni, oltre a esplorare clustering sui dati raw, è utile normalizzare i dati grezzi prima di clustering. Ci sono molti modi per normalizzare i dati. È una tecnica comune per calcolare la media (m) e la deviazione standard (sd) per ogni attributo, quindi per ogni calcolo di attributo valore (v) un normalizzato valore nv = (v-m) / sd.
L'assegnazione di ogni tupla in un Cluster
Con un metodo per calcolare il centroide di ciascun cluster in mano, è possibile scrivere un metodo per assegnare ogni tupla in un cluster. Metodo assegnare è elencato Figura 6.
Figura 6 metodo assegna
static bool Assign(double[][] rawData,
nt[] clustering, double[][] centroids)
{
int numClusters = centroids.Length;
bool changed = false;
double[] distances = new double[numClusters];
for (int i = 0; i < rawData.Length; ++i)
{
for (int k = 0; k < numClusters; ++k)
distances[k] = Distance(rawData[i], centroids[k]);
int newCluster = MinIndex(distances);
if (newCluster != clustering[i])
{
changed = true;
clustering[i] = newCluster;
}
}
return changed;
}
Metodo assegnare accetta una matrice di valori centroide e scorre ogni tupla di dati. Per ogni tupla di dati, la distanza di ciascuno dei centroidi cluster è calcolata e memorizzata in una matrice locale denominata distanze, dove l'indice della matrice rappresenta un ID di cluster. Metodo helper MinIndex determina quindi l'indice nelle distanze di matrice che ha il valore più piccolo della distanza, che è l'ID del cluster del cluster che ha baricentro più vicino alla tupla.
Ecco il metodo di supporto MinIndex:
static int MinIndex(double[] distances)
{
int indexOfMin = 0;
double smallDist = distances[0];
for (int k = 0; k < distances.Length; ++k)
{
if (distances[k] < smallDist)
{
smallDist = distances[k]; indexOfMin = k;
}
}
return indexOfMin;
}
Nell'assegnare, se l'ID del cluster calcolato è diverso da esistere cluster ID memorizzati nell'array clustering, array clustering è aggiornato e un flag booleano per indicare che vi è stato almeno un cambio il clustering è attivata o disattivata. Questo flag verrà utilizzato per determinare quando fermare il ciclo principale algoritmo — quando viene superato il numero massimo di iterazioni o quando non non c'è nessun cambiamento del clustering.
Questa implementazione dell'algoritmo k-means presuppone che vi sia sempre almeno una tupla di dati assegnata per ogni cluster. Come dato in Figura 6, metodo assegna non impedisce una situazione dove un cluster non ha Tuple assegnate. In pratica, questo di solito non è un problema. Prevenire la condizione di errore è un po ' complicato. L'approccio che generalmente uso è quello di creare una matrice denominata centroidIndexes che funziona in congiunzione con i centroidi matrice. Ricordo che i centroidi matrice contiene valori centroide, per esempio (61,0, 120,0) è il baricentro per cluster 2 in Figura 2. Matrice centroidIndexes contiene l'indice tupla associato, ad esempio [3]. Quindi nel metodo assegna, il primo passo è da assegnare a ciascun cluster la tupla di dati che contiene i valori del centroide, e solo allora fa il metodo scorrere ogni tupla rimanente e assegnare ciascuno a un cluster. Questo approccio garantisce che ogni cluster ha almeno una tupla.
Il metodo di Cluster
Metodo Cluster, elencati in Figura 7, è la routine di alto livello che chiama tutti i metodi helper e sub-helper per eseguire il clustering di dati di fatto.
Figura 7 il metodo Cluster
static int[] Cluster(double[][] rawData, int numClusters,
int numAttributes, int maxCount)
{
bool changed = true;
int ct = 0;
int numTuples = rawData.Length;
int[] clustering = InitClustering(numTuples, numClusters, 0);
double[][] means = Allocate(numClusters, numAttributes);
double[][] centroids = Allocate(numClusters, numAttributes);
UpdateMeans(rawData, clustering, means);
UpdateCentroids(rawData, clustering, means, centroids);
while (changed == true && ct < maxCount)
{
++ct;
changed = Assign(rawData, clustering, centroids);
UpdateMeans(rawData, clustering, means);
UpdateCentroids(rawData, clustering, means, centroids);
}
return clustering;
}
Il principale mentre loop ripetutamente assegna ogni tupla di dati a un cluster, calcola i nuovi mezzi di tupla per ogni cluster, quindi utilizza i nuovi mezzi per calcolare i nuovi valori di centroide di ciascun cluster. Il ciclo termina quando non non c'è nessun cambiamento nell'assegnazione di cluster o qualche conteggio massimo è raggiunto. Perché i mezzi matrice viene utilizzata solo per calcolare i centroidi, si potrebbe desiderare di refactor Cluster inserendo la chiamata a UpdateMeans all'interno del metodo UpdateCentroids.
Prima inizierà il ciclo di elaborazione, la matrice di clustering è inizializzata dal metodo InitClustering:
static int[] InitClustering(int numTuples,
int numClusters, int randomSeed)
{
Random random = new Random(randomSeed);
int[] clustering = new int[numTuples];
for (int i = 0; i < numClusters; ++i)
clustering[i] = i;
for (int i = numClusters; i < clustering.Length; ++i)
clustering[i] = random.Next(0, numClusters);
return clustering;
}
Il metodo InitClustering prima assegna le tuple 0 attraverso numcluster-1 al cluster 0 attraverso numClusters-1, rispettivamente, così che ogni cluster inizierà con almeno una tupla assegnata. Le tuple rimanenti vengono assegnate a un cluster selezionato casualmente.
Una sorprendente quantità di ricerca è stato fatto su k-means clustering inizializzazione e volete sperimentare alternative all'approccio dato qui. In molti casi, il raggruppamento finale prodotto dall'algoritmo k-means dipende come viene inizializzato il clustering.
Alla ricerca di dati anomali
Un modo per utilizzare il clustering di dati è semplicemente esplorare diversi clusterings e cercare risultati inattesi o sorprendente. Un'altra possibilità è cercare dati insoliti tuple all'interno di un cluster. Il programma demo verifica cluster 0 per trovare la tupla in cluster che è più lontana il centroide del cluster utilizzando un metodo denominato Outlier, che è elencato in Figura 8.
Figura 8 il metodo Outlier
static double[] Outlier(double[][] rawData, int[] clustering,
int numClusters, int cluster)
{
int numAttributes = rawData[0].Length;
double[] outlier = new double[numAttributes];
double maxDist = 0.0;
double[][] means = Allocate(numClusters, numAttributes);
double[][] centroids = Allocate(numClusters, numAttributes);
UpdateMeans(rawData, clustering, means);
UpdateCentroids(rawData, clustering, means, centroids);
for (int i = 0; i < rawData.Length; ++i)
{
int c = clustering[i];
if (c != cluster) continue;
double dist = Distance(rawData[i], centroids[cluster]);
if (dist > maxDist)
{
maxDist = dist;
Array.Copy(rawData[i], outlier, rawData[i].Length);
}
}
return outlier;
}
Dopo l'inizializzazione mezzi e matrici di centroidi, metodo Outlier scorre ogni tupla nel cluster specificato e calcola la distanza euclidea dalla tupla il centroide del cluster, quindi restituisce i valori della tupla che ha la distanza più grande ai valori centroide. Un'alternativa minore per voi di prendere in considerazione è per restituire l'indice della tupla dati più lontana.
Ci sono molti altri modi è possibile esaminare i dati in cluster per anomalie. Ad esempio, è possibile determinare la distanza media tra ogni tupla e relativo centroide del cluster assegnati, o si potrebbe voler esaminare le distanze dei centroidi cluster da altro.
Visualizzare le routine
Per completezza, qui ci sono alcune routine di visualizzazione semplificata. Download del codice ha versioni leggermente più elaborate. Se si utilizzano queste procedure semplificate, dovrete modificare le chiamate del metodo Main. Per visualizzare i dati grezzi, mezzi e i centroidi che è possibile utilizzare:
static void ShowMatrix(double[][] matrix)
{
for (int i = 0; i < numRows; ++i)
{
Console.Write("[" + i.ToString().PadLeft(2) + "] ");
for (int j = 0; j < matrix[i].Length; ++j)
Console.Write(matrix[i][j].ToString("F1") + " ");
Console.WriteLine("");
}
}
Per visualizzare la matrice di cluster che è possibile utilizzare:
static void ShowVector(int[] vector)
{
for (int i = 0; i < vector.Length; ++i)
Console.Write(vector[i] + " ");
Console.WriteLine("");
}
Per visualizzare i valori di un outlier che è possibile utilizzare:
static void ShowVector(double[] vector)
{
for (int i = 0; i < vector.Length; ++i)
Console.Write(vector[i].ToString("F1") + " ");
Console.WriteLine("");
}
E per visualizzare i dati raw raggruppati per cluster che è possibile utilizzare:
static void ShowClustering(double[][] rawData,
int numClusters, int[] clustering)
{
for (int k = 0; k < numClusters; ++k) // Each cluster
{
for (int i = 0; i < rawData.Length; ++i) // Each tuple
if (clustering[i] == k)
{
for (int j = 0; j < rawData[i].Length; ++j)
Console.Write(rawData[i][j].ToString("F1") + " ");
Console.WriteLine("");
}
Console.WriteLine("");
}
}
Conclusioni
Clustering di dati sono strettamente imparentati e talvolta confusa con la classificazione dei dati. Clustering è una tecnica non supervisionata che raggruppa gli elementi di dati insieme senza alcuna preconoscenza di che cosa potrebbero essere quei gruppi. Il clustering è tipicamente un processo esplorativo. Classificazione, al contrario, è una supervisione tecnica che richiede la specifica di noti gruppi di dati di training, dopo che ogni tupla di dati viene inserito in uno di questi gruppi. Classificazione viene in genere utilizzato per scopi di previsione.
Il codice e spiegazione presentato in questo articolo dovrebbe darvi informazioni sufficienti per sperimentare con dati k-means clustering, o creare un autonomo completamente personalizzabile clustering strumento o per aggiungere funzionalità di clustering per un'applicazione .NET senza basarsi su eventuali dipendenze esterne. Ci sono molti altri algoritmi di clustering oltre k-means e ti presento alcune di queste in futuro gli articoli di MSDN Magazine, compresi dati entropia minimizzazione, utilità di categoria e Naive Bayes inferenza.
Dr.James McCaffrey funziona per Volt Information Sciences Inc., dove gestisce la formazione tecnica per gli ingegneri software della Microsoft di Redmond, Washington, campus. Si è occupato di diversi prodotti Microsoft, inclusi Internet Explorer e MSN Search. Egli è l'autore di ".NET Test Automation Recipes" (Apress, 2006) e può essere raggiunto a jammc@microsoft.com.
Grazie all'esperto tecnica seguente per la revisione di questo articolo: Darren Gehring