ROC Convex Hull Algorithm
Jump to navigation
Jump to search
A ROC Convex Hull Algorithm is a Convex Hull Algorithm that constructs the convex hull of an ROC curve.
- AKA: ROC Convex Hull Computation Algorithm.
- Context:
- It can be implemented by ROC Convex Hull System to solve a ROC Convex Hull Task.
- Example(s):
- Counter-Example(s):
- an Andrew's Monotone Chain Algorithm,
- a Chan's Convex Hull Algorithm,
- a Divide and Conquer Convex Hull Algorithm,
- a Gift Wrapping Algorithm,
- a Graham Scan Algorithm,
- a Kirkpatrick-Seidel Convex Hull Algorithm.
- an Incremental Convex Hull Algorithm,
- a Potato Peeling Algorithm,
- a Quickhull Algorithm,
- a Simple Polygon Convex Hull Algorithm.
- See: Convex Hull, ROC Curve, Pareto Frontier, Area Under The Curve, Brier Score, Matthews Correlation Coefficient, Wilcoxon Signed-Rank Test, Gini Coefficient.
References
2017
- (Sammut & Webb, 2017) ⇒ Claude Sammut, and Geoffrey I. Webb. (2017). “ROC Convex Hull.” In: (Sammut & Webb, 2017). DOI: 10.1007/978-1-4899-7687-1_734
- QUOTE: The convex hull of an ROC curve is a geometric construction that selects the points on the curve that are optimal under some class and cost distribution. It is analogous to the Pareto front in multi-objective optimization. See ROC Analysis.
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Receiver_operating_characteristic#Area_under_the_curve Retrieved:2015-7-18.
- … It is also common to calculate the Area Under the ROC Convex Hull (ROC AUCH = ROCH AUC) as any point on the line segment between two prediction results can be achieved by randomly using one or other system with probabilities proportional to the relative length of the opposite component of the segment. Interestingly, it is also possible to invert concavities – just as in the figure the worse solution can be reflected to become a better solution; concavities can be reflected in any line segment, but this more extreme form of fusion is much more likely to overfit the data. ...
2005
- (Flach & Wu, 2005) ⇒ Peter A. Flach, and Shaomin Wu. (2005). “Repairing Concavities in ROC Curves.” In: Proceedings of IJCAI (IJCAI-2005)
- QUOTE: Figure 3 shows both the ROC curve for a probabilistic model evaluated on a small test set[1] and its convex hull (Provost & Fawcett, 2001).
|
- Four points of the ROC curve (point a, b, c and d) are located on the convex hull. Each of these points corresponds to a probability threshold, and thus each segment of the convex hull corresponds to a probability interval. For instance, the convex hull in Figure 3 has three segments corresponding to three disjoint probability intervals. (...) It is interesting to note that if this procedure is followed for all concavities, this corresponds to constructing the convex hull by discretising the probability scores. (...) by applying this algorithm to the model corresponding to threshold $c_2$, this point would be point-mirrored through the midpoint on line segment $c_d$ to the other side of the convex hull.
(...) The AUC of the repaired curve is therefore larger than both the AUC of the original curve and the AUC of its convex hull.
- Four points of the ROC curve (point a, b, c and d) are located on the convex hull. Each of these points corresponds to a probability threshold, and thus each segment of the convex hull corresponds to a probability interval. For instance, the convex hull in Figure 3 has three segments corresponding to three disjoint probability intervals. (...) It is interesting to note that if this procedure is followed for all concavities, this corresponds to constructing the convex hull by discretising the probability scores. (...) by applying this algorithm to the model corresponding to threshold $c_2$, this point would be point-mirrored through the midpoint on line segment $c_d$ to the other side of the convex hull.
- ↑ For illustration purposes, the test set contains only a few examples and the resolution of the ROC curve is low. In practical circumstances a step curve with much higher resolution is obtained.
2001
- (Provost & Fawcett, 2001) ⇒ Foster Provost, and Tom Fawcett. (2001). “Robust Classification for Imprecise Environments.” In: Machine Learning Journal, 42(3). doi:10.1023/A:1007601015854
- QUOTE: This uncertainty makes building robust classification systems problematic. We show that it is possible to build a hybrid classifier that will perform at least as well as the best available classifier for any target conditions. … The hybrid is based on a method for the comparison of classifier performance that is robust to imprecise class distributions and misclassification costs. The ROC convex hull (ROCCH) method combines techniques from ROC analysis, decision analysis and computational geometry, and adapts them to the particulars of analyzing learned classifiers. ...