本文是计算机应用技术专业博士毕业论文，主要研究海量动态数据流分类方法。

1绪论

随着信息技术的发展，人类获得了前所未有的收集和使用数据的能力。通过海量数据，人们可以更好的了解周围环境(人或自然)，能够更准确、高效、实时的感知自身以外的任何事物的状态，提高工作、生活品质。但是面对如此海量的数据，如何管理和使用它们，并且为人们工作和生活服务，是一项亟待解决的问题，己成为工商业和学术界研宄的新热点。在海量数据中，数据流是最具有代表性的一种数据，其定义可以描述如下。定义1.1数据流数据流可以看成是一种由无限数据集构成，其中，表示数据中的值，且X,ex是一个多维度向量，re{1,2,...,C}表示数据所述类别。从上述定义中可以看出数据流具有海量性、实时性和动态变化性三个基本特点，下面将分别进行介绍。

(1)海量性。由于数据流是随着时间而不停产生的，除非人为干预，否则这种状态会一直持续下去，没有终点。因此可以把数据流看成是无限的，其包含数据量也可以认为是海量的。

(2)实时性。与海量性特点描述相似，由于数据的产生是随着时间而进行的，因此数据流具有时间属性，即实时性。在自然条件下，数据产生的速度和频率也仅与时间属性相关，不受人为因素影响。

(3)动态变化性。由于数据流产生往往受到当前采集环境的影响，因此导致数据流会随着时间而发生变化，即发生概念漂移。对该现象产生的原因，目前学术界尚无统一认识，主要原因是造成概念漂移的因素太多，例如，环境突变、网络攻击、用户兴趣、数据噪声等等。

因此，在上述数据流三个特点背景下，针对数据流的数据挖掘研究逐渐进入了学者们的视野，成为研宄及工程人员争相探索的热点领域。本文通过对近年来数据流挖掘领域相关研究成果的汇总与分析，以动态数据流环境为背景，针对数据流分类问题展开研究，提出了三种动态数据流分类方法，即基于集成学习的数据流分类方法、基于增量式学习的动态数据流分类方法和基于概念漂移检测的数据流分类方法。本章首先概述了数据挖掘与数据流发掘的关系，然后对数据流分类问题的国内外研宄现状和方法进行汇总和分析，最后给出本文主要的研究工作和组织结构。

1.1研究背景及意义

1.1.1研究背景

数据流挖掘是数据挖掘领域的一个分支，因此对数据流挖掘的背景介绍必然涉及到数据挖掘相关研宄内容，因此为更加全面的说明数据流的研究背景，本节分别对数据挖掘和数据流挖掘的研究背景分别进行介绍。一般来说，所谓数据挖掘(Data Mining)就是将数据中所隐含的知识与信息进行提取，即从大量的、有噪声的、不确定的、随机的数据中，挖掘出隐含于内的、不为人知的、具有实际作用与价值的信息与知识⑴。传统数据挖掘技术的发展过程可以追溯到上个世纪80年代，其里程碑事件是1989年在美国底特律召开的第11届人工智能联合会。在此次会议上首次将数据库知识挖掘的内容进行专题讨论(KDD Workshop)。随后，关于数据挖掘的KDD会议成为数据挖掘领域顶级会议，该会议每两年举办一次[2]。KDD会议每次讨论的议题均有不同，例如KDD1999年会议的议题是网络攻击检测，KDD2001年的议题是生物制药数据方面的挖掘等等，总体来说每次KDD会议的议题都会根据近期最新的技术或趋势进行设定，最近一次KDD会议于2011年在我国北京举办，主要讨论的内容是社交网络数据下的挖掘，这也是当前比较热门的问题之一。除了 KDD会议之外，还有很多国际顶级会议涉及到数据挖掘相关领域，如VLDB、SIGMOD、PKDD、ICDM、SDM、PODS等等，针对不同的数据挖掘问题进行专门讨论，在这些会议的推动下，数据挖掘相关理论和技术得到了极大的丰富和长足的进步。

2基于集成学习的数据流分类方法

通过前面介绍可知，海量性是数据流三大基本特点之一。正因为如此，数据流中样本在特征空间的分布，较传统静态数据来说，往往呈现出更为复杂的状况。在此背景下，若继续使用传统单模型结构的分类器对数据流进行分类，则会受到单模型适应性及学习能力的局限，导致分类性能低下，甚至完全失效[128，129]。针对此问题，本章利用集成学习思想构建分类模型对数据流进行分类。所提出模型使用支持向量机模型(SupportVector Machines, SVM)以及自组织映射(Self-Organizing Map, SOM)模型进行构建，并且通过数据归一化方法、遗传算法(Genetic Algorithm, GA)和粒子群算法(Particle SwarmOptimization, PSO)对模型参数进行初始化和优化，以达到最优分类效果。

2. 1引言

