基于FP-Growth的营销策略关联规则分析算法设计与实现(数据准备与原理阐释）_fp算法应用案例

1. • 绪论

随着互联网媒介的发展兴起，营销活动已成为企业、商家等组织的一种营销手段和吸粉途径。一场好的营销活动，为企业带来的商业价值和意义是值得肯定的。

活动营销是指企业通过介入重大的社会活动或整合有效的资源策划大型活动而迅速提高企业及其品牌知名度、美誉度和影响力，促进产品销售的一种营销方式，是围绕活动而展开的营销，以活动为载体，使企业获得品牌的提升或是销量的增长。活动营销的意义包括：

1. 提升品牌的影响力，将品牌核心价值融入到活动营销的主题里，引起消费者的情感共鸣；

2. 提升消费者的忠诚度，提升消费者对品牌的美誉度；

3、吸引媒体的关注度。

数据挖掘( DM, Data Mining) 又称知识发现 ( KDD, Knowledge Discovery in Databases) 就是从大量的、不完全的、有噪声的、模糊的、随机的数据中, 提取隐含在其中的、人们事先不知道的、但又潜在的有用信息和知识的过程。数据挖掘有时也被人们称为知识挖掘、知识提取等。在数据挖掘知识中, 关联规则模式是比较重要的一种。关联规则揭示项集间有趣的相联关系,可广泛应用于市场营销、医学、金融、生物、电信、农业等领域,是数据挖掘的重要研究课题。而FP-growth算法是当前挖掘频繁项集算法中应用最广,并且不需要产生候选项集的关联规则挖掘算法。

这次我的选题便是从关联规则视角出发，以使公司能够最大化下一次营销活动的利润为立足点，建立了基于FP-Growth的营销策略关联规则分析算法，并从宏观角度提出将营销活动与客户的个人特征与选择相结合的最大化下一次营销活动的利润营销策略。

2. • 相关理论与技术

2.1关联规则介绍：

数据挖掘中的关联规则是其中最有用的信息之一, 它反映了大量数据中项目集之间"有趣" 的关联或相关联系。

关联分析算法有一个非常有名的故事——“购物篮分析”，在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是："跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在"尿布与啤酒"背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。

频繁项集导致发现大型事务或关系数据集中项之间有趣地关联和相关性。购物篮中的商品之间可能存在关联，分析顾客的购物习惯，比如顾客购物篮中，同时出现啤酒和尿不湿的例子多，可以帮助零售商做选择性销售以及货物安排。

频繁模式：指频繁地出现在数据集中的模式（如项集、子序列或子结构），比如频繁同时出现婴儿纸尿裤和啤酒的购物篮的例子在交易数据集中的商品的集合称为频繁项集。就比如最常出现的如果是先买啤酒，再买婴儿纸尿裤，如果这样的数据频繁出现，则称为频繁序列模式。子图、子树或子格等结构频繁出现在数据库中，称为频繁结构模式。

这种这种通过研究用户消费数据，将不同商品之间进行关联，并挖掘二者之间联系的分析方法，就叫做商品关联分析法，即购物篮分析模型。类似于我这次的选题——基于FP-Growth的营销策略关联规则分析算法设计与实现，主要目标是得到不同顾客之间进行关联，并挖掘二者之间联系的分析方法，使公司能够最大化下一次营销活动的利润。

2.2关联规则及其抽象描述

2.2.1相关术语：

1. 事务（Transaction Data Itemset, TI）：

事务是项的集合。本质上，一个事务就是事实表中的一条记录。事务是项集I的子集。事务的集合称为事务集。一般用符号D表示事务集/事务数据库。

2. 项（Item）：

对一个数据表而言，表的每个字段都具有一个或多个不同的值。字段的每种取值都是一个项Item。

3. 项集（Itemset）：

项的集合称为项集itemset。包含k个项的项集被称为k-项集，k表示项集中项的数目。由所有的项所构成的集合是最大的项集，一般用符号I表示。

4. k−项集：

包含k个项的项集叫做k-项集，例如{Cola}叫做1-项集，{Cola, Egg}叫做2-项集。

5. 支持度计数：

一个项集出现在几个事务当中，它的支持度计数就是几。例如{Diaper, Beer}出现在事务002、003和004中，所以它的支持度计数是3。

6. 频繁项集（Frequent Itemset）：

项集的出现频率是包含项集的事务数，简称项集的频率；项集满足最小支持度阈值minsup，如果项集的出现频率大于或等于minsup与D中事务总数的乘积；满足最小支持阈值的项集就称为频繁项集（大项集）。频繁k项集的集合记为Lk；

7. 最大频繁项（Max Frequent Itemset）：

如果频繁项集L的所有超集都是非频繁项集，那么称L为最大频繁项集。

8. 关联规则：

给定一个事务集D，挖掘关联规则的问题就变成如何产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则的问题。（标准）

9. 强关联规则：

大于或等于最小支持度阈值和最小置信度阈值的规则叫做强关联规则。关联分析的最终目标就是要找出强关联规则。

那么，关联规则的本质，其实就是挖掘频繁项，那么算法的目的也就是尽可能快速有效的挖掘不同事物间关系出现的频率。

而衡量规则是否成立的三个参考维度，就是支持度、置信度以及提升度。

2.2.2支持度、置信度或提升度

那么如何判断商品之间的关联程度呢？有以下三个经典的标准来衡量：支持度、置信度或提升度。

1. • 支持度

A商品和B商品同时被购买的概率，显然支持度越大，商品间关联性越强。计算公式：同时购买A和B订单数 / 总购买订单数，即

比如今天共有10笔订单，其中同时购买尿不湿和啤酒的次数是7次，那么尿不湿+啤酒组合的支持度就是7/10=70%。

2. • 置信度

因为购买了A所以购买了B的概率。表示当A项出现时B项同时出现的频率，记作{A→B}。换言之，置信度指同时包含A项和B项的交易数与包含A项的交易数之比。

计算公式：同时购买A和B订单数 / 购买A的订单数，即：

比如今天共有10笔订单，其中购买啤酒的次数是4，同时购买尿不湿+啤酒组合次数是3，则其置信度是3/4=75%

3. • 提升度

指A项和B项一同出现的频率，但同时要考虑这两项各自出现的频率。先购买A对购买B的提升作用，用来判断商品组合方式是否具有实际价值，大于1说明该组合方式有效，小于1则说明无效。 计算公式：支持度 / ( (购买A次数/总购买订单数)*(购买B次数/总购买订单数) )，即：

比如今天共有10笔订单，购买尿不湿的次数是8，购买啤酒的次数是6，购买尿不湿+啤酒组合的次数是6，那么提升度是0.6 /（0.8*0.6）>1，因此尿不湿+啤酒组合的组合方式是有效的。

关联分析，即找到一定的关联规则，使得支持度、置信度或提升度能够满足规定的阈值。

2.3关联规则挖掘的FP-Growth算法及分析

起初Apriori算法的提出有效的能发现这种物品间的关联规则。Apriori算法是发现频繁项集的一种方法。Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个物品的项集列表。接着扫描交易记录来查看哪些项集满足最小支持度的要求，那些不满足最小支持度的集合会被去掉。然后，对剩下来的集合进行组合以生成包含两个元素的项集。接下来，再重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复进行直到满足退出条件。

但是Apriori算法频繁的扫描数据集，造成效率低下，在大的数据集上执行的会非常缓慢。后来FP-Growth算法的提出有效的解决了这个缺点。

FP-Growth(Frequent Pattern Tree，频繁模式树)算法是关联分析算法，巧妙的将树型结构引入算法中，它采取如下分治策略：提供频繁项集的数据库压缩到一棵频繁模式树（FP-Tree），但仍保留项集关联信息；该算法和Apriori算法最大的不同有两点：

第一，不产生候选集。

第二，只需要两次遍历数据库，大大提高了效率

关联规则挖掘的相关算法及分析关联规则挖掘的目标就是要找出所有的强关联规则。挖掘过程主要分为两步：

• 步骤１：找到所有不小于最小支持度阈值的规则，即所有频繁项集；

• 步骤２：对频繁项集进行过滤，滤掉小于最小置信度的项集，找出强关联规则。

步骤２只需根据步骤１找出的频繁项集使用简单的计算就能得出，因此联规则挖掘算法的核心在于频繁项集的挖掘。最简单的算法是穷举所有的项集组合作为候选集，然后分别检验支持度是否满足预先设定的阈值。这种算法虽简单，但计算效率却很低。随着特征维度的增大，候选集数量会呈指数级增加；且对于每一个候选项集，都需要扫描数据集计算其支持度，当数据量很大时，需要的计算量也很大。显然这种暴力算法不是最好的选择，因此人们致力于寻找更为高效的算法，其中FP-Growth算法是较为经典的算法．

FP-growth算法

FP-growth算法是韩家炜等人于2000年提出的一个关联规则挖掘算法。它设计了一种称为频繁模式树（FP－tree）的数据结构，将原始数据集进行压缩存储。树的根结点为“null”，其余节点代表一个特征项及其支持度信息，每一个项集对应树上的一条路径。为了更加快速地挖掘频繁项集，FP－tree还包含一个两列的频繁项表：

第一列是特征项名称，按照特征项支持度降序排序。

第二列存储一个链表，将FP－tree树中相同特征项的节点连接起来。

FP-growth算法主要分为构建FP－tree和基于FP－tree递归的挖掘频繁项集两个步骤。

FP－tree构建完成后，便可基于它来挖掘频繁项集。分别以频繁项表中的项作为后缀，构造它的条件模式基，条件模式基是FP－tree中与该后缀一起出现的前缀路径的集合。通过条件模式基构造该项的条件FP－tree，并递归地在该树上进行挖掘。模式增长通过后缀模式与条件FP－tree产生的频繁项目连接实现。

图2-1-1 基于FP－tree挖掘频繁项集流程图

总结FP-growth的一般流程如下：

1：先扫描一遍数据集，得到频繁项为1的项目集，定义最小支持度（项目出现最少次数），删除那些小于最小支持度的项目，然后将原始数据集中的条目按项目集中降序进行排列。

2：第二次扫描，创建项头表（从上往下降序），以及FP树。

3：对于每个项目（可以按照从下往上的顺序）找到其条件模式基（CPB，conditional patten base）,递归调用树结构，删除小于最小支持度的项。如果最终呈现单一路径的树结构，则直接列举所有组合；非单一路径的则继续调用树结构，直到形成单一路径即可

FP-growth算法通过两次遍历原始数据集，将数据以FP－tree的形式进行压缩存储。后续频繁项集的挖掘直接利用FP－tree，避免生成无用的候选项集，大大提高了效率。但该算法生成的是频繁项集，而不是关联规则。如要进一步生成关联规则，需根据频繁项集生成候选关联规则，然后通过最小置信度对关联规则进一步过滤，得到强关联规则。

剩下的下一篇博客继续分析，喜欢的话点赞关注，加个收藏不迷路。