Forest trees for on-line data

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2004

Autores

Gama, J (Autor) FEP; Medas, P (Autor) Outra; Rocha, R (Autor) Outra

Ata de Conferência Internacional

Título: Proceedings of the ACM Symposium on Applied Computing

Páginas: 632-636

Applied Computing 2004 - Proceedings of the 2004 ACM Symposium on Applied Computing

Nicosia, 14 March 2004 through 17 March 2004

Indexação

ISI Web of Knowledge

Scopus - 62 Citações

Outras Informações

ID Authenticus: P-007-DYY

DOI: 10.1145/967900.968033

Abstract (EN): This paper presents an hybrid adaptive system for induction of forest of trees from data streams. The Ultra Fast Forest Tree system (UFFT) is an incremental algorithm, with constant time for processing each example, works online, and uses the Hoeffding bound to decide when to install a splitting test in a leaf leading to a decision node. Our system has been designed for continuous data. It uses analytical techniques to choose the splitting criteria, and the information gain to estimate the merit of each possible splitting-test. The number of examples required to evaluate the splitting criteria is sound, based on the Hoeffding bound. For multiclass problems,the algorithm builds a binary tree for each possible pair of classes, leading to a forest of trees. During the training phase the algorithm maintains a short term memory. Given a data stream, a fixed number of the most recent examples are maintained in a data-structure that supports constant time insertion and deletion. When a test is installed, a leaf is transformed into a decision node with two descendant leaves. The sufficient statistics of these leaves are initialized with the examples in the short term memory that will fall at these leaves. We study the behavior of UFFT in different problems. The experimental results shows that UFFT is competitive against a batch decision tree learner in large and medium datasets.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 5