基于堆排序的重要关联规则挖掘算法研究

张永梅,许 静,郭 莎

(北方工业大学 计算机学院，北京 100144)

基于堆排序的重要关联规则挖掘算法研究

张永梅,许 静,郭 莎

(北方工业大学 计算机学院，北京 100144)

现有的关联规则数据挖掘算法或方法中，获取规则的计算时间很大一部分都耗费在关联项目集的扫描、数据库频繁扫描和生成冗余候选频繁项目集中。传统方法虽然得到的挖掘结果比较全面，但并不是所有挖掘结果中的规则都是重要的，以往的方法没有反映出重要的关联规则而使得挖掘结果的有效性不高，不利于得到需要的重要目标结果。针对重要目标的挖掘，提出一种基于堆排序及链表结构的改进Apriori算法。算法通过扫描数据库，统计得到各个项目集在所有事务集中出现的频率，并按照项目集的频率次数进行堆排序。然后根据建立的堆得到所有k阶候选项目集并计算其相对应的支持度，将不同项目集的支持度与预先设定的最小支持度进行比较，若满足最小支持度，就将对应的频繁项目集加入链表中，否则依据剪枝策略剪去这个对应项，将通过连接运算生成的候选k+1阶项目集采用同样的操作可以生成k+1阶频繁项目集。这样可以很大程度上优化算法的频繁项目集的生成过程并加速了重要关联规则的生成过程，从整体上提高了运算速度。

主要目标；Apriori算法；关联规则；频繁项目集；排序

0 引 言

随着现代技术的飞速发展，知识正在以一种前所未有的方式飞速向前发展，如果还是按照以往的技术去分析所得到的知识，将很难得到所需要有价值的信息，即使能得到，也将会付出很大的代价，而这是所不希望的。

现有的数据挖掘算法及其改进算法，很多都是针对数据的存储以及数据的结构进行相应优化，虽然能够在一定程度上提高算法的挖掘效率，但是在一些方面还是不能够满足应用上的需求[1]，因此改进算法还是有一定的需求。

堆排序是利用树的一种结构，可以很快得到需要的数据，并且还可以动态调整堆的结构，保持堆排序的正常和维护堆的平衡，是一种具有很高效率的结构。链表是一种具有动态分配并且可以动态增长的数据结构，可以根据需要来调整链表。文中根据堆排序的结果来选取前n项(这个根据需要调整，比如前20%、前10%等)，目的是为了得到重要的关联规则，并且可以优化频繁项目集的生成和扫描等操作。

关联规则挖掘是从大量的事物集中发现事物之间潜在的关联关系，以发现隐藏在其中的客户行为模式等[2]。通常频繁率越高的规则在实际中具有越重要的价值。基于此，文中要挖掘事物之间联系最密切的关联规则，即重要关联规则，以便于发现事物集中最紧密的关联关系，而不是得到所有与之相联系的关系，需要的是精确而又有所针对性的关联关系，这才是日益需要挖掘的结果[3]。

文中提出一种基于堆排序算法以及链表相结合的方法[4]，以优化频繁项目集的产生以及生成过程，从而可以快速得到数据挖掘结果。首先算法通过扫描数据库，统计得到各个项目集在所有事务集中出现的频率，并按照项目集的频率次数进行堆排序，然后可以从建立的堆中选取前n项并计算它们的支持度，比较项目集的支持度是否满足最小支持度。若满足最小支持度，就将对应的频繁项目集加入链表中，否则依据剪枝策略剪去这个对应项，这样就可以得到相对应的k阶频繁项目集[5-7]。确定的k阶频繁项目集是从已经生成的频繁项目集中选取前n项得到的。而k+1阶项目集的生成是根据已经确定的k阶频繁项目集进行连接操作而得到的。至于k+1阶频繁项目集则是进行前面相同的操作得到的，而没有新的项目集生成是终止操作的条件。进行排序操作是为了便于得到前n项，而选取n项是为了缩减频繁项目集的扫描及生成运算。

1 Apriori算法及其改进

1.1 关联规则相关概念

关联规则可以简单表示为在已有的数据集D中，若由X出现可以得出Y的出现，并且X∩Y=0，则称X为规则的前提，Y为结果。一般情况下将每一个可能出现的情况称为一项项目集[8-10]。

