ESPM——频繁子树挖掘算法  

ESPM—An Algorithm to Mine Frequent Subtrees

作　　者：朱永泰[1] 王晨[1] 洪铭胜[1] 汪卫[1] 施伯乐[1] 

机构地区：[1]复旦大学计算机与信息技术系,上海200433

出　　处：《计算机研究与发展》2004年第10期1720-1727,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金重点项目 ( 6993 3 0 10 ;60 3 0 3 0 0 8);国家"八六三"高技术研究发展计划基金项目 ( 2 0 0 2AA4Z3 43 0 ;2 0 0 2AA2 3 10 41)

摘　　要：随着互联网的发展 ,频繁模式的挖掘由频繁项集扩展到结构化数据 :树和图 在这些结构上的挖掘工作被应用于更为复杂的领域 ,比如生物信息学、网络日志和XML文档 提出了一个新颖的算法 :ESPM ,以挖掘有序标号树中的频繁子树 不同于以往的工作 ,把树同构的判断工作放到了算法的晚期 ,从而减少了整个挖掘过程的时间开销 人工数据集和真实数据集上的实验都证明ESPM相较于其他算法的优越性With the development of Internet, frequent pattern mining generalizes to more complex patterns like tree mining and graph mining Such applications arise in complex domains like Bioinformatics, web mining, etc In this paper a novel algorithm, named ESPM (expanded subtree pattern miner), is presented to discover frequent subtrees from ordered labeled trees Unlike previous works, the work of distinguishing isomorphism is left in the later part of the algorithm, which minimizes the cost of the whole process The performance of the algorithm is evaluated with experiments on synthetic and real datasets The experimental result shows that the algorithm can do the job well and is better than previous algorithms Finally the potential improvement of ESPM is mentioned

关 键 词：数据挖掘 频繁模式 频繁子树 ESPM 

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