论文摘要
随着互联网、数据库和嵌入式技术的飞速发展以及现实应用需求的持续推动,一种被称为数据流的全新数据类型已广泛应用在传感器数据处理、网络安全监控、金融证券管理、事务日志分析等众多领域。与传统数据库截然不同,由一系列值对(事件类型,时间戳)构成的数据流具有高速、无界、连续、时变的特点,这些特点使得面向传统数据库的数据挖掘算法难以直接应用到数据流的分析中。作为数据流分析的重要任务之一,数据流预测在面临巨大挑战的同时也迎来了前所未有的应用机遇,并已成为学术界和工业界的研究热点。本文在总结国内外相关研究工作的基础上,针对数据流预测涉及的频繁情节挖掘、频繁闭情节挖掘、无冗余情节规则抽取、情节规则匹配等四个关键问题展开了深入探讨,形成了一个数据流预测的研究体系,主要贡献包括：1.提出了一个事件序列上的频繁情节挖掘算法MANEPI。频繁情节刻画了现实应用中用户或系统的行为。现有的频繁情节挖掘算法大多基于最小发生或非重叠发生来计算一个情节的支持度,容易导致情节发生的“过计数”问题或不能很好地刻画一个情节中事件类型之间的紧随关系。另外,这些算法均采用了与Apriori算法一样的广度优先搜索策略,需要多遍扫描事件序列,并且产生了大量的候选情节。然而,算法MANEPI基于最小且非重叠发生的概念来计算一个情节的支持度,并采用深度优先的搜索策略,只需单遍扫描事件序列且不产生任何候选情节。此外,MANEPI利用情节的Apriori性质避免了不必要的情节增长,进一步缩小了频繁情节的搜索空间。理论分析和实验评估证明MANEPI具有较高的挖掘效率和挖掘质量。2.提出了一个事件序列上的频繁闭情节挖掘算法FCEMiner。频繁闭情节集是所有频繁情节的一个无损压缩表示。尽我们所知,Clo_episode[58]是目前仅有的一个频繁闭情节挖掘算法。尽管只需单遍扫描事件序列,但是Clo_episode采用了广度优先的搜索策略,在挖掘过程中产生了大量的候选情节。另外,该算法基于最小发生来计算一个情节的支持度,也会导致情节发生的“过计数”问题。然而,算法FCEMiner采用了与MANEPI一样的搜索策略和支持度定义来发现频繁情节的简约且完备集,并利用特殊前向扩展的非闭一致性避免了冗余的闭合性检查,进一步缩小了频繁闭情节的搜索空间,加速了挖掘过程。理论分析和实验评估证明FCEMiner能够高效地发现事件序列上的频繁闭情节。3.提出了一个事件序列上的无冗余情节规则抽取算法Extractor。情节规则描述了频繁情节之间的因果关系。现有的情节规则抽取算法主要存在三个问题：第一,基于滑动窗口或最小发生来计算一个情节的支持度,致使频繁情节的挖掘质量不高；第二,直接由频繁情节产生情节规则,导致规则数量过于庞大且存在冗余；第三,尽管利用一些修剪技术来筛选冗余的情节规则,但这种后期的修剪处理增加了算法的时间代价。然而,算法Extractor采用最小且非重叠发生的支持度定义和深度优先的搜索策略来发现频繁闭情节及其生成子,保证了频繁闭情节及其生成子的挖掘质量和挖掘效率；利用非生成子情节的Apriori性质,避免了冗余的生成子判断；直接由频繁闭情节及其生成子来产生无冗余情节规则,提高了情节规则的生成质量和生成效率。理论分析和实验评估证明Extractor能够有效抽取给定事件序列上所有的无冗余情节规则。4.提出了一个数据流上基于情节规则匹配的预测算法Predictor。研究历史流数据的潜在规律并应用这些规律对未来流数据作出预测,能够为许多现实应用提供重要的决策支持。现有的数据流预测算法大多采用回归分析或规则匹配的方法。回归分析方法预测速度快,但只适于线性数据预测；规则匹配方法可预测线性和非线性数据,但存在规则形式严格、预测区间受限或过时、规则过于匹配等问题。然而,算法Predictor使用无冗余情节规则作为待匹配规则,保证了待匹配规则内涵的代表性和形式的一般性。预测时Predictor为每个情节规则分别使用了一个自动机,通过单遍扫描数据流来同时跟踪这些自动机的状态变迁,以搜索每个规则前件最近的最小且非重叠发生,这样不仅将无界的数据流映射到有限的状态空间,而且避免了对情节规则的过于匹配。另外,Predictor预测的结果是未来多个情节的发生区间和发生概率。理论分析和实验评估证明Predictor具有较高的预测效率和预测精度。综上所述,本文针对数据流预测涉及的频繁情节挖掘、频繁闭情节挖掘、无冗余情节规则抽取、情节规则匹配等四个关键问题展开了深入探讨,并提出了有效的解决方法,理论分析与实验评估表明本文提出的算法对于推动数据流预测的研究具有一定的理论意义和应用价值。