论文部分内容阅读
数据挖掘(Data Mining, DM)是从大型数据库或数据仓库中提取隐含的、未知的、非平凡的及有潜在价值的信息或者模式。在数据挖掘概念提出以来十几年间,数据挖掘技术得到日益的重视和广泛的应用、研究。因此,作为数据挖掘重要分支的频繁项目集和关联规则的挖掘,更是引起了广泛的关注且得到的较大的研究、发展。随着数据挖掘应用领域的不断扩大和涉及到的数据种类的增多,特别是网络技术的发展,面向传统领域的结构化关系数据库和事务数据库的挖掘技术,不能满足非传统领域的数据挖掘技术的要求,比如:半结构化数据类型和非结构化数据类型。而这些数据类型在生物信息学、Web挖掘、化合物结构分析等领域有着广泛的应用。本文对面向非结构化数据——树和无环图的挖掘技术进行了深入的研究和分析。主要工作包括:首先,对数据挖掘技术的相关背景知识进行深入的介绍和分析。其中,重点阐述数据挖掘技术的一个重要分支——关联规则挖掘。综述关联规则挖掘的不同种类,并对其中的频繁项集挖掘做了全面深入的介绍。其次,对面向树结构的挖掘技术主要算法作了归类,并比较两大类算法的效率,得出结论深度优先的算法效率较高。这样为本文的研究方向找准了的切入点,在后面作者的算法采用的是面向深度优先,垂直搜索的方式。然后,分析当前采用深度优先算法中效率较高的两个经典算法,TreeMiner和FreeTreeMiner,总结和分析它们的优缺点,并为作者后续算法所用。然后,对面向无环图(自由树)类型的算法作了规划,共分4个步骤:(1)寻找自由树的中心点,对此,作者提出高效的LWA(Longest Way Algorithm)算法,并证明该算法的正确性和高效性。(2)对有根无序树作规范化,作者在这里提出规范化算法Canonicalization,并分析此算法的时间复杂度,证明其时间复杂度与当前效率最高的同类算法相当。(3)挖掘频繁序列模式,作者把“同分异构”的思想引入频繁序列挖掘,较大幅度的提高算法的速度效率。(4)引入索引的方法挖掘具有相同序列的不同结构的频繁子树。最后,本文用实验比较了算法SFTM(SequenceFreeTreeMiner)和类似的Chopper算法,FreeTreeMiner算法,验证了SFTM算法的高效性和正确性。