Judging the Performance of Classifiers

Lecture 2 Judging the Performance of Classifiers 1 In this note we will examine the question of how to judge the usefulness of a classifier and how to compare different classifiers. Not only do we have a wide choice of different types of classifiers to choose from but within each type of classifier we have many options such as how many nearest neighbors to use in a k-nearest neighbors classifier, the minimum number of cases we should require in a leaf node in a tree classifier, which subsets of predictors to use in a logistic regression model, and how many hidden layer neurons to use in a neural net. A Two-class Classifier Let us first look at a single classifier for two classes with options set at certain values. The twoclass situation is certainly the most common and occurs very frequently in practice. We will extend our analysis to more than two classes later. A natural criterion for judging the performance of a classifier is the probability that it makes a misclassification. A classifier that makes no errors would be perfect but we do not expect to be able to construct such classifiers in the real world due to “noise” and to not having all the information needed to precisely classify cases. Is there a minimum probability of misclassification we should require of a classifier? Suppose that the two classes are denoted by C0 and C1. Let p(C0) and p(C1) be the apriori probabilities that a case belongs to C0 and C1 respectively. The apriori probability is the probability that a case belongs to a class without any more knowledge about it than that it belongs to a population where the proportion of C0’s is p(C0) and the proportion of C1’s is p(C1) . In this situation we will minimize the chance of a misclassification error by assigning class C1 to the case if p( C1 ) > p( C0 ) and to C0 otherwise. The probability of making a misclassification would be the minimum of p(C0) and p(C1). If we are using misclassification rate as our criterion any classifier that uses predictor variables must have an error rate better than this. What is the best performance we can expect from a classifier? Clearly the more training data available to a classifier the more accurate it will be. Suppose we had a huge amount of training data, would we then be able to build a classifier that makes no errors? The answer is no. The accuracy of a classifier depends critically on how separated the classes are with respect to the predictor variables that the classifier uses. We can use the well-known Bayes’ formula from probability theory to derive the best performance we can expect from a classifier for a given set of predictor variables if we had a very large amount of training data. Bayes' formula uses the distributions of the decision variables in the two classes to give us a classifier that will have the minimum error amongst all classifiers that use the same predictor variables. This classifier follows the Minimum Error Bayes Rule. Bayes Rule for Minimum Error Let us take a simple situation where we have just one continuous predictor variable for classification, say X. X is a random variable, since it's value depends on the individual case we sample from the population consisting of all possible cases of the class to which the case belongs. Suppose that we have a very large training data set. Then the relative frequency histogram of the variable X in each class would be almost identical to the probability density function (p.d.f.) of X for that class. Let us assume that we have a huge amount of training data and so we know the p.d.f.s accurately. These p.d.f.s are denoted f0(x) and f1(x) for classes C0 and C1 in Fig. 1 below. 2 Figure 1 f1(x) f0(x) a x Now suppose we wish to classify an object for which the value of X is x0. Let us use Bayes’ formula to predict the probability that the object belongs to class 1 conditional on the fact that it has an X value of x0. Appling Bayes’ formula, the probability, denoted by p(C1|X= x0), is given by: p(C1 | X = x0 ) = p( X = x0 | C1 ) p(C1 ) p( X = x0 | C0 ) p(C0 ) + p( X = x0 | C1 ) p(C1 ) Writing this in terms of the density functions, we get p(C1 | X = x0 ) = f 1 ( x0 ) p(C1 ) f 0 ( x0 ) p(C0 ) + f 1 ( x0 ) p(C1 ) Notice that to calculate p(C1|X= x0) we need to know the apriori probabilities p(C0) and p(C1). Since there are only two possible classes, if we know p(C1) we can always compute p(C0) because p(C0) = 1 - p(C1). The apriori probability p(C1) is the probability that an object belongs to C1 without any knowledge of the value of X associated with it. Bayes’ formula enables us to update this apriori probability to the aposteriori probability, the probability of the object belonging to C1 after knowing that its X value is x0. When p(C1) = p(C0) = 0.5, the formula shows that p(C1 | X = x0 ) > p(C0 | X = x0 ) if f 1 ( x0 ) > f 0 ( x0 ) . This means that if x0 is greater than a, and we classify the object as belonging to C1 we will make a smaller misclassification error than if we were to classify it as belonging to C0 .Similarly if x0 is less than a, and we classify the object as belonging to C0 we will make a smaller misclassification error than if we were to classify it as belonging to C1. If x0 is exactly equal to a we have a 50% chance of making an error for either classification. 3 Figure 2 f1(x) 2f0(x) ab x What if the prior class probabilities were not the same? Suppose C0 is twice as likely apriori as C1. Then the formula says that p(C1 | X = x0 ) > p(C0 | X = x0 ) if f 1 ( x0 ) > 2 × f 0 ( x0 ) . The new boundary value, b for classification will be to the right of a as shown in Fig.2. This is intuitively what we would expect. If a class is more likely we would expect the cut-off to move in a direction that would increase the range over which it is preferred. In general we will minimize the misclassification error rate if we classify a case as belonging to C1 if p(C1 ) × f 1 ( x0 ) > p(C0 ) × f 0 ( x0 ) , and to C0 , otherwise. This rule holds even when X is a vector consisting of several components, each of which is a random variable. In the remainder of this note we shall assume that X is a vector. An important advantage of Bayes’ Rule is that, as a by-product of classifying a case, we can compute the conditional probability that the case belongs to each class. This has two advantages. First, we can use this probability as a “score” for each case that we are classifying. The score enables us to rank cases that we have predicted as belonging to a class in order of confidence that we have made a correct classification. This capability is important in developing a lift curve (explained later) that is important for many practical data mining applications. Second, it enables us to compute the expected profit or loss for a given case. This gives us a better decision criterion than misclassification error when the loss due to error is different for the two classes. 4 Practical assessment of a classifier using misclassification error as the criterion In practice, we can estimate p(C1 ) and p(C0 ) from the data we are using to build the classifier by simply computing the proportion of cases that belong to each class. Of course, these are estimates and they can be incorrect, but if we have a large enough data set and neither class is very rare our estimates will be reliable. Sometimes, we may be able to use public data such as census data to estimate these proportions. However, in most practical business settings we will not know f 1 ( x ) and f 0 ( x ) . If we want to apply Bayes’ Rule we will need to estimate these density functions in some way. Many classification methods can be interpreted as being methods for estimating such density functions1. In practice X will almost always be a vector. This makes the task difficult and subject to the curse of dimensionality we referred to when discussing the kNearest Neighbors technique. To obtain an honest estimate of classification error, let us suppose that we have partitioned a data set into training and validation data sets by random selection of cases. Let us assume that we have constructed a classifier using the training data. When we apply it to the validation data, we will classify each case into C0 or C1. The resulting misclassification errors can be displayed in what is known as a confusion table, with rows and columns corresponding to the true and predicted classes respectively. We can summarize our results in a confusion table for training data in a similar fashion. The resulting confusion table will not give us an honest estimate of the misclassification rate due to over-fitting. However such a table will be useful to signal overfitting when it has substantially lower misclassification rates than the confusion table for validation data. Predicted Class Confusion Table (Validation Cases) True Class C0 C1 C0 True Negatives (Number of correctly classified cases that belong to C0) False Positives (Number of cases incorrectly classified as C1 that belong to C0) C1 False Negatives (Number of cases incorrectly classified as C0 that belong to C1) True Positives (Number of correctly classified cases that belong to C1) If we denote the number in the cell at row i and column j by Nij, the estimated misclassification rate Err = ( N 01 + N 10 ) / N val where N val ≡ ( N 00 + N 01 + N10 + N 11 ) , or the total number of cases in the validation data set. If Nval is reasonably large, our estimate of the misclassification 1 There are classifiers that focus on simply finding the boundary between the regions to predict each class without being concerned with estimating the density of cases within each region. For example, Support Vector Machine classifiers have this characteristic. 5 rate is probably quite accurate. We can compute a confidence interval for Err using the standard formula for estimating a population proportion from a random sample. The table below gives an idea of how the accuracy of the estimate varies with Nval . The column headings are values of the misclassification rate and the rows give the desired accuracy in estimating the misclassification rate as measured by the half-width of the confidence interval at the 99% confidence level. For example, if we think that the true misclassification rate is likely to be around 0.05 and we want to be 99% confident that Err is within ± 0.01 of the true misclassification rate, we need to have a validation data set with 3,152 cases. 0.01 0.05 250 504 ±0.025 657 3,152 ±0.010 ±0.005 2,628 12,608 0.10 956 5,972 23,889 0.15 1,354 8,461 33,842 0.20 1,699 10,617 42,469 0.30 2,230 13,935 55,741 0.40 2,548 15,926 63,703 0.50 2,654 16,589 66,358 Note that we are assuming that the cost (or benefit) of making correct classifications is zero. At first glance, this may seem incomplete. After all, the benefit (negative cost) of correctly classifying a buyer as a buyer would seem substantial. And, in other circumstances (e.g. calculating the expected profit from having a new mailing list ), it will be appropriate to consider the actual net dollar impact of classifying each case on the list. Here, however, we are attempting to assess the value of a classifier in terms of misclassifications, so it greatly simplifies matters if we can capture all cost/benefit information in the misclassification cells. So, instead of recording the benefit of correctly classifying a buyer, we record the cost of failing to classify him as a buyer. It amounts to the same thing. In fact the costs we are using are the opportunity costs. 6 Asymmetric misclassification costs and Bayes’ Risk Up to this point we have been using the misclassification error rate as the criterion for judging the efficacy of a classifier. However, there are circumstances when this measure is not appropriate. Sometimes the error of misclassifying a case belonging to one class is more serious than for the other class. For example, misclassifying a household as unlikely to respond to a sales offer when it belongs to the class that would respond incurs a greater opportunity cost than the converse error. In such a scenario using misclassification error as a criterion can be misleading. Consider the situation where the sales offer is accepted by 1% of the households on a list. If a classifier simply classifies every household as a non-responder it will have an error rate of only 1% but will be useless in practice. A classifier that misclassifies 30% of buying households as non-buyers and 2% of the non-buyers as buyers would have a higher error rate but would be better if the profit from a sale is substantially higher than the cost of sending out an offer. In these situations, if we have estimates of the cost of both types of misclassification, we can use the confusion table to compute the expected cost of misclassification for each case in the validation data. This enables us to compare different classifiers using opportunity cost as the criterion. This may suffice for some situations, but a better method would be to change the classification rules (and hence the misclassification rates) to reflect the asymmetric costs. In fact, there is a Bayes classifier for this situation which gives rules that are optimal for minimizing the expected opportunity loss from misclassification. This classifier is known as the Bayes’ Risk Classifier and the corresponding minimum expected opportunity cost of misclassification is known as the Bayes’ Risk. The Bayes’ Risk Classifier employs the following classification rule: | ) > p(C0 ) × f 0 ( x0 ) × C (10 | ) , and to Classify a case as belonging to C1 if p(C1 ) × f 1 ( x0 ) × C (01 C0 , otherwise. Here C(0|1) is the opportunity cost of misclassifying a C1 case as belonging to C0 and C(1|0) is the opportunity cost of misclassifying a C0 case as belonging to C1. Note that the opportunity cost of correct classification for either class is zero. Notice also that this rule reduces to the Minimum Error Bayes Rule when C(0|1) = C(1|0). Again, as we rarely know f 1 ( x ) and f 0 ( x ) , we cannot construct this classifier in practice. Nonetheless, it provides us with an ideal that the various classifiers we construct for minimizing expected opportunity cost attempt to emulate. The method used most often in practice is to use stratified sampling instead of random sampling so as to change the ratio of cases in the training set to reflect the relative costs of making the two types of misclassification errors. 7 Stratified sampling to make the classifier sensitive to asymmetric costs The basic idea in using stratified sampling is to oversample the cases from a class to increase the weight given to errors made in classifying cases in that class. If we feel that the opportunity cost of misclassifying a class C1 case as a C0 case is ten times that of misclassifying a class C0 case as a C1 case, we randomly sample ten times as many C1 cases as we randomly sample C0 cases. By virtue of this oversampling, the training data will automatically tune the classifier to be more accurate in classifying C1 cases than C0 cases. Most of the time the class that has a higher misclassification cost will be the less frequently occurring class (for example fraudulent cases). In this situation rather than reduce the number of cases that are not fraudulent to a small fraction of the fraud cases and thus have a drastic reduction in the training data size, a good thumb rule often used in practice is to sample an equal number of cases from each class. This is a very commonly used option as it tends to produce rules that are quite efficient relative to the best over a wide range of misclassification cost ratios. Generalization to more than two classes All the comments made above about two-class classifiers extend readily to classification into more than two classes. Let us suppose we have k classes C0, C1, C2, … Ck-1. Then Bayes formula gives us: p ( C j | X = x0 ) = f j ( x0 ) p ( C j ) k −1 ¦ f ( x ) p( C ) i 0 i i =1 The Bayes Rule for Minimum Error is to classify a case as belonging to Cj if p(C j ) × f j ( x0 ) ≥ Max p(Ci ) × f i ( x0 ) . i = 0 ,1, k −1 The confusion table has k rows and k columns. The opportunity cost associated with the diagonal cells is always zero. If the costs are asymmetric the Bayes Risk Classifier follows the rule: Classify a case as belonging to C1 if p(C j ) × f j ( x0 ) × C (~ j| j ) ≥ Max p(Ci ) × f i ( x0 ) × C (~ i|i ) . i≠ j where C(~j|j) is the cost of misclassifying a case that belongs to Cj to any other class Ci, i ≠ j. 8 Lift Charts for two-class classifiers Often in practice, opportunity costs are not known accurately and decision makers would like to examine a range of possible opportunity costs. In such cases, when the classifier gives a probability of belonging to each class and not just a binary (or “hard”) classification to C1 or C0, we can use a very useful device known as the lift curve. The lift curve is a popular technique in direct marketing. The input required to construct a lift curve is a validation data set that has been “scored” by appending the probability predicted by a classifier to each case. In fact we can use classifiers that do not predict probabilities but give scores that enable us to rank cases in order of how likely the cases are to belong to one of the classes. Example: Boston Housing (Two classes) Let us fit a logistic regression model to the Boston Housing data. We fit a logistic regression model to the training data (304 randomly selected cases) with all the 13 variables available in the data set as predictor variables and with the binary variable HICLASS (high valued property neighborhood) as the dependent variable. The model coefficients are applied to the validation data (the remaining 202 cases in the data set). The first three columns of XLMiner output for the first 30 cases in the validation data are shown below. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Predicted Log-odds of Success Predicted Prob. of Success Actual Value of HICLASS 3.5993 0.9734 1 -6.5073 0.0015 0 0.4061 0.6002 0 -14.2910 0.0000 0 4.5273 0.9893 1 -1.2916 0.2156 0 -37.6119 0.0000 0 -1.1157 0.2468 0 -4.3290 0.0130 0 -24.5364 0.0000 0 -21.6854 0.0000 0 -19.8654 0.0000 0 -13.1040 0.0000 0 4.4472 0.9884 1 3.5294 0.9715 1 3.6381 0.9744 1 -2.6806 0.0641 0 -0.0402 0.4900 0 -10.0750 0.0000 0 -10.2859 0.0000 0 -14.6084 0.0000 0 8.9016 0.9999 1 0.0874 0.5218 0 -6.0590 0.0023 1 -1.9183 0.1281 1 -13.2349 0.0000 0 9 27 28 29 30 -9.6509 0.0001 0 -13.4562 0.0000 0 -13.9340 0.0000 0 1.7257 0.8489 1 The same 30 cases are shown below sorted in descending order of the predicted probability of being a HCLASS=1 case. 22 5 14 16 1 15 30 3 23 18 8 6 25 17 9 24 2 27 19 20 13 26 28 29 4 21 12 11 10 7 Predicted Log-odds of Success Predicted Prob. of Success Actual Value of HICLASS 8.9016 0.9999 1 4.5273 0.9893 1 4.4472 0.9884 1 3.6381 0.9744 1 3.5993 0.9734 1 3.5294 0.9715 1 1.7257 0.8489 1 0.4061 0.6002 0 0.0874 0.5218 0 -0.0402 0.4900 0 -1.1157 0.2468 0 -1.2916 0.2156 0 -1.9183 0.1281 1 -2.6806 0.0641 0 -4.3290 0.0130 0 -6.0590 0.0023 1 -6.5073 0.0015 0 -9.6509 0.0001 0 -10.0750 0.0000 0 -10.2859 0.0000 0 -13.1040 0.0000 0 -13.2349 0.0000 0 -13.4562 0.0000 0 -13.9340 0.0000 0 -14.2910 0.0000 0 -14.6084 0.0000 0 -19.8654 0.0000 0 -21.6854 0.0000 0 -24.5364 0.0000 0 -37.6119 0.0000 0 First, we need to set a cutoff probability value, above which we will consider a case to be a positive or "1," and below which we will consider a case to be a negative or "0." For any given cutoff level, we can use the sorted table to compute a confusion table for a given cut-off probability. For example, if we use a cut-off probability level of 0.400, we will predict 10 positives (7 true positives and 3 false positives); we will also predict 20 negatives (18 true negatives and 2 false negatives). For each cut-off level, we can calculate the appropriate confusion table. Instead of looking at a large number of confusion tables, it is much more convenient to look at the cumulative lift curve (sometimes called a gains chart) which 10 summarizes all the information in these multiple confusion tables into a graph. The graph is constructed with the cumulative number of cases (in descending order of probability) on the x axis and the cumulative number of true positives on the y axis as shown below. Probability Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Predicted Prob. of Success Actual cumulative Value of Actual Value HICLASS 0.9999 1 0.9893 1 0.9884 1 0.9744 1 0.9734 1 0.9715 1 0.8489 1 0.6002 0 0.5218 0 0.4900 0 0.2468 0 0.2156 0 0.1281 1 0.0641 0 0.0130 0 0.0023 1 0.0015 0 0.0001 0 0.0000 0 0.0000 0 0.0000 0 0.0000 0 0.0000 0 0.0000 0 0.0000 0 0.0000 0 0.0000 0 0.0000 0 0.0000 0 0.0000 0 1 2 3 4 5 6 7 7 7 7 7 7 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 The cumulative lift chart is shown below. 11 Cumulative positives Cumulative Lift 10 9 8 7 6 5 4 3 2 1 0 0 5 10 15 20 25 30 35 Score rank The line joining the points (0,0) to (30,9) is a reference line. It represents the expected number of positives we would predict if we did not have a model but simply selected cases at random. It provides a benchmark against which we can see performance of the model. If we had to choose 10 neighborhoods as HICLASS=1 neighborhoods and used our model to pick the ones most likely to be "1's,", the lift curve tells us that we would be right about 7 of them. If we simply select 10 cases at random we expect to be right for 10 × 9/30 = 3 cases. The model gives us a "lift" in predicting HICLASS of 7/3 = 2.33. The lift will vary with the number of cases we choose to act on. A good classifier will give us a high lift when we act on only a few cases (i.e. use the prediction for the ones at the top). As we include more cases the lift will decrease. The lift curve for the best possible classifier is shown as a broken line. XLMiner automatically creates lift charts from probabilities predicted by logistic regression for both training and validation data. The charts created for the full Boston Housing data are shown below. 12 Lift chart (validation dataset) 45 40 Cumulative HIGHCLASS when sorted using predicted values Cumulative 35 30 25 20 Cumulative HIGHCLASS using average 15 10 5 0 0 100 200 300 # cases Lift chart (training dataset) 45 40 Cumulative HIGHCLASS when sorted using predicted values Cumulative 35 30 25 20 Cumulative HIGHCLASS using average 15 10 5 0 0 100 200 300 400 # cases It is worth mentioning that a curve that captures the same information as the lift curve in a slightly different manner is also popular in data mining applications. This is the ROC (short for Receiver Operating Characteristic) curve. It uses the same variable on the y axis as the lift curve (but expressed as a percentage of the maximum) and on the x axis it shows the false positives (also expressed as a percentage of the maximum) for differing cut-off levels. 13 The ROC curve for our 30 cases example above is shown below. 100.0% 90.0% True Positive Cases% 80.0% 70.0% 60.0% 50.0% 40.0% 30.0% 20.0% 10.0% 0.0% 0.0% 20.0% 40.0% 60.0% 80.0% 100.0% False Positive Cases % 14 Classification using a Triage strategy In some cases it is useful to have a “can’t say” option for the classifier. In a two-class situation this means that for a case we can make one of three predictions. The case belongs to C0, or the case belongs to C1, or we cannot make a prediction because there is not enough information to confidently pick C0 or C1. Cases that the classifier cannot classify are subjected to closer scrutiny either by using expert judgment or by enriching the set of predictor variables by gathering additional information that is perhaps more difficult or expensive to obtain. This is analogous to the strategy of triage that is often employed during retreat in battle. The wounded are classified into those who are well enough to retreat, those who are too ill to retreat even if medically treated under the prevailing conditions, and those who are likely to become well enough to retreat if given medical attention. An example is in processing credit card transactions where a classifier may be used to identify clearly legitimate cases and the obviously fraudulent ones while referring the remaining cases to a human decision-maker who may look up a database to form a judgment. Since the vast majority of transactions are legitimate, such a classifier would substantially reduce the burden on human experts. To gain some insight into forming such a strategy let us revisit the simple two-class, one predictor variable, classifier that we examined at the beginning of this chapter. f1(x) f0(x) a “Grey” area x Clearly the grey area of greatest doubt in classification is the area around a. At a the ratio of the conditional probabilities of belonging to the classes is one. A sensible rule way to define the grey area is the set of x values such that: t> p(C1 ) × f 1 ( x0 ) > 1/ t p(C0 ) × f 0 ( x0 ) where t is a threshold for the ratio. A typical value of t may in the range 1.05 or 1.2. 15