不平稳数据流的分类技术研究

论文摘要

随着信息技术的快速发展,在诸如无线传感器网络、网络流量监测、信用卡欺诈检测等越来越多的应用领域产生了高速动态、数据规模宏大且连续不断的数据流。数据流挖掘已成为数据挖掘的前沿领域之一,而其中如何高效正确地处理不平稳数据流问题,是当前研究中富有挑战的课题。这里,不平稳数据流是至少存在下列特征之一的数据流:1)存在概念漂移;2)存在大量噪声数据;3)各类样本数量分布不平衡。本文也称存在概念漂移的数据流为进化数据流,各类样本数量分布不平衡的数据流为不平衡数据流。本文聚焦于不平稳数据流挖掘中的分类技术研究,围绕概念漂移处理的增量式学习方法（单分类器方法）和集成分类器方法,以及噪声数据与不平衡数据处理的集成分类器方法等问题展开研究。本文主要工作包括:1.分析研究了当前进化数据流的分类技术,总结了探测概念漂移的各种方法,详细分析了相关的处理系统与算法,探讨了当前数据流分类技术的发展趋势及所面临的挑战。2.研究了传统增量式学习算法在进化数据流挖掘中的应用。在决策树算法CVFDT的基础上,提出了基于跳表技术的单分类器算法SLCVFDT。该算法利用跳表所具有的插入与搜索快速的特点,使它既能满足概念漂移处理所需要的在样本插入、搜索和删除时的快速性,又在最佳划分结点的选取上具有很好的效率。实验表明该算法对进化数据流的处理具有很好的扩展性与稳定性。3.针对现实不平稳数据流同时存在概念漂移与噪声数据的问题,基于可学习假设的平均概率AP集成分类器,提出了集成分类器WEAP-I与WEAP-II。WEAP-I结合基于权重的集成分类器与AP集成分类器,通过缓冲部分历史数据来解决噪声问题。实验验证了WEAP-I的良好抗噪性能。WEAP-II在AP集成分类器的基础上,通过分块技术,结合基于权重的集成分类器,有效解决了块内隐含渐进概念漂移、块间含连续突变概念漂移的噪声数据流分类问题。理论分析与实验验证表明:相比AP集成分类器,WEAP-II集成分类器更能适应同时存在概念漂移与噪声数据的数据流分类挖掘,其分类性能优于AP集成分类器,抗噪性能更强,并且具有与AP相近甚至更低的时间复杂度。4.针对稳态假设下不平衡进化数据流分类问题,在基于权重的AWE集成分类器基础上,综合利用过抽样与欠抽样技术,提出了IMDWE集成分类器模型。IMDWE集成分类器在集成学习过程中,根据分类性能的不同目标,采取了不同的权重确定策略。理论分析与实验验证表明:相比基于权重的AWE集成分类器,该集成分类器具有更低的时间复杂度——实验结果显示IMDWE生成分类模型的平均执行时间减少37.3%;更能适应存在不平衡进化数据流分类,其整体分类性能（G-mean指标）优于AWE集成分类器模型——实验结果显示相比AWE集成分类器平均提高为7.22%;能明显提升少数类的分类精度——实验结果显示相比AWE集成分类器平均提高为15.63%。5.针对噪声数据流分类问题,在可学习假设下,综合利用基于平均概率的AP集成分类器与抽样技术,提出了一种处理不平衡噪声数据流的集成分类器模型IMDAP。理论分析与实验验证表明:该集成分类器有效解决了概念漂移与噪声共存的不平衡数据流分类问题,并具有与AP集成分类器相近的时间复杂度,同时抗噪性能更强;其整体分类性能（G-mean指标）优于AP集成分类器——实验结果显示相比AP集成分类器平均提高为2.3%;能明显提升少数类的分类精度——实验结果显示相比AP集成分类器平均提高为7.1%。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 数据挖掘与数据流挖掘
• 1.2 数据流挖掘中的分类技术
• 1.2.1 基本概念
• 1.2.2 分类器性能评估
• 1.2.3 分类器的概率输出
• 1.2.4 面临的挑战
• 1.3 论文的工作与组织
• 1.3.1 论文的工作
• 1.3.2 论文的组织结构
• 第二章 相关研究
• 2.1 概念与目标概念
• 2.2 概念漂移
• 2.2.1 概念漂移定义
• 2.2.2 概念漂移学习的理论基础
• 2.2.3 概念漂移类型
• 2.2.4 概念漂移与数据流分类的关系
• 2.3 概念漂移处理方法概览
• 2.4 概念漂移处理系统和方法
• 2.4.1 Stagger
• 2.4.2 概念版本
• 2.4.3 FLORA 框架
• 2.4.4 元学习方法
• 2.4.5 CD 算法
• 2.4.6 基于模糊信息网络的方法
• 2.4.7 AQ-PM
• 2.4.8 SPLICE
• 2.4.9 决策树方法
• 2.4.10 集成分类器方法
• 2.5 小结
• 第三章 基于跳表的单分类器模型
• 3.1 引言
• 3.2 相关工作
• 3.2.1 跳表
• 3.2.2 VFDT
• 3.2.3 CVFDT
• 3.2.4 连续属性离散化
• CVFDT 单分类器模型'>3.3 SL_CVFDT 单分类器模型
• 3.3.1 跳表结构
• 3.3.2 属性值插入过程
• 3.3.3 样本流出滑动窗口时跳表的删除过程
• 3.3.4 最佳划分结点的选取过程
• 3.4 实验结果与分析
• 3.4.1 算法对连续属性处理的有效性
• 3.4.2 算法的抗噪声能力
• 3.4.3 连续属性个数对算法的影响
• 3.5 小结
• 第四章 基于权重与平均概率的集成分类器模型
• 4.1 引言
• 4.2 相关工作
• 4.2.1 概念漂移与训练数据集
• 4.2.2 基于权重的集成分类器方法
• 4.2.3 基于平均概率的集成分类器方法
• 4.3 WEAP 集成分类器的设计与分析
• 4.3.1 WEAP-I 集成分类器
• 4.3.2 WEAP-I 集成分类器性能分析
• 4.3.3 WEAP 集成分类器
• 4.3.4 WEAP 集成分类器理论分析
• 4.3.5 WEAP 的扩展
• 4.4 实验结果与分析
• 4.4.1 实验设置
• 4.4.2 实验结果与分析
• 4.5 小结
• 第五章 稳态假设下的不平衡数据流集成分类器模型
• 5.1 引言
• 5.2 相关研究
• 5.2.1 不平衡学习问题
• 5.2.2 不平衡学习研究进展
• 5.2.3 AWE 集成分类器
• 5.3 IMDWE 集成分类器的设计与分析
• 5.3.1 IMDWE 集成分类器
• 5.3.2 权重的确定策略
• 5.3.3 复杂度分析
• 5.4 实验分析
• 5.4.1 实验设置
• 5.4.2 实验结果与分析
• 5.5 小结
• 第六章 可学习假设下的不平衡数据流集成分类器模型
• 6.1 引言
• 6.2 相关工作
• 6.2.1 不平衡数据集分类的基本方法
• 6.2.2 不平衡数据流分类的性能评价标准
• 6.2.3 AP 集成分类器
• 6.3 IMDAP 集成分类器的设计与分析
• 6.3.1 IMDAP 集成分类器
• 6.3.2 复杂度分析
• 6.4 实验分析
• 6.4.1 实验设置
• 6.4.2 实验结果与分析
• 6.5 小结
• 第七章 结论与展望
• 7.1 论文工作总结
• 7.2 工作展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果