近年来，随着物联网、云计算和智能终端等等技术的发展，传统数据挖掘方法正面临越来越多的新挑战在众多挑战中，底层的数据形式的改变是核心挑战，即由传统的静态存储数据向动态数据流发展。随之而来的是数据在特征空间的分布也发生变化，变的越来越复杂和多样[13“134]。因此，如何适应数据流海量数据特点，设计和创造相对应分类方法，提高数据流分类准确率成为新的研宄热点。针对数据流海量性特点，需要分类模型具有较强的学习能力，以适应不同数据环境的变化，而传统单模型结构的分类方法很难适应这一要求。近年来，随着学术界对此问题研究的深入，很多方法己经被提出，其中使用集成学习思想构建数据流分类模型是其中较为流行的研究方法之一。Yu等人使用集成学习方法对多标签数据分类问题进行研究，并最终将所提出模型在生物蛋白功能判定领域进行应用，通过实验验证了有效性。Li等人针对集成学习模型中的结果融合部分进行研宄，提出一种基于权值的分类结果选择方法(DCE-CC)，通过对不同个体分离输出结果进行判定，将个体分类器赋予不同的权重，并根据权重，对分类结果进行计对性汇总，从而避免误分类模型对整体分类结果的影响。Yu等人1〗39]使用半监督学习策略，通过将高维数据流进行低维子空间映射的方法，降低维度对分类器的影响，并且对每种不同的数据流构建一个分类器，将这些个体分类器利用集成学习思想进行架构，从而建立多数据流集成分类模型。Zhang等人fi4o，i4i]提出一种集成模型对海量数据流分类和预测问题进行研究。所提出模型能够使用有类别标签和缺失类别标签的数据进行训练，通过调整不同分类器的权重，对个体分类器给出结果进行汇总，得到最终分类结果。在此基础上，Zhang等人提出一种懒惰学习(Lazy learning)方法，对动态和复杂数据流环境进行学习，有效对数据流进行分类。Xiao等人针对客户数据流进行研究，提出一种基于集成学习架构的客户数据分类模型。在传统通过对集成模型的调整，满足在不平衡数据环境下，仍然能够对数据进行正确分类和动态更新的要求。

3基于增量式学习数据流分类方法......... 41

3.1引言......... 41

3.2问题提出......... 42

3.3相关工作......... 42

3.4基于轮转式结构的增量式数据流分类模型......... 51

3.5实验及结果分析......... 54

3.5.1实验数据 .........55

3.5.2归一化方法验证实验 .........55

3.5.3轮转式多分类器模型构建方案实验......... 56

3.5.4模型比较性实验 .........58

3.6本章小结......... 59

4基于概念漂移检测的数据流分类方法.................. 60

4.1引言......... 60

4.2问题提出......... 61

4.3相关工作......... 62

4.3.1概念漂移介绍......... 62

4.3.2概念漂移检测方法......... 64

4.4基于概念漂移检测的数据流分类模型......... 66

4.4.1基于KL-distance的数据流分类模型......... 66

4.4.2概念漂移可视化方法......... 73

4.5实验及结果分析.........75

4.6本章总结......... 87

5结论与展望.........88

5.1结论.........89

5.2创新点摘要......... 89

5.3展望 .........90

结论

经过十几年的不断发展，数据挖掘己经成为计算机领域中一项重要的研宄内容，并且在很多实际问题中得以成功应用。本文针对数据挖掘领域中的数据流分类问题展开研宄，具体研究内容包括基于集成学习的数据流分类方法、基于增量式学习的数据流分类方法以及基于概念漂移检测的分类模型等相关内容。本文所取得的研究成果简要介绍如下：

(1)针对数据流海量性特点，受到集成学习模型思想的启发，提出一种基于集成学习思想的数据流分类模型。该模型使用支持向量机模型作为基础分类器，结合三种不同核函数，最终构建分类器模型，与传统集成模型不同在于，在分类结果融合部分使用自组织映射算法，对分类结果进行聚类得到最终分类结果。实验证明，所提出方法对数据流分类是有效的，能够提高分类准确率。

(2)针对数据流实时性特点，受到增量式学习方法的启发，提出一种基于增量式学习的数据流分类模型，通过增量式学习机制，控制训练集中样本数量，保证模型更新速度不会随着数据量增加而减慢，并且通过提高模型更新速度，降低概念漂移对分类模型的影响。实验表明基于增量式学习的数据流分类方法，可以有效降低概念漂移对模型分类的影响，并且不会降低模型实时分类的性能。

(3)针对数据流动态变化性特点，提出一种基于概念漂移检测的数据流分类模型，通过对不同数据块之间概念漂移检测，控制分类模型更新频率，减少模型无谓更新次数，并且设计一种分类器池机制，能够将历史出现的概念进行保存，防止重复相同概念漂移造成模型重复训练的问题。此外，使用概念转移图，对概念漂移过程及不同概念之间的关系进行可视化。实验结果表明，使用概念漂移检测方法后，能够减少模型训练次数，并且对概念漂移能够降低对模型分类准确率的影响。

参考文献

[1]悅萍.流数据挖掘关键技术研宄[D].北京：北京邮电大学，2010.

[2]陈刚.数据流的无阻塞连接算法研究[D].武汉：华中科技大学，2010.

[3]朱辉生，汪卫，施伯乐.基于情节规则匹配的数据流预测[J].软件学报，2012, 23(5);1183-1194.

[4]徐文华，覃征，常扬.基于半监督学习的数据流集成分类算法[J].模式识别与人工智能，2012, 25(2): 292-299.

[5]文益民，强保华，范志刚.概念漂移数据流分类研宄综述[J].智能系统学报，2012，7(6):1-10.

[6]曲武，隋海峰，杨炳儒.分布式数据流挖掘的研宄进展[J].计算机科学，2012，39(1):1-8+36.

[7] Ricci E. , Rugini L., Perfetti R. SVM-based CDMA receiver with incremental activelearning[J]. Neurocomputing, 2006, 69(13-15): 1691-1696

[8] Zhao L.，Wang L.，Xu Q. Z. Data stream classification with artificial endocrinesystem[J]. Applied Intelligence, 2012， 37(3): 390-404.

[9] Lines J.，Davis L. M.，Hills J. , et al. A shapelet transform for time seriesclassification[C]. Proceedings of the 18th ACM SIGKDD international conference onKnowledge discovery and data mining, Beijing, China, Aug 12-16, 2012: 289-297.

[10] Masud M. M.，WoolamC.，Gao J. , et al. Facing the reality of data stream classification:coping with scarcity of labeled data[J]. Knowledge and Information Systems, 2012,33(1) : 213-244.