王栓杰 李华 陈智博

【摘要】 在以往的加权遍历模式应用过程中，挖掘是影响最终应用效果的主要问题。相比之下，在全局图遍历基础上加权频繁模式的应用能够有效解决挖掘问题。本文从图遍历分析入手，对基于全局图遍历的加权频繁模式进行研究和分析。

【关键词】 全局图遍历 加权频繁模式

一、图遍历分析

这里以WWW站点访问和在线服务系统为例，对图遍历进行分析：在该过程中，用户需要通过超级链接等有效形式搜索所需内容或感兴趣内容，这个过程是由两个不同数据点之间的转换完成的，可将该结构模拟成一个图，将用户所访问的Web页面中的超级链接看成是图的边，将Web页面看成是图的各个顶点，将用户的访问过程看成是该图中的遍历。

二、基于全局图遍历的加权频繁模式

1、剪枝策略。数据挖掘是传统加权遍历模式应用过程中存在的主要问题之一。剪枝策略的应用则可以有效提升模式的挖掘性能。在剪枝策略中，需要将成为加权频繁模式可能性较低的候选模式项逐渐减掉，从保留的可能性较高的候选模式项中获得最终的加权频繁模式。

2、产生候选项策略。为了获得新的候选模式项，可以使得原本的扩展模式中存在一个向下闭合特性，进而从该模式的候选模式中获得新候选模式向。

3、基于全局图遍历的加权频繁模式。这里在结合剪枝策略与产生候选项策略的基础上，达到从全局图遍历中娃聚加权频繁模式的目的。该目的是通过以下算法步骤实现的：首先，将加权支持度的最小值、遍历数据库Q以及加权有向图W输入。当上述数据输入完成后，会获得加权频繁模式列表L1的输出。在后续的计算过程中，首先要将加权频繁模式可能长度的max找出来，然后将初始化长度设置为1，得出相应的候选模式。第三，需要对当前候选模式的支持度计数进行计算。第四，完成相应加权频繁模式的确定。第五，从上述操作的数据中得到剪枝候选模式集。

三、基于全局图遍历的加权频繁模式的实验分析

1、基于全局图遍历的加权频繁模式的实验环境。计算机为3.03GHz Pentium IV PC，Windows XP Professonal操作系统，内存为812M。上述设备能够为加权频繁模式实验提供SQL Server2000的软环境，该环境的作用是对WDG和WDG遍历进行模拟。除此之外，设备还能为实验提供VC++6.0的软环境，该环境的作用是实现基于全局图遍历的加权频繁模式挖掘算法。

2、生成合成数据方面。在实验过程中，全局图中所含顶点数目Bn以及各个顶点能够连接边数量的最大值Ymax是实现DG的两项主要参数。顶点数目的范围为100-400；一个顶点连接边数量的最大值取值范围为[1，4]。当DG生成过程结束之后，对其中顶点进行随机赋值，权值Wi的赋值过程完成之后即生成WDG。为了保证后续算法性能比较的有效性，共计生成八组不同的遍历数据，并将其组成一个数据库。 将各族遍历中可遍历模式长度的最大值变化范围控制在5-10之间，并对其应用相同的权值集进行计算。

3、性能方面。这里对基于全局遍历图的加权频繁模式挖掘算法与Apriori算法在性能方面的差别进行比较。这里主要讲算法的性能比较对象确定为运行执行时间以及可扩展模式数量。就运行执行时间而言，在Max-L为7的情况下，基于全局图遍历的加权频繁模式挖掘算法与Apriori算法的实际运行执行时间会随着加权支持度最小值的不断降低而逐渐增加。如果加权支持度最小值越小，二者之间的性能差别则表现得更加明显。从加权支持度最小值的变化过程中可以发现，由于基于全局图遍历的加权频繁模式挖掘算法的频繁模式挖掘操作具有权值约束特点，这种特点可以实现对候选集搜索空间的有效控制，且该过程中涉及的剪枝操作较少，进而使得该算法产生较好的性能。相比之下，另一种算法的频繁模式挖掘不带权值约束，其搜索模式空间相对较大，因此性能相对较差。就可扩展模式数量而言，在Max-L逐渐减少的情况下，基于全局图遍历的加权频繁模式挖掘算法的可扩展模式数量逐渐增加。

4、可扩展性方面。就基于全局图遍历的加权频繁模式挖掘算法的可扩展性实验而言，在Max-L为7的情况下，当遍历图中顶点数发生减少变化时（其变化范围为100-400），基于全局图遍历的加权频繁模式挖掘算法的执行时间也会相应地减少。当遍历图中包含顶点数增加时，该算法的实际执行时间会发生相应的增加。除了执行时间之外，顶点数量的增加变化还会造成候选集的增大，进而引发其搜索时间的延长。从实验中可以看出，在EGTG方式下，基于全局遍历图的加权频繁模式挖掘算法的可扩展性较好，其数据集尺寸与实际执行时间之间的关系为分段线性关系。

结论：加权遍历模式应用存在的主要问题是其无法实现目标数据的有效挖掘。对此，这里通过成为加权频繁模式可能性较低的候选模式项的剪掉策略以及候选项产生策略的基础上，得出一种基于全局图遍历的加权频繁模式，该模式挖掘算法具有良好的可扩展性和性能。

参 考 文 献

[1]耿汝年. 加权频繁模式挖掘算法研究[D].江南大学，2008.

[2]肖港松，陈晓云. 基于加权动态网络的频繁模式挖掘研究[J]. 微型机与应用，2011，19：7-10.