Data Mining: The Textbook
Yüklə 17,13 Mb.
|
10.9.1.3 Bootstrap In the bootstrap method, the labeled data is sampled uniformly with replacement, to create a training data set, which might possibly contain duplicates. The labeled data of size n is sampled n times with replacement. This results in a training data with the same size as the original labeled data. However, the training typically contains duplicates and also misses some points in the original labeled data. The probability that a particular data point is not included in a sample is given by (1−1/n). Therefore, the probability that the data point is not included in n samples is given by (1 − 1/n)n . For large values of n, this expression evaluates to approximately 1/e, where e is the base of the natural logarithm. The fraction of the labeled data points included at least once in the training data is therefore 1 − 1/e ≈ 0.632. The training model M is constructed on the bootstrapped sample containing duplicates. The overall accuracy is computed using the original set of full labeled data as the test examples. The estimate is highly optimistic of the true classifier accuracy because of the large overlap between training and test examples. In fact, a 1-nearest neighbor classifier will always yield 100 % accuracy for the portion of test points included in the bootstrap sample and the estimates are therefore not realistic in many scenarios. By repeating the process over b different bootstrap samples, the mean and the variance of the error estimates may be determined. A better alternative is to use leave-one-out bootstrap. In this approach, the accuracy A(X) of each labeled instance X is computed using the classifier performance on only the subset of the b bootstrapped samples in which X is not a part of the bootstrapped sample of training data. The overall accuracy Al of the leave-one-out bootstrap is the mean value of A(X ) over all labeled instances X. This approach provides a pessimistic accuracy estimate. The 0.632-bootstrap further improves this accuracy with a “compromise” approach. The average training-data accuracy At over the b bootstrapped samples is computed. This is a highly optimistic estimate. For example, At will always be 100 % for a 1-nearest neighbor classifier. The overall accuracy A is a weighted average of the leave-one-out accuracy and the training-data accuracy.
In spite of the compromise approach, the estimates of 0.632 bootstrap are usually optimistic. The bootstrap method is more appropriate when the size of the labeled data is small. 10.9.2 Quantification Issues This section will discuss how the quantification of the accuracy of a classifier is performed after the training and test set for a classifier are fixed. Several measures of accuracy are used depending on the nature of the classifier output: In most classifiers, the output is predicted in the form of a label associated with the test instance. In such cases, the ground-truth label of the test instance is compared with the predicted label to generate an overall value of the classifier accuracy. In many cases, the output is presented as a numerical score for each labeling possibility for the test instance. An example is the Bayes classifier where a probability is reported for a test instance. As a convention, it will be assumed that higher values of the score imply a greater likelihood to belong to a particular class. The following sections will discuss methods for quantifying accuracy in both scenarios. 338 CHAPTER 10. DATA CLASSIFICATION 10.9.2.1 Output as Class Labels When the output is presented in the form of class labels, the ground-truth labels are com-pared to the predicted labels to yield the following measures: Yüklə 17,13 Mb. Dostları ilə paylaş:
|