第3章 关联规则与推荐算法
关联规则和推荐算法都可用来为客户推荐商品等信息。关联规则是根据商品之间的
关联性推荐,其算法复杂度较高,适合离线计算,推荐算法根据商品之间的相似性或用户
之间的相似性推荐,其算法复杂度低,适合在线计算。
3.1 关联规则挖掘
关联规则(associationrules)用来反映一个事务与其他事务之间的相互依存性和关联
性,是数据挖掘的一项重要技术,用于从大量数据中挖掘有价值的数据项之间的相关
关系。关
联规则挖掘源于购物篮分析,即在超市中用来分析顾客所购买的商品之间的关联
性,这有助于决定超市商品的摆放和商品的捆绑销售策略。
3.1.1 基本概念
关联规则挖掘用来发现数据集中项集之间有趣的关联联系。如果两项或多项之间存
在关联,就可以根据其中一项推荐相关联的另一项。关联规则的一般表现为蕴含式规则
形式:X .Y。X 称为关联规则的前提或先导条件,Y 称为关联规则的结果或后继。定义
和表示关联规则需要引入置信度(confidence)和支持度(support)两个指标。例如: 
buys(x, "diapers")==>buys(x, "beers") [0.5%, 60%] 
表示购买尿布的客户也会购买啤酒,该规则的支持度为0.5%,置信度为60%。该规则也
可简写为:diapers.beers[0.5%,60%]。又如: 
major(x, "CS") ^ takes(x, "DB")==>grade(x, "A") [1%, 75%] 
表示专业为计算机选修数据库的学生成绩得A 的支持度为1%,置信度为75%。该规则
也可简写为:CS^DB.A[1%,75%]。
关联规则中的基本概念如下。
1)项与项集
数据库中不可分割的最小信息单位(即记录)称为项(或项目),用符号i 表示,项的集
合称为项集。设集合I={i1,i2,…,ik}为项集,I 中项的个数为k,则集合I 称为k-项集。
例如,集合{啤酒,尿布,奶粉}是一个3-项集,而奶粉就是一个项。

2)事务

每一个事务都是一个项集。设I={i1,i2,…,
k 
}

i是由数据库中所有项构成的全集, 
则每一个事务t对应的项集都是
I 
的子集。事务数据库T={t2,…,
n 
}是由一系列

t1,t

具有唯一标识的(i) 事务组成的集合。例如,如果把超市中的所有商品看成I,则每个顾客每

张小票中的商品集合就是一个事务,很多顾客的购物小票就构成一个事务数据库。

3)项集的频数

包含某个项集的事务在事务数据库中出现的次数称为项集的频数。例如,事务数据

库中有且仅有3个事务t1={啤酒,奶粉}、t2={啤酒,尿布,奶粉,面包}、t3={啤酒,尿

布,奶粉}, 它们都包含了项集I1={啤酒,奶粉}, 则称项集I1 的频数为3,项集的频数代

表了支持度计数。

4)关联规则

关联规则是形如
X 
.
Y 
的蕴含式,其中
X 
、
Y 
分别是项集
I 
的真子集,并且
X 
∩Y= 

.,
X 
称为规则的前提,
Y 
中的

Y 
称为规则的结果。关联规则反映了
X 
中的项目出现时,

项目也跟着出现的规律。

5)支持度

关联规则的支持度是事务集中同时包含项
X 
和
Y 
的事务数与事务集中总事务数的
比值。它反映了
X 
和
Y 
中所包含的项在事务集中同时出现的概率,记为support(
X 
. 
Y), 即
support(
X 
.Y)=support(
X 
∪Y)=P(XY) (3-1)

6)置信度
关联规则的置信度是事务集中同时包含
X 
和
Y 
的事务数与包含
X 
的事务数的比
值,记为confidence(
X 
.Y)。置信度反映了包含
X 
的事务中出现
Y 
的条件概率,即

nice(support(
X 
∪Y) Y|X)(-2)

cofdenX 
.Y)=X) P(3

7)最小支持度与最小置信度
support(

通常,支持度与置信度必须都大于(或等于)人为设置的阈值,才表明项与项之间存在
关联。支持度的阈值称为最小支持度(minsup), 它描述了关联规则的最低重要程度;置
信度的阈值称为最小置信度(min_conf), 它反(_) 映了关联规则必须满足的最小可靠性。

8)强关联规则

如果某条关联规则
X 
.
Y 
的支持度大于或等于最小支持度,置信度大于或等于最小

置信度,则称关联规则X.
Y 
为强关联规则,否则称
X 
.
Y 
为弱关联规则。只有强关联规

则才有实际意义,因此通常所说的关联规则都指强关联规则。

9)频繁项集
X,的支持度spprX.如果某个项集的支持度大于或等于最小支持度,即项集{Y} uot(
Y)≥minsup,则称该项集为频繁项集。求频繁项集是求强关联规则的第一步。
支持度(_) 和置信度的示意图如图3-1所示。其中,若
T 
代表事务数据库,则
A 
的支持
度就是A/T,A.
C 
或C.
A 
的支持度为(A∩C)/T,A.
C 
的置信度为(A∩C)/A。
【例3-1】现有事务数据库
T 
如表3-1所示,设最小支持度为50%,最小可信度为

68 


图3-1 支持度和置信度的示意图
50%,求所有频繁项集(2项集以上)和强关联规则。

表3-
1 
事务数据库
T 

交易ID 1001 1002 1003 1004 
购买的商品A,B,
C 
A,
D 
A,
C 
B,E,
F 

