在學習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
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/292545.html
標籤：其他