关联规则数据挖掘算法分析

1、1题 目: 关联规则数据挖掘算法分析 姓 名: 学 院: 专 业: 班 级: 学 号: 指导教师: 职称: 年 月 日 2目 录1 绪论.511 研究背景与意义.5111 数据挖掘的商业背景.5112 数据挖掘的社会背景.512 数据挖掘的研究意义.513 国内外发展及研究现状.514 开发环境.5141 采用 Java 语言的原因 .62 数据集介绍.63 关联规则算法.631 Apriori 算法.63.1.1 Apriori 算法介绍.63.1.2 Apriori 算法实现.63.2 频繁模式增长算法.73.2.1 FP-growth 算法介绍 .73.2.2 FP-growth 算法实

2、现 .73.3 Eclat 算法.83.3.1 Eclat 算法介绍.83.3.2 Eclat 算法实现.84 实验结果与分析.94.1 相同算法对相同数据集进行不同阈值数据挖掘.94.1.1 Apriori 算法对各个数据集进行不同阈值数据挖掘.94.1.2 Fp_growth 算法对各个数据集进行不同阈值数据挖掘.104.1.3 Eclat 算法对各个数据集进行不同阈值数据挖掘.104.2 相同算法对不同数据集进行相同阈值数据挖掘.114.2.1 Apriori 算法对不同数据集进行各个阈值数据挖掘.114.2.2 Fp_growth 算法对不同数据集进行各个阈值数据挖掘.124.2.3

3、Eclat 算法对不同数据集进行各个阈值数据挖掘.134.3 不同算法对相同数据集进行相同阈值数据挖掘.134.3.1 不同算法对 mushroom 数据集进行各个阈值数据挖掘 .1334.3.2 不同算法对 T10I4D100K 数据集进行各个阈值数据挖掘.144.3.3 不同算法对 accidents 数据集进行各个阈值数据挖掘.154.3.4 不同算法对 connect 数据集进行各个阈值数据挖掘.165 不同算法的优势与不足.166 不足与展望.177 致谢.17参考文献：.174关联规则数据挖掘算法分析 摘要：数据挖掘技术在当今需要存储、处理、计算大量数据与信息的社会中有非常重要的作

4、用。数据挖掘出现之前，海量的数据只是被简单的存储，不能对隐含在其中的信息进行分析、利用与创造价值，数据挖掘由此出现。数据挖掘是新兴且前沿的技术，是信息领域和数据库领域热点之一。数据挖掘技术的快速发展，出现了适合各领域需求各异的多种不同的分析方法与算法。算法是分析方法的具体实现，首先详细介绍了基于关联规则分析的 Apriori 算法、FP-growth 算法和 Eclat 算法，并通过对比这些算法在不同数据集的运行结果，分析了算法各自的优缺点及其适用领域，同时探讨了各个算法的优势互补、有机结合以弥补单独算法不足的可能性。关键词：数据挖掘；关联规则；Apriori 算法；FP-growth 算法；

5、Eclat 算法Analysis of Association Rules Data Mining Algorithm Abstract： Data mining technology is based on storage, process, and calculation of a large quantity of data and information, which plays an important role in promoting an information society. Prior to the birth of data mining, massive data w

6、as simply stored so that it cant be implied in the information analysis, or be used to create value. Then data mining appeared and things become different. Data mining is not only a brand new technology in recent years, but also one of the most advanced research directions in the field of database a

7、nd information decision. Data mining, which is developing at a rapid rate, leads to a wide range of types of data mining algorithms and methods for various requirements and different fields. Generally, algorithm is a realization of analysis method, this paper analyzes the rules and relationship base

8、d on Apriori algorithm, FP growth algorithm and Eclat algorithm. Then, this paper compares the differences of running results, points out the advantages and disadvantages of each of the algorithms in its field of application. Besides, these algorithms have their own limitations, which means a proper