解:事务数据库
T 
中共4个事务,项集{A,C}在所有事务中出现了2次,因此{A,C}
的支持度为2/4=50%,不小于最小支持度,其余项集(2项集以上)均只出现过1次,故项
集{A,C}为
T 
中唯一的频繁项集。

在频繁项集的基础上求强关联规则,项集{A,C}可以构成的关联规则有2条,即
A.
C 
和C.
A 
confidence(A.C)=support(
A 
∪C)/support(A)=(2/4)/(3/4)=2/3=66% 
confidence(C.A)=support(
C 
∪A)/support(C)=2/2=100% 

因为A.
C 
和C.
A 
的置信度均大于最小置信度,因此它们都是强关联规则。
说明: 

①在同一个事务数据库中,所有项集的支持度的分母都相同,例如本例为4。因此, 
在求置信度时,两个项集支持度的分母可以约去,故可直接用项集的频数相除求置信度。
②为什么用支持度和置信度就能表示关联性呢,这是因为: 
假设一个超市一天有10000 条销售记录,如果100 条销售记录中都同时销售了
A 
商
品和
C 
商品,当然可以认为商品
A 
和
C 
之间具有某种销售关联性,这就是支持度。但是, 
如果另外900 条销售记录里也销售了
A 
商品,但却没出现
C 
商品,这时似乎就不能认为
买
A 
商品的顾客一定也会买
C 
商品,这就是置信度,因此商品之间的关联性与支持度和
置信度都有关系。

【练习3-1】已知总交易笔数(事务数)为1000,其中包含某些商品的交易数如下。
包含“牛奶”:50,包含“面包”:80,包含“鸡蛋”:20; 
包含“牛奶”和“面包”:15,包含“鸡蛋”和“面包”:10,包含“牛奶”和“鸡蛋”:10,包含

“牛奶”“鸡蛋”“面包”:5。
求“牛奶和面包”的支持度,“牛奶、面包和鸡蛋”的支持度;
“牛奶.面包”的置信度,“面包.牛奶”的置信度; 

69 


“牛奶和面包.鸡蛋”的置信度,“鸡蛋.牛奶和面包”的置信度。

3.1.2 
Apriori算法
关联规则挖掘可分解为两个子问题:第一步是找出事务数据库中所有大于或等于用

户指定的最小支持度的数据项集,即频繁项集;第二步是利用频繁项集生成所需要的关联

规则,方法是根据用户设定的最小置信度进行取舍,从而得到强关联规则。识别或发现所

有频繁项集是关联规则发现算法的核心。

1993 年,Agrawal等首先提出关联规则概念,1994 年,又提出著名的Apriori算法,之
后该算法成为关联规则挖掘的经典算法。

1.Apriori算法的原理和实例
Apriori算法的基本思想是:通过对事务数据库的多次扫描计算项集的支持度,发现
所有的频繁项集,从而生成关联规则。Apriori算法对数据集进行多次扫描。第一次扫描
项集的集合L1, k>1)次扫描首先利用第k

