关联规则挖掘算法-CATS Tree(Compressed and Arranged Transaction Sequences Tree)

小咪咪 2022-06-05 23:25 142阅读 0赞

## CATS Tree ##

压缩排序事务树  
FPTree的一个扩展  
允许单路径频繁模式挖掘  
适用于**多种支持度、流数据、增量数据**的情况

## 算法基本过程 ##

数据集

![这里写图片描述][SouthEast]  
新建root节点  
扫描TID1,构建CATS Tree 每个节点计数为1  
扫描TID2，可以看出两条数据的共同路径是f-a-c-m,而已构建额树结构中不包含item：d  
则从d的父节点M建立分支，将之后的节点顺序加入facm节点数加1，其余新增节点计数为1，,如图figure1所示  
扫描TID3,B,F,H,J,O 共同路径为f,则f节点计数加1，同时在f顺序增加子节点bhjo,计数为1  
![这里写图片描述][SouthEast 1]

扫描TID4，这里没有共同的项，则直接在root节点下新增子节点，顺序添加，计数为1，如图figure2  
扫描TID5，这里与原树相比较，有共同项f-a-c-m-p，则触发了p节点与前置节点d的交换  
当p节点交换结束，没有共同项，TID5中剩余的项在路径f-a-c-m下新建分支，顺序加入，计数增1  
![这里写图片描述][SouthEast 2]

**CATS Tree 与 FP-Tree的比较**  
CATS Tree：  
包含事务中所有的项  
子树被局部优化以改善压缩  
从root到叶子节点的路径中项的排序是根据局部支持度计数  
同一个父节点的CATS节点根据局部支持度计数按降序排列

FP-Tree:  
只包含频繁项  
子树不是局部优化的  
从root到叶子节点的路径中项的排序是不是根据局部支持度计数  
一个节点的所有子节点不是有序的

## 性质 ##

1）所有子节点的频繁度计数之和小于等于父节点  
2）一个节点的所有子节点是有序的

## 伪代码 ##

Algorithm: CATS Tree Builder
    Input: set of transactions
    Output: CATS Tree
    1. PROCEDURE CATSTreeBuilder(input_set S) 2. for all transactions t Î S 3. for all i Î t 4. i.(frequency in header)++;
    5. root.add(t);
    6. PROCEDURE add(transaction t) 7. if (this.children Ç t ¹ Æ) 8. child node.merge(t);
    9. else if (this.descendant Ç t ¹ Æ))
    10. swap descendant node and split child
    node if necessary;
    11. descendant.merge(t);
    12. else
    13. this.children ¬ t;
    14. Reposition the merged node if necessary;
    15. PROCEDURE merge(transaction t) 16. this.frequency++;
    17. remove this.item from t;
    18. node.add(t);

## 参考文献 ##

【1】Cheung W, Zaane O R. Incremental Mining of Frequent Patterns without Candidate Generation or Support Constraint\[C\]// Database Engineering and Applications Symposium, 2003. Proceedings. Seventh International. IEEE, 2007:111-116.

[SouthEast]: /images/20220606/47c8ce59e65b4f4099b503b505341b4a.png
[SouthEast 1]: /images/20220606/72ae62cdb97b437fbef65acd62d08bd3.png
[SouthEast 2]: /images/20220606/cc2b33d331dd41fa9bb8a7438b5324af.png