Convex Hull-Based Multiobjective Genetic Programming for Maximizing Receiver Operating Characteristic Performance

The receiver operating characteristic (ROC) is commonly used to analyze the performance of classifiers in data mining. An important topic in ROC analysis is the ROC convex hull (ROCCH), which is the least convex majorant (LCM) of the empirical ROC curve and covers potential optima for a given set of classifiers. ROCCH maximization problems have been taken as multiobjective optimization problem (MOPs) in some previous work. However, the special characteristics of ROCCH maximization problem makes it different from traditional MOPs. In this paper, the difference will be discussed in detail and a new convex hull-based multiobjective genetic programming (CH-MOGP) is proposed to solve ROCCH maximization problems. Specifically, convex hull-based without redundancy sorting (CWR-sorting) is introduced, which is an indicator-based selection scheme that aims to maximize the area under the convex hull. A novel selection procedure is also proposed based on the proposed sorting scheme. It is hypothesized that by using a tailored indicator-based selection, CH-MOGP becomes more efficient for ROC convex hull approximation than algorithms that compute all Pareto optimal points. Empirical studies are conducted to compare CH-MOGP to both existing machine learning approaches and multiobjective genetic programming (MOGP) methods with classical selection schemes. Experimental results show that CH-MOGP outperforms the other approaches significantly.