{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:31:33Z","timestamp":1740123093581,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,12,14]],"date-time":"2021-12-14T00:00:00Z","timestamp":1639440000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,14]],"date-time":"2021-12-14T00:00:00Z","timestamp":1639440000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Helsinki including Helsinki University Central Hospital"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2022,8]]},"abstract":"Abstract<\/jats:title>Measuring the performance of a classifier is a vital task in machine learning. The running time of an algorithm that computes the measure plays a very small role in an offline setting, for example, when the classifier is being developed by a researcher. However, the running time becomes more crucial if our goal is to monitor the performance of a classifier over time. In this paper we study three algorithms for maintaining two measures. The first algorithm maintains area under the ROC curve (AUC) under addition and deletion of data points in $$\\mathcal {O} \\mathopen {}\\left( \\log n\\right)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n \n log<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. This is done by maintaining the data points sorted in a self-balanced search tree. In addition, we augment the search tree that allows us to query the ROC coordinates of a data point in $$\\mathcal {O} \\mathopen {}\\left( \\log n\\right)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n \n log<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. In doing so we are able to maintain AUC in $$\\mathcal {O} \\mathopen {}\\left( \\log n\\right)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n \n log<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. Our next two algorithms involve in maintaining H<\/jats:italic>-measure, an alternative measure based on the ROC curve. Computing the measure is a two-step process: first we need to compute a convex hull of the ROC curve, followed by a sum over the convex hull. We demonstrate that we can maintain the convex hull using a minor modification of the classic convex hull maintenance algorithm. We then show that under certain conditions, we can compute the H<\/jats:italic>-measure exactly in $$\\mathcal {O} \\mathopen {}\\left( \\log ^2 n\\right)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n \n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, and if the conditions are not met, then we can estimate the H<\/jats:italic>-measure in $$\\mathcal {O} \\mathopen {}\\left( (\\log n + \\epsilon ^{-1})\\log n\\right)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n \n \u03f5<\/mml:mi>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. We show empirically that our methods are significantly faster than the baselines.<\/jats:p>","DOI":"10.1007\/s10994-021-06084-6","type":"journal-article","created":{"date-parts":[[2021,12,14]],"date-time":"2021-12-14T17:04:37Z","timestamp":1639501477000},"page":"2839-2862","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maintaining AUC and H-measure over time"],"prefix":"10.1007","volume":"111","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2087-5360","authenticated-orcid":false,"given":"Nikolaj","family":"Tatti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,12,14]]},"reference":[{"key":"6084_CR1","doi-asserted-by":"crossref","unstructured":"Ataman, K., Streetr, W., & Zhang, Y. (2006). Learning to rank by maximizing auc with linear programming. In IEEE international joint conference on neural networks, IJCNN\u201906, 2006 (pp. 123\u2013129).","DOI":"10.1109\/IJCNN.2006.246669"},{"key":"6084_CR2","doi-asserted-by":"crossref","unstructured":"Bifet, A., & Frank, E. (2010). Sentiment knowledge discovery in twitter streaming data. In Discovery science (pp. 1\u201315). Springer.","DOI":"10.1007\/978-3-642-16184-1_1"},{"key":"6084_CR3","doi-asserted-by":"crossref","unstructured":"Bouckaert, R.R. (2006). Efficient AUC learning curve calculation. In Australasian joint conference on artificial intelligence (pp. 181\u2013191).","DOI":"10.1007\/11941439_22"},{"key":"6084_CR4","doi-asserted-by":"crossref","unstructured":"Brefeld, U., & Scheffer, T. (2005). Auc maximizing support vector learning. In Proceedings of the ICML 2005 workshop on ROC analysis in machine learning","DOI":"10.1145\/1015330.1015350"},{"key":"6084_CR5","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., & Jacob, R. (2002). Dynamic planar convex hull. In The 43rd annual IEEE symposium on foundations of computer science, 2002. Proceedings (pp. 617\u2013626). IEEE","DOI":"10.1109\/SFCS.2002.1181985"},{"issue":"2","key":"6084_CR6","first-page":"531","volume":"52","author":"D Brzezinski","year":"2017","unstructured":"Brzezinski, D., & Stefanowski, J. (2017). Prequential AUC: Properties of the area under the ROC curve for data streams with concept drift. KAIS, 52(2), 531\u2013562.","journal-title":"KAIS"},{"key":"6084_CR7","doi-asserted-by":"crossref","unstructured":"Calders, T., & Jaroszewicz, S.: Efficient AUC optimization for classification. In PKDD (pp. 42\u201353).","DOI":"10.1007\/978-3-540-74976-9_8"},{"issue":"1","key":"6084_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10994-006-8199-5","volume":"65","author":"C Drummond","year":"2006","unstructured":"Drummond, C., & Holte, R. C. (2006). Cost curves: An improved method for visualizing classifier performance. Machine Learning, 65(1), 95\u2013130.","journal-title":"Machine Learning"},{"key":"6084_CR9","unstructured":"Ferri, C., Flach, P., & Hern\u00e1ndez-Orallo, J. (2002). Learning decision trees using the area under the ROC curve. In ICML (vol.\u00a02, pp. 139\u2013146)"},{"key":"6084_CR10","unstructured":"Flach, P.A., Hern\u00e1ndez-Orallo, J., & Ramirez, C.F.: A coherent interpretation of auc as a measure of aggregated classification performance. In: ICML (2011)"},{"key":"6084_CR11","doi-asserted-by":"publisher","DOI":"10.1201\/EBK1439826119","volume-title":"Knowledge discovery from data streams","author":"J Gama","year":"2010","unstructured":"Gama, J. (2010). Knowledge discovery from data streams. Boca Raton: CRC Press."},{"issue":"3","key":"6084_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s10994-012-5320-9","volume":"90","author":"J Gama","year":"2013","unstructured":"Gama, J., Sebasti\u00e3o, R., & Rodrigues, P. P. (2013). On evaluating stream learning algorithms. Machine Learning, 90(3), 317\u2013346.","journal-title":"Machine Learning"},{"issue":"4","key":"6084_CR13","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1145\/2523813","volume":"46","author":"J Gama","year":"2014","unstructured":"Gama, J., \u017dliobait\u0117, I., Bifet, A., Pechenizkiy, M., & Bouchachia, A. (2014). A survey on concept drift adaptation. ACM Computing Surveys, 46(4), 44.","journal-title":"ACM Computing Surveys"},{"issue":"1","key":"6084_CR14","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s10994-009-5119-5","volume":"77","author":"DJ Hand","year":"2009","unstructured":"Hand, D. J. (2009). Measuring classifier performance: A coherent alternative to the area under the ROC curve. Machine Learning, 77(1), 103\u2013123.","journal-title":"Machine Learning"},{"key":"6084_CR15","doi-asserted-by":"crossref","unstructured":"Herschtal, A., & Raskutti, B. (2004). Optimising area under the roc curve using gradient descent. In Proceedings of the twenty-first international conference on machine learning (p.\u00a049). ACM.","DOI":"10.1145\/1015330.1015366"},{"key":"6084_CR16","doi-asserted-by":"crossref","unstructured":"Mann, H.B., & Whitney, D.R. (1947). On a test of whether one of two random variables is stochastically larger than the other. In The Annals of Mathematical Statistics (pp. 50\u201360).","DOI":"10.1214\/aoms\/1177730491"},{"issue":"1","key":"6084_CR17","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J Nievergelt","year":"1973","unstructured":"Nievergelt, J., & Reingold, E. M. (1973). Binary search trees of bounded balance. SIAM Journal on Computing, 2(1), 33\u201343.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"6084_CR18","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"MH Overmars","year":"1981","unstructured":"Overmars, M. H., & Van Leeuwen, J. (1981). Maintenance of configurations in the plane. Journal of computer and System Sciences, 23(2), 166\u2013204.","journal-title":"Journal of computer and System Sciences"},{"key":"6084_CR19","doi-asserted-by":"crossref","unstructured":"Tatti, N. (2018). Efficient estimation of auc in a sliding window. In ECML PKDD (pp. 671\u2013686).","DOI":"10.1007\/978-3-030-10925-7_41"},{"issue":"3","key":"6084_CR20","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s10994-014-5441-4","volume":"98","author":"I \u017dliobait\u0117","year":"2015","unstructured":"\u017dliobait\u0117, I., Bifet, A., Read, J., Pfahringer, B., & Holmes, G. (2015). Evaluation methods and decision theory for classification of streaming data with temporal dependence. Machine Learning, 98(3), 455\u2013482.","journal-title":"Machine Learning"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06084-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-06084-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06084-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T20:09:51Z","timestamp":1659384591000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-06084-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,14]]},"references-count":20,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["6084"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-06084-6","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2021,12,14]]},"assertion":[{"value":"12 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 December 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}