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  集合的过程. 另外为了便于进一步
   445   446   447   448   449   450   451   452   453   454   455