论文部分内容阅读
数据流是一个有时间顺序的,连续的,无限的事务(或实例,记录)序列.数据流与传统的静态数据或数据库相比具有非常不同的特性,如动态、无限、有序、非重复性、高速和变化.在真实的数据流环境中,一些数据源分布是随着时间改变的,即具有概念漂移特征,称此类数据流为可变数据流或概念漂移数据流.因此处理数据流的方法需要自动调整以适应概念变化.为了得到无损压缩的且满足用户不同需求的有趣模式结果集合,研究数据流中满足约束的、闭合的频繁模式挖掘算法;为了提高数据流分类效率,研究基于频繁模式的分类算法;研究模式挖掘和分类过程中概念漂移问题的处理方法.主要的工作包括:(1)在数据流中挖掘频繁模式面临的主要挑战是数据的无限性使得模式不断的产生,因此数量巨大.尤其是支持度阈值低时可能导致输出模式的数量爆炸.由于概念漂移特性,在一些数据流应用中通常认为最新的数据比历史数据重要.为此,研究使用闭合算子方法提高闭合模式挖掘的效率.研究并设计了一种均值衰减因子提高模式结果集合的准确性和完整性.研究并设计了一种基于滑动窗口模型和时间衰减模型的闭合频繁模式挖掘算法TDMCS.通过实验分析,与已有同类算法相比TDMCS算法可以得到稳定的模式集合,且具有更加均衡的查全率和查准率.(2)已有的衰减因子设置方式对历史事务和最新事务权重采用相同的衰减强度,这样不能更一步的区分新旧事务的重要性.为此,研究并设计了一种基于高斯函数的衰减方式.与已有的衰减方式相比,它对新近事务的衰减程度更低,而对历史事务的衰减程度更高.研究采用多种衰减因子设置时间衰减模型的方式.在高斯衰减因子的基础上,研究并设计了基于堆积衰减值的TDMCS+算法.对已有的常见衰减因子进行分析总结,并通过理论和实验对比分析使用高斯衰减因子的优势.(3)一些高维数据中包含大量的重复项,已有的模式挖掘算法处理此类数据会产生大量的短的、非连续的无用模式.针对此类数据的特征,研究并设计了三种支持度,包括支持度、局部支持度和全局支持度.局部支持度和全局支持度可用于挖掘在一条数据中多次出现的模式.研究并设计了算法MCCPM挖掘基于三种支持度的、连续的、闭合的模式.因此,挖掘过程中需要记录模式在每条数据中出现的位置和次数.实验分析证明与已有方式相比,MCCPM算法可以减少内存消耗,可以得到更加有趣的模式结果集合.通过对模式结果进行分析表明,这些有趣模式可以用于序列的对比,或者用于对未知序列的分类.(4)无限的数据流中可能存在着大量无用的信息或者噪声,而模式挖掘可以去除数据中的无用信息且不受噪声的影响.因此,挖掘有趣的、频繁的和有区分力的模式,可以用于有效的分类.研究并设计了一种两层结构的频繁模式决策树分类算法PatHT.第一层设计算法CCFPM挖掘具有约束的闭合频繁模式集合,该算法使用可变滑动窗口,当检测到概念漂移时进行窗口的收缩,同时对历史模式进行删除.接着对模式结果抽样产生集合CFTSet;第二层设计算法HTreeGrow使用CFTSet生成分类模型.PatHT算法为不同特征的数据流,设计不同的模式使用策略.算法中采用概念漂移检测器跟踪概念变化,从而自适应的调整分类模型.通过对真实和虚拟数据流的实验分析,与已有数据流分类算法相比PatHT算法可以提高分类正确率或明显降低时空消耗。