0 引言

数据挖掘指的是从大量的数据中通过相应的算法发现隐藏于其中未知且可能有用的信息^[1-2]。在数据挖掘领域，频繁模式挖掘始终扮演着至关重要的作用^[3]。在传统的频繁模式挖掘过程中，用户需要输入最小支持度阈值来生成满足条件的频繁模式集合，因此传统的频繁模式挖掘可能会产生以下两个问题^[4]： 1) 用户很难准确设置合适的最小支持度，如果阈值太小可能会产生大量的频繁模式，阈值太大可能会把某些关键信息过滤掉；2) 传统的频繁模式挖掘结果中往往包含大量用户不感兴趣的关联规则。

基于上述问题，Han等^[5]提出了一种新的挖掘任务——Top-k的频繁闭模式，其中k是被挖掘的频繁闭模式的数量，并且模式的最小长度为min_l。为了更好地解决上述问题，Wang等^[6]提出了一种有效的挖掘算法——TFP(Top-k Frequent Patterns)算法。然而，在Top-k的频繁闭模式过程中，用户同样需要输入参数min_l，这对于用户同样是很难精确把握的。在此基础上，Deng等^[7]提出了一种Top-Rank-k频繁模式的挖掘任务，并且提出了解决该问题的FAE(Filtering And Extending)算法。与Top-k的频繁闭模式不同的是，在Top-Rank-k频繁模式挖掘过程中，用户不需要设置参数min_l；由于此挖掘过程中是按照Rank-k对于候选模式进行筛选，因此能够包含更多用户感兴趣的规则。

在上述学者的研究基础上，Fang等^[8]在FAE算法的基础上，采用一种数据垂直分布的形式，将频繁模式的计数转化为一种Tid-lists相交操作，有效地提高了挖掘效率。Deng^[9]将事务数据库采用PPC-tree进行存储，对所有的项集按照Node-list进行编码，将Top-Rank-k频繁模式挖掘转化为Node-list的操作，提出了NTK(Node-list Top-Rank-K)算法。Huynh-Thi-Le等^[10]在NTK算法的基础上，将Subsume的概念及其相关性质应用到Top-Rank-k频繁模式中，提出了iNTK(improved Node-list Top-Rank-K)算法。由于PPC-tree在构建采用“先建树后编码”的方式，所以该过程需要扫描两次事务数据库，随着事务数据库的增加，算法效率有待提高，因此Dam等^[11]采用一种“边建树边编码”的方式，设计和实现了更加有效的数据结构——TB-tree，并在此基础上采用B-list的方式进行编码，提出了更加有效的BTK(B-list Top-Rank-K)算法。

本研究团队一直从事中医方剂中治疗消渴病^[12]方剂的数据挖掘工作。消渴病是以多饮、多食、多尿、身体消瘦，或尿浊、尿中有甜味为主要表现的一种临床常见病、多发病，严重危害着人类的健康，中医对于消渴病的预防和治疗有着丰富而且独特的经验^[13]，因此，对《中医方剂大辞典》中收录的治疗消渴病肾阴虚型方剂的研究也尤为重要。在研究中发现，在实际中医方剂数据挖掘中，用户很难设置合理的最小支持度阈值，因此相比传统的频繁模式，Top-Rank-k频繁模式挖掘更加具有实际应用价值。此外，治疗消渴病相关症型的方剂中往往存在大量的频繁k-itemset，而相比1-itemset、2-itemset而言，k-itemset(k≥3) 对于治疗消渴病肾阴虚型也更具有重要的临床参考价值。同时，在对方剂数据库的Top-Rank-k频繁模式挖掘过程中，上述传统的算法在找到频繁项集结果后，却不能有效发现该频繁项集所对应的方剂名称，而方剂名称和频繁项集的对应关系，对方剂规律分析具有重要意义。

