Execução de teste

Convertendo dados numéricos em dados categóricos

James McCaffrey

Baixar o código de exemplo

Uma tarefa fundamental no campo de aprendizado de máquina é converter dados numéricos em dados categóricos. Por exemplo, se você tem um conjunto de dados da altura das pessoas em polegadas, como 59,5, 64.0 e 75,5, convém converter esses dados numéricos em dados categóricos, por exemplo, 0, 1 e 2, para representar a baixo, médio e alto. Informalmente, esse processo é algumas vezes chamado de compartimentalização de dados. Na literatura de aprendizado de máquina, o processo geralmente é chamado discretização de dados contínuos.

Existem várias situações em que você pode querer discretizar os dados. Muitos algoritmos de aprendizado de máquina, como a classificação e previsão bayesiana ingênua, funcionam somente com dados categóricos. Então, se seus dados brutos são numéricos e você deseja aplicar a abordagem bayesiana ingênua, você deve discretizar os dados. Você também pode ter dados numéricos e categóricos misturados, como os dados encontrados frequentemente em uma planilha do Excel. Pouquíssimos algoritmos de aprendizado de máquina funcionam com dados mistos e, portanto, você pode converter os dados numéricos em dados categóricos e depois usar um algoritmo de aprendizado de máquina que funcione com dados categóricos. O clustering de dados usando o Category Utility é um exemplo.

Talvez porque o tema não seja muito glamoroso, existem poucos recursos disponíveis que descrevem exatamente como implementar algoritmos de discretização. Neste artigo, apresentarei um algoritmo de discretização eficiente. Embora as ideias não sejam novas, até onde eu saiba, a implementação apresentada neste artigo não foi publicada antes.

A melhor maneira de saber o rumo que este artigo tomará é examinar o programa de demonstração mostrado na Figura 1. O demonstração define 20 pontos de dados que representam a altura das pessoas em polegadas. Os dados brutos são mostrados no histograma na Figura 2. A demonstração analisa os dados e cria um objeto discretizer, depois mostra uma representação interna do discretizer. O discretizer mantém uma cópia dos valores distintos dos dados brutos em uma matriz classificada (dos valores menores para os maiores) chamada data. O número de categorias foi calculado para ser três e é armazenado na variável membro k.

Figura 1 Conversão de dados numéricos em dados categóricos

Figura 2 Dados brutos para categorizar

Cada um dos pontos de dados foi atribuído a uma das três categorias. Cada categoria é codificada como um inteiro baseado em zero, 0 a 2, e as informações de atribuição são armazenadas em uma matriz chamada clustering. Os três primeiros pontos de dados (60.0, 61.0, 62.0) foram atribuídos à categoria 0. Os próximos quatro pontos de dados (66.0 67.0, 68.0, 69.0) foram atribuídos à categoria 1, e os quatro pontos de dados finais (73.0, 74.0, 76.0, 78.0) foram atribuídos à categoria 2. A média aritmética dos três primeiros pontos de dados na categoria 0 é 61.00, e as médias dos pontos de dados nas categorias 1 e 2 são 67.50 e 75.25, respectivamente.

Depois de criar o objeto discretizer, o programa de demonstração configura três valores de dados existentes (62.0, 66.0, 73.0) e três novos valores de dados (59.5, 75.5, 80.5). A ideia aqui é que às vezes você tem um conjunto de dados fixo, mas em outros casos, novos dados são gerados dinamicamente e devem ser convertidos. O discretizer converte cada um dos seis pontos de dados numéricos em dados categóricos: 0, 1, 2 e 0, 2, 2, respectivamente.

Este artigo pressupõe que você tenha no mínimo habilidades de programação de nível intermediário. Codifiquei o algoritmo de discretização usando a linguagem C#, mas você não deve ter muita dificuldade para refatorar o código em outra linguagem, como Python ou Visual Basic. Omiti grande parte da verificação de erros normal para manter o código pequeno e a ideia principal clara. O código de demonstração é um pouco longo para ser apresentado por completo neste artigo, mas o código-fonte completo está disponível em archive.msdn.microsoft.com/mag201308TestRun.

