关联规则更新与路径型关联规则探索

# 关联规则更新与路径型关联规则探索 ## 1. IACF算法与规则更新 ### 1.1 最大顺序差异（MOD） 在关联分类规则更新中，规则顺序差异（OD）需超过最大顺序差异（MOD）阈值，IACF 才会执行分类器更新。MOD 的定义如下： \[MOD = C \times L \times Y\] 其中： - \(C\) 是用户指定的系数，默认值为 1。 - \(L\) 是项目的数量。 - \(Y\) 是类别项目的数量。 若 \(OD > MOD\)，则更新分类器模型。若事务插入前后项目与类别值之间的关联几乎相同（数据分布相同），则假设每个规则的顺序差异最大为 1，所有规则的总差异顺序等于 \(R2\) 中的规则数量。 ### 1.2 IACF算法流程 IACF 算法分为两个阶段：初始阶段计算原始数据库的规则顺序；增量阶段确定更新插入前后 \(R2\) 规则的 OD。以下是 IACF 算法的详细步骤： ```plaintext 输入: 原始数据库 D, 增量数据库 di, MOD 输出: 原始数据库的大小为 2 的规则 RD, 增量数据库的大小为 2 的规则 RDd 过程 IACF 1) α ← 0 2) i ← 0 3) While (D ≠ ∅) 4) If α = 0 Then // 初始阶段 5) BuildClassifier (D); 6) f(r) = ComputeOrder (RD); 7) α ← 1; 8) Else // 增量阶段 9) d ← di++; 10) Dd ← D ∪ d; 11) f'(r) = ComputeOrder (RDd); 12) // 计算 OD 13) For each r ∈ RD = r ∈ RDd 14) // 如果 R 按置信度排序 15) // 从方程 (1) 计算 f(r)Δf'(r) 16) // 如果 R 按支持度排序 17) // 从方程 (2) 计算 f(r)Δf'(r) 18) ODr' = f(r)Δf'(r); 19) End 20) OD = ∑ ODr' (r ∈ RD); 21) If OD > MOD Then 22) D ← D ∪ d; 23) α ← 0; 24) i ← 0; 25) Else 26) // 当前分类器模型 27) // 预测增量数据库 28) ModelPredict (d); 29) α ← 1; 30) End 31) End 32) End ``` ### 1.3 执行示例 以 \(MOD = 12\) 为例，使用 OD 方程 (2)（规则按支持度排序）计算 OD： 1. **原始数据库轮次**：IACF 计算每个规则的支持度，并按降序支持度排序。例如，AX 的支持度最大，顺序为 1。 2. **增量数据库轮次 1**：IACF 计算每个规则的新支持度，通过将原始数据库和增量数据库的支持度相加，然后按降序支持度排序规则。AX 的支持度从 10 变为 11，顺序从 1 变为 3，其 OD 为 \(|(1 - 3)^2 * log |1 / (1 - 3)^2|| = 2.41\)，小于 \(MOD = 12\)，因此 IACF 使用现有分类器模型。 3. **增量数据库轮次 2**：IACF 计算每个规则的新支持度，通过将原始数据库和累积增量数据库的支持度相加，然后按降序支持度排序规则。AX 的支持度仍为 11，但顺序从 3 变为 5，其 OD 为 \(|(1 - 5)^2 * log |1 / (1 - 5)^2|| = 19.27\)。所有规则的 OD 总和为 40.94，大于 \(MOD = 12\)，因此 IACF 将创建新的分类器模型。 ### 1.4 实验结果 通过实验比较了 IACF 与两个现有框架 FW1 和 FW2 在平均准确率和平均计算时间方面的性能。实验使用 CBA 进行数据分类任务，所有实验在配备 2.1 GHz Intel Core Duo CPU 和 4 GB 内存的计算机上进行。 实验使用了六个来自 UCI 机器学习库的数据集： - Adult.D97.N48842.C2 - Connect4.D129.N675557.C3 - Led7.D24.N3200.C10 - Nursery.D32.N12960.C5 - PageBlocks.D46.N5473.C5 - PenDigits.D89.N10992.C10 根据数据集的特点，可将其分为不平衡数据集（Adult、Connect4、PageBlocks）和平衡数据集（Nursery、Led7、PenDigits）。实验结果如下表所示： **表 1：各框架的平均准确率** | 数据集 | FW1 平均准确率 | FW2 平均准确率 | IACF Eqn (1) 平均准确率 | IACF Eqn (2) 平均准确率 | | --- | --- | --- | --- | ---