Exploiting empirical variance for data stream classification |
| |
Authors: | Muhammad Zia-Ur Rehman Tian-rui Li and Tao Li |
| |
Institution: | [1]School of Information Science and Technology, Southwest Jiaotong University, Chenggdu 610031, China; [2]School of Computer Science, Florida International University, Miami 33199, USA) |
| |
Abstract: | Classification, using the decision tree algorithm, is a widely studied problem in data streams. The challenge is when to split
a decision node into multiple leaves. Concentration inequalities, that exploit variance information such as Bernstein’s and
Bennett’s inequalities, are often substantially strict as compared with Hoeffding’s bound which disregards variance. Many
machine learning algorithms for stream classification such as very fast decision tree (VFDT) learner, AdaBoost and support
vector machines (SVMs), use the Hoeffding’s bound as a performance guarantee. In this paper, we propose a new algorithm based
on the recently proposed empirical Bernstein’s bound to achieve a better probabilistic bound on the accuracy of the decision
tree. Experimental results on four synthetic and two real world data sets demonstrate the performance gain of our proposed
technique. |
| |
Keywords: | |
本文献已被 维普 SpringerLink 等数据库收录! |
|