论文部分内容阅读
实际应用领域中产生了大量的数据流,例如电子商务交易记录,网络搜索请求,电信通话记录等,这些数据流中隐含着丰富的有价值的知识亟待挖掘。然而,由于数据流具有的快速性、无限性、连续性、多变性等特征,使得已有的分类方法面临着巨大的挑战。因此,开展数据流的分类方法研究具有重要的研究和应用价值。
传统的分类方法多基于多遍扫描并存储全部数据的方式,难以适应数据流的环境。此外,实际领域数据流中客观存在的概念漂移现象,以及概念漂移所具有的多重性,是数据流分类过程中无法回避的问题。为此,本文开展数据流的分类研究,研究内容涉及两方面:(1)研究适应于数据流环境的实时、低耗、抗噪的数据流分类方法:(2)数据流中有效的概念漂移处理方法。
主要研究内容如下:
(1)基于UFFT和随机决策树,分别提出了数据流集成分类算法UFFT-WB和IRDTC-DS。UFFT通过增量统计的方法构建决策树,因而具有良好的时空性能,然而这种增量统计方法导致历史数据对分类器的影响过大。为此,在构建UFFT集成分类器时,通过删除较差基分类器来减小过期历史数据对当前数据的影响,从而在保证时空性能的基础上提高了算法的分类准确率；由于随机决策树采用随机方法选择分裂属性具有较高的时间效率,但对分类性能带来一定的影响,为此在基于随机决策树的集成分类方法中提出了采用Hoeffding bounds确定连续属性的分割阈值,引入朴素贝叶斯方法判断叶子结点类别标识等改进措施,并实现了集成随机决策树的增量式构建方法。理论分析与实验表明:上述两种集成分类方法是在保证时空性能的同时提高了分类精度,因而能有效处理数据流分类问题。
(2)提出一种具有较强抗噪性的数据流混合集成分类方法WE-HG:针对单一模型集成分类方法可能导致分类误差扩大现象,难以适应含噪数据流的分类,而AP,AE等集成方法虽采用了多模型的集成方法,也存在对当前数据过拟合和时空性能不佳等问题。为此,论文提出基于WE框架的混合集成方法,通过构建1个决策树的集成分类器和1个相对全局的Na(i)ve
Bayes分类器进行集成,利用全局的Na(i)ve Bayes提高整个分类器的抗噪性能。实验表明,与AP,AE和WE等集成方法相比,WE-HG在合理的时空开销范围内,能有效提高集成分类器的抗噪性能,因而是一种有效的数据流分类方法。
(3)提出一种基于实例方法的、自适应的概念漂移处理方法ACCD:基于“与当前分类模型不适应的实例可能代表了新概念的变化方向”这一假设,在决策树的集成分类模型基础上,引入实例加权方法,使得基分类器在构建过程中更关注代表漂移方向的实例,从而使分类器能更快的拟合新概念。此外,针对实际应用中存在的渐进式和突变式概念漂移,为提高模型对不同概念漂移的适应性,引入似然估计法区分数据流中的渐变式和突变式概念漂移,并分别采用不同的基分类器更新策略。实验表明,该方法对突变式漂移能较快的收敛,而对渐变式概念漂移在其收敛过程中具有较高的分类精度,是一种有效的概念漂移处理方法。
(4)提出一种基于概念漂移检测的集成分类算法DWCDS:针对已有方法大多通过监测滑动窗口之间准确率的变化情况来检测概念漂移,而窗口尺寸难以同时适应渐变式和突变式的概念漂移这一问题,提出基于一种双层滑动窗口的检测机制,该方法能根据漂移点动态调整窗口尺寸,一定程度上缓解了固定尺寸窗口难以同时有效检测渐变式和突变式漂移的矛盾。实验结果表明,该方法能有效的检测出上述两种概念漂移,基于该检测机制的数据流分类方法具有较好的分类效果。