ESPM--频繁子树挖掘算法.pdfVIP

第41卷第10期 计算机研究与发展 Vd．41．No．10 oct．2004 2004年10月 oFa姗UTERRESEARCHANDDEVELOPMENT JCH珉NAL EsPM——频繁子树挖掘算法 朱永泰 王 晨 洪铭胜 汪 卫 施伯乐 (复旦大学计算机与信息技术系上海200433) (yt-zhu@fudan．edu．cn) 摘要随着互联网的发展，频繁模式的挖掘由频繁项集扩展到结构化数据：树和图．在这些结构上的挖掘工作被应用 于更为复杂的领域，比如生物信息学、网络日志和x№文档．提出了一个新颖的算法：EsPM，以挖掘有序标号树中的频 繁子树．不同于以往的工作，把树同构的判断工作放到了算法的晚期，从而减少了整个挖掘过程的时间开销．人工数据 集和真实数据集上的实验都证明EsPM相较于其他算法的优越性．还提出了一些可能的改进． 关键词数据挖掘；频繁模式；频繁子树；ESPM 中图法分类号TP311．13 ESPM—An toMine Subtrees AlgorithmFrequent ZHU NG SHIBai—Le Chen，HONG Wei，and Y。ng—Tai，WANG Ming—Sheng，WA 200433) (＆抛以铆删0，CD例毗}i馏口以J咖口￡洳T0如加妞y，F讹nmi御百匆，勖硎咖i AbstractWiththe of tomore developmentIntemet，frequentpattemmininggeneralizescOmplexpattems liketree and ariSein domainslike mininggraphmining．Suchapplicationscomplex this anovel subtree miner)，is mining，etc．In aIgorithm，namedESPM(expandedpattem presented paper todisoover subtreesfrclmordered1abeledtrees．Unlike wo】．kof works，the frequent previous inthelater ofthe minimizesthecOstofthewhOle isleft iSOmorphism part algo“thm，which pr。ceSs．The real The ofthe is evaluatedwith on and dataSets． algorithm experirnentssynthetic perfonnance shawsthatthe candothe weUandisbetterthan reSult experimental