基于McDiarmid不等式的决策树分类算法

摘要

大多数处理数据流的决策树方法是基于Hoeffding不等式设计的。但是Hoeffding不等式本身只能处理数值数据流,并且在属性度量方面存在不足。为了解决这个问题,文章在Hoeffding不等式算法的基础上引入McDiarmid不等式,将二者融合并做了相应的改进作为新的属性度量选择,提出了一种基于McDiarmid不等式的新决策树分类算法,即McTree。该算法使用ε/2进行属性分类度量来提高分类性能。在真实与虚拟数据流上的实验结果表明,McTree与经典算法相比,在分类精度升高或几乎保持不变的情况下,生成树的规模明显降低。其中生成树节点数平均降低70%左右,树层数平均降低50%左右。