基于哈希表与十字链表存储的Apriori算法优化

吴 昊 刘 钊 顾进广

(武汉科技大学计算机科学与技术学院 湖北 武汉 430065) (武汉科技大学大数据科学与工程研究院 湖北 武汉 430065) (湖北省智能信息处理与实时工业系统重点实验室 湖北 武汉 430065)

0 引 言

虽然Apriori算法原理简单,算法容易实现,但是该算法的时间复杂度和空间复杂度比较高,导致在计算频繁项集的过程中时间效率和空间效率比较低。针对传统Apriori算法在时间复杂度和空间复杂度上的不足,文献[1]提出了使用优化的链表数据结构进行存储，并提高支持计数效率,同时采用了候选生成方法来减少匹配候选项目集。文献[2]提出了一种基于MapReduce的频繁项集挖掘方法，在云计算中引入了MapReduce模型来实现Apriori算法并行化。文献[3]提出了一种基于标记事务压缩改进的Apriori算法，该算法优化了关联规则的参数,减少标签比较的次数。文献[4]提出了编码和适应度函数的方案，建立了关联规则的模式，提高了算法的效率和准确性。廖纪勇等[5]提出了一种基于布尔矩阵约简的Apriori改进算法,将矩阵各列元素按照支持度升序排列,使得算法在压缩过程中减少了扫描矩阵各列的次数,缩短了算法的运行时间。李洁等[6]提出一种基于哈希存储与事务加权的并行Apriori改进算法，通过哈希存储的去重特性，减少冗余计算,开启多个线程，并行计算候选集的支持度，从而提高Apriori算法的运行效率。文武等[7]提出了一种结合遗传算法的Apriori算法来挖掘频繁项集,结合Apriori算法和遗传算法的特点,利用交叉算子产生候选项集和变异算法筛选频繁项集。赵学健等[8]提出了一种利用正交链表存储数据所对应的关系矩阵,同时优化了传统的Apriori算法的自连接和剪枝过程,合理缩小了搜索空间。

1 Apriori算法

1.1 数据关联规则原理

假定数据集为D，Item={I1,I2,…,Im}表示数据库所有数据的集合,I={t1,t2,…,tk}用来表示不同的事务集,每个ti对应一个事务。is、it是I中任意一个项集,并且is中含有事务的数量记为n,表示n项集,根据数据集D中生成的关联规则表示is≥it,同时is⊆I,it⊆I,is∩it为空集,is与it是通过最小支持度(Support)和最小置信度(Conf)来对关联规则进行约束的。频繁项集的支持度表示对应关联规则的频度,频繁项集的置信度表示对应的关联规则的强度[9]。

关联规则is⟹it在D中的频繁项集的支持度是指Item中同时包含is、it的数量与Item的总的数量之比[9],记作:

Support(is⟹it)=|{I:is∪it⊆I,Item∈D}|/|D|

关联规则is⟹it在数据集D中的频繁项集的置信度是指Item中同时包含is项集和it项集的数量与Item中包含is项集的数量之比,记作:

Conf(is⟹it)=|{I:is∪it⊆I,I∈D}|/|{I:is⊆I,I∈D}|

在数据集D中利用算法挖掘有效的关联规则就是为了找出符合用户给定的最小支持度(Min_Support)和最小置信度(Min_Conf)的关联规则,当利用算法挖掘出来的关联规则的置信度和支持度分别大于Min_Support与Min_Conf时,则认为该关联规则是有效的,称为强关联规则[9]。

1.2 Apriori算法过程

Apriori算法计算频繁项集的主要原理：首先利用数据的关联规则计算出候选1项集(简称C1)；然后通过C1自连接的方式计算生成候选2项集(简称C2)；然后由候选2项集继续通过自连接的方式来扩展生成候选3项集(简称C3)；接下来按上述方法一直迭代计算下去,直到判断不能继续扩展生成下一项项集时,表示该迭代计算的过程结束,算法结束。

算法具体实现步骤如下:

(1) 首先对数据库中的数据进行预处理,然后扫描数据库中数据中的事务,统计出每个事务对应的支持度频数,即可生成候选1项集(简称C1),如果候选1项集中的事务支持度频数满足最小支持度频数,经过筛选之后就可以生成频繁1项集(简称L1)。

(2) 将L1中项集进行自连接,由此可以通过L1自连接生成候选2项集合(简称C2)。

(3) 通过C2继续遍历数据库中每条数据的事务，利用计算每一个候选项集的支持度频数,如果候选项集支持度频数满足最小支持度频数,经过筛选后就生成频繁2项集(简称L2)。

