Robust Classification for Imprecise Environments.
In real-world environments it usually is difficult to specify target operating conditions precisely, for example, target misclassification costs. 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. In some cases, the performance of the hybrid actually can surpass that of the best known classifier. This robust performance extends across a wide variety of comparison frameworks, including the optimization of metrics such as accuracy, expected cost, lift, precision, recall, and workforce utilization. The hybrid also is efficient to build, to store, and to update. 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. The method is efficient and incremental, minimizes the management of classifier performance data, and allows for clear visual comparisons and sensitivity analyses. Finally, we point to empirical evidence that a robust hybrid classifier indeed is needed for many real-world problems.
Introduction
Traditionally, classification systems have been built by experimenting with many different classifiers, comparing
their performance and choosing the best. Experimenting with different induction algorithms, parameter settings,
and training regimes yields a large number of classifiers to be evaluated and compared. Unfortunately, comparison
is often difficult in real-world environments because key parameters of the target environment are not known. For
example, the optimal cost/benefit tradeoffs and the target class priors seldom are known precisely, and often are
subject to change. For example, in fraud detection we cannot ignore either the cost or class distribution, nor can
we assume that our distribution specifications are precise or static (Fawcett & Provost, 1997). We need a method
for the management, comparison, and application of multiple classifiers that is robust to imprecise and changing
environments.
We describe the ROC convex hull (rocch) method, which combines techniques from ROC analysis, decision
analysis and computational geometry. The ROC convex hull decouples classifier performance from specific class
and cost distributions, and may be used to specify the subset of methods that are potentially optimal under any
combination of cost assumptions and class distribution assumptions. The rocch method is efficient, so it facilitates
the comparison of a large number of classifiers. It minimizes the management of classifier performance data because
it can specify exactly those classifiers that are potentially optimal, and it is incremental, easily incorporating new
and varied classifiers.
We demonstrate that it is possible and desirable to avoid complete commitment to a single best classifier during
system construction. Instead, the rocch can be used to build from the available classifiers a hybrid classification
system that will perform best under any target cost/benefit and class distributions. Target conditions can then be
specified at run time. Moreover, in cases where precise information is still unavailable when the system is run (or if
the conditions change dynamically during operation), the hybrid system can be tuned easily (and optimally) based
on feedback from its actual performance.
The paper is structured as follows. First we sketch briefly the traditional approach to building such systems,
in order to demonstrate that it is brittle under the types of imprecision common in real-world problems. We then
introduce and describe the rocch and its properties for comparing and visualizing classifier performance in imprecise
environments. In the following sections we formalize the notion of a robust classification system, and show that the
rocch is an elegant method for constructing one automatically. The solution is elegant because the resulting hybrid
classifier is robust for a wide variety of problem formulations, including the optimization of metrics such as accuracy,
expected cost, lift, precision, recall, and workforce utilization, and it is efficient to build, store and update. We then
show that the hybrid can actually do better than the best known classifier in some situations. Finally, by citing
results from empirical studies, we provide evidence that this type of system is needed.
1.1 An example
A systems-building team wants to create a system that will take a large number of instances and identify those for
which an action should be taken. The instances could be potential cases of fraudulent account behavior, of faulty
equipment, of responsive customers, of interesting science, etc. We consider problems for which the best method for
classifying or ranking instances is not well defined, so the system builders may consider machine learning methods,
neural networks, case-based systems, and hand-crafted knowledge bases as potential classification models. Ignoring
for the moment issues of efficiency, the foremost question facing the system builders is: which of the available models
performs "best" at classification?
Traditionally, an experimental approach has been taken to answer this question, because the distribution of
instances can be sampled if it is not known a priori. The standard approach is to estimate the error rate of each
model statistically and then to choose the model with the lowest error rate. This strategy is common in machine
learning, pattern recognition, data mining, expert systems and medical diagnosis. In some cases, other measures such
as cost or benefit are used as well. Applied statistics provides methods such as cross-validation and the bootstrap
for estimating model error rates and recent studies have compared the effectiveness of different methods (Salzberg,
1997; Kohavi, 1995; Dietterich, 1998).
Unfortunately, this experimental approach is brittle under two types of imprecision that are common in real-world
environments. Specifically, costs and benefits usually are not known precisely, and target class distributions often
are known only approximately as well. This observation has been made by many authors (Bradley, 1997; Catlett,
1995), and is in fact the concern of a large subfield of decision analysis (Weinstein & Fineberg, 1980). Imprecision
also arises because the environment may change between the time the system is conceived and the time it is used,
and even as it is used. For example, levels of fraud and levels of customer responsiveness change continually over
time and from place to place.
1.2 Basic terminology
In this paper we address two-class problems. Formally, each instance I is mapped to one element of the set fp; ng of
(correct) positive and negative classes. A classification model (or classifier) is a mapping from instances to predicted
classes. Some classification models produce a continuous output (e.g., an estimate of an instance's class membership
probability) to which different thresholds may be applied to predict class membership. To distinguish between the
actual class and the predicted class of an instance, we will use the labels fY; Ng for the classifications produced by a
model. For our discussion, let c(classification; class) be a two-place error cost function where c(Y; n) is the cost of a
false positive error and c(N; p) is the cost of a false negative error. 1 We represent class distributions by the classes'
prior probabilities p(p) and
The true positive rate, or hit rate, of a classifier is:
positives correctly classified
total positives
The false positive rate, or false alarm rate, of a classifier is:
negatives incorrectly classified
total negatives
The traditional experimental approach is brittle because it chooses one model as "best" with respect to a specific
set of cost functions and class distribution. If the target conditions change, this system may no longer perform
optimally, or even acceptably. As an example, assume that we have a maximum false positive rate FP , that must
not be exceeded. We want to find the classifier with the highest possible true positive rate, TP , that does not exceed
the FP limit. This is the Neyman-Pearson decision criterion (Egan, 1975). Three classifiers, under three such FP
limits, are shown in Figure 1. A different classifier is best for each FP limit; any system built with a single "best"
classifier is brittle if the FP requirement can change.
1 For this paper, consider error costs to include benefits not realized.
True
positive
rate
False positive rates

Figure

1: Three classifiers under three different Neyman-Pearson decision criteria
Evaluating and visualizing classifier performance
2.1 Classifier comparison: decision analysis and ROC analysis
Most prior work on building classifiers uses classification accuracy (or, equivalently, undifferentiated error rate) as
the primary evaluation metric. The use of accuracy assumes that the class priors in the target environment will be
constant and relatively balanced. In the real world this is rarely the case. Classifiers are often used to sift through
a large population of normal or uninteresting entities in order to find a relatively small number of unusual ones;
for example, looking for defrauded accounts among a large population of customers, screening medical tests for rare
diseases, and checking an assembly line for defective parts. Because the unusual or interesting class is rare among
the general population, the class distribution is very skewed (Ezawa, Singh, & Norton, 1996; Fawcett & Provost,
1997; Kubat, Holte, & Matwin, 1998; Saitta & Neri, 1998).
As the class distribution becomes more skewed, evaluation based on accuracy breaks down. Consider a domain
where the classes appear in a 999:1 ratio. A simple rule-always classify as the maximum likelihood class-gives
a 99.9% accuracy. This performance may be quite difficult for an induction algorithm to beat, though the simple
rule presumably is unacceptable if a non-trivial solution is sought. Skews of 10 2 are common in fraud detection and
reported in other applications (Clearwater & Stern, 1991).
Evaluation by classification accuracy also tacitly assumes equal In the real world
this is rarely the case because classifications tacitly involve actions, which have consequences. Actions can be as
diverse as cancelling a credit card account, moving a control surface on an airplane, or informing a patient of a cancer
diagnosis. These actions have consequences, sometimes grave, and performing an incorrect action can be very costly.
Rarely are the costs of mistakes equivalent. In mushroom classification, for example, judging a poisonous mushroom
to be edible is far worse than judging an edible mushroom to be poisonous. Indeed, it is hard to imagine a domain
in which a learning system may be indifferent to whether it makes a false positive or a false negative error. In such
cases, accuracy maximization should be replaced with cost minimization.
The problems of unequal error costs and uneven class distributions are related. It has been suggested that, for
learning, high-cost instances can be compensated for by increasing their prevalence in an instance set (Breiman,
Friedman, Olshen, & Stone, 1984). Unfortunately, little work has been published on either problem. There exist
several dozen articles in which techniques for cost-sensitive learning are suggested (Turney, 1996), but little is done
to evaluate and compare them (the article of Pazzani et al. (1994) being the exception). The literature provides even
less guidance in situations where distributions are imprecise or can change.
If a model produces an estimate of p(pjI), the posterior probability of an instance's class membership, as most
machine-learned models can, decision analysis gives us a way to produce cost-sensitive classifications (Weinstein &
Fineberg, 1980). Classifier error frequencies can be used to approximate probabilities (Pazzani et al., 1994). For an
instance I , the decision to emit a positive classification from a particular classifier is:
Regardless of whether a classifier produces probabilistic or binary classifications, its normalized cost on a test set
can be evaluated empirically as:
Most published work on cost-sensitive classification uses an equation such as this to rank classifiers. Given a set of
classifiers, a set of examples, and a precise cost function, each classifier's cost is computed and the minimum-cost
classifier is chosen. However, as discussed above, such analyses assume that the distributions are precise and static.
True
positive
rate
False positive rate
Classifier 3

