Page 446 - 《软件学报》2025年第5期

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

1
p 2 ,…, p i ,…, p n (p 1 =q 且 p n =p), 且这系列数据中任意 2 个相邻成员 p i 到 p i+ 直接密度可达, 那么 q 到 p 密度可达,
x
其中, p i ∈ TS , 1≤i≤n.
例 11: 接着考虑例 5, 考虑 TS {b, f} 中一系列数据 [12,13,13,14,14,15], 通过计算可得任 2 个相邻成员都直接密度
可达, 则 12 到 15 密度可达.
定义 12. 密度相连 [41] . 考虑包含 w 个事务的 TDS 和项集 x, ∀p,q, s ∈ TS , 如果存在 s 到 p 和 q 皆密度可达,
x
则 q 到 p 密度相连.
例 12: 接着考虑例 5, 考虑 TS {b, f} 中成员 12, 13 和 15, 可得 13 到 12 和 15 皆密度可达, 则 12 到 15 密度相连.
定义 13. 项集 x 发生时间的聚簇集合 [41] . 考虑包含 w 个事务的 TDS 和项集 x, x 发生时间的聚簇集合 C =
x
x
{c 1 ,…,c g }, g≥1, 其中每个 c i (1≤i≤g) 是非空, 且满足如下条件的 TS 子集:
x
(1) ∀p, q∈TS , 如果 p ∈ c i , p 到 q 密度可达, 则 q ∈ c i (最大性).
(2) ∀p, q∈c i , p 与 q 密度相连 (连通性).
x
x
|C |表示聚簇内容数, 其值为每个簇中所含 TS 中成员数的总和, |c i |是 c i 中成员数.
例 13: 接着考虑例 12, 可得 C {b,f} ={c 1 }= {[12,13,13,14,14,15]}, |C {b,f} |=6, |c 1 |=6.
定义 14. 对项集发生时间集合的划分 [40] . 考虑包含 w 个事务的 TDS 和项集 x, TS 是 x x 的发生时间集合, 给定
x
x
参数 Eps (半径), minPts (最小点数量), TS 关于 Eps 和 minPts 划分得到的 P =C ∪Noi 会将 TS 的所有元素分为
x
x
x
x
x
(g+1) 组. 其中, C ={c 1 ,…,c g }包含 g 个聚簇; Noi 包含所有噪声点, 簇和噪声点分别满足定义 13 和定义 9. 定义噪
/
x
x
点比 NR =|Noi | |TS |.
x
例 14: 接着考虑例 13, 对 TS {b,f} 进行划分, 得到 P {b,f} =C {b,f} ∪Noi {b,f} . 其中, C {b,f} ={c 1 }={[12,13,13,14,14,15]},
|C {b,f} |=6, Noi {b,f} =[18,20], NR {b,f} =2/8=0.25.
定义 15. 频繁项集. 考虑包含 w 个事务的 TDS 和项集 x, x 在 TDS 中支持度为 TDS 中包含 x 的事务个数与
x
x
x
x
x
x
/
/
TDS 中事务总数|TDS|的比值, 记为 Sup =|T | |TDS|. 根据定义 4, |TS |=|T |, 所以, 也可表示为 Sup =|TS | |TDS|. 给定
x
频繁阈值 minSup, 若 Sup ≥minSup (0≤minSup≤1), 则 x 为频繁项集.
例 15: 接着考虑例 6, 给定 minSup=0.2, {b,f}对应 Sup {b,f} = 7/15=0.53>minSup, 则{b,f}是一个频繁项集.
定义 16. 聚簇频繁模式. 考虑包含 w 个事务的 TDS 和项集 x, 给定参数 Eps、minPts 以及阈值 minSup 和
x
x
maxNR, 其中 maxNR 是最大噪点比阈值. 如果项集 x 及对应分区 P =C ∪Noi 满足以下条件:
x
x
(1) Sup ≥minSup;
x
(2) NR ≤maxNR.
x
x
x
那么 x 就是一个聚簇频繁模式 (custer frequent pattern, CFP), C 的发生区间集合 L ={l 1 ,…,l g }, 其中, g 为 C 包
含簇的总数, l z =[begin(c z ), end(c z )], begin(c z ) 表示簇 c z 的开始发生时间, end(c z ) 表示簇 c z 的最后发生时间, 1≤z≤g.
注意, 此处的 [] 表示发生区间.
例 16: 接着考虑例 14 和例 15, 给定 maxNR=0.3. 由于 Sup {b, f} >minSup 且 NR {b,f} <maxNR, 则{b,f}是聚簇频繁模
式, 对应聚簇频繁模式发生区间集合 L {b,f} ={l 1 }={[12,15]}.

2.2 问题说明
定义 16 给出了本文聚焦问题的形式化定义, 通过最小频繁阈值 (minSup) 来保证所找的项集的频繁特征, 通
过邻域半径阈值 (Eps), 密度阈值 (minPts) 以及最大噪点比阈值 (maxNR) 来保证所找项集的聚簇特性. 本文接下来
的工作就是设计出一种有效的方法, 以便在给定一个 TDS, 以及最小频繁阈值, 邻域半径阈值, 密度阈值, 最大噪点
比阈值的情况下, 有效挖掘出 TDS 中所有频繁且发生时间呈聚簇状态的项集, 并将满足条件的项集及对应聚簇发
生区间呈现给用户.

3 聚簇频繁模式挖掘算法
本节针对聚簇频繁模式的具体挖掘方法展开研究. 第 3.1 节给出了从定义出发挖掘聚簇频繁模式的 Naive 算