FP_growth与Apriori算法比较应用.pdf

FP_growth 与 Apriori 算法比较应用 杨威 1，耿立明 2，杨丹 3 1.辽宁工程技术大学电子与信息工程学院，辽宁葫芦岛（125105） 2.辽宁工程技术大学电气与控制工程学院，辽宁葫芦岛（125105） 3.辽宁工程技术大学职业技术学院，辽宁阜新（123000） 摘 要：随着数据挖掘技术的不断向前发展，新的、高效的算法的不断出现。服务行业业务 中，由于算法的固有缺陷而影响数据挖掘效果和效率的问题显得尤为突出。因此，如何发现 应用新算法在各行各业中将是我们面临的新的问题。本文以关联规则数据挖掘技术为基础， 在关联规则众多算法中通过比较经典 Apriori 算法与 FP_growth 算法，论证后者的性能优越 性并以之应用于保险营销数据应用。 关键词：关联规则，Apriori 算法，FP_growth 算法 中图分类号：TP311 0. 绪论 就保险行业来讲，关联规则在[2]整个服务性行业中有着重要的作用，都是关系各行业的 经营、利益等。分析来讲，顾客至上并非空谈，在现实中对服务行业真应该说“顾客就是上 帝”。保险行业在这方面的依赖性就更加明显。首先利用关联规则可以分析客户的基本情况、 家庭组成、经营情况、投保和赔付历史以及稳定程度等信息，细分客户、细分服务，鉴别优 质劣质客户，进而采用不同的服务。其次，集成数据，适时分析业务发展状况，及时调整经 营策略。通过分析数据、指标和数学模型来加强风险控制。再次，借助要客户关系管理分析 客户需求，提高本公司的决策支持和商业智能水平。建立科学的管理和服务体系，作为稳定 和吸引客户的重要措施[1]。 1. Apriori 算法 1.1 基本概念和性质 为了生成所有频繁项集，Apriori 使用了递推方法。 定义 4.9：给定最小支持率 Minsupport，若项目集 A 的支持率大于 Minsupport，则称项 目集 A 是频繁项目集或频繁模式。 定义 4.10：满足最小支持度和最小信任度的关联规则称为强关联规则(Strong Association Rules)。 性质 1：频繁项的子项也是频繁项。 性质2：非频繁项的父项也是非频繁项。 1.2 Apriori 算法基本思想 （1）找出所有的频繁项集：根据定义，这些项集出现的频繁性至少和预定义的最小支持度 一样，即满足 Support 不小于 Minsupport 的所有项目子集。 （2）由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小可信度。 挖掘关联规则的总体性能由第一步决定。 频繁项集的生成原理：从包含每个项的 C1 中找出 1-项频繁集的集合 L1。然后，连接 LK-1 产 生 k -项候选集的集合 CK，并根据 Apriori 性质删除那些具有非频繁子集的候选集。最后， -1- 扫描数据库一次，统计候选集的支持计数，与最小支持计数相比，形成频繁集。 1.3 Apriori 算法瓶颈 很显然，Apriori 算法有如下四方面的性能瓶颈： 1）对数据库的扫描次数过多。当事务数据库中存放大量事务数据时，在有限的内存容 量下，系统 I/O 负载相当大。对每次 k 循环，候选集 CK 中的每个元素都必须通过扫描数据 库一次来验证其是否加入 LK。假如有一个频繁大项集包含 10 个项的话，那么就至少需要扫 描事务数据库 10 遍。每次扫描数据库的时间就会非常长，这样导致 Apriori 算法效率相对低。