(4) 将L2中项集进行自连接,由此可以通过L2自连接生成候选3项集合(简称C3)。

(5) 通过C3继续遍历数据库中每条数据的事务，计算每一个候选项集的支持度频数,如果候选项集支持度频数满足最小支持度频数,经过筛选后就生成频繁3项集(简称L3)。

(6)将上述计算过程一直迭代进行,直到候选k项集为空就停止计算,算法结束,符合最小支持度的项集称为频繁项集[10]。

由上述过程可以看出Apriori算法在时间效率和空间效率方面有以下不足之处[9]:

(1) 首先将数据进行预处理之后,每计算一次项集的频数就需要访问数据库,并对数据库每一条数据进行扫描,因此扫描的次数比较多,这样将会造成I/O上有比较大负载和时间开销,降低了算法的计算性能。

(2) Apriori算法计算过程中会产生大量冗余候选项集。例如频繁n项集经过自连接扩展生成所有的候选n+1项集Cn+1,扫描数据库后就需要进行多次自连接产生冗余的项集,同时生成的候选项集与最小支持度比较次数增多。这样造成了内存空间占用和计算时间的浪费。

(3) 在频繁项集进行扩展生成下一项的时候,测试C(C∈Ck)里每个k-1项集是否是Lk-1中频繁k-1项集,扫描k次Lk-1,对于Lk-1扫描的时间复杂度为O(k×|Lk-1|/2)，所以扫描每一个候选k项集Ck的时间复杂度为O(Ck×k×|Lk-1|/2),在计算过程中需要消耗大量时间[11]。

2 HTACL-Apriori算法

2.1 十字链表表示方法

十字链表节点的结构如图1所示,Item为项目名，Number表示Item部分节点数目，Down表示向下指向其他事务部分,Right表示向右指向其他事务部分[11]。

图1 十字链表结构

2.2 HTACL-Apriori挖掘算法原理

假定D={I1,I2,…,In}表示是所有数据的集合,I={t1,t2,…,tn}表示每条数据中的每一个事务。其中ti(i=1,2,…,n)表示每条数据中第i个事务,同时ti对应D上的一个子集(ti⊆D)。

定义1对于每一个项Pj定义为：

Pj=(X1j,X2j,…,Xmj)

性质1矩阵中存储的每行元素都对应事务数据库中的一个事务,每个事务中在矩阵用1/0表示该项目是否存在,这样可以将所有事务都存储在矩阵中(设定为1),后面就可以利用矩阵计算项集的频数[10]。

定理1如果集合X的频数小于最小支持度频数,则集合X一定不是频繁项集,如果存在X集合，且Y⊆X,可以判断Y集合一定不是频繁项集[12]。

定理2如果存在集合X，且集合X支持度频数大于最小支持度频数,则可以判定集合X为频繁项集,如果存在Y集合，且Y⊆X,可以判断Y集合同样是频繁项集[12]。

推论1假设频繁k项集合个数记为|Lk|,如果|Lk|

3 HTACL-Apriori算法的优化

3.1 算法优化思想

通过3个步骤对传统的Apriori算法进行改进优化:

(1) 将数据库中的事务映射到布尔矩阵进行存储(0表示不存在,1表示存在),这样避免多次访问数据库扫描数据,只需要将数据一次性存储在布尔矩阵中,后面利用布尔矩阵的特性来进行计算项集的频数,极大地减少了计算过程中的I/O时间开销与负载,优化了算法的运行速度[13]。

(2) 由于链表具有动态插入和动态删除的优点,因此对每次生成的项集和对应频数作为一个节点插入到链表中,然后对链表节点进行部分选择排序,经过部分选择排序,将不满足最小支持度频数的项集直接删除(满足最小支持度的项集不用排序),在后面的计算过程中减少了一些无效的自连接匹配运算,优化了算法运行速度和内存空间。

(3) 利用布尔矩阵的特性减少匹配时间。十字链表中节点的Item部分转换为布尔向量和布尔矩阵中每一行进行“与”操作,然后利用定义1来计算项集在数据中出现的频数,其过程所需要的时间小于事务数据之间自连接后再逐一判断每个事务是否匹配所需要时间,通过布尔矩阵的特性来判断,减少了一些无效自连接匹配运算,减少了时间消耗。

(4) 利用十字链表交叉正交存储频繁项集。根据定理1和定理2,利用哈希表对项集进行剪枝和去除重复项集,然后存储在十字链表中，极大地减少了内存占用空间和冗余项集计算频数的时间[13]。

3.2 算法的优化步骤