(1)支持度：在数据集D中，项目集X的支持度为项目集X出现的总次数除以项目集D上的总次数，即sup(X)=X/D。一般用Minsup表示最小支持度。

(2)频繁项目集：若项目集X的支持度满足预先设定的最小支持度，则称项目集X为频繁项目集。

1.2 Apriori算法步骤

Apriori算法为了得到所有的频繁项目集需要对数据集进行多次扫描。算法开始时，为了得到1阶项目集，需要对数据集进行第一次扫描，计算支持度并比较计算的支持度是否满足最小支持度的要求，若满足就得到了1阶频繁项目集，然后2阶项目集是由1阶频繁项目集进行扩展得到的。生成2频繁项目集的条件是对已经得到的2阶项目集需要计算其支持度，而支持度满足最小支持度的要求。这样k+1阶项目集每次都是由k阶频繁项目集得到的，而通过得到的k+1阶项目集又可以确定k+1频繁项目集，直到满足结束条件时结束，从而得到所有的频繁项目集[11-12]。算法流程图如图1所示。

图1 Apriori算法流程图

Apriori算法可以通过挖掘数据集得到数据集中的联系。但是Apriori算法需要重复扫描数据库，消耗了很多运算时间在数据的扫描上，且在生成每个候选规则时都需要判断低阶项目集是否是频繁项目集导致大量重复操作，并且由k阶频繁项目集生成k+1阶项目集的过程中需要重复比较项目集是否满足要求，然而满足要求的项目集需要再次扫描数据集。这是Apriori算法的不足之处。

2 算法的改进及分析

2.1 算法的改进

由于在实际应用的数据库中是不断增长的，并且具有不确定性，而且每次扫描数据集都十分浪费资源，不能够满足生产和生活的需求，所以文中针对传统算法的缺点以及应用进行了改进：

(1)标记每一个项目集的数目；

(2)采用基于动态堆排序的方法获取满足要求的前n项；

(3)将以后新收集到的数据集加入到已有的结果中，而不用再重新计算。

具体策略为在扫描数据集的过程中，需要标记每一个项目集出现的总数目，并计算该项目集的支持度[13]。若支持度大于预先设定的最小支持度，则对该项目集进行标记并加入队列，然后进行堆排序(文中采用大堆方式，这样便于选取前n项以及合并后来的选项)。采用这种方式可以很快地找到满足要求的频繁项目集[14]，而且对以后收集到新的数据集，如果要加入现有的结果中，也是十分方便的。

2.2 算法改进的步骤

(1)确定n值和最小支持度。这样可以进行后续的相关操作，否则无法选取数据，进行后续计算。

(2)开始第一次扫描数据集D，标记每一个项目集出现的次数,并进行堆排序。首先从1阶项目集的堆排序序列开始，计算1阶项目集的支持度并将其支持度与最小支持度进行比较。若大于最小支持度，则加入堆排序队列，并标记出现的次数，否则将其忽略，进行下一个项目集的扫描和计算，直到完成所有的1阶项目集的扫描和计算[15]。根据确定的n值从已经得到的1阶频繁项目集中选取前n项。若得到的1阶频繁项目集数目小于n，则全部加入，否则选取前n项1阶频繁项目集，然后根据1阶频繁项目集生成2阶项目集。为了得到2阶频繁项目集需要进行同样的操作运算[16-17]。

(3)根据上一步确定的k阶频繁项目集产生新的k+1阶项目集，计算支持度，然后与最小支持度进行比较，若满足要求，则进行堆排序。而算法结束的条件是没有新的频繁项目集生成。

(4)若在现有的运行条件下又有新的数据集E加入，则只需扫描新加入的数据集E，得到各个新加入的项目集的计数，并将新加入的项目集的计数与原来项目集的计数进行合并，然后比较前n项是否改变。若前n项有所改变，则重新计算该阶频繁项目集，若没有添加或新增新的项目集到前n项，则该阶频繁项目集是不需要改变的。

(5)综合上述步骤，可以很快得到频繁项目集，并且有新的数据集加入时，也可以很快得到结果。

