一种基于图论与最大路径的关联规则挖掘算法

涂晓斌，郭 力，刘晨宁，周 婷，左黎明

（华东交通大学理学院，江西 南昌 330013）

最初提出关联规则的动机是针对购物篮分析问题，除了应用于顾客模式的挖掘，在其它领域也得到了应用，包括工程、医疗保健、金融证券分析、电信和保险业的错误校验等。Agrawal[1]首先在1993 年提出了关联规则概念， 随后在1994 年提出了经典的Apriori 算法，该算法第一次实现了在大数据集上的关联规则提取，利用逐层搜索的迭代方法找出数据库中项集的关系，形成规则。 汪曦曦[2]根据事务数据集生成一个布尔矩阵，并得到关联规则图， 通过判断节点之间是否存在通路，产生频繁项集，该过程需删除无用的通路。 罗丹等[3]在基于矩阵的改进算法中，删除了不能连接的项集和非频繁项集，使矩阵更加简化，但计算过程避免不了新矩阵的生成。 宋文慧等[4]利用一个上三角矩阵表示事务之间的关系，但在挖掘频繁项集的过程中生成大量的候选项集。 边根庆等[5]扫描一次数据库，生成布尔矩阵，赋予项和事务权重，定义了一个权重支持度，通过大量计算得到频繁项集。 杨秋翔等[6]在布尔矩阵的下方添加一行，用于计算项目支持数，删除统计值等于0的事务在矩阵中所对应的行，挖掘过程需要反复进行排序和计算操作。 廖纪勇等[7]在生成关联规则的布尔矩阵后，将各列按照支持度计数进行排序，但每生成一组频繁k-项集，需要重新排序得到新的矩阵。 田建勇等[8]利用矩阵表示事务间的关系，但在生成频繁项集的过程中仍然产生候选项集。

这些算法基于矩阵挖掘频繁项集[9-10]，在一定程度上有效减少了对数据集扫描的次数，但在挖掘过程中出现了候选项集或新的矩阵，占用大量内存。在超大数据集下，规则生成的效率较低。本文以布尔矩阵为基础，将图论与最大路径问题[11-13]相结合，通过增加步长搜索频繁项集，能有效提高算法效率。

1 Apriori 算法流程

Apriori 算法的主要思想是找出存在于事务数据集中最大的频繁项集，再利用得到的最大频繁项集与预先设定的最小置信度阈值生成强关联规则。Apriori 算法的步骤如下。

1） 扫描全部数据集，产生候选1-项集的集合；

2） 根据最小支持度， 由候选1-项集的集合产生频繁1-项集；

3） 当k＞1，重复执行步骤（4）（5）（6）；

4） 由Lk执行连接和剪枝操作，产生候选k+1-项集的集合Ck+1；

5） 根据最小支持度， 由候选k+1-项集的集合Ck+1，产生频繁k+1-项集的集合Lk+1；

6） 若L 不等于空，则k=k+1，跳往步骤（4）；否则，跳往步骤（7）；

7） 根据最小置信度，由频繁项集产生强关联规则，结束。

2 基于图和最大路径的优化算法

定义1 最长路径问题。 指给定图中找到一条最长长度的简单路径问题。 路径的长度可以通过其边数来测量，而在加权图中通过各边的权重之和来测量。

定义2 k-path 问题。当规定长度或步长时，找出一条长度为k 的简单路径， 或是在固定步长时，找到一条长度最长的简单路径。

这种问题应用在关联规则中，可以将事务作为结点，当两个事务同时出现时就会相连接而产生一条边，二者同时出现的频率作为边的权值，从而构成一张无向带权图。 当规定步数为k 且k＞2 时，所经过的结点数为k+1，此时，挖掘频繁k+2-项集的任务即可转变成寻找一条最大权值的k-path。

2.1 改进的算法

假设数据集D 中包含m 个事务T 和n 个项目t，即D={T1，T2，…，Tm}，其 中I={i1，i2，…，ik}为k-项集，设置一个最小支持度min_support。

Step1 构造关联规则矩阵。将事务集看作列向量，项目集看作行向量，则按以下规则可生成一个m 行n 列的事务集布尔矩阵R。

Step2 矩阵的清理。 对于矩阵R 按列求和，得出各个项目在整个数据库的支持度计数，删去列和小于最小支持度计数的列，剩下的列所对应的项目名即频繁1-项集L1，整理后的矩阵记作R′。

Step3 构造关联规则图。 根据矩阵R′创建一个简单无向图G=（V，E）， 顶点为频繁1-项集中的所有项目，即V=L1＝{i1，i2，…，ip}，p≤n。 对于L1中的项目，两两组合，在矩阵R′中进行按位与运算计数，记的数为W（isit），即有isit＝W（isit），其中s，t=1，2，…，p 且s≠t。 对图G，连接isit＝W（isit）≠0 的顶点，则边isit的权重为W（isit），关联规则图构建完毕。

