首页 | 本学科首页   官方微博 | 高级检索  
     

一种基于线索化二叉排序树的数据流挖掘的决策树分类新算法
引用本文:王涛,李舟军,颜跃进,陈火旺.一种基于线索化二叉排序树的数据流挖掘的决策树分类新算法[J].计算机研究与发展,2007,44(Z2):42-46.
作者姓名:王涛  李舟军  颜跃进  陈火旺
作者单位:王涛(国防科学技术大学计算机学院,长沙,410073);李舟军(北京航空航天大学计算机学院,北京,100083);颜跃进(国防科学技术大学计算机学院,长沙,410073);陈火旺(国防科学技术大学计算机学院,长沙,410073)
摘    要:数据流具有数据持续到达、到达速度快、数据规模巨大等特点,这些都给数据流挖掘领域研究工作带来了新挑战,而其中分类算法更是当前的研究热点. 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  线索化  二叉排序树  数据  流挖掘  决策树分类  算法  Trees  Search  Binary  Based  Mining  Data  Streams  Classification  Method  分节点数  计算方法  选取  最佳  改进  属性节点  复杂度
修稿时间:2007年3月5日

A New Decision Tree Classification Method for Data Streams Mining Based on Threaded Binary Search Trees
Wang Tao,Li Zhoujun,Yan Yuejin,Chen Huowang.A New Decision Tree Classification Method for Data Streams Mining Based on Threaded Binary Search Trees[J].Journal of Computer Research and Development,2007,44(Z2):42-46.
Authors:Wang Tao  Li Zhoujun  Yan Yuejin  Chen Huowang
Abstract:
Keywords:
本文献已被 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号