Série de tests

Conversion de données numériques en données catégoriques

James McCaffrey

Télécharger l'exemple de code

L'une des tâches fondamentales de l'apprentissage automatique consiste à convertir des données numériques et données catégoriques. Par exemple, si vous avez un jeu de données de tailles de personnes, exprimées en pouces, comme 59,5, 64,0 et 75,5 (1,50, 1,60 et 1,90 m), il se peut que vous souhaitiez convertir ces données numériques en données catégoriques, par exemple 0, 1 et 2, pour désigner Petit, Moyen et Grand. De manière informelle, nous appelons parfois ce processus « binning data », en anglais. Dans la documentation traitant de l'apprentissage automatique, nous l'appelons généralement discrétisation de données continues.

Il existe plusieurs scénarios qui peuvent nécessiter de discrétiser des données. De nombreux algorithmes d'apprentissage automatique, comme la classification et la prédiction naïve bayésienne, ne fonctionnent qu'avec des données catégoriques. Ainsi, si vos données brutes sont numériques et si vous souhaitez appliquer la naïve bayésienne, vous devez discrétiser les données. Il se peut même que vous rencontriez des données mixtes, numériques et catégoriques, comme les données que l'on trouve souvent sur les feuilles de calcul Excel. Très peu d'algorithmes d'apprentissage automatique fonctionnent avec des données mixtes, vous pouvez donc convertir les données numériques en données catégoriques, puis utiliser un algorithme d'apprentissage automatique qui fonctionne avec des données catégoriques. Le clustering de données par un utilitaire de catégorie en est un exemple.

Il existe très peu de ressources disponibles décrivant exactement comment implémenter les algorithmes de discrétisation, peut-être parce que le sujet n'est pas le plus glamour qui soit. Dans cet article, je présente un algorithme de discrétisation puissant. Bien que l'idée ne soit pas nouvelle, à ma connaissance, l'implémentation présentée ici n'a jamais été publiée.

Pour mieux comprendre où cet article veut en venir, observez le programme de démo illustré à la figure 1. Cette démo définit 20 points de données qui représentent les tailles des personnes, exprimées en pouces. Les données brutes sont présentées dans l'histogramme de la figure 2. Elle analyse les données et crée un objet discrétiseur, puis affiche une représentation interne du discrétiseur. Celui-ci conserve une copie des valeurs distinctes des données brutes dans un tableau trié (des valeurs les plus basses aux plus hautes) nommé data. Le nombre de catégories a été calculé pour être au nombre de trois, stockés dans la variable membre, k.

Figure 1 Conversion de données numériques en données catégoriques

Figure 2 Données brutes à catégoriser

Chacun des points de données a été attribué à l'une des trois catégories. Chaque catégorie est encodée sous la forme d'un entier de base zéro, de 0 à 2, et les informations d'attribution sont stockées dans un tableau nommé clustering. Les trois premiers points de données (60,0, 61,0, 62,0) ont été attribués à la catégorie 0. Les quatre points de données suivants (66,0, 67,0, 68,0, 69,0) ont été attribués à la catégorie 1 et les quatre derniers points de données (73,0, 74,0, 76,0, 78,0) ont été attribués à la catégorie 2. La moyenne arithmétique des trois premiers points de données de la catégorie 0 est de 61,00 et les moyennes des points de données des catégories 1 et 2 sont respectivement de 67,50 et 75,25.

Une fois l'objet discrétiseur créé, le programme de démo définit trois valeurs de données existantes (62,0, 66,0, 73,0) et trois nouvelles valeurs de données (59,5, 75,5, 80,5). Ici, la particularité réside dans le besoin, parfois, d'un jeu de données fixe, mais dans d'autres scénarios, de nouvelles données sont générées de manière dynamique et doivent être converties. Le discrétiseur convertit chacun des six points de données numériques en données catégoriques : 0, 1, 2 et 0, 2, 2, respectivement.

Cet article part du principe que vous disposez au moins de compétences de niveau intermédiaire en programmation. J'ai codé cet algorithme de discrétisation avec le langage C#, mais vous ne devriez pas avoir trop de difficultés à refactoriser le code dans un autre langage, comme Python ou Visual Basic. J'ai volontairement omis d'effectuer la vérification d'erreurs la plus normale afin de garder un code de taille réduite et les idées principales claires. Le code de démonstration est trop long pour être présenté intégralement dans cet article, mais le code source complet est disponible à l'adresse suivante : archive.msdn.microsoft.com/mag201308TestRun.