Não é tão fácil quanto parece

A princípio, converter dados numéricos em dados categóricos parece ser um problema fácil de resolver. Uma abordagem simples seria dividir os dados de origem brutos em intervalos iguais. Por exemplo, para os dados na demonstração e na Figura 2, o intervalo é 78.0 - 60.0 = 18.0. Dividindo isso por k = 3 intervalos dá uma largura de intervalo de 6,0 polegadas. Então, os dados entre 60.0 e 66.0 seriam atribuídos à categoria 0, os dados entre 66.0 e 72.0 seriam atribuídos à categoria 1, e os dados entre 72.0 e 78.0 seriam atribuídos à categoria 2. O problema com essa abordagem de intervalos iguais é que ela ignora as quebras naturais nos dados. Se você verificar a Figura 2, verá que um bom algoritmo de discretização deve quebrar os dados em algum lugar entre 63.0 e 65.0, não em 66.0.

Uma segunda abordagem ingênua de discretização seria usar a frequência igual. Para os dados de exemplo, como há 11 pontos de dados distintos, com k = 3 categorias e 11 / 3 = 3 (com truncamento de divisão de número inteiro), você pode atribuir os três primeiros pontos de dados à categoria 0, três pontos de dados seguintes à categoria 1 e os últimos cinco pontos de dados à categoria 2. A abordagem de frequência igual também ignora quebras naturais nos dados.

O algoritmo de discretização apresentado neste artigo usa uma abordagem de clustering de dados. Os dados brutos são agrupados usando um algoritmo k-means (que leva em conta quebras naturais nos dados) e, em seguida, usam as médias geradas pelo algoritmo de clustering para categorizar os novos dados. Por exemplo, na Figura 1, as três médias são 61.00, 67.50 e 75.25. Para associar o valor numérico 62.5 a um valor categórico, o discretizer determina qual das três médias está mais próxima de 62.5 (que é 61.0) e, em seguida, atribui o valor de cluster associado a 61.0 (que é 0) como o valor de categoria para 62.5.

O clustering de k-Means

O algoritmo de clustering k-means é bastante simples. Há muitas variações do algoritmo. Em sua forma mais básica, para determinado conjunto de pontos de dados e número de clusters k, o processo de inicialização atribui cada ponto de dados a um cluster selecionado aleatoriamente. Em seguida, as médias dos pontos de dados em cada um dos clusters são calculadas. Em seguida, cada ponto de dados é analisado e reatribuído ao cluster que tem a média mais próxima ao ponto de dados. As etapas de cálculo das médias e de reatribuição ao cluster são repetidas até que nenhum ponto de dados seja reatribuído a um novo cluster.

Estrutura geral do programa

O programa de demonstração mostrado na Figura 1 é um único aplicativo de console. Usei o Visual Studio 2012, mas a demonstração não tem dependências significativas e qualquer versão do Visual Studio com o Microsoft .NET Framework 2.0 ou superior deve funcionar. Criei um novo aplicativo de console em C# e dei-lhe o nome de BinningData. Após o carregamento do código de modelo, na janela do Solution Explorer, renomeei o arquivo Program.cs para o mais descritivo BinningProgram.cs, e o Visual Studio automaticamente renomeou a classe do programa. Na parte superior do código-fonte, exclui todas as referências aos namespaces, exceto as que se referem a System e Collections.Generic.

A estrutura geral do programa, com pequenas edições, é apresentada na Figura 3. As principais instruções de chamada podem ser resumidas como:

double[] rawData = new int[] { 66.0, 66.0, ... };
Discretizer d = new Discretizer(rawData);
double numericVal = 75.5;
int catVal = d.Discretize(numericVal);

Figura 3 A estrutura do programa de demonstração

