数据流频繁项集概念漂移检测与移动环境业务流程随机模型挖掘

# 数据流频繁项集概念漂移检测与移动环境业务流程随机模型挖掘 ## 1. 数据流频繁项集概念漂移检测算法 ### 1.1 FCDT 算法效率评估 为评估 FCDT（Frequent Concept Drift Detection Tree）算法的执行效率，测量了 FCDT 和 FP - Growth 在每 100 个时间点的累积执行时间。结果显示，FCDT 发现完整频繁项集所需的时间几乎是 FP - Growth 的 1/100，这表明 FCDT 在执行效率上具有显著优势。 ### 1.2 FCDB 算法实验结果 在一组实验中，使用数据集 T5I4D60K 来模拟数据流，每个基本块包含 1000 个事务。运行 FCDB（Frequent Concept Drift Detection Based on Batch）算法时，将参数 min_support 和 w 分别设置为 0.02 和 20。 - **变化率估计**：通过与 FP - growth 在每个时间点的挖掘结果得到的实际变化率进行比较，观察 FCDB 算法估计值的准确性。采用 min_SC ×6 来选择样本以求解方程（3）中的参数 θ 和 Ω。标记为 “min_SC ×6 - SD” 的曲线表明，在使用误差的标准推导来补偿 si 估计值的估计误差后，估计的变化率接近其真实值。 - **概念漂移检测**：设定变化率阈值 δ 为 0.2。当变化率大于 0.2 时，FCDB 将触发 FP - growth 来发现一组新的频繁项集，这意味着频繁模式发生了概念漂移。如图所示，第 27 个块显示了概念漂移的发生。 - **执行时间比较**：当没有概念漂移发生时，只需要维护监控结构和计算估计变化率的成本。因此，FCDB 的执行时间在大多数情况下介于 0.5 到 1.5 秒之间，大约是每个时间点执行 FP - Growth 所需时间的一半。 ### 1.3 算法总结 提出了一种连续监控数据流以检测概念漂移的方法。为避免在每个时间点挖掘频繁项集，增量维护所提出的数据结构以监控频繁项集的变化。此外，应用项集支持的幂律分布特性来估计新生成频繁项集的大致数量。只有在观察到显著变化时，才需要挖掘算法来发现一组完整的新频繁项集。 提出了两种算法，FCDT 和 FCDB，分别基于按事务更新和按批更新的滑动窗口来监控数据流上频繁项集的变化率。实验结果表明，FCDT 和 FCDB 能够有效且高效地检测频繁项集的概念漂移，它们的执行时间明显少于在每个时间点通过滑动窗口挖掘频繁项集所需的时间。 下面是一个简单的流程图，展示 FCDB 算法的主要流程： ```mermaid graph TD; A[开始] --> B[设置参数 min_support 和 w]; B --> C[模拟数据流 T5I4D60K]; C --> D[计算估计变化率]; D --> E{变化率 > 0.2?}; E -- 是 --> F[触发 FP - growth 挖掘新频繁项集]; F --> G[更新频繁项集]; G --> D; E -- 否 --> D; ``` ## 2. 移动环境业务流程随机模型挖掘框架 ### 2.1 背景与问题提出 在现代业务流程系统中，使用便携式终端进行移动业务管理是一种趋势。然而，由于移动无线环境的动态和开放性，业务流程系统的日志往往不完整且包含噪声。当前的流程挖掘方法通常假设从日志中获取的信息是完美的，但在移动环境中，日志很少是完整或无噪声的。此外，现有的挖掘算法没有解决如何从执行日志中挖掘相应的形式化随机模型的问题，导致无法分析业务管理系统的性能。 ### 2.2 相关工作 - **流程发现方法**：Cook 和 Wolf 描述了三种流程发现方法，包括神经网络、纯算法方法和马尔可夫方法，并提供了一种测量方法来量化流程模型与实际行为之间的差异。 - **基于工作流网的算法**：一些基于工作流网的挖掘算法被提出，如 α 算法可以挖掘无短循环的结构化工作流网，+α 和 β 算法被扩展用于挖掘有短循环的结构化工作流网。此外，一种启发式方法使用简单的度量来构建 “依赖/频率表” 和 “依赖/频率图”，作为 α 算法的输入，以处理噪声问题。 ### 2.3 挖掘框架介绍 提出了一个名为 FMAM（Framework for Mining stochastic Model）的框架，用于从与业务系统相关的不完整和有噪声的日志中挖掘和生成形式化随机模型。该框架的主要模块如下： - **MLE 分析**：对包含缺失标签的日志进行最大似然估计（Maximum Likelihood Estimation）分析。对于每个缺失标签，通过添加一组随机标签来修复数据，每个添加的标签关联一个额外的权重，形成一个分数样本。通过考虑每个元组的最大似然来找到