Pas aussi simple qu'il y paraît

Au premier abord, la conversion de données numériques en données catégoriques peut sembler facile. Une approche simple consisterait à diviser les données source brutes en intervalles égaux. Par exemple, dans les données de la démo et de la figure 2, la plage est 78,0 - 60.0 = 18.0. Si elles sont divisées par k = 3 intervalles, cela fait une largeur d'intervalle de 6,0 pouces (15 cm). Ainsi, toutes les données situées entre 60,0 et 66,0 seraient attribuées à la catégorie 0, les données situées entre 66,0 et 72,0 seraient attribuées à la catégorie 1 et celles situées entre 72,0 et 78,0 seraient attribuées à la catégorie 2. Le problème de cette approche d'intervalle égal est le suivant : elle ignore les divisions naturelles dans les données. Regardez maintenant la figure 2 et vous constaterez qu'un bon algorithme de discrétisation doit diviser les données quelque part entre 63,0 et 65,0, mais pas à 66,0.

L'utilisation d'une fréquence égale constitue une seconde approche naïve de la discrétisation. Pour ce qui concerne les données en exemple, puisqu'il existe 11 points de données distincts, avec k = 3 catégories et que 11/3 = 3 (par troncation de la division des entiers), vous pouvez attribuer les trois premiers points de données à la catégorie 0, les trois points de données suivants à la catégorie 1 et les cinq derniers points de données à la catégorie 2. L'approche equal-frequency ignore elle aussi les divisions naturelles dans les données.

L'algorithme de discrétisation présenté dans cet article utilise l'approche data-clustering. Les données brutes sont regroupées en cluster à l'aide d'un algorithme k-means (qui prend en compte les divisions naturelles dans les données) qui utilise ensuite les moyennes générées par l'algorithme de clustering pour catégoriser les nouvelles données. Par exemple, dans la figure 1, les trois moyennes sont 61,00, 67,50 et 75,25. Pour associer la valeur numérique 62,5 à une valeur catégorique, le discrétiseur détermine laquelle des trois valeurs moyennes est la plus proche de 62,5 (c'est-à-dire 61,0), puis attribue la valeur du cluster associée à 61,0 (c'est-à-dire 0) comme valeur de catégorie pour 62,5.

Clustering k-means

L'algorithme de clustering k-means est assez simple. Il en existe de nombreuses variations. Dans sa forme la plus basique, pour un jeu de points de données précis et un nombre de clusters k donné, le processus d'initialisation attribue chaque point de données à un cluster sélectionné au hasard. Ensuite, les moyennes des points de données de chacun des clusters sont calculées. Puis chaque point de données est analysé et réattribué au cluster dont la moyenne est la plus proche du point de données. Les étapes compute-means et reassign-cluster sont répétées jusqu'à ce qu'aucun point de données ne soit réattribué à un nouveau cluster.

Structure générale du programme

Le programme de démonstration présenté à la figure 1 est une application de console unique. J'ai utilisé Visual Studio 2012, mais la démonstration n'a aucune dépendance significative et n'importe quelle version de Visual Studio équipé de Microsoft .NET Framework 2.0. ou ultérieur devrait fonctionner parfaitement. J'ai créé une nouvelle application de console C# et l'ai nommée BinningData. Une fois le code du modèle chargé, dans la fenêtre de l'explorateur de solutions, j'ai renommé le fichier Program.cs en BinningProgram.cs, nom plus descriptif, ce qui a eu pour effet automatique pour Visual Studio de renommer la classe du programme. En haut du code source, j'ai supprimé toutes les références aux espaces de noms, à l'exception de System et Collections.Generic.

La structure générale du programme, avec quelques modifications mineures, est présentée à la figure 3. Les instructions d'appel clé peuvent être résumées de la manière suivante :

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

Figure 3 Structure du programme de démo

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

Classe Discretizer

La classe Discretizer compte quatre membres de données :

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

Le constructeur Discretizer utilise des données numériques pour activer une méthode Discretize qui accepte une valeur numérique et retourne une valeur catégorique d'un entier de base zéro. Remarquez que le discrétiseur détermine automatiquement le nombre de catégories.

Les données du tableau contiennent les valeurs distinctes des données brutes et servent à créer le clustering. L'entier k désigne le nombre de clusters auxquels attribuer les données, ce qui correspond également au nombre de catégories de données. Le tableau nommé means présente la taille k et contient les moyennes arithmétiques des points de données attribués à chaque cluster à n'importe quel moment de l'exécution de l'algorithme de clustering.

Le tableau nommé clustering encode la manière dont les données sont mises en cluster à n'importe quel moment. L'index du tableau clustering représente l'index d'un point de données stocké dans le tableau data et la valeur dans le tableau clustering représente l'attribution actuelle du cluster. Par exemple, si clustering[9] = 2, alors le point de données à data[9] est attribué au cluster 2.

Constructeur Discretizer

Le constructeur Discretizer est défini par :

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();
}

