Mesure des taux d'erreur entre les listes de classement

Question

J'essaie de mesurer l'accord entre deux systèmes de classification différents (l'un basé sur des algorithmes d'apprentissage automatique et l'autre basé sur la vérification au sol), et je Je cherche des commentaires de quelqu'un qui a mis en place un système similaire.

Le schéma de classification permet de classer chaque élément en plusieurs nœuds différents dans une taxonomie de catégorie, chaque classification portant un coefficient de pondération. Par exemple, si un élément peut être classé en quatre nœuds de taxonomie différentes, le résultat pourrait ressembler à ceci pour les classificateurs algorithmiques et rez-de-vérité:

   ALGO TRUTH 
CATEGORY A:  0.35  0.50 
CATEGORY B:  0.30  0.30 
CATEGORY C:  0.25  0.15 
CATEGORY D:  0.10  0.05 

Les poids toujours ajouter jusqu'à exactement 1.0, pour tous sélectionnés les nœuds de catégorie (dont il existe environ 200 dans la taxonomie de classification). Dans l'exemple ci-dessus, il est important de noter que les deux listes s'accordent sur l'ordre de classement (ABCD), elles doivent donc être considérées comme fortement en accord (même s'il y a des différences dans les poids assignés à chaque classe). . catégorie en revanche, dans l'exemple suivant, les deux classifications sont en désaccord avec la question de rang ordre.

   ALGO TRUTH 
CATEGORY A:  0.40  0.10 
CATEGORY B:  0.35  0.15 
CATEGORY C:  0.15  0.35 
CATEGORY D:  0.10  0.40 

Ainsi, un résultat comme celui-ci devrait obtenir un score très faible

un dernier exemple illustre un cas courant où la vérité au sol générée par l'utilisateur contient des valeurs de poids en double:

   ALGO TRUTH 
CATEGORY A:  0.40  0.50 
CATEGORY B:  0.35  0.50 
CATEGORY C:  0.15  0.00 
CATEGORY D:  0.10  0.00 

Il est donc important que l'algorithme permet des listes sans ordre de classement parfait (puisque la vérité du terrain pourrait être interprété valablement comme ABCD, ABCD, BACD ou BADC)

Stuff J'ai essayé jusqu'à présent:

• Root Mean Squared Error (RMSE): Très problématique. Il ne tient pas compte de l'accord de classement, ce qui signifie que les désaccords bruts entre les catégories en haut de la liste sont balayés sous le tapis par un accord sur les catégories au bas de la liste.

• Spearman's Rank Correlation: Bien qu'il prenne en compte les différences de rang, il donne un poids égal aux accords de classement en haut de la liste et ceux en bas de la liste. Je ne me soucie pas vraiment des écarts de bas niveau, tant que les écarts de haut niveau contribuent à la mesure de l'erreur. Il ne gère pas non plus les cas où plusieurs catégories peuvent avoir des rangs de liens.

• Kendall Tau Rank Correlation Coefficient: A les mêmes propriétés et limitations de base que la corrélation de rang de Spearman, autant que je sache.

J'ai pensé à rouler mes propres mesures ad hoc, mais je ne suis pas mathématicien, donc je serais méfiant si ma petite mesure apporterait une valeur beaucoup plus rigoureuse. S'il y a une méthodologie standard pour ce genre de chose, je préfère l'utiliser.

Des idées?

Answer 1

D'accord, j'ai décidé de mettre en œuvre un RMSE pondéré. Il ne prend pas directement en compte les relations de classement, mais le système de pondération met automatiquement en évidence ces entrées en haut de la liste.

Juste pour examen (pour ceux qui ne connaissent pas RMSE), l'équation se présente comme suit, en supposant deux classificateurs différents A et B, dont les résultats figurent dans un tableau du même nom:

RMSE Equation http://benjismith.net/images/rmse.png

en java la mise en œuvre ressemble à ceci:

double[] A = getAFromSomewhere(); 
double[] B = getBFromSomewhere(); 

// Assumes that A and B have the same length. If not, your classifier is broken. 
int count = A.length; 

double sumSquaredError = 0; 
for (int i = 0; i < count; i++) { 
    double aElement = A[i]; 
    double bElement = B[i]; 
    double error = aElement - bElement; 
    double squaredError = error * error; 
    sumSquaredError += squaredError; 
} 
double meanSquaredError = sumSquaredError/count; 
double rootMeanSquaredError = Math.sqrt(meanSquaredError); 

C'est le point de départ pour ma mise en œuvre modifiée. Je devais mettre au point un système de pondération qui représente l'ampleur combinée des deux valeurs (des deux classificateurs). Je vais donc multiplier chaque valeur d'erreur au carré par SQRT(Ai^2 + Bi^2), qui est une fonction de distance euclidienne simple. Bien sûr, puisque j'utilise une erreur pondérée dans le numérateur, je dois également utiliser la somme de tous les poids dans le dénominateur, de sorte que mes résultats sont renormalisés dans la gamme (0.0, 1.0).

J'appelle la nouvelle mesure "RMWSE", car il est un Root Mean pondéré Erreur Squared. Voici ce que la nouvelle équation ressemble:

RMWSE Equation http://benjismith.net/images/rmwse.png

Et voici à quoi il ressemble en java:

double[] A = getAFromSomewhere(); 
double[] B = getBFromSomewhere(); 

// Assumes that A and B have the same length. If not, your classifier is broken. 
int count = A.length; 

double sumWeightedSquaredError = 0; 
double sumWeights = 0; 
for (int i = 0; i < count; i++) { 
    double aElement = A[i]; 
    double bElement = B[i]; 
    double error = aElement - bElement; 
    double squaredError = error * error; 
    double weight = Math.sqrt((aElement * aElement) + (bElement * bElement)); 
    double weightedSquaredError = weight * squaredError; 
    sumWeightedSquaredError += weightedSquaredError; 
    sumWeights += weight; 
} 
double meanWeightedSquaredError = sumWeightedSquaredError/sumWeights; 
double rootMeanWeightedSquaredError = Math.sqrt(meanWeightedSquaredError); 

Pour vous donner une idée de la façon dont ce poids fonctionne dans la pratique, disons mes deux les classificateurs produisent les valeurs 0.95 et 0.85 pour certaines catégories. L'erreur entre ces deux valeurs est 0.10, mais le poids est 1.2748 (que je suis arrivé à l'aide de SQRT(0.95^2 + 0.85^2)). L'erreur pondérée est 0.12748.

De même, si les classificateurs produisent 0.45 et 0.35 pour une autre catégorie, l'erreur est encore juste 0.10, mais le poids est seulement 0.5701, et l'erreur pondérée est donc que 0.05701. Donc toute catégorie avec des valeurs élevées des deux classificateurs sera plus fortement pondérée que les catégories avec une valeur élevée à partir d'un seul classificateur, ou des catégories avec des valeurs faibles des deux classificateurs.Cela fonctionne mieux lorsque mes valeurs de classification sont renormalisées de sorte que les valeurs maximales dans A et B sont 1.0, et toutes les autres valeurs sont augmentées proportionnellement. Par conséquent, les dimensions ne se résument plus à 1.0 pour un classificateur donné, mais cela n'a pas vraiment d'importance, puisque je n'exploitais pas cette propriété pour quelque chose d'utile.

Pour l'anecdote, je suis assez satisfait des résultats que cela donne dans mon jeu de données, mais si quelqu'un a d'autres idées d'amélioration, je serais totalement ouvert aux suggestions!

Answer 2

Je ne pense pas que vous ayez à vous soucier de la rigueur dans cette mesure. Si vous voulez accorder plus de poids à certains types d'accords, c'est parfaitement légitime.Par exemple, calculez uniquement Spearman pour les catégories k supérieures. Je pense que vous devriez obtenir des réponses parfaitement légitimes.

Vous pouvez également effectuer une transformation z etc. pour tout mapper à [0,1] tout en préservant ce que vous considérez comme les pièces "importantes" de votre ensemble de données (variance, différence, etc.). Vous pouvez alors prendre avantage du grand nombre de fonctions de test d'hypothèses disponibles.

(Comme une note de côté, vous pouvez modifier de Spearman pour tenir compte des liens. Voir Wikipedia.)