基于加权有向图的权频繁模式挖掘算法

封 军,郑 诚,郑小波,肖 云

(安徽大学 计算智能与信号处理教育部重点实验室，安徽 合肥230039)

在现实世界中，许多复杂问题可以被描述成有向图及在其上的遍历问题，其中具有代表性的实例是WWW的站点访问[1]，可以把每个网站站点模拟成一个有向图，图中的顶点代表Web页面，并代表一个页面到另一个页面的链接，用户在网站上访问的页面记录可以看成在一张图上的遍历，一旦所有的遍历都给出，即可从中挖掘出有用的信息知识。这些信息知识的表现之一就是频繁模式的挖掘发现。而通过这些频繁模式的发现，不仅可以改进网站系统的性能，而且还可以相应地制定出市场决策(例如在用户经常访问的Web页面做产品推销和广告发布等)。此外，如超文本访问、人际关系网络构成等，都可以通过图来模拟其基本特征。所以，图遍历模式挖掘一直是一个研究热点。

针对带权值的有向图的挖掘已不再有效,例如Apriori、FP-增长算法等[4]传统挖掘算法。本文为了解决加权有向图遍历挖掘的问题，提出一种基于有向加权图权频繁模式挖掘算法，简称GTWF算法。对于加权图遍历模式的挖掘，传统的图挖掘没有考虑到带有权值的图遍历模式挖掘[5]，对于此项研究，先前的工作大多是与挖掘加权关联规则和其子问题——加权频繁项集有关的，而没有考虑到带有权值的图遍历问题。

1 基本概念

图1 加权有向图

定义1加权有向图：给某个有向图的每个顶点加上相应权值，这些权值各自代表相应顶点的重要程度，这样的图称作加权有向图。

例如图1,如果把这个有向图看作一个Web站点的结构图，则它有 7个结点{A,B,C,D,E,F,G},每个顶点分别代表一个网页，还有9个边，他们代表两网页之间的链接，并且在每个结点有一个相应的权值,这个权值可以代表用户对这些Web页面的兴趣度[6]，这样的权值可根据用户在Web页面上的停留时间、用户对Web页面访问行为[2](网页滚动条的次数、被收藏的次数等)或访问Web页面的用户数进行分析和评估得出。

定义2路径遍历数据库(Path Traversal Database),如表1,把所有关于有向图上的遍历路径综合到一个数据库D中，这个的数据库称为路径遍历数据库。例如，用户对某一Web站点访问时，把他们各自访问所有Web页面按访问的先后顺序进行排列后，得到一系列访问路径，这样的路径称为在站点结构图上的遍历路径。如路径遍历模式P：＜B,C,E,F＞,即为图1中的一个遍历路径。

定义3支持度，把某一遍历路径模式P在上述数据库D中出现的次数记为count(P),称为P的支持数。关于上述数据库D，设|D|为所有遍历路径的总数。所以P的支持度可以如下定义：

表1 路径遍历数据库D

定义4可扩展模式[3]，若一个模式P扩展为长度更长的模式后，有可能成为频繁模式，则称模式P为可扩展模式。如果判断一个模式P是否具有可扩展性，则P要满足下述情况，给定一个最小支持数 minsup，若 k-模式 P要扩展到 k+1模式，必须满足 count(P)＞=minsup，则称模式P具有可扩展的可行性(Feasible)。例如，设定最小支持数 minsup=2，有 2-模式 P：＜A，B＞，从上述访问路径数据库 D中得出 count(P)=2,然后可得 count(P)＞=minsup,则 P具有扩展 3-模式＜A,B,C＞或＜A,B,D＞的可行性。

定义5权支持度[3](weighted support)，如模式P的权支持度(wsupport)可定义如下：

这里 V＝{v1,v2,...,vn}为图的顶点集合,每一个顶点 vj有一个权 wj≥0，wj∈W,W={w1,w2,...,wn}。

定义6权频繁模式[3]，如果 P为权频繁模式，则 P的权支持度(wsupport)一定要大于或等于给定的一个最小权支持度(minwsup)。数学表达式如下：

所以根据式(1)、式(2)和式(3),如P是权频繁项,可以得到以下的不等式：

把式(4)右边进行向上取整，得到的值定义为P支持数的较低限度(lower bound)，简称为sbound(P)。如式(5)：

最终，综合式(4)式和式(5)，可以得到以下定义，当count(P)≥sbound(P)时，模式 P为权频繁模式。

2 基于加权有向图的权频繁模式挖掘算法

本文提出的基于加权有向图的权频繁模式挖掘算法(简称GTWF算法)过程与传统 Apriori算法基本相似，最主要的过程是剪枝步和候选项的产生，不同的是GTWF算法提出模式的可扩展性的概念，并把它应用到剪枝和候选项产生操作中，这样可以找出可能具有权频模式的所有模式。下面，对GTWF算法的过程进行详细描述。

