PFTM:一种基于投影的频繁子树挖掘算法  

PFTM: A Frequent Subtrees Mining Algorithm Based on Projection

作　　者：杨沛[1] 郑启伦[1] 彭宏[1] 李颖基[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广州510640

出　　处：《计算机科学》2005年第2期206-209,共4页Computer Science

基　　金：广东省科技攻关项目(C10201;A1020103)资助

摘　　要：频繁子树在Web挖掘、XML文档分析、生物信息处理等领域有着重要的应用。提出了一种新的基于投影的频繁子树挖掘算法(PFTM),通过对数据库和候选节点集进行投影,并采用递推式候选节点集更新技术来有效地压缩搜索空间,以高效地从森林中挖掘出频繁子树。PFTM不需要产生候选子树。性能对比实验表明,PFTM是有效和可扩展的,而在算法效率上,PFTM要比FREQT平均高出40％左右。Mining frequents subtrees is very useful in domains such as Web mining,XML data analysis,bioninformat- ics,and so on. A novel algorithm called PFTM to discover all frequent subtrees in a forest based on projection is pre- sented. The process partitions both the projected database and the set of candidate nodes. No candidate subtree need to be generated by PFTM. An novel method of recursive updating the set of candidate nodes is applied to greatly reduce the search space. We contrast PFTM with FREQT. We conduct detailed experiments on synthetic datasets to test the performance and scalability of these two methods. Experiments show that PFTM outperforms the FREQT by an aver- age of 25 percent.

关 键 词：挖掘算法 可扩展 投影 XML文档 WEB挖掘 算法效率 数据库 点集 对数 搜索空间 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TP301.6[自动化与计算机技术—计算机科学与技术]