基于McDiarmid不等式的决策树分类方法计算机研究与应用

本文是一篇计算机论文研究，本文从以下三个方面对本文的工作做出总结，为进一步提高数据流分类性能提供了可能。具体内容如下。本文首先对现有数据流分类方法的相关研究现状进行介绍、分析和总结。主要从数据流的概念、定义和特点等方面对数据流进行概述，接着按照分类模型对决策树算法进行分类介绍和总结。其次针对Hoeffding不等式处理数据流时间复杂度过高，并且在属性分裂度量方面存在不足等缺陷，结合McDiarmid定理设计并推导出新的用于数据流决策树分类的McDiarmid不等式。因而提出了基于McDiarmid不等式的决策树算法（McDDT）。然而，在实验中为了进一步提高分类性能，设计使用 /2进行属性分类度量。结果表明，在McDDT和经典算法性能对比实验中，除了RRBFS和RRBFC两个数据流在实验中分类精度有所下降（2%左右），其它数据流的分类精度均是提升的，并且在8个数据流上有5个数据流的分类精度最高。即McDDT算法在分类精度升高或几乎保持不变的情况下，算法运行时间明显减少，生成树的规模明显降低。

第一章 引言

1.1 研究目的和意义
数据挖掘技术可用于从大量数据中获取未知和有用的信息。在不同的领域，使用一个有效的工具来处理海量数据流非常重要，找到分析此类数据的方法至关重要[1]。如今，在信息爆炸的时代，数据流模型被广泛应用于社会生产和生活的各个领域。传统的数据挖掘技术以脱机模式处理收集的数据。利用历史数据训练预测模型，需要多次扫描数据以提取其中有价值的信息。这些数据流与传统的数据相比，具有快速流动、高维无限、不可复现、实时处理等特性[2][3]。这些数据流通常是实时生成的，并且不易存储。因此，在线处理用于挖掘数据流中的有用信息。这是未来数据流发展的一个主要趋势，并且已经成为当前的一个研究热点。
随着数据量的不断增长，传统的数据挖掘技术在技术和应用上已不再可行了。数据流是一个实时产生、连续变化、无限有序的元组序列[4]。虽然传统的数据挖掘技术是为挖掘静态数据而设计的，但是与传统的数据集相比，数据流具有以下一些鲜明特征：
（1）有序性。数据流中的元组是按照时间先后顺序生成的，并且序列号是隐含在传入时间中或直接与时间戳一起记录。
（2）不可复现性。数据流中的数据一旦流过处理节点，除非将其输入特殊保存，否则它不会重新出现。
（3）高速性。数据流的增长速度是特别快的，换言之，元组的生成速率是非常高的。
（4）无穷大。数据流数据是连续生成的，通常数量无限。
（5）高维性。数据流中的数据通常有多种属性，也就是说，数据流的维数很多。
（6）动态性。生成数据流的概率分布是随时间变化的，并且变化率是很难控制的。

........................

1.2主要研究内容
本文针对Hoeffding不等式处理数据时间过长，并且在属性分裂度量方面存在不足等问题，提出并设计了一种基于McDiarmid不等式的数据流决策树分类算法（McDDT），设计实现基于决策树分类算法的行为分析验证平台。本文有两个创新点，首先使用 McDiarmid 不等式作为分裂度量函数，其次进一步提高算法分类性能，使用  t 作为属性判断条件。McDDT 算法与经典决策树算法相比，在分类准确率升高或者几乎保持不变的情况下，算法运行时间明显减少，并且生成决策树的节点数与层数明显降低。
本文的主要内容有五章，具体如下：
第一章为引言，详细介绍了现有数据流分类方法的研究目的和意义、数据流分类方法的研究现状以及本文的主要研究内容。
第二章为数据流决策树分类算法概述，首先详细介绍了数据流分类的相关知识，然后对决策树分类算法进行分析讨论。
第三章为基于McDiarmid不等式的数据流决策树分类算法研究。首先，对基于McDiarmid不等式的分类方法和属性度量选择进行介绍。其次，针对Hoeffding不等式的缺陷，设计基于McDiarmid不等式的决策树算法。最后设计实验验证McDDT算法的分类性能。
第四章为基于决策树分类算法验证平台的设计与实现，使用Python语言基于Tkinter框架实现了客户端模式的用户行为分析验证平台，验证平台主要包含数据处理、数据分析和结果显示等核心功能，用于实现用户到访行政区的预测分析。
第五章为总结与展望，对本文提出的基于 McDiarmid 不等式的数据流决策树分类方法与基于McDDT 算法的行为分析验证平台进行总结，并对进一步改进算法的研究思路做出展望。
.........................

