Cet article a fait l'objet d'une traduction automatique.

Série de tests

Classification consensus à l'aide de C#

James McCaffrey

Télécharger l'exemple de code

En machine learning (ML), la classification est le processus de création d'un modèle (en général une équation mathématique quelconque), ou un ensemble de règles qui prédit une valeur qui peut prendre des valeurs discrètes, non numériques. Par exemple, vous pourriez vouloir prédire le parti (démocrate ou républicain) d'un membre du Congrès après son dossier avec droit de vote. Le modèle de formation est le processus de trouver l'ensemble des constantes (pour un modèle d'équations mathématiques) ou un ensemble de règles (pour un modèle fondé sur des règles), afin que quand présenté avec des données d'entraînement avec des valeurs de variable dépendante de sortie connus, les sorties calculées correspondent étroitement les résultats connus. Ensuite, le modèle peut être utilisé pour faire des prédictions pour les nouvelles données avec sorties inconnus.

Bien qu'il existe de nombreux algorithmes de classification standard et techniques, y compris Naive Bayes classification, classification de la régression logistique et classification des réseaux de neurones, pour certains problèmes, un algorithme de classification personnalisé est utile. Cet article présente une technique personnalisée qui, faute d'un meilleur nom, j'appelle la classification de consensus. Le meilleur moyen pour avoir une idée de quelle classification de consensus est et de voir où va cet article doit avoir un regard sur le programme de démonstration en Figure 1.

Figure 1 Classification de Consensus en Action

Le programme de démonstration vise à créer un modèle qui prédit le parti politique, démocrate ou républicain, d'un membre de l'US Chambre des représentants, selon vote dossier du représentant sur 16 projets de loi. L'ensemble de données brute se compose de 100 éléments, dont chacun correspond à un représentant et a 17 champs. Les 16 premiers champs de chaque élément sont votes où caractère « y » est un vote oui et caractère « n » n'est aucun un droit de vote. Le dernier champ de chaque élément est parti de politique réelle du représentant. Par exemple, les premiers éléments de deux données sont :

n, y, y, n, y, y, n, n, n, n, n, n, y, y, y, y, democrat
n, y, n, y, y, y, n, n, n, n, n, y, y, y, n, y, republican

Les données de démo sont un sous-ensemble d'un ensemble de point de repère bien connu appelé le jeu de données comptes rendus du Congrès vote. L'ensemble de données de référence complet a 435 Articles, dont certains ont une valeur de vote de "?," indiquant un vote inconnu, ou leur abstention. Le sous-ensemble de démo est constitué des 100 premiers éléments, parmi l'ensemble complet, qui n'ont pas «? » votes. En outre, le jeu de données est parti dans la première colonne ; J'ai déménagé le parti à la dernière colonne, qui est beaucoup plus pratique lors de la programmation.

Bien qu'il n'est pas nécessaire de savoir quel projet de loi, chacun des 16 votes correspondent aux, suggère le thème de chaque projet de loi 16 courts termes suivants : handicapés-bébés, eau-projet, adopter-budget, médecin-frais, el-salvador, école-religion, antisatellite, Nicaragua-contras, mx-missile, -Loi sur l'immigration, synfuels-bitume fluxé, dépenses d'éducation, superfund-sue, crime-projet de loi, en franchise de droits, l'Afrique du Sud.

Le programme de démonstration divise l'ensemble de données de 100 éléments en un ensemble de 80 questions utilisées pour l'apprentissage du modèle et un ensemble de données de 20 points pour estimer la précision du modèle qui en résulte. Un modèle de classification de consensus se compose d'un ensemble de règles simples telles que, « si le représentant a voté « y » sur le projet de loi 0 et « n » sur le projet de loi 3 et « y » sur le projet de loi 15, puis le représentant est un républicain. » Dans la démo, le nombre des conditions booléennes dans chaque règle simple est fixé à 5, et le nombre total de règles est défini à 500. En outre, chaque règle simple est nécessaire pour être précis sur les éléments de données de formation pour laquelle la règle s'applique au moins 90 %.