La première étape vise à extraire les valeurs distinctes des données brutes. Il y a plusieurs façons de procéder. Ici, le code trie une copie des données brutes puis appelle une méthode d'assistance, GetDistinctValues. Une fois les valeurs distinctes déterminées, le tableau clustering peut être alloué.

Voici la méthode 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;
}

Une fois les données source triées, la méthode peut exécuter une seule analyse en recherchant les instances où deux valeurs consécutives ne sont pas égales. Les données brutes sont de type double, ce qui signifie que la comparaison de deux valeurs en matière d'égalité exacte peut être risquée, c'est pourquoi nous utilisons une méthode d'assistance, AreEqual :

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

La méthode AreEqual utilise un seuil de proximité arbitraire de 0,000001. Il peut être bon de transmettre cette valeur dans l'objet Discretizer sous la forme d'un paramètre d'entrée. Une variable, nommée epsilon, est souvent utilisée dans ce scénario.

Une fois les valeurs distinctes extraites des données brutes, l'étape suivante consiste à déterminer k, le nombre de clusters, qui correspond également au nombre de catégories. J'utilise ici une règle générale et k devient la racine carrée du nombre d'éléments de données. Il est également possible d'écrire le constructeur de manière à ce que la valeur de k soit transmise sous la forme d'un paramètre. Déterminer la valeur optimale de k est essentiellement un problème de recherche non solutionné d'apprentissage automatique.

Une fois la valeur de k calculée, le constructeur alloue de l'espace pour les moyennes du tableau, puis appelle la méthode Cluster. Cette méthode effectue le clustering k-means sur les données et les valeurs du dernier tableau de moyennes peuvent servir à attribuer une valeur catégorie à n'importe quelle valeur numérique.

Algorithme de clustering

Le cœur de la classe Discretizer est constitué du code qui effectue le clustering k-means. La méthode Cluster est présentée dans la figure 4.

Figure 4 Méthode 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();
  }
}

La méthode Cluster est relativement courte car elle renvoie tout le travail le plus dur aux méthodes d'assistance. La méthode InitializeClustering attribue tous les points de données à un cluster initial. Ensuite, les moyennes des points de données attribués à chacun des clusters sont calculées à l'aide des attributions de clustering.

Dans la boucle du principal algorithme de clustering, tous les points de données sont attribués à un cluster par la méthode AssignAll. Cette méthode AssignAll appelle les méthodes d'assistance Distance et MinIndex. La méthode Distance définit la distance entre deux points de données :

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

Ici, j'utilise la distance euclidienne (définie comme la racine carrée de la différence au carré). Puisque les points de données sont des valeurs uniques et non pas des vecteurs, la distance euclidienne équivaut à Math.Abs(x1 - x2), il est peut-être préférable d'utiliser ce calcul plus simple.

La boucle sort lorsqu'aucun changement n'est effectué dans le tableau clustering, indiqué par la valeur de retour de AssignAll ou lorsque le tableau des moyennes ne peut pas être calculé parce que le nombre de valeurs attribué à un cluster est de zéro ou lorsqu'une valeur maximale de décompte de boucles est atteinte. Ici, maxCt se voit attribuer de manière arbitraire une valeur de 10 fois le nombre de points de données. En général, l'algorithme de clustering converge extrêmement rapidement et une condition de sortie de boucle parce qu'elle a atteint maxCt est probablement due à une erreur de logique. Il est préférable de vérifier cet élément.