图2为改进后的算法流程图。

在算法的执行过程中，主要操作是扫描、排序及比较操作。具体内容如下：

(1)扫描。通过对数据库的预处理，扫描数据集，标记每一项目集的计数，并对同一长度的项目集进行堆排序，这样便于查找前n项的项目集，为后续操作提供基础。

(2)排序。主要是针对同最小支持度比较以后，通过堆排序算法将频繁项目集进行排序，因为堆排序可以很方便地找到前n项，并且可以很快地调整前n项的顺序，便于动态增长和删除频繁项目集。

(3)比较。主要包含两部分：第一部分是项目集的支持度与最小支持度的比较，如果某一项目集的支持度大于最小支持度，则将该项目集加入频繁项目集的堆排序的序列中，否则，删减掉该项目集。第二部分是比较新加入的数据集的项目集是否影响已经选取的前n项的频繁项目集。对新加入的数据集进行统计分析，从1阶项目集开始，合并已有的和新加入的1阶项目集的数目，看是否影响了前n项的项目集，若更改了前n项，则需对1阶频繁项目集进行调整。对调整后的2阶项目集需要进行同样的操作运算。

经过上面的几步操作，避免了重复扫描数据集，不仅优化了剪枝方案，而且可以得到重要的关联规则。

图2 改进算法的流程图

3 实验结果及分析

为了检验改进算法效率的提升程度，需要在同样的实验条件下，将改进前与改进后的算法进行比较。文中在实验中采用的是人工模拟随机产生的数据集。

根据实验条件选取了一定量的事务集，对改进前后的算法的挖掘结果进行比较，如图3所示。

从图中可以很明显地看出，改进算法的挖掘结果比Apriori算法的结果在频繁项目集上有所缩减，开始缩减的程度比较高，但是随着支持度的不断提高这种差异越来越小。从改进算法所得到的挖掘结果中可以看到，文中所提算法的实验结果中明显减少了一些不太重要的关联规则，降低了结果的冗余性，提高了挖掘结果的有效性。

图3 运行结果对比图

为了验证改进后算法效率的提升程度，将改进前和改进后的算法在挖掘结果的运行时间上进行比较，如图4所示。

图4 运行时间对比图

从结果图中可以看到，改进后的算法在同样的最小支持度条件下，开始时时间提高的不是很明显，但随着支持度的加大，时间也随之增长。这就是改进后的方法不用每次扫描数据集的优势。

4 结束语

对重要关联规则的挖掘算法进行了研究，采用一种基于堆排序及链表结构的改进Apriori算法。虽然Apriori算法是一种经典的关联规则挖掘算法且在数据挖掘、数据分析及电商平台等方面应用广泛，但是存在数据挖掘效率低且难以适用于较大数据量的致命缺陷。通过研究Apriori算法和重要目标关联规则的特征，结合堆排序的特点并将其应用于规则发现的过程中，优化了数据集的选择以及生成候选集的运算，同时同剪枝策略的结合也优化了剪枝的过程。另外在一定程度上可以利用已有的挖掘结果，方便将现有的结果

和未来的数据集相结合，能更好地发现重要规则并利用其价值推断相应的规律等。改进算法在挖掘速度上有了一定的提高，并且数据挖掘的结果有一定的缩减。

[1] 黄红星.挖掘完全频繁项集的蚁群算法[J].微电子学与计算机,2014,31(12):144-147.

[2] 马玉玲.基于clustering算法的事务抽样关联规则挖掘算法[J].计算机应用,2015,35(S2):77-79.

[3] 孟海东,李丹丹,吴鹏飞.基于数据场的量化关联规则挖掘研究与实现[J].计算机应用与软件,2014,31(7):40-42.

[4] 杨绣丞,李 彤,赵 娜,等.计算排序算法设计与分析[J].计算机应用研究,2014,31(3):658-662.

[5] 郑 麟.一种直接生成频繁项集的分治Apriori算法[J].计算机应用与软件,2014,31(4):297-301.

[6] 陈方健,张明新,杨 昆.一种具有跳跃式前进的Apriori算法[J].计算机应用与软件,2015,32(3):34-36.