因此，针对上述研究问题，本文提出了一种基于带权无向图(Weighted Undirected Graph,WUG)的Top-Rank-k频繁模式挖掘算法 (Top-Rank-k frequent patterns mining algorithm based on WUG,WUG_TK)。该算法在动态位向量(Dynamic Bit Vector,DBV)^[14]的数据结构基础上引入相关的性质对无向图中的权重进行压缩存储，可以有效地提高空间效率；同时通过搜索频繁项集环，大幅减少对原始数据库的扫描次数，避免产生大量的候选项集，能够直接有效地挖掘出满足条件的k-itemset(k≥3) ，并且快速回溯到该频繁项集所对应的方剂名称，提高对于中医方剂数据挖掘效率。

1 系统模型 1.1 基本概念

本文系统模型为，存在项集I={I₁,I₂,…,I_m}，事务数据库D={〈TID,T〉|T⊆I}，其中：TID为代表每一条事务的标识符；T为项的集合称为模式或者项集；T的支持度用Sup(T)表示。本文中所涉及到的概念介绍如下：

  定义1  模式的Rank。假设存在某模式A，以及事务数据库D，A模式的Rank记为R_A，则：

$RA=|\{Sup(X)\}|X\subseteq I\wedge Sup(X)\ge Sup(A)\}|$

其中|Y|表示集合Y里面的元素数目。

例如在表 1的事务数据库中，I₂分别出现在TID₁、TID₂、TID₃、TID₄、TID₅模式中，Sup(I₂)=5，通过计算其他模式的支持度可以发现Sup(I₂)最大，因此{I₂}的Rank为1，记为：R_I2=1。

  定义2  Top-Rank-k频繁模式。假设存在事务数据库D和阈值k，∃A⊆I，如果R_A≤k，那么A为Top-Rank-k频繁模式。

Top-Rank-k频繁模式挖掘的目的是在给定的事务数据库D和阈值k基础上，发现所有的模式Rank不超过k的模式集合，记为S_Top-Rank-k，则：

$S\text{Top-Rank-}k=\{X|X\subseteq I\wedge RX\le k\}$

例如在表 1的事务数据库中，假设k=3,则满足条件的Top-Rank-k频繁模式如下所示：

$\begin{align} & S\text{Top-Rank}-k=\{\{I1\},\{I2\},\{I1I2\},\{I4\},\{I5\}, \\ & \{I1I4\},\{I1I5\},\{I2I4\},\{I2I5\}, \\ & \{I1I2I4\},\{I1I2I5\}\} \end{align}$

文献[7]中已经证明Top-Rank-k频繁模式挖掘过程满足反单调性，即：∃模式A⊂B，如果模式A不是Top-Rank-k频繁模式，那么B也一定不是Top-Rank-k频繁模式。

1.2 DBV数据结构

Top-Rank-k频繁模式挖掘过程中，如何对数据进行高效存储十分重要。Dong等^[15]提出的BitTable-FI和Song等^[16]提出的Index-BitTableFI都是根据事务的数量，采用一种基于数据垂直分布的定长的方式进行储存。当处理数据比较稀疏时，BitTable-FI和Index-BitTableFI会造成空间的浪费，因此，本文采用一种更加高效的数据结构——动态位向量(DBV)^[14]进行存储，并且在此基础上引入了有关DBV的定义以及与本文算法有关的性质和操作。

DBV数据结构包含两个域，用二元组的形式表示：〈Pos，BVecor〉，其中:Pos表示存储的第一个非0位的位置； BVecor表示从Pos开始到尾部最后一个非0位置的所有二进制位(本文中采取十进制的形式表示)。

例如，在表 1中，n=5，在申请1个char类型存储空间(8位)的情况下，按照从低位到高位的按位存储，项I₁存在的TID为2，3，4，5，即：t(I₁)=〈0,1,1,1,1,0,0,0〉，项I₁二进制位存储方式如图 1所示。