Step4 构造待挖掘矩阵。将关联规则图转换成邻接矩阵Mp×p， 此处的图为无向带权图， 邻接矩阵Mp×p的主对角线一定为0。 在遍历过程中，为避免元素被重复计算，对矩阵Mp×p进行约简，将其下三角区域元素用0 替换，对于小于最小支持度计数的元素也以0 替换，得到待挖掘的矩阵M′p×p。

Step5 频繁k-项集的生成。对于频繁2-项集，筛选图G 中大于min_support 的边即可。 去除待挖掘矩阵的全0 行，全0 列。 以矩阵的左上角非0 元素为起点，频繁k-项集（k＞2）所对应的步长为k-2，因该矩阵为上三角矩阵， 在列方向上向下移动，行方向上左右移动，找出权值最大的一条路径。 连接该路径中元素所对应的项目，生成频繁k-项集。 当步长等于max|T|时，停止搜索。

3 算法分析与实验结果

3.1 实例分析

为了进一步说明算法，给出一个简单的算例。 已知数据库D 中包含10 个事务，D={T1，T2，T3，…，T10}，项目集合为I={a，b，c，d，e，f}， 最小支持度为0.2，事务数据集如表1。

表1 事务数据集Tab.1 Transactional datasets

1） 扫描数据库D，可构造一个10 行6 列的0-1 事务矩阵R。 根据所给条件计算出最小支持度计数：min sup_count=min_support×|D|=0.2×10=2。 计算矩阵各列的列和， 删去小于最小支持度计数的列，得到一个新的矩阵R′， 也就是频繁1-项集所对应的矩阵。

由此得到频繁1-项集L1={{a}，{b}，{c}，{e}，{f}}。

2） 根据矩阵R′构造一个关联规则图G=（V，E）， 其中V={a，b，c，e，f}； 对矩阵R′各列按位采用“与运算”， 得出边集为E={ab，ac，ae，af，bc，be，bf，ce，cf，ef}，对应的权重如表2。

表2 边与权重Tab.2 Edges and weight

画出关联规则图如图1。

图1 关联规则图Fig.1 Association rule graph

3） 根据关联图生成邻接矩阵M，并将小于最小支持度计数的元素用0 替换。

同时可得到频繁2-项集：L2={{ab}，{ac}，{ae}，{af}，{bc}，{bf}，{ce}，{cf}，{ef}}。

4） 频繁k-项集的生成k＞2。搜寻频繁3-项集，取步长为1。 在去除全0 行、全0 列后，从第1 行开始遍历，选择非0 出发点ab，向矩阵的右下角搜索最大路径，移至点ac，该路径所对应的行、列索引名组合成频繁项集，即{abc}。同理对于下一个点ac，有两种移动情况，都得到频繁项集{abc}。 如图2（A），最终得频繁项集：{abc}，{ace}，{abf}，{aef}； 遍历第2 行，出发点为bc，无法移动，对下一个点进行操作，如图2（B），得到频繁项集：{bcf}；遍历第3 行，如图2（C），得到频繁项集：{cef}。

图2 频繁k-项集的生成过程Fig.2 The process of generating frequent k-itemsets

最终可得频繁3-项集L3={{abc}，{ace}，{abf}，{aef}，{bcf}，{cef}}。 当步长等于max|T|时，停止搜索。

3.2 实验结果分析

为测试改进后的算法性能， 将本文算法与Apriori 算法进行关联规则挖掘实验。 硬件环境为Intel（R）Core（TM）i7-10 750 Hz@2.60 GHz，软件环境为Windows10 操作系统，使用Python 编程实现。本实验选择了某商品零售企业提供的购物篮数据集(https://download.csdn.net/download/qq_42878458/16601884?spm=1001.2014.3001.5503)，该数据包含9 835个购物篮数据，169 个商品类别。

考虑当事务数增加时，将改进的算法与传统的Apriori 算法进行时间的对比，所得实验结果见图3。

图3 改进的算法与Apriori 算法Fig.3 Improved algorithm and Apriori algorithm

由图3 可知，与Apriori 算法相比，随着数据规模的增大，改进的算法挖掘频繁项集的时间在不断减少，有效改进了传统算法挖掘效率低的问题。

4 结论

1） Apriori 算法基于多次扫描事务数据集来执行，在改进的算法中，把事务集看作列向量，项目集看作行向量，只扫描一次数据集，并构造出0-1 关联规则矩阵，减少了时间和空间消耗。

2） 对关联规则矩阵进行约简，删去列和小于最小支持度计数的列；对待挖掘矩阵进行约简，将下三角区域和小于最小支持度计数的元素以0 替换，避免重复计算。

3） 结合最大路径问题，以待挖掘矩阵的左上角非0 元素为起点， 结合图论中的最大路径问题，向右下角搜索权值最大的一条路径，并根据步长确定频繁项集， 在时间复杂度上要优于传统的算法，在海量数据的处理方面有一定优势。