输入:数据库中数据经过预处理后的数量有N条,假定最小支持度为Min_Support,则最小支持度频数为Min_support_Count=N×Min_Support。

输出:输出符合条件的频繁项集。

算法优化的具体步骤如下:

(1) 将数据库中的数据经过预处理后,根据性质1将每条数据中的事务按照0/1分布(0表示不存在,1表示存在)映射到布尔矩阵中,遍历矩阵,利用定义1计算出候选1项集对应的频数。

(2) 将候选1项集和对应频数作为节点插入到链表中,然后对链表中项集的频数进行部分选择排序,只需要将不满足最小支持度的项集频数对应的链表节点筛选出来(不需要链表所有节点全部排序)进行删除,同时利用哈希表hash_unfrequent存储非频繁项集(后面过程中利用定理1可以剪枝优化,减少计算时间),利用哈希表hash_frequent存储频繁项集(后面过程利用定理2可以剪枝优化,减少计算时间),就生成了频繁1项集链表L1。

(3) 利用步骤(2)得到的频繁1项集的链表进行交叉正交,然后将交叉正交的项集用哈希表hash_unique存储(表示该项集已经出现,在后面项集的生成过程中可以去除重复项集,减少计算时间和冗余数据内存空间),将十字链表中节点Item部分转换为对应布尔向量(0表示不存在,1表示存在),然后与布尔矩阵中每条数据进行“与”运算,如果判断在该条数据中存在该项集,利用定义1可以计算出每个项集的对应的频数,然后链表交叉正交生成项集时,首先用哈希表hash_unfrequent来判断,如果符合定理1的情况的非频繁项集进行剪枝优化(不用计算项集支持度频数,不用将节点插入到十字链表中,继续下一步),然后用哈希表hash_frequent来判断,如果符合定理2情况的频繁项集进行剪枝(直接将项集的频数设置为最小支持度频数,然后将节点直接插入到十字链表中)。接着用哈希表hash_unique判断是否出现重复项集,如果哈希表hash_unique判断已经存在,继续下一步,不用将节点插入到十字链表中,反之,将节点插入到十字链表中。这样就生成候选2项集的十字链表,遍历十字链表中的每一个节点,将节点插入到新的链表当中。此时就生成候选2项集链表C2,将链表进行部分选择排序,动态删除小于最小支持度的链表节点,同时将非频繁项集插入到哈希表hash_unfrequent中,将频繁项集插入到哈希表hash_frequent中,最后生成频繁2项集链表L2。

(4) 利用推论1来判断|Lk|

(5) 循环重复步骤(4)。如果满足|Lk|

HTICL-Apriori算法优化思想伪代码描述如下:

HTICL-Apriori()

{

//将数据库中的每条数据映射存入布尔矩阵Boolean_Matrix

//(M×N，其中：N为数据中事务最多的数量；M为数据条数)。

//用0/1区别,1表示存在,0表示不存在

//数组origin存储扫描数组后的候选项集C1,哈希表hash_

//frequent用来存储生成的频繁项集,hash_unfrequent用来存储

//生成的非频繁项集,hash_unique存储链表交叉正交生成的项

//集,用于去除重复项集

FOR(i=1;i<=N;i++) DO

FOR(j=1;j<=M;j++) DO

IFBoolean_Matrix[i][j]>0

origin[i].count++;

END FOR

END FOR

//将origin中的项集和对应的频数插入P1链表中

P1.insert(origin[i](i=1,2,…,n))

HTACL-Apriori_Sort(P1)；

//对链表P1中每一个项集对应的频数进行部分选择排序

//遍历Pk+1

IF(P1.number>=Min_support_Count)

hash_ frequent.insert(P1.frequent);

//存储满足最小支持度的项集

Else

hash_unfrequent.insert(P1.unfrequent);

//存储不满足最小支持度的项集

delete(P1.unfrequent);

//将链表P1中非频繁项集的部分删除

WHILE(Pk.length()>=k+1&&Pk!=∅)

{

根据定理1可知,由频繁1项集事务进行转置和频繁1项集进行内积变换,生成二维布尔矩阵

FOR(i=1;z<|Pk|.length();i++) DO

FOR(j=i+1;y<|Pk|.length();j++) DO

Ck=Pk.Item[i]∪Pk.Item[j]

//交叉正交

//根据定理1和定量2判断

IFCk∈hash_unfrequent

Pk同时向右和向下移动

Continue

IFCk∈hash_frequent

Pk.Ck.number=Min_Support_Count;

Pk同时向右和向下移动

Continue

IFCk∈hash_unique

//项集已经出现

Pk同时向右和向下移动

Continue

hash_unique.insert(Ck);

//hash_unique插入Ck,方便在十字链表中去除存储重复项集

将Ck中的项集先转换成布尔向量,用0/1区别,1表示存在,0表示不存在

WHILE矩阵Matrix

Ck与布尔矩阵Matrix每一行对应的列进行“与”运算,如果判断在该条数据中存在该项集,利用定义1计算项集频数。

Pk.Ck.number++;

//对该项集计数

Cross_Listk.insert(Pk)

//将该节点Pk插入十字链表中

END FOR

END FOR

将Cross_Listk的向下和向右的尾端设置为NULL

将十字链表Cross_Listk中生成的候选项集全部插入到链表Pk+1中。

HTACL-Apriori_Sort(Pk+1)//对链表Pk+1中每一个项集对应的

//频数进行部分选择排序遍历Pk+1

IF(Pk+1.number>=Min_support_Count)

hash_ frequent.insert(Pk+1.frequent);

//存储频繁项集。

Else

hash_unfrequent.insert(Pk+1.unfrequent);

//存储非频繁项集

Delete(Pk+1.unfrequent);

//将链表Pk+1中非频繁项集的部分删除

END WHILE

}

HTACL-Apriori_Sort(Pk)、

{

//链表节点中的number,用部分选择排序(把项集按照最小支

//持度分成两个部分)

调用选择排序算法Sort(Pk)

}}