得到频繁1-第k(1次扫描的结果Lk-1产生

候选k-项集的集合Ck 
,然后在扫描的过程中确定Ck 
中元素的支持度,最后在每一次扫描

结束时计算频繁k-项集的集合Lk 
,算法当候选k-项集的集合Ck 
为空时结束。

可见,Apriori算法是通过频繁1-项集求频繁2-项集,再通过频繁2-项集生成频繁
3-项集,如此迭代。这样做的理论依据是:频繁项集的任何子集也一定是频繁的;反之, 
任何一个项集是非频繁的,那么它的超集也一定不是频繁项集。例如,如果{A,C}不是
频繁项集,那么{A,B,C}也一定不会是频繁项集。

【例3-2】现有A、B、C、D、
E 
5种商品的交易记录表(见表3-2), 试找出3种商品的
k=insup≥50%, incon

关联销售情况(3), 设最小支持度m_最小置信度m_f≥75% 。

表3-
2 
交易记录表

交易号101 102 103 104 
商品代码A,C,
D 
B,C,
E 
A,B,C,
E 
B,
E 

解:因为要找出3种商品的关联销售情况,所以要找出所有的频繁3-项集。那么,必
须先找频繁1-项集,再找频繁2-项集。

(1)首先,第1次扫描数据库,并计算每个1-项集的支持度,得到候选1-项集C1。在
候选1-项集中去掉支持度小于最小支持度的项集,得到频繁1-项集,如图3-2所示。
图3-2 从候选1-项集中找频繁1-项集

70 


71 
(2)第2次扫描,为了得到候选2-项集,算法使用C2=L1∞L1,即把L1 中的4个1 
项集两两组合,得到6个候选2-项集,再在候选2-项集中去掉不满足最小支持度的项集, 
得到频繁2-项集,如图3-3所示。
图3-3 从候选2-项集找频繁2-项集
(3)第3次扫描,为了得到候选3-项集,算法使用C3=L2∞L2,即把L2 中的4个2 
项集两两组合,产生的详细项集列表如下。
①C3=L2∞L2={{A ,B,C},{A ,B,C,E},{A ,C,E},{B,C,E}}。
② 使用Apriori剪枝算法,因为{A ,B,C,E}是4项集,故从C3 中删除。另外,频繁
项集的所有子集也应该是频繁项集,若某个候选3-项集的子集中存在非频繁项集,则应
该将该候选3-项集删除,这称为Apriori剪枝。在C3 中,候选3-项集{A ,C,E }的子集
{A ,E}是非频繁项集,故应将{A ,C,E}删除。{A ,B,C}的子集{A ,B}也是非频繁项集, 
故应将{A ,B,C}删除,最终得到C3 为{{B,C,E}}。
③ 在候选3-项集C3 中去掉不满足最小支持度的项集,得到频繁3-项集L3,如图3-4 
所示。
图3-4 从频繁2-项集得到候选3-项集的过程
(4)得到频繁3-项集后,就可以找出3种商品的关联销售情况,方法是:找出频繁3- 
项集{B,C,E}的所有真子集,并计算这些真子集的支持度。再用真子集的支持度除以
L3 的支持度,就得到关联规则的置信度,置信度大于min_conf的就是强关联规则,如
图3-5所示。
所以,最终得到的强关联规则有2条,即B ^C .E [50%,100%]、C ^E .B [50%, 
100%],表示购买了商品B、C 的顾客可能会购买商品E,购买了商品C、E 的顾客可能会
购买商品B。

72 
图3-5 从频繁3-项集中找强关联规则
2.Apriori算法的实现
Apriori算法的主要步骤如下。
(1)扫描整个事务数据库,产生候选1-项集的集合C1。
(2)根据最小支持度,由候选1-项集的集合C1 产生频繁1-项集的集合L1。
(3)设k 表示k-项集,对k>1,重复置信步骤(4)~步骤(6)。
(4)由Lk 执行连接和剪枝操作,产生候选(k+1)-项集的集合Ck+1。
(5)根据最小支持度,由候选(k+1)-项集的集合Ck+1,产生频繁(k+1)-项集的集
合Lk+1。
(6)若Lk+1≠.,则k=k+1,跳往步骤(4);否则转到步骤(7)。
(7)根据最小置信度,由频繁项集产生强关联规则,算法结束。
Apriori算法求频繁项集的伪代码描述如下。
输入:事务数据库D ,最小支持度min_sup。
输出:D 中的频繁项集L(k)。 
L1=find_frequent_1-itemsets(D); //找出频繁1-项集
for(k=2;Lk-1 ≠.;k++) { 
Ck =apriori_gen(Lk-1); //产生候选k-项集 
for each 事务t in D { //扫描事务数据库 
Ct =subset(Ck, t); //得到t 的子集 
for each candidate c in Ct 
c.count++; 
} 
//返回候选项集中不小于最小支持度的项集 
Lk ={c∈Ck | c.count≥min_sup} 
}r
eturn L=所有频繁项集Lk 的并集; 
在该算法中,候选项集的生成是整个算法的核心,是通过apriori_gen()函数的连接
和剪枝两步生成的。apriori_gen()函数的参数为Lk-1,即所有频繁(k-1)-项集的集合。
它返回所有频繁k-项集的一个超集(superset)。方法是:首先,在连接步,将Lk-1与Lk-1 
自连接,获得一个k 阶候选项集Ck ,条件p[k-1]<q[k-1]保证不会出现相同的扩展项

73 
集,经过合并运算,Ck .Lk 。apriori_gen()函数的伪代码如下。 
Procedure apriori_gen(Lk-1) 
for each 项集p in Lk-1 
for each 项集q in Lk-1 
if((p[1]=q[1])&& (p[2]=q[2])&&…&& (p[k-2]=q[k-2])&& (p[k-1]< 
q[k-1])) { 
c=q 连接p 
//若k-1 项集中已经存在子集c,则进行剪枝 
if has_infrequent_subset(c, Lk-1) then 
delete c; //剪枝步,删除非频繁候选项集 
else add c to Ck 
} 
return Ck; 
其中,在剪枝步,对于所有项集c∈Ck ,若它的某项(k-1)-项集不在Lk-1中,则将该项集
c 删除。检测是否存在非频繁项集的伪代码如下。 
Procedure has_infrequent_subset(c, Lk-1) //检测是否存在非频繁项集 
for each(k-1)-subset s of c 
if(s.Lk-1) {return true;} 
return false; 
例如,假设频繁2-项集L2={{A ,B},{A ,C},{A ,E},{B,C},{B,D },{B,E}},则
得到候选3-项集的连接和剪枝过程如下。
连接步:L2 按照上面的步骤自连接得到{{A,B,C},{A,B,E},{A,C,E},{B,C,D}, 
{B,C,E},{B,D ,E}}。
剪枝步:{A ,B,C}的所有2项子集{A ,B},{A ,C},{B,C}都是L2 中的元素,因此, 
保留{A ,B,C}在C3 中。{B,C,E}的2项子集中的{C,E }不是L2 中的元素,因此,在
C3 中删除{B,C,E},最终剪枝后的结果是C3={{A ,B,C},{A ,B,E}}。
3.Apriori算法的优缺点及应用
Apriori算法的缺点主要表现在计算性能上,其计算开销耗费在两方面:一是会产生
巨大的候选集Ck ,算法采用自连接的方式产生候选集,例如,104 个频繁1-项集i 将生成
107个候选2-项集,如果要找尺寸为100的频繁模式,如{a1,a2,…,a100},则必须先产生
2100≈1030个候选集。显然,这将耗费巨大的内存空间。二是需要多次扫描事务数据库, 
每次产生候选集都要扫描一次数据库,如果最长的模式是n,则需要(n+1)次数据库
扫描。
Apriori算法的优点有:它是一个迭代算法;数据采用水平组织方式;可采用Apriori 
优化方法;适合事务数据库的关联规则挖掘;适合稀疏数据集。
Apriori算法广泛应用于商业,以及消费市场价格分析中,它能很快地求出各种产品

74 
之间的价格关系,以及它们之间的影响。通过数据挖掘,市场商人可以瞄准目标客户,采
用最新信息、特殊的市场推广活动或其他一些特殊的信息手段,极大地减少广告预算和增
加收入。百货商场、超市和一些零售店也在进行数据挖掘,以便猜测这些年顾客的消费
习惯。
Apriori算法也应用于网络安全领域,如网络入侵检测技术中。早期中大型的计算机
系统中都收集审计信息来建立跟踪档,这些审计跟踪的目的多是为了性能测试或计费,因
此对攻击检测提供的有用信息比较少。Apriori算法通过模式的学习和训练可以发现网
络用户的异常行为模式,使网络入侵检测系统可以快速发现用户的行为模式,能够快速锁
定攻击者,提高了基于关联规则的入侵检测系统的检测性。
3.1.3 Apriori算法的程序实现
由于Sklearn框架中没有提供关联规则分析的功能,因此没有Apriori和Fp-growth 
算法,但是其他一些Python工具包中提供了Apriori算法,可以通过https://pypi.org搜
索Python的工具包。本节选择efficient-apriori1.1.1,将其安装文件efficient_apriori- 
1.1.1-py3-none-any.whl下载下来,然后执行“pipinstall安装文件路径和文件名”命令即
完成安装。
efficient-apriori模块提供了apriori类,该类的构造函数有3个参数,分别是数据集、
最小支持度和最小置信度,输出是所有的频繁项集和关联规则。
【程序3-1】 使用Apriori算法挖掘事务数据集data的频繁项集,并输出关联规则。 
from efficient_apriori import apriori #导入模块 
#设置事务数据集data 
data=[('牛奶','面包','香蕉'), 
('可乐','面包', '香蕉', '啤酒'), 
('牛奶','香蕉', '啤酒', '鸡蛋'), 
('面包', '牛奶', '香蕉', '啤酒'), 
('面包', '牛奶', '香蕉', '可乐')] 
#挖掘频繁项集和频繁规则
itemsets, rules=apriori(data, min_support=0.5, min_confidence=1) 
print(itemsets) #输出频繁项集
print(rules) #输出关联规则
该程序的输出结果如下。 
{1: {('香蕉',): 5, ('面包',): 4, ('牛奶',): 4, ('啤酒',): 3}, 
2: {('牛奶', '面包'): 3, ('牛奶', '香蕉'): 4, ('面包', '香蕉'): 4, ('啤酒', 
'香蕉'): 3}, 
3: {('牛奶', '面包', '香蕉'): 3}} 
[{牛奶} ->{香蕉}, {面包} ->{香蕉}, {啤酒} ->{香蕉}, {牛奶, 面包} ->{香蕉}] 
其中,“1:”表示频繁1-项集,“('香蕉',):5”表示香蕉的支持度计数为5。

3.4 
FPGoth算法
1.-rw

Apriori算法由于会重复扫描数据库,并且产生巨大的候选集,导致其算法性能较差。
2000年,由韩嘉炜等提出的一种不产生候选项集的算法,称为FP-Growth(Frequent 
PaternGrowth,频繁模式树增长)算法,它采用分而治之的思想,将数据库中的频繁项集
压缩到一棵频繁模式树中,同时保持项集之间的关联关系。然后,将这些压缩后的频繁模
式树分成一些条件子树,每个条件子树对应一个频繁项,从而获得频繁项集,最后挖掘
出关联规则。该算法总共需对数据库进行两次扫描,因此能显著加快发现频繁项集的

速度。
h算法的主要任务是将数据集存储在FPe(频繁模式树)中,通过FP

FP-Growt-Tr-Tre 
可以高效地发现频繁项集,执行速度通常比Apriori算法快两个数量级。FP-Growth算
法只给出了高效地发现频繁项集的方法,但不能用于发现关联规则。

1.FP-Growth算法的原理及实例
FP-Growth算法的基本思路如下。

(1)遍历一次数据库,找出频繁1-项集,按递减顺序排序。
(2)建立FP-Tre
。
(3)利用FP-Tre 
为频繁1-项集的每一项构造条件FP-Tre
。
(4)得到频繁项集。
【例3-3】表3-3是一个事务数据库,试利用FP-Growth算法找出所有含2项以上
的频繁项集(设最小支持度计数为2)。

表3-
3 
事务数据库

交易号商品代码交易号商品代码
1 A,B,
E 
6 B,
C 
2 B,
D 
7 A,
C 
3 B,
C 
8 A,B,C,
E 
4 A,B,
D 
9 A,B,
C 
5 A,
C 

解:(1)扫描事务数据库得到频繁1-项集,如表3-4所示,这是第1次扫描数据库。
表3-
4 
频繁1-项集

A B C D E 
6 7 6 2 2 

(2)对频繁1-项集按项集的频数从大到小排序,得到排序后的频繁1-项集,如表3-5 
所示。
75 


表3-
5 
排序后的频繁1-项集

B A C D E 
7 6 6 2 2 

(3)按频繁1-项集支持度递减的顺序重新排序事务数据库中的项,如表3-6所示。
表3-
6 
按支持度计数递减排序的事务数据库

交易号商品代码交易号商品代码
1 B,A,
E 
6 B,
C 
2 B,
D 
7 A,
C 
3 B,
C 
8 B,A,C,
E 
4 B,A,
D 
9 B,A,
C 
5 A,
C 

(4)创建FP-Tre 
的根结点和频繁项目表,FP-Tre 
的根结点总是Nul
。
(5)向FP-Tre 
中加入每个事务,这是第2次扫描数据库。例如,经排序后的第1个
事务是{B,A,E},则按照该排序顺序将B、A、
E 
依次添加到FP-Tre 
的一个分支中,并
将计数值设为1,如图3-6所示。为了方便遍历,FP-Growth算法还需要一个称为结点头
(Node-head)指针表的数据结构,这是一个用来记录各个元素项的总出现次数的数组,再附
带一个指针指向FP-Tre 
中该元素项的第一个结点,这样每个元素项都构成一条单链表。
图3-6 向FP-Tre 
中加入第1个事务

(6)然后依次加入第2个事务(见3-7)和第3个事务(见图3-8),如果FP-Tre 
中已
经有该事务,则将该事务的计数加1。
图3-7 加入第2个事务

76 


77 
图3-8 加入第3个事务
(7)按照上述方法加入剩下的第4~9个事务。最终生成的FP-Tree如图3-9所示。
图3-9 最终生成的FP-Tree 
在FP-Tree建立好之后,只要寻找结点的条件模式基(conditionalpatternbase),就
能快速得到频繁项集。条件模式基是以所查找元素项为结尾的路径集合。每一条路径其
实都是一条前缀路径。
例如,要找包含E 的频繁项集,方法是:从元素E 向上找它的前缀路径,图3-9中有
2个结点E,因此E 的前缀路径有2条。条件模式基的计数为E 的计数值(本例均为1)。
得到E 的条件模式基为 
<(B,A):1>,<(B,A,C):1> 
将条件模式基中结点的出现次数合并,得到包含E 的频繁项集为 
{{B,E:2},{A,E:2},{A,B,E:2}} 
同理,对于元素C,得到的条件模式基为 
<(B,A):2>,<B:2>,<A:2> 
得到C 的频繁项集为 
{{B,C:4},{A,C:4},{A,B,C:2}}

其他结点的频繁项集也是按上述步骤生成的,从而得到所有频繁项集,再根据频繁项
集生成关联规则即可完成关联规则的挖掘。

2.FP-Growth算法的程序实现
FP-Growth算法的程序实现步骤如下。

(1)建立头指针:遍历数据集,找出所有的频繁一项集,构成头指针,并根据支持度
对一项集排序。
(2)建立FP-Tre:定义根结点,遍历数据集,对于每条记录,根据头指针的顺序向树
中添加结点。如果记录中上一个结点的子结点中当前结点已存在,则结点支持度+记录
支持度;如果结点不存在,则在上一结点中添加当前子结点,并设置支持度为记录支持度。
(3)查找条件模式基:根据头指针查找每个一项集的前缀路径,作为条件模式基,且
当前一项集作为频繁项基。
(4)查找频繁项:深度遍历,重复步骤(3)。每次查找完成后,将每一层遍历的频繁项集
+新的头指针中的频繁一项集作为频繁项,重复此步骤,直到FP-Tre 
的头指针为空。
下面给出FP-Growth算法的描述。
输入:事务集D、最小支持度。
输出:FP-Tre
、头指针表。
算法步骤如下。
(1)遍历事务集D,统计各元素项出现的次数,创建头指针表。
(2)移除头指针表中不满足最小支持度的元素项。
(3)第二次遍历数据集,创建FP-Tre
。对每个事务集中的项集。
①初始化空FP-Tre; 
②对每个项集进行过滤和重排序; 
③使用这个项集更新FP-Tre,从FP-Tre 
的根结点开始: 
● 如果当前项集的第一个元素项存在于FP-Tre 
当前结点的子结点中,则更新这个
子结点的计数值。
否则,创建新的子结点,更新头指针表。
●

● 对当前项集的其余元素项和当前元素项的对应子结点递归③的过程。
3.FP-Growth算法的特点
FP-Growth算法的优点包括不生成候选集,不用候选测试;使用紧缩的数据结构;避
免重复数据库扫描;基本操作是计数和建立FP-Tre
。缺点是:实现比较困难,在某些数
据集上性能会下降。

3.推荐系统及算法
2 

推荐系统在互联网领域有非常广泛的应用,推荐可以满足用户非明确的潜在需求,而
搜索用来满足用户主动表达的需求。可见,推荐是搜索功能的重要补充。据统计,在电子

78 


商务网站中,有35%的销售来源推荐。在视频播放网站中,有75%的观看来自推荐。在
交友网站中,推荐系统常根据好友的爱好,向用户推荐他可能感兴趣的人。在移动App
中,经常根据用户所处的地理位置推荐附近的景点、美食和住宿等信息。可见,推荐在互
联网领域无处不在,这是因为互联网上信息过载,用户常被湮没在信息中,而对自己的实
际需求不明确;其次,推荐很强地依赖于用户行为,互联网上很难获取用户的真实信息和
喜好,只能通过捕获用户的行为获取,如记录用户的浏览历史,点击、收藏、搜索等行为,根
据这些行为衡量用户的兴趣。

推荐系统是通过用户与产品之间的二元关系,利用已有的选择过程或相似性关系挖
掘每个用户潜在的感兴趣对象,进而进行个性化推荐,其本质是信息过滤。一个完整的推
荐系统由3个模块组成:收集用户信息的行为记录模块、分析用户喜好的模型分析模块
和推荐算法模块。其中,协同过滤推荐算法是推荐系统最常用的算法,它能分析用户的喜
好,并根据推荐算法进行推荐。

2.协同过滤推荐算法
3.1 

协同过滤(colaborativefiltering,CF)推荐算法是推荐系统中主流的推荐算法。它包
括协同和过滤两个操作。所谓协同,就是利用群体的行为做决策(推荐),而过滤是从可行
的决策(推荐)方案(标的物)中将用户喜欢的方案找(过滤)出来。

1.两种协同过滤推荐算法
协同过滤推荐分为基于用户的协同过滤方法(user-basedCF)和基于物品的协同过
滤方法(dCF )。

item-base

基于用户的协同过滤基本假设为:为了给用户推荐感兴趣的内容,可通过找到与该
用户偏好相似的其他用户,并将他们感兴趣的内容推荐给该用户。举例来说,如果A、
B 
两个用户都购买了x、y、z三本图书,并且给出了5星好评。那么,
A 
和
B 
就属于相似的
用户。可以将
A 
看过的图书w推荐给用户B。

基于物品的协同过滤基本假设为:如果一个用户对某个物品感兴趣,则将与该物品
相似的其他物品推荐给该用户。物品与物品之间的相似性根据物品是否被许多用户同时
购买来评判,而不会考虑物品本身的属性。例如,有很多购买iPhone手机的用户也同时
购买了iPad,则说明iPhone和iPad这两种物品具有相似性,可向购买了iPhone的用户
推荐iPad。

2.基于物品的协同过滤推荐
该算法通过用户对不同物品的评分评测物品之间的相似性,基于物品之间的相似性
做出推荐。这里不是利用物品自身属性计算物品之间的相似度,而是通过分析用户的行
为记录计算物品之间的相似度。具体而言,通过计算不同用户对不同物品的评分获得物
品间的关系,基于物品间的关系对用户进行相似物品的推荐,这里的评分代表用户对商品
的态度和偏好。简单来说,如图3-10所示,用户User1和User2都购买了Product1和

79 

Product3,并给出了5星好评,说明商品Product1 和Product3 比较相似,那么,当用
户
User3 也购买了商品Product3 时,可以推断他也有购买Product1 的潜在需求,因此
可


向他推荐Product1 。


图3-10 基于物品的协同过滤推荐算法示意图

基于物品的协同过滤算法的实现步骤如下。

(1)计数物品之间的相似度。在协同过滤算法中,相似度是采用余弦相似度衡量的, 
余弦相似度表征了两个向量之间夹角的相似度,即如果两个向量的方向相似,它们的余弦
相似度值就较大(接近于1)。
采用余弦相似度,是因为两个用户购买或评价的商品种类可能各不相同,如果采用距
离的方法度量,则距离的某些维度将没有值,距离计算将无法进行。其次,每个用户的评
分宽严程度不同,有些用户的评分可能总体偏低,此时如果计算距离将差距较大,而计算
向量的方向(余弦相似度)则差距很小。

余弦相似度的计算方法如下。
i 
xxixj1,xj

假设两个对象v和vj 
对应的向量分别为X=(i2,…,)和Y=(xj2,…,), 

i1,x

n n 
则余弦相似度sim(vi,vj)的计算公式为
n 

Σxik 
×xjk 

k=1

X

·

Y

sim(vj)

vi,
= 

(3-3)

Y
X


= 

nn 

x2 x2

Σik × 
Σjk 

k=1 k=1 


wij= 
|
N 
(i)|·|
N ( 
(3-4) 

设xik 
和xjk 
的取值只能是0或1, 
则式(3-3)可转换成如下形式
:
|
N 
(j)
|


i)∩
N 
(

例如,对于物品a、b、、
d 
和用户A、B、C、设Nj(
)
| 
表示对物品
a 
感兴趣
b)
cA,D} 
D, a)={A,B} 
C 
和D, 