9、 combination is needed in application field. In this way, these algorithms can work in more effective and efficient ways.Key words: Data mining；Association rule；Apriori algorithms；Fp-growth algorithms；Eclat algorithms引言 在第 11 届国际人工智能协会的会议中，第一次出现了数据库的知识发现的概念，并且在这次会议后，关于知识发现的学术会议与专题研讨会也在很国际知名的会议上5提出1。

10、继 1995 年第一届 KDD 国际学术会议在蒙特利尔举行之后，该会议会每年举行。KDD 是一个迭代的数据处理过程2。整个过程需要由用户提供主要决策，并依据决策经历多个步骤来得到结果。具体的工作步骤有：1） 数据准备；2） 数据选取；3） 数据预处理；4） 数据变换；5） 确定 KDD 目标；6） 选择算法；7） 数据挖掘；8） 模式解释；9） 知识评价。数据挖掘是一个对知识发现最重要的一个部分3。利用数据挖掘技术的工具已经普及到了很多领域，如 Health-KEFIT 是用于健康状况预警的知识发现系统4。这些系统或工具具有如下共同特征：1） 海量数据集。2） 数据利用非常不足。3） 在开发只

11、是发现系统时，领域专家对该领域的熟悉程度至关重要。4） 最终用户专业知识缺乏。1 绪论11 研究背景与意义 111 数据挖掘的商业背景通过商业销售记录收集用于数据挖掘的数据是最重要的一个方面。而数据挖掘的价值主要表现在降低开销与提高收入两个方面。对商业运营的过程，知识发现用作以下四种工具：1） 数据挖掘为研究工具。2） 利用数据挖掘提高过程的效率。3） 数据挖掘成为市场营销工具。4） 数据挖掘为管理客户关系提供方法。112 数据挖掘的社会背景数据挖掘在个人预言方面：数据挖掘是通过客户历史记录数据的分析，归类对比，预测客户其后的行为5。但实际上，自己的下一步目标客户自己可能都不十分清楚。所以，对

12、于数据挖掘的结果，有一定参考价值，却不一定为生活中的真正答案。12 数据挖掘的研究意义在信息时代，我们生产和处理数据能力迅速提高，但是被我们直接利用的数据只占我们存储的一部分，将隐含在其中有价值的信息，从随机的，有噪声的信息中提取出来，应用于实际操作中，提供决策支持，创造价值6。13 国内外发展及研究现状其他国家对数据挖掘的研究与应用已有很长的时间的发展，累积了了大量的数据与6研究成果7。国外在数据挖掘的应用方面，已经有大量的软数据挖掘软件应用于各种领域，并在应用的领域创造了巨大的价值。国内对知识与发现的研究要相比于国外，落后的差距较大。我国在 1993 年才对数据挖掘研究起步，目前主要的研究

13、人员在大学中，并且还停留在对理论的研究。对应用方面还是较为薄弱，所以其研究资金主要是由国家承担的。14 开发环境本文采用了基于 Myeclipse 平台的 java 语言。下面对采用 Java 语言和 Myeclipse 平台的原因进行阐述。141 采用 Java 语言的原因Java 语言具有以下特点：1） 支持多平台，Java 虚拟机解决了操作系统和核心系统资源变化对编写的程序造成的影响，Java 编写的程序可以在任何安装了 Java 虚拟机的计算机上正确运行；2） 多线程，允许同时完成多个任务；3） 面向对象，支持垃圾回收和异常处理机制；4） 解释型；5） Java 语言是免费和开放的。2

14、 数据集介绍表 2.1 数据集数据个数数据集数据个数（个）频繁项集数Mushroom186852一般Connect2904951极多Accidents72307多T10I4D100K1010228极少表 2.2 数据集数据规律数据集数据集特征数据示例Mushroom数据大小变化速度快，增加幅度无规律。1 3 9 15 23 25 34 36 38 40 52 54 59 63 67 76 85 86 90 93 Connect数据每次增加 3，添加少量噪声数据。10 13 16 27 30 33 65 68 71 74 77 Accidents数据每次增加 1，并在连续几个数之后，突变到另一个

