Page 448 - 《软件学报》2025年第5期
P. 448

2348                                                       软件学报  2025  年第  36  卷第  5  期


                 |Candidates|≤1 (第  15–18  行).
                    算法  2  给出了  Naive-Generate 算法的执行情况.

                 算法  2. Naive-Generate 算法.
                 输入: Candidates, minSup, Eps, minPts, maxNR, minCF, TDS;
                 输出: 长度为   (k+1) 的聚簇频繁模式.

                 1. Candidate k+1 =  ∅ ; //用于存储长度为  (k+1) 频繁项集;
                 2. 将  Candidates 中包含的所有  k 项集放入  itemsets 中;
                 3. foreach Px  ∈ itemsets do
                             ∈ itemsets 且  Px≠Py do
                 4.  foreach Py
                 5.   tid(Pxy)=Candidates(Px)∩Candidates(Py); //Candidate k (Px) 和  Candidate k (Py) 表示  Px, Py 对应事务  ID  集合;
                        Pxy
                 6.   TS =map(TDS, tid(Pxy));
                              Pxy
                         Pxy
                                /
                 7.   Sup =|TS |   |TDS|;
                          Pxy
                 8.   if Sup ≥minSup then
                 9.      将  (Pxy, tid(Pxy)) 加入  Candidate k+ 中;
                                                   1
                                    Pxy
                              Pxy
                                                 Pxy
                          Pxy
                 10.    P =C ∪Noi =DBSCAN(TS , Eps, minPts);
                                   /
                           Pxy
                                      Pxy
                                 Pxy
                 11.    NR =|Noi |   |TS |;
                                                                             Pxy
                             Pxy
                 12.    if NR ≤maxNR then 通过  C Pxy  计算得到  L Pxy  并且输出  Pxy 及对应  L ;
                 13.   end if
                 14.  end foreach
                 15. end foreach
                 16. return Candidate k+1
                    Naive-Generate (算法  2), 将  Candidates, minSup, Eps, minPts, maxNR, minCF, TDS  作为输入, 输出长度为  (k+1)
                 的聚簇频繁模式. 算法首先初始化          Candidate k+ 为空, Candidate k+ 用来存储频繁  k+1  项集, Candidate k+ 的结构与
                                                    1
                                                                                                1
                                                                   1
                 算法  1  中的  R  相同. 之后, 将  Candidates 中的项集放入  itemsets 中  (第  1, 2  行). 接下来, 执行双重循环组合  2  个不
                 同的  k 项集以生成    (k+1) 项集  (第  3、4  行). 将  Px 和  Py 对应的  Candidates(Px) 和  Candidates(Py) 取交集后得到
                                                                 Pxy
                                                  Pxy
                 tid(Pxy), 对  tid(Pxy) 通过  TDS  映射得到  TS , 并计算得到  Sup  (第  5–7  行). 接下来, 如果  Sup ≥minSup, 根据定
                                                                                         Pxy
                 义  15, Pxy 是一个频繁项集, 将  Pxy 及  tid(Pxy) 转为哈希结构  (Pxy, tid(Pxy)) 并加入  Candidate k+ 中 1  (第  8、9 行) (第  1
                 阶段). 下一步, 对   TS Pxy  根据  Eps 和  minPts 使用  DBSCAN  进行划分并得到  P , 并计算  NR . 如果  NR ≤maxNR,
                                                                                       Pxy
                                                                                                Pxy
                                                                            Pxy
                 那么  Pxy  是一个聚簇频繁模式, 通过       C  Pxy  得到  L Pxy  并输出  P  Pxy  和  L  Pxy  (第  10–12  行) (第  2  阶段). 最后算法返回
                 Candidate k+1 , 用来下一次调用  Naive-Generate 时生成  (k+2) 项集  (第  16  行).

                 3.1.2    算法复杂度分析
                    (1) 时间复杂度
                    算法首先基于包含       m  个事务的时间事务数据集        TDS  得到  R, 对应的时间复杂度为      O(m×w). 其中, w  为每个事
                 务平均长度. 之后, 对     TDS  中每个  1  项集做聚簇频繁模式判断. 对项集        x  ∈ itemsets, 令  R(x) 长度为  r, 则映射为  TS x
                                       x
                 的时间复杂度为      O(r); 求  Sup 对应的时间复杂度为     O(1); 如果项集满足频繁, 则可继续向下判断, DBSCAN            算法
                 在最坏情况下的时间复杂度为           O(r ); 由于计算  L 须遍历  1  遍  C , 令|C |=s, 则对应的时间复杂度为    O(s). 综上, 对
                                                                       x
                                                                  x
                                                       x
                                            2
                                                            2
                 每个  1  项集做聚簇频繁模式判断的时间复杂度为             O(r+r +s). 之后, 调用  Naive-Generate 生成  (k+1) 项集, 直到无法
                 生成更多项集. 其中, k≥1. 如果     itemsets 中包含  g  个  k 项集, 那么所有  g  个  k 项集将组合为  (g×(g–1))/2  对项集以生
                 成  (k+1) 项集. 对每一对项集   Px 和  Py, 将其对应的  Candidates (Px) 和  Candidates (Py) 取交集得到  tid(Pxy), 对应的
                 时间复杂度为     O(r ). 接下来的判断过程与      1  项集类似, 可得对每个     (k+1) 项集做聚簇频繁模式判断的时间复杂度
                               2
   443   444   445   446   447   448   449   450   451   452   453