Figure

2: ROC graph of three classifiers
More general comparisons can be made with Receiver Operating Characteristic (ROC) analysis, a classic methodology
from signal detection theory that is now common in medical diagnosis and has recently begun to be used more
generally in AI classifier work (Egan, 1975; Beck & Schultz, 1986; Swets, 1988). ROC graphs depict tradeoffs between
hit rate and false alarm rate.
We use the term ROC space to denote the coordinate system used for visualizing classifier performance. In ROC
space, TP is represented on the Y axis and FP is represented on the X axis. Each classifier is represented by the
point in ROC space corresponding to its For models that produce a continuous output, e.g., posterior
probabilities, TP and FP vary together as a threshold on the output is varied between its extremes (each threshold
defines a classifier); the resulting curve is called the ROC curve. An ROC curve illustrates the error tradeoffs available
with a given model. Figure 2 shows a graph of three typical ROC curves; in fact, these are the complete ROC curves
of the classifiers shown in Figure 1.
For orientation, several points on an ROC graph should be noted. The lower left point (0; 0) represents the
strategy of never alarming, the upper right point (1; 1) represents the strategy of always alarming, the point (0; 1)
represents perfect classification, and the line represents the strategy of randomly guessing the
class. Informally, one point in ROC space is better than another if it is to the northwest (TP is higher, FP is lower,
False Positive rate
True
Positive
rate
A

Figure

3: An ROC graph of four classifiers
or both). An ROC graph allows an informal visual comparison of a set of classifiers. In Figure 3, curve A is better
than curve D because it dominates in all points.
ROC graphs illustrate the behavior of a classifier without regard to class distribution or error cost, and so they
decouple classification performance from these factors. Unfortunately, while an ROC graph is a valuable visualization
technique, it does a poor job of aiding the choice of classifiers. Only when one classifier clearly dominates another
over the entire performance space can it be declared better. Consider the classifiers shown in Figure 3. Which is
best? The answer depends upon the performance requirements, i.e., the error costs and class distributions in effect
when the classifiers are to be used. Take a moment to convince yourself which classifiers in Figure 3 are optimal for
what conditions.
2.2 The ROC Convex Hull method
In this section we combine decision analysis with ROC analysis and adapt them for comparing the performance of a
set of learned classifiers. The method is based on three high-level principles. First, ROC space is used to separate
classification performance from class and cost distribution information. Second, decision-analytic information is
projected onto the ROC space. Third, the convex hull in ROC space is used to identify the subset of methods that
are potentially optimal.
2.2.1 Iso-performance lines
By separating classification performance from class and cost distribution assumptions, the decision goal can be
projected onto ROC space for a neat visualization. Specifically, the expected cost of applying the classifier represented
by a point space is:
Therefore, two points,
have the same performance if
c(N; p)p(p)
This equation defines the slope of an iso-performance line, i.e., all classifiers corresponding to points on the line
have the same expected cost. Each set of class and cost distributions defines a family of iso-performance lines.
Lines "more northwest"-having a larger TP -intercept-are better because they correspond to classifiers with lower
expected cost.
Because in most real-world cases the target distributions are not known precisely, it is valuable to be able
to identify what subset of classifiers is potentially optimal. Each possible set of distributions defines a family of
iso-performance lines, and for a given family, the optimal methods are those that lie on the "most-northwest" iso-
performance line. Thus, a classifier is potentially optimal if and only if it lies on the northwest boundary (i.e., above
the line of the convex hull (Barber, Dobkin, & Huhdanpaa, 1993) of the set of points in ROC space. 2
In Section 3 we provide a formal proof, but roughly one can see that if a point lies on the convex hull, then
there exists a line through that point such that no other line with the same slope through any other point has a
larger TP -intercept, and thus the classifier represented by the point is optimal under any distribution assumptions
corresponding the that slope. If a point does not lie on the convex hull, then for any family of iso-performance lines
there is another point that lies on an iso-performance line with the same slope but larger TP -intercept, and thus the
classifier cannot be optimal.
2 The convex hull of a set of points is the smallest convex set that contains the points.
False Positive rate
True
Positive
rate
A D
CH

Figure

4: The ROC convex hull identifies potentially optimal classifiers.
We call the convex hull of the set of points in ROC space the ROC convex hull (rocch) of the corresponding set
of classifiers. Figure 4 shows the curves of Figure 3 with the ROC convex hull drawn (CH, the border between the
shaded and unshaded areas). D is clearly not optimal. Surprisingly, B can never be optimal either because none of
the points of its ROC curve lies on the convex hull. We can also remove from consideration any points of A and C
that do not lie on the hull.
2.2.2 The ROC convex hull
Consider these classifiers under two distribution scenarios. In each, negative examples outnumber positives by 5:1.
In scenario A, false positive and false negative errors have equal cost. In scenario B, a false negative is 25 times as
expensive as a false positive (e.g., missing a case of fraud is much worse than a false alarm). Each scenario defines
a family of iso-performance lines. The lines corresponding to scenario A have slope 5; those for B have slope 1
Figure

5 shows the convex hull and two iso-performance lines, ff and fi. Line ff is the "best" line with slope 5 that
intersects the convex hull; line fi is the best line with slope 1that intersects the convex hull. Each line identifies the
optimal classifier under the given distribution.

Figure

6 shows the three ROC curves from our initial example, with the convex hull drawn.
A
False Positive rate
True
Positive
rate
a

Figure

5: Lines ff and fi show the optimal classifier under different sets of conditions.
2.2.3 Generating the ROC Convex Hull
The ROC convex hull method selects the potentially optimal classifiers based on the ROC convex hull and iso-
performance lines.
1. For each classifier, plot TP and FP in ROC space. For continuous-output classifiers, vary a threshold over the
output range and plot the ROC curve.
2. Find the convex hull of the set of points representing the predictive behavior of all classifiers of interest. For n
classifiers this can be done in O(n log(n)) time by the QuickHull algorithm (Barber et al., 1993).
3. For each set of class and cost distributions of interest, find the slope (or range of slopes) of the corresponding
iso-performance lines.
4. For each set of class and cost distributions, the optimal classifier will be the point on the convex hull that
intersects the iso-performance line with largest TP -intercept. Ranges of slopes specify hull segments.

Figures

4 and 5 demonstrate how the subset of classifiers that are potentially optimal can be identified and how
classifiers can be compared under different cost and class distributions. We now demonstrate additional benefits of
the method.
True
positive
rate
False positive rate
Classifier 3
Convex Hull

Figure

curves with convex hull
2.2.4 Comparing a variety of classifiers
The ROC convex hull method accommodates both binary and continuous classifiers. Binary classifiers are represented
by individual points in ROC space. Continuous classifiers produce numeric outputs to which thresholds can be
applied, yielding a series of comprising an ROC curve. Each point may or may not contribute to the
ROC convex hull. Figure 7 depicts the binary classifiers E, F and G added to the previous hull. E may be optimal
under some circumstances because it extents the convex hull. Classifiers F and G never will be optimal because they
do not extend the hull.
New classifiers can be added incrementally to an rocch analysis, as demonstrated in Figure 7 by the addition
of classifiers E,F, and G. Each new classifier either extends the existing hull or does not. In the former case the hull
must be updated accordingly, but in the latter case the new classifier can be ignored. Therefore, the method does not
require saving every classifier (or saving statistics on every classifier) for re-analysis under different conditions-only
those points on the convex hull. No other classifiers can ever be optimal, so they need not be saved. Every classifier
that does lie on the convex hull must be saved.
False Positive rate
A
True
Positive
rate
F
G

Figure

7: Classifier E may be optimal because it extends the ROC convex hull. F and G cannot because they do
not.
2.2.5 Changing distributions and costs
Class and cost distributions that change over time necessitate the reevaluation of classifier choice. In fraud detection,
costs change based on workforce and reimbursement issues; the amount of fraud changes monthly. With the ROC
convex hull method, comparing under a new distribution involves only calculating the slope(s) of the corresponding
iso-performance lines and intersecting them with the hull, as shown in Figure 5.
The ROC convex hull method scales gracefully to any degree of precision in specifying the cost and class distribu-
tions. If nothing is known about a distribution, the ROC convex hull shows all classifiers that may be optimal under
any conditions. Figure 4 showed that, given classifiers A, B, C and D of Figure 3, only A and C can ever be optimal.
With complete information, the method identifies the optimal classifier(s). In Figure 5 we saw that classifier A (with
a particular threshold value) is optimal under scenario A and classifier C is optimal under scenario B. Next we will
see that with less precise information, the ROC convex hull can show the subset of possibly optimal classifiers.
2.2.6 Sensitivity analysis
Imprecise distribution information defines a range of slopes for iso-performance lines. This range of slopes intersects
a segment of the ROC convex hull, which facilitates sensitivity analysis. For example, if the segment defined by a
False Positive rate
A
True
Positive
rate
False Positive rate
A
True
Positive
rate(b)
False Positive rate
True
Positive
rate a
A
(c)

Figure

8: Sensitivity analysis using the ROC convex hull: (a) low sensitivity (only C can be optimal), (b) high
sensitivity (A, E, or C can be optimal), (c) doing nothing is the optimal strategy
range of slopes corresponds to a single point in ROC space or a small threshold range for a single classifier, then there
is no sensitivity to the distribution assumptions in question. Consider a scenario similar to A and B in that negative
examples are 5 times as prevalent as positive ones. In this scenario, the cost of dealing with a false alarm is between
$10 and $20, and the cost of missing a positive example is between $200 and $250. This defines a range of slopes
for iso-performance lines: 1- m - 1. Figure 8a depicts this range of slopes and the corresponding segment of the
ROC convex hull. The figure shows that the choice of classifier is insensitive to changes within this range (and only
fine tuning of the classifier's threshold will be necessary). Figure 8b depicts a scenario with a wider range of slopes:2
3. The figure shows that under this scenario the choice of classifier is very sensitive to the distribution.
Classifiers A, C and E each are optimal for some subrange.
A particularly interesting question in any domain is, When is a "do nothing" strategy better than any of my
available classifiers? Consider Figure 8c. The point (0; 0) corresponds to doing nothing, i.e., issuing negative
classifications regardless of input. Any set of cost and class distribution assumptions for which the best hull-
intersecting iso-performance line passes through the origin (e.g., line ff) defines a scenario where this null strategy is
optimal. Intuitively, Figure 8c illustrates that false positives are so expensive (or negatives so prevalent) that neither
A nor C is good enough to be used. Improvements to A might allow it to beat the null strategy represented by ff,
but no modification to C is likely to have an effect.
Building robust classifiers
Up to this point, we have concentrated on the use of the rocch for visualizing and evaluating sets of classifiers. The
rocch helps to delay classifier selection as long as possible, yet provides a rich performance comparison. However,
once system-building incorporates a particular classifier, the problem of brittleness resurfaces. This is important
because the delay between system-building and deployment may be large, and because many systems must survive
for years. In fact, in many domains a precise, static specification of future costs and class distributions is not just
unlikely, it is impossible (Provost, Fawcett, & Kohavi, 1998).
We address this brittleness by using the rocch to produce robust classifiers, defined as satisfying the following.
Under any target cost and class distributions, a robust classifier will perform at least as well as the best classifier for
those conditions. Our statements about optimality are practical: the "best" classifier may not be the Bayes-optimal
classifier, but it is at least as good as any known classifier. Stating that a classifier is robust is stronger than stating
that it is optimal for a specific set of conditions. A robust classifier is optimal under all possible conditions.
In principle, classification brittleness could be overcome by saving all possible classifiers (neural nets, decision
trees, expert systems, probabilistic models, etc.) and then performing an automated run-time comparison under the
desired target conditions. However, such a system is not feasible because of time and space limitations-there are
myriad possible classification models, arising from the many different learning methods under their many different
parameter settings. Storing all the classifiers is not practical, and tuning the system by comparing classifiers on the
fly under different conditions is not practical. Fortunately, doing so is not necessary. Moreover, we will show that it
is sometimes possible to do better than any of these classifiers.
3.1 ROCCH-hybrid classifiers
We now show that robust hybrid classifiers can be built using the rocch.
I be the space of possible instances and let C be the space of sets of classification models. Let a
-hybrid classifier comprise a set of classification models C 2 C and a function
A -hybrid classifier takes as input an instance I 2 I for classification and a number x 2 !. As output, it produces
the classification produced by -(I ; x; C).
Things will get more involved later, but for the time being consider that each set of cost and class distributions
defines a value for x, which is used to select the (predetermined) best classifier for those conditions. To build a
-hybrid classifier, we must define - and the set C. We would like C to include only those models that perform
optimally under some conditions (class and cost distributions), since these will be stored by the system, and we
would like - to be general enough to apply to a variety of problem formulations.
The models comprising the rocch can be combined to form a -hybrid classifier that is an elegant, robust
classifier.
Definition 2 The rocch-hybrid is a -hybrid classifier where C is the set of classifiers that comprise the rocch
and - makes classifications using the classifier on the rocch with
Note that for the moment the rocch-hybrid is defined only for FP values corresponding to rocch vertices.
3.2 Robust classification
Our definition of robust classifiers was intentionally vague about what it means for one classifier to be better than
another, because different situations call for different comparison frameworks. We now continue with minimizing
expected cost, because the process of proving that the rocch-hybrid minimizes expected cost for any cost and class
distributions provides a deep understanding of why and how the rocch-hybrid works. Later we generalize to a wide
variety of comparison frameworks.
The rocch-hybrid can be seen as an application of multicriteria optimization to classifier design and construction.
The classifiers on the rocch are Edgeworth-Pareto optimal (Stadler, 1988) with respect to TP, FP, and the objective
functions we discuss. Multicriteria optimization was used previously in machine learning by Tcheng, Lambert, Lu
and Rendell for the selection of inductive bias (Tcheng, Lambert, Lu, & Rendell, 1989). Alternatively, the rocch
can be seen as an application of the theory of games and statistical decisions, for which convex sets (and the convex
3.2.1 Minimizing expected cost
From above, the expected cost of applying a classifier is:
For a particular set of cost and class distributions, the slope of the corresponding iso-performance lines is:
c(N; p)p(p) (2)
Every set of conditions will define an m ec - 0. We now can show that the rocch-hybrid is robust for problems
where the "best" classifier is the classifier with the minimum expected cost.
The slope of the rocch is an important tool in our argument. The rocch is a piecewise-linear, concave-down
"curve." Therefore, as x increases, the slope of the rocch is monotonically non-increasing with
where k is the number of rocch component classifiers, including the degenerate classifiers that define the rocch
endpoints. Where there will be no confusion, we use phrases such as "points in ROC space" as a shorthand for the
more cumbersome "classifiers corresponding to points in ROC space." For this subsection, "points on the rocch"
refer to vertices of the rocch.
Definition 3 For any real number m - 0, the point where the slope of the rocch is m is one of the (arbitrarily
chosen) endpoints of the segment of the rocch with slope m, if such a segment exists. Otherwise, it is the vertex for
which the left adjacent segment has slope greater than m and the right adjacent segment has slope less than m.
For completeness, the leftmost endpoint of the rocch is considered to be attached to a segment with infinite
slope and the rightmost endpoint of the rocch is considered to be attached to a segment with zero slope. Note that
every defines at least one point on the rocch.
Lemma 1 For any set of cost and class distributions, there is a point on the rocch with minimum expected cost.
Proof: (by contradiction) Assume that for some conditions there exists a point C with smaller expected cost than
any point on the rocch. By equations 1 and 2, a point
) has the same expected cost as a point
if
Therefore, for conditions corresponding to m ec , all points with equal expected cost form an iso-performance line in
ROC space with slope m ec . Also by 1 and 2, points on lines with larger y-intercept have lower expected cost. Now,
point C is not on the rocch, so it is either above the curve or below the curve. If it is above the curve, then
the rocch is not a convex set enclosing all points, which is a contradiction. If it is below the curve, then the iso-
performance line through C also contains a point P that is on the rocch. Since all points on an iso-performance
line have the same expected cost, point C does not have smaller expected cost than all points on the rocch, which is
also a contradiction. 2
Although it is not necessary for our purposes here, it can be shown that all of the minimum expected cost
classifiers are on the rocch.
Definition 4 An iso-performance line with slope m is an m-iso-performance line.
Lemma 2 For any cost and class distributions that translate to m ec , a point on the rocch has minimum expected
cost only if the slope of the rocch at that point is m ec .
Proof: (by contradiction) Suppose that there is a point D on the rocch where the slope is not m ec , but the point
does have minimum expected cost. By Definition 3, either (a) the segment to the left of D has slope less than m ec ,
or (b) the segment to the right of D has slope greater than m ec . For case (a), consider point N, the vertex of the
rocch that neighbors D to the left, and consider the (parallel) m ec -iso-performance lines l D and l N through D and
N. Because N is to the left of D and the line connecting them has slope less than m ec , the y-intercept of l N will be
greater than the y-intercept of l D . This means that N will have lower expected cost than D, which is a contradiction.
The argument for (b) is analogous (symmetric). 2
Lemma 3 If the slope of the rocch at a point is m ec , then the point has minimum expected cost.
Proof: If this point is the only point where the slope of the rocch is m ec , then the proof follows directly from Lemma
1 and Lemma 2. If there are multiple such points, then by definition they are connected by an m ec -iso-performance
line, so they have the same expected cost, and once again the proof follows directly from Lemma 1 and Lemma 2. 2
It is straightforward now to show that the rocch-hybrid is robust for the problem of minimizing expected cost.
Theorem 4 The rocch-hybrid minimizes expected cost for any cost distribution and any class distribution.
Proof: Because the rocch-hybrid is composed of the classifiers corresponding to the points on the rocch, this
follows directly from Lemmas 1, 2, and 3. 2
Now we have shown that the rocch-hybrid is robust when the goal is to provide the minimum expected cost
classification. This result is important even for accuracy maximization, because the preferred classifier may be
different for different target class distributions. This is rarely taken into account in experimental comparisons of
classifiers.
Corollary 5 The rocch-hybrid minimizes error rate (maximizes accuracy) for any target class distribution.
Proof: rate minimization is cost minimization with uniform error costs. 2
3.3 Robust classification for other common metrics
Showing that the rocch-hybrid is robust not only helps us with understanding the rocch method generally, it also
shows us how the rocch-hybrid will pick the best classifier in order to produce the best classifications, which we
will return to later. If we ignore the need to specify how to pick the best component classifier, we can show that the
rocch applies more generally.
Theorem 6 For any classifier evaluation metric f(FP; TP ), if @f
there exists a point on
the rocch with an f-value at least as high as that of any known classifier.
Proof: (by contradiction) Assume that there exists a classifier C o , not on the rocch, with an f-value higher than
that of any point on the rocch. C o is either (i) above or (ii) below the rocch. In case (i), the rocch is not a convex
set enclosing all the points, which is a contradiction. In case (ii), let C o be represented in ROC-space by
Because C o is below the rocch there exist points, call one on the rocch with TP p ? TP
However, by the restriction on the partial derivatives, for any such point f(FP
again is a contradiction. 2
True
positive
rate
False positive rate
Classifier 3
Hull
Neyman-Pearson

Figure

9: The ROC Convex Hull used to select a classifier under the Neyman-Pearson criterion
There are two complications to the more general use of the rocch, both of which are illustrated by the decision
criterion from our very first example. Recall that the Neyman-Pearson criterion specifies a maximum acceptable
FP rate. In standard ROC analysis, selecting the best classifier for the Neyman-Pearson criterion is easy: plot
ROC curves, draw a vertical line at the desired maximum FP , and pick the ROC curve with the largest TP at the
intersection with this line.
For minimizing expected cost it was sufficient for the rocch-hybrid to choose a vertex from the rocch for any
ec value. For problem formulations such as the Neyman-Pearson criterion, the performance statistics at a non-
vertex point on the rocch may be preferable (see Figure 9). Fortunately, with a slight extension, the rocch-hybrid
can yield a classifier with these performance statistics.
Theorem 7 An rocch-hybrid can achieve the TP :F P tradeoff represented by any point on the rocch, not just the
vertices.
Proof: (by construction) Extend -(I ; x; C) to non-vertex points as follows. Pick the point P on the rocch with
(there is exactly one). Let TP x be the TP value of this point. If (x, TP x ) is an rocch vertex, use the
corresponding classifier. If it is not a vertex, call the left endpoint of the hull segment C l and the right endpoint C r .
Let d be the distance between C l and C r , and let p be the distance between C l and P . Make classifications as follows.
For each input instance flip a weighted coin and choose the answer given by classifier C l with probability p
d and that
given by classifier C r with probability
d . It is straightforward to show that FP and TP for this classifier will be
x and TP x . 2
The second complication is that, as illustrated by the Neyman-Pearson criterion, many practical classifier comparison
frameworks include constrained optimization problems (below we will discuss other frameworks). Arbitrarily
constrained optimizations are problematic for the rocch-hybrid. Given total freedom, it is easy to place constraints
on classifier performance such that, even with the restriction on the partial derivatives, an interior point scores higher
than any acceptable point on the hull. For example, two linear constraints can enclose a subset of the interior and
exclude the entire rocch-there will be no acceptable points on the rocch. However, many realistic constraints do
not thwart the optimality of the rocch-hybrid.
Theorem 8 For any classifier evaluation metric f(FP; TP ), if @f
no constraint on classifier
performance eliminates any point on the rocch without also eliminating all higher-scoring interior points, then the
rocch-hybrid can perform at least as well as any known classifier.
Proof: Follows directly from Theorem 6 and Theorem 7. 2
Linear constraints on classifiers' FP : TP performance are common for real-world problems, so the following is
useful.
Theorem 9 For any classifier evaluation metric f(FP; TP ), if @f
there is a single constraint
on classifier performance of the form a with a and b non-negative, then the rocch-hybrid can
perform at least as well as any known classifier.
Proof: The single constraint eliminates from contention all points (classifiers) that do not fall to the left of, or below,
a line with non-positive slope. By the restriction on the partial derivatives, such a constraint will not eliminate a
point on the rocch without also eliminating all interior points with higher f-values. Thus, the proof follows directly
from Theorem 8. 2
So, finally, we have the following.
Corollary 10 For the Neyman-Pearson criterion, the rocch-hybrid can perform at least as well as that of any
known classifier.
Proof: For the Neyman-Pearson criterion, the evaluation metric higher TP is better.
The constraint on classifier performance is FP - FPmax . These satisfy the conditions for Theorem 9, and therefore
this corollary follows. 2
All the foregoing effort may seem misplaced for a simple criterion like Neyman-Pearson. However, there are many
other realistic problem formulations. For example, consider the decision-support problem of optimizing workforce
utilization, in which a workforce is available that can process a fixed number of cases. Too few cases will under-utilize
the workforce, but too many cases will leave some cases unattended (expanding the workforce usually is not a short-term
solution). If the workforce can handle C cases, the system should present the best possible set of C cases. This
is similar to the Neyman-Pearson criterion, but with an absolute cutoff (C) instead of a percentage cutoff
Theorem 11 For workforce utilization, the rocch-hybrid will provide the best set of C cases, for any choice of C.
Proof: (by construction) The decision criterion is to maximize TP subject to the constraint:
The theorem therefore follows from Theorem 9. 2
In fact, many screening problems, such as are found in marketing and information retrieval, use exactly this linear
constraint, so it follows that for maximizing lift (Berry & Linoff, 1997), precision or recall, subject to absolute or
percentage cutoffs on case presentation, the rocch-hybrid will provide the best set of cases.
As with minimizing expected cost, imprecision in the environment forces us to favor a robust solution for these
other comparison frameworks. For many real-world problems, the precise desired cutoff will be unknown or will
change (e.g., because of fundamental uncertainty, variability in case difficulty or competing responsibilities). What
is worse, for a fixed (absolute) cutoff merely changing the size of the universe of cases (e.g., the size of a document
corpus) may change the preferred classifier, because it will change the constraint line. The rocch-hybrid provides
a robust solution because it gives the optimal subset of cases for any constraint line. For example, for document
retrieval the rocch-hybrid will yield the best N documents for any N , for any prior class distribution (in the target
corpus), and for any target corpus size.
3.4 Ranking cases
An apparent solution to the problem of robust classification is to use a system that ranks cases, rather than one
that provides classifications, and just work down the ranked list (the cutoff is implicit). However, for most practical
situations, choosing the best ranking model is equivalent to choosing which classifier is best for the cutoff that will be
used. Remember that ROC curves are formed from case rankings by moving the cutoff from one extreme to the other.
For different cutoffs, implicit or explicit, different ranking functions perform better. This is exactly the problem of
robust classification, and is solved elegantly by the rocch-hybrid-the rocch-hybrid comprises the set rankers that
are best for all possible cutoffs. As an example, consider two ranking functions R a and R b . R a is perfect for the first
cases, and picks randomly thereafter. R b randomly chooses the first 10 cases, and ranks perfectly thereafter. R a
is preferable for a cutoff of 10 cases and R b is preferable for much larger cutoffs.
Whole-curve metrics
In situations where either the target cost distribution or class distribution is completely unknown, some researchers
advocate choosing the classifier that maximizes a single-number metric representing the average performance over
the entire curve. A common whole-curve metric is the area under the ROC curve (AUC) (Bradley, 1997). The
AUC is equivalent to the probability that a randomly chosen positive instance will be rated higher than a negative
instance, and thereby is also estimated by the Wilcoxon test of ranks (Hanley & McNeil, 1982). A criticism of AUC
is that for specific target conditions the classifier with the maximum AUC may be suboptimal (Provost et al., 1998)
(this criticism may be made of any single-number metric). Fortunately, not only is the rocch-hybrid optimal for
any specific target conditions, it has the maximum AUC.
Theorem 12 There is no classifier with AUC larger than that of the rocch-hybrid.
Proof: (by contradiction) Assume the ROC curve for another classifier had larger area. This curve would have to
have at least one point in ROC-space that falls outside the area enclosed by the rocch. This means that the convex
hull does not enclose all points, which is a contradiction. 2
3.6 Using the ROCCH-hybrid
To use the rocch-hybrid for classification, we need to translate environmental conditions to x values to plug into
C). For minimizing expected cost, Equation 2 shows how to translate conditions to m ec . For any m ec , by
Lemma 3 we want the FP value of the point where the slope of the rocch is m ec , which is straightforward to
calculate. For the Neyman-Pearson criterion the conditions are defined as FP values. For workforce utilization with
conditions corresponding to a cutoff C, the FP value is found by intersecting the line TP
the rocch.
We have argued that target conditions (misclassification costs and class distribution) are rarely known. It may
be confusing that we now seem to require exact knowledge of these conditions. The rocch-hybrid gives us two
important capabilities. First, the need for precise knowledge of target conditions is deferred until run time. Second,
in the absence of precise knowledge even at run time, the system can be optimized easily with minimal feedback.
By using the rocch-hybrid, information on target conditions is not needed to train and compare classifiers. This
is important because of imprecision caused by temporal, geographic, or other differences that may exist between
training and use. For example, building a system for a real-world problem introduces a non-trivial delay between the
time data are gathered and the time the learned models will be used. The problem is exacerbated in domains where
error costs or class distributions change over time; even with slow drift, a brittle model may become suboptimal
quickly. In many such scenarios, costs and class distributions can be specified (or respecified) at run time with
reasonable precision by sampling from the current population, and used to ensure that the rocch-hybrid always
performs optimally.
In some cases, even at run time these quantities are not known exactly. A further benefit of the rocch-hybrid
is that it can be tuned easily to yield optimal performance with only minimal feedback from the environment.
Conceptually, the rocch-hybrid has one "knob" that varies x in -(I ; x; C) from one extreme to the other. For any
knob setting, the rocch-hybrid will give the optimal TP :F P tradeoff for the target conditions corresponding to
that setting. Turning the knob to the right increases TP ; turning the knob to the left decreases FP . Because of
the monotonicity of the rocch-hybrid, simple hill-climbing can guarantee optimal performance. For example, if the
system produces too many false alarms, turn the knob to the left; if the system is presenting too few cases, turn the
knob to the right.
3.7 Beating the component classifiers
Perhaps surprisingly, in many realistic situations an rocch-hybrid system can do better than any of its component
classifiers. Consider the Neyman-Pearson decision criterion. The rocch may intersect the FP -line above the highest
component ROC curve. This occurs when the FP -line intersects the rocch between vertices; therefore, there is no
component classifier that actually produces these particular statistics, as in Figure 9.
Theorem 13 The rocch-hybrid can surpass the performance of its component classifiers for some Neyman-Pearson
problems.
Proof: For any non-vertex hull point (x,T P x ), TP x is larger than the TP for any other point with
Theorem 7, the rocch-hybrid can achieve any TP on the hull. Only a small number of FP values correspond to
hull vertices. 2
The same holds for other common problem formulations, such as workforce utilization, lift maximization, precision
maximization, and recall maximization.
3.8 Time and space efficiency
We have argued that the rocch-hybrid is robust for a wide variety of problem formulations. It is also efficient to
build, to store, and to update.
The time efficiency of building the rocch-hybrid depends first on the efficiency of building the component models,
which varies widely by model type. Some models built by machine learning methods can be built in seconds (once
data are available). Hand-built models can take years to build. However, we presume that this is work that would be
done anyway. The rocch-hybrid can be built with whatever methods are available, be there two or two thousand.
As described below, as new classifiers become available, the rocch-hybrid can be updated incrementally. The time
efficiency depends also on the efficiency of the experimental evaluation of the classifiers. Once again, we presume
that this is work that would be done anyway (more on this in Limitations). Finally, the time efficiency of the
rocch-hybrid depends on the efficiency of building the rocch, which can be done in O(N log N) time using the
QuickHull algorithm (Barber et al., 1993) where N is the number of classifiers.
The rocch is space efficient, too, because it comprises only classifiers that might be optimal under some target
conditions.
Theorem 14 For minimizing expected cost, the rocch-hybrid comprises only classifiers that are optimal under some
cost and class distributions.
Proof: Follows directly from Lemmas 1-3 and Definitions 3 and 4. 2
The number of classifiers that must be stored can be reduced if bounds can be placed on the potential target
conditions. As described above, ranges of conditions define segments of the rocch. Thus, the rocch-hybrid may
need only a subset of C.
Adding new classifiers to the rocch-hybrid also is efficient. Adding a classifier to the rocch will either (i) extend
the hull, adding to (and possibly subtracting from) the rocch-hybrid, or (ii) conclude that the new classifiers are
not superior to the existing classifiers in any portion of ROC space and can be discarded.
The run-time (classification) complexity of the rocch-hybrid is never worse than that of the component classifiers.
In situations where run-time complexity is crucial, the rocch should be constructed without prohibitively expensive
classification models. It will then find the best subset of the computationally efficient models.
Empirical demonstration of need
Robust classification is of fundamental interest because it weakens two very strong assumptions: the availability of
precise knowledge of costs and of class distributions. However, might it not be that existing classifiers are already
robust? For example, if a given classifier is optimal under one set of conditions, might it not be optimal under all?
It is beyond the scope of this paper to offer an in-depth experimental study answering this question. However,
we can provide solid evidence that the answer is "no" by referring to the results of two prior studies. One is a
comprehensive ROC analysis of medical domains recently conducted by Andrew Bradley (1997). 3 The other is a
published ROC analysis of UCI database domains that we undertook last year with Ronny Kohavi (Provost et al.,
1998).
Note that a classifier dominates if its ROC curve completely defines the rocch (which means dominating classifiers
are robust and vice versa). Therefore, if there exist more than a trivially few domains where no classifier dominates,
then techniques like the rocch-hybrid are essential.
3 His purpose was not to answer this question; fortunately his published results do anyway.
True
positive
rate
False positive rate
Bayes
K-NN
MSC
Perceptron

Figure

10: Bradley's classifier results for the heart bleeding data.
4.1 Bradley's study
Bradley studied six medical data sets, noting that "unfortunately, we rarely know what the individual misclassification
costs are." He plotted the ROC curves of six classifier learning algorithms (two neural nets, two decision trees and
two statistical techniques).
On not one of these data sets was there a dominating classifier. This means that for each domain, there exist
different sets of conditions for which different classifiers are preferable. In fact, our running example is based on the
three best classifiers from Bradley's results on the heart bleeding data; his results for the full set of six classifiers can
be found in Figure 10. Classifiers constructed for the Cleveland heart disease data, are shown in Figure 11.
Bradley's results show clearly that for many domains the classifier that maximizes any single metric-be it
accuracy, cost, or the area under the ROC curve-will be the best for some cost and class distributions and will not
be the best for others. We have shown that the rocch-hybrid will be the best for all.
4.2 Our study
In the study we performed with Ronny Kohavi, we chose ten datasets from the UCI repository that contained at
least 250 instances, but for which the accuracy for decision trees was less than 95%. For each domain, we induced
classifiers for the minority class (for Road, we chose the class Grass). We selected several induction algorithms from
MLC++ (Kohavi, Sommerfield, & Dougherty, 1997): a decision tree learner (MC4), Naive Bayes with discretization
(NB), k-nearest neighbor for several k values (IBk), and Bagged-MC4 (Breiman, 1996). MC4 is similar to C4.5
True
positive
rate
False positive rate
Bayes
K-NN
MSC
Perceptron

Figure

11: Bradley's classifier results for the Cleveland heart disease data
(Quinlan, 1993); probabilistic predictions are made by using a Laplace correction at the leaves. NB discretizes the
data based on entropy minimization (Dougherty, Kohavi, & Sahami, 1995) and then builds the Naive-Bayes model
(Domingos & Pazzani, 1997). IBk votes the closest k neighbors; each neighbor votes with a weight equal to one over
its distance from the test instance.
Some of the ROC curves are shown in Figures 12. For only one (Vehicle) of these ten domains was there an
absolute dominator. In general, very few of the 100 runs performed (on 10 data sets, using 10 cross-validation folds
dominating classifiers. Some cases are very close, for example Adult and Waveform-21. In other cases a
curve that dominates in one area of ROC space is dominated in another. These results also support the need for
methods like the rocch-hybrid, which produce robust classifiers.
As examples of what expected-cost-minimizing rocch-hybrids would look like internally, Table 1 shows the
component classifiers that make up the rocch for the four UCI domains of Figure 12. For example, in the Road
domain (see Figure 12 and Table 1), Naive Bayes would be chosen for any target conditions corresponding to a slope
less than 0:38, and Bagged-MC4 would be chosen for slopes greater than 0:38. They perform equally well at 0:38.
5 Limitations and future work
There are limitations to the rocch method as we have presented it here. We have defined it only for two-class
problems. We believe that it can be extended to multi-class problems, but have not yet done so formally. It should
be noted that the dimensionality of the "ROC-hyperspace" grows quadratically in the number of classes. We have
Table

1: Locally dominating classifiers for four UCI domains
Domain Slope range Dominator Domain Slope range Dominator
Vehicle [0, 1) Bagged-MC4 Satimage [0, 0.05] NB
Road [0, 0.38] NB [0.05, 0.22] Bagged-MC4
CRX [0, 0.03] Bagged-MC4 [2.60, 3.11] IB3
[0.06, 2.06] Bagged-MC4 [7.54, 31.14] IB3
also assumed constant error costs for a given type of error, e.g., all false positives cost the same. For some problems,
different errors of the same type have different costs. In many cases, such a problem can be transformed for evaluation
into an equivalent problem with uniform intra-type error costs by duplicating instances in proportion to their costs
(or by simply modifying the counting procedure accordingly).
We have also assumed for this paper that the estimates of the classifiers' performance statistics (FP and TP ) are
very good. As mentioned above, much work has addressed the production of good estimates for simple performance
statistics such as error rate. Much less work has addressed the production of good ROC curve estimates. As with
simpler statistics, care should be taken to avoid over-fitting the training data and to ensure that differences between
ROC curves are meaningful. One solution is to use cross-validation with averaging of ROC curves (Provost et al.,
1998), which is the procedure used to produce the ROC curves in Section 4.2. To our knowledge, the issue is open
of how best to produce confidence bands appropriate to a particular problem. Those shown in Section 4.2 are
appropriate for the Neyman-Pearson decision criterion (i.e., they show confidence on TP for various values of FP ).
Also, we have addressed predictive performance and computational performance. These are not the only concerns
in choosing a classification model. What if comprehensibility is important? The easy answer is that for any particular
setting, the rocch-hybrid is as comprehensible as the underlying model it is using. However, this answer falls short
if the rocch-hybrid is interpolating between two models or if one wants to understand the "multiple-model" system
as a whole.
This work is fundamentally different from other recent machine learning work on combining multiple models (Ali
1996). That work combines models in order to boost performance for a fixed cost and class distribution.
The rocch-hybrid combines models for robustness across different cost and class distributions. In principle, these
methods should be independent-multiple-model classifiers are candidates for extending the rocch. However, it
may be that some multiple-model classifiers achieve increased performance for a specific set of conditions by (in
interpolating along edges of the rocch.
The rocch method also complements research on cost-sensitive learning (Turney, 1996). Existing cost-sensitive
learning methods are brittle with respect to imprecise cost knowledge. Thus, the rocch is an essential evaluation
tool. Furthermore, cost-sensitive learning may be used to find better components for the rocch-hybrid, by searching
explicitly for classifiers that extend the rocch.
6 Conclusion
The ROC convex hull method is a robust, efficient solution to the problem of comparing multiple classifiers in
imprecise and changing environments. It is intuitive, can compare classifiers both in general and under specific
distribution assumptions, and provides crisp visualizations. It minimizes the management of classifier performance
data, by selecting exactly those classifiers that are potentially optimal; thus, only these need to be saved in preparation
for changing conditions. Moreover, due to its incremental nature, new classifiers can be incorporated easily, e.g.,
when trying a new parameter setting.
The rocch-hybrid performs optimally under any target conditions for many realistic problem formulations,
including the optimization of metrics such as accuracy, expected cost, lift, precision, recall, and workforce utilization.
It is efficient to build in terms of time and space, and can be updated incrementally. Furthermore, it can sometimes
classify better than any (other) known model. Therefore, we conclude that it is an elegant, robust classification
system.
We believe that this work has important implications for both machine learning applications and machine learning
research (Provost et al., 1998). For applications, it helps free system designers from the need to choose (sometimes
arbitrary) comparison metrics before precise knowledge of key evaluation parameters is available. Indeed, such
knowledge may never be available, yet robust systems can still be built.
For machine learning research, it frees researchers from the need to have precise class and cost distribution
information in order to study important related phenomena. In particular, work on cost-sensitive learning has been
impeded by the difficulty of specifying costs, and by the tenuous nature of conclusions based on a single cost metric.
Researchers need not be held back by either. Cost-sensitive learning can be studied generally without specifying costs
precisely. The same goes for research on learning with highly skewed distributions. Which methods are effective for
which levels of distribution skew? The rocch will provide a detailed answer.
Note: An implementation of the rocch method in Perl is publicly available. The code and related papers may
be found at: http://www.croftj.net/~fawcett/ROCCH/.

Acknowledgments

We thank the many with whom we have discussed ROC analysis and classifier comparison, especially Rob Holte,
George John, Ron Kohavi, Ron Rymon, and Peter Turney. We thank Andrew Bradley for supplying data from his
analysis.



--R

reduction through learning multiple descriptions.
The quickhull algorithm for convex hull.
The use of ROC curves in test performance evaluation.
Data Mining Techniques: For Marketing
Theory of Games and Statistical Decisions.
Republished by Dover Publications
The use of the area under the ROC curve in the evaluation of machine learning algorithms.

Classification and regression trees.
Bagging predictors.
Tailoring rulesets to misclassificatioin costs.

Approximate statistical tests for comparing supervised classification learning algorithms.
Neural Computation
Beyond independence: Conditions for the optimality of the simple Bayesian classifier.
Supervised and unsupervised discretization of continuous features.
In Prieditis

Learning goal oriented bayesian networks for telecommunications risk management.
Adaptive fraud detection.
Available as http://www.
The meaning and use of the area under a receiver operating characteristic (roc) curve.
A study of cross-validation and bootstrap for accuracy estimation and model selection
http://robotics.
Data mining using MLC
Machine learning for the detection of oil spills in satellite radar images.
Reducing misclassification costs.
The case against accuracy estimation for comparing induction algorithms.

"real world"
On comparing classifiers: Pitfalls to avoid and a recommended approach.

Measuring the accuracy of diagnostic systems.
Building robust learning systems by combining induction and optimization.
Cost sensitive learning bibliography.
Clinical Decision Analysis.




--TR
C4.5: programs for machine learning
Bagging predictors
The quickhull algorithm for convex hulls
reduction through learning multiple descriptions
On the Optimality of the Simple Bayesian Classifier under Zero-One Loss
Learning in the MYAMPERSANDldquo;Real WorldMYAMPERSANDrdquo;
Machine Learning for the Detection of Oil Spills in Satellite Radar Images
Approximate statistical tests for comparing supervised classification learning algorithms
Activity monitoring
MetaCost
Explicitly representing expected cost
Data Mining Techniques
Adaptive Fraud Detection
On Comparing Classifiers
The Case against Accuracy Estimation for Comparing Induction Algorithms
Detecting Concept Drift with Support Vector Machines

--CTR
Jigang Xie , Zhengding Qiu , Zhenjiang Miao , Yanqiang Zhang, Bootstrap FDA for counting positives accurately in imprecise environments, Pattern Recognition, v.40 n.11, p.3292-3298, November, 2007
Anna Olecka, Evaluating classifiers' performance in a constrained environment, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Tom Fawcett , Peter A. Flach, A response to Webb and Ting's on the application of ROC analysis to predict classification performance under varying class distributions, Machine Learning, v.58 n.1, p.33-38, January 2005
Tom Fawcett , Alexandru Niculescu-Mizil, PAV and the ROC convex hull, Machine Learning, v.68 n.1, p.97-106, July      2007
Sven F. Crone , Stefan Lessmann , Robert Stahlbock, Utility based data mining for time series analysis: cost-sensitive learning for neural network predictors, Proceedings of the 1st international workshop on Utility-based data mining, p.59-68, August 21-21, 2005, Chicago, Illinois
Reuven Arbel , Lior Rokach, Classifier evaluation under limited resources, Pattern Recognition Letters, v.27 n.14, p.1619-1631, 15 October 2006
Geoffrey I. Webb , Kai Ming Ting, On the application of ROC analysis to predict classification performance under varying class distributions, Machine Learning, v.58 n.1, p.25-32, January 2005
Lian Yan , Michael Fassino , Patrick Baldasare, Enhancing the lift under budget constraints: an application in the mutual fund industry, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Csar Ferri , Peter Flach , Jos Hernndez-Orallo, Delegating classifiers, Proceedings of the twenty-first international conference on Machine learning, p.37, July 04-08, 2004, Banff, Alberta, Canada
Steven N. Thorsen , Mark E. Oxley, A description of competing fusion systems, Information Fusion, v.7 n.4, p.346-360, December, 2006
Jos Mara Gmez Hidalgo , Guillermo Cajigas Bringas , Enrique Puertas Snz , Francisco Carrero Garca, Content based SMS spam filtering, Proceedings of the 2006 ACM symposium on Document engineering, October 10-13, 2006, Amsterdam, The Netherlands
Jos Mara Gmez Hidalgo, Evaluating cost-sensitive Unsolicited Bulk Email categorization, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
Tom Fawcett, ROC graphs with instance-varying costs, Pattern Recognition Letters, v.27 n.8, p.882-891, June 2006
Exploiting AUC for optimal linear combinations of dichotomizers, Pattern Recognition Letters, v.27 n.8, p.900-907, June 2006
Zhiqiang Zheng , Balaji Padmanabhan , Haoqiang Zheng, A DEA approach for model combination, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Csar Ferri, Multi-paradigm learning of declarative models: Thesis, AI Communications, v.17 n.2, p.95-97, April 2004
Rich Caruana , Mohamed Elhawary , Art Munson , Mirek Riedewald , Daria Sorokina , Daniel Fink , Wesley M. Hochachka , Steve Kelling, Mining citizen science data to predict orevalence of wild bird species, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
David Jensen , Matthew Rattigan , Hannah Blau, Information awareness: a prospective technical assessment, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Thomas C. W. Landgrebe , David M. J. Tax , Pavel Paclk , Robert P. W. Duin, The interaction between classification and reject performance for distance-based reject-option classifiers, Pattern Recognition Letters, v.27 n.8, p.908-917, June 2006
Katia Kermanidis , Manolis Maragoudakis , Nikos Fakotakis , George Kokkinakis, Learning Greek verb complements: addressing the class imbalance, Proceedings of the 20th international conference on Computational Linguistics, p.1065-es, August 23-27, 2004, Geneva, Switzerland
Francesco Tortorella, A ROC-based reject rule for dichotomizers, Pattern Recognition Letters, v.26 n.2, p.167-180, 15 January 2005
Bianca Zadrozny , Charles Elkan, Learning and making decisions when costs and probabilities are both unknown, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.204-213, August 26-29, 2001, San Francisco, California
Dirk Ourston , Sara Matzner , William Stump , Bryan Hopkins, Coordinated internet attacks: responding to attack complexity, Journal of Computer Security, v.12 n.2, p.165-190, May 2004
Gerhard Widmer, Discovering simple rules in complex data: a meta-learning algorithm and some surprising musical discoveries, Artificial Intelligence, v.146 n.2, p.129-148, June
Chao-Ton Su , Long-Sheng Chen , Tai-Lin Chiang, A neural network based information granulation approach to shorten the cellular phone test process, Computers in Industry, v.57 n.5, p.412-423, June 2006
Francis R. Bach , David Heckerman , Eric Horvitz, Considering Cost Asymmetry in Learning Classifiers, The Journal of Machine Learning Research, 7, p.1713-1741, 12/1/2006
Tadeusz Pietraszek, On the use of ROC analysis for the optimization of abstaining classifiers, Machine Learning, v.68 n.2, p.137-169, August    2007
Juan Jos Garca Adeva , Juan Manuel Pikatza Atxa, Intrusion detection in web applications using text mining, Engineering Applications of Artificial Intelligence, v.20 n.4, p.555-566, June, 2007
Jerzy W. Grzymala-Busse , Linda K. Goodwin , Xiaohui Zhang, Increasing sensitivity of preterm birth by changing rule strengths, Pattern Recognition Letters, v.24 n.6, p.903-910, March
Nilesh Dalvi , Pedro Domingos , Mausam , Sumit Sanghai , Deepak Verma, Adversarial classification, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Paul N. Bennett , Susan T. Dumais , Eric Horvitz, Probabilistic combination of text classifiers using reliability indicators: models and results, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland
Ashwin Srinivasan, Extracting Context-Sensitive Models in Inductive Logic Programming, Machine Learning, v.44 n.3, p.301-324, September 2001
Tom Fawcett, An introduction to ROC analysis, Pattern Recognition Letters, v.27 n.8, p.861-874, June 2006
Stijn Viaene , Bart Baesens , Guido Dedene , Jan Vanthienen , Dirk Van den Poel, Proof running two state-of-the-art pattern recognition techniques in the field of direct marketing, Enterprise information systems IV, Kluwer Academic Publishers, Hingham, MA,
Sofus A. Macskassy , Foster Provost, Intelligent information triage, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-326, September 2001, New Orleans, Louisiana, United States
Daniel Grossman , Pedro Domingos, Learning Bayesian network classifiers by maximizing conditional likelihood, Proceedings of the twenty-first international conference on Machine learning, p.46, July 04-08, 2004, Banff, Alberta, Canada
Tom Fawcett, "In vivo" spam filtering: a challenge problem for KDD, ACM SIGKDD Explorations Newsletter, v.5 n.2, December
Tams Horvth , Thomas Grtner , Stefan Wrobel, Cyclic pattern kernels for predictive graph mining, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Aleksandar Lazarevic , Vipin Kumar, Feature bagging for outlier detection, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Aleksander Kolcz, Local sparsity control for naive Bayes with extreme misclassification costs, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Roco Alaiz-Rodrguez , Alicia Guerrero-Curieses , Jess Cid-Sueiro, Minimax Regret Classifier for Imprecise Class Distributions, The Journal of Machine Learning Research, 8, p.103-130, 5/1/2007
Mansoor J. Zolghadri , Eghbal G. Mansoori, Weighting fuzzy classification rules using receiver operating characteristics (ROC) analysis, Information Sciences: an International Journal, v.177 n.11, p.2296-2307, June, 2007
Anneleen Assche , Celine Vens , Hendrik Blockeel , Sao Deroski, First order random forests: Learning relational classifiers with complex aggregates, Machine Learning, v.64 n.1-3, p.149-182, September 2006
Thomas Grtner , John W. Lloyd , Peter A. Flach, Kernels and Distances for Structured Data, Machine Learning, v.57 n.3, p.205-232, December 2004
Ashwin Srinivasan , David Page , Rui Camacho , Ross King, Quantitative pharmacophore models with inductive logic programming, Machine Learning, v.64 n.1-3, p.65-90, September 2006
Shlomo Hershkop , Salvatore J. Stolfo, Combining email models for false positive reduction, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
D. M. Gavrila , S. Munder, Multi-cue Pedestrian Detection and Tracking from a Moving Vehicle, International Journal of Computer Vision, v.73 n.1, p.41-59, June      2007
Konstantinos Koumpis , Steve Renals, Automatic summarization of voicemail messages using lexical and prosodic features, ACM Transactions on Speech and Language Processing (TSLP), v.2 n.1, p.1-es, February 2005
Nada Lavra , Branko Kavek , Peter Flach , Ljupo Todorovski, Subgroup Discovery with CN2-SD, The Journal of Machine Learning Research, 5, p.153-188, 12/1/2004
Clifton Phua , Damminda Alahakoon , Vincent Lee, Minority report in fraud detection: classification of skewed data, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004
Jeremy Z. Kolter , Marcus A. Maloof, Learning to detect malicious executables in the wild, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Paul N. Bennett , Susan T. Dumais , Eric Horvitz, The Combination of Text Classifiers Using Reliability Indicators, Information Retrieval, v.8 n.1, p.67-100, January 2005
Stijn Viaene , Richard A. Derrig , Guido Dedene, A Case Study of Applying Boosting Naive Bayes to Claim Fraud Diagnosis, IEEE Transactions on Knowledge and Data Engineering, v.16 n.5, p.612-620, May 2004
J. Zico Kolter , Marcus A. Maloof, Learning to Detect and Classify Malicious Executables in the Wild, The Journal of Machine Learning Research, 7, p.2721-2744, 12/1/2006
Johannes Frnkranz , Peter A. Flach, ROC 'n' rule learning: towards a better understanding of covering algorithms, Machine Learning, v.58 n.1, p.39-77, January 2005
Foster Provost , Pedro Domingos, Tree Induction for Probability-Based Ranking, Machine Learning, v.52 n.3, p.199-215, September
Gary M. Weiss, Mining with rarity: a unifying framework, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004
Nitesh V. Chawla , Nathalie Japkowicz , Aleksander Kotcz, Editorial: special issue on learning from imbalanced data sets, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004
Estevam R. Hruschka, Jr. , Nelson F. F. Ebecken, Towards efficient variables ordering for Bayesian networks classifier, Data & Knowledge Engineering, v.63 n.2, p.258-269, November, 2007
Chris Drummond , Robert C. Holte, Cost curves: An improved method for visualizing classifier performance, Machine Learning, v.65 n.1, p.95-130, October   2006
Mohammed J. Zaki , Charu C. Aggarwal, XRules: An effective algorithm for structural classification of XML data, Machine Learning, v.62 n.1-2, p.137-170, February  2006
Perlich , Foster Provost , Jeffrey S. Simonoff, Tree induction vs. logistic regression: a learning-curve analysis, The Journal of Machine Learning Research, 4, p.211-255, 12/1/2003
Mukund Deshpande , Michihiro Kuramochi , Nikil Wale , George Karypis, Frequent Substructure-Based Approaches for Classifying Chemical Compounds, IEEE Transactions on Knowledge and Data Engineering, v.17 n.8, p.1036-1050, August 2005
Ming-Hsuan Yang , David J. Kriegman , Narendra Ahuja, Detecting Faces in Images: A Survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.1, p.34-58, January 2002
Michael Berthold , David J. Hand, References, Intelligent data analysis, Springer-Verlag New York, Inc., New York, NY,
uncertainty;evaluation;classification;learning;multiple models;comparison;cost-sensitive learning;skewed distributions