H5W3
当前位置:H5W3 > 其他技术问题 > 正文

TKEH算法

未完待续…

写在前面:本篇记录对APIN-TKEN文献上翻译的个人理解,如有错误还望指正。

Top-k高效用项集挖掘

样本

交易数据集
各项利润值

定义

  • 交易数据集(Transaction Dataset):设 I= {I_1, I_2, cdots, I_m} 是许多不同项的集合,项集 X subseteq I,其中交易项 T supseteq X,交易数据集 D = {T_1, T_2, cdots, T_n}

  • 内部效用值(Internal Utility):也可以看作数量,设 exists x in I, T_j in DIU(x, T_j) 意味着在交易项 T_j 中,项 x 的出现次数,可以参考 Table 2

  • 外部效用值(External Utility):也可以看作利润,设 exists x in IEU(x) 意味着该项的利润值,可以参考 Table 3

  • Utility of an item in a transaction:是某个项在某个交易项中的效用值,计算公式如下:

    U(x, T_j) = IU(x, T_j) times EU(x)
  • Utility of an itemset in a transaction:是某个项集在某个交易项中的效用值,上一条的plus版,计算公式如下:

    U(X, T_j) = sum_{x in X land X subseteq T_j}U(x, T_j)

    例如 U({B, D}, T_3) = U(B, T_3) + U(D, T_3) = 6 + 12 = 18

  • Utility of an itemset in a dataset:是某个项集在整个交易数据集中的效用值,上一条的plus版,计算公式如下:

    U(X) = sum_{X subseteq (T_j in D)}U(X, T_j)

    例如 U({A, E}) = U({A, E}, T_1) + U({A, E}, T_6) = 7 + 5 = 12

  • 交易项效用值(Transaction Utility):是某个交易项里所有项的效用值之和,计算公式如下:

    TU(T_j) = sum_{x in T_j land T_j in D}U(x, T_j)

    例如 TU(T_5) = U(A, T_5) + U(F, T_5) = 4 + 3 = 7

  • 交易项权重效用值(Transaction Weighted Utility):是包含某个项集 X 的所有交易项效用值和,计算公式如下:

    TWU(X) = sum_{X in T_j land T_j in D}TU(T_j)

    例如 TWU({A, B}) = TU(T_1) + TU(T_6) = 17 + 20 = 37

    Ps. TWU的作用在整个算法中还是很重要的,因为它具备反单调性(目的与频繁项集挖掘一致),对整个项集和交易项的排序、裁剪有很大作用,有以下性质:

    1. 基于估值计算TWU:当 TWU(X) >= U(X) 时,可以认为这个项集 X 的效用值被高估了【这里暂时没想到比较好的表达】
    2. 基于剪枝计算TWU:当 TWU(X) < minUtil 时,可以认为这个项集和它的扩展集不可能是高效用项集
  • 剩余效用值(Remaining Utility):在某个交易项 T_j 中大于项集 X 的所有项集都用 T/X 表示(这里的比较关系在后面会有定义说明),所谓剩余效用值就是某个项集在某个交易项中,除去该项集剩下的项的效用值之和,计算公式如下:

    RU(X, T_j) = sum_{x in T_j / X land X subseteq T_j}U(x, T_j)

    例如 设各项排序为 A < B < C < D < E < F,RU({A, C}, T_6) = U(D, T_6) + U(E, T_6) = 8 + 1 = 9 这部分与后面的交易项投影归并结合起来计算,其中各项的顺序至关重要,会直接影响到结果

  • 效用列表结构(Utility-List Structure):这是所有single-phase的高效用模式挖掘里常见的一种结构,它可以在线性时间内完成对TWU、Secondary(α)和Primary(α)等值的计算。它包含三个部分:TID、iutil、rutil。其中 TID 就是包含项集 X 交易项的标识,iutil 是 U(X),rutil 是 RU(X, T_j)

    对任意的项集 X,若 REU(X) = U(X) + RU(X) < minUtil(RU(X) = sum_{X subseteq (T_j in D)}RU(X, T_j)),那么这个项集和它的扩展集都不是高效用项集,反之则是

  • Top-k high utility itemset:对于项集 X,如果有少于 k 个项的效用值大于项集 X 的效用值,那么该项集就是 top-k HUIs

