Page 450 - 《软件学报》2025年第5期
P. 450
2350 软件学报 2025 年第 36 卷第 5 期
求得 Noi {b,e} =[ts 14 ], NR {b,e} =0.2>maxNR, 可知{b,e}不是聚簇频繁模式, 同时计算得到|C {b,e} |<minCF (引理 2).
由引理 1 和引理 2 不难推得下面定理 1 和定理 2 成立.
定理 1. 对于频繁项集 x'⊂x, 如果|C |<minCF, 则任何超集 x⊃x'都不是聚簇频繁模式.
x'
x
x'
x'
证明: 由于|C |<minCF, 根据引理 2, 可得 x'不是聚簇频繁模式. 根据引理 1, 可知|C |≤|C |, 所以, 可得
|C |<minCF. 根据引理 2, 可得 x 不是聚簇频繁模式. 因此, 如果 x'不是聚簇频繁模式, 则任何超集 x⊃x'都不是聚簇
x
频繁模式. 证毕.
定理 2. 对项集 x'⊂x, 如果∃x''⊂x'且|C |<minCF, 则 x'不是聚簇频繁模式且任何超集 x⊃x'都不是聚簇频繁模式.
x''
x'
x'
x''
证明: 由于|C |<minCF, 根据引理 2, x''不是聚簇频繁模式. 根据引理 1, 可知|C |≤|C |≤|C |. 因此, 可得|C |和|C | x
x''
x
都要小于 minCF. 所以, 根据引理 2, 可得 x'不是聚簇频繁模式且任何超集 x⊃x'都不是聚簇频繁模式. 证毕.
定理 1 和定理 2 给出了在 Naive 算法第 2 阶段实施优化的理论基础, 其中定理 1 能够在结果搜索的过程中,
有效减小搜索空间; 定理 2 可以在确定 n 项聚簇频繁项集结果的时候, 参考 (n–1) 项集的判别结果, 可以减少冗余
判别操作. 这 2 个定理能够对第 1 阶段的执行结果执行很好地优化. 具体可以通过如下实例来说明.
考虑表 1 所示 TDS, 给定 minSup=0.3, maxNR=0.1, Eps=2(天), minPts=3(天), 计算得到 minCF=4.5. 考虑 2 项集
{d,f}, 求得 Sup {d,f} =0.3≥minSup, 之后对 TS {d,f} 进行划分得到 C {d,f} ={c 1 }={[13,14,14]}, Noi {d,f} =[20,20], NR {d,f} =
{d,f}
0.4>maxNR, 则{d,f}不是聚簇频繁模式, 且|C |=3<minCF. 同理, 可得{d,f}在 TDS 中长度为 3 的超集{a,d,f},
{b,d,f}, {c,d,f}, {d,e,f}都不是聚簇频繁模式 (定理 1), 且{d,f}长度为 3 的所有超集对应长度为 4 的超集也都不是聚
簇频繁模式 (定理 2).
3.2.2 数据结构
Naive 算法本质上使用了 Apriori-TID 算法思想生成候选项集, 算法记录了每个 k 项集发生的事务 ID 集合, 通
过求 2 个 k 项集发生事务的 ID 集合交集来确定产生于它们的 (k+1) 项集发生事务的 ID 集合. 之后基于发生事务
ID 集合, 找该 (k+1) 项集的发生时间集合. 这个过程中, 随着数据规模变大, 每个 k 项集发生事务的 ID 集合体量也
会变大, 占用较多存储空间, 另外在计算 (k+1) 项集的发生事 ID 集合时, 大量集合的交集运算会更加耗时. 本部分
借鉴了文献 [7] 中使用位向量表示时间集合的思路, 提出了 ICFPM-list 的数据结构. 可以解决上述问题. 另外为了
方便基于项集发生事务 ID 集合找该项集的发生时间集合, 我们设计了 bvTimeMap 结构.
定义 17. 项集 x 的发生位置向量 bitvec x . 考虑包含 w 个事务的 TDS 和项集 x, bitvec x 是一个长度为 w, 且用于
标识 x 发生事务 ID 的向量. bitvec x [i](1≤i≤w) 表示 bitvec x 中第 i 个成员, 当 x 在 ID 值为 i 的事务中发生, 则
bitvec x [i] 值为 1, 否则值为 0.
例 17: 考虑表 1 所示 TDS, 1 项集{a}对应 bitvec {a} 可以表示为位向量 101010010100110.
定义 18. ICFPM-list. 考虑包含 w 个事务的 TDS 和项集 x, ICFPM-list 是一个结构为 (x, bitvec x ) 的哈希表, 其
x
中 x 是哈希表的 key, bitvec x 是哈希表的 Value. x 对应的 ICFPM-list 记为 ICFPM-list , 使用 ICFPM-list(x) 表示 bitvec x .
例 18: 接着考虑例 17, ICFPM-list =({a}, 101010010100110), TDS 中所有 1 项集对应 ICFPM-list 如图 1 所示.
{a}
Key Value
{a}
{b}
{c}
{d}
{e}
{f}
图 1 位向量表示项集及对应发生位置
ICFPM-list 利用位向量存储不同项集的发生位置, 可以减少用于存储每个 k 项集发生事务 ID 集合的开销, 同
时也便于计算不同项集发生位置的交集, 可以加速获得 (k+1) 项集发生事务 ID 集合的过程. 另外为了便于进一步