Dans les coulisses, le processus de formation a généré les 500 règles simples. Une fois le modèle a été créé, le programme de démonstration appliqué les règles de modèle pour les données d'apprentissage et obtenu une précision de 93,75 %. Ensuite le modèle a été appliqué à l'ensemble de test de 20 points, ayant pour résultat 84.21 % exactitude — 16 prédictions correctes, trois prédictions erronées et une donnée où aucune des règles dans le modèle 500 étaient applicable.

Cet article suppose que vous avez au moins intermédiaire programmation des compétences et une connaissance de base de la classification de ML. La démo est codée à l'aide de c#, mais vous ne devriez pas avoir beaucoup de peine refactorisation du code dans une autre langue, comme Visual Basic .NET ou Python. Le code de démo est un peu trop de temps à présenter dans son intégralité, mais le code source complet est disponible dans le téléchargement qui accompagne cet article à msdn.microsoft.com/magazine/msdnmag1114.

Structure générale du programme

La structure générale du programme de démonstration, avec certaines modifications WriteLine Instructions retirées et mineurs pour économiser l'espace, est présentée en Figure 2. Pour créer la démo, j'ai lancé Visual Studio et créé une nouvelle application de console c# et baptisa Consensus­Classification. La démo n'a aucune dépendance significative de Microsoft .NET Framework, donc toutes les versions relativement récentes de Visual Studio fonctionnent. Une fois le code généré par le modèle chargé, dans la fenêtre de l'Explorateur de solutions j'ai renommé le fichier Program.cs pour le ConsensusProgram.cs plus descriptif et Visual Studio renommé automatiquement la classe Program pour moi.

Figure 2 Structure globale du programme

using System;
using System.Collections.Generic;
namespace ConsensusClassification
{
  class ConsensusProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin consensus classification demo");
      Console.WriteLine("Goal is predict political party");
      string[][] allData = new string[100][];
      allData[0] = new string[] { "n", "y", "y", "n", "y", "y", "n", "n",
        "n", "n", "n", "n", "y", "y", "y", "y", "democrat" };
      allData[1] = new string[] { "n", "y", "n", "y", "y", "y", "n", "n",
        "n", "n", "n", "y", "y", "y", "n", "y", "republican" };
      // Etc.
      allData[99] = new string[] { "y", "n", "y", "n", "n", "y", "y", "y",
        "y", "y", "y", "n", "n", "n", "y", "y", "democrat" };
      Console.WriteLine("All data: ");
      ShowData(allData, 5, true);
      Console.WriteLine("Creating 80-20 train-test data");
      string[][] trainData;
      string[][] testData;
      MakeTrainTest(allData, 0, out trainData, out testData); // 0 = seed
      Console.WriteLine("Training data: \n");
      ShowData(trainData, 3, true);
      Console.WriteLine("Test data: \n");
      ShowData(testData, 3, true);
      int numConditions = 5; // Conditions per rule
      int maxNumRules = 500;
      double minAccuracy = 0.90; // Min % rule accuracy
      Console.WriteLine("Setting number conditions per rule = " + 
        numConditions);
      Console.WriteLine("Setting max number simple rules    = " + 
        maxNumRules);
      Console.WriteLine("Setting simple rule min accuracy   = " +
        minAccuracy.ToString("F2"));
      ConsensusClassifier cc =
        new ConsensusClassifier(numConditions, maxNumRules);
      Console.WriteLine("Starting training");
      cc.Train(trainData, minAccuracy);
      Console.WriteLine("Done");
      Console.WriteLine("Created " + cc.RuleCount() + " simple rules");
      double trainAcc = cc.Accuracy(trainData);
      Console.WriteLine("Accuracy on train data = " + 
        trainAcc.ToString("F4"));
      int numCorrect, numWrong, numUnknown;
      double testAcc = cc.Accuracy(testData, out numCorrect,
        out numWrong, out numUnknown);
      Console.WriteLine("Accuracy on test data  = " + 
        testAcc.ToString("F4"));
      Console.WriteLine("Number correct = " + numCorrect);
      Console.WriteLine("Number wrong   = " + numWrong);
      Console.WriteLine("Number unknown = " + numUnknown);
      Console.WriteLine("End consensus classification demo\n");
      Console.ReadLine();
    }
    static void MakeTrainTest(string[][] allData, int seed,
      out string[][] trainData, out string[][] testData) { . . }
    static void ShowData(string[][] rawData, int numRows,
      bool indices) { . . }
  } // Program
  public class ConsensusClassifier { . . }
} // ns