TKEH算法

1.The Search Space

和其它算法一样,也采用枚举树结构来操作,使用深度遍历方法,根节点为空,对所有的项以TUW值的大小进行升序排列

补充定义

  • 项扩展(Extension of an item):设 α 是一个项集,可用于扩展项集 α 的项组成的集合我们称为项扩展 E(alpha) = {z | z in I land z succ x, forall x in alpha}(翻译一下就是在一个交易项中大于项集 α 的项组成的项集)
  • 项集扩展(Extension of an itemset):设 α 是一个项集,Z 是 α 的扩展(出现在 α 的子枚举树中),当 Z = alpha cup W, W in 2^{E(alpha)} 时,Z 是 α 的一元扩展项,出现在 α 的子枚举树中;当 Z = α ∪ {z},z ∈ E(α) 时,Z 是 α 的多元扩展项

2.Concept of co-occurrence structure

在 top-k-HUIs mining 算法中最关键的就是如何让 minUtil 高效地自动增长,文中设计了一种叫 EUCST(Estimated Utility Co-occurrence Pruning Strategy with Threshold)的方法,可以同时达到增长 minUtil 和检索空间剪枝的效果

定义

  • EUCS structure:是一系列元组结构,形如 (x, y, z) in I^* times I^* times mathbb{R}^+,同时 (x, y, z) 定义为 TWU({x, y}) = z

    例如查看Table 8 中的 第一个交易项, TWU({A, D}) = 37、TWU({D, B}) = 58

Final EUCS Map

设 X 是项集,当 TWU(X) < minUtil 时,对于项集 X 的任何扩展 y∈Y,都有 U({Y, X}) < minUtil

从上图来看 EUCS 结构是一种三角矩阵,但在代码实现中使用的时 hashMap,EUCS 结构只存储 TWU ≠ 0 的值。本算法第一次扫描数据集的时候计算出所有一元项的 TWU,然后进行升序排序,如Table 4:

排序后的一元项

第二次扫描构建 EUCS 结构,表格中的每个单元表示该项集的 TWU 值,如Table 5,6:

                   【以下几张表中的交易项和 Table 2 冲突了,那么 Table 3 在这也不适用】
 
EUCS map for transaction T1

Ps. T1=(A, 4), (D, 4), (B, 6), (E, 3),在这个表中可以得到以下元组:(A,D, 17), (A, B, 17), (A, E, 17), (D, B, 17), (D, E, 17), (B, E, 17)

EUCS map up-to transaction T2

Ps. T2 = (F, 6), (C, 5), (B, 3), (E, 1),同样可以得到以下元组(F, C, 15), (F, B, 15), (F, E, 15), (C, B, 15), (C, E, 15), (B, E, 15),很明显(B, E, 15)已经存在,那我们只要把值叠加即可

经过不断叠加至所有交易项都算完,可得 Table 7:

EUCS Map with all TWU

最后删除那些小于minUtil的值,得到最终结果 Table 8:

Final EUCS Map

3.Dataset scanning techniques

基于 EUCS结构 的剪枝被称为 EUCP,本算法也涉及到映射和归并技术

数据集投影

补充定义

  • 数据集投影(Projected Dataset):项集 α 在某个交易项上的投影设定为 α-T = {i | i ∈ T 且 i ∈ E(α)};项集 α 在数据集 D 上的投影设定为 α-D = {α-T | T ∈ D 且 α-T ≠ null}

交易项归并

在投影结束后,可能会产生某些不同的交易项投影出来的项一致(项的IU可能不一样),为此本文将这些相同地交易项合并成一条,减少扫描次数