using System;
using System.Collections.Generic;
namespace BinningData
{
  class BinningProgram
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin discretization of continuous data demo\n");
        double[] rawData = new double[20] {
          66, 66, 66, 67, 67, 67, 67, 68, 68, 69,
          73, 73, 73, 74, 76, 78,
          60, 61, 62, 62 };
        Console.WriteLine("Raw data:");
        ShowVector(rawData, 2, 10);
        Console.WriteLine("\nCreating a discretizer on the raw data");
        Discretizer d = new Discretizer(rawData);
        Console.WriteLine("\nDiscretizer creation complete");
        Console.WriteLine("\nDisplaying internal structure of the discretizer:\n");
        Console.WriteLine(d.ToString());
        Console.WriteLine("\nGenerating three existing and three new data values");
        double[] newData = new double[6] { 62.0, 66.0, 73.0, 59.5, 75.5, 80.5 };
        Console.WriteLine("\nData values:");
        ShowVector(newData, 2, 10);
        Console.WriteLine("\nDiscretizing the data:\n");
        for (int i = 0; i < newData.Length; ++i)
        {
          int cat = d.Discretize(newData[i]);
          Console.WriteLine(newData[i].ToString("F2") + " -> " + cat);
        }
        Console.WriteLine("\n\nEnd discretization demo");
        Console.ReadLine();
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
        Console.ReadLine();
      }
    } // Main
    public static void ShowVector(double[] vector, int decimals,
      int itemsPerRow) { . . }
  } // Program
  public class Discretizer
  {
    public Discretizer(double[] rawData) { . . }
    private static double[] GetDistinctValues(double[] array) { . . }
    private static bool AreEqual(double x1, double x2) { . . }
    public int Discretize(double x) { . . }
    public override string ToString() { . . }
    private void InitializeClustering() { . . }
    private int[] GetInitialIndexes() { . . }
    private int InitialCluster(int di, int[] initialIndexes) { . . }
    private void Cluster() { . . }
    private bool ComputeMeans() { . . }
    private bool AssignAll() { . . }
    private int MinIndex(double[] distances) { . . }
    private static double Distance(double x1, double x2) { . . }
  }
} // ns

A classe Discretizer

A classe Discretizer tem quatro membros de dados:

private double[] data;
private int k;
private double[] means;
private int[] clustering;

O construtor Discretizer usa dados numéricos para habilitar um método Discretize que aceite um valor numérico e que retorne um valor categórico inteiro baseado em zero. Observe que o Discretizer determina o número de categorias automaticamente.

Os dados da matriz mantém os valores distintos dos dados brutos e são usados para criar o clustering. O inteiro k é o número de clusters para atribuir aos dados, que é também o número de categorias de dados. A matriz chamada means tem o k de tamanho e detém a média aritmética dos pontos de dados atribuídos a cada cluster em um determinado momento durante a execução do algoritmo de clustering.

A matriz chamada clustering codifica como os dados são agrupados em qualquer momento. O índice da matriz clustering indica o índice de um ponto de dados armazenado na matriz data, e o valor na matriz clustering indica a atribuição de cluster atual. Por exemplo, se clustering[9] = 2, o ponto de dados em data[9] será atribuído ao cluster 2.

O construtor Discretizer

O construtor Discretizer é definido como:

public Discretizer(double[] rawData)
{
  double[] sortedRawData = new double[rawData.Length];
  Array.Copy(rawData, sortedRawData, rawData.Length);
  Array.Sort(sortedRawData);
  this.data = GetDistinctValues(sortedRawData);
  this.clustering = new int[data.Length];
  this.k = (int)Math.Sqrt(data.Length); // heuristic
  this.means = new double[k];
  this.Cluster();
}

O primeiro passo é extrair os valores distintos dos dados brutos. Existem várias formas de se fazer isso. O código aqui classifica uma cópia dos dados brutos e chama um método auxiliar, GetDistinctValues. Uma vez determinados os valores distintos, a matriz clustering pode ser alocada.

Este é o método GetDistinctValues:

private static double[] GetDistinctValues(double[] array)
{
  List<double> distinctList = new List<double>();
  distinctList.Add(array[0]);
  for (int i = 0; i < array.Length - 1; ++i)
    if (AreEqual(array[i], array[i + 1]) == false)
      distinctList.Add(array[i+1]);
  double[] result = new double[distinctList.Count];
  distinctList.CopyTo(result);
  return result;
}