由此可见，当数据比较稀疏时，低位和高位存储的0会造成空间浪费，因此采用DBV数据结构进行存储，如图 2所示。

在t(I₁)=〈0,1,1,1,1,0,0,0〉中，存储的第一个非0位的位置是1，所以Pos=1，则项I₁的DBV存储方式为：

$\begin{align} & DBV(I1)=\langle 1,\langle 1,1,1,1\rangle \rangle = \\ & \langle 1,\langle {{2}^{1}}+{{2}^{2}}+{{2}^{3}}+{{2}^{4}}=30\rangle \rangle =\langle 1,30\rangle \\ \end{align}$

下面介绍两个DBV之间的相交操作。

  定义3  对于任意两个DBV，假设DBV₁=〈Pos₁,BVector₁〉，DBV₂=〈Pos₂,BVector₂〉，当且仅当DBV₁∩DBV₂=DBV₁时，DBV₁是DBV₂的子集，即：DBV₁⊆DBV₂。

  定义4  对于任意两个DBV，假设DBV₁=〈Pos₁,BVector₁〉,DBV₂=〈Pos₂,BVector₂〉，当且仅当Pos₁=Pos₂,|BVector₁|=|BVector₂|,∀i∈[0,| BVector₁|-1]，BVector₁[i]=BVector₂[i]，则DBV₁与DBV₂相等，即：DBV₁=DBV₂

  性质1 对于任意两个DBV，假设DBV₁=〈Pos₁,BVector₁〉，DBV₂=〈Pos₂,BVector₂〉，如果Pos₁+| BVector₁|＜Pos₂或者Pos₂+|BVector₂|＜Pos₁，则DBV₁∩DBV₂=∅。

  证明 当Pos₁+| BVector₁|＜Pos₂时，表明所有DBV₁的非0元素对应DBV₂的0，所以〈Pos₁,BVector₁〉和〈Pos₂,BVector₂〉进行 & 操作时，结果为0，即：DBV₁∩DBV₂=∅；

当Pos₂+|BVector₂|＜Pos₁时，同理可证。

对于两个DBV之间的相交操作之前，首先要对于DBV₁和DBV₂进行相交操作，以判断是否存在子集、相等、空集，如果存在，则由上述定义3、定义4和性质1直接进行计算。否则，从Pos_max的位置对BVector进行 & 操作，如果 & 操作结果为0，则Pos_max+1，直到 & 操作结果为1，则Pos_max记录下该位置；从该位置开始进行 & 操作，一直到剩余位都是0。具体算法DBV_Intersection如下所示：

  Input: DBV₁=〈Pos₁,BVector₁〉,DBV₂=〈Pos₂,BVector₂〉

  Output: DBV_final

  Procedure DBV_Intersection(DBV₁,DBV₂)

  1)  Pos=max(Pos₁,Pos₂)

  2)  i=Pos₁＜Pos₂? Pos₂-Pos₁ : 0

  3)  j=Pos₁＜Pos₂? 0: Pos₁-Pos₂

  4)  count=|BVector₁|-i＜|BVector₂|-j?|BVector₁|-

      i:|BVector₂|-j     //intersection操作中的位数

  5)  while count>0 and BVector₁[i] & BVector₂[j]=0

      //找到第一个非零位

  6)  i=i+1; j=j+1;

  7)  Pos=Pos+1;count=count-1;

  8)  i₁=i+count-1; j₁=j+count-1;

  9)  while count>0 and BVector₁[i₁] & BVector₂[j₁]=0

      //找到最后一个非零位

  10)  i₁=i₁-1; j₁=j₁-1;

  11)  count=count-1;

  12)  For k=0 to count-1   //找到进行intersection操作的位置

  13)  BVector[k]=BVector₁[i] & BVector₂[j]

  14)  i=i+1; j=j+1;

  End procedure

