Clustering de dados
Detectando dados anormais usando o clustering de k-Means
Considere o problema de identificação de itens de dados anormais de um conjunto de dados muito grande, por exemplo, identificando transações de cartão de crédito potencialmente fraudulentas, aplicativos de empréstimos de risco e assim por diante. Uma abordagem para detectar dados anormais é agrupar os itens de dados em clusters semelhantes e procurar itens de dados dentro de cada cluster que sejam diferentes de alguma forma de outros itens de dados dentro do cluster.
Há muitos algoritmos de clustering diferentes. Um dos mais antigos e mais amplamente usados é o algoritmo k-means. Neste artigo explicarei como o algoritmo k-means funciona e apresentarei um programa completo de demonstração do C#. Existem muitas ferramentas de clustering de dados autônomas, portanto, por que você precisa criar código de clustering de k-means a partir do zero? As ferramentas de clustering existentes podem ser difíceis ou impossíveis de serem integradas em um sistema de software, elas podem não ser personalizáveis para lidar com cenários incomuns ou outros problemas de propriedade intelectual. Depois de ler este artigo, você estará apto a fazer experiências com o clustering de k-means e terá a base de conhecimento para adicionar funcionalidade de clustering a um aplicativo .NET.
A melhor maneira de ter uma noção do que é o clustering de k-means e de ver onde quero chegar neste artigo é examinar a Figura 1. O programa de demonstração começa criando um conjunto fictício de 20 itens de dados. Na terminologia de clustering, itens de dados algumas vezes são chamados de tuplas. Cada tupla aqui representa uma pessoa e tem dois valores de atributos numéricos, uma altura em polegadas e um peso em libras. Uma das limitações do algoritmo k-means é que ele se aplica apenas a casos onde as tuplas de dados são completamente numéricas.
.png)
Figura 1 Clustering usando k-Means
Os dados fictícios são carregados em uma matriz na memória. Em seguida, o número de cluster é definido como três. Embora existam técnicas de clustering avançadas, que podem sugerir o número ideal de clusters a serem usados, em clustering geral de dados esse é um processo exploratório e o melhor número de clusters a ser usado normalmente é localizado por tentativa e erro. Como você verá brevemente, o clustering de k-means é um processo iterativo. O programa de demonstração tem uma variável maxCount, que é usada para limitar o número de vezes que o loop principal de clustering será executado. Aqui esse valor está definido arbitrariamente como 30.
Em seguida, nos bastidores, o programa de demonstração usa o algoritmo k-means para posicionar cada tupla de dados em um dos três clusters. Há várias maneiras de codificar um clustering. Neste caso, um clustering é definido por uma matriz de inteiros onde o índice da matriz representa uma tupla, e o valor da matriz associada representa a ID do cluster com base em zero. Portanto, na Figura 1, a tupla 0 (65.0, 220.0) é atribuída ao cluster 0, a tupla 1 (73.0, 160.0) é atribuída ao cluster 1, a tupla 2 (59.0, 110.0) é atribuída ao cluster 2, a tupla 3 (61.0, 120.0) é atribuída ao cluster 2 e assim por diante. Observe que há oito tuplas atribuídas ao cluster 0, cinco tuplas atribuídas ao cluster 1, e sete tuplas atribuídas ao cluster 2.
Em seguida, o programa de demonstração exibe os dados agrupados por cluster. Se você examinar os dados clusterizados, verá que o cluster 0 pode ser chamado de cluster de pessoas pesadas, o cluster 1 pode ser chamado de cluster de pessoas altas, e o cluster 2 pode ser chamado de cluster de pessoas baixas. O programa de demonstração conclui analisando as tuplas atribuídas ao cluster 0 e determina que, por algum critério, a tupla 5 (67.0, 240.0) é a tupla mais anormal.
Nas seções a seguir, descreverei o código que produziu a captura de tela da Figura 1, de forma que você poderá modificar esse código para atender às suas próprias necessidades. Este artigo pressupõe que você tenha no mínimo habilidades de nível intermediário em programação com uma linguagem da família C, mas não pressupõe que conheça qualquer coisa sobre clustering de dados. Codifiquei o programa de demonstração usando C#, mas usei um estilo não OOP para que você não tenha muita dificuldade para refatorar a demonstração para outro idioma se desejar. Apresento todo o código-fonte do programa de demonstração neste artigo. O código-fonte também está disponível em archive.msdn.microsoft.com/mag201302kmeans.
O algoritmo k-Means
Em princípio, pelo menos, o algoritmo k-means é bastante simples. Mas como você verá, alguns detalhes da implementação são um pouco complicados. O conceito central do algoritmo k-means é o centroide. No clustering de dados, o centroide de um conjunto de tuplas de dados é a tupla que mais representa o grupo. A ideia é melhor explicada por um exemplo. Suponha que você tenha três tuplas de peso-altura semelhantes às mostradas na Figura 1:
[a] (61.0, 100.0) [b] (64.0, 150.0) [c] (70.0, 140.0)
Qual tupla é mais representativa? Uma abordagem é computar uma tupla de média aritmética (mean) e, em seguida, selecionar como a centroide a tupla que mais se aproxima dessa tupla média. Portanto, neste caso, a tupla média é:
[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 agora, qual das três tuplas mais se aproxima de (65.0, 130.0)? Há várias maneiras de definir a que mais se aproxima. A abordagem mais comum, que é usada no programa de demonstração, é usar a distância euclidiana. Enunciando, a distância euclidiana entre duas tuplas é a raiz quadrada da soma das diferenças ao quadrado entre cada componente das tuplas. Mais uma vez, a melhor maneira de explicar isso é com um exemplo. A distância euclidiana entre a tupla (61.0, 100.0) e a tupla média (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
De maneira semelhante:
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
Como a menor das três distâncias é a distância entre a média aritmética e a tupla [c], o centroide das três tuplas é a tupla [c]. Você pode fazer uma experiência com o programa de demonstração usando diferentes definições da distância entre duas tuplas para ver como elas afetam o clustering final produzido.
Estabelecido o conceito de centroide de cluster, o algoritmo k-means é relativamente simples. Em pseudocó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
Se você pesquisar na Web, localizará várias boas animações online do algoritmo k-means em ação. A imagem da Figura 2 mostra o clustering produzido pelo programa de demonstração. O item de dados dentro de um círculo em cada cluster é o centroide do cluster.
.png)
Figura 2 Dados clusterizados e centroides
Estrutura geral do programa
A estrutura geral do programa de demonstração mostrado na Figura 1, com algumas pequenas edições, é listada na Figura 3. Usei o Visual Studio 2010 para criar um novo aplicativo de console em C# chamado ClusteringKMeans. Qualquer versão recente do Visual Studio também deverá funcionar. Na janela do Gerenciador de Soluções, renomeei o arquivo Program.cs para ClusteringKMeansProgram.cs, que automaticamente renomeou a classe gerada pelo modelo. Removi as não necessárias usando instruções no início do arquivo.
Figura 3 Estrutura geral do 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 simplificar, usei uma abordagem de método estático e removi todas as verificações de erros. A primeira parte do código de demonstração configura os dados de altura e de peso a serem clusterizados. Como existem apenas 20 tuplas, inseri os dados no código e os armazenei na memória em uma matriz chamada rawData. Normalmente, seus dados serão armazenados em um arquivo de texto ou em uma tabela SQL. Nesses casos, você precisará escrever uma função auxiliar para carregar os dados na memória. Se sua fonte de dados for muito grande para a memória da máquina, você precisará modificar o código de demonstração para iterar por uma fonte de dados externa em vez de uma matriz de dados.
Depois de configurar os dados brutos, o programa de demonstração chama a função auxiliar ShowMatrix para exibir os dados. Em seguida, os valores 2 (altura e peso), 3 e 30 são atribuídos às variáveis numAttributes, numClusters e maxCount respectivamente. Chamar maxCount novamente limita o número de iterações no loop de processamento do algoritmo principal. O algoritmo k-means tende a convergir rapidamente, mas você pode precisar experimentar um pouco com o valor de maxCount.
Todo o trabalho de clustering é executado pelo método Cluster. O método retorna uma matriz de inteiros que define como cada tupla é atribuída a um cluster. Depois de concluído, o programa de demonstração exibe o clustering codificado e também os dados brutos, agrupados de acordo com o cluster.
O programa de demonstração conclui analisando os dados clusterizados das tuplas de exceção, possivelmente anormais, usando o método Outliers. Esse método aceita uma ID de cluster e retorna os valores da tupla de dados que estão mais distantes (conforme medido pela distância euclidiana) do centroide do cluster (tupla mais representativa). Neste caso, para o cluster 0, o cluster de pessoas mais pesadas, a tupla de exceção é (67.0, 240.0), a pessoa mais pesada.
Computados centroides de cluster
Lembre-se de que um centroide de cluster é uma tupla que é a mais representativa das tuplas atribuídas a um cluster, e que uma maneira de determinar um centroide de cluster é computar uma tupla de média aritmética e, em seguida, localizar a tupla mais próxima da tupla média. O método auxiliar UpdateMeans computa a tupla de média aritmética de cada cluster e é listado na Figura 4.
Figura 4 O 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; }
O método UpdateMeans pressupõe que uma matriz de matrizes chamada means já existe, em vez de criar a matriz e, em seguida, retorná-la. Como é pressuposto que a matriz means existe, você pode desejar torná-la um parâmetro de referência. A matriz means é criada usando o 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; }
O primeiro índice da matriz means representa a ID de um cluster e o segundo índice indica o atributo. Por exemplo, se means[0][1] = 150.33 então a média dos valores de peso (1) das tuplas do cluster 0 será 150.33.
O método UpdateMeans primeiro zera os valores existentes na matriz means, em seguida, itera em cada tupla de dados e calcula a contagem de tuplas em cada cluster e acumula as somas para cada atributo e, em seguida, divide cada soma acumulada pela contagem de clusters apropriada. Observe que o método gerará uma exceção se a contagem de qualquer cluster for igual a zero, portanto, você talvez queira adicionar uma verificação de erro.
O método ComputeCentroid (listado na Figura 5) determina os valores dos centroides — os valores da tupla que mais se aproxima dos valores da tupla média para um determinado cluster.
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; }
O método ComputeCentroid itera em cada tupla do conjunto de dados, ignorando as tuplas que não estão no cluster especificado. Para cada tupla do cluster especificado, a distância euclidiana entre a tupla e a média do cluster é calculada usando o método auxiliar Distance. Os valores das tuplas mais próximas (que têm a menor distância) dos valores médios são armazenados e retornados.
O método UpdateCentroids chama o ComputeCentroid para cada cluster para dar os centroides para todos os clusters:
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; } }
O método UpdateCentroids pressupõe que existe uma matriz de matrizes chamada centroids. A matriz centroids é muito semelhante à matriz means: O primeiro índice representa a ID de um cluster e o segundo índice indica o atributo de dados.
Para resumir, cada cluster tem um centroide, que é a tupla mais representativa do cluster. Os valores dos centroides são computados com a localização de uma tupla em cada cluster que mais se aproxima da tupla média (a média) de cada cluster. Cada tupla de dados é atribuída ao cluster cujo centroide de cluster está mais próximo da tupla.
A função Distance e a normalização de dados
O método ComputeCentroid chama um método Distance para determinar qual tupla de dados está mais próxima de uma média de cluster. Conforme descrito anteriormente, a maneira mais comum de medir a distância das tuplas até as médias é usar a distância 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); }
Talvez você queira considerar maneiras alternativas de definir a distância. Uma opção muito comum é usar a soma dos valores absolutos das diferenças entre cada componente. Como a distância euclidiana eleva as diferenças ao quadrado, diferenças grandes são ponderadas de maneira muito mais pesada do que diferenças pequenas.
Outro fator importante relacionado à opção da função distance no algoritmo de clustering k-means é a normalização de dados. O programa de demonstração usa dados brutos, não normalizados. Como os pesos das tuplas são normalmente valores como 160.0, e as alturas das tuplas são normalmente valores como 67.0, as diferenças em pesos têm muito mais influência do que as diferenças em alturas. Em muitas situações, além de explorar o clustering em dados brutos, é útil normalizar os dados brutos antes do clustering. Há muitas maneiras de normalizar dados. Uma técnica comum é computar a média (m) e o desvio padrão (dp) de cada atributo e, em seguida, para cada valor de atributo (v), computar um valor normalizado vn = (v-m)/dp.
Atribuindo cada tupla a um cluster
Com um método para computar o centroide de cada cluster em mãos, é possível escrever um método para atribuir cada tupla a um cluster. O método Assign está listado na Figura 6.
Figura 6 O 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; }
O método Assign aceita uma matriz de valores de centroides e itera em cada tupla de dados. Para cada tupla de dados, a distância até cada um dos centroides de cluster é computada e armazenada em uma matriz local chamada distances, onde o índice da matriz representa a ID de um cluster. Em seguida, o método auxiliar MinIndex determina o índice da matriz distances que tem o menor valor de distância, que é a ID do cluster que tem o centroide mais próximo da tupla.
Este é o 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; }
No Assign, se a ID computada do cluster for diferente da ID do cluster existente armazenada no clustering de matriz, o clustering de matriz será atualizado e um sinalizador booliano para indicar que houve pelo menos uma alteração no clustering será ativado/desativado. Esse sinalizador será usado para determinar quando parar o loop do algoritmo principal — quando o número máximo de iterações for excedido ou quando não houver alteração no clustering.
Essa implementação do algoritmo k-means pressupõe que sempre há pelo menos uma tupla de dados atribuída a cada cluster. Conforme mostrado na Figura 6, o método Assign não impede uma situação onde o cluster não tem tuplas atribuídas. Na prática, isso normalmente não é um problema. Impedir a condição de erro é um pouco complicado. A abordagem que eu geralmente uso é criar uma matriz chamada centroidIndexes que funciona em conjunto com a matriz centroids. Lembre-se de que a matriz centroids contém valores de centroides, por exemplo (61.0, 120.0) é o centroide do cluster 2 na Figura 2. A matriz centroidIndexes tem o índice de tupla associado, por exemplo [3]. Em seguida, no método Assign, a primeira etapa é atribuir a cada cluster a tupla de dados que tem os valores de centroides e apenas depois é que o método itera em cada tupla restante e atribui cada uma a um cluster. Essa abordagem garante que cada cluster tenha pelo menos uma tupla.
O método Cluster
O método Cluster, listado na Figura 7, é a rotina de alto nível que chama todos os métodos auxiliares e subauxiliares para realmente executar o clustering de dados.
Figura 7 O 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; }
O loop while principal atribui repetitivamente cada tupla de dados a um cluster, computa a nova tupla média de cada cluster e usa a nova média para computar os novos valores de centroide para cada cluster. O loop termina quando não há nenhuma alteração na atribuição de cluster ou quando a contagem máxima é atingida. Como a matriz means é usada apenas para computar centroides, talvez você queira refatorar o Cluster colocando a chamada para UpdateMeans dentro do método UpdateCentroids.
Antes de cancelar o loop em processamento, a matriz do clustering é inicializada pelo método 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; }
O método InitClustering primeiro atribui tuplas 0 por meio de numClusters-1 aos clusters 0 por meio de numClusters-1, respectivamente, de forma que cada cluster começará com pelo menos uma tupla atribuída. As tuplas restantes são atribuídas a um cluster selecionado aleatoriamente.
Uma quantidade um tanto surpreendente de pesquisa foi feita na inicialização do clustering de k-means e talvez você queira experimentar alternativas à abordagem fornecida aqui. Em muitos casos, o clustering final produzido pelo algoritmo k-means depende de como o clustering é inicializado.
Procurando dados anormais
Uma maneira de usar o clustering de dados é simplesmente explorar diferentes clusterings e procurar resultados inesperados ou surpreendentes. Outra possibilidade é procurar tuplas de dados anormais dentro de um cluster. O programa de demonstração verifica o cluster 0 para localizar a tupla daquele cluster que está mais distante do centroide do cluster usando um método chamado Outlier, que está listado na Figura 8.
Figura 8 O 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; }
Depois de inicializar as matrizes means e centroids, o método Outlier itera em cada tupla do cluster especificado e computa a distância euclidiana da tupla até o centroide do cluster e, em seguida, retorna os valores da tupla que tem a maior distância para os valores de centroide. Uma alternativa secundária a ser considerada é retornar o índice da tupla de dados mais distante.
Há muitas outras maneiras que podem ser usadas para examinar anormalidades em dados clusterizados. Por exemplo, talvez você queira determinar a distância média entre cada tupla e seu centroide de cluster atribuído ou queira examinar as distâncias dos centroides de cluster um do outro.
Rotina de exibição
Para completar, apresentamos aqui algumas rotinas de exibição simplificadas. O download do código tem versões um pouco mais sofisticadas. Se você usar essas rotinas simplificadas, precisará modificar essas chamadas no método Main. Para exibir dados brutos, médias e centroides, você pode usar:
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 exibir a matriz de clustering, você pode usar:
static void ShowVector(int[] vector) { for (int i = 0; i < vector.Length; ++i) Console.Write(vector[i] + " "); Console.WriteLine(""); }
Para exibir os valores de exceção, você pode usar:
static void ShowVector(double[] vector) { for (int i = 0; i < vector.Length; ++i) Console.Write(vector[i].ToString("F1") + " "); Console.WriteLine(""); }
E para exibir dados brutos agrupados por cluster, você pode 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(""); } }
Conclusão
O clustering de dados está intimamente relacionado à classificação de dados e algumas vezes é confundido com ela. O clustering é uma técnica não supervisionada que agrupa itens de dados sem nenhuma previsão do que esses grupos podem ser. Normalmente, o clustering é um processo exploratório. Por outro lado, a classificação é uma técnica supervisionada que requer a especificação de grupos conhecidos em dados de treinamento, depois do que cada tupla é colocada em um desses grupos. Normalmente, a classificação é usada para fins de previsão.
O código e a explicação apresentados neste artigo devem dar a você informações suficientes para experimentar o clustering de dados k-means ou para criar uma ferramenta de clustering autônoma totalmente personalizável ou para adicionar recursos de clustering a um aplicativo .NET sem contar com qualquer dependência externa. Existem muitos outros algoritmos de clustering além do k-means, e eu apresentarei alguns deles em artigos futuros da MSDN Magazine, incluindo minimização de entropia de dados, utilitário de categoria e inferência bayesiana ingênua.
Dr. James McCaffrey trabalha para a Volt Information Sciences Inc., onde gerencia o treinamento técnico de engenheiros de software que trabalham no campus da Microsoft, em Redmond, Washington. Ele trabalhou em vários produtos da Microsoft, como o Internet Explorer e o MSN Busca. Ele é autor de “.NET Test Automation Recipes” (Apress, 2006) e pode ser contatado pelo email jammc@microsoft.com.
Agradecemos ao seguinte especialista técnico pela revisão deste artigo: Darren Gehring