半结构化文档数据流的快速频繁模式挖掘.pdfVIP

维普资讯 第36卷第3期 东南大 学学报 (自然科学版) Vo1．36 No．3 2006年5月 JOURNAL OFSOUTHEAST UNIVERSITY (NaturalScienceEdition) M ay 2006 半结构化文档数据流的快速频繁模式挖掘 赵传 申 孙志挥 (东南大学计算机科学与工程学院，南京210096) 摘要：为了提高半结构化文档数据流的挖掘效率，对原有挖掘算法StreamT进行了改进，提出了 一 种半结构化文档数据流的快速频繁模式挖掘算法——FstreamT．该算法针对利用集合存储候 选频繁模式效率较低的缺点，采用枚举树存储候选频繁模式，可以有效地提高对候选频繁模式集 合进行查找和更新的效率，同时利用频繁模式的单调性和枚举树的特点减小了维护负边界的搜 索空间，从而提高了整个算法的效率．理论分析和实验结果表明，算法FStreamT与算法StreamT 相 比具有较高的效率，是有效可行的． 关键词：数据挖掘；频繁模式；数据流；枚举树 中图分类号：TP311 文献标识码：A 文章编号：1001—0505(2006)03-0452-05 Fastminingfrequentpatternsin semi-structureddata stream ZhaoChuanshen SunZhihui (SchoolofComputerScienceandEngineering，SoutheastUniversity，Nanjing210096．China) Abstract：Toimprovetheefficiencyofthesemi—structureddatastream mining，afastalgorithm for miningrfequentpattemsrfom semi—sturctureddata srteam ，FStreamT，isproposedbasedon Stre- amT．Tosolvehteproblem oflow efficiencyofstoringfrequentpatternsinset，thisalgorithm stores rfequentpatternsinenumerationtree，which ismoreefficientwhensearchingandupdatinghtefre- quentpattem set．andathtesametimereducestheserach spaceofmaintainingthenegativeborder usinghtemonotonicityofrfequentpattem andhtechraacteristicsofenumeration tree．Theoretical analysisandexperimentalresultsshow thattheFStreamTalgorithm isfeasibleandmoreefficientthan theStreamT algorihtm． Keywords：datamining；rfequentpattem ；datastrema ；enumerationtree 近几年由于网络技术和WEB技术的发展，数 SOAPl2通过 Intemet传送不同种类的弱结构数 据流应用迅速发展起来．此时数据不像原来那样完 据．由于传统的数据挖掘方法不能直接应用到此类 整地存储在数据库中，而是以序列 (流)的形式到 数据流的挖掘中，因此如何高效地在这类数据流中 达．在数据流的应用中，无法控制数据到达的顺序， 挖掘有用信息非常重要． 也不能将流数据完整地存储在本地．数据流的应用 半结构化数据中的频繁结构挖掘有不少学者 领域比较广泛，例