《基于窗口机制的概念漂移数据流分类算法研究》由会员分享，可在线阅读，更多相关《基于窗口机制的概念漂移数据流分类算法研究（54页珍藏版）》请在金锄头文库上搜索。
1、合肥工业大学 硕士学位论文 基于窗口机制的概念漂移数据流分类算法研究 姓名：朱群 申请学位级别：硕士 专业：计算机应用技术 指导教师：胡学钢 2011-04 基于窗口机制的概念漂移数据流分类算法研究基于窗口机制的概念漂移数据流分类算法研究 摘摘 要要 随着信息科技的快速发展，很多应用领域产生了大量的现实数据。如网络 安全、股票分析、电子商务、气象监控等领域。在这些数据中可能隐含着丰富 的、有价值的、亟待挖掘的信息，并且人们对这些信息的需求也变得越来越迫 切，这无形中都推动了数据流研究的快速发展。 数据流中的数据普遍具有快速性、连续性、多变化和无限性等特点，且概 念漂移现象常常出现。这使得建立在
2、原始数据集上的模型不再适应，从而给传 统分类问题提出了极大的挑战。为此，本文针对概念漂移问题展开了一系列的 研究，主要工作如下： （1）概述概念漂移数据流处理普遍存在的问题，分析已有算法在处理概念 漂移问题时存在的优缺点。 （2） 数据流的快速性等特性对模型的时空性能有更高的要求。 针对此问题， 研究并提出了一种基于单窗口的概念漂移数据流分类算法 SWCDS。该算法采 用随机森林作为基础模型，使用滑动窗口机制检测概念漂移，并根据检测结果 动态地调整分类器模型使其更适应新概念数据。实验表明：与已有的代表性的 概念漂移数据流分类算法相比，该算法在保证时空性能的同时具有较优的分类 精度和抗燥性。 （
3、3）单窗口机制中窗口值较大有利于低漂移率的数据流处理，却不适应新 的目标函数；窗口值较小能快速地适应概念漂移，却常常由于实例不足导致学 习不充分。针对此问题，设计并提出了一种基于双层窗口的概念漂移数据流分 类算法 DWCDS。该算法采用 SWCDS 算法中的随机森林作为基础模型，利用 双层窗口机制周期性地检测滑动窗口中流数据分布的变化，并动态地更新模型 以适应概念漂移。实验表明：双层窗口机制比单窗口具有更优的漂移检测能力。 （4）基于以上工作，设计并实现了概念漂移数据流分类系统 DWCDS，该 系统集成了 SWCDS 与 DWCDS 两种算法，为概念漂移数据流分类提供了一个 实验平台。 关键词
4、: 关键词: 数据流；分类；概念漂移；随机森林 Window-based Classification Algorithms for Concept Drifting Data Streams ABSTRACT With the development of information technology, lots of data are generated in the numerous application fields, such as network security, stock analysis, e-commerce and weather monitoring. In the
5、se data, abundant and valuable information is hidden and needed to be mined urgently. Motivated by this, more and more attentions are focused on the learning from data streams. Data streams present new characteristics as being fast, continuous, high-volume, open-ended, and concept drifting. It is he
6、nce a challenge for most traditional classification algorithms. However, our work is focused on the classification of concept drifting data stream, and main contributions are as follows: (1) Some problems in data streams are first summarized, and then the related work on the classification of concep
7、t drifting data streams are reviewed and analyzed. (2) In this thesis, a fixed-window-based classification algorithm for data streams with concept drifts (named SWCDS) is first proposed to adapt new characteristics of data streams. In SWCDS, random forests of decision trees are selected as the base
8、classifiers. Meanwhile, a sliding window mechanism is utilized to detect concept drifts, and the classifier model is updated dynamically to adapt to concept drifts. Extensive experiments demonstrate that the performance on the robustness to noise and the classification accuracy in SWCDS is improved
9、significantly compared to several state-of-the-art classification algorithms for concept drifting data streams. (3) In terms of the aforementioned work, a new concept drifting data stream classification algorithm based on a double-window mechanism (named DWCDS) is further proposed in this dissertati
10、on. DWCDS adopts the same model in SWCDS as the base classifier. Meanwhile, to overcome the weakness of single-window-based mechanism, it introduces a double-window-based mechanism to detect different types of concept drifts. Experimental results show that the proposed double-window-based mechanism
11、could detect various concept drifts from streaming data quickly and efficiently compared to the single-window-based mechanism. (4) Last, the prototype system for mining concept drifting data streams is designed. It includes the algorithms of SWCDS and DWCDS mentioned above, which provides an experim
12、ental classification platform. Keywords: Data Streams; Classification; Concept Drift; Random Forests 插图清单插图清单 图 3.1 漂移判断图. 16 图 3.2 LED 数据集上噪音率与分类错误率的关系 . 20 图 3.3 HyperPlane 数据集上噪音率与分类错误率的关系 . 20 图 4.1 双层窗口结构图 . 24 图 4.2 不同漂移情况 . 25 图 4.3 LED 数据集上噪音率与分类错误率的关系 . 29 图 4.4 HyperPlane 数据集上噪音率与分类错误率的关系
13、. 29 图 5.1 DWCDS/SWCDS 算法参数设定主菜单. 31 图 5.2 DWCDS/SWCDS 算法中一般参数设定对话框 . 31 图 5.3 DWCDS/SWCDS 算法运行前参数设置示例 . 34 图 5.4 DWCDS 算法运行中的特征读取、算法运行以及结果显示 . 35 表格清单表格清单 表 3.1 时间复杂度分析 . 17 表 3.2 空间复杂度分析 . 17 表 3.3 漂移检测统计信息. 19 表 3.4 分类错误率比较 . 19 表 3.5 时空性能比较 . 21 表 4.1 从前往后与从后往前漂移检测统计信息 . 26 表 4.2 漂移检测统计信息. 27 表 4.3 分类错误率比较 .
