Using dynamical quantization to perform split attempts in online tree regressors

Autor(es)

Mastelini, Saulo Martiello ^[1] ; Carvalho, Andre Carlos Ponce de Leon Ferreira de ^[1]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Math & Comp Sci, BR-13566590 Sao Carlos - Brazil

• Tipo de documento: Artigo Científico
• Fonte: PATTERN RECOGNITION LETTERS; v. 145, p. 37-42, MAY 2021.
• Citações Web of Science: 0

Resumo

A central aspect of online decision trees is evaluating the incoming data and performing model growth. For such, trees much deal with different kinds of input features. Numerical features are no exception, and they pose additional challenges compared to other kinds of features, as there is no trivial strategy to choose the best point to make a split decision. Regression tasks are even more challenging because both the features and the target are continuous. Typical online solutions evaluate and store all the points monitored between split attempts, which goes against the constraints posed in real-time applications. In this paper, we introduce the Quantization Observer (QO), a simple yet effective hashing-based algorithm to monitor and evaluate split candidates in numerical features for online tree regressors. QO can be easily integrated into incremental decision trees, such as Hoeffding Trees, and it has a monitoring cost of O (1) per instance and a sub-linear cost to evaluate split candidates. Previous solutions had a O(logn) cost per insertion (in the best case) and a linear cost to evaluate split candidates. Our extensive experimental setup highlights QO's effectiveness in providing accurate split point suggestions while spending much less memory and processing time than its competitors. (C) 2021 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 18/07319-6 - Mineração multi-alvos em fluxos de dados
• Beneficiário: Saulo Martiello Mastelini
• Modalidade de apoio: Bolsas no Brasil - Doutorado