J’ai trouv\u00e9 3 m\u00e9thodes pour calculer une\u00a0AUC:<\/p>\n
- \n
- Aire des trap\u00e9zo\u00efdes: il faut commencer par transformer le vecteur de scores en un vecteur de coordonn\u00e9es (qui repr\u00e9sente la courbe ROC) et calculer l’aire de chaque trap\u00e9zo\u00efdes.<\/li>\n
- Mesure de concordance: il faut comparer toutes les paires possibles et de compter le nombre de fois o\u00f9 le Score(A) > Score(B).<\/li>\n
- \u00c0 partir du test Mann Whitney: on utilise le calcul de la statistique\u00a0U.<\/em><\/li>\n<\/ol>\n
Maintenant, je vous propose d’identifier la m\u00e9thode la plus rapide en estimant le nombre d’op\u00e9rations n\u00e9cessaires pour chaque strat\u00e9gie. Globalement, si on a besoin de plus d’op\u00e9rations, alors le calcul devrait \u00eatre plus long. Estimer le nombre d’op\u00e9rations est un sujet vaste appel\u00e9 la\u00a0complexit\u00e9<\/a>, mais ici je propose\u00a0une approche simplifi\u00e9:<\/p>\n
- \n
- La mesure de concordance\u00a0n\u00e9cessite\u00a0n*m comparaisons, avec n (resp. m) le nombre d’\u00e9chantillons A (resp. B). Cette m\u00e9thode fait\u00a0partie des algorithmes dit quadratiques, le nombre d’op\u00e9rations augmente de fa\u00e7on exponentielle avec le nombre d’\u00e9chantillons. Il est possible de r\u00e9duire le nombre d’op\u00e9rations en comparant seulement un sous-ensemble de paires (n*m*p, with 0<p<1). Chaque paire doit \u00eatre choisie al\u00e9atoirement avec remise. Attention cette astuce ne fait qu’\u00e9changer de la pr\u00e9cision (au niveau du calcul de l’AUC) contre du temps, et trouver la \u00ab\u00a0taille optimale\u00a0\u00bb\u00a0du sous-ensemble n’est pas forc\u00e9ment \u00e9vident.<\/li>\n
- u-test<\/a>: Pour calculer la statistique U<\/em>, nous avons principalement besoin de calculer le rang de chaque \u00e9chantillon en fonction de son score, ce qui peut \u00eatre fait avec un algorithme de tri<\/a>\u00a0en\u00a0N*log(N) op\u00e9rations (avec N=n+m).<\/li>\n
- Calcul de l’aire commence par trier le vecteur pour transformer les scores en coordonn\u00e9es. Il est ensuite possible de calculer et de faire la somme de l’aire des N-1 trap\u00e9zo\u00efdes<\/a>. Ceci n\u00e9cessite N*log(N) + N op\u00e9rations.<\/li>\n<\/ul>\n
Ainsi, c’est le U-test qui calcule l’AUC avec le moins d’op\u00e9rations et qui devrait \u00eatre la m\u00e9thode la plus rapide. Pour v\u00e9rifier ce r\u00e9sultat de fa\u00e7on concr\u00e8te, j’ai impl\u00e9ment\u00e9 toutes ces m\u00e9thodes en python3 et j’ai obtenu la figure ci-dessous.<\/p>\n
![\"time_auc\"](\"https:\/\/bioinfo.iric.ca\/wpbioinfo\/wp-content\/uploads\/2016\/08\/time_auc-2-300x212.png\")
<\/a><\/p>\n\u00ab\u00a0concordance_15p\u00a0\u00bb (resp. \u00ab\u00a0concordance_5p\u00a0\u00bb) repr\u00e9sente la m\u00e9thode \u00ab\u00a0concordance\u00a0\u00bb appliqu\u00e9e \u00e0 un sous-ensemble de paires avec p=0.15 (resp. 0.05).<\/p>\n
Comme on peut le voir:<\/p>\n
- \n
- Mann Whitney\/u-test est bien la m\u00e9thode la plus rapide, si on n’a pas besoin des coordonn\u00e9es pour afficher la courbe ROC.<\/li>\n
- Le temps de calcul de l’aire progresse de mani\u00e8re similaire \u00e0 celui du u-test (les 2 m\u00e9thodes sont dans la cat\u00e9gories des algorithmes pseudo lin\u00e9aires). Comme on pouvait s’y attendre, il est toutefois 2 fois plus lent que le u-test: N*log(N) + N = 2*\u00a0<\/strong>N*(log(N)+1).<\/li>\n
- Comme pour le nombre d’op\u00e9rations, le temps de calcul de la concordance augmente de fa\u00e7on exponentielle avec le nombre d’\u00e9chantillons.<\/li>\n
- Le calcul de la concordance sur un sous-ensemble est toujours plus lent que le calcul du\u00a0u-test. Je n’ai pas mesur\u00e9 la pr\u00e9cision des estimations de l’AUC, mais je ne vois aucun avantage \u00e0 utiliser cette m\u00e9thode. En fait, je ne comprends pas pourquoi cette m\u00e9thode est si souvent cit\u00e9e contrairement au u-test.<\/li>\n<\/ul>\n
Ci-dessous vous trouverez l’impl\u00e9mentation du \u00ab\u00a0u-test\u00a0\u00bb en R et python. Les impl\u00e9mentations de toutes ces m\u00e9thodes sont d’ailleurs disponibles sur mon\u00a0git<\/a>.<\/p>\n
- Calcul de l’aire commence par trier le vecteur pour transformer les scores en coordonn\u00e9es. Il est ensuite possible de calculer et de faire la somme de l’aire des N-1 trap\u00e9zo\u00efdes<\/a>. Ceci n\u00e9cessite N*log(N) + N op\u00e9rations.<\/li>\n<\/ul>\n