3.3 算法的优化示例说明

假定关联规则的最小支持度为0.4,数据量有10条,首先将数据进行预处理,将每条数据中的事务按照字母序列递增排序(如表1所示),然后可以计算出最小支持度频数Min_Support_Count=10×0.4=4,同时按照以下步骤来计算频繁项集。

表1 数据表

(1) 将经过预处理的数据根据性质1按照0/1分布映射到布尔矩阵中对应的位置来表示对应事务是否存在,矩阵中的行表示每条数据，每一列表示每一个事务，转换成对应矩阵Boolean_Matrix(本示例中以事务a,b,c,d,e,f,g,h为行)。

(2) 遍历布尔矩阵中的每一个事务,根据定义1可以计算出该数据集中每个事务对应的频数,数据如表2所示。

表2 数据中事务表

(3) 按照每个事务对应的数量进行部分选择排序,将小于最小支持度的项集排在最后,然后将满足最小支持度的项集插入到链表中,由此可以得到新链表,同时将链表中频繁项集全部插入到哈希表hash_frequent中,将链表中非频繁项集全部插入到哈希表hash_unfrequent中。

(4) 由此可以计算出频繁1项集链表(如图1所示),即L1={{a},{b},{d},{e},{g},{h}}。同时计算出频繁1项集的个数|L1|=6≥K+1。根据推论1可以得出可以由L1继续向候选2项集进行扩展,将链表L1交叉正交生成候选2项集,首先根据定理1判断该项集是否在哈希表hash_unfrequent中存在,如果存在则进行剪枝(不必计算项集的频数,不必插入十字链表,继续下一步计算),继续根据定理2判断是否在哈希表hash_frequent中存在,如果存在(直接设置为最小支持度,插入十字链表),继续判断该项集是否存在于哈希表hash_unique,如果存在则去重(不必计算项集的频数,不必插入十字链表,继续下一步),将生成候选2项集插入哈希表hash_unique(去除重复项集),最后将生成的项集转换为布尔向量(0表示该事务不存在,1表示该事务存在),通过定义1进行计算对应的频数,如果频数不满足最小支持度,就将项集插入哈希表hash_unfrequent中,反之插入哈希表hash_frequent中。经过上述步骤,就可以生成交叉正交后十字链表,如图2所示。

图2 频繁1项集链表

(5) 遍历十字链表中每一个节点,并且插入在新链表中,将新链表节点中的频数按照最小支持度频数进行部分选择排序,将链表部分非频繁项集进行删除,这样就生成新链表(如图3所示),将频繁项集全部插入到哈希表hash_frequent,非频繁项集插入到哈希表hash_unfrequent，由此计算出频繁2项集L2={{bd},{be},{de},{dg},{dh},{eg}},同时可以计算出频繁2项集的数量为|L2|=6≥k+1,由推论1可以继续向k+1项集进行扩展,重复步骤(3)中链表交叉正交的步骤,可以生成十字链表(如图4所示)。

图3 频繁1项集十字链表

图4 频繁2项集链表

(6) 遍历十字链表中的节点,将每一个节点插入到新的链表中,然后将新链表进行部分选择排序,将链表中非频繁项集进行删除,这样就生成新链表(如图5所示[13]),重复步骤(4)，由此计算出L3={{bde},{deg},{deh}}(如图6所示),然后通过推论1判断是否能够继续进行扩展。

