基于McDiarmid不等式的决策树分类方法研究与应用
Research and Application of Decision Tree Classification Method Based on Mcdiarmid's Inequality
随着信息技术和大数据的不断发展,数据流模型被广泛应用于社会生产和生活的各个领域.因此,数据流的收集和分析就变得至关重要.数据流的爆炸性增长,使得研究者需要更大的内存来存储这些数据流.然而,使用传统的数据挖掘技术很难处理数据流,并且不可能从大量数据流中提取有价值的信息.如今,研究者使用增量决策树方法来处理数据流分类问题,这是挖掘大量数据流中有用信息的方法之一.本文首先对数据流决策树分类方法的相关知识进行概述,包括数据流的定义、概念、特征等.其次介绍了现有的决策树分类方法,主要包括单分类决策树方法和集成分类决策树方法.然后研究基于McDiarmid不等式的数据流决策树分类算法.最后设计实现基于决策树分类方法的城市用户行为分析验证平台.本文的主要贡献如下:(1)首先介绍数据流的概念、特点和处理方式等基本知识.其次,对现阶段用于处理数据流的分类方法,包括决策树、支持向量机、贝叶斯、神经网络、KNN和关联/分类规则进行分析比较.接下来分析数据流决策树分类方法,包括单分类决策树方法和集成分类决策树方法.其中,单分类决策树方法包括快速决策树、快速决策树的衍生算法和其它类型的决策树算法.集成分类决策树方法包括基于Hoeffding不等式的集成分类方法、随机决策树衍生的集成分类方法和其它类型集成分类方法.(2)针对Hoeffding不等式处理数据流时间过长,并且在属性分裂度量方面存在不足等问题.比如信息增益和基尼指数,不能表示为实数值随机变量的和,其中,1≤≤,表示属性数是具有一定分布的实数值随机变量.为了进一步提高分类性能,本文提出了一种基于McDiarmid不等式的数据流决策树分类算法(McDiarmid Decision Tree,McDDT),并研究使用t进行属性分类度量.该算法与经典决策树算法相比,在分类准确率升高或者几乎保持不变的情况下,算法运行时间明显减少,生成决策树的节点数与层数明显降低.(3)本文设计了一种基于McDDT算法的用户到访行为分析验证平台,该平台采用Python语言基于Tkinter框架设计的.主要向用户提供了数据处理、数据分析和结果显示等核心功能,用于实现用户所到行政区的预测分析功能.
- 作者：
- 贾涛
- 学位授予单位：
- 北方民族大学
- 专业名称：
- 计算机技术(专业学位)
- 授予学位：
- 硕士
- 学位年度：
- 2019年
- 导师姓名：
- 韩萌；王生国
- 中图分类号：
- TP311.13；TP181
- 关键词：
- 数据流；分类；决策树；Hoeffding不等式；McDiarmid不等式
- data streams; classification; decision tree; Hoeffding's inequality; McDiarmid's inequality;