柴然++刘媛媛++郭彦颖

[摘 要]最大频繁子图挖掘得到的结果数量少而且不会丢失信息，有益于对结果的理解和应用。为了避免挖掘所有频繁子图，降低挖掘难度，本文应用决策树挖掘最大频繁子图。挖掘过程中，首先构造决策树，然后对决策树进行剪枝得到最大频繁子图，最后通过实验验证算法的可行性以及正确性。

[关键词]数据；挖掘；最大频繁子图；决策树；子图同构

doi：10.3969/j.issn.1673 - 0194.2017.04.099

[中图分类号]TP301.6 [文献标识码]A [文章编号]1673-0194（2017）04-0-02

基于图的数据挖掘提出时间不长，但图论作为数学的研究领域已经有了很长的历史，所以频繁子图挖掘得以很好地发展。但是频繁子图挖掘得到的结果数量巨大，影响着对结果的理解、应用以及分析工作。最大频繁子图包含了所有频繁子图，挖掘最大频繁子图可以保证信息的完整性，而且挖掘最大频繁子图可以得到少量结果从而节省了空间，简化了分析工作。基于此，可以将频繁子图挖掘转换为最大频繁子图挖掘。MARGIN算法和SPIN算法是经典的最大频繁子图挖掘算法，它们必须挖掘出所有的频繁子图，然后再挖掘最大频繁子图。虽然最大频繁子图挖掘得到的结果少了，但挖掘过程很复杂，难度很高。

针对最大频繁子图挖掘算法中存在的问题，本文提出新的最大频繁子图挖掘算法DMFS（Decision tree to Mining Maximal Frequent Subgraph）。DMFS算法利用决策树来挖掘最大频繁子图，首先构造决策树，其次对决策树进行剪枝（剪掉决策树中不频繁的节点），最后通过剪枝后的决策树来得到最大频繁子图集合。……