如图 3中所示，DBV(I₃)=〈0,〈1,1〉〉，DBV(I₁)=〈1,〈1,1,1,1〉〉，则从Pos_I₁开始对DBV数据结构中的BVector进行 & 操作，则DBV(I₁ I₃)=〈1,1〉=〈1,2〉。

1.3 带权无向图

针对中医方剂Top-Rank-k频繁模式挖掘，本文采用一种带权无向图对于Top-Rank-k频繁模式进行存储，该算法可以直接产生更加符合中医数据特点的频繁模式(k-itemset,k≥3) ，而且可以有效地回溯到该频繁模式所对应的方剂名，这对于中医方剂数据挖掘有着重要意义。另外，该算法还可以避免产生大量的候选项集，提高算法效率。

本文中带权无向图中的节点由项集I中的项组成；节点项之间如果是Top-Rank-k频繁模式，则有边；1-itemset为点集V；E为边集；E(V_x,V_y)表示点V_x和V_y的边；Top-Rank-k频繁模式阈值为k。则有以下定义：

  定义5  权重。 假设存在项集X、Y，以及DBV(X)和DBV(Y)，如果DBV(XY)=DBV(X)∩DBV(Y)，则称该DBV(XY)为X与Y之间的权重。

例如DBV(I₃)={0,{1,1}}，DBV(I₁)=〈1,〈1,1,1,1〉〉，则DBV(I₁ I₃)=〈1,1〉=〈1,2〉,则DBV(I₁ I₃)则为I₁ 与I₃之间的权重，Sup(I₁ I₃)=|DBV(I₁ I₃)|=1。

对于任意两个项集X和Y，如果XY模式Rank不大于k，即：R_XY≤k，则X与Y之间存在边E(X,Y)，该边加入到E中，同时weight(X,Y)=DBV(XY)。重复此过程生成可存储Top-Rank-k频繁模式的带权无向图，具体的生成算法Procedure WUG_GEN如下所示：

  Input： Transactional Database D,k

  Output: WUG

  Procedure WUG_GEN(D,k)

  1)  For each V_j∈L₁

  2)  For each V_i∈L₁(i≠j)

  3)  Count Sup(V_jV_i) and sort in descending

      order by Sup(V_jV_i)

  4)  If R(V_jV_i)≤k

  5)  Add E(V_i,V_i) to Edge set E;

      //增加边E(V_i,V_i)到边集E中

  6)    weight(V_i,V_j)=DBV_Intersection

  7)    End if;

  8)     End for;

  9)    End for;

  End procedure

  定理1  在给定的带权无向图中，对于某个点集合V′中任意两点V_i和V_k，如果都存在一条边E(V_i,V_k)∈E，则V′中所有的点构成一条Top-Rank-k频繁项集环，即为Top-Rank-k频繁项集。

证明 假设∀V_i∈V(1≤i≤m),∃V′=〈V₁,V₂,…,V_i,…,V_j,…,V_k〉,如果对于∀V_i∈V′,∀V_j∈V′，使得E(V_i,V_j)∈E成立，由Procedure WUG_GEN和Top-Rank-k频繁模式挖掘过程中的反单调性^[7]可知，{V₁，V₂，V_i,…,V_j,…，V_k}为Top-Rank-k频繁项集，即存在一条Top-Rank-k频繁项集环，该环路经过的顶点〈V₁,V₂,…,V_k〉即为满足Rank条件的频繁项集。

2 WUG_TK

本文在带权无向项图的基础上，提出了一种Top-Rank-k频繁模式挖掘算法(WUG_TK)。算法中使用带权无向图存储Top-Rank-k频繁模式，图中顶点集合即为1-itemset，顶点之间边的权值即为DBV(V_iV_j)，如果存在Top-Rank-k频繁项集环，则环上面的顶点即为满足Rank条件的频繁项集。环路的每条边的权值，进行与( & )操作，其结果即为频繁项集所在的TID。该TID在具体中医方剂数据处理中，即为频繁药物组合所对应的方剂名称。