15、数，继续每次增加 1，加入少量噪声数据10 11 12 21 22 23 29 30T10I4D100K数据无规律，完全散乱排列。93 354 583 606 617 937 71 236 419 477 489 701 706 722 7363 关联规则算法关联规则即支持度和信任度都完全满足客户设定阈值的规则8。事实上，支持度就是一个对数据库研究的概率值，支持度越高代表发现规则的价值在该领域在该数据库越高，由客户或者用户指定实际所需的支持度，代表了用户意愿及其应用领域的特征。从定义上可以得出， 的置信度是一个条件概率。也就是YX)|(XYP)()(supportYXPYX)|(）（confi

16、denceXYPYX31 Apriori 算法3.1.1 Apriori 算法介绍7R.Agrawal 首先提出关联规则模型，并提出了 Apriori 算法9。Apriori 算法是用先验规律来减少扫描所花费的时间代价，使算法效率提高。Apriori 算法在数据挖掘领域具有很高的地位与很大影响力，很多算法都借鉴过 Apriori 算法的思想并加以改进。3.1.2 Apriori 算法实现数据库中的项集具有如下性质：性质 1：频繁项集的子集必为频繁项集。性质 2：非频繁项集的超集一定是非频繁的10。算法的伪代码描述：输入：数据库；D最小支持度阈值supmin输出：关联规则频繁项集。;sup;mi

17、n.|;.);,(all);(_);2(；频繁一项集111kkkktktkkkLAnswercountcCcLcountcdoCccandidatesallfortCsubsetCbegindoDtnstransactioforLgenaprioriCbegindokLkforL;)()1(112211;,;1,1,2,1C into()_111kkkkkCfromcdeletethenLsifdocofsubsetskallforkqkpandkqkpandandqpwhereqLPLformkqkpppselectinsertgenapriori3.2 频繁模式增长算法3.2.1 FP-g

18、rowth 算法介绍 Jiawei Hn 等人在研究数据挖掘算法时，没有采用 Apriori 算法的先验方法缩减项集，而是提出了 FP_Tree 算法11。 Fp-growth 算法的结构是用频繁模式树：1）频繁模式树的根结点为 null。 82）每个结点包含 3 个部分：item-name 项目名，count 结点数，item-next 指向兄弟结点。3.2.2 FP-growth 算法实现构建 FP 树算法：1）通过初次读取数据集，得到该数据集内的频繁一项集及其阈值集合。2）对每个频繁一项集按照第一次扫描的支持度降序排列每个频繁项集，并形成项目频繁列表 L，创建树的结点并且根节点值为空。

19、3）；begindoDtntranscatioallfor4） endTPptreeinsert);,|(_5）);,(_)!(;点队列中；连接到根节点与同名结; 1.:)(;.)_._.&();,|(_NPtreeinsertthennullPifpPPendcountNNNewelsecountNthennameitempnameitemNTNifTPptreeinsert3.3 Eclat 算法3.3.1 Eclat 算法介绍J.ZAKI 于 2000 年提出了 ECLAT 算法，采用了与传统挖掘算法水平数据库表示方式完全不同的数据库结构垂直数据表示，利用前缀等价关系划分搜索空间

20、12。算法过程：1) 首次扫描，可以得出频繁一项集并获得其支持度。2) 再次扫描，可以得出频繁二项集并以链表方式存储。表 3.1 水平数据库事物 TID项目 Item1A,B,D2C,D,E,F3B,C,E4A,C,D,E5A,B,C,D,E,F6C,E,F表 3.2 Tidset 垂直数据库项目 Item事物 TIDA1,4,5B1,3,5C2,3,4,5,69D1,2,4,5E2,3,4,5,6F2,5,63.3.2 Eclat 算法实现输入：数据集， 最小支持度。minsup输出：频繁项集。首次扫描，找出其内的频繁一项集。;);()(,)minsup)();()()(;,)1(11end

21、ElseTEclatTifRTTRLLRTidsetifXTidsetXTidsetRTidsetXXRdoijLXallfordoLXallforLECLATiiiiiijiii4 实验结果与分析4.1 相同算法对相同数据集进行不同支持度数据挖掘4.1.1 Apriori 对各个数据集进行不同阈值数据挖掘表 4-1 Apriori 算法对 mushroom 数据集进行不同阈值数据挖掘阈值0.350.305时间（ms）50311103222033282754742334项集（个）1189273555455366398575单个项集时间（ms）4.234.033.975.2

22、77.53对表 4-1 进行分析，可以发现 Apriori 算法在对快速增长数据集进行数据挖掘时，所用的时间随着频繁项集的增加而增加，通过与项集个数的对比，可以发现，在阈值大于 0.25 时，频繁项集数量增加的速度不快，单个项集所用的时间基本相等而在阈值小于 0.25 后，频繁项集的数量突然急剧增加，算法所用的时间与发现单个频繁项集的时间都大幅度增长。表 4-2 Apriori 算法对 T10I4D100K 进行不同阈值数据挖掘阈值0.350.3050.100.05时间（ms）2032352192192032191297项集（个）00000010单个项集时-129.710

23、间（ms）对表 4-2 进行分析，可以发现 Apriori 算法那在对 T10I4D100K 数据集进行数据挖掘时，在没有频繁项集时，其所用时间非常平稳，但在出现频繁项集后，所用时间有一个大幅度的突变增加。表 4-3 Apriori 对 accidents 进行不同阈值数据挖掘阈值0.350.30时间（ms）6539722515885项集（个）91851201883单个项集时间（ms）7.1212.46对表 4-3 进行分析，Apriori 算法对突变数据集进行数据挖掘时，发现单个项集的时间与总时间随着频繁项集数目的增多而增多。通过与表 4-1 一起分析，可以发现，Apriori 算法对频繁项

24、集的个数较为敏感，总时间与发现单个项集的时间会随着频繁项集数量的增加而增加。表 4-4 Apriori 算法对 connect 数据集进行不同阈值数据挖掘（未完成运行）阈值0.35时间（小时）10.5项集（个）79555单个项集时间（ms）475.14Apriori 算法在运行该算法时，由于所需运行时间太长，无法运行出最终结果，只能对部分结果进行分析，通过与表 4-1、表 4-3 一起分析，发现运行时间更长，而发现的频繁项集数目却更少，而原因就在数据集本身，由于 connect 数据集比 accidents数据集与 mushroom 数据集大的多，所以发现每个频繁项集就需要扫描一遍数据集而导致

25、时间的极速增长而发现的频繁项集的速度异常慢。4.1.2 Fp_Tree 对各个数据集进行不相同阈值数据挖掘表 4-5 Fp_Tree 算法对 mushroom 数据集进行不同阈值数据挖掘阈值0.350.305时间（ms）7199381516754314349项集（个）1189273555455366398575单个项集时间（ms）0.600.340.270.140.15对表 4-5 进行分析，Fp-Tree 算法对 mushroom 数据集进行数据发现时所用的总时间会随着阈值的降低，频繁项集数目的增多而增加，但是比较得知单个频繁项集的时间却会减小，减小的幅度会随着频繁项集

26、的增多而减缓。表 4-6 Fp_Tree 对 T104D100K 数据集进行不同阈值数据挖掘阈值0.350.3050.100.05时间（ms）8766831385958344838184708547项集（个）00000010单个项集时间（ms）-854.7对表 4-6 进行分析，Fp-Tree 对 T104D100K 进行数据挖掘所用的总时间比较平稳，即使项集数目的突然少量增加，也不会对算法所用的总时间造成影响。表 4-7 Fp_Tree 对 accidents 数据集进行不同阈值数据挖掘阈值0.350.305时间（ms）20023432329409

27、4239159732903项集（个）9185120188347484512410693957195单个项集时间（ms）00.190.185对表 4-7 进行分析，Fp-growth 对突变数据集（accidents）进行数据挖掘，当阈值减小，频繁项集数目增多，总时间也会随之增多，但是单个频繁项集所用的时间会11减少。与表 4-5 一起分析，可以发现该算法的效率会随着频繁项集数目的增多而提高。因为算法在其所构建的树上进行数据挖掘，所以数据越多，效率越高，花费在构建树上的时间所占比例就越少。4.1.3 Eclat 算法对各个数据集进行不同阈值数据挖掘表 4-8 Eclat 算

28、法对 mushroom 进行不同阈值数据挖掘阈值0.350.305时间（ms）17651172186022192437项集（个）1189273555455366398575单个项集时间（ms）1.480.430.340.0410.0025对表 4-8 进行分析，Eclat 算法对快速增长数据集进行数据挖掘，在阈值减少，频繁项集数目快速增长时，所用的总时间只是缓慢增长，而发现单个频繁项集的时间则急剧减少。表 4-9 Eclat 算法对 T1I4D100K 进行不同阈值数据挖掘阈值0.350.3050.100.05时间（ms）82888578881282

29、97834483298360项集（个）00000010单个项集时间（ms）-836对表 4-9 进行分析，可以发现，Eclat 算法对稀疏集进行数据挖掘所消耗的时间代价十分平稳，即使项集少量增加，总时间亦无明显变化。表 4-10 Eclat 对 accidents 进行不同阈值数据挖掘阈值0.350.305时间（ms）323484691919673500521652项集（个）9185120188347484512410693957195单个项集时间（ms）0.0350.0420.0400.0590.13对表 4-10 进行分析，可以发现阈值减少，频繁项集数目极速增加，所花

30、费的总时间也快速增加，发现打个频繁项集的时间也在增加。Eclat 在进行挖掘时，首先要为每个数据创建并分配概念格，之后的操作的在就是对概念格的操作，所以对数据个数总数小，频繁项集数目较多的数据集进行数据挖掘时，效率高。4.2 相同算法对不同数据集进行相同支持度数据挖掘4.2.1 Apriori 对不同数据集进行各个阈值数据挖掘表 4-11 Apriori 算法对不同数据集进行阈值为 0.35 数据挖掘数据集mushroomT10I4D100Kaccidentsconnect（未完）时间（ms）503120365397210.5 小时项集（个）118909185179555单个项集时间（ms）4

31、.23-7.12475.14表 4-12 Apriori 算法对不同数据集进行阈值为 0.30 数据挖掘数据集mushroomT10I4D100Kaccidents时间（ms）110322352515885项集（个）27350201883单个项集时间（ms）4.03-12.46表 4-13 Apriori 算法对不同数据集进行阈值为 0.25 数据挖掘数据集mushroomT10I4D100K12时间（ms）22033219项集（个）55450单个项集时间（ms）3.97-表 4-15 Apriori 算法对不同数据集进行阈值为 0.20 数据挖掘数据集mushroomT10I4D100K时间

32、（ms）282754219项集（个）536630单个项集时间（ms）5.27-表 4-16 Apriori 算法对不同数据集进行阈值为 0.15 数据挖掘数据集mushroomT10I4D100K时间（ms）742334203项集（个）985750单个项集时间（ms）7.53-对表 4-114-16 进行分析，可以发现 Apriori 算法对 mushroom 数据集的效率最高，对 connect 数据集的效率最低。考虑不同数据集内数据量的多少，与频繁项集的多少，可以发现，Apriori 对快速变化，数据量较少的数据集（mushroom）效率最高，对数据数量很少，但频繁项集很多的数据集（acc

33、idents）的效率一般，而对数据量异常多，频繁项集也极多的数据集（connect）的效率极低。总结为，Apriori 由于发现每个项集都要对数据集进行一次完整的扫描，算法的效率受频繁项集的数量与数据集内数据的数量的限制，数据集内数据的个数越多效率越低。所以算法擅长对频繁项集数量少或者频繁项集数量极少，数据量很大的数据集进行数据挖掘。4.2.2 Fp_Tree 算法对不同数据集进行各个阈值数据挖掘表 4-17 Fp_Tree 对不同数据集进行支持度为 0.35 数据挖掘数据集mushroomT10I4D100Kaccidents时间（ms）719876620023项集（个）1189091851

34、单个项集时间（ms）0.60-0.22表 4-18 Fp_Tree 对不同数据集进行支持度为 0.30 数据挖掘数据集mushroomT10I4D100Kaccidents时间（ms）938831343232项集（个）27350201883单个项集时间（ms）0.34-0.21表 4-19 Fp_Tree 对不同数据集进行支持度为 0.25 数据挖掘数据集mushroomT10I4D100Kaccidents时间（ms）1516859594094项集（个）55450474845单个项集时间（ms）0.27-0.20表 4-20 Fp_Tree 对不同数据集进行支持度为 0.20 数据挖掘数据集

35、mushroomT10I4D100Kaccidents时间（ms）75438344239159项集（个）5366301241069单个项集时间（ms）0.14-0.1913表 4-21 Fp_Tree 对不同数据集进行支持度为 0.15 数据挖掘数据集mushroomT10I4D100Kaccidents时间（ms）143498381732903项集（个）9857503957195单个项集时间（ms）0.15-0.185对表 4-17表 4-21 进行分析，可以发现 Fp-growth 算法的效率随着阈值的减少，频繁项集数目的增多，算法的效率不断提高，但在阈值小于等于 0.20 时，Fp_tr

36、ee 对mushroom 数据集的效率超过了对 accidents 数据集的效率。总结为，Fp-growth 算法在阈值较大时，对数据量较少，频繁项集数目较多的数据集进行数据挖掘的效率较高；在阈值较小时，对数据量较多，频繁项集数目较少的数据集进行数据挖掘的效率较高。因为如果频繁项集越多，树内存储的信息就会越多，在树内进行挖掘的效率就会越高。4.2.3 Eclat 算法对不同数据集进行各个阈值数据挖掘表 4-22 Eclat 算法对不同数据集进行阈值为 0.35 数据挖掘数据集mushroomT10I4D100Kaccidents时间（ms）176582883234项集（个）1189091851

37、单个项集时间（ms）1.48-0.035表 4-23 Eclat 算法对不同数据集进行阈值为 0.30 数据挖掘数据集mushroomT10I4D100Kaccidents时间（ms）117285788469项集（个）27350201883单个项集时间（ms）0.43-0.042表 4-24 Eclat 算法对不同数据集进行阈值为 0.25 数据挖掘数据集mushroomT10I4D100Kaccidents时间（ms）1860881219196项集（个）55450474845单个项集时间（ms）0.34-0.040表 4-25 Eclat 算法对不同数据集进行阈值为 0.20 数据挖掘数据集

38、mushroomT10I4D100Kaccidents时间（ms）2219829773500项集（个）5366301241069单个项集时间（ms）0.041-0.059表 4-26 Eclat 算法对不同数据集进行阈值为 0.15 数据挖掘数据集mushroomT10I4D100Kaccidents时间（ms）24348344521652项集（个）9857503957195单个项集时间（ms）0.0025-0.13对表 4-22表 4-26 进行分析，可以发现 Eclat 算法对 mushroom 数据集进行数据挖掘时，其总时间随着频繁项集数目的总数的增多而缓慢增加，效率则会随着越来越14高

39、。而对 accidents 数据集进行数据挖掘时，总时间会随着频繁项集数目的增多而快速增加，其效率则不断降低，发现单个频繁项集的时间会增加。总结为 Eclat 算法对数据量较多而频繁项集数目较少的数据集进行数据挖掘时，其挖掘效率会随着阈值的降低而提高；对数据集内数据个数较少，而频繁项集数目多的数据集，该算法的挖掘效率会因为阈值的减少，频繁项集的增多而增长。因为算法是基于概念格理论，其操作是 and，or 操作。所以，频繁项集越多，一个概念格进行与或操作的次数就会越多，发现的频繁项集就会越多，其效率也会越高。4.3 不同算法对相同数据集进行相同阈值数据挖掘4.3.1 不同算法对 mushroom

40、 进行各个阈值挖掘表 4-27 不同算法对 mushroom 数据集进行阈值为 0.35 数据挖掘算法FP_growthEclatApriori时间（ms）71917655031项集（个）118911891189单个项集时间（ms）0.601.484.23表 4-28 不同算法对 mushroom 数据集进行阈值为 0.30 数据挖掘算法FP_growthEclatApriori时间（ms）938117211032项集（个）273527352735单个项集时间（ms）0.340.434.03表 4-29 不同算法对 mushroom 数据集进行阈值为 0.25 数据挖掘算法FP_growthE

41、clatApriori时间（ms）1516186022033项集（个）554555455545单个项集时间（ms）0.270.343.97表 4-30 不同算法对 mushroom 数据集进行阈值为 0.20 数据挖掘算法FP_growthEclatApriori时间（ms）75432219282754项集（个）536635366353663单个项集时间（ms）0.140.0415.27表 4-31 不同算法对 mushroom 数据集进行阈值为 0.15 数据挖掘算法FP_growthEclatApriori时间（ms）143492437742334项集（个）985759857598575单

42、个项集时间（ms）0.150.00257.53对表 4-27表 4-31 进行分析，可以发现，Apriori 对 mushroom 数据集的效率是最低的，Apriori 所用的时间与效率和 Fp-tree 算法，Eclat 比较，差距会随着阈值的降低、数据集频繁项集数量的增多而不断加大。与另外两个算法相比，Apriori 算法不擅长对该数据库进行数据挖掘，因为 Apriori 算法会随着频繁项集的增多，遍历整个数据集的趟数也会增多。通过对 FP-tree 算法与 Eclat 算法的时间与效率对比，在阈值较大时，Fp-tree 算法的效率要优于 Eclat 算法，并且两个算法的效率都会由于阈值的

43、减少，频繁项集数15目的增大而提高，但是 Eclat 算法的效率的加快要高于 Fp-growth 算法，所以在阈值为 0.20 时，Eclat 算法的效率超过了 Fp-growth 算法。Fp-growth 算法先构造树，如果树的结构过大，树内寻找到另一个数据所花的时间代价也不可忽略，而 Eclat 算法，通过对概念格的操作，不需要频繁的寻址，在频繁项集数量多时，优势就会体现出来。总结为 Apriori 算法与 Fp_tree 算法和 Eclat 算法相比，在对数据集内数据量较少，频繁项集较少的数据集进行数据挖掘时，没有任何优势。而 Fp-growth 算法在阈值较大时，效率高于 Eclat；

44、阈值较小时，则是 Eclat 算法的效率高于 Fp-growth 算法。4.3.2 不同算法对 T10I4D100K 进行各个支持度挖掘表 4-32 不同算法对 T10I4100K 进行阈值为 0.35 数据挖掘算法FP_growthEclatApriori时间（ms）87668288203项集（个）000单个项集时间（ms）-表 4-33 不同算法对 T10I4100K 进行阈值为 0.05 数据挖掘算法FP_growthEclatApriori时间（ms）854783601297项集（个）101010单个项集时间（ms）854.7836.0129.7由于在阈值为 0.30-0.10 时，结

45、果与阈值为 0.35 几乎一致，所以省略0.30,0.25,0.20,0.15,0.10 这 5 张图表。对表 4-32表 433 进行分析，可以发现Apriori 算法全面优于 Fp-growth 算法和 Eclat 算法。即使突然有了少量频繁项集，但是 Apriori 的算法依旧比其他两个算法快了不少，但是相比所花费时间的稳定性，Apriori 算法就差了不少，在有了频繁项集之后，Apriori 算法有一个突变。但是 Fp-growth 算法和 Eclat 算法所花费的时间并无多大的变化。4.3.3 不同算法对 accidents 进行各个阈值数据挖掘表 4-34 不同算法对 accide

46、nts 进行阈值为 0.35 数据挖掘算法FP_growthEclatApriori时间（ms）200233234653972项集（个）918519185191851单个项集时间（ms）0.220.0357.12表 4-35 不同算法对 accidents 进行阈值为 0.30 数据挖掘算法FP_growthEclatApriori时间（ms）4323284692515885项集（个）201883201883201883单个项集时间（ms）0.210.0424.03表 4-36 不同算法对 accidents 进行阈值为 0.25 数据挖掘算法FP_growthEclat时间（ms）94094

47、19196项集（个）474845474845单个项集时间（ms）0.200.04016表 4-37 不同算法对 accidents 进行阈值为 0.20 数据挖掘算法FP_growthEclat时间（ms）23915973500项集（个）12410691241069单个项集时间（ms）0.190.059表 4-38 不同算法对 accidents 进行阈值为 0.15 数据挖掘算法FP_growthEclat时间（ms）732903521652项集（个）39571953957195单个项集时间（ms）0.1850.13对表 4-34表 4-38 分析，可以得知 Apriori 在频繁项集数目项

48、集数目较多时，全面落后于 Fp-growth 算法和 Eclat 算法，它所耗费的时间和它的效率不在一个数量级上。所以对比分析就在 Fp-growth 算法和 Eclat 算法中进行。可以看出 Eclat 算法一直优于 Fp-growth 算法，但是在阈值大于 0.25 之后，Eclat 算法效率有降低的趋势，而 Fp-growth 算法的效率虽然相比 Eclat 算法较低，但是它的效率依然在缓慢提升；如果按照这个趋势发展，Fp-growth 算法的效率很可能超过 Eclat 算法。4.3.4 不同算法对 connect 进行各个阈值挖掘表 4-39 不同算法对 connect 进行阈值为 0

49、.35 挖掘（未完成运行）算法Apriori时间（小时）10.5项集（个）79555单个项集时间（ms）475.14在对 connect 数据集进行数据挖掘时，由于在编译器中限制了运行内存的大小，导致 Fp-growth 算法和 Eclat 算法在运行时会直接发生内存溢出异常，而 Apriori 算法虽然运行的异常缓慢，运行了 10.5 个小时只出了一小部分结果，可以预见，在大量的时间下，Apriori 算法会运行出最终结果。5 不同算法的优势与不足Apriori 算法的优势：在对 T10I4D100K 进行数据挖掘时，表现最为突出，速度是Fp-tree 算法和 Eclat 算法的近 40 倍

50、。表明如果数据集内数量庞大，几乎没有频繁项集的情况下，Apriori 的效率有绝对的优势。该算法对 connect 数据进行数据挖掘，可以得知，Apriori 所耗费的物理内存要远小于 Fp-tree。所以，Apriori 更加适合只有很少频繁项集的数据集。由于其对物理内存的要求不高，所以如果设备的物理内存少，而且数据集庞大，频繁项集多的情况下，Apriori 算法也是很好的选择。Apriori 算法的不足：在频繁项集数量极少的数据集上有优异表现的 Apriori，在频繁项集数目较多的情况下就全面落后于 Fp-tree 和 Eclat，它对这样的数据集进行数据挖掘时，效率会差另外两个算法十倍百

51、倍或者更多。并且由于 Apriori 的运行原理，每发现一个项集，就要完整遍历一遍数据集。在频繁项集数目较多时，会对物理存储设备造成较大的损耗。Fp-growth 算法的优势：通过对 T10I4D100K 的数据挖掘，Fp-growth 算法的稳定性很高，波动很小，花费的时间即使在频繁项集数目有一个突变时也无明显变化。在对 mushroom 数据集进行高阈值数据挖掘时，是三个算法中表现最突出的。可以得知Fp-treeh 算法擅长对数据集数量中等，并且项集数目较少的数据集进行数据挖掘。Fp-17growth 算法在对 accidents 进行数据挖掘时，Fp-growth 算法在实验阈值内的效率并没有超过 Eclat 算法，但是会随着阈值的降低，效率提升的速度会超过 Eclat 算法。表明 Fp-growth 算法在对数据量较少，频繁项集数量多的数据集进行低阈值数据挖掘时，也会有出彩的表现。Fp-growth 算法的不足：虽然在 T10I4D100K 数据集上表现出了很好的稳定性，但是所花费的时间与 Apriori 算法相比还是略长。在对 mushroom 数据集进行低阈值数据挖掘时，