面向高速数据流集成分类器算法.docVIP

面向高速数据流集成分类器算法 　　摘要:数据流挖掘要求算法在占用少量内存空间的前提下快速地处理数据并且自适应概念漂移,据此提出一种面向高速数据流的集成分类器算法。该算法将原始数据流沿着时间轴划分为若干数据块后,在各个数据块上计算所有类别的中心点和对应的子空间;此后将各个数据块上每个类别的中心点和对应的子空间集成作为分类模型,并利用统计理论的相关知识检测概念漂移,动态地调整模型。实验结果表明,该方法能够在自适应数据流概念漂移的前提下对数据流进行快速的分类,并得到较好的分类效果。 　　关键词:概念漂移;数据流;子空间;分类;集成 　　中图分类号: TP18;TP311文献标志码:A 　　Ensemble classification algorithm for high speed data stream 　　英文作者名LI Nan1,2, GUO Gong-de1,2* 　　英文地址(1.School of Mathematics and Computer Science, Fujian Normal University,Fuzhou Fujian 350007,China; 　　2.Key Laboratory of Network Security and Cryptography, Fujian Normal University,Fuzhou Fujian 350007,China) 　　Abstract: The algorithms for mining data streams have to make fast response and adapt to the concept drift at the premise of light demands on memory resources. This paper proposed an ensemble classification algorithm for high speed data stream. After dividing a given data stream into several data blocks, it computed the central point and subspace for every class on each block which were integrated as the classification model. Meanwhile, it made use of statistics to detect concept drift. The experimental results show that the proposed method not only classifies the data stream fast and adapt to the concept drift with higher speed, but also has a better classification performance. 　　Key words: concept drift; data stream; subspace; classification; integration 　　0引言 　　随着信息产业的发展,超市交易、电信等众多应用领域每天都产生大量的数据流,其中蕴含着丰富的有价值的知识有待挖掘,近年来已成为数据挖掘领域的一个研究热点。由于数据流具有快速性、无限性和实时性的特点[1],使得传统的挖掘算法显得有些力不从心。同时,数据流中隐含的概念或知识可能会随着时间的推移或环境的改变而发生变化, 即1996年Widmer和Kubat[2]提出的概念漂移问题。因此,数据流挖掘要求算法能在有限的计算时间和内???资源内完成挖掘任务,并且根据当前的概念自适应地改变模型[3]。 　　目前,处理数据流上概念漂移的方法有3种[4]:实例选择、实例加权和集成学习。Hansen等[5]证明使用集成分类器方法比仅使用单个分类器方法具有更好的适应性和精确性。Wang等[6]提出了一个集成学习的通用框架用于挖掘概念漂移数据流。Street等[7]提出一个可以自适应数据流概念漂移的集成分类器算法(Streaming Ensemble Algorithm, SEA),展示了集成学习的有效性。此后,许多学者深入研究了集成分类器的权值设计[8-10]以及集成策略[11-13]。 　　然而,上述已存在的数据流分类模型不仅构建模型耗时多,而且面临着同一个问题:当数据流中只有少部分类别发生概念漂移时,仍必须抛弃现有的整个集成分类模型进行重建以适应新的概念,降低了分类效率。针对以上问题,本文提出了一种新颖的面向