A Survey of Evaluation and Design for AUC Based Classifier
WANG Yun-Yun, CHEN Song-Can
Department of Computer Science and Technology, College of Information Science and Technology Nanjing University of Aeronautics and Astronautics, Nanjing 210016
Abstract Though as a common performance evaluating index for classification algorithms, accuracy (or total misclassification error) has several deficiencies, such as the sensitivity to class prior distribution and misclassification costs, and the ignorance of the posterior probability and ranking information obtained by classification algorithms. While the area under the receiver operation characteristic (ROC) curve measures the classification performance across the entire range of class prior distribution and misclassification costs, as well as the probability and ranking performance. Thus, it attracts much attention in classification learning and evokes a lot of researches. In this paper, a relative comprehensive survey for these researches is presented, including the advantages of AUC as a performance evaluating index, the design of algorithms based on AUC, the relationship between the accuracy-maximizing and AUC-maximizing algorithms and the deficiencies of AUC along with its variants.
[1] Duda R O, Hart P E, Stork D G. Pattern Classification. 2nd Edition. New York, USA: Wiley, 2001 [2] Bradley A P. The Use of the Area under the ROC Curve in the Evaluation of Machine Learning Algorithms. Pattern Recognition, 1997, 30(7): 1145-1159 [3] Provost F T, Fawcett T, Kohavi R. The Case against Accuracy Estimation for Comparing Induction Algorithms // Proc of the 15th International Conference on Machine Learning. Madison, USA, 1998: 445-453 [4] Provost F, Fawcett T. Robust Classification for Imprecise Environments. Machine Learning, 2001, 42(3): 203-231 [5] Ling C X, Huang Jin, Zhang H. AUC: A Better Measure than Accuracy in Comparing Learning Algorithms // Proc of the 16th Canadian Society for Computational Studies of Intelligence Conference on Advances in Artificial Intelligence. Halifax, Canada, 2003: 329-341 [6] Ling C X, Huang Jin, Zhang H. AUC: A Statistically Consistent and More Discriminating Measure Than Accuracy // Proc of the 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 519-526 [7] Maloof M A. Learning When Data Sets Are Imbalanced and When Costs Are Unequal and Unknown // Proc of the Workshop on Learning from Imbalanced Data Sets II. Washington, USA, 2003: 96-105 [8] Akbani R, Kwek S, Japkowicz N. Applying Support Vector Machines to Imbalance Data Sets // Proc of the 15th European Conference on Machine Learning. Pisa, Italy, 2004: 39-50 [9] Provost F, Fawcett T. Analysis and Visualization of Classifier Performance: Comparison under Imprecise Class and Cost // Proc of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose, USA, 1997: 43-48 [10] Huang Jin, Ling C X. Using AUC and Accuracy in Evaluating Learning Algorithms. IEEE Trans on Knowledge and Data Engineering, 2005, 17(3): 299-310 [11] Yan Lian, Dodier R, Mozer M C, et al. Optimizing Classifier Performance via the Wilcoxon-Mann-Whitney Statistic // Proc of the 20th International Conference on Machine Learning. Washington, USA, 2003: 848-855 [12] Freund Y, Iyer R, Schapire R E, et al. An Efficient Boosting Algorithm for Combining Preferences // Proc of the International Conference on Machine Learning. Madison, USA, 1998: 170-178 [13] Herschtal A, Raskutti B. Optimizing Area under the ROC Curve Using Gradient Descent // Proc of the 21st International Conference on Machine Learning. Banff, Canada, 2004: 49-56 [14] Rakotomamonjy A. Optimizing AUC with Support Vector Machine (SVM) // Proc of the European Conference on Artificial Intelligence Workshop on ROC Analysis and Artificial Intelligence. Valencia, Spain, 2004: 71-80 [15] Rakotomamonjy A. Quadratic Programming for AUC Optimization // Proc of the 2nd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences. Metz, France, 2004: 603-610 [16] Fawcett T. An Introduction to ROC Analysis. Pattern Recognition Letters, 2006, 27(8): 861-874 [17] Rosset S. Model Selection via the AUC // Proc of the 21st International Conference on Machine Learning. Banff, Canada, 2004: 89-97 [18] Wu S, Flach P. A Scored AUC Metric for Classifier Evaluation and Selection // Proc of the ICML Workshop on ROC Analysis in Machine Learning. Bonn, Germany, 2005: 247-262 [19] Hand D J, Till R J. A Simple Generalization of the Area under the ROC Curve for Multiple-Class Classification Problems. Machine Learning, 2001, 45(2): 171-186 [20] Calders T, Jaroszewicz S. Efficient AUC Optimization for Classification // Proc of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases. Warsaw, Poland, 2007: 42-53 [21] Burges C, Shaked T, Renshaw E, et al. Learning to Rank Using Gradient Descent // Proc of the 22nd International Conference on Machine Learning. Bonn, Germany, 2005: 89-96 [22] Freund Y, Iyer R, Schapire R E, et al. An Efficient Boosting Algorithm for Combining Preferences. Journal of Machine Learning Research, 2003, 4: 933-969 [23] Cristianini N, Shawe-Taylor J. An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods. Cambridge, UK: Cambridge University Press, 2000 [24] Lin Yi, Lee Y, Wahba G. Support Vector Machines for Classification in Nonstandard Situations. Machine Learning, 2002, 46(1/2/3): 191-202 [25] Fumera G, Roli F. Cost-Sensitive Learning in Support Vector Machine // Proc of the Workshop on Machine Learning, Methods and Applications. Siena, Italy, 2002: 147-167 [26] Brefeld U, Scheffer T. AUC Maximizing Support Vector Learning // Proc of the ICML Workshop on ROC Analysis in Machine Learning. Bonn, Germany, 2005: 377-384 [27] Joachims T. Optimizing Search Engines Using Clickthrough Data // Proc of the ACM Conference on Knowledge Discovery and Data Mining. Edmonton. Canada, 2002: 133-142 [28] Wang Yunyun, Chen Songcan, Xue Hui. Structure-Embedded AUC-SVM. International Journal of Pattern Recognition and Artificial Intelligence, 2010, 24(5): 667-690 [29] Fung G, Rosales R O, Krishnapuram B. Learning Rankings via Convex Hull Separation // Proc of the 19th Annual Conference on Neural Information Processing Systems. Vancouver, Canada, 2005: 395-402 [30] Yan Rong, Hauptmann A G. Efficient Margin-Based Rank Learning Algorithms for Information Retrieval // Proc of the International Conference on Image and Video Retrieval. Tempe, USA, 2006: 113-122 [31] Tax D M J, Veenman C J. Tuning the Hyperparameter of an AUC-Optimized Classifier // Proc of the 17th Belgium-Netherlands Conference on Artificial Intelligence. Brussels, Belgium, 2005: 224-231 [32] Tax D M J, Duin R P W. Linear Model Combining by Optimizing the Area under the ROC Curve // Proc of the 18th International Conference on Pattern Recognition. Hongkong, China, 2006: 119-122 [33] Ataman K, Street W N, Zhang Y. Learning to Rank by Maximizing AUC with Linear Programming // Proc of the IEEE International Joint Conference on Neural Networks. Vancouver. Canada, 2006: 123-129 [34] Ataman K. Learning to Rank by Maximizing the AUC with Linear Programming for Problems with Binary Output. Ph.D Dissertation. Iowa, USA: University of Iowa. Department of Management Sciences, 2007 [35] Yu H, Kim Y, Hwang S. RV-SVM: An Efficient Method for Learning Ranking SVM // Proc of the 13th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Bangkok, Thailand, 2009: 426-438 [36] Ferri C, Flach P, Hernández-Orallo J, et al. Modifying ROC Curves to Incorporate Predicted Probabilities // Proc of the ICML Workshop on ROC Analysis in Machine Learning. Bonn, Germany, 2005: 30-40 [37] Raykar V C, Duraiswami R, Krishnapuram B. A Fast Algorithm for Learning a Ranking Function from Large Scale Data Sets. IEEE Trans on Pattern Analysis and Machine Intelligence, 2008, 30(7): 1158-1170 [38] Raykar V C, Duraiswami R, Krishnapuram B. A Fast Algorithm for Learning Large Scale Preference Relations // Proc of the 11th International Conference on Artificial Intelligence and Statistics. San Juan, Puerto Rico, 2007: 385-392 [39] Pahikkala T, Airola A, Suominen H, et al. Efficient AUC Maximization with Regularized Least-Squares // Proc of the 10th Scandinavian Conference on Artificial Intelligence. Stockholm City, Sweden, 2008: 12-19 [40] Pahikkala T, Tsivtsivadze E, Airola A, et al. An Efficient Algorithm for Learning to Rank from Preference Graphs. Machine Learning, 2009, 75(1): 129-165 [41] Toh K A, Kim J, Lee S. Maximizing Area under ROC Curve for Biometric Scores Fusion. Pattern Recognition, 2008, 41(11): 3373-3392 [42] Rudin C, Schapire R E. Margin-Based Ranking and an Equivalence between AdaBoost and RankBoost. Journal of Machine Learning Research, 2008, 10: 2193-2232 [43] Rudin C, Cortes C, Mohri M, et al. Margin-Based Ranking Meets Boosting in the Middle // Proc of the 18th Annual Conference on Computational Learning Theory. Bertinoro, Italy, 2005: 63-78 [44] Moribe J I, Hatano K, Takimoto E, et al. Smooth Boosting for Margin-Based Ranking // Proc of the 19th International Conference on Algorithmic Learning Theory. Budapest, Hungary, 2008: 227-239 [45] Pelckmans K, Suykens J A K. LPRankBoost and Column Generation // Proc of the International Conference/Euro Mini Conference on Continuous Optimization and Knowledge-Based Technologies. Neringa, Lithuania, 2008: 165-169 [46] Merler M, Yan R, Smith J R. Imbalanced RankBoost for Efficiently Ranking Large-Scale Image/Video Collections // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Miami, USA, 2009: 2607-2614 [47] Warmuth M, Glocer K, Rtsch G. Boosting Algorithms for Maximizing the Soft Margin // Proc of the 22nd Annual Conference on Neural Information Processing Systems. Vancouver, Canada, 2008: 1441-1448 [48] Tsai M F, Liu T Y, Qin Tao, et al. FRank: A Ranking Method with Fidelity Loss // Proc of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Amsterdam, Netherlands, 2007: 383-390 [49] Pahikkala T, Tsivtsivadze E, Airola A, et al. Learning to Rank with Pairwise Regularized Least-Squares // Proc of the SIGIR Workshop on Learning to Rank for Information Retrieval. Amsterdam, Netherlands, 2007: 27-33 [50] Tong Zong. Statistical Analysis of Some Multi-Category Large Margin Classification Methods. Journal of Machine Learning Research, 2004, 5: 1225-1251 [51] Rosasco L, Vito E D, Caponnetto A, et al. Are Loss Function All the Same? Neural Computation, 2004, 16(5): 1063-1076 [52] Nguyen X, Wainwright M J, Jordan M I. On Surrogate Loss Functions and f-Divergences. The Annals of Statistics, 2009, 37(2): 876-904 [53] Steck H. Hinge Rank Loss and the Area under the ROC Curve // Proc of the 18th European Conference on Machine Learning. Warsaw, Poland, 2007: 347-358 [54] Huang Jin, Ling C X. Constructing New and Better Evaluation Measures for Machine Learning // Proc of the 20th International Joint Conference on Artificial Intelligence. Hyderabad, India, 2007: 859-864 [55] Vanderlooy S, Hüllermeier E. A Critical Analysis of Variants of the AUC. Machine Learning, 2008, 72(3): 247-262 [56] Hand D J. Measuring Classifier Performance: A Coherent Alternative to the Area under the ROC Curve. Machine Learning, 2009, 77(1): 103-123
2011, Vol. 24 