Como a fonte de dados foi classificada, o método pode executar uma única verificação procurando instâncias onde dois valores consecutivos não são iguais. Os dados brutos são de tipo duplo, o que significa que comparar dois valores de igualdade exata pode ser arriscado e, portanto, um método auxiliar, AreEqual, é usado:

private static bool AreEqual(double x1, double x2)
{
  if (Math.Abs(x1 - x2) < 0.000001) return true;
  else return false;
}

O método AreEqual usa um limite de proximidade arbitrário de 0,000001. Pode ser conveniente passar esse valor para o objeto Discretizer como um parâmetro de entrada. Uma variável chamada epsilon é muitas vezes usada nesse caso.

Depois de extrair os valores distintos dos dados brutos, o próximo passo é determinar o k, o número de clusters, que também é o número de categorias. Aqui uma regra básica é usada e k torna-se a raiz quadrada do número de itens de dados. Uma alternativa é escrever o construtor de forma que o valor de k seja passado como um parâmetro. Determinar o valor ideal de k é essencialmente um problema de pesquisa de aprendizado de máquina sem solução.

Depois foi calculado o valor de k, o construtor aloca espaço para a matriz means e depois chama o método Cluster. Esse método executa o clustering de k-means nos dados e nos valores da matriz means final que podem ser usados para atribuir um valor de categoria a qualquer valor numérico.

O algoritmo de clustering

O coração da classe Discretizer é o código que executa o clustering de k-means. O método Cluster está listado na Figura 4.

Figura 4 O método Cluster

private void Cluster()
{
  InitializeClustering();
  ComputeMeans();
  bool changed = true; bool success = true;
  int ct = 0;
  int maxCt = data.Length * 10; // Heuristic
  while (changed == true && success == true && ct < maxCt) {
    ++ct;
    changed = AssignAll();
    success = ComputeMeans();
  }
}

O método Cluster é relativamente curto, porque delega todo o trabalho pesado para os métodos auxiliares. O método InitializeClustering atribui todos os pontos de dados a um cluster inicial. Em seguida, as médias dos pontos de dados atribuídas a cada cluster são calculadas usando as atribuições de clustering.

Dentro do loop do algoritmo de clustering principal, todos os pontos de dados são atribuídos a um cluster pelo método AssignAll. O método AssignAll chama os métodos auxiliares Distance e MinIndex. O método Distance define a distância entre dois pontos de dados:

private static double Distance(double x1, double x2)
{
  return Math.Sqrt((x1 - x2) * (x1 - x2));
}

Aqui, a distância euclidiana (definida como a raiz quadrada da diferença ao quadrado) é usada. Como os pontos de dados são valores únicos, e não vetores, a distância euclidiana é equivalente a Math.Abs(x1 - x2) e, portanto, convém usar este cálculo mais simples.

O loop é encerrado quando não há alteração na matriz de clustering, indicada pelo valor de retorno de AssignAll, ou quando a matriz means não pode ser computada porque a contagem dos valores atribuídos a um cluster é zero, ou quando é atingido o valor máximo do contador de loop. Aqui, maxCt é atribuído arbitrariamente a um valor 10 vezes o número de pontos de dados. Em geral, o algoritmo de clustering aqui converge muito rapidamente, e uma condição de encerramento do loop por atingir maxCt se deve provavelmente a um erro de lógica e, portanto, convém verificar isso.

Como o processo de clustering reatribui repetidamente valores a clusters, é possível que o número de valores atribuídos a um cluster se tornar zero, tornando impossível calcular a média. O método auxiliar ComputeMeans tenta calcular todos as médias de k, mas retorna false se a contagem for zero. O método é apresentado na Figura 5.

Figura 5 O método ComputeMeans