2.1 剪枝步

在本文算法中，剪枝操作主要是把没有可能成为权频繁模式的候选项剪掉，保留那些有可能成为权频繁模式的候选项。由定义4可知，如果模式P满足条件count(P)≥minsup，则它具有可扩展性，否则 P从候选模式集中剪掉。

结合定义4可得出下列算法：

2.2 候选项的产生

本文算法的候选项主要是从可扩展模式集中产生的，如果一个可扩展 k-模式＜p1,p2,…,pk＞的两个(k-1)-子模式＜p1,p2,…,pk-1＞和＜p2,p3,…,pk＞都是可扩展的，则它们之间有完全向下闭合性。当存在完全向下闭合性时，则可以从可扩展的k-模式集Ck产生一个候选(k+1)-模式集Ck+1，算法描述如下：

2.3 基于有向加权图权的频繁模式挖掘算法（GTWF算法）步骤

GTWF算法的主要过程与Apriori算法基本相似，就是把剪枝操作算法与候选模式产生算法结合在一起。下面是GTWF算法的详细步骤：

2.4 实例分析

通过图1和表1数据做GTWF算法相应的实例分析。假设最小权支持度minwsup=5，最小支持数minsup=2。下面根据GTWF算法步骤做具体实例分析。

(1)根据算法步骤 1，扫描路径遍历数据库 D，得出权频繁模式的最大可能长度u=4,总的数据库记录数|D|＝8。

(2)根据算法步骤2，初始化长度为1的候选模式如下：

C1={＜A＞,＜B＞,＜C＞,＜D＞,＜E＞,＜F＞,＜G＞}

(3)表 2、表 3、表 4和表 5是根据算法步骤 3、步骤4、步骤5循环执行所得出的结果。

得出最终的权频繁模式集为：{＜C,E＞,＜B,C,E＞}。

3 实验分析

本实验是在 Pentium4 3.0 GHz，内存为1GB的PC上进行，算法的实现环境为VC++6.0和SQL Server 2005。实验数据是合成数据,实验数据中加权图的顶点数(v)最多有500个，顶点权值(w)范围为 0＜w≤12。合成路径遍历数据库|D|=10 000,最小权支持度(minwsup)可分别为1,2,3,4,5。最小支持数（m）可分别为 2，3，4，5。

表2 一项模式集

表3 二项模式集

表4 三项模式集

表5 四项模式集

实验研究了不同的最小支持数阈值、最小权支持度阈值、候选遍历模式数、图的顶点数与运行时间的关系。图2、图3分别进行算法性能评估。图2(a)主要说明不同顶点数与执行时间的关系——随着图顶点数的增加，算法执行时间也是递增的。图2(b)主要说明候选遍历模式数与执行时间的关系——随着候选遍历模式数目的增加，执行时间也是呈递增状态。图3随着最小支持数(m)的增加，执行时间将减少，因为当最小支持数增加时，可扩展模式数就越来越少，相应的剪枝等操作也少了，所以执行时间就变少。另外图中还说明随着最小权支持度（minwsup）的增加，执行时间也减少，因为随着最小权支持度的增加，从算法循环一开始，可确定的权频繁模式就减少，直接导致可供下次循环的候选模式也减少了，从而减少了搜索和剪枝等操作，所以执行时间就减少。

本文主要分析讨论了通过加权有向图的遍历来挖掘权频繁模式的问题，提出了解决此问题的GTWF算法。在算法中，利用权支持度、可扩展模式和权频繁模式等概念，并通过剪枝操作和候选模式产生操作来实现算法对图遍历模式的挖掘，最后通过实验对算法的性能进行了验证。实验结果表明算法在可伸缩性与执行性能等方面具有较好的效果。

[1]HEYDARI M,HELAL R A,GHAUTH K I.A graphbased Web usage mining method considering client side data[C].2009 IEEE.

[2]TAO Yu Hui,HONG Tzung Pei,SU Yu Ming.Web usage mining with intentional browsing Data[C].2007 Elsevier Ltd.

[3]LEE S D,PARK H C.Mining weighted frequent patterns from path traversals on weighted graph[C].Department of Computer Engineering,Korea Maritime University,Korea

[4]张云涛,龚玲.数据挖掘——原理与技术[M].北京:机械工业出版社,2004.

[5]韩家炜,KAMBER M.数据挖掘：概念与技术[M].北京：机械工业出版社,2001:351-364.

[6]郭岩,白硕,杨志峰,等.网络日志规模分析和用户兴趣挖掘[J].计算机学报,2005,28(9):1483-1496.