一种高效的最大频繁Embedded子树挖掘算法  

An Efficient Algorithm for Mining Maximal Frequent Embedded Subtrees

作　　者：朱颖雯[1] 吉根林[1] 

机构地区：[1]南京师范大学计算机系,南京210097

出　　处：《计算机科学》2007年第12期175-179,共5页Computer Science

基　　金：江苏省自然科学基金(BK2005135)

摘　　要：提出了一种高效的最大频繁Embedded子树挖掘算法--CMPETree Miner。该算法采用先序遍历序列存储树,并将节点的范围属性加入该序列,采用伪投影技术对频繁子序列进行投影,并对投影序列中的每个节点编码。在挖掘带编码的频繁子序列过程中,对频繁子序列进行高效剪枝,得到最大频繁Embedded子树,无需生成所有频繁Embedded子树。实验结果表明,CMPETree Miner算法是高效可行的。In this paper a novel algorithm, named CMPETreeMiner, is presented to discover maximal frequent embedded subtrees from ordered labeled trees. The algorithm uses preorder sequence to store trees. The attribute of node＇s scope is added in the preorder sequence. Pseudo-projection technique is used during projection and each node is encoded. Mining the encoded frequent sub-sequence can be directly correspond to an embedded frequent subtree. Unlike prevoius works, several techniques are proposed to prune the frequent subsequence that do not correspond to closed or maximal frequent embedded subtree using code and scope information. Experiment results show that CMPETreeMiner is efficient and effective.

关 键 词：Embedded子树 频繁子树 最大频繁子树 闭合频繁子树 数据挖掘 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]