Estimating ROC/AUC on large data sets?

Plotting an ROC curve of a classifier compared to cases requires that the data set be sorted first on the classifier score. I am in a position where I need to calculate ROC on a large data set very quickly and sorting is the bottleneck (even using quicksort in C or F90). If instead of calculating ROC by thresholding at each case in the data set I instead threshold at every 100 cases then my execution time decreases by orders of magnitude based upon how I can write the code. The result is an ROC curve with let's say 10,000 points instead of 1,000,000. My tests show that the area under these two curves are the same out to > 5 decimal places.

I would like to use this method but have not ran into anyone trying to speed up calculation in this way. Most of the lit. is on uses of ROC analysis where the data sets are relatively small and execution time is not an issue, so I have not found anyone else using this method or another to speed calculation by "thinning" out the points on the curve.

Has anyone ran into a reference/study that has used or evaluated this or another method for speeding up ROC analysis? If so, or if you have other thoughts, please share.

• Why threshold at every 100 cases rather than select a sample of 10,000 cases? Oct 29 '13 at 16:58
• To have a larger sample size between thresholds. Instead of each point in the ROC being estimated by a single comparison, it is estimated by 100. Oct 29 '13 at 17:17

It makes sense to take a large random sample of N cases (10,000) to estimate the real distribution (the full 1 million). The area under the curve will be an approximate, but a very good approximate as N increases.

If this is something that needs to be done frequently, you can try the ROC calculation with increasingly large sample sizes to find an optimally large sub-set. Optimal here would mean that the loss of information is acceptable. Be warned that a random sample needs to still be representative of the full dataset (whatever that means for your study).

I can't cite any literature off-hand, but I know this type of sampling is used often in practice for different reasons. I for one often use sampling to reduce a large data-set (1-2 million) to something more easily handled (~5-10K) before starting on a data analysis.

• Sure, but I think it is obvious that estimating each of the 10,000 points on the ROC curve using 100 data points for each of the 10,000 is superior to doing so with 1 data point each. Oct 29 '13 at 21:02
• Superior in the sense that you don't lose any information. So if the curve with 1 data point per 10,000 is the same as the full curve, then you haven't lost much accuracy. Try testing with different sample sizes. Oct 31 '13 at 5:54
• I have. On sample data sets, my estimation technique is accurate to > 5 decimal places. I found no previous work doing this, so I just stated in the manuscript what my test results were. The advantage here is that I do not have to worry about my sample being representative,because there are not samples.I need to worry instead of whether or not my number of 'slices' are sufficient. It seems that it is.Taking a sample would actually slow the process down as I would have to visit each cell once more.I am writing this ground up in a compiled language. Nov 13 '13 at 4:10

This does not really answer your question, I guess, but it is too long for a comment so here goes.

If instead of calculating ROC by thresholding at each case in the data set I instead threshold at every 100 cases then my execution time decreases by orders of magnitude based upon how I can write the code. The result is an ROC curve with let's say 10,000 points instead of 1,000,000. My tests show that the area under these two curves are the same out to > 5 decimal places.

I don't see why this makes such a large difference. In either scenario you will need to sort all scores (the supposed bottleneck). After they are sorted it is trivial to compute the ROC curve for all distinct scores simply by iterating over the sorted scores. If you implement this properly you will not lose orders of magnitude of speed when using all scores.

It sounds to me like you have an overly complex implementation of computing the ROC curve. Your speedup still requires sorting the scores, after which you may as well use all distinct scores. Using all distinct scores will require more memory but if you deal with such huge data sets I assume this won't be an issue at all. The difference won't be orders of magnitude anyway.

• It is much easier to sort two lists of 50 data points than one list of 100 data points. Therefore, splitting into descending classes using some easy method such as a stretch function and then sorting each class alone will ordinarily be much faster. This is shown by looking at the sort time for various algorithms and then playing with the number of points sorted and then multiplying to get the total time based upon number of groups. This is because all sorting algorithms scale nonlinearly with number of points sorted. No algorithm that I know of benefits from lumping points together. Jul 9 '14 at 7:47