引用本文

张宇, 包研科, 邵良杉, 刘威. 面向分布式数据流大数据分类的多变量决策树. 自动化学报, 2018, 44(6): 1115-1127. doi: 10.16383/j.aas.2017.c160809

ZHANG Yu, BAO Yan-Ke, SHAO Liang-Shan, LIU Wei. A Multivariate Decision Tree for Big Data Classification of Distributed Data Streams. ACTA AUTOMATICA SINICA, 2018, 44(6): 1115-1127. doi: 10.16383/j.aas.2017.c160809

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160809

关键词

分布式数据流，大数据，分类，几何轮廓相似度，多变量决策树 

摘要

分布式数据流大数据中的类别边界不规则且易变，因此基于单变量决策树的集成分类器需要较大数量的基分类器才能准确地近似表达类别边界，这将降低集成分类器的学习与分类性能.因而，本文提出了基于几何轮廓相似度的多变量决策树.在最优基准向量的引导下将n维空间样本点投影到一维空间以建立有序投影点集合，然后通过类别投影边界将有序投影点集合划分为多个子集，接着分别对不同类别集合的交集递归投影分裂，最终生成决策树.实验表明，本文提出的多变量决策树GODT具有很高的分类精度和较低的训练时间，有效结合了单变量决策树学习效率高与多变量决策树表示能力强的优点.

文章导读

分布式和流动性的大数据简称分布式数据流大数据, 广泛存在于大型电子商务网站的交易系统、网络监控系统、传感器网络、股票交易及银行业务等系统, 具有突发性、快速性、无限性、概念漂移、分散性、信息价值稀疏性等特点[1-3], 给此类数据的分类挖掘提出了极大的挑战.

针对数据流的分类问题, 基于集成学习[4-5]的分类模型是较好的解决方法, 因其具有很高的抗概念漂移能力, 并且分类准确性也较高[6].很多集成分类模型采用决策树作为基分类器, 因为决策树学习效率高, 模型简单, 其内在的不稳定性可以提高集成分类模型的多样性[7].但是, 面对分布式数据流大数据分类, 现有基于决策树的集成分类模型面临一个急需解决的问题:此类数据在线到达的数据量大且分散化, 类别的边界呈现易变性和不规则性, 而且这些有价值的边界信息相对于数据总体呈现稀疏性.然而, 现有基于决策树的集成分类器多采用单变量决策树作为基分类器, 由于单变量决策树只能生成平行于坐标轴的决策边界, 因此需要较大数量的基分类器才能正确地近似表示类别边界, 这使得集成分类模型的学习性能和预测效率降低, 很难适应入侵检测等需要快速预测的应用.

鉴于上述问题, 本文提出了基于几何轮廓相似度的多变量决策树(Decision tree based on geometric outline similarity, GODT). GODT可以产生任意角度的决策边界, 相比单变量决策树, 其表示能力更强.另外, 最小交集分裂准则促使GODT可以快速发现类别边界, 而递归投影分裂策略可以有效降低中间节点的分裂次数, 因此GODT具有较低的学习时间.在表示相同决策边界的条件下, 相比单变量决策树, GODT作为基分类器所需的数量更少, 所以可有效解决因增加基分类器而由此产生的学习与预测性能下降问题.本文研究的创新点主要包括两点: 1)提出最小交集分裂准则.基于类别相似度偏差最大化的方法求解最优基准向量, 使得在最优基准向量的引导下, 不同类别投影点集合的交集最小, 实现了类别归属不确定的样本集合最小化. 2)提出递归投影分裂策略.针对父节点中的投影重叠区域, 在其子节点重新计算最优基准向量, 这样可使得重叠区域的样本点经过重新投影之后, 被正确地分离开, 解决了投影重叠区域的分裂问题.

本文组织结构如下:第1节介绍面向数据流分类的基于决策树的集成学习方法的相关研究; 第2节介绍经典的多变量决策树算法和几何轮廓相似度函数; 第3节详细阐述GODT, 包括建立属性组合度量标准, 分析算法的原理, 设计和实现GODT算法; 第4节是实验, 从分类的准确性、训练时间和多样性等几个方面测试GODT; 第5节是总结及后续的研究.

图 1  投影点集合P1与P2的位置关系

图 2  两类投影点集合的交集

图 3  分类精度随滑动窗口大小的变化情况

本文提出了一种新的多变量决策树.利用几何轮廓相似度函数将多维属性合成为一维属性, 建立了非线性属性组合方法, 并在此基础上提出了最小交集分裂准则, 这使得中间节点分裂的不确定性最小化.此外, 通过对投影分裂过程的分析, 提出了递归投影策略, 并将该策略与最优分裂准则相结合, 形成了一种有效的分裂方法, 降低了中间节点分裂的不均衡性, 简化了决策树的结构.同其他几种面向数据流的基分类器相比, 在分布式数据流环境下, 本文提出的多变量决策树具有较高的分类准确性和较低的训练时间, 为构建分布式数据流大数据环境下的集成分类模型提供了一种有效的基分类器.

分布式数据流大数据的分类挖掘需要整体的解决方法, 并非单一技术所能解决, 本文算法也仅仅是针对单变量决策树在分布式数据流大数据分类中的表示能力有限来研究对应的解决方法, 除此之外, 分布式数据流大数据的分类挖掘还面临数据类型多样化、大数据的形式化表达、多节点的概念漂移检测、复杂多分布的数据统计与样本重构方法等很多问题, 下一步工作的重点将围绕复杂多分布环境下的数据统计与样本重构方法, 开展相应的理论和算法研究.

作者简介

包研科

辽宁工程技术大学理学院副教授.主要研究方向为数据挖掘, 数据分析.E-mail:baoyanke9257@163.com

邵良杉   

辽宁工程技术大学系统工程研究所教授.主要研究方向为数据挖掘, 复杂管理信息系统.E-mail:lntushao@163.com

刘威   

辽宁工程技术大学理学院副教授.主要研究方向为人工智能, 模式识别, 机器学习.E-mail:lv8218218@126.com

张宇   

辽宁工程技术大学理学院讲师.主要研究方向为数据流挖掘, 人体行为识别, 机器学习.本文通信作者.E-mail:vectorzhy@outlook.com