图5 频繁2项集交叉正交十字链表

图6 频繁3项集链表

(7) 重复循环步骤(4)和步骤(5)中计算(k+1)项的步骤,如果不满足推论1条件,表示无法计算出下一项频繁项集,算法结束,输出频繁项集。

3.4 算法的性能分析

评价算法性能的优劣主要从算法的时间复杂度和空间复杂度来进行衡量。

3.4.1两种算法时间复杂度分析

假定有M条数据,每条数据中有事务数为L。计算频繁项集分为3个过程。

步骤1每一次计算项集频数扫描数据库数据时间复杂度约为：T1=O(M×L)。

步骤2扫描数据库中的数据后，进行项集自连接平均的时间复杂度约为：T2=O(|Lk-1|×|Lk-1|)。

步骤3在计算频繁项集的过程中,经过动态剪枝判断符合最小支持度的平均的时间复杂度为：T3=O(M×|Ck|)。

本文利用了布尔矩阵“与”运算来求项集频数,结合哈希表剪枝和十字链表去重来计算频繁项集,因此主要在布尔矩阵生成以及链表交叉正交及剪枝去重过程中消耗时间。假设布尔矩阵数据为M条,每一条数据的事务长度为N,频繁项集的长度为|Lk|。

步骤1每计算一次项集需要扫描矩阵中的数据的时间复杂度为：H1=O(M×N)。

步骤2链表交叉正交和剪枝与去除重后存储在十字链表中的项集的时间复杂度约为O(((|Lk-1|×|Lk-1|)/2-|Lk-1|)×M),剪枝和去重的时间为|Tk|,该过程时间复杂度为:H2=O((((|Lk-1|×|Lk-1|)/2-|Lk-1|)-|Tk|)×M)。

步骤3遍历十字链表生成新链表的时间复杂度为：H3=O(|Ck|)。

结论：通过前面的分析，本文利用布尔矩阵“与”运算来计算频繁可以优化算法的运行速度，说明时间复杂度H1

3.4.2算法的空间复杂度分析

假定数据量为M,事务项的长度为L。Apriori算法的空间复杂度为:S1=O(|Lk-1|×|Lk-1|+|Ck|)。

3.5 实验结果分析

对文献[14]的优化方法进行算法复现(简称VM_Apriori算法)，本文在相同环境下做了大量的实验来比较三种算法的时间效率和空间占用效率,实验的操作系统为Windows 10,数据库为MySQL,编程语言为Python3.7,开源软件RGui自带的Groceries数据集作为实验数据集,该数据集中有9 835条数据，169项不同的事务。

(1) 分组设置不同的最小支持度，来比较两种算法在计算时间上的性能[15],三种算法使用相同的数据，均为9 835条，如图7所示。

图7 不同支持度的计算时间

在实验数据的测试的对比之下，经过改进后的HTACL_Apriori算法在同样的环境与数据下,耗时明显减少,达到了预期效果。

(2) 分组设置不同的数据量，来比较三种算法的时间效率[16]，三种算法的最小支持度均为0.01，如图8所示。

图8 不同数据量的计算时间

当数据量比较小的时候，算法的耗时也比较少，随着数据量增加，三种算法所消耗的时间也不断地增加。在实验数据的对比之下，经过改进后的HTACL_Apriori算法在同样的环境与数据下,耗时明显减少,达到了实验的预期效果。

(3) 分组设置不同的数据量，来比较三种算法的空间效率[17]，三种算法的最小支持度均为0.01，实验对比如图9所示。

图9 不同数据量内存空间占用

可以看出，当数据量比较小的时候，算法的空间占用也比较小，随着数据量增加，三种算法的空间内存开销也不断地增加。在实验数据的对比之下，经过改进后的算法在同样的环境与数据下,空间内存开销明显减少,达到了预期效果[18]。

通过上述理论分析和多组数据实验对比了三种算法的性能[19]，在环境相同的情况下，算法优化后的时间复杂度和空间复杂度得到了明显的改善,达到了预期效果。

4 结 语

本文提出利用布尔矩阵表示事务,并且结合哈希表和十字链表存储对项集进行剪枝和去除重复值降低时间复杂度和空间复杂度。并且通过对实验数据对比分析,验证了HTACL_Apriori算法的时间复杂度和空间复杂度得到了明显的优化。但是当数据量达到较大的规模,所处理的数据会受限于内存计算容量。在后续的研究中将考虑基于结合Spark框架,实现大规模数据处理,期望在数据处理方面得到更好的效果。