推荐算法之模型协同过滤(1)-- 关联规则

一、概念

1、关联规则

关联规则是数据挖掘中的典型问题之一,又被称为购物篮分析,这是因为传统的关联规则案例大多发生在超市中,例如所谓的啤酒与尿布传说。事实上,“购物篮”这个词也揭示了关联规则挖掘的一个重要特点:以交易记录为研究对象,每一个购物篮(transaction)就是一条记录。关联规则希望挖掘的规则就是:哪些商品会经常在同一个购物篮中出现,其中有没有因果关系。为了描述这种“经常性”及“因果关系”,分析者定义了几个指标,基于这些指标来筛选关联规则,从而得到那些不平凡的规律。

2、关联规则的计算

名词解释
事务:每一条交易称为一个事务
项:交易的每一个物品称为一个项,例如Cola、Egg等。
项集:包含零个或多个项的集合叫做项集,例如{Cola, Egg, Ham}。
k−项集:包含k个项的项集叫做k-项集,例如{Cola}叫做1-项集,{Cola, Egg}叫做2-项集。
频繁项集:支持度大于或等于某个阈值的项集就叫做频繁项集。例如阈值设为50%时,因为{Diaper, Beer}的支持度是75%,所以它是频繁项集。

(1)计算支持度
支持度计数:一个项集出现在几个事务当中,它的支持度计数就是几。例如{Diaper, Beer}出现在事务 002、003和004中,所以它的支持度计数是3
支持度:支持度计数除于总的事务数。例如上例中总的事务数为4,{Diaper, Beer}的支持度计数为3,所以它的支持度是3÷4=75%,说明有75%的人同时买了Diaper和Beer。

(2)计算置信度
置信度:对于规则{Diaper}→{Beer},{Diaper, Beer}的支持度计数除于{Diaper}的支持度计数,为这个规则的置信度。例如规则{Diaper}→{Beer}的置信度为3÷3=100%。说明买了Diaper的人100%也买了Beer。

3、关联规则与物品协同过滤

一般地,关联规则被划分为动态推荐,而协同过滤则更多地被视为静态推荐。
所谓动态推荐,就是推荐的基础是且只是当前一次(最近一次)的购买或者点击。譬如用户在网站上看了一个啤酒,系统就找到与这个啤酒相关的关联规则,然后根据这个规则向用户进行推荐。而静态推荐则是在对用户进行了一定分析的基础上,建立了这个用户在一定时期内的偏好排序,然后在这段时期内持续地按照这个排序来进行推荐。由此可见,关联规则与协同过滤的策略思路是完全不同的类型。
事实上,即便在当下很多能够拿到用户ID的场景,使用动态的关联规则推荐仍然是值得考虑的一种方法(尤其是我们经常把很多推荐方法的结果综合起来做一个混合的推荐),因为这种方法的逻辑思路跟协同过滤有着本质的不同,问题似乎仅仅在于:个人的偏好到底有多稳定,推荐到底是要迎合用户的长期偏好还是用户的当下需求。

二、实现关联规则推荐

挖掘关联规则主要有Apriori算法和FP-Growth算法。后者解决了前者由于频繁的扫描数据集造成的效率低下缺点。以下按照Apriori算法来讲解。

1、执行步骤

step 1:扫描数据集生成满足最小支持度的频繁项集。
step 2:计算规则的置信度,返回满足最小置信度的规则。

2、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
# coding=utf-8
'''
基于Apriori算法的关联规则推荐
'''
import numpy as np

#========================================================
# 测试数据
#========================================================

def loadDataSet():
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5], [1, 2, 3, 5], [1, 2, 3, 5]]

#========================================================
# 生成候选1项集、候选k项集
#========================================================

def createC1(dataSet):
'''
生成候选1项集
INPUT -> 事务集(购物篮)
'''
C1 = []
for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
# 这里的排序是为了在生成新的候选集时可以直接认为两个n项候选集前面的部分相同
C1.sort()
return list(map(frozenset, C1)) # map(frozenset, C1)的语义是将C1由Python列表转换为不变集合