在上述生成的带权无向图(WUG)的基础上，搜索Top-Rank-k频繁项集环的操作见Procedure Mining_Top-Rank-k_Frequent Patterns算法，该算法调用Procedure Top-Rank-k_Frequent Patterns loop来完成对Top-Rank-k频繁项集环的搜索。

  Mining_Top-Rank-k_Frequent Patterns算法描述如下：

  Input： WUG

  Output: Top-Rank-k_Frequent Patterns,TID

  Procedure Mining_Top-Rank-k_Frequent Patterns(WUG)

  1) While V≠∅ do

  2)  For each V_i,V_j(i≠j) of V

  3)  If E(V_i,V_j)∈E then    //V_i,V_j之间有边相连

  4)  L=V_i∪V_j,V′=V-{V_i,V_j}

      //L为其中任意两点都有边相连的点集合；

        //V′为含有未搜索到的点的集合

  5)  Search Top-Rank-k_Frequent Patterns loop(L,V′);

    //调用Procedure Top-Rank-k_Frequent Patterns loop

        //来搜索Top-Rank-k频繁项集环

  6)     End If;

  7)    End For;

  8)   End While;

  End procedure;

  Procedure Top-Rank-k_Frequent Patterns loop(L,V′)

  1)  While V′≠null do

  2)    For unvisited V_k of V′

  3)     If E(V_k,∀V_j∈V′)∈E then;

  4)      L=L∪V_k,V′=V′-{V_k};

  5)       Output L and weight_ & ;

      //输出Top-Rank-k_Frequent Patterns和对应的TID

  6)     End if;

  7)    End for;

  8)   End while;

  End procedure

例如在表 1事务数据库中，设k=3，根据WUG_GEN算法：I₁出现TID分别为2、3、4、5，则DBV(I₁)=〈1,〈1,1,1,1〉〉=〈1,30〉，I₂出现TID分别为1、2、3、4、5，则DBV(I₂)=〈0,〈1,1,1,1,1〉〉=〈0,31〉，因为DBV(I₁)是DBV(I₂)的子集，则DBV(I₁)∩DBV(I₂)=DBV(I₁)=〈1,〈1,1,1,1〉〉，则Sup(I₁ I₂)=4，此时R_{(I1 I2)}=1，则顶点I₁顶点I₂之间存在一条边E(I₁,I₂)，weight(I₁,I₂)=〈1,〈1,1,1,1〉〉=〈1,30〉，以此类推可以生成如图 4所示的Top-Rank-3的频繁模式图。

根据Mining_Top-Rank-k_Frequent Patterns算法：对于WUG(V,E,W)中∀E(V_i,V_j)∈E，例如图 1中的点I₁和点I₂，从V′=V-{I₁,I₂}={I₄,I₅}中选取点I₄，则E(I₄,I₁)∈E，E(I₄,I₂)∈E，则点I₁、点I₂和点I₄之间存在一条Top-Rank-3频繁项集环，则I₁ I₂ I₄为满足Rank小于等于3的频繁3-itemset，weight(I₁,I₂) & weight(I₁,I₄) & weight(I₂,I₄)=〈1,〈1,1,0,1〉〉，即I₁ I₂ I₄出现的TID为2、3、5。同理可以由图 4可以生成Rank小于等于2的频繁3-itemsetI₁ I₂ I₅，I₁ I₂ I₅出现的TID为3、4、5。

3 实验与结果分析 3.1 实验设置与结果

实验环境为Intel Core i3-3110M 2.4 GHz CPU,4 GB RAM，操作系统为Windows 7。算法在Visual Studio 2012，.Net Framework Version 4.5.50709 的环境下实现。

中医方剂实验数据是从《中医方剂大辞典》中收录的治疗消渴病肾阴虚型方剂中筛选出来的346首方剂，包含163味中药药材。针对数据的前期准备处理主要是针对药物组成的规范，该规范包括：药材的重名和异名处理、同名异方的处理、药材计量单位的统一。在此规范数据基础上，构建方剂数据库。