补充定义

  • 交易项归并(Transaction Merging):设存在多个交易项 T_{a1} = T_{a2} = cdots = T_{am},则用 T_M 来统一表示这些交易项,有 forall x in T_M, IU(x, T_M) = sum_{j = 1cdots}IU(x, T_{aj})

4.Threshold raising strategies

RIU strategy

Real item utilities

该方法是由 REPT算法 提出的,全称是 Real item utilities。在第一轮扫描数据集的时候,计算 sum_{T_j in D}U(x, T_j) 的同时也把值存入 RIU(x) 中,以列表的形式存储这些值,并对其做升序排列。然后,RIU方法将minUtil提高到排序后的RIU列表中的第k个最大值,这个值就是现在设定的阈值,直到有其它方法提高了阈值

CUD strategy

CUD strategy

该方法是由 kHMC算法提出的,通过利用 EUCS结构 里的二元项集效用值来增加minUtil,EUCS结构包含一对TWU值大于 minUtil 的项,因此可能是一个高效用项集。为此,可以考虑再度提高阈值(使用CUD方法)用于存储这对项效用值的结构称为 CUD效用矩阵(CUDM),CUD方法是在RIU方法之后执行的。

COV strategy

Coverage strategy

该方法全称是 Coverage strategy,该方法使用COVL(coverage list)结构来成对存储项的效用值

5.Pruning strategies

基于EFIM算法的sub-tree utility剪枝策略改进版,命名为 EUCP

定义

  • Pruning using EUC (EUCP):设项集 X,若 TWU(X) < minUtil,那么对于任意项集 X 的扩展项 Y,有 U(XY) < minUtil

  • Sub-tree Utility(SU):设项集 α,且有项 x ∈ E(α) 在深度遍历项集过程中能够成为其子树,有 SU(alpha, x) = sum_{T in (alpha cup {x})}[U(alpha, T) + U(x, T) + sum_{i in T land i in E(alpha cup {x})}U(i, T)]

    设项集 α,且有项 x ∈ E(α) ,其中 SU(alpha, x) ge U(alpha cup {x})

    设项集 z = x ∪ y,则有关系 TWU(z) = EUCP(x, y) ge REU(z) = su(x, y) 成立

  • Secondary(α):最开始由TWU(α)【 α 是一元项】值组成,计算公式为
    Secondary(alpha) = {x | x in E(alpha) land TWU(alpha, x) ge minUtil}

  • Primary(α):最开始由SU(α)【 α 是一元项】值组成,计算公式为
    Primary(alpha) = {x | x in E(alpha) land SU(alpha, x) ge minUtil}

    因为有 TWU(alpha, x) ge SU(alpha, x),所以 Primary(alpha) subseteq Secondary(alpha) 成立

6.Calculate upper bounds using utility array

同EFIM一样,本文也使用了Utility Array结构,对每个交易项的每个项进行同层、上下累加计算,算完最后一个交易项时,有 TWU(x) = UA[x] = SU(x),计算公式分别为:

TWU:UA[x] = UA[x] + TU(x, T_j), x in I \ SU:UA[x] = UA[x] + U(alpha, T) + U(x, T) + sum_{i in T land i in E(alpha cup {x})}U(x, T), x in E(alpha)

7.Main procedure of TKEH

以下是算法的核心部分伪代码:

TKEH algorithm
The Search algorithm

参考

  1. Kuldeep Singh、Shashank Sheshar Singh、Ajay Kumar、Bhaskar Biswas: Efficient Algorithms for Mining Top-K High Utility Itemsets-
    xueshu.baidu.com/s?wd=paperu…
  2. Top-k高效用项集挖掘_学习笔记(一) 基础概念: Erpim-blog.csdn.net/qq_35414569…
  3. Top-k高效用项集挖掘_学习笔记(二) TKU: Erpim-blog.csdn.net/qq_35414569…
  4. Top-k高效用项集挖掘_学习笔记(三) TKO: Erpim-blog.csdn.net/qq_35414569…

本文地址:H5W3 » TKEH算法

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址