def createCk(C1, L_temp, k):
'''
由k-1项频繁集生成候选k项集
INPUT -> 候选1项集, 当前的频繁项集, 目标项数
'''
Ck = []
lenLt = len(L_temp)
for i in range(lenLt):
for j in C1:
LL = L_temp[i]|j
if LL not in Ck and len(LL)==k:
Ck.append(LL)
return Ck

#========================================================
# 发现频繁项集
#========================================================

def supportCount(dataSet, Ck):
'''
计算支持度计数
INPUT -> 事务集(购物篮), 候选项集
'''
sCount = {} # 支持度计数
for transaction in dataSet:
for candidate_items in Ck:
if candidate_items.issubset(transaction):
sCount[candidate_items] = sCount.get(candidate_items, 0) + 1
return sCount

def scanD(dataSet, Ck, minSup):
'''
从候选项集Ck中发现频繁项集Lk
INPUT -> 事务集(购物篮), 候选项集, 最小支持度
'''
sCount = supportCount(dataSet, Ck)

Lk = []
supportData = {}
for candidate_items in sCount:
support = sCount[candidate_items] / float(len(dataSet)) # 支持度 = 某项集的支持度计数/总记录数
if support >= minSup:
Lk.insert(0, candidate_items) # 将频繁项集插入返回列表的首部
supportData[candidate_items] = support

return Lk, supportData # Lk为在Ck中找出的频繁项集(支持度大于minSupport的),supportData记录各频繁项集的支持度

#========================================================
# 得到满足最小支持度的规则
#========================================================

def calcSupport(dataSet, minSup=0.5, k=2):
'''
获取事务集中的所有的频繁项集
INPUT -> 事务集(购物篮), 最小支持度, 频繁项集大小
'''
# 初始项数
n = 1
# 从事务集中获取候选1项集
C1 = createC1(dataSet)
# 获取频繁1项集和对应的支持度
F1, supportData = scanD(dataSet, C1, minSup)

# 符合条件的频繁集和其支持度
output = []
output_supportData = {}

F_temp = F1
while (n <= k):
# 根据频繁项集生成新的候选项集。Ck表示项数为k的候选项集
Ck = createCk(C1, F_temp, n+1)
F_temp = []

Fk, supK = scanD(dataSet, Ck, minSup)
if Fk == []:
break
else:
for i in range(len(Fk)):
F_temp.append(Fk[i])
if len(Fk[i]) == k: # 符合长度要求
output.append(Fk[i])
output_supportData[Fk[i]] = supK[Fk[i]]
n += 1
return output, output_supportData

#========================================================
# 得到满足最小置信度的规则
#========================================================

def calcConfidence(dataSet, Fk, minConf=0.5):
'''
计算规则的置信度,返回满足最小置信度的规则
INPUT -> 事务集(购物篮), 频繁k项集, 最小置信度
'''
C1 = createC1(dataSet)
C1_sCount = supportCount(dataSet, C1) # 频繁项集中每一个元素的支持度计数
Fk_sCount = supportCount(dataSet, Fk) # 频繁项集中每一个项集的支持度计数

TrustedR = {}
for freq_items in Fk:
for item in freq_items:
conf = Fk_sCount[freq_items] / C1_sCount[frozenset({item})]
if conf >= minConf:
TrustedR[item] = [x for x in freq_items if x != item]
return TrustedR

#========================================================
# Apriori算法
#========================================================

def Apriori(dataSet, k=2, minSup=0.5, minConf=0.5):
'''
Apriori算法,先挖掘频繁集再用置信度过滤
INPUT -> 数据集, 项数, 最小支持度, 最小置信度
'''
Fk, suppData = calcSupport(dataSet, minSup=minSup, k=k)
TrustedR = calcConfidence(dataSet, Fk, minConf=0.5)
return TrustedR

#========================================================
# 主程序
#========================================================

if __name__=='__main__':
dataSet = loadDataSet() # 获取事务集。每个元素都是列表
TrustedR = Apriori(dataSet, k=3, minSup=0.5, minConf=0.5)
print(TrustedR)

如下所示,当用户购买1商品时推荐2、3商品

0%