- 1 -
中国科技论文在线
FP-Growth 算法的改进及在电子商务推荐
中的应用#
张同启，张华**
基金项目：国家自然科学基金项目（编号：61300181, 61272057, 61202434, 61170270, 61100203, 61121061）
作者简介：张同启（1989），男，硕士研究生，信息安全
通信联系人：张华（1978），女，副教授，主要研究方向：密码协议、物联网和云计算安全、工业控制系
统安全、移动互联网安全
（北京邮电大学网络与交换技术国家重点实验室，北京 100876） 5
摘要：本文在分析 mahout 中并发 FP-Growth 关联挖掘算法源码基础上，结合 B2C 领域中某
大型电子商务网站的实际交易数据特点和具体适配场景，对 FP-Growth 算法存在的事务区分
度差和“长尾”商品的推荐结果缺失进行了改进，以提高 FP-Growth 算法在推荐引擎应用上
的准确率和覆盖率。利用 Java 技术在 Hadoop 平台对该推荐算法的进行了设计与实现。实验10
数据表明，基于改进的算法对该大型网站的实际业务数据来进行关联分析，显著提高了商品
的用户点击率和下载率。
关键词：关联规则；FP-Growth；推荐系统；电子商务
中图分类号：
15
The Research and Improvement of FP-Growth on
E-commerce Recommendation System
ZHANG Tongqi, ZHANG Hua
(State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and
Telecommunications, Beijing, 100876, China) 20
Abstract: In this paper, based on the analysis of source code of concurrent FP-Growth algorithm,
combined with the actual transaction data of a large e-commerce system in B2C field, the
algorithm has been improved in no difference in transaction and the "tail" missing to enhance its
accuracy and coverage rate. The recommendation algorithm is designed and implemented in
hadoop by java language. Through analysis of the actual transaction data, the user's click-through 25
rate and download rate improved significantly.
Key words: Association Rules; FP-Growth; Recommender System; E-commerce
0 引言
随着计算机的普及和互联网的发展，电子商务已经作为一种新型和高效的商务模式迅速
普及，用户在电脑或其他智能设备上轻松点击就能完成复杂的商品买卖行为，但电子商务给30
人们带来方便和快捷的同时也带来了“信息过载”[1]的问题，尤其在用户和商品集相对较大
的 B2C 零售领域。如何帮助客户顺利地完成购物活动成为商家获得利润和信誉的关键[2]。
关联规则算法作为一种高效快速的数据挖掘算法已成为很多领域中最流行的推荐算法
之一，近年来，先后出现了 APRIORI，AIS，PARTITIO 等多种关联规则挖掘算法，其中
FP-Growth 算法最为著名，它相对于其他算法，在时空复杂度和算法精准度等方面都有了很35
大程度的提高，特别是该算法适于并发运算的特性，使其更适应当前不断发展的大数据环境。
尽管如此，在商务推荐领域，FP-Growth 算法必须适应具体推荐场景和数据特点，这就
要求算法必须根据系统应用场景现状进行相应改进。本文在分析 mahout 下并发 FP-Growth
关联算法的基础上，结合某大型电子商务网站的实际业务数据，在事务无区分度和“长尾商
品”的推荐结果缺失方面进行了改进。实验结果表明，改进的 FP-Growth 关联算法应用到商40
- 2 -
中国科技论文在线
品关联分析后，大大提升了推荐系统的准确率和转化率，对商城用户忠诚度和活跃度的提高
具有很强的促进作用。
1 基于并行 FP-Growth 的关联挖掘技术
关联规则算法可以说是一种知识学习系统，它将用户的商务行为作为知识，通过不断学
习获得潜在的频繁模式集合。到目前为止，经过相关专家和学者的不懈努力，关联规则算法45
已经取得了很大进展，不仅产生了很多高效多样的算法，而且随着大数据时代的到来，算法
的数据结构和运算模式也出现了并行化发展趋势。FP-Growth 算法便是一种高效的、适于并
行的算法，最先由知名学者 Han Jiawei[3]教授等提出。
并行 FP-Growth 算法的数据结构
FP-Growth 算法采用了一种称为 Frequent Pattern Tree（简称 FP-Tree[4]）的特殊前缀索50
引树作为存储候选集的数据结构，在建树过程中不断将候选集压缩到这棵频繁树上，这种数
据结构大幅度地压缩了候选集所占空间的大小，同时也使得在找寻关联规则过程中只需两次
遍历数据库，其性能大大优于 APRIORI 算法。假定事务数据库的事务列表如图 1，则一个
典型的频繁模式树的数据结构如图 2 所示。
FP-Growth 的设计体现了一种分治的思想[5]。该算法需要扫描两次数据库，第一次扫描55
数据库时计算所有数据项的频数，并按照此频数的降序排序生成一个 F-List。第二次扫描数
据库首先对事务进行 FP-Tree 的压缩，然后对 FP-Tree 进行递归挖掘，为建查找和建树的过
程。建立 FP-Tree 的时间复杂度可以用如下的递推表达式来进行估计
1
1
t
i
f n f n g i
其中 t 表示第 n 条事务的项目数。当 n 较大的时候，不妨设总事务的项目条数为 s ,则60
g i 的时间复杂度为 O s ,相应的
1
t
i
g i
时间复杂度为 2O s 。所以，总运行时间复杂度的
一个保守上限估计是 2O n s [2]。
Header table
itemcount
Head of
node-links
F
C
A
B
M
p
4
4
3
3
3
3
root
F:4
C:3
A:3
M:2
P:2
B:1
B:1
M:1
C:1
B:1
P:1
图 1 事务数据列表 图 2 FP-Tree 数据结构
Fig. 1 Transaction List Fig. 2 Data Structure of FP-Tree 65
- 3 -
中国科技论文在线
并行 FP-Growth 算法的现状分析及存在问题
关联规则思想于 1993 年由 Agrawal 等人首次提出，通过众多学者和专家的努力，许多
具体算法相继产生。Azgrawal、Imielinski 和 srikant 提出了著名的 Apriori 算法[6]；Park 等人
提出了DHP算法[7]；Haoyuan Li，Edward Y. Chang等提出了时空效率明显提升的FP-Growth[5]70
等。在众多算法中，以 Apriori 和 FP-Growth 算法的应用最为广泛，在实用性和时效性方面
效果也最为突出。随着互联网数据量的激增，FP-Growth 优势更加明显，该算法将事务数据
库有效压缩成多个小存储空间的数据结构 FP-Tree 和 F-List，克服了 Aprior 算法多次扫描事
务数据库的缺陷，同时这种数据结构实现了事务数据库的并行存储，为事务的并行计算提供
了便利。因此，与当前同类关联规则算法相比，FP-Growth 算法更适于应用在大数据环境下75
的商务推荐系统中。
尽管如此，FP-Growth 算法也存在以下两个方面的缺陷：算法本身将所有事务同等对待，
缺少事务区分度，导致算法挖掘出的用户兴趣度模型过于粗糙；另外，由于 FP-Growth 算法
为频繁模式挖掘的一种，其最小支持度决定总性能，这样导致大量“长尾”商品被过滤，影
响推荐系统的预测覆盖率[8]。 80
2 引入时效度和兴趣度概念的 FP-Growth 算法
为增加 FP-Growth 算法的事务区分度，进一步提高推荐系统的准确率。下面从事务的时
效度和兴趣度方面进行相应改进。
时效度
关联规则算法 FP-Growth 本身对事务无差别对待，但是在实际生活中，人类遗忘曲线[9]85
客观存在，购物习惯也在不断变化，具体表现在距现在时间点越近的事务越能代表用户的习
性变化。比如一个客户过去很长时间喜欢看“Java 系列丛书”，最近由于研读挖掘算法，
浏览或购买了数本相关书籍，此时用户的需求很可能为包含挖掘算法相关书籍推荐列表。但
是一般情况下，用户历史行为记录远大于数月，最近时间的这种兴趣变化很可能会被大量历
史数据所淹没。故算法很难反映用户最近的行为变化，即推荐系统不能快速进行知识的学习。 90
时效度概念
定义（时效度）：时效度是指对不同事务按照距离当前时间点远近设置不同权值的序列，
目的是使算法能够通过机器的快速知识学习来反映用户习惯的变化。
时效度设计方案
目标：在时间序列上找到一系列阈值，使之能够在一定程度上反映不同时间段的购买/95
浏览等行为对用户未来购买行为的影响情况。
方法：采用单变量策略对一系列阈值进行调整，自变量为阈值分布情况，目的变量为
F-Score，输入数据为不同时间段的用户商务行为。
第一步，对阈值分布进行初始化操作，在不同时间段赋初值，最好是有经验的销售专家
给予初值指导，以减少调整次数。 100
第二步，抽取能代表商场正常营业情况的一周数据作为测试集。
第三步，从一定时间范围的用户历史行为记录中抽取不同时间段的事务记录组成训练
集，抽取时保证不同时间段的记录数目相同，且保证记录在具体时间段内随机抽样。
第四步，基于艾宾浩斯记忆曲线趋势和专家初值指导，设置不同权值序列并不断进行微
- 4 -
中国科技论文在线
调，采用 F-Score 评价体系对不同阈值组合下的算法进行评估。F-Score[10]定义如下： 105
Pr
u uu
uu
R T
ecision
R
Re
u uu
uu
R T
call
T
Pr Re
2
Pr Re
ecision call
F Score
ecision call
注：R 代表推荐的数目，T 代表测试集。准确率和召回率各表征了模型的预测和覆盖能力，而 F-Score
则是这两方面的均衡表现。 110
第五步：重复上述两步，直到 F-Score 的结果满意为止。此时得到的阈值序列即为该商
品类别下用户对商品的时效度分布。
兴趣度
在 B2C 电子商务领域，能够反映用户兴趣模型的因素很多，比如用户的购买/浏览/收藏
等行为，另外还包括用户对商品的评分或者评论等。目前大部分商务推荐系统都是采用购买115
等一类用户行为，这使得算法构建出的用户兴趣度模型过于粗糙。
兴趣度概念
定义（兴趣度）：兴趣度是指根据用户在电商交易中的多种商务行为，经过一定算法得
到的用户对事务的喜好程度。
用户的行为，可分为显性行为和隐性行为，显性行为包括购买/浏览/收藏等，隐性行为120
包括评分和评论等。这里区分的标准是在目前环境下算法能否对商品行为进行进一步预测，
比如评论，需要相应策略对评论进行处理，使得 FP-Growth 算法能够识别不同评论，将评论
转化为对系统具有真正意义的分值。
对于具体用户，分值大小的确可以反映用户对某件商品的喜爱程度，但是不同用户对于
一个确定评分的理解不同，比如 3 分可能对于用户 A 代表自己对此商品的评价是基本符合125
自己需求，而对于用户 B 来讲可能代表自己对此商品几乎无法忍受。所以如何使评分分值
真正反映用户的兴趣度，需要对用户评分相应处理。
兴趣度设计方案
目标：根据用户对商品的喜好程度和“用户兴趣度统一映射表”，调整用户对商品评分，
使用户评分分值能够在系统层次上反映用户的喜好程度。 130
方法：第一步，定义兴趣度权值映射表。此表可以对商品权值和用户的喜好程度进行映
射，如表 1 所示。
第二步，对用户的历史评论进行文本分析，利用 TF-IDF 算法找到该用户评分下的兴趣
度，通过系统不断收集，建立用户的个人兴趣度和评分映射表，功能类似分类算法的分类器，
这里称为个人评分分类表。其中 TF-IDF 算法的应用方式描述如下：首先抽取一部分符合用135
户兴趣度和商品评分预测匹配的用户评分和评论记录作为训练集，找寻特定分数下的有效关
键词集合；然后将这些关键词组成特征向量，模拟朴素贝叶斯算法对未来用户评论进行评分
预测。
第三步，根据训练集训练出的分类器对实际数据的评分记录进行分类处理，最终得到比
较完备的代表用户的评分分值和兴趣度的个人映射表。 140
- 5 -
中国科技论文在线
第四步，最后根据兴趣度权值映射表将个人兴趣度转化用户对商品的权值。
表 1 兴趣度权值映射表
Tab. 1 The map of the interest and value degree
兴趣分词 出乎意料的好 喜欢 一般 差评 难以接受
权值 2 1 0 -1 -2
算法事务的权值的形成 145
时效度和兴趣度最终要转化为 FP-Growth 算法输入模型中事务的权值，改变过去算法不
区分事务的缺陷。
由于归一化评分为用户对单个商品的评分，而事务为一次购买/浏览等行为，包含多个
商品的评分，所以这里采用平均思想，用算术平均值表示。
另外，对事务的权值建模采用 1 2 3 4Y ax bx cx dx 的数学表达式来表示。具体参数可150
由有经验的专家按照实际业务行为进行赋值。这里暂定为 32 4
12
10 2 3
xx x
Y x ，其中 1x 代表
事务是否为购买记录，若是则为 1，否则为 0； 2x 代表事务是否为浏览记录，取值规则与 1x
类似； 3x 代表该事务的商品权值的算数平均值； 4x 代表时效性的权值。
3 FP-Growth 补充算法-基于分层和用户偏好程度的 TOP- k 算法
问题分析 155
关联规则算法的最小支持度决定总性能，这样导致大量“长尾”商品（事务数据库中出
现次数小于最小支持度的商品）被过滤，推荐系统针对“长尾”商品的推荐列表总是为空，
这与推荐结果的实用性相悖。
问题处理：基于分层和用户偏好程度的 TOP- k 算法
对于大型商务网站，由于商品种类繁多，层级复杂，很多应用在不同维度之间的数据稀160
疏性差异很大。这样会导致在原始具体商品层的数据项之间很难找到强关联规则，而在过高
的概念层发现的强关联规则可能提供了普遍意义的知识，导致推荐意义不大[11]。因此，在
对用户进行偏好度推荐前如能根据业务数据为每个分类找到一个相应的层级结构，会在一定
程度上提升算法的时间复杂度和准确率，并能减少“规则爆炸”的发生风险，其中层级可以
由负责业务的人员为每个频道进行设置或通过离线测试得到。 165
本系统以书籍为例，以书籍的情感分类为适应层级对算法进行 TOP-K 的推荐，比如喜
剧小说：相应推荐列表 1；悲剧小说：相应推荐列表 2。具体推荐场景如下，用户购买了小
说 B，若改进的 FP-Growth 推荐列表 key 中含有 B，则根据该推荐列表给用户推荐，否则进
行 TOP-K 算法补充推荐，首先分析小说情感类别，然后根据小说种类将 TOP-K 算法推荐列
表的相关结果推荐给用户。 170
定义（用户偏好程度）：根据用户的大量行为日志分析用户在每个频道的具体层次结构
（比如书籍所在第三层）上的喜好程度。比如,用户 A：探险类小说（60%），励志类小说（18%），
历史类小说（12%），其他（10%），其中括号内的数值代表用户对该类小说的喜好程度。
用户偏好程度算法描述如下：
- 6 -
中国科技论文在线
遍历数据库事务集
海量数据分片
（split）
事务(即一次购买行为)数据形式：
USERID: ITEMID1，ITEMID2，ITEMID3，„
由于在统计“USERID+ITEMID”过程，数据
集以事务为单位进行分片，不影响最终结
果。所以这种数据格式适合进行MR运算
商品特征信息表
商品特征信息表数据形式（以图书为例）：
ITEMID:分类1，分类2，author, Romance/
Fantasy/...,„„
Reduce收集操作
MAP处理
KEY:USERID
VALUE:商品类别-account
对KEY和VALUE进行重构，将原来
KEY中USERID单独设置为KEY，余下
的商品分类与后面MR1的VALUE输
出合并，格式可以自定义
Reduce收集操作 收集过程中，需要对收集结
果进行偏好度排名后再输出
MAP处理
对事务中ITEMID进行
商品类别映射
和词频统计类似，对key的
value值进行赋“1”值操作
MAP分发
Key:USERID+商品类别
Value:1
175
图 3 用户偏好度算法描述
Fig. 3 Description of User preference algorithm
用户偏好程度用于对该补充算法的推荐结果进行重排序。
Top-k 算法描述如下： 180
Top K
MR1：
根据建模（用户同类商品的行为数据），对同类数据
进行Top K 处理
根据具体商品种类找到用户自
定义的商品类别层次
查询：
对同类商品Top K 按同频道同层次进行分类，其中阅读
类商品按照图书情感分类进行划分；音乐类商品按照专辑
情感分类进行划分。
同层次商品不足，继
续补充
若同层次商品不足，用同类商品的Top K’补充（K‘为页
面要显示的推荐数）
合并同频道下的同层次商品
MR2：
根据查询结果，对Top K 中商品进行同层次划分
图 4 TOP-K 算法描述
Fig. 4 Description of TOP-K algorithm
综上所述，基于分层[12]和用户偏好程度的 TOP -K 算法是为 FP-Growth 算法不能推荐低185
频商品设计的补充算法，算法粒度要根据具体业务数据特征来确定。通过该补充算法的加入，
关联规则算法不仅提高了推荐引擎的预测覆盖率，而且增强了算法的个性化。
- 7 -
中国科技论文在线
4 算法改进后的实验性评估
测试环境概述：
数据与评价指标分析 190
1）数据选取情况：
训练集情况：商城 3 个月的下载信息，共计 左右。其中用户量为 102,330,58；下
载记录数为 71,387,845；商品数量为 51,279。测试集情况：商城一周的下载信息，其中下载
记录数为 4,759,189 条，不同商品数目共计 1483 个，用户数目为 75,102。
2）评估指标分析： 195
准确率和覆盖率的原定义的评测对象为用户，由于 FP-Growth 算法为物-物推荐，所以
在此将评价对象改为商品，且准确率和预测覆盖率均采用算术平均值。
软硬件资源配置：
硬件方面，推荐系统管理节点 1 台，Hadoop 数据节点 14 台，NOSQL 数据库节点 3 台。
其中 Hadoop 管理节点：2 个双核 CPU，16G 内存，500G 自带存储；Hadoop 数据节点：1200
个双核 CPU，2G 内存，1000G 自带存储；NOSQL 节点：1 个双核 CPU，2G 内存，1000G
自带存储；网络设备：千兆交换机。
软件方面，操作系统：Centos；Hadoop：Hadoop ；Mongo：MongoDB Linux 。
实验结果及分析
由图 5 至图 6 可知，从算法改进前后准确率的商品分布情况对比看，商品推荐准确率明205
显提升，经计算，平均准确率从 %上升至 %。这说明兴趣度和时效度的加入有效
提升了推荐结果的准确度，从而证实了兴趣度和时效度的加入在一定程度上提升了推荐引擎
的性能。
根据图 7 至图 8 分析可知，算法的预测覆盖率大幅度提升，每个种类的预测覆盖率均达
到 95%以上。理论上，基于分层和用户偏好程度的 TOP- K 算法可以使算法进行完全商品匹210
配，但是实际数据中存在非卖商品和敏感规则规避等人为干预，导致少量商品不能进入推荐
列表。预测覆盖率的提高，弥补了 FP-Growth 算法在“长尾”商品推荐方面的缺陷，使算法
更加符合现实推荐场景。
(1), 引入时效度和兴趣度概念的 FP-Growth 算法改进前后的商品分布情况如图 5 至图 6，
评估指标为推荐准确率。 215
FP-Growth 算法改进前： FP-Growth 算法改进后：
图 5 准确率的商品分布情况
Fig. 5 Distribution of accuracy rate in items
图 6 准确率的商品分布情况
Fig. 6 Distribution of accuracy rate in items
- 8 -
中国科技论文在线
(2）,基于分层和用户偏好度的 FP-Growth 算法改进前后对比，评估指标为商品类别下的预
测覆盖率。
FP-Growth 算法改进前： FP-Growth 算法改进后：
图 7 覆盖率的商品分布情况
Fig. 7 Distribution of coverage rate in items
图 8 覆盖率的商品分布情况
Fig. 8 Distribution of coverage rate in items
5 结论 220
本文基于 FP-Growth 算法和某大型商务网站的具体业务，对事务数据库中的不同事务根
据时效度和兴趣度赋予不同权值，使推荐算法更加符合实际推荐场景，提高了算法的准确度
和事务个性化。同时，针对 FP-Growth 的“长尾”推荐缺失，本文提出了基于分层和用户偏
好度的 TOP-K 算法，有效提高了系统的预测覆盖率和用户个性化。实验数据表明，通过上
述两种策略的加入，改进后的 FP-Growth 算法更加适用于商务推荐这一应用场景，有利于用225
户对网站的忠诚度和活跃度的提高。
当然，推荐系统的评价指标除准确率和覆盖率外，还包括多样性，新颖性，召回率[10]等，
如要全面提升推荐系统的性能，还需借助其他改进方案。
[参考文献] (References)
[1] 马刚. 关联规则挖掘在电子商务中的研究与应用[D]. 上海：上海交通大学，2008. 230
[2] 罗建，李艳梅. FP-Growth 算法改进研究及在电子商务中的应用[J]. 西华师范大学学报，2010，31(3)：
309-313.
[3] Han J, Pei J, Yin Y. Mining frequent patterns without candidate generation[J]. SIGMOD Record, 2000, 29(2):
1-12.
[4] Han J, Pei J, Yin Y, et al. Mining frequent patterns without candidate generation: A frequent-pattern tree 235
approach[J]. Data mining and knowledge discovery, 2004, 8(1): 53-87.
[5] Li H, Wang Y, Zhang D, et al. Pfp: parallel fp-growth for query recommendation[A]. ACM. Proceedings of the
2008 ACM conference on Recommender systems[C]. New York: SIGMOD Record, 2008. 107-114.
[6] Park J S, Chen M S, Yu P S. An effective hash-based algorithm for mining association rules[M]. New York:
ACM NY, 1995. 240
[7] , , . Mining Association Rules between Sets of Items in Very Large
Databases[J]. SIGMOD Record, 1993, 1(5): 207-216.
[8] Zhu Y X, Lu L Y. Evaluation metrics for recommender systems[J]. Journal of University of Electronic Science
and Technology of China, 2012, 41(2): 163-175.
[9] Averell L, Heathcote A. The form of the forgetting curve and the fate of memories[J]. Journal of Mathematical 245
Psychology, 2011, 55(1): 25-35.
[10] 项亮. 推荐系统实践[M]. 北京：人民邮电出版社，2012.
[11] 王娟. 基于 FP-Growth 算法改进的多层次关联规则挖掘算法[J]. 电脑与知识技术，2008，4(7)：1994-1996.
[12] 毛宇星，陈彤兵，施伯乐. 一种高效的多层和概化关联规则挖掘方法[J]. 软件学报，2011，22(12)：
2965-2980. 250
