一种高效的数据流挖掘增量模糊决策树分类算法

被引：19

作者：

王涛 ^{[1
]}

李舟军 ^{[2
]}

胡小华 ^{[3
]}

颜跃进 ^{[1
]}

陈火旺 ^{[1
]}

机构：

[1] 国防科学技术大学计算机学院

[2] 北京航空航天大学计算机学院

[3] 德雷塞尔大学信息科学与技术学院

来源：

计算机学报 | 2007年 / 08期

关键词：

数据流; 线索化二叉排序树; 连续属性; 模糊离散化; 增量; VFDT;

D O I：

暂无

中图分类号：

TP181 [自动推理、机器学习]; TP311.13 [];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ; 1201 ;

摘要：

数据流具有数据持续到达、到达速度快、数据规模巨大等特点,这些都给数据流挖掘领域的研究工作带来了新挑战,而其中分类算法更是当前的研究热点.Domingos等在VFDT中利用Hoeffding不等式很好地解决了在数据流上进行单遍扫描获取高精度决策树的问题.Gama等对VFDT进行扩展并实现了VFDTc,使系统能够处理连续属性.Peng等在传统数据挖掘环境下提出了基于模糊理论的连续属性平滑离散化方法.基于前述工作,作者设计并实现了一种基于线索化排序二叉树的增量模糊决策树分类算法fVFDT,其主要贡献有如下4点:(1)第一次设计并实现了数据流上的基于线索化二叉排序树(TBST)的连续属性处理方法.相比VFDT,fVFDT的样本插入时间复杂度由O(n2)降低到O(nlogn).当新样本到达时,VFDTc需要更新O(logn)个属性节点,而fVFDT只需要更新相应的一个节点即可;(2)改进了VFDTc连续属性的最佳划分节点选取的计算方法,使其时间复杂度由O(nlogn)降低到O(n);(3)根据Fayyad等的研究成果,相比VFDTc,fVFDT只需从更少的备选划分节点中选取最佳节点,备选划分节点数由O(n)降低到O(logn);(4)改进了传统数据挖掘环境下的基于模糊理论的连续属性平滑离散化方法,有效地处理了噪声数据,很好地提高了分类精度.

引用

页码：1244 / 1250

页数：7