关联规则挖掘算法
设
为所有项目的集合，
为事务数据库，事物
是一个项目子集（
）。每一个事务具有唯一的事务标识
。设
是一个由项目构成的集合，称为
。事务
包含项集
，当且仅当
。如果项集
中包含
个项目，则称其为
项集
在事务数据库
中出现的次数占总事务的百分比叫做项集的
。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是
关联规则是形如
的逻辑蕴含式，其中
，且
如果事务数据库D中有
的事务包含
， 则称关 联规则
的⽀持度为
关联规则的信任度为
也就是：
强关联规则就是⽀持度和信任度分别满⾜⽤户 给定阈值的规则
例子
交易ID | 购买的商品 |
|---|---|
2000 | A,B,C |
1000 | A,C |
4000 | A,D |
5000 | B,E,F |
设最⼩⽀持度为50%, 最⼩可信度为 50%, 则可得到
- A ⇒ C (50%, 66.6%)
- C ⇒ A (50%, 100%)
Apriori算法
命名源于算法使⽤了频繁项集性质的先验（ Prior） 知识。
Apriori算法将发现关联规则的过程分为两个步骤：
- 通过迭代， 检索出事务数据库中的所有频繁 项集， 即⽀持度不低于⽤户设定的阈值的项集；
- 利⽤频繁项集构造出满⾜⽤户最⼩信任度的 规则。
- 挖掘或识别出所有频繁项集是该算法的核⼼， 占整个 计算量的⼤部分
Apriori的性质
性质1： 频繁项集的所有⾮空⼦集必为频繁项集。
性质2： ⾮频繁项集的超集⼀定是⾮频繁的。
Apriori的步骤
连接步： 为找Lk，通过将Lk-1与⾃⾝连接产⽣候选k项集 的集合
剪枝步： Ck是Lk 的超集， 也就是说， Ck的成员可以是 也可以不是频繁的， 但所有的频繁k项集都包含在Ck中。 任何⾮频繁的（ k-1） 项集都不是频繁k项集的⼦集
Apriori算法实例
现有A、 B、 C、 D、 E五种商品的交易记录表， 试找出 三种商品关联销售情况(k=3)， 最小支持度=50%
交易号 | 商品代码 |
|---|---|
100 | A,C,D |
200 | B,C,E |
300 | A,B,C,E |
400 | B,E |
读入数据
data = {'交易号':range(100,500,100),'商品代码':['A,C,D', 'B,C,E', 'A,B,C,E', 'B,E']}
df_data = pd.DataFrame(data=data)算一个事务集在事务数据库的支持度
def get_score(values):
score = 0.0
b = True
for value_code in df_data['商品代码'].values:
b = True
for value in values:
if value not in value_code:
b = False
break
if b is True:
score += 1
return score/len(df_data)首先构造等候集C
c = []
for code in df_data['商品代码'].values:
for _ in code.split(','):
if {_} not in c:
c.append({_})输出c
[{'A'}, {'C'}, {'D'}, {'B'}, {'E'}]计算L
from collections import defaultdict
score = 0.5
# 这里用字典来保存频繁项集
L = defaultdict(list)
i = 0
length = len(c)
while c:
i += 1
for ci in c:
if get_score(ci) >= score:
L[i].append(ci)
print L[i]
c = get_c(L[i])[set(['A']), set(['C']), set(['B']), set(['E'])]
[set(['A', 'C']), set(['C', 'B']), set(['C', 'E']), set(['B', 'E'])]
[set(['C', 'B', 'E'])]可以得出三种商品关联销售情况(k=3)， 最小支持度=50%只有一组（CBE）
Apriori算法的不⾜
中的项集是⽤来产⽣频集的候选集.
- 最后的频集
必须是
的⼀个⼦集。
中的每个元素需在交易数据库中进⾏验证来决定其是否加 ⼊
- 验证过程是性能瓶颈 交易数据库可能⾮常⼤ ⽐如频集最多包含10个项， 那么就需要扫描交易数据库10遍 需要很⼤的I/O负载。
腾讯云开发者