Puisque le processus de clustering réattribue de manière répétée les valeurs aux clusters, il se peut que le nombre de valeurs attribué à un cluster devienne zéro, ce qui rend impossible le calcul d'une moyenne. La méthode d'assistance ComputeMeans tente de calculer toutes les moyennes k mais retourne des erreurs si le nombre est de zéro. La méthode est présentée à la figure 5.

Figure 5 Méthode 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
}

Initialisation du clustering

Le processus d'initialisation du clustering est un peu complexe. Supposons que les données soient constituées de 11 valeurs triées, comme illustré dans la figure 1 et que k, le nombre de clusters, ait été défini sur trois. Après l'initialisation, l'objectif du clustering des membres du tableau est d'avoir trois valeurs 0 dans les cellules 0 à 2, trois valeurs 1 dans les cellules 3 à 5 et les cinq valeurs 2 restantes dans les cellules 6 à 10. En d'autres termes, le clustering doit être distribué de manière égale par fréquence.

La première étape consiste à générer des valeurs en bordure de {3, 6, 9}, ce qui implicitement définit les intervalles sur 0-2, 3-5 et 6 et plus. Ceci se fait grâce à la méthode d'assistance GetInitialIndexes, qui divise juste le nombre de points de données par le nombre 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;
}

La deuxième étape consiste à définir une méthode d'assistance qui calcule la valeur du cluster pour une valeur d'index de données spécifiée, à l'aide des valeurs en bordure :

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
}

La troisième étape consiste à attribuer tous les index de données à un cluster :

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

Par essence, le processus d'initialisation correspond à l'approche equal-frequency décrite précédemment dans ce même article.

Méthode Discretize

Une fois les données mises en clusters, les valeurs finales dans les tableaux de moyennes peuvent servir à attribuer une valeur catégorique de base zéro à une valeur numérique. La méthode Discretize est la suivante :

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);
}

La méthode calcule la distance entre la valeur d'entrée x et chaque moyenne k puis retourne l'index de la moyenne la plus proche, qui est un ID de cluster et aussi une valeur catégorique. Par exemple, si les dernières moyennes sont de 61,00, 67,50 et 75,25 et si x est de 70,00, la distance entre x et mean[0] = sqrt((70.00 - 61.00)^2) = sqrt(81.00) = 9.00. De la même manière, mean[1] = sqrt((70.00 - 67.50)^2) = 2.50 et mean[2] = sqrt((70.00 - 75.25)^2) = 5.25. La distance la plus courte est de 2,50, ce qui la situe à l'index [1], donc 70,00 est attribué à la valeur catégorique de 1.

Pour résumer

Le code présenté dans cet article peut être utilisé en l'état pour vous offrir une conversion de données numériques en données catégoriques de haute qualité pour l'apprentissage automatique. Il peut être bon d'encapsuler la classe Discretizer dans une bibliothèque de classes plutôt que d'intégrer directement le code dans une application.

La fonctionnalité essentielle que vous souhaitez sûrement personnaliser vise à déterminer le nombre de catégories, k. Pour cela, vous pouvez définir une valeur de seuil. Sous ce seuil, chaque point de données génère une valeur de catégorie. Supposons par exemple que vous vous occupiez de l'âge des personnes. Imaginons que ces âges vont de 1 à 120. Avec uniquement 120 valeurs distinctes possibles, plutôt que de calculer k en tant que racine carrée de 120 (ce qui donnerait 10 catégories), vous pourriez définir k comme égale à 120.

Dr. James McCaffrey travaille pour Microsoft sur le campus de l'entreprise à Redmond, État de Washington. Il a collaboré à plusieurs produits Microsoft, comme Internet Explorer et MSN Search. Il est l'auteur de « .NET Test Automation Recipes » (Apress, 2006) et vous pouvez le contacter à l'adresse jammc@microsoft.com.

Merci aux experts techniques suivants d'avoir relu cet article : Richard Hughes (Microsoft Research)