概率频繁模式挖掘算法研究综述

苏莉

摘 要

本文围绕图集中的频繁子图挖掘算法、单图中的频繁子图挖掘算法两个方面展开讨论，对概率频繁模式挖掘算法进行了研究以及综述，并在此基础上提出了一些笔者自己的见解，希望能够对今后的概率频率模式挖掘算法的研究提供一些理论建议。

【关键词】概率频繁模式 挖掘算法

现阶段，已有越来越多高效的算法被研发出来，用于对图集进行挖掘，其中也不乏有一些算法是用作对单图中的模式进行挖掘的，由于这些算法的应用对象有所差别，因此他们的效果也存在一定的差异。而针对任何一个实际存在的问题，最大的挑战在于如何进行有效解决。在这一需求下，我们需要将这些不同的算法进行分类。在本文中，笔者主要针对概率频繁模式挖掘算法展开了研究与综述，并根据图的频繁子图挖掘算法的应用对象分为图集以及单图两类。

1 图集中的频繁子图挖掘算法

1.1 依托贪心搜索的挖掘算法

有关贪心搜索下的频繁子图挖掘算法，早在一九九四年就已经获得了两大代表性的研究成果，分别为SUBDUE以及GBI，笔者以SUBDUE举例进行说明。SUBDUE是在最小描述长度原则下，使用定点替代方式来识别出所有能够有效压缩原始输入数据的模式。这一算法的以仅含有输入图 G中的一个定点所对应的子图为起点，在逐渐加入顶点的方式下使子图得到扩展。此外，SUBDUE还有一大优势即在于它能够实现与子图近似值的匹配，此外它还能够同预先定义子图的方式来实现背景知识的嵌入。SUBDUE运用了一种启发式搜索模式来降低搜索空间大小，以此来达到提升计算性能的目的。此后，SUBDUE还被拓展成为了一种图分类算法，被称作SUBDUECL。这种新的算法不需要再使用最小的描述长度，而是使用以子图置信度的启发模式所取代。

另外一种GBI算法与SUBDUE存在极大的共同点，它也是使用一个顶点来替代每一个所识别的子图从而来实现压图像的不断压缩，从而使图规模不断缩小。它使用了经验图规模定义，充分反映了压缩图以及图区模式的规模，这种搜索方式的优势在于对不间断压缩产生了妨碍作用。此外，GBI还能够对有闭路径中的有向或者无向标签图进行处理。搜索时的每一个环节都是使用边或块老搜索到对应的连接顶点集合，在规范化标记法的应用下确认获取的子图是否结构相同。GBI还是一种特征构造器，可以对图数据中的决策树分类器特征进行构造。

1.2 依托ILP的挖掘算法

我们可以简单地使用一阶逻辑来对图进行表达，因此在此基础上设计了一个以ILP为依托的挖掘算法。在ILP算法的基础上能够总结出一个可以对正负样本集进行准确分类的规则集合 。在ILP系统中对图模型进行构建时，杉树规则一般来说所对应的均为子图，基本上所有基于ILP的方法从根本上分析都未贪心算法，使用各种不同的启发方式对可能的假设结果进行剪辑。由此可见，它们更加倾向于识别一些支持性较高的子图，而由DEHASPE等设计的ILP系统WARMR则另当别论，它不是在图形结构处理这一需求导向下而特意设计而成的，同时也没有使用图模型 特定的优化技术，所以说它对应的计算量极高。此外，还有一个特例为WARMR系统，但是该系统在计算过程中较为复杂，因此一般情况下我们都将其应用在出现频率较高的子结构当中。

2 单图中的频繁子图挖掘算法

SUBDUE与GBI不仅能够应用在频繁子图外界当中，同时它也是目前知名度最高的单图频繁子图挖掘使用顶点编号对输入图进行有损性压缩，在此基础上获得一种数据结构，叫做SUMMARY，这一数据机构能够在短时间内排除所有频率较低的候选子图，若图中的子图类型较少但频率极高，就能够将这一方法进行有效发挥，反之则无法有效发挥其效果。其中值得一提的是，有损压缩、SEUS算法以及上文提到的两种算法都不具备较高的精确度，Vanetik等研究学者设计了一种依托边的子图增長策略而形成的算法，这种算法能够应用在带有标识的无向单图当中，此外还能够对一切包含在内的频繁子图进行准确挖掘，在这种算法当中，每一个嵌入间边均无法叠加在一起，且每一种子图对应的嵌入数量实际上也就是这一子图的发生频率。二零零五年，Ku-ramochi等研究学者设计了SiGram（ Pafi）算法，并与此同时提出了子图间边叠加频繁的这一问题，然而遗憾的是，并没有针对这一问题提出对策，这一算法抓住了边无法叠加子图反向闭包的这个特点，并使用了广度以及深度两个截然不同的增长办法进行计算，实现了有效的子图挖掘目的。可叠加挖掘算法对于后基因组分子生物学来说具有十分关键的意义。

3 结束语

随着社会的不断发展，各种现代化科学技术也在飞跃进步，如生物信息学、计算机网络学、Web分析学以及化学情报学等，这些学科的发展使得图数据变得更加重要了，尤其是在一些结构问题十分复杂的建模过程中，其重要性得到了不断的突显。为了能够实现对图的深入特征化分析以及分类分析，频繁子图挖掘技术所肩负的任务也越来越艰巨。在本文中，笔者针对典型频繁子图挖掘算法进行了详细的综述，并对这些算法的具体应用情况以及相互之间的关系进行了重点介绍，并提出了这些算法各种存在的不足以及长处。站在理论角度来分析，频繁子图挖掘算法无论是在同构还是在图特征方面都存在着许多问题，因此在今后的研究过程中还具有很大可挖掘的价值，现阶段已经发展成为了数据挖掘领域中的重点研究内容。从一九九四年至今，该领域相关的论文已发表数百篇，足已显现出其可观的发展趋势。

参考文献

[1]乔少杰，韩楠，丁治明，金澈清，孙未未，舒红平.多模式移动对象不确定性轨迹预测模型[J].自动化学报：1-11.

[2]杜戈王子.概率频繁模式挖掘之U-apriori算法研究[J].湖南城市学院学报（自然科学版），2013（03）：71-75.

[3]韩蒙.RAKING：一种高效的不确定图K-极大频繁模式挖掘算法[A].中国计算机学会数据库专业委员会.NDBC2010第27届中国数据库学术会议论文集A辑一[C].中国计算机学会数据库专业委员会，2010：9.

[4]唐懿芳，穆志纯，张师超，钟达夫.挖掘数据流频繁模式的相关技术和算法研究综述[J].计算机工程与应用，2009（26）：121-125.