通过对《中医方剂大辞典》中收录的方剂进行分析，初步按照编号、方剂名、组成、别名、性、味、归经、功效等8个属性进行描述，完成对原始数据库的构建；然后利用基于带权无向图的Top-Rank-k频繁模式挖掘算法对数据源存储的方剂进行分析研究。

根据本次治疗肾阴虚型方剂数量和用到的中药个数，结合经验判断以及不同参数提取数据的预读，筛选出部分有价值的Top-Rank-16的k-itemset(k≥3) 及所对应的方剂名见表 2。

3.2 算法性能对比及分析

本文提出的WUG_TK算法主要与Huynh-Thi-Le等^[10]的iNTK算法和Dam等^[11]的BTK算法分别从运行时间、消耗空间作了对比实验。对比实验数据集分别采用中医方剂数据集和公开测试数据集。中医方剂数据集实验数据采用《中医方剂大辞典》中收录的治疗消渴病肾阴虚型和胃火炽盛型两种症型方剂。其中，治疗肾阴虚型方剂共346首，包含163味中药药材；治疗消渴病胃火炽盛方剂共382首，包含218味中药药材。公开测试数据集如表 3所示，主要包括Chess、Pumsb和Retail三个真实数据集(http://fimi.ua.ac.be/data/)，以及T10I4D100K和Test2K50KD1人工合成数据集。其中人工合成数据集主要是由LUCS-KDD数据生成器合成的。算法运行时间的对比实验在真实数据集上进行，结果如图 5所示；而算法消耗空间的对比实验在人工模拟数据集上进行，结果如图 6所示。

实验中，三种算法通过设置不同的k值进行实验比较。当平均项数目较小时，生成有效项集的概率就会降低，符合条件的Top-Rank-k的频繁模式就会增多，挖掘代价也会相应增加。因此，实验中对不同的实验数据集选择不同的阈值，从而保证实验结果的有效性。

由于WUG_TK算法通过带权无向图直接产生k-itemset(k≥3) ，避免了候选项集的产生，而iNTK和BTK都采取了“建树-编码”的过程，与之相比，WUG_TK算法不需要对数据集中的项集进行编码，而是在构造完成的带权无向图上直接搜索符合Rank条件的频繁模式环，从而大幅提高了算法的运行效率，因此WUG_TK算法性能明显优于iNTK和BTK算法。

由于WUG_TK算法中对于权重采用DBV的压缩数据结构进行存储，可以有效地提高空间利用率，而iNTK算法和BTK算法在运行过程中都需要采用临时表对中间结果集进行存储，从而也造成了过大开销。因此本文提出的WUG_TK算法在空间效率上也优于iNTK算法和BTK算法。

4 结语

本文根据中医方剂的数据特点，提出了一种基于带权无向图的Top-Rank-k频繁模式挖掘算法WUG_TK。该算法在不产生1-itemset和2-itemset的前提下，可以直接产生k-itemset(k≥3) ，更加符合中医方剂挖掘的需求；同时WUG_TK可以回溯到频繁项集所在的方剂名，这对方剂规律分析具有重要意义；此外，WUG_TK算法中采用DBV数据结构对于无向图中的权重进行压缩存储，可以有效地降低空间复杂度。实验结果表明，WUG_TK算法与iNTK和BTK算法相比具有更高的时间和空间效率。

由于本文中DBV数据结构采取了一种位向量的方式进行动态压缩存储，当处理的数据过于稠密时，数据中往往存在大量的非0位，此时DBV的压缩效果还有待提高。另外，由于中医方剂Top-Rank-k频繁模式挖掘中往往存在冗余，这就会造成挖掘效率的降低，下一步将针对如何在挖掘过程中减少信息冗余进行研究。