a)∩
N 
(|{A,B}∩{A,C,wab==
= 
|
N 
(·|
N 
(2×36 

的用户有
A 
和B,
N 
(={C,表示对物品
b 
感兴趣的用户有A、各用户对
各物品的感兴趣程度均为1,则物品a、
b 
之间的相似度为
|
N 
(b)|D}
| 
1 

a)|b)
| 

提示:只有当感兴趣程度只能为1或0时,才能使用简化式(3-4)计算余弦相似度, 
否则必须使用完整式(3-3)计算。

80 


然后根据wi。(j) 的大小选出与物品
i 
最相似的
K 
个物品(
K 
的大小视情况而定), 求这
K 
个物品的集合

(2)根据物品的相似度和用户的历史行为给用户生成推荐列表。计算用户
u 
对物品
j 
的感兴趣程度puj 
的公式如下: 
wir(3-5)
puj = 
Σ juj 

u) 
i∈SjK 
∩N(u) 
表示与物品
j 
最相似的
K 
个物

其中,
N 
(表示用户
u 
曾经有过正反馈的物品集合;SjK 
品的集合;u用正整数表示)。通过设定阈值决定是

r表示用户
u 
对物品
j 
的感兴趣程度
(
否推荐物品,从(j) 而生成推荐列表
。
例3-对于物品ace 
和用户A、D, a)A,b)A,


【4】、b、、d、B、C、设N(={B},N(={C}, 
N 
(c)={B},
N 
(={D},
N 
(={D}。各用户对各物品的感兴趣程度均为
D,d)A,e)C,
1,推荐阈值为0.

9。试使用基于物品的协同过滤算法给用户
A 
推荐物品。
解:根据式(3-4)计算物品之间的相似度,有
wab 
=1/2,wac 
=1/2,wa=1/2,wae 
=0/2=0 
取
K 
=3,而用户
A 
对物品a、b、
d 
感兴趣(K(d) =3), 剩余可推荐物品只有
c 
和e。先看

c 
和a、b、
d 
的相似度,wac=wcd 
=1/2,wbc 
=0,则pAc=1/2×1+0×1+1/2×1=1。
又因为wbe 
=wde=1/2,wae=0,所以pAe 
=1/2×1+0×1+1/2×1=1。
由于阈值为0.因此物品
c 
和
e 
均可推荐给用户A。

9, 

3. 
基于用户的协同过滤推荐
该算法通过不同用户对物品的评分评测用户之间的相似性,然后基于用户之间的相
似性做出推荐。具体而言,基于用户的协同过滤算法是通过用户的历史行为数据,发现用
户对物品的喜好(如商品购买、收藏、内容评论或分享), 并对这些喜好进行度量和打分。
根据不同用户对相同商品或内容的态度和偏好程度计算用户之间的关系,在有相同喜好
的用户间进行商品推荐。简单地说,如图3-11 所示,用户User1 和User3 都购买了
Product2 和Product3,并给出了5星好评,那么,User1 和User3 就属于同一类用户, 
可以将User1 买过的物品Product1 和Product4 推荐给User3 。


图3-11 基于用户的协同过滤推荐算法示意图
【例3-5】对于用户A、B、C、
D 
和物品a、b、c、d、e,设
N 
(A)a,d},
N 
(B)=

={b,

81 


{c},e},}。各用户对各物品的感兴趣程度均为1,推荐阈
a,
N 
(={
N 
(D)={d,
值为0.
C)b,c,
e 

7。试使用基于用户的协同过滤推荐算法给用户
A 
推荐物品
。
解:根据式(3-4)计算用户之间的相似度,
有


111 

wAB = 
6,wAC = 
6,wAD = 
3 

和e。
取
K 
=3,因为用户
A 
对物品a、b、
d 
感兴趣(
K 
=3), 所以剩余可推荐物品只有
c 

因为用户
B 
和用户
D 
对商品
c 
感兴趣,而用户
A 
和用户B、用户
D 
之间有相似性, 
故用户
A 
对物品
c 
的感兴趣程度为

× 
3×1≈0.
因为用户
C 
和用户
D 
对商品
c 
感兴趣,而用户
6A 
和用户C、用户
D 
之间有相似性, 
故用户
A 
对物品
e 
的感兴趣程度为

pAc=wAB 
·rAc 
+wAD 
·rAc= 
1 1 742 

6
由于阈值为0.因此物品
c 
和
e 
均可推荐给用户A
。


1 1 742 

× 
3×1≈0.
pAe 
=wAC 
·rAe 
+wAD 
·rAe = 

7, 

3.2 
协同过滤推荐算法应用实例
2.
在例3-3和例3-4中,都是假设用户对商品的感兴趣程度是1或0,而实际上,感兴趣
程度是通过用户的行为评估的。通常对用户的各种行为赋予不同的权重值,然后根据权
重值判断用户的感兴趣程度。

1. 
基于物品的协同过滤推荐算法实例
【例3-6】假设在电子商务网站中,用户的行为有以下4种。

(1)点击,用户点击了某个商品页面,设权重值为1分。
(2)搜索,用户在搜索栏搜索某种商品,设权重值为3分。
(3)收藏,用户收藏了某个商品,设权重值为5分。
(4)付款,设权重值为10 分
。
现有如下用户、商品和行为
:
用户:A、B、C;
商品:1、2、3、4、5、6;
行为:点击(1分)、搜索(3分)、收藏(5分)、付款(10 分)
。
网站记录的用户行为列表如图3-12(a)所示
。
基于物品的协同过滤推荐算法的执行步骤如下
。
(1)根据用户行为列表计算用户、物品的评分矩阵,如图3-12(b)所示。
(2)将用户、物品的评分矩阵中的用户行为转换成权重值,如图3-13(a)所示。显然, 
评分矩阵中的每个权重值,就代表了用户对物品的喜好程度。
82 


图3-12 用户行为列表与用户、物品的评分矩阵

(3)根据用户、物品的评分矩阵计算物品与物品的相似度矩阵。例如,使用余弦相似
度公式计算物品1和物品2之间的相似度,如图3-13(b)所示。
图3-13 根据用户、物品的评分矩阵计算物品与物品的相似度

按照该方法,对所有物品计算两两之间的相似度值,得到如图3-14 所示的物品与物
品之间的相似度矩阵。显然,相似度矩阵中的相似度值,就代表了物品与物品之间的相
似度。


图3-14 物品与物品之间的相似度矩阵

(4)相似度矩阵(相似程度)×评分矩阵(喜好程度)=推荐列表,如图3-15 所示。
得到的推荐列表如图3-16 所示。
83 


图3-15 相似度矩阵×评分矩阵

(5)根据推荐列表,将推荐值最高的若干种物品推荐给用户,如图3-17 所示。当然, 
也可先将用户已经购买过的物品推荐值置为0。
图3-16 得到的推荐列表图3-17 推荐权重值最高的物品

例如,对于用户
A 
来说,推荐值最高的是物品6,因此可将物品6推荐给A。
总结:基于物品的协同过滤推荐算法步骤如下。

(1)根据用户行为列表计算用户、物品的评分矩阵。
(2)根据用户、物品的评分矩阵计算物品、物品的相似度矩阵。
(3)物品、物品相似度矩阵×用户、物品评分矩阵=推荐列表。
(4)将推荐列表中用户之前已经有过购买行为的元素推荐值置为0。
基于物品的协同过滤推荐算法的优缺点如下。
优点:两个物品之间的距离可能是根据成百上千万用户的评分计算得出的,因此这
个评分往往能在一段时间内保持稳定。因此,这种算法可以预先计算距离,其在线部分能
更快地生成推荐列表。
缺点:不同领域的最热门物品之间经常具有较高的相似度。这样,可能会给喜欢《算
法导论》的读者推荐《哈利波特》。为此,在运行这种算法时可以不纳入最畅销商品。

2. 
基于用户的协同过滤推荐算法实例
基于用户的协同过滤推荐算法的基本假设为:和我兴趣相似的人喜欢的商品,我也
会喜欢。对于例3-6,这种推荐算法的主要步骤如下。

(1)根据用户对各种物品的偏好值的相似程度,在每两个用户之间进行相似度计算, 
84 


为每个用户找到与之相似度最高的几个邻居用户,这一步是对用户进行分类。

(2)将目标用户的邻居对每个物品的偏好值的加权平均作为目标用户偏好值的预测
值。把预测值最高的若干商品作为目标用户的推荐列表。
其中,每个邻居用户的权重取决于该邻居用户与目标用户之间的相似度。
算法具体步骤如下。

(1)根据用户行为列表计算物品、用户的评分矩阵。
(2)根据用户、物品的评分矩阵计算用户、用户的相似度矩阵。
(3)用户与用户相似度矩阵×评分矩阵=推荐列表。
(4)将推荐列表中用户之前已经有过购买行为的元素推荐值置为0。
基于用户的协同过滤推荐算法的缺点是:①形成有意义的邻居集合很难,很多用户
两两之间只有很少几个共同评分,而仅有的共同打了分的物品,往往是最热门的商品。

②用户之间的距离可能变化得很快,这让离线算法难以瞬间更新推荐结果。
3. 
在协同过滤算法中考虑时间和地域的因素
在协同过滤推荐算法中,还应考虑时间和地域的因素。这是因为用户对商品的喜好
具有时效性。为此,在基于物品的协同过滤中:①物品之间的相似度可以改为,同一用户
在间隔很短的时间内喜欢的两件商品之间,可以给予更高的相似度。②根据当前用户的
偏好,推荐相似的物品给他,可以改为,在描述目标用户偏好时,给其最近喜欢的物品赋予
较高权重。在基于用户的协同过滤中,计算相似度和描述用户行为时,都给最新的偏好赋
予较高权重。

在协同过滤中要考虑到地域因素,因为不同地域的用户对商品的偏好往往是有区别
的。为此,在基于物品的协同过滤中,物品之间的相似度可以改为,同一用户在同一地域
内喜欢的两件商品之间,可以给予更高的相似度。在基于用户的协同过滤中,把类似地域
用户的行为作为推荐的主要依据。

4. 
协同过滤推荐算法的特点
协同过滤推荐算法有下列优点。

(1)不需要根据内容计算物品之间的相似性,使得某些物品(如艺术品、音乐、视频) 
即使机器无法对其内容进行分析,也能使用协同过滤推荐算法。
(2)能够基于一些复杂的、难以表达的概念(信息质量、品位)进行过滤。
(3)推荐结果具有新颖性
。
协同过滤推荐算法有下列缺点
。
(1)系统刚使用时,用户对商品的评价非常少,这样,基于用户的评价所得到的用户
间(或物品间)的相似性可能不准确(即冷启动问题)。
(2)随着用户和商品的增多,系统的性能会越来越低。
(3)如果从来没有用户对某一商品加以评价,则这个商品就不可能被推荐(即最初评
价问题)。
85 

86 
3.3 电影节目推荐实例
目前,电影节目在智能电视和视频网站中日益丰富,使观众迅速从节目匮乏时代进入
内容过剩时代。用户在面对繁多的节目时,往往难以找到感兴趣的电影节目,这不仅影响
了收视用户的收看感受,也在某种程度上影响到电影节目的收视率。为了给用户推荐个
性化的电影节目,本实例采用MovieLens数据集作为样本数据,使用两种协同过滤推荐
算法向用户推荐相似电影,并比较两种算法的推荐结果。
MovieLens数据集包含许多用户对很多部电影的评分数据,也包括电影元数据信息
和用户属性信息。这个数据集经常用来做推荐系统、机器学习算法的测试数据集。根据
这些电影评分数据,就可计算出电影的相似度或用户的相似度,然后根据相似度推荐相似
电影给用户。该数据集的下载地址为http://files.grouplens.org/datasets/movielens/, 
它有多种版本,对应不同数据量,本例所用的数据为1MB的数据集(u.data)。该数据集
包含来自943个用户以及1682部电影的总计10万条电影评分记录。
文件里的内容包含了每个用户对每部电影的评分。数据格式如下。 
userId(用户id), movieId(电影的id), rating(用户评分,是5 星制,按半颗星的规模递
增), timestamp(时间戳) 
例如:{196 242 3 881250949}就是一条评分记录。
【程序3-2】 使用两种协同过滤推荐算法向用户推荐相似电影,并评估两种算法的
推荐结果。 
import numpy as np 
import pandas as pd #用pandas 库读取u.data 文件
#数据文件格式: 用户id、商品id、用户评分、时间戳
header=['user_id', 'item_id', 'rating', 'timestamp'] 
df=pd.read_csv('u.data', sep='\t', names=header) #读取u.data 文件
#计算唯一用户和电影的数量
n_users=df.user_id.unique().shape[0] 
n_items=df.item_id.unique().shape[0] 
print('Number of users='+str(n_users)+' | Number of movies='+str(n_items)) 
from sklearn.model_selection import train_test_split 
train_data, test_data=train_test_split(df, test_size=0.2, random_state=21) 
#协同过滤推荐算法
#第一步是创建user-item 矩阵,这需创建训练和测试两个user-item 矩阵
train_data_matrix=np.zeros((n_users, n_items)) 
for line in train_data.itertuples(): 
train_data_matrix[line[1]-1, line[2]-1]=line[3] 
test_data_matrix=np.zeros((n_users, n_items)) 
for line in test_data.itertuples():