Toute la logique du programme est contenue dans la méthode Main. La démo a deux méthodes d'assistance statiques, MakeTrainTest et ShowData. La logique de classement est contenue dans une classe unique défini par le programme, nommée ConsensusClassifier. Le classificateur expose les six méthodes publiques : un seul constructeur, RuleCount (le nombre réel de règles simples dans le modèle), ComputeOutput (pour faire des prédictions après que le modèle a été créé), Train (pour créer le modèle) et une précision surchargée (pour calculer le pourcentage de prédictions correctes).

Dans la méthode Main, les démo programme hardcodes les données source 100-point dans un tableau de tableaux-style-chaîne de matrice :

string[][] allData = new string[100][];
allData[0] = new string[] { "n", "y", "y", "n", "y", "y", "n", "n",
  "n", "n", "n", "n", "y", "y", "y", "y", "democrat" };
...

Dans un scénario non-démo, vos données seraient probablement dans un fichier texte et vous chargeriez les données en mémoire à l'aide d'une méthode d'assistance. Les données de la source sont divisées en un jeu d'apprentissage et un jeu de test, comme suit :

string[][] trainData;
string[][] testData;
MakeTrainTest(allData, 0, out trainData, out testData);

Les pourcentages de répartition 80/20 sont codés en dur. La valeur 0 argument passé à la méthode MakeTrainTest est une valeur de départ pour un objet Math.Random afin que la séparation du train-test peut assigner des éléments de données au hasard. Une alternative consiste à utiliser une approche stratifiée afin que les proportions des éléments de données démocrate et républicain dans les matrices d'examen et de formation sont à peu près les mêmes que les pourcentages dans l'ensemble des données source.

La démo crée le modèle avec ce code :

int numConditions = 5;
int maxNumRules = 500;
double minAccuracy = 0.90;
ConsensusClassifier cc = 
  new ConsensusClassifier(numConditions, maxNumRules);
cc.Train(trainData, minAccuracy);

