Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Using dynamical quantization to perform split attempts in online tree regressors

Full text
Author(s):
Mastelini, Saulo Martiello [1] ; Carvalho, Andre Carlos Ponce de Leon Ferreira de [1]
Total Authors: 2
Affiliation:
[1] Univ Sao Paulo, Inst Math & Comp Sci, BR-13566590 Sao Carlos - Brazil
Total Affiliations: 1
Document type: Journal article
Source: PATTERN RECOGNITION LETTERS; v. 145, p. 37-42, MAY 2021.
Web of Science Citations: 0
Abstract

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)

FAPESP's process: 18/07319-6 - Multi-target data stream mining
Grantee:Saulo Martiello Mastelini
Support Opportunities: Scholarships in Brazil - Doctorate