基于关联规则的Apriori改进算法

2018-09-10李俊

企业科技与发展 2018年9期

李俊

【摘要】为解决Apriori算法多次遍历数据库及产生大量中间冗余候选项集等问题，文章提出了一种基于对角线下方全为0的矩阵和向量矩阵相结合的改进算法，该算法只对数据库进行一次遍历，通过遍历对角线下方全为0的矩阵可获取频繁1项集与频繁2项集及候选3项集，再将候选3项集与布尔向量矩阵的各行循环做“与”运算后相加，即可得项集支持度。通过实验对比，改进算法能较好地挖掘频繁项集，提高了运行效率和存储空间利用率。

【关键词】数据挖掘；Apriori算法；关联规则；向量矩阵

【中图分类号】TP311.13 【文献标识码】A 【文章编号】1674-0688（2018）09-0042-04

1 概述

Apriori算法是经典的关联规则挖掘算法之一，它分为两个过程：查找频繁项集及生成关联规则，核心是频繁项集的自连接和候选集的剪枝。然而该算法存在几个挑战：？譹？訛事物数据库的多次扫描；？譺？訛产生庞大的中间候选项集；？譻？訛候选项集的支持度计算需不断扫描数据库，支持度计数工作量大，造成了空间和时间的浪费。

本文基于上述的问题提出了一种基于矩阵和向量矩阵相结合的改进算法。算法对只数据库进行一次遍历，通过遍历矩阵可获取频繁1项集与频繁2项集及候选3项集，然后将候选3项集与布尔向量矩阵的各行循环做“与”运算后相加即可得项集支持度。

2 Apriori改进算法

2.1 算法的改进思想

首先通过扫描数据库将事物数据库同时映射为对角线下方全为0的矩阵和只布尔向量矩阵。算法只对数据库进行一次遍历，通过扫描矩阵可获得频繁1-项集、频繁2-项集和候选3-项集。将候选3项集与布尔向量矩阵的各行循环做“与”运算后相加即可得候选项集支持度。执行步骤如下。

step1：先将事务数据库同时转换为对角线下方全为0的矩阵F和只含有0和1的布尔向量矩阵matrix。

step2：由于矩阵F的主对角线的数值表示单个项集在事务数据库里出现的总次数，读取主对角线数值可得频繁1项集。矩阵F的上三角数值代表项集在事物数据库中总的计数，通过与最小支持度比较可获取频繁2-项集。

step3：根据原始的Apriori算法对频繁2-项集进行自连接剪枝后能获取候选3项集。

step4：将候选3项集合的各个项目转为只含数值0和1的二进制编码向量，并将候选3项集的二进制向量与布尔矩阵matrix的各行循环做“与”运算后相加即可得项集支持度，从而生成了频繁3-项集。

当k>=4时，循环步骤5。

step5：将频繁k-1项集自连接产生候选k项集，将候选k项集与布尔向量矩阵matrix的各行循环做“與”运算后相加即可得项集支持度，当不能产生频繁k项集即可退出循环，算法结束，否则继续。

算法的伪代码如下：

Improved_ Apriori算法的描述如下：

输入：事物数据库DB，最小支持度

输出：频繁项集

%取一条记录row，生成对角线下方全为0的矩阵F

for A，B in row %若记录中任意两项A，B若都为1则将对角线上方位置F[A][B]加1

for each A==1&B==1

F[A][B]++

%生成布尔向量矩阵matrix，行rv为“事物标识”，列cv表示“项集标识”

rv=size（DB，1）；%获取数据库DB行数即事物数

cv= size（DB，1）；%获取数据库DB列数即事物中包含的项目总数

matrix=zeros（rv，cv）；%

for i=1：M

for j=1：N

matrix（i，DB（i，j））=1；

%通过扫描矩阵F对角线生成候选-1项集的支持度从而生成频繁1项集

for i=1：rv

if F[i][i]>=min_sup %对比最小支持度即可获得一项频繁集L1

L1=F矩阵对角线大于最小支持度的项目集合

%产生频繁2项集L2

for i=1：rv

for j=1：cv

if F[i][j]>=min_sup

L2=F矩阵中除对角线大于最小支持度的项目集合

%L2自连接获取候选3项集

C3=L2xL2

%产生K项频繁集

for each C 属于Ck

C_supk==0，BC=0 %初始化候选项的支持度C_supk，候选集C的二进制码为BC

从左往右扫描C的列若等于0则BC加0，否则加1

for i in matrixi

if Ci==0 then continue

if BC&matrixi=BC %候选集的二进制码与矩阵的行向量进行“与”运算

C_supk++ %计算支持度

if C_supkCi=0 else

Lk=候选集Ck的C_supk大于等于最小支持度的项目集合

if Lk==null %若频繁项集为空，则运算结束

return 1

2.3 Improved_Apriori算法的实现