Ici, j'ai décidé de passer des valeurs pour le nombre de conditions booléennes dans chaque État et le nombre maximal de règles pour créer au constructeur, puis passez une référence pour les données d'apprentissage et de la précision minimale que chaque règle doit satisfaire à la méthode Train. De nombreux développeurs préfèrent passer tous les paramètres pertinents au constructeur (au détriment d'un constructeur avec un grand nombre de paramètres). Ici, je suis passé de valeurs plus directement liés à chaque méthode (au détriment d'une interface d'appel plutôt arbitraire prospectifs).

Le programme de démonstration se termine par le calcul et l'affichage de la précision du modèle :

double trainAcc = cc.Accuracy(trainData);
Console.WriteLine("Accuracy on train data = " + trainAcc.ToString("F4"));
int numCorrect, numWrong, numUnknown;
double testAcc = cc.Accuracy(testData, out numCorrect, out numWrong,
  out numUnknown);
Console.WriteLine("Accuracy on test data  = " + testAcc.ToString("F4"));
Console.WriteLine("Number correct = " + numCorrect);
Console.WriteLine("Number wrong   = " + numWrong);
Console.WriteLine("Number unknown = " + numUnknown);

La première précision surchargée retourne seulement le pourcentage des classifications correctes. Le deuxième surchargée précision renvoie, en outre, le nombre correct, incorrect et les éléments de données non applicables, lorsque non applicables signifie qu'aucun des règles du modèle s'appliquent à un élément de données particulier. Par exemple, supposons que le paramètre nombre-de-conditions a été fixé à 3 et les éléments de données a vote0 = « y, » vote1 = « y » et vote2 = « n. » même avec 500 règles, il est possible pour aucune des règles de prendre cette combinaison de votes en compte. Une alternative consiste à concevoir la méthode précision afin que les éléments de données non applicables ne sont pas possibles. Une façon courante de le faire est d'ajouter une règle finale qui ressemble, ". . .else représentant est un démocrate,"où le démocrate est une valeur par défaut, qui est généralement la valeur de variable dépendante plus courante.

Le programme de démonstration n'utilise pas le modèle pour prédire le parti politique, d'un représentant. Prédire le parti politique, d'un représentant qui ont voté « oui » sur les projets de loi [0] à [7] et « non » sur les projets de loi [8] à [15] pourrait ressembler à ceci :

string[] newData = new string[] { "y", "y", "y", "y", "y", "y", "y", "y",
  "n", "n", "n", "n", "n", "n", "n", "n" };
int party = cc.ComputeOutput(newData);
Console.WriteLine("Predicted party = " + party);

Méthode ComputeOutput retourne une valeur entière, 0 ou 1, où 0 indique républicain et 1 indique démocrate.

L'algorithme de Consensus

Le cœur du classifieur consensus est un ensemble de règles. Les deux problèmes principaux à traiter sont décider comment représenter une règle et générant des règles. Le programme de démonstration représente une règle comme un tableau d'entiers. Le régime est mieux expliqué à l'aide d'un exemple concret, comme le montre Figure 3. Supposons que le nombre des conditions booléennes dans chaque règle est fixé à trois. Une seule règle serait représentée sous forme de tableau avec sept cellules. Si le tableau possèdent des valeurs {3, 0, 8, 1, 15, 1, 0}, alors la règle correspond à « Si vote [3] est 0 et vote [8] est 1 et crédit [15] est 1, puis parti est 0. » L'ensemble de règles est une collection générique de la liste des règles.

Figure 3 Structures de données de Classification de Consensus

Le sens de 0 et 1 peut varier pour chaque colonne/crédit. Le programme de démonstration construit un tableau des collections de dictionnaires, un par colonne/vote. Entière de base zéro IDs sont assignés à chaque valeur de chaîne comme elles sont rencontrées dans chaque colonne dans les données d'apprentissage. Par exemple, dans la colonne [0], vote [0], dans les données d'apprentissage, « n » est rencontré tout d'abord attribué à 0 et « y » est rencontré ensuite assigné à 1. Mais dans la colonne [1], « y » est rencontré tout d'abord et attribué à 0 et « n » est rencontré deuxième et assignée à 1.

De même, dans la colonne [16] les données d'entraînement, la dernière colonne, qui détient les valeurs de variable dépendante « démocrates » et « républicaine », « républicaine » est tout d'abord rencontrée est donc 0 et « démocrate » est 1. Les informations de mappage de chaîne-à-entier sont stockées dans un tableau de membres de classe nommé stringToInt, comme le montre Figure 3. Si l'expression stringToInt [1] ["y"] retourne la valeur d'index de base zéro de voter oui pour vote [1], qui, pour les données d'apprentissage de démo, est 0.

Voici le pseudo-code de haut niveau pour la création de règles qui définissent le modèle de classification :

loop while numRules < maxRules && trial < maxTrials
  ++trial
  select a random row of training data
  select numConditions random columns of selected row
  create candidate rule from selected columns of selected row
  if candidate rule already in rule list, continue
  if candidate rule does not meet minimum accuracy, continue
  candidate rule is good so add rule to rule list
end loop

Un exemple concret peut aider à clarifier. Dans la boucle principale, supposons que la rangée [0] les données d'entraînement est choisie au hasard. Ensuite, supposons que numConditions a la valeur 3 et trois au hasard les colonnes sélectionnées sont [1], [2] et [15]. Dans les données d'apprentissage, ces colonnes ont des valeurs "y", "n", et « y » et la variable dépendante a la valeur « républicaine ». Les valeurs de colonne sont recherchés dans la baie-des-­collections de dictionnaires et sont 0, 0 et 0. Par conséquent, la règle du candidat est un tableau d'entiers avec les valeurs {1, 0, 2, 0, 15, 0, 0}, qui peut être interprété comme « Si la colonne 1 est 0 et la colonne 2 est 0 et colonne 15 0, puis parti est 0. »

Ensuite, les 80 points dans les données d'apprentissage sont analysés afin de voir si la règle du candidat satisfait aux critères de précision minimale. Notez que la règle du candidat sera correcte pour au moins une donnée — l'élément qui a été utilisé pour créer la règle. Toutefois, la règle du candidat ne sera pas forcément applicable à tous les éléments de formation. Par exemple, la règle de candidat {1, 0, 2, 0, 15, 0, 0} qui provenait de l'élément de données [0] n'est pas applicable à l'élément de données [1] parce que la colonne [2] a la valeur 1, et non le 0 requis.

Une fois que l'ensemble de règles a été créé, la sortie pour un jeu de données d'entrée est déterminée par ce que l'on pourrait qualifier dépouillement du scrutin. Pour chaque élément de données, toutes les règles dans l'ensemble de règles sont analysés. Supposons que, comme dans la démo, le jeu de règle a 500 règles. Et supposons que pour l'élément d'un données 220 des règles prédisent un parti politique républicain, 250 des règles prévoir démocrate et 30 du règlement ne sont pas applicables. Le classificateur prédirait la personne associée aux données est un démocrate. En d'autres termes, la sortie est un consensus des prévisions de l'ensemble de règles.

Quelques commentaires

La motivation pour la technique de classification de consensus présentée dans cet article provenait d'un projet de recherche, que je travaillais sur il ya quelque temps. En particulier, j'ai essayé de prédire le sexe – homme ou femme – d'un utilisateur de messagerie instantanée basé sur des variables telles que la région de l'utilisateur, la catégorie d'âge de l'utilisateur et ainsi de suite. J'ai essayé tous les types d'approche de classification standard que je pouvais penser, en utilisant les outils existants de ML, mais aucune de mes approches ont pu générer un modèle de prévision efficace, même si mon sentiment était que les données contenaient suffisamment d'informations pour donner un signal.

J'ai remarqué qu'en utilisant la classification Naïve Bayes semblait être le meilleur de mes tentatives. Naive Bayes suppose que chaque variable prédictive est mathématiquement indépendant. Même si cette hypothèse n'est pas toujours vraie, Naive Bayes fonctionne parfois très bien. Pour mon problème, les variables prédictives étaient presque certainement liées d'une certaine façon, mais je ne savais pas quelles variables ont été associés. J'ai donc décidé d'utiliser des pièces de plusieurs techniques de ML pour créer l'approche décrite dans cet article. En fin de compte, j'ai été en mesure de créer un modèle de prédiction qui était beaucoup plus précis que n'importe quel modèle de norme technique.

Le problème de la démo est un problème de classification binaire, parce que la variable dépendante peut être démocrate ou républicain. En outre, toutes les variables explicatives sont variables catégoriques binaires car ils peuvent être soit oui ou non. Consensus classification peut traiter des problèmes de classification multinomiale (par exemple, démocrate, républicain, indépendant) et peut gérer des variables explicatives catégorielles disposant de plus de deux valeurs (par exemple, oui, non, en l'absence, se sont abstenus). Dans mes expériences, on voit mal comment classification de consensus efficace est lorsque présentent des problèmes où les variables prédictives sont numériques, comme avec l'âge et ont été mis en cellule en catégories (par exemple, jeunes, médium et vieux).

Combinant plusieurs des règles ou des modèles pour générer un résultat de classification est souvent appelé ensemble d'apprentissage de vocabulaire ML. L'idée de générer de nombreuses règles simples est utilisée dans les techniques de ML, et ceux-ci sont parfois dénommés renforcement des techniques. Permettez-moi de noter que, dans ma chronique série de tests, j'ai presque toujours présenter techniques ML qui ont une base solide de recherche. Cet article est une exception. La technique présentée ici n'a pas été étudiée formellement ou soumise à des recherches sérieuses. Plusieurs de mes collègues universitaires ont pris moi à partie pour avoir la galle colossale d'utiliser des techniques de ML personnalisés, non traditionnels, mais mon habitude quelque peu réponse de mauvaise humeur, c'est que je suis généralement plus préoccupé par l'obtention de résultats qu'avec l'établissement d'un théorème mathématique élégante. À mon avis, selon les techniques habituelles de ML est la meilleure façon d'approcher au départ un problème de ML, mais lorsque les techniques traditionnelles ne parviennent pas, créer une solution personnalisée peut être parfois étonnamment efficace.

---

Dr. James McCaffrey travaille pour Microsoft Research à Redmond, Washington  Il a travaillé sur plusieurs produits Microsoft, y compris Internet Explorer et Bing. Il peut être contacté à jammc@microsoft.com.

Remercie les experts techniques suivants Microsoft Research pour avoir relu cet article : Marciano Moreno Diaz Covarrubias, Delbert Murphy, David Raskino et Alisson Sol