{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:23:26Z","timestamp":1740108206120,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T00:00:00Z","timestamp":1665014400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T00:00:00Z","timestamp":1665014400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"academy of finland","award":["311273","313266"],"award-info":[{"award-number":["311273","313266"]}]},{"name":"University of Turku (UTU) including Turku University Central Hospital"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Stat"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Receiver Operating Characteristic (ROC) curve analysis and area under the ROC curve (AUC) are commonly used performance measures in diagnostic systems. In this work, we assume a setting, where a classifier is inferred from multivariate data to predict the diagnostic outcome for new cases. Cross-validation is a resampling method for estimating the prediction performance of a classifier on data not used for inferring it. Tournament leave-pair-out (TLPO) cross-validation has been shown to be better than other resampling methods at producing a ranking of data that can be used for estimating the ROC curves and areas under them. However, the time complexity of TLPOCV,<jats:inline-formula><jats:alternatives><jats:tex-math>$$O\\left( n^2\\right)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mfenced><mml:msup><mml:mi>n<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><\/mml:mfenced><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, means that it is impractical in many applications. In this article, a method called quicksort leave-pair-out cross-validation (QLPOCV) is presented in order to decrease the time complexity of obtaining a reliable ranking of data to<jats:inline-formula><jats:alternatives><jats:tex-math>$$O\\left( n\\log n\\right)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mfenced><mml:mi>n<\/mml:mi><mml:mo>log<\/mml:mo><mml:mi>n<\/mml:mi><\/mml:mfenced><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The proposed method is compared with existing ones in an experimental study, demonstrating that in terms of ROC curves and AUC values QLPOCV produces as accurate performance estimation as TLPOCV, outperforming both<jats:italic>k<\/jats:italic>-fold and leave-one-out cross-validation.<\/jats:p>","DOI":"10.1007\/s00180-022-01288-3","type":"journal-article","created":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T15:10:23Z","timestamp":1665069023000},"page":"1579-1595","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Quicksort leave-pair-out cross-validation for ROC curve analysis"],"prefix":"10.1007","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2283-6290","authenticated-orcid":false,"given":"Riikka","family":"Numminen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ileana","family":"Montoya Perez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan","family":"Jambor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tapio","family":"Pahikkala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antti","family":"Airola","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,6]]},"reference":[{"key":"1288_CR1","unstructured":"Ailon N, Mohri M (2008) An efficient reduction of ranking to classification. In: 21st Annual Conference on Learning Theory, COLT (2008)"},{"issue":"4","key":"1288_CR2","doi-asserted-by":"publisher","first-page":"1828","DOI":"10.1016\/j.csda.2010.11.018","volume":"55","author":"A Airola","year":"2011","unstructured":"Airola A, Pahikkala T, Waegeman W, De Baets B, Salakoski T (2011) An experimental comparison of cross-validation techniques for estimating the area under the ROC curve. Comput Stat Data Anal 55(4):1828\u20131844","journal-title":"Comput Stat Data Anal"},{"issue":"1\u20132","key":"1288_CR3","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s10994-008-5058-6","volume":"72","author":"MF Balcan","year":"2008","unstructured":"Balcan MF, Bansal N, Beygelzimer A, Coppersmith D, Langford J, Sorkin GB (2008) Robust reductions from ranking to classification. Mach Learn 72(1\u20132):139\u2013153","journal-title":"Mach Learn"},{"issue":"1","key":"1288_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41746-020-00373-5","volume":"4","author":"V Berisha","year":"2021","unstructured":"Berisha V, Krantsevich C, Hahn PR, Hahn S, Dasarathy G, Turaga P, Liss J (2021) Digital medicine and the curse of dimensionality. NPJ Dig Med 4(1):1\u20138","journal-title":"NPJ Dig Med"},{"issue":"7","key":"1288_CR5","doi-asserted-by":"publisher","first-page":"1145","DOI":"10.1016\/S0031-3203(96)00142-2","volume":"30","author":"AP Bradley","year":"1997","unstructured":"Bradley AP (1997) The use of the area under the ROC curve in the evaluation of machine learning algorithms. Pattern Recogn 30(7):1145\u20131159","journal-title":"Pattern Recogn"},{"issue":"1","key":"1288_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1010933404324","volume":"45","author":"L Breiman","year":"2001","unstructured":"Breiman L (2001) Random forests. Mach Learn 45(1):5\u201332","journal-title":"Mach Learn"},{"key":"1288_CR7","unstructured":"Cormen T.H, Leiserson C.E, Rivest R.L (1990) Introduction to algorithms. MIT press"},{"issue":"3","key":"1288_CR8","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1037\/h0044139","volume":"70","author":"W Edwards","year":"1963","unstructured":"Edwards W, Lindman H, Savage LJ (1963) Bayesian statistical inference for psychological research. Psychol Rev 70(3):193","journal-title":"Psychol Rev"},{"issue":"8","key":"1288_CR9","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1016\/j.patrec.2005.10.010","volume":"27","author":"T Fawcett","year":"2006","unstructured":"Fawcett T (2006) An introduction to ROC analysis. Pattern Recogn Lett 27(8):861\u2013874","journal-title":"Pattern Recogn Lett"},{"issue":"1","key":"1288_CR10","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/1882471.1882479","volume":"12","author":"G Forman","year":"2010","unstructured":"Forman G, Scholz M (2010) Apples-to-apples in cross-validation studies: pitfalls in classifier performance measurement. ACM SIGKDD Explor Newsl 12(1):49\u201357","journal-title":"ACM SIGKDD Explor Newsl"},{"key":"1288_CR11","doi-asserted-by":"crossref","unstructured":"Ginsburg S, Tiwari P, Kurhanewicz J, Madabhushi A (2011) Variable ranking with PCA: Finding multiparametric MR imaging markers for prostate cancer diagnosis and grading. In: International Workshop on Prostate Cancer Imaging. Springer, pp 146\u2013157","DOI":"10.1007\/978-3-642-23944-1_15"},{"key":"1288_CR12","doi-asserted-by":"crossref","unstructured":"Golland P, Liang F, Mukherjee S, Panchenko D (2005) Permutation tests for classification. In: International conference on computational learning theory, pp. 501\u2013515. Springer","DOI":"10.1007\/11503415_34"},{"issue":"1","key":"1288_CR13","first-page":"1","volume":"12","author":"L Gon\u00e7alves","year":"2014","unstructured":"Gon\u00e7alves L, Subtil A, Oliveira MR, de Zea Bermudez P (2014) ROC curve estimation: an overview. REVSTAT-Statistical J 12(1):1\u201320","journal-title":"REVSTAT-Statistical J"},{"issue":"1","key":"1288_CR14","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1148\/radiology.143.1.7063747","volume":"143","author":"JA Hanley","year":"1982","unstructured":"Hanley JA, McNeil BJ (1982) The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology 143(1):29\u201336","journal-title":"Radiology"},{"key":"1288_CR15","unstructured":"Hastie T, Tibshirani R, Friedman J (2017) The elements of statistical learning, 2 edn. Springer series in statistics New York"},{"issue":"1","key":"1288_CR16","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","volume":"5","author":"CA Hoare","year":"1962","unstructured":"Hoare CA (1962) Quicksort. Comput J 5(1):10\u201316","journal-title":"Comput J"},{"issue":"1","key":"1288_CR17","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1080\/00401706.1970.10488634","volume":"12","author":"AE Hoerl","year":"1970","unstructured":"Hoerl AE, Kennard RW (1970) Ridge regression: biased estimation for nonorthogonal problems. Technometrics 12(1):55\u201367","journal-title":"Technometrics"},{"key":"1288_CR18","unstructured":"Iliopoulos V (2013) The quicksort algorithm and related topics. Ph.D. thesis, Department of Mathematical Sciences, University of Essex"},{"issue":"2","key":"1288_CR19","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1002\/jmri.21824","volume":"30","author":"DL Langer","year":"2009","unstructured":"Langer DL, Van der Kwast TH, Evans AJ, Trachtenberg J, Wilson BC, Haider MA (2009) Prostate cancer detection with multi-parametric MRI: Logistic regression analysis of quantitative t2, diffusion-weighted imaging, and dynamic contrast-enhanced MRI. J Magnet Resonance Imag: An Official J Int Soc Magnet Resonance in Med 30(2):327\u2013334","journal-title":"J Magnet Resonance Imag: An Official J Int Soc Magnet Resonance in Med"},{"issue":"4","key":"1288_CR20","doi-asserted-by":"publisher","first-page":"1422","DOI":"10.1111\/biom.13365","volume":"77","author":"DJ Luckett","year":"2021","unstructured":"Luckett DJ, Laber EB, El-Kamary SS, Fan C, Jhaveri R, Perou CM, Shebl FM, Kosorok MR (2021) Receiver operating characteristic curves and confidence bands for support vector machines. Biometrics 77(4):1422\u20131430","journal-title":"Biometrics"},{"issue":"5","key":"1288_CR21","doi-asserted-by":"publisher","first-page":"1954","DOI":"10.1002\/mrm.25310","volume":"73","author":"H Merisaari","year":"2015","unstructured":"Merisaari H, Jambor I (2015) Optimization of b-value distribution for four mathematical models of prostate cancer diffusion-weighted imaging using b values up to 2000 s\/mm2: simulation and repeatability study. Magn Reson Med 73(5):1954\u20131969","journal-title":"Magn Reson Med"},{"issue":"4","key":"1288_CR22","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/S0001-2998(78)80014-2","volume":"8","author":"CE Metz","year":"1978","unstructured":"Metz CE (1978) Basic principles of ROC analysis. Semin Nucl Med 8(4):283\u2013298","journal-title":"Semin Nucl Med"},{"issue":"10\u201311","key":"1288_CR23","doi-asserted-by":"publisher","first-page":"2975","DOI":"10.1177\/0962280218795190","volume":"28","author":"I Montoya Perez","year":"2019","unstructured":"Montoya Perez I, Airola A, Bostr\u00f6m PJ, Jambor I, Pahikkala T (2019) Tournament leave-pair-out cross-validation for receiver operating characteristic analysis. Stat Methods Med Res 28(10\u201311):2975\u20132991","journal-title":"Stat Methods Med Res"},{"key":"1288_CR24","doi-asserted-by":"crossref","unstructured":"Montoya Perez I, Toivonen J, Movahedi P, Merisaari H, Pesola M, Taimen P, Bostr\u00f6m P.J, Kiviniemi A, Aronen H.J, Pahikkala T, et al. Diffusion weighted imaging of prostate cancer: prediction of cancer using texture features from parametric maps of the monoexponential and kurtosis functions. In: 2016 Sixth International Conference on Image Processing Theory, Tools and Applications (IPTA), pp. 1\u20136. IEEE (2016)","DOI":"10.1109\/IPTA.2016.7820993"},{"issue":"1","key":"1288_CR25","first-page":"7803","volume":"17","author":"T Pahikkala","year":"2016","unstructured":"Pahikkala T, Airola A (2016) RLScore: regularized least-squares learners. J Mach Learn Res 17(1):7803\u20137807","journal-title":"J Mach Learn Res"},{"key":"1288_CR26","first-page":"1","volume":"2008","author":"T Pahikkala","year":"2008","unstructured":"Pahikkala T, Airola A, Boberg J, Salakoski T (2008) Exact and efficient leave-pair-out cross-validation for ranking RLS. Proceedings of AKRR 2008:1\u20138","journal-title":"Proceedings of AKRR"},{"issue":"1","key":"1288_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-8-326","volume":"8","author":"BJ Parker","year":"2007","unstructured":"Parker BJ, G\u00fcnter S, Bedo J (2007) Stratification bias in low signal microarray studies. BMC Bioinform 8(1):1\u201316","journal-title":"BMC Bioinform"},{"key":"1288_CR28","first-page":"2825","volume":"12","author":"F Pedregosa","year":"2011","unstructured":"Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, Prettenhofer P, Weiss R, Dubourg V, Vanderplas J, Passos A, Cournapeau D, Brucher M, Perrot M, Duchesnay E (2011) Scikit-learn: Machine learning in Python. J Mach Learn Res 12:2825\u20132830","journal-title":"J Mach Learn Res"},{"key":"1288_CR29","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509844.001.0001","volume-title":"The statistical evaluation of medical tests for classification and prediction","author":"MS Pepe","year":"2003","unstructured":"Pepe MS (2003) The statistical evaluation of medical tests for classification and prediction. Oxford University Press, USA"},{"key":"1288_CR30","first-page":"131","volume":"190","author":"R Rifkin","year":"2003","unstructured":"Rifkin R, Yeo G, Poggio T et al (2003) Regularized least-squares classification. Nato Sci Series Sub Series III Comput Syst Sci 190:131\u2013154","journal-title":"Nato Sci Series Sub Series III Comput Syst Sci"},{"key":"1288_CR31","unstructured":"Rifkin RM, Lippert RA (2007) Notes on regularized least squares. Tech. rep, Massachusetts Institute of Technology, Cambridge"},{"key":"1288_CR32","doi-asserted-by":"crossref","unstructured":"Shalev-Shwartz S, Ben-David S (2014)Understanding machine learning: From theory to algorithms. Cambridge university press","DOI":"10.1017\/CBO9781107298019"},{"issue":"2","key":"1288_CR33","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1177\/096228029900800203","volume":"8","author":"DE Shapiro","year":"1999","unstructured":"Shapiro DE (1999) The interpretation of diagnostic tests. Stat Methods Med Res 8(2):113\u2013134","journal-title":"Stat Methods Med Res"},{"issue":"3","key":"1288_CR34","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1093\/aje\/kwu140","volume":"180","author":"GC Smith","year":"2014","unstructured":"Smith GC, Seaman SR, Wood AM, Royston P, White IR (2014) Correcting for optimistic prediction in small data sets. Am J Epidemiol 180(3):318\u2013324","journal-title":"Am J Epidemiol"},{"issue":"4","key":"1288_CR35","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1002\/mrm.25482","volume":"74","author":"J Toivonen","year":"2015","unstructured":"Toivonen J, Merisaari H, Pesola M, Taimen P, Bostr\u00f6m PJ, Pahikkala T, Aronen HJ, Jambor I (2015) Mathematical models for diffusion-weighted imaging of prostate cancer using b values up to 2000 s\/mm2: Correlation with gleason score and repeatability of region of interest analysis. Magn Reson Med 74(4):1116\u20131124","journal-title":"Magn Reson Med"},{"issue":"1","key":"1288_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-7-91","volume":"7","author":"S Varma","year":"2006","unstructured":"Varma S, Simon R (2006) Bias in error estimation when using cross-validation for model selection. BMC Bioinform 7(1):1\u20138","journal-title":"BMC Bioinform"}],"container-title":["Computational Statistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00180-022-01288-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00180-022-01288-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00180-022-01288-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T14:53:25Z","timestamp":1701183205000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00180-022-01288-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,6]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1288"],"URL":"https:\/\/doi.org\/10.1007\/s00180-022-01288-3","relation":{},"ISSN":["0943-4062","1613-9658"],"issn-type":[{"type":"print","value":"0943-4062"},{"type":"electronic","value":"1613-9658"}],"subject":[],"published":{"date-parts":[[2022,10,6]]},"assertion":[{"value":"19 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author(s) declare(s) that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Data and results are available online:\u00a0.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Availability of data and material"}},{"value":"The code \u00a0is available\u00a0online:\u00a0.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}