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 informa...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.展开更多
基金the National Natural Science Foundation of China(Nos.60873108,61175047 and 61152001)the Fundamental Research Funds for the Central Universities of China(No.SWJTU11ZT08)
文摘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.
