一种基于线索化二叉排序树的数据流挖掘的决策树分类新算法  

A New Decision Tree Classification Method for Data Streams Mining Based on Threaded Binary Search Trees

作　　者：王涛[1] 李舟军[1] 颜跃进[1] 陈火旺[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙,410073 北京航空航天大学计算机学院,北京,100083 国防科学技术大学计算机学院,长沙,410073 国防科学技术大学计算机学院,长沙,410073

出　　处：《计算机研究与发展》2007年第z2期42-46,共5页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60573057,60473057,90604007)

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

关 键 词：数据流 线索化二叉排序树 连续属性 VFDT 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]