卫朝霞，邹倩影

(1.四川大学锦城学院，四川 成都 611731；2.电子科技大学成都学院，四川 成都 611731)

1 引言

频繁子树挖掘是数据挖掘的主要研究内容，在生物信息、Web结构分析等方面具有较高的应用价值。作为如此有价值的任务，同样也充满挑战，例如，即便使顶点集合缩小到最小范围内，仍然能形成很多结构不一致的树，并且每一棵树的不同节点能够取相同的权，这会导致对树的同构判断非常复杂。

针对上述问题，一些学者给出如下方法。文献[1]提出基于B-list的频繁子树挖掘算法。采用B-list数据结构挖掘频繁项集，将全序搜索树当作搜索空间，通过父等价剪枝方法限制搜索范围，并结合MFI-tree投影技术完成挖掘。实验结果表明，该算法无论在稠密数据集还是稀疏数据集中都有较好挖掘效果。文献[2]提出基于FP-Tree的频繁子树挖掘方法。将数据集合分为大小相同的模块进行挖掘，任意一个模块都运用三角矩阵的方式进行储存，并设计一个NCFP-Tree储存每个滑动窗口中的频繁项集，使用优化挖掘算法将每个窗口中频繁子树全部挖掘出来。该方法挖掘过程简便，挖掘准确率较高。

上述方法虽然简化了挖掘过程，但是不能描述数据对象之间的内在联系，在挖掘中会产生大量的冗余信息，影响挖掘效率。由于数据目标不仅是集合关系，更多时候是具有结构层次的，因此，在模式增长[3]的基础上对嵌入式频繁子树进行挖掘，并在挖掘过程中提出如下要求：数据库必须是大量且真实的；……