private bool ComputeMeans()
{
  double[] sums = new double[k];
  int[] counts = new int[k];
  for (int i = 0; i < data.Length; ++i)
  {
    int c = clustering[i]; // Cluster ID
    sums[c] += data[i];
    counts[c]++;
  }
  for (int c = 0; c < sums.Length; ++c)
  {
    if (counts[c] == 0)
      return false; // fail
    else
      sums[c] = sums[c] / counts[c];
  }
  sums.CopyTo(this.means, 0);
  return true; // Success
}

Inicializando o clustering

O processo de inicialização do clustering é um pouco complicado. Suponha que os dados consistam em 11 valores classificados como mostrado na Figura 1, e k, o número de clusters, tenha sido definido como três. Após a inicialização, o objetivo é que o clustering de membros da matriz tenha três valores 0 nas células de 0 a 2, três valores 1 nas células de 3 a 5, e os restantes cinco valores 2 nas células de 6 a 10. Em outras palavras, o clustering deve ser distribuído uniformemente pela frequência.

O primeiro passo é gerar valores de fronteira de {3, 6, 9}, que implicitamente definem intervalos de 0-2, 3-5 e 6-maior. Isso é feito pelo método auxiliar GetInitialIndexes, que apenas divide o número de pontos dados pelo número de clusters:

private int[] GetInitialIndexes()
{
  int interval = data.Length / k;
  int[] result = new int[k];
  for (int i = 0; i < k; ++i)
    result[i] = interval * (i + 1);
  return result;
}

O segundo passo é definir um método auxiliar que calcule o valor do cluster para um determinado valor de índice de dados usando os valores de fronteira:

private int InitialCluster(int di, int[] initialIndexes)
{
  for (int i = 0; i < initialIndexes.Length; ++i)
    if (di < initialIndexes[i])
      return i;
  return initialIndexes.Length - 1; // Last cluster
}

O terceiro passo é atribuir todos os índices de dados a um cluster:

private void InitializeClustering()
{
  int[] initialIndexes = GetInitialIndexes();
  for (int di = 0; di < data.Length; ++di)
  {
    int c = InitialCluster(di, initialIndexes);
    clustering[di] = c;
  }
}

Essencialmente, o processo de inicialização é a abordagem de frequência igual descrita anteriormente neste artigo.

O método Discretize

Depois de clusterizar os dados, os valores finais da matriz means podem ser usados para atribuir um valor categórico baseado em zero a um valor numérico. O método Discretize é:

public int Discretize(double x)
{
  double[] distances = new double[k];
  for (int c = 0; c < k; ++c)
    distances[c] = Distance(x, data[means[c]]);
  return MinIndex(distances);
}

O método calcula a distância do valor de entrada x para cada média k e depois retorna o índice da média mais próxima, que é uma ID de cluster e é também um valor categórico. Por exemplo, se as médias finais forem 61.00, 67.50 e 75.25, e x for 70.00, a distância de x para mean[0] = sqrt((70.00 - 61.00)^2) = sqrt(81.00) = 9.00. Da mesma forma, mean[1] = sqrt((70.00 - 67.50)^2) = 2.50, e mean[2] = sqrt((70.00 - 75.25)^2) = 5.25. A menor distância é 2.50, que está no índice [1]. Portanto, 70.00 é atribuído ao valor categórico 1.

Conclusão

O código apresentado neste artigo pode ser usado como está para lhe fornecer conversão de dados numéricos em categóricos de alta qualidade para o aprendizado de máquina. Convém encapsular a classe Discretizer em uma biblioteca de classes em vez de incorporar o código diretamente em um aplicativo.

O principal componente que convém personalizar é a determinação do número de categorias, k. Uma possibilidade é definir um valor limite. Abaixo do limite, cada ponto de dados gera um valor de categoria. Por exemplo, suponha que você está lidando com a idade das pessoas. Suponha que a variação de idades seja 1 a 120. Com apenas 120 valores distintos possíveis, em vez de calcular k como a raiz quadrada de 120 (que lhe daria 10 categorias), bastaria apenas definir k igual a 120.

Dr. James McCaffrey trabalha para a Microsoft, no campus de Redmond, Wash., da empresa. 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: Richard Hughes (Microsoft Research)