[7] 崔 亮,郭 静,吴玲达.一种基于动态散列和事务压缩的关联规则挖掘算法[J].计算机科学,2015,42(9):41-44.

[8] 罗 丹,李陶深.一种基于压缩矩阵的Apriori算法改进研究[J].计算机科学,2013,40(12):75-80.

[9] 吴 斌,肖 刚,陆佳炜.基于关联规则挖掘领域的Apriori算法的优化研究[J].计算机工程与科学,2009,31(6):116-118.

[10] 张 敏,姚良威,侯 宇.基于向量和矩阵的频繁项集挖掘算法研究[J].计算机工程与设计,2013,34(3):939-943.

[11] 毕 岩,章 韵,徐小龙.基于关系矩阵和频集树的关联规则算法及动态更新算法[J].南京邮电大学学报:自然科学版,2015,35(4):96-103.

[12] 胡维华,冯 伟.基于分解事务矩阵的关联规则挖掘算法[J].计算机应用,2014,34(S2):113-116.

[13]HuangYF,LaiCJ.Integratingfrequentpatternclusteringandbranch-and-boundapproachesfordatapartitioning[J].InformationSciences,2016,328:288-301.

[14]FerrerU.ThemultipleaprioriofsocialactsinAdolfReinach[J].LosmúltipleaprioridelosactossocialesenAdolfReinach,2015,49:209-230.

[15]QinShanshan,LiuFeng,WangChen.Spatial-temporalanalysisandprojectionofextremeparticulatematter(PM10andPM2.5)levelsusingassociationrules:acasestudyoftheJing-Jin-Jiregion,China[J].AtmosphericEnvironment,2015,120:339-350.

[16]KhaliliA,SamiA.SysDetect:asystematicapproachtocriticalstatedeterminationforindustrialintrusiondetectionsystemsusingApriorialgorithm[J].JournalofProcessControl,2015,32:154-160.

[17]LinJC,GanWensheng,HongTP.Efficientalgorithmsforminingup-to-datehigh-utilitypatterns[J].AdvancedEngineeringInformatics,2015,29(3):648-661.

Research on Association Rules Mining Algorithm for Main Target

ZHANG Yong-mei,XU Jing,GUO Sha

(School of Computer Science，North China University of Technology，Beijing 100144，China)

The existing association rule mining algorithms or methods waste most of their time on the correlation set database scanning,the frequent scanning and the generating of redundant frequent itemsets candidates during their rule acquisition computation.The traditional methods can get more comprehensive mining results,but not all of the rules that came from the mining result are important.Traditional methods don’t reflect the importance of association rules so as to have inefficiency for mining results,and they are not conducive to the gaining of main target results.Aimed at the mining of important goal,an improved Apriori algorithm based on linked list structure and heap sort is proposed.The algorithm scans the whole database to get the frequency of the appearance of each item set among the whole datasets and do the heap sort.Then,according to the established heap,all thekrankcandidatesetsareobtainedandtherelativesupportiscalculated.Thesupportdegreeofdifferentprojectsetsiscomparedwiththeminimumsupportdegree.Iftheminimumsupportismet,thecorrespondingfrequentitemsetshouldbeaddedtothelist,oritshouldbecutaccordingtotheshearorpruningstrategy.Byconnectingoperation,thecandidatek+1orderitemsetcanbeobtainedfromthegeneratedkorderfrequentitemsets,sotogeneratethek+1orderfrequentitemsets.Inthisway,thegenerationoffrequentitemsetscanbegreatlyimproved,andtheminingresultsofimportantassociationrulescanbeprovided,whichcanimprovethespeedofoperation.

main target;Apriori algorithm;association rules;frequent itemsets;sorting

2016-02-01

2016-06-02

时间：2016-11-22

国家自然科学基金资助项目(61371143)；北京市自然科学基金项目(4132026)

张永梅(1967-)，女，教授，硕士研究生导师，CCF会员，研究方向为图像处理、人工智能、数据挖掘；许 静(1990-)，男，硕士研究生，研究方向为图像处理、数据挖掘。

http://www.cnki.net/kcms/detail/61.1450.TP.20161122.1227.002.html

TP

A

1673-629X(2016)12-0045-04

10.3969/j.issn.1673-629X.2016.12.010