在学习UP-Growth算法前需先了解FP-Growth算法
UP-Growth算法简介
UP-Growth算法中运用了事务权重的概念，并在UP-Tree中存储事务权重效用，提出四种策略以减少UP-tree中的全局效用值和局部效用值，从而减少挖掘出的潜在高效用项集的数量，缩短了验证高效用项集阶的时间。
一些定义
1、i的profit记作p(i) 如A的profit为5，记作p(A)=5
2、事务T中项i的数量记作q(i,T) 如T2中A的数量为2，q(A,T2)=2
3、事务T中项i的效用记作u(i,T)=p(i)×q(i,T) 如对于T1来说u({A},T1)=5×1=5
4、TU等于事务中每个项的效用相加 如T1中的TU=u(A,T1)+u(C,T1)+u(D,T1)=5×1+1×1+2×1=8
5、项X的事务权重效用是所有包含X的事务的事务效用之和 即TU和 记作TWU
四种策略
1、Discarding global unpromising items(DGU)，即将所有TWU<min_util的项从相应事务中删除。
2、Discarding global node utilities(DGN)，即对于全局UP-tree，每一个节点的效用需减去其后续节点的效用
3、Discarding local unpromising items(DLU)，在得到某项的CPB即条件模式基后，在生成该项的conditional UP-tree时，去除path utility<min_util的项
4、Decreasing local node utilities(DLN)，对于一个path在conditional UP-Tree中的每个节点的效用值，减去其后续节点的效用
输入事务数据库和各项目效用值,并计算得到TU
| Item | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| Profit | 5 | 2 | 1 | 2 | 3 | 1 | 1 |
| TID | Transaction | TU |
|---|---|---|
| T1 | (A,1) (C,1) (D,1) | 8 |
| T2 | (A,2) (C,6) (E,2) (G,5) | 27 |
| T3 | (A,1) (B,2) (C,1) (D,6) (E,1) (F,5) | 30 |
| T4 | (B,4) (C,3) (D,3) (E,1) | 20 |
| T5 | (B,2) (C,2) (E,1) (G,2) | 11 |
计算TWU，并按降序排列
| Item | TWU |
|---|---|
| C | 96 |
| E | 88 |
| A | 65 |
| B | 61 |
| D | 58 |
| G | 38 |
| F | 30 |
构建UP-tree
构建方法与FP-Growth算法相似
设置min_util=40，删除低效用项重新排列事务
| TID | Reorganize transation | RTD |
|---|---|---|
| T1 | (C,1) (A,1) (D,1) | 8 |
| T2 | (C,6) (E,2) (A,2) | 22 |
| T3 | (C,1) (E,1) (A,1) (B,2) (D,6) | 25 |
| T4 | (C,3) (E,1) (B,4) (D,3) | 20 |
| T5 | (C,2) (E,1) (B,2) | 9 |
利用策略1（DGU），删除F，G项后重新构建UP-tree
D的条件模式基
运用策略1和策略2，
对于{CEABD}这条路径即事务T3来说项B此时的效用为13，因为根据策略DGN，它原来的效用25需减去其后续节点D在T3中的数量乘D的profit即6×2=12。对于同一条路径中的A来说，需减去B，D 由原来的47减去（2×2+6×2）
对于E来说，它需要减去路径{CEABD}、{CEA}、{CEBD}、{CEB}中的后续节点效用
根据策略DGU，DGN，GLU得到如下表
运用四种策略后D的conditional UP-tree