第二章 数据流决策树分类

2.1 数据流概述
近年来，随着新技术和实时应用的出现，世界范围内的用户随时随地共享了大量的数据。实时应用程序生成快速连续的信息流被称为数据流。数据流可以定义为随着时间的推移高速连续流动的有序数据项序列。许多数据源，如社交网络、移动和 web 应用程序以及电信服务，都可能生成这些数据流[25]。每个数据项到达之间的时间间隔可能会有所不同。这些数据项可以是简单的属性值对（例如关系数据库元组）或更复杂的结构[45]。
许多实例被组织成具有生成顺序的数据集，并且大家将数据集称为数据块，因此知道所有数据流都由许多数据块组成。由于海量数据和数据流的高速到达，这些数据只允许访问一次，并且应用了滑动窗口机制[47]。在滑动窗口中，窗口中同时存在一个或多个数据块，只有当前窗口中的数据被完全处理时，才允许下一个数据块进入滑动窗口[48]。
数据流具有高速流动、实时处理、高维无限等特征。因此，数据流挖掘算法应该是高效的和自适应的，以管理大量的数据，而这些数据的分布不断发生未知的变化。在文[49]中提供了广泛的数据流方法和算法，其中采用了数据挖掘技术来处理数据流问题。例如，它是实时产生，也不可能使用多次扫描来处理数据。数据流必须在线分析一次。为了限制内存的使用，将计算和存储关于以前看到的数据摘要。因而，对到达的新数据流进行实时处理，然后丢弃。
.........................

2.2 决策树分类算法
本节将数据流决策树分类按照分类模型分为两类，单分类决策树模型和集成分类决策树模型。如图 2-1 所示。其中，单分类模型技术可以维护和增量更新单个（单一）分类模型，从而可以有效地应对概念漂移。相对于单个模型，集成模型需要比单分类更简单的技术更新模型，且同样可以有效地处理概念漂移[50]。更新模型以反映最近的实例并适应内存。具有最低分类精度的模型被丢弃用于概念漂移。基于集成的模型比单一的基于增量的方法具有更好的分类精度[51]。

...........................

第三章 基于 McDiarmid 不等式的决策树算法研究................................... 19
3.1 背景知识............................................19
3.2 属性度量选择........................................20
3.3 McDDT 算法的研究......................... 22
第四章 决策树分类算法验证平台的设计与实现........................................ 39
4.1 平台概述....................................39
4.2 数据处理...............................................41
4.3 行为分析平台的设计与实现...............................47
第五章 总结与展望.....................................57
5.1 工作总结..................................57
5.2 未来展望................................57

第四章 决策树分类算法验证平台的设计与实现

4.1 平台概述
本文设计的行为分析验证平台是基于 McDiarmid 不等式的数据流决策树分类算法（McDDT）设计的。该验证平台采用 Python 语言基于 Tkinter 框架进行实现，主要包括数据采集层、数据分析层和结果显示层。数据分析层包括数据存取接口、数据预处理和用户行为分析等模块。实验数据使用用户到访数据进行验证，以数据流最后一列的 9 个行政区作为 9 个决策节点，能够为城市管理者在进行城市行政区规划工作时提供决策支持，用于实现用户所到行政区的预测分析功能。该验证平台的结构如图 4-1 所示。

.........................