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

王少鹏 等: 面向时间有序事务数据的聚簇频繁模式挖掘 2345

长度, 有|TDS|=w. TDS 中的每个事务数据 T i (1≤i≤w) 是一个三元组 (i,t i ,ts i ) , 其中 t i ⊂S I , ts i 表示 t i 的发生时间, i
是 t i 的唯一标识 ID. 对于 TDS 中任意 2 个相邻成员 T i 和 T j (1≤i<j≤w), 其对应的三元组成员 (i,t i ,ts i ) 与 ( j,t j ,ts j ) 间
存在如下关系: j=(i+1), ts j ≥ts i . 另设 TDS.ts mi 与 n TDS.ts ma 分别表示 TDS 中第 1 个和最后一个成员的发生时间, 即
x
有 ts min =ts 1 且 ts max =ts w .
例 1: 考虑表 1 所示的时间有序事务数据集 TDS, 其中共有 15 个成员 {T 1 ,T 2 ,...,T 15 } , 因此|TDS| = 15. 该数据

集相关的项集 S I = {a,b,c,d,e, f} . 集合 {a,b} 是一个包含 2 个项且长度为 2 的 2 项集. T 1 表示在 2023 年 6 月 6 日
购买了商品 a 和 c. 另外也可以看出, 该实例中 TDS.ts min =ts 1 =2023 年 6 月 6 日且 TDS.ts max =t 15 =2023 年 6 月 20 日.
定义 2. 事务数据中项集的出现 [7] . 考虑 TDS 的事务数据 T i (1≤i≤w) 和项集 x⊂S I , 如果 x⊂T i , 则称 x 出现在
T i 处, 或出现在时间戳 ts i 处.
例 2: 考虑表 1 所示的 TDS, 2 项集 {c,e} 出现在 T 6 、T 9 和 T 1 处, 或称出现在时间戳 ts 6 、ts 9 和 ts 1 处.
3
3
定义 3. 项集发生的事务集合. 考虑包含 w 个事务的 TDS 和项集 x⊂S I , 集合{T q |1≤q≤w, T q 属于 TDS 且
x
x⊂T q }为项集 x 发生的事务集合, 记为 T , |T |是 x T 中的成员数.
x
例 3: 考虑表 1 所示的 TDS, 2 项集 c,e 出现的事务集合 T {c,e} = {T 6 ,T 9 ,T 13 },|T {c,e} | = 3 .
定义 4. 项集发生的时间集合. 考虑包含 w 个事务的 TDS 和项集 x⊂S I , 集合{T q .ts q |1≤q≤w,T q 属于 TDS 且
x⊂T q }为项集 x 发生的时间集合, 记为 TS , |TS |是 x TS 中的成员数. 考虑到一个时间可能有多个项集发生, 这里的
x
x
x
x
集合设定为多重集合 (即允许重复的时间戳成员存在), 所以满足|TS |=|T |.
例 4: 接着考虑例 3, {c,e} 的发生时间集合 TS {c,e} = [ts 6 ,ts 9 ,ts 13 ] = [13,14,19] , 由于时间戳长度较长, 本文都使
用数字简写为发生在哪一天, |TS {c,e} |=|T {c,e} |=3.
定义 5. 项集关于发生时间的 Eps-邻域 [41] . 考虑包含 w 个事务的 TDS 和项集 x⊂S I , x 关于发生时间 p (p ∈
TS ) 的 Eps-邻域定义为多重集合 {q | q ∈ TS ,dist(p,q) ⩽ Eps} , 记为 N (p) . 其中, Eps 是设置的邻域半径阈值,
x
x
x
Eps
x x
dist(p, q)=|p–q|. |N (p)| 表示 N (p) 中成员数.
Eps Eps
例 5: 考虑表 1 所示数据集 TDS, 给定 Eps=2(天), 2 项集 {b, f} 对应 TS {b,f} = [12,13,13,14,14,15,18,20] . 以时间
戳 14 为例, N {b,f} (14) = [12,13,13,14,15], |N {b,f} (14)| = 5 .
Eps Eps
定义 6. 项集关于发生时间的密度 [41] . 考虑包含 w 个事务的 TDS 和项集 x⊂S I , x 关于发生时间 p (p ∈ TS ) 的
x
密度记为 ρ x (p), 可表示为 ρ x (p) = |N (p)| .
x
Eps
例 6: 接着考虑例 5, ρ {b, f} (14) = |N {b,f} (14)| = 5 .
Eps
定义 7. 项集 x 发生时间的核心点 [41] . 考虑包含 w 个事务的 TDS 和项集 x, 给定 p ∈ TS , 如果 ρ x (p)≥minPts 成
x
立, 则 p 是项集 x 发生时间的核心点, 否则 p 是非核心点. 其中, minPts 是设置的密度阈值.
例 7: 接着考虑例 7, 给定 minPts=3(天). 由于 ρ {b, f} (14)≥minPts, 则 14 是{b, f}发生时间的核心点.
定义 8. 边界点 [41] . 考虑包含 w 个事务的 TDS 和项集 x, ∀p ∈ TS , 如果点 p 是非核心点, 并且在 TS 中存在成
x
x
员 q 是项集 x 发生时间的核心点, 使得它们间存在 p ∈ N (q) 的关系, 则 p 是边界点.
x
Eps
例 8: 考虑表 1 所示数据集 TDS, 给定 Eps=1(天), minPts=3(天). 1 项集{f}对应 TS { f} = [12,13,13,14,14,18,19,
20,20] , 以时间戳 18 为例, N (18) = [19], ρ {f} (18) = 1＜minPts , 则 18 是非核心点. 而 N (19) = [18,20,20], ρ {f} (19) =
{f}
{f}
Eps Eps
{ f}
3 ⩾ minPts ,19 是核心点, 且满足 18 ∈ N (19) , 则 18 是边界点.
Eps
x
定义 9. 项集 x 发生时间的噪声点 [41] . 考虑包含 w 个事务的 TDS 和项集 x, ∀p ∈ TS , 如果 p 不是核心点, 同时
也不是边界点, 则它是噪声点.
例 9: 接着考虑例 5, N Eps (18) = [20], N Eps (20) = [18] , 由于 ρ {b,f} (18), ρ {b,f} (20)＜minPts, 则 18 和 20 是噪声点.
{b,f}
{b,f}
x
定义 10. 直接密度可达 [41] . 考虑包含 w 个事务的 TDS 和项集 x, ∀p, q ∈ TS , 如果 p ∈ N (q) , 且 q 是核心点,
x
Eps
则 q 到 p 直接密度可达.
例 10: 接着考虑例 5, 由于时间戳 12 ∈ N {b,f} (14) , 则 12 到 14 直接密度可达.
Eps
定义 11. 密度可达 [41] . 考虑包含 w 个事务的 TDS 和项集 x, ∀p, q ∈ TS , 如果在 TS 中存在一系列数据 p 1 ,
x
x