基于红黑树的连续属性数据流快速决策树分类算法

摘要

以提高连续属性数据流的分类挖掘效率为目标,设计并实现了一种基于红黑树的连续属性数据流快速决策树分类算法VFDT_RBT。该算法利用红黑树来更有效地处理样本的插入,使得有序插入时的时间复杂度仍为O(nlogn);利用堆栈和红黑树中序遍历有序的特点来降低最佳划分阈值选取过程的时间复杂度;利用hoeffding不等式确定连续属性划分阈值所需的样本数量;在允许连续属性多次出现的原则下选择划分属性建立决策树,提高了算法的分类精度。在多个数据集上的分类实验结果表明:VFDT_RBT比已有的VFDTc具有更低的时间复杂度和更高的分类精度,更适合处理多属性样本。