Clústeres de datos
Detección de datos anormales con la agrupación en clústeres k-means
Considere el problema de identificar elementos de datos anormales en un gran conjunto de datos, por ejemplo, al identificar posibles transacciones fraudulentas de tarjetas de crédito, solicitudes de préstamo riesgosas, etcétera. Un enfoque para detectar datos anormales es agrupar los elementos de datos en clústeres similares y luego buscar elementos de datos dentro de cada clúster que sean diferentes en alguna medida a los otros elementos dentro del mismo clúster.
Existen muchos algoritmos de clústeres diferentes. Uno de los más antiguos y usados a nivel mundial es el algoritmo k-means. En este artículo, explicaré cómo funciona el algoritmo k-means y presentaré un completo programa de demostración de C#. Existen muchas herramientas independientes de clústeres de datos, así que ¿para qué crear un código de agrupaciones k-means desde cero? Puede ser difícil o tal vez no se puedan integrar las herramientas actuales de clústeres a un sistema de software, es posible que no se puedan personalizar para que se enfrenten a escenarios poco comunes y que estén protegidas por copyright o que presenten otro tipo de problemas relacionados con la propiedad intelectual. Después de leer este artículo, podrá experimentar con agrupaciones k-means y tendrá el conocimiento básico para agregar la funcionalidad de clústeres a una aplicación .NET.
La mejor manera de entender lo que significan las agrupaciones en clústeres k-means y de comprender lo que pretendo con este artículo es ver la Figura 1. El programa de demostración comienza con la creación de un conjunto ficticio de 20 elementos de datos. En la terminología de clústeres, a veces se les llama tuplas a los elementos de datos. Aquí, cada tupla representa a una persona, tiene dos valores de atributo numéricos, y presenta el alto en pulgadas y el peso en libras. Una de las limitaciones del algoritmo k-means es que solo se aplica en los casos en que las tuplas de datos son completamente numéricas.
.png)
Figura 1 Agrupación en clústeres mediante k-means
Se cargan los datos ficticios en una matriz de la memoria. Luego, se establece el número de clústeres en tres. Aunque hay técnicas avanzadas para la agrupación en clústeres que pueden sugerir el número óptimo de clústeres a usar, la agrupación de datos en clústeres es, por lo general, un proceso exploratorio y se puede encontrar el mejor número de clústeres a usar mediante ensayo y error. Como verá dentro de poco, la agrupación en clústeres k-means es un proceso iterativo. El programa de demostración tiene una variable maxCount, que se usa para limitar el número de veces que se podrá ejecutar el bucle principal de clústeres. En este caso, ese valor se establece arbitrariamente en 30.
A continuación, el programa de demostración usa el algoritmo k-means en segundo plano para colocar cada tupla de datos en uno de los tres clústeres. Hay varias formas de codificar una agrupación en clústeres. En este caso, se define una agrupación en clústeres como una matriz de int, en la que el índice matriz representa a una tupla y el valor matriz asociado representa el identificador de clústeres de base 0. Así que, en la Figura 1, la tupla 0 (65.0, 220.0) se asigna al clúster 0, la tupla 1 (73.0, 160.0) se asigna al clúster 1, la tupla 2 (59.0, 110.0) se asigna al clúster 2, la tupla 3 (61.0, 120.0) se asigna al clúster 2 y así sucesivamente. Observe que hay ocho tuplas asignadas al clúster 0, cinco tuplas asignadas al clúster 1 y siete tuplas asignadas al clúster 2.
Luego, el programa de demostración muestra los datos, agrupados según clústeres. Si examina los datos clusterizados podrá ver que el clúster 0 se podría llamar clúster de personas de mucho peso, el clúster 1 se podría llamar clúster de personas altas y el clúster 2 se podría llamar clúster de personas bajas. El programa de demostración finaliza con el análisis de las tuplas asignadas al clúster 0 y determina que según cierto criterio, la tupla 5 (67.0, 240.0) es la tupla más anormal.
En las siguientes secciones recorreremos el código que produjo la captura de pantalla de la Figura 1, para que pueda modificar este código con el fin de que satisfaga sus necesidades. Este artículo da por sentado que usted tiene (al menos) habilidades de programación de nivel intermedio con lenguaje de familia C, pero no supone que sabe algo de la agrupación de datos en clústeres. Codifiqué el programa de demostración con C#, pero usé un estilo diferente a OOP, así que no debería resultarle difícil la refactorización de esta demostración a otro lenguaje, si así lo desea. En este artículo presento todo el código fuente para el programa de demostración. El código fuente también está disponible en archive.msdn.microsoft.com/mag201302kmeans.
El algoritmo k-means
En principio, al menos, el algoritmo k-means es bastante simple. Pero como podrá ver, algunos de los detalles de implementación pueden ser algo complicados. El concepto central del algoritmo k-means es el centroide. En la agrupación de datos en clústeres, el centroide de un conjunto de tuplas de datos es la tupla más representativa del grupo. Se explica mejor esta idea a través de un ejemplo. Supongamos que tiene tres tuplas de estatura y peso similares a las señaladas en la Figura 1:
[a] (61.0, 100.0)
[b] (64.0, 150.0)
[c] (70.0, 140.0)
¿Qué tupla es la más representativa? Un enfoque es calcular una tupla promedio matemática (medios) y luego seleccionar como centroide la tupla que se acerque más a esa tupla promedio. Así que, en este caso, la tupla promedio es:
[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)
Y ahora, ¿cuál de las siguientes tres tuplas está más cerca de (65.0, 130.0)? Hay varias formas para definir la más cercana. El enfoque más común, y que usamos en este programa de demostración, es usar la distancia euclidiana. En palabras, la distancia euclidiana entre dos tuplas es la raíz cuadrada de la suma de las diferencias cuadradas entre cada componente de las tuplas. Una vez más, la mejor manera de explicarlo es con un ejemplo. La distancia euclidiana entre la tupla (61.0, 100.0) y la tupla promedio (65.0, 130.0) es:
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
De forma similar:
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
Debido a que la menor de las tres distancias es la distancia entre el promedio matemático y la tupla [c], el centroide de las tres tuplas es la tupla [c]. Tal vez le gustaría experimentar con este programa de demostración al usar otras definiciones de la distancia entre dos tuplas, para ver cómo afecta eso a la agrupación en clústeres final que se produce.
Con la noción de centroide de clúster ya establecida, el algoritmo k-means es relativamente sencillo. En seudocódigo:
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
Si busca en la Web, puede encontrar varias animaciones en línea del algoritmo k-means en acción. La imagen en la Figura 2 muestra la agrupación en clústeres que produjo el programa de demostración. El elemento de datos encerrado en un círculo en cada clúster es el centroide de clúster.
.png)
Figura 2 Datos clusterizados y centroides
Estructura general del programa
La estructura general del programa para la demostración en la Figura 1, con algunos cambios menores, se incluye en la lista de la Figura 3. Usé Visual Studio 2010 para crear una nueva consola de aplicación de C# llamada ClusteringKMeans; también debería funcionar cualquier versión reciente de Visual Studio. En la ventana del Explorador de soluciones, cambié el nombre del archivo Program.cs a ClusteringKMeansProgram.cs, lo que automáticamente cambió el nombre de la clase generada por la plantilla. Eliminé lo innecesario con el uso de instrucciones en la parte superior del archivo.
Figura 3 Estructura general de programa
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
}
}
Para hacerlo más sencillo, usé un enfoque de métodos estáticos y eliminé la comprobación de errores. La primera parte del código de demostración establece los datos de estatura y de peso que se agruparán. Debido a que solo hay 20 tuplas, codifiqué los datos y los almacené en la memoria, en una matriz llamada rawData. Por lo general, sus datos se almacenarán en un archivo de texto o en una tabla SQL. En tal caso, tendrá que escribir una función auxiliar para cargar los datos en la memoria. Si su origen de datos es demasiado grande para la memoria de la máquina, tendrá que modificar el código de demostración para iterar mediante un origen de datos externo en vez de mediante una matriz de datos.
Luego de establecer los datos sin procesar, el programa de demostración llama a la función auxiliar ShowMatrix para que muestre los datos. A continuación, a las variables numAttributes, numClusters y maxCount se le asignan valores de 2 (estatura y peso), 3 y 30 respectivamente. Recuerde que maxCount limita el número de iteraciones en el bucle de procesamiento del algoritmo principal. El algoritmo k-means tiende a converger rápidamente, pero tal vez tenga que experimentar un poco con el valor de maxCount.
El método Cluster se encarga de toda la agrupación en clústeres. El método devuelve una matriz de int que define cómo se asigna cada tupla a un clúster. Al finalizar, el programa de demostración muestra la agrupación en clústeres codificada, junto a los datos sin procesar, agrupados según clúster.
El programa de demostración finaliza al analizar los datos clusterizados para ver si hay tuplas con valores atípicos, tal vez anormales, mediante el método Outlier (valor atípico). Ese método acepta un identificador de clúster y devuelve los valores de la tupla de datos más alejada (calculada según la distancia euclidiana) del centroide del clúster (la tupla más representativa). En este caso, para el clúster 0, el clúster de las personas de mucho peso, la tupla de valor atípico es (67.0, 240.0), la persona con más peso.
Calcular centroides de clúster
Recuerde que un centroide de clúster es la tupla más representativa de las tuplas que se asignaron al clúster y que una forma de determinar un centroide de clúster es calcular una tupla promedio, luego hay que encontrar la tupla que se encuentre más cerca de la tupla promedio. El método auxiliar UpdateMeans calcula la tupla promedio para cada clúster y se muestra en la Figura 4.
Figura 4 Método 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;
}
El método UpdateMeans da por sentado que ya existe una matriz de matrices llamada medios, en lugar de crear una matriz y luego devolverla. Como se supone que la matriz de medios existe, tal vez le gustaría convertirla en un parámetro de referencia. Se crea la matriz de medios con el método auxiliar 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;
}
El primer índice de la matriz de medios representa a un identificador de clúster y el segundo indica el atributo. Por ejemplo, si means[0][1] = 150.33 entonces, el promedio de los valores de peso (1) de las tuplas en el clúster 0 es 150.33.
Primero, el método UpdateMeans reduce a cero los valores existentes de la matriz de medios, luego itera a través de cada tupla de datos y lleva la cuenta de las tuplas en cada clúster, también acumula las sumas de cada atributo y divide cada suma acumulada según la cuenta adecuada de clústeres. Tenga en cuenta que el método generará una excepción si hay una cuenta de clúster en 0, por lo que tal vez sea bueno que añada una comprobación de errores.
El método ComputeCentroid (que aparece en la Figura 5) determina los valores del centroide, el valor de la tupla que se encuentra más cerca de los valores de la tupla promedio de un clúster determinado.
Figura 5 Método 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;
}
El método ComputeCentroid itera a través de cada tupla en el conjunto de datos, omitiendo las tuplas que no estén en el clúster especificado. Para cada tupla del clúster especificado, la distancia euclidiana entre la tupla y el clúster de medios se calcula mediante el método auxiliar Distance. Los valores de la tupla más cercanos (con la menor distancia) a los valores de medios se almacenan y se devuelven.
El método UpdateCentroids llama a ComputeCentroid para que cada clúster proporcione centroides para todos los clústeres:
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;
}
}
El método UpdateCentroids supone que existe una matriz de matrices llamada centroides. La matriz de centroides es muy similar a la matriz de medios: el primer índice representa a un identificador de clúster y el segundo indica el atributo de datos.
En resumen, cada clúster tiene un centroide, que es la tupla más representativa en él. Los valores del centroide se calculan al encontrar la tupla de cada clúster más cercana a la tupla promedio (los medios) de cada clúster. Se asigna cada tupla de datos al clúster cuyo centroide sea el más cercano a la tupla.
Función Distance y normalización de datos
El método ComputeCentroid llama al método Distance para determinar la tupla de datos más cercana a un medio de clúster. Tal como se comentó anteriormente, la forma más común de medir la distancia entre las tuplas y los medios es usar la distancia euclidiana:
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);
}
Tal vez le gustaría considerar formas alternativas para definir la distancia. Una opción común es usar la suma de los valores absolutos de las diferencias entre cada componente. Ya que la distancia euclidiana cuadra las diferencias, las grandes diferencias se ponderan mucho más que las diferencias más pequeñas.
Otro factor importante relacionado con la elección de la función de distancia en el algoritmo de agrupación en clústeres k-means es la normalización de los datos. El programa de demostración usa datos sin procesar y no normalizados. Debido a que los pesos de las tuplas son por lo general valores como 160.0 y sus estaturas valores como 67.0, las diferencias en peso influyen mucho más que las diferencias en estatura. En varias situaciones, además de explorar la agrupación en clústeres en datos sin procesar, es bastante útil normalizar dichos datos antes de la agrupación en clústeres. Hay varias formas de normalizar los datos. Una técnica común es calcular el medio (m) y la desviación estándar (sd) de cada atributo, luego por cada valor de atributo (v) se calcula un valor normalizado nv = (v-m)/sd.
Asignar cada tupla a un clúster
Con un método para calcular el centroide de cada clúster, es posible escribir un método para asignar cada tupla a un clúster. El método Assign aparece en la Figura 6.
Figura 6 Método Assign
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;
}
El método Assign acepta una matriz de valores de centroides e itera a través de cada tupla de datos. Por cada tupla de datos, se calcula la distancia de cada centroide de clúster y se almacenan en una matriz local llamada distancias, donde el índice de la matriz representa al identificador de un clúster. Luego, el método auxiliar MinIndex determina el índice en las distancias de matriz que tengan el menor valor de distancia, lo que sería el identificador de clúster del clúster que tenga la tupla más cercana al centroide.
Este es el método auxiliar 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;
}
En Assign, si el identificador de clúster calculado es diferente al que está almacenado en los clústeres de matriz, estos se actualizarán y se generará un marcador booleano para indicar que ha activado al menos un cambio en la agrupación en clústeres. Este marcador se usará para determinar cuando detener el bucle del algoritmo principal; cuando se excede el número máximo de iteraciones o cuando no hay modificaciones en la agrupación en clústeres.
Esta implementación del algoritmo k-means supone que siempre hay al menos una tupla de datos asignada a cada clúster. Como se ve en la Figura 6, el método Assign no previene una situación en la que un clúster no tenga tuplas asignadas. En la práctica, esto no suele ser un problema. Prevenir la condición de error puede resultar algo complicado. El enfoque que generalmente uso es crear una matriz llamada centroidIndexes, que funciona en conjunto con la matriz de centroides. Recuerde que la matriz de centroides contiene los valores de los centroides, por ejemplo (61.0, 120.0) es el centroide para el clúster 2 en la Figura 2. La matriz centroidIndexes contiene el índice de tupla asignado, por ejemplo [3]. Entonces, en el método Assign, el primer paso es asignar a cada clúster la tupla de datos que contenga los valores de centroide, solo entonces el método podrá iterar a través de cada tupla restante y podrá asignar cada una a un clúster. Este enfoque garantiza que cada clúster tenga al menos una tupla.
El método Cluster
El método Cluster, que aparece en la Figura 7, es la rutina de alto nivel que llama a todos los métodos auxiliares o subauxiliares para que realicen la agrupación de datos en clústeres.
Figura 7 Método 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;
}
El bucle while principal asigna repetidamente cada tupla de datos a un clúster, calcula los nuevos medios de tupla para cada clúster y luego usa estos nuevos medios para calcular los nuevos valores de centroides para cada clúster. El bucle está presente cuando no hay cambios en la asignación de clústeres o cuando se alcanza algún recuento máximo. Ya que la matriz de medios se usa solo para calcular centroides, es posible que quiera refactorizar el método Cluster al fijar la llamada a UpdateMeans dentro del método UpdateCentroids.
Antes de poner en marcha el proceso del bucle, el método InitClustering inicia la matriz de clústeres:
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;
}
El método InitClustering asigna primero tuplas 0 a través de numClusters-1 a los clústeres 0 mediante numClusters-1 respectivamente, para que cada clúster comience con al menos una tupla asignada. Las tuplas restantes se asignan a un clúster seleccionado al azar.
Se ha realizado una sorprendente cantidad de investigación sobre la inicialización de la agrupación en clústeres k-means, tal vez le gustaría experimentar con alternativas del enfoque que presentamos aquí. En varios casos, la agrupación final en clústeres que produce el algoritmo k-means depende de cómo se inicia dicha agrupación.
Buscar datos anormales
Una forma de usar la agrupación de datos en clústeres es simplemente explorar las diferentes agrupaciones en clústeres y buscar resultados inesperados o sorpresivos. Otra posibilidad es buscar tuplas de datos inusuales dentro de un clúster. El programa de demostración revisa el clúster 0 para encontrar la tupla más alejada del centroide del clúster, para ello se usa un método llamado Outlier, que aparece en la Figura 8.
Figura 8 El método 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;
}
Después de iniciar las matrices de medios y de centroides, el método Outlier itera a través de cada tupla en el clúster especificado, luego calcula la distancia euclidiana desde la tupla al centroide del clúster y devuelve los valores de la tupla que presenten la mayor distancia respecto de los valores del centroide. Otra alternativa que podría considerar es devolver el índice de la tupla de datos más alejada.
Existen muchas otras formas para examinar los datos clusterizados en busca de anormalidades. Por ejemplo, tal vez quiera determinar la distancia promedio entre cada tupla y su centroide de clúster asignado o podría examinar las distancias que hay entre los centroides del clúster.
Rutinas de visualización
Para tener la información completa, aquí se muestran algunas rutinas de visualización simplificadas. La descarga de código tiene versiones un poco más elegantes. Si usa estas rutinas simplificadas, tendrá que modificar sus llamados en el método Main. Puede usar lo siguiente para visualizar los datos sin procesar, medios y centroides:
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("");
}
}
Para visualizar la matriz de clústeres que puede usar:
static void ShowVector(int[] vector)
{
for (int i = 0; i < vector.Length; ++i)
Console.Write(vector[i] + " ");
Console.WriteLine("");
}
Para visualizar los valores atípicos que puede usar:
static void ShowVector(double[] vector)
{
for (int i = 0; i < vector.Length; ++i)
Console.Write(vector[i].ToString("F1") + " ");
Console.WriteLine("");
}
Y para visualizar los datos sin procesar agrupados según clúster, puede usar:
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("");
}
}
Conclusión
La agrupación de datos en clústeres está estrechamente relacionada con (y a veces se le confunde con) la clasificación de datos. La agrupación en clústeres es una técnica sin supervisión que agrupa elementos de datos sin de antemano qué podrían ser dichos grupos. La agrupación en clústeres es, por lo general, un proceso exploratorio. La clasificación, por otra parte, es una técnica supervisada que necesita la especificación de grupos conocidos de datos de entrenamiento, tras lo cual cada tupla de datos se ubica en uno de estos grupos. Por lo general, la clasificación se usa para obtener predicciones.
El código y la explicación que se muestran en este artículo deberían entregarle la información necesaria para experimentar con la agrupación de datos en clústeres k-means o para crear una herramienta de agrupación en clústeres independiente y personalizable, también para agregar características de agrupación en clústeres a una aplicación .NET sin tener que depender de dependencias externas. Hay muchos otros algoritmos de agrupación en clústeres además del k-means y presentaré algunos de ellos en futuros artículos de MSDN Magazine, inclusive la minimización de entropía de datos, la utilidad de la categoría y la inferencia de Naive Bayes.
El Dr. James McCaffrey trabaja en Volt Information Sciences Inc., donde está a cargo del entrenamiento técnico de los ingenieros informáticos que trabajan en el campus de Microsoft en Redmond, Washington. Ha colaborado en el desarrollo de varios productos de Microsoft como, por ejemplo, Internet Explorer y MSN Search. Es el autor de “.NET Test Automation Recipes” (Apress, 2006) y se puede ubicar en la dirección de correo electrónico jammc@microsoft.com.
Gracias a los siguientes expertos técnicos por su ayuda en la revisión de este artículo: Darren Gehring