FP―Growth算法在电子商务中的应用

【摘要】针对电子商务推荐销售的需求和FP-Growth算法不产生候选集的特性，提出利用FP-Growth算法，运用VC++程序开发工具，对某一电商卖家的数据进行频繁项集挖掘，针对挖掘得到的频繁K项集，指导卖家如何组合商品销售。试验结果表明利用FP-Growth算法在电商组合销售中是有效的。

【关键词】候选集；频繁项集；电子商务；FP-Growth FP-Tree

引言

在过去的数十年中，经济发展迅猛，信息化水平不断提高，网络购物成为人们购物的新趋势，各大电子商务平台方便快捷的收集了海量数据，利用好这些数据就可以为网络销售提供丰富的、有用的商业信息。频繁项集挖掘就是利用这些数据的一个典型算法，很早之前就开始应用到传统零售行业的购物篮分析[1，2]，把这种数据挖掘算法应用在电子商务中就是购物车分析[3]。其核心思想是通过频繁项集的分析处理，发现买家“购物车”中所有商品之间的关联，获悉顾客的购买习惯。这种关联的发现可以帮助电商卖家了解哪些商品会被顾客同时购买，帮助他们设计更好的组合销售营销策略。例如，如果顾客在当当网购买点读笔的同时，他们有多大可能也同时购买点读材料（以及何种点读材料），这种信息可以帮助电商合理组合商品优惠，吸引消费者购买更多产品，从而增加销售量。购物车分析的目标是在顾客的购买交易中分析出同时购买一类产品或一组产品的可能性（相互关联），从购物车分析中获得的知识是很有价值的。关联规则挖掘在数据挖掘是一个活跃的研究内容。其中比较常用的算法有早期的Apriori[5]的算法，FP-Growth算法，以及这两种算法的各种改进版本。本文旨在为中小电商卖家（如淘宝、天猫上的店铺）提供一些有效的数据分析，因此在算法上选择比较经典FP-Growth算法，这种算法主要通过FP-Tree来构造频繁集。

FP-Tree是一个数据库里跟产生频繁项集有关的信的压缩表示。在具体的实现中，我们通过了一系列的信息的从低到高的数据结构来实现它，并进而实现整个算法。

1、关联规则挖掘基本概念

FP-Growth算法的优点是节省时间和空间，对大规模数据采用分治的办法以避免规模巨大难以接受。FP-Growth算法主要通过FP-Tree来构造频繁集。这里仅介绍与FP增长算法有关的基础概念。

定义一：设 I = { I1 ， I 2 ，...， I n }是n个不同项的集合，称Ik为一个项目，项目的集合I称为项集，其中元素的个数称为项集的长度k。

定义二：每个事务T是项集I的一个子集，即TI。每个事务有一个唯一的标识符，记作TID。事务全体构成了事务数据库D。

定义三：设项集X，有XT。关联规则是形如XY的蕴涵式，其中XI，YI，并且。表示项集X在某一交易中出现，则导致Y以某一概率也会出现。用户关心的关联规则，可以用两个标准来衡量：支持度（support）和可信度（confidence）。

定义四：支持度是项集同时包含X和Y的项集个数与项集个数之比。它是概率P（XY）。可信度是指包含X和Y的项集个数与包含X的项集个数之比，它是条件概率P（Y|X）。即

定义五：设关联规则的最小支持度和最小可信度分别为sup_min和conf_min，支持度小于sup_min且置信度小于conf_min的规则记作强关联规则。关联规则挖掘的目的就是找出这种强关联规则。

定义六：支持度不小于sup_min的项集称为频繁集，长度为k的频繁集称为k-频繁集。

通过以上定义，我们知道关联规则挖掘的两个主要问题是：

（1）找出项集数据库中所有大于或者等于sup_min的频繁项集。

（2）根据conf_min筛选出强关联规则。

在这两个问题中，找出频繁集是比较困难，所以目前所有的关联规则算法主要是针对第一个问题进行研究，而有了频繁集再生成强关联规则就相对容易了。

2、FP增长算法应用

FP-Growth算法是一种不产生候选集的挖掘频繁项集算法。它通过构造一个数据结构（FP-tree），高度压缩原来的事务数据库。FP-Growth的算法共扫描两次数据库[3]：第1次扫描数据库，得到频繁1-项集；第2次扫描数据库，利用频繁1-项集过滤数据库中的非频繁项，同时生成FP-Tree。最后通过这棵树生成关联规则。

2.1建立原始样本数据库

设事务数据库中有5个事务，见下表1所示。

2.2建立频繁项集头表

假定最小事务支持计数为3（即min_sup=3/5=60%）。扫描数据库一次，得到频繁1-项集，把项集按支持度递减排序，确定频繁项集头表Head。它由具有最小支持度的候选1-项集组成，见表2所示。

2.3建立FP-Tree

2.4从FP-Tree到条件模式库

按每个频繁项的连接遍历FP-Tree，列出能够到达此项的所有前缀路径，得到条件模式库，如表4所示。

2.5从条件模式库得到频繁项集

从条件模式库的p项开始，遍历其条件模式库中的每一项，列出公共部分，包括单项及多项之间的组合，并进行相应的计数，得到条件FP-Tree，再将条件FP-Tree与相应的头表项进行连接，最终生成频繁项集。如表5所示。

3、FP增长算法应用实例和程序实现

3.1应用实例

我们随机的从淘宝某卖家的实验样本中抽取了一部分数据（如表6所示）模拟FP增长算法的过程。表格中的数据表示不同的顾客购买不同的商品种类，表格开头一列是顾客的编号，每一行表示的是顾客购物车中的商品名称编号，对这个原始购物车数据可以挖掘出商品间的关联关系。

3.2程序模块设计和代码实现

3.2.1程序模块设计

在进行程序设计时，我们采用三层处理模块（如图3所示）。底层为数据处理模块，采用UltraEdit等工具来提供原始数据并进行数据处理；中间层为业务逻辑处理模块，按照论文所用到的FP增长算法计算顾客购物车中商品的关联关系，具体过程在Visual C++开发工具环境中实现的；上层为输出模块，用户可以观看到频繁项集挖掘结果。

3.2.2部分代码实现

4、结束语

本文利用程序把以上分析的FP-Growth算法实现，并挑选了一些中小电商卖家的销售数据进行实验。试验结果表明，这些挖掘算法在电子商务的购物车分析中有相当大的优势，为电商卖家提供了非常有说服力的销售策略数据。但是当数据量巨大是，我们选择的挖掘算法就难以顺利进行。因此需要针对大数据量背景下的挖掘算法改进，其中思路之一就是利用Hadhoop框架实现并行化且负载均衡的FP-Growth算法，以解决原有FP-Growth算法在内存和计算能力上的问题，为当当、京东、亚马逊等大型电商平台提供组合推荐销售的理论依据。