下面结合案例来详细说明算法的实现方法。设存在事物数据库BD={T1，T2，T3，T4，T5，T6，T7，T8}，DB中包含有8个事物，对应的项目集I={A，B，C，D}，如表1所示，设最小支持度min_sup为2。

（1）先对数据库DB进行扫描，生成对角线下方全为0的矩阵F和布尔矩阵matrix。矩阵matrix的行代表事物，列代表项。生成的结果如下所示。

F=5 6 2 7 6 2 5 4 2 6

matrix=1 1 0 11 1 1 11 0 0 10 1 1 01 0 1 01 1 0 10 1 1 10 1 0 1

（2）生成频繁1-项集L1。对矩阵F进行逐行扫描，获取对角线位置的元素，生成频繁1-集L1。扫描矩阵F中除对角线位置的数值，生成频繁2-项集L2。查找结果见表2、表3。

（3）由表3可知，频繁2-项集L2为{A，B}，{A，C}，{A，D}，{B，C}，{B，D}，{C，D}，由频繁2-项集生成候选3-项集{A，B，C}{A，B，D}{A，C，D}{B，C，D}。为求频繁3项集- L3，先将候选3项集转为二进制向量，即{A，B，C}→1110，{A，B，D}→1101，{A，C，D}→1011，{B，C，D}→0111，将转换的二进制向量依次与矩阵matrix的每行进行“与”运算后进行求和。

（4）频繁3-项集为{A，B，D}，{B，C，D}，由于此两频繁项集无法自连接，算法结束。综合上述的计算结果可得出在事物数据库DB中，包含频繁项集L1={A，B，D}，L2={B，C，D}。根据Aporiori的性质可知，由L1生成的非空子集也是频繁的，L1的非空子集有{A}{B}{D}{A，B}{A，D}{B，D}。同样可得L2的非空子集有则{B}{C}{D}{B，C}{B，D}{C，D}。可以生成如下的关联规则：

B -> D 置信度：83.333 3%

D -> B 置信度：83.333 3%

A -> D 置信度：80%

D -> A 置信度：66.666 7%

A -> B 置信度：60%

C -> B 置信度：75%

A -> B，D 置信度：60%

A，B -> D 置信度：100%

A，D -> B 置信度：75%

B，D -> A 置信度：60%

B，C -> D 置信度：66.666 7%

C，D -> B 置信度：100%

3 改进算法的实验及性能分析

为对比分析改进的Improved_Apriori算法与原始的Apriori算法的运行效率，将这2种算法在不一样数据记录下的执行时间进行比较。

本测试的数据来源于mushroom.dat数据集（http：//fimi.ua.ac.be/）。测试环境：操作系统为win7 64位，内存容量为8 G，测试工具为Matlab 2016a。实验时利用oracle的plsqldev工具先将mushroom.dat进行预处理。本实验将采用不同的事物记录数、不同的项目数及不同的支持度来对比计算2种算法的运行时间。

（1）设最小支持度为6，该数据集的项目数为23。在事物数量不同的实验条件下，这2种算法的执行时间见表5。

由图1可知，保持最小支持度不变，原始的apriori算法的执行时间明显大于改进的Improved_Apriori算法运行时间。

（2）该组测试取事物数据条数为8 000条，截取数据集的项目数为23。在支持度不同的条件下，这2种算法的执行时间见表6。

经图2可知，随着支持度的不断增加，2种算法的执行时间逐渐减少，然而原始的apriori算法的减少范围更大。由图2可得出：事物数据条数及项目数不变，支持度越小，改进算法比原始算法的处理效率要高很多。

（3）该组测试选取的事物数为8 000条，支持度为3。实验中，通过选取不同的项目个数，计算执行时间。2种算法的执行时间见表7。

經图3可知，事物数据条数及支持度不变，当项目数不断增加时，2种算法的运行时间也同时增加。由图3可知，改进的Improved_ Apriori比原始的apriori算法执行效率更高。

改进的Improved_ Apriori主要有以下几个方面的优点。

（1）由于将事物数据库转为单纯的数字型类型，从而压缩了存储空间，减少I/0负担，大大提高空间利用效率。

（2）在获取所有频繁项集时，只需对事物数据库进行一次扫描，程序执行效率得到提高，在时间利用效率上也有了明显的提高。

（3）Improved_ Apriori算法通过对角线下方全为0的矩阵直接获取了频繁1-项集和频繁2-项集及候选3-项集，避免大量无用中间候选2-项集的产生。

4 结语

本文针对Apriori算法存在的问题，提出了一种基于对角线下方全为0的矩阵和向量矩阵相结合的改进算法，并将改进的算法和原始算法进行性能分析，算法通过将事情数据库压缩为矩阵，有效地减少了数据库扫描次数，同时减少了大量冗余候选2-项集的产生，从而从时间和空间上获取了良好的性能。