http://www.paper.edu.cn
1 相关定义
1.1 HUIM 的相关定义
一个事务数据集 D = {T
1
, T
2
, · · · , T
n
} 是由多个事务组成的集合。每个交易集都有一个唯
一的标志符,记为 T
ID
,其中 I = {l
1
, l
2
, · · · , l
n
} 是 D 中所有非重复的项组成的集合。每个事务
的项集 X 都是 I 的子集。每个事务中的每个项都有内部效用值 (比如数量) 和外部效用值 (比
如利润)。一个包含 5 个事务的事务数据库如表 1 所示
[13]
,外部效用值如表 2所示。
表 1: 事务数据集
TID Transaction
T
1
(a, 1)(c, 1)(d, 1)
T
2
(a, 2)(c, 6)(e, 2)(g, 5)
T
3
(a, 1)(b, 2)(c, 1)(d, 6)(e, 1)(f, 5)
T
4
(b, 4)(c, 3)(d, 3)(e, 1)
T
5
(b, 2)(c, 2)(e, 1)(g, 2)
表 2: 利润表
Item a b c d e f g
Prot 5 2 1 2 3 1 1
定义 1 (项或项集的效用值). 在事务 T
c
中的项 i 的内部效用值记为 q(i, T
c
),外部效用值记
为 p(i)。项 i 的效用值记为 u(i, T
c
) = p(i) × q(i, T
c
)。项集 X 在事务 T
c
的效用值 u(X, T
c
),
定义为 u(X, T
c
) =
∑
i∈X
u(i, T )。项集 X 在整个事务数据库上的效用值记为 u(X),定义为
u(X) =
∑
T
c
∈g (X )
u(X, T
c
),其中 g(X) 是包含项集 X 的事务的集合。
例如,项 b 在事务 T
3
的效用值是 u(b, T
3
) = 2 × 2 = 4。项集 {a, b} 在 T
3
的效用值是
u({a, b}, T
3
) = u(a, T
3
) +u(b, T
3
) = 5 ×1+ 2 × 2 = 9。项集 {a, b} 在整个事务数据库上的效用值
是 {a, d} is u({a, d}) = u({a, d}, T
1
) + u({a, d}, T
3
) = u(a, T
1
) + u(d, T
1
) + u(a, T
3
) + u(d, T
3
) =
5 + 2 + 5 + 12 = 24。
定义 2 (HUI). 假设一个项集 X 的效用值是高于人为设定的一个阈值,那么我们认为 X 是高
效用项集,反之就认为是一个低效用项集。高效用项集算法的目的是找出所有的高效用项集。
例如,阈值 minutil = 30,在表 1中挖掘出来的高效用项集是 {b, d},{a, c, e},{b, c, d },
{b, c, e},{b, d, e},{b, c, d, e},和 {a, b, c, d, e, f },对应的效用值是 30,31,34,31,36,40,和
30。
定义 3 (事务加权效用 ((Transaction weighted utilization,T W U)). 事务 T
c
的效用记为 T U (T
c
),
定义为 T U (T
c
) =
∑
x∈T
c
u(x, T
c
)。项集 X 的事务加权效用是所有包含项集 X 的事务效用的
和,记为 T W U (X),定义为 T W U(X) =
∑
T
c
∈g (X )
T U(T
c
)。
例如,项集 {g} 的事务加权效用是 T W U [g] = T U [T
2
]+T U [T
5
] = 10+6+6+5+4+2+3+2 =
38。
定理 1 (T W U 剪枝). 任意的项集 X,如果 T W U (X) < minutil,那么 X 和它的超集都是低
效用项集
[19]
。
- 3 -