时间序列异常子序列发现与关联分类规则更新策略研究

### 时间序列异常子序列发现与关联分类规则更新策略研究 #### 1. 时间序列异常子序列发现实验 在时间序列分析中，发现最不寻常的子序列是一个重要的研究方向。为了评估相关算法的性能，选取了五个数据集：ERP、KOSKI、随机游走、电力数据和 EEG。针对每个数据集，创建了长度分别为 5000、10000、15000、20000 和 25000 的时间序列。对于每个数据集和长度的组合，随机抽取 100 个子集用于测试。所有实验均在一台 Core2Duo 2.2 GHz、1GB RAM 的 PC 上进行。 为了比较算法性能，采用了两个评估指标：距离函数调用次数和 CPU 时间。对于第一个指标，遵循特定的指导原则；同时，使用实际 CPU 时间作为第一个指标的补充。由于算法采用了在字典树上的分支限界搜索，算法的运行时间包括字典树遍历的开销，该开销取决于字典树的高度和结构。因此，仅基于距离函数调用次数进行评估是不够的。 每个实验重复 10 次并取平均值。实验中设置了以下参数：异常子序列长度 n = {128, 256}，单词大小 w = { 4, 8, 16, 32 }，字母表基数 a = { 3, 4, 5}。 ##### 1.1 外循环启发式实验 为了实证比较外循环排序启发式方法，测试了九种排序启发式（SORT、SORT REV、SELECT、PAR、PAR REV、HOT LIKE、SEQ、SEQ REV）和五种异常度量函数（Sub、Pos、SubPos、PosSub 和 Com）的所有组合，并在五个不同的数据集上进行测试，为每个数据集确定了最佳情况。 实验结果可能起初令人惊讶，外循环启发式和异常度量函数的选择取决于数据集。某些排序启发式/异常度量函数的设置在某些数据集上更有效，但在其他数据集上可能表现不佳。 以下是五个测试数据集各自的良好外循环启发式方法，按从最佳到次佳的顺序排列： | 数据集 | 启发式方法 | | ---- | ---- | | EEG | 1. Com - SeqRev <br> 2. Sub - HotLike <br> 3. Sub - ParRev | | ERP | 1. Hot <br> 2. SubPosHotLike <br> 3. None | | Koski | 1. Com - Seq <br> 2. Com - Sort <br> 3. Com - Par | | Random | 1. SubPos - Par <br> 2. SubPos - Seq <br> 3. Com - Par | | Power | 1. SubPos - Seq <br> 2. Com - Seq <br> 3. SubPos - Par | 其中，加粗的启发式方法将用于后续实验。 ##### 1.2 内循环启发式实验 在具有合理高度的增强字典树中，字典树遍历的开销约占查找异常子序列成本的 5% 到 12%。显然，如果字典树的高度过高，字典树遍历的成本会显著增加，从而降低该机制的效益；如果字典树的高度过小，叶节点中的子序列数量会增加，不必要的子序列检查也会增多，同样会使字典树遍历成本增加。 通过实验发现，字典树高度的最佳值为 w = 8。建议字典树的高度约为 log₂n，其中 n 是异常子序列的长度。需要注意的是，随着时间序列长度和异常子序列长度的增加，字典树遍历开销在查找异常子序列成本中所占的百分比会降低。例如，当时间序列长度约为 50000 时，在实验中字典树遍历的成本可以忽略不计。 字母表大小也会影响算法的性能。对于较小的字母表大小，如 a = 3，由于 SAX 编码的性质，相邻的两个符号会被视为相同，字典树遍历会变成穷举搜索，导致算法效率低下。实验结果表明，当 a = 3 时，算法性能较差；当 a = {4, 5} 时，由于字典树遍历的有效性，算法性能显著提高。但如果 a 过大，字典树中的叶节点数量会增加，从而增加字典树遍历的开销。实验显示，EHOT 算法在 a = {4, 5} 时表现最佳。 ##### 1.3 与 HOT SAX 和 WAT 的比较 将 EHOT 算法与 HOT SAX 和 WAT 算法在五个数据集上进行了效率比较，比较指标为距离函数调用次数和 CPU 时间。这里仅报告 n = 128 时的实验结果，n = 256 时得到了相同的结果。 实验结果表明，EHOT 算法在效率上优于 HOT SAX 和 WAT 算法。然而，EHOT 算法的一个缺点是对参数设置敏感。在处理这些数据集时，单词大小和字母表基数的最佳值分别为 w = { 8 } 和 a = { 4, 5 }。 #### 2. 关联分类规则更新策略 关联分类是一种著名的数据分类技术。随着数据量的不断增加，维持分类准确性变得越来越困难。更新关联分类规则需要大量的处理时间，而且预测准确性往往提升不大。 ##### 2.1 关联分类背景 关联分类挖掘利用关联规则发现技术构建分类系统，即关联分类器。构建分类器时，首先从训练数据集中发现关联分类规则（CARs），然后选择其中的一个子集形成分类器。 目前已经提出了多种关联分类算法，如 CBA、CBA2、CMAR、CPAR、MCAR 和 MMAC 等。尽管这些现有算法在准确性方面比传统分类算法（如决策树）更具竞争力，但它们都没有纳入增量关联分类。当新事务插入数据库时，当前的关联分类算法必须重新扫描更新后的训练数据集并更新 CARs，以反映变化。重新扫描操作的计算成本很高。 虽然已经提出了一些增量关联规则发现方法，如 FUP、FUP2、Negative Border、UWEP、Sliding - Window Filtering 和 NUWEP 等，以减少训练数据集的重新扫描次数，但为每一轮事务插入重新生成 CARs 仍然需要大量的计算时间，而且预测准确性可能不会比原始分类器模型有显著提高。这意味着每次插入事务后都更新分类器模型并非必要。因此，确定是否更新分类器模型以维持分类准确性是一个新的重要研究方向。 ##### 2.